Математическая энциклопедия - неразрешимость

невозможность решения данной задачи точно очерченными средствами. Ниже рассмотрены важнейшие примеры Н. в математике.

Алгоритмическая неразрешимость. В различных областях математики возникают проблемы, в к-рых требуется найти единую механич. процедуру ( алгоритм), с помощью к-рой можно было бы решить любую задачу из данного бесконечного класса однотипных задач. Такие проблемы наз. массовыми проблемами. Примером может служить 10-я проблема Гильберта, состоящая в построении алгоритма, к-рый позволил бы для любого заданного многочлена с целыми коэффициентами узнать, существуют ли целые значения переменных, обращающие этот многочлен в нуль. Многие массовые проблемы долгое время не поддавались решению; впоследствии оказалось, что трудность их решения имеет принципиальный характер. Это удалось установить лишь после того, как в 30-х гг. 20 в. в математич. логике было выработано точное понятие алгоритма и для нек-рых массовых проблем было доказано, что искомые в них алгоритмы не существуют. Такие массовые проблемы наз. неразрешимыми, или алгоритмически не разрешимыми. Неразрешимыми оказались многие другие алгоритмич. проблемы из различных областей математики, в частности 10-я проблема Гильберта (см. также Алгоритмическая проблема).

Установление алгоритмической Н. данной массовой проблемы показывает, что для решения каждой конкретной задачи из рассматриваемого класса требуется свой специфический для этой задачи метод, т. к. единого метода решения всех этих задач не существует.

Неразрешимые предложения. Одним из способов построения математич. теории является аксиоматический метод. При аксиоматич. построении теории ряд ее положений принимается в качестве исходных, или аксиом, а другие получаются как их следствия. В работах Д. Гильберта (D. Hilbert) и его школы понятие аксиоматич. теории было уточнено в виде понятия формальной системы. Намеченная Д. Гильбертом программа обоснования математики предусматривала, в частности, формализацию основных разделов математики арифметики, анализа, теории множеств, т. е. построение формальной системы, из аксиом к-рой можно было бы вывести практически все математич. теоремы. Однако в 1931 К. Гёдель (К. Godel) показал, что всякая формальная система арифметики неполна в том смысле, что можно указать предложение, к-рое в этой системе нельзя ни доказать, ни опровергнуть (т. е. доказать его отрицание). Такие предложения наз. неразрешимыми, или формально неразрешимым и, в данной системе. В частности, для всякой непротиворечивой формальной системы, содержащей достаточно богатую часть арифметики, утверждение о непротиворечивости этой системы оказывается неразрешимым в ней (см. Гёделя теорема о неполноте).

Н. предложения в данной формальной системе означает, что невозможно убедиться в его истинности или ложности на основании лишь тех представлений об исследуемом объекте, к-рые выражены в аксиомах и правилах вывода. Часто оказывается возможным расширить формальную систему за счет новых аксиом таким образом, чтобы нек-рое конкретное неразрешимое в ней предложение можно было доказать или опровергнуть в получившейся системе. Обнаружение в аксиоматич. теории неразрешимых предложений имеет важное значение для развития этой теории, т. к. стимулирует поиск новых фундаментальных положений, к-рые можно было бы принять в качестве аксиом.

Примером Н. в элементарной математике является Н. таких геометрич. задач на построение, как трисекция угла и квадратура круга при помощи циркуля и линейки.

Лит.:[1] Гильберт Д., Бернайс П., Основания математики. Логические исчисления и формализация арифметики, пер. с нем., М., 1979.

В. Е. Плиско.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985