ГЁДЕЛЯ ТЕОРЕМА О НЕПОЛНОТЕ это:

ГЁДЕЛЯ ТЕОРЕМА О НЕПОЛНОТЕ

общее название двух теорем, установленных К. Гёделем [1]. Первая Г. т. о н. утверждает, что в любой непротиворечивой формальной системе, содержащей минимум арифметики ( знаки и обычные правила обращения с ними), найдется формально неразрешимое суждение, т. е. такая замкнутая формула А, что ни А, ни не являются выводимыми в системе. Вторая Г. т. о н. утверждает, что при выполнении естественных дополнительных условий в качестве Аможно взять утверждение о непротиворечивости рассматриваемой системы. Эти теоремы знаменовали неудачу первоначального понимания программы Гильберта в области оснований математики, к-рая предусматривала полную формализацию всей существующей математики или значительной ее части (невозможность этого показала первая Г. т. о н.) и обоснование полученной формальной системы путем .финитного доказательства ее непротиворечивости (вторая Г. т. о н. показала, что даже если финитными считаются все средства формализованной арифметики, этого не хватит уже для доказательства непротиворечивости арифметики).

Формально неразрешимое суждение строится методом арифметизации синтаксиса, к-рый стал одним из основных методов теории доказательств (метаматематики).

Фиксируется нумерация основных формальных объектов (формул, конечных последовательностей формул и т. д.) натуральными числами такая, что основные свойства этих объектов (быть аксиомой, быть выводом по правилам системы и т. д.) оказываются распознаваемыми по их номерам с помощью весьма простых алгоритмов. Столь же просто вычисляются по номерам исходных данных номера результатов комбинаторных преобразований (напр., подстановки терма в формулу вместо переменной). При этом оказывается возможным написать арифметич. формулу В( а,b), имеющую вид (f - примитивно рекурсивная функция) и выражающую условие: b есть номер формулы, к-рая получается из формулы с номером апутем подстановки натурального числа авместо переменной х. Если р - номер формулы то формула выражает свою собственную невыводимость. Она и оказывается формально неразрешимой. Отсюда следует, что в любой непротиворечивой системе с минимальными выразительными арифметическими возможностями имеется истинное, но не выводимое суждение указанного вида.

Вторая Г. т. о н. получается путем формализации доказательства первой Г. т. о н. Ее доказательство существенно использует особенности арифметизации синтаксиса рассматриваемой системы, а именно - требуется выводимость в этой системе формул, выражающих суждения: 1) система замкнута относительно правила сокращения посылки (модус поненс);2) система замкнута относительно подстановки термов вместо предметных переменных; 3) из истинности формулы вида , где N - натуральное число, f - примитивно рекурсивная функция, следует ее выводимость. Эти условия выполняются для естественной арифметизации, но можно, не меняя алгорифмич. характеристик арифметизации (все функции и предикаты остаются примитивно рекурсивными), изменить ее так, что формула, выражающая непротиворечивость системы (применительно к новой арифметизации), будет выводима. При этом для новой арифметизации будет нарушено условие 1).

Вторая Г. т. о н. дает критерий сравнения формальных систем: если в системе Sможно доказать непротиворечивость системы Т, то Sне погружается в Т(см. Погружающая операция). Так, доказывается, что формальный математический анализ не погружается в арифметику, типов теория не погружается в анализ, теория множеств Zне погружается в теорию типов.

Лит.:[1] Godе1 К., "Monatshefte fur Math, und Phys.", 1931, Bd 38, S. 173-98: [2] Hi1bеrt D., Веrnауs P, Grundlagcn der Mathematik, 2 Aufl., Bd 2, В., 1970; [3] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957.

Г. Е. Минц.


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

Смотреть что такое "ГЁДЕЛЯ ТЕОРЕМА О НЕПОЛНОТЕ" в других словарях:

  • ГЁДЕЛЯ ТЕОРЕМА — важнейший результат, полученный австр. логиком и математиком К. Гёделем. В 1931 в ст. «О формально неразрешимых предложениях Pnncipia Mathematica и родственных систем» Гёдель доказал теорему о неполноте: если система Z(содержащая арифметику… …   Философская энциклопедия

  • гёделя теорема — важнейший результат, полученный австрийским логиком и математиком К. Гёделем (1906 1978). В 1931 г. в статье О формально неразрешимых предложениях Principia Mathematica и родственных систем Гёдель доказал теорему о неполноте: если система Z… …   Словарь терминов логики

  • Теорема Гёделя о неполноте — У этого термина существуют и другие значения, см. Теорема Гёделя. Теорема Гёделя о неполноте и вторая теорема Гёделя[ 1]  две теоремы математической логики о принципиальных ограничениях формальной арифметики и, как следствие, всякой… …   Википедия

  • Теорема Гёделя — Теорема Гёделя: Теорема Гёделя о полноте, или Первая теорема Гёделя (1929 год) Теорема Гёделя о неполноте, или Вторая теорема Гёделя (1930 год) …   Википедия

  • Теорема Гёделя —    гласит, что в широком классе систем, в которых вообще существуют понятия утверждения и доказательства (например, математика), существуют утверждения, которые не могут быть ни опровергнуты, ни доказаны; данное утверждение широко используется за …   Мир Лема - словарь и путеводитель

  • Теорема Гёделя о полноте — У этого термина существуют и другие значения, см. Теорема Гёделя. Теорема Гёделя о полноте исчисления предикатов является одной из фундаментальных теорем математической логики: она устанавливает однозначную связь между логической истинностью… …   Википедия

  • Теоремы Гёделя о неполноте — Теоремы Гёделя о неполноте  две теоремы математической логики о принципиальных ограничениях формальной арифметики и, как следствие, всякой достаточно сильной[1] теории первого порядка. Первая теорема утверждает, что если формальная… …   Википедия

  • Вторая теорема Гёделя — Теоремы Гёделя о неполноте две теоремы математической логики о неполноте формальных систем определённого рода. Содержание 1 Первая теорема Гёделя о неполноте 2 Вторая теорема Гёделя о неполноте …   Википедия

  • ГЁДЕЛЬ — (Godel) Курт (1906 1978) австр. логик и математик. Участвовал в работе Венского кружка. В 1933 1939 приват доцент Венского ун та, в 1940 эмигрировал в США, с 1953 проф. Ин та высших исследований в Принстоне. Г. принадлежат ряд важнейших… …   Философская энциклопедия

  • ТЕОРЕМА — (от греч. theoreo – рассматриваю) научное положение. Философский энциклопедический словарь. 2010. ТЕОРЕМА (греч. ϑεώρημα, от ϑεωρέω – рассматриваю, исследу …   Философская энциклопедия

Книги



Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»