yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->6. 6. Теорема Геделя о неполноте.

Математическая логика

6. 6. Теорема Геделя о неполноте.

Пусть К - теория первого порядка с теми же самыми символами, что и S. Теория К называется   -непротиворечивой, если для всякой формулы А(х.) этой теории из того, что при любом n |-A(n), следует невозможность |-kx¬A(х). Если мы признаем стандартную интерпретацию теории S в качестве модели этой теории, то тогда теорию S следует признать -непротиворечивой.

 Теорема 6.8. Если теория К -непротиворечива, то она непротиворечива.

Доказательство. Пусть теория К -непротиворечива. Рассмотрим какую-нибудь выводимую в К формулу А(х) со свободной  переменной, например:x=xх=х.  При любом  n  имеем,  очевидно,  |-kn=nn=n.  Поэтому  формула х¬(x=хx=x) не выводима в К. Следовательно, теория К непротиворечива (ибо, в силу тавтологии ¬A (AВ),  из противоречивости  К  следовала бы выводимость в К любой формулы).

Рассмотрим отношение W1(u.y).

Отношение   W1(u,y)   примитивно   рекурсивно   и   потому   выразимо   в   S некоторой формулой W(x1,x2) с двумя свободными переменными х1, х2. Это значит что если W1(k1,k2) истинно, то |-s W(k1,k2), и если W1(k1,k2) ложно, то |-s¬ W(k1,k2). Рассмотрим теперь формулу

x2 ¬W(x1,x2).                                           (*).

Пусть m есть геделев номер формулы (*).Подставив в (*) m вместо х1, мы получим замкнутую формулу

x2¬ W(m,x2.).                                          (G).

Вспомним, что утверждение W1(u,y) истинно тогда и только тогда, когда u есть   геделев   номер  некоторой   формулы   А(х1),   содержащей   свободную переменную   х1,   а   у   есть   геделев   номер   вывода   в   S   формулы А(u).

Следовательно,

(1)   Если теория S непротиворечива, формула G не выводима в S.

(2)   Если теория S -непротиворечива, то формула ¬G не выводима в S

 (Таким образом, в силу теоремы 6.8, если теория S -не противоречива, то замкнутая формула G не выводима и неопровержима в S, замкнутые формулы, обладающие таким свойством, называются предложениями теории S.)

оряе

Доказательство (1) Предположим, что теория S непротиворечива и |-sx2 ¬W(m,x2). Пусть тогда k - геделев номер какого-нибудь вывода в S этой последней формулы. В силу (I), справедливо W1(m,k). Так как 1 выражает W, в S, то |-s W(m,k). Из x2¬ W(m,x2) по правилу А4 (универсальной конкретизации) мы можем вывести ¬W(m,k). Таким образом, в S оказываются выводимыми формулы W(m,k) и ¬W(m,k), что противоречит предположению о непротиворечивости S.

(2) Предположим, что теория S -не противоречива и |-s¬x2¬W(m,x2), т.е. |-s¬G. На основании теоремы 6.8, заключаем, что теория  S непротиворечива и, следовательно, не |-sG. Поэтому, каково бы ни было натуральное число n, n не есть геделев номер вывода в S формулы G, т.е. W1(m,n) ложно для любого n. А это значит, что |-s¬W(m,n) для любого n. Взяв в качестве формулы А(х2) формулу ¬W(m,x.2), мы, на основании предположения об -непротиворечивости теории S, заключаем, что не |-sx2¬¬W(m,x2) и- следовательно, не |-sx2W(m,x2). Мы пришли, таким образом, к противоречию с предположением, что |-sx2W(m,x2).

Рассмотрим стандартную интерпретацию неразрешимого предложения G: x2¬W(m.x2). Так как 1 выражает в S отношение W1, то, в соответствии со стандартной интерпретацией, G утверждает, что W1(m,x2) ложно для каждого натурального числа х2. Согласно (I), это означает, что не существует вывода формулы G в S. Другими словами, формула G утверждает свою собственную не выводимость в S. По теореме же Геделя, если только теория S непротиворечива, эта формула и в самом деле не выводима в S и потому истинна при стандартной интерпретации.

Итак, для натуральных чисел, соответствующих обычной интерпретации, формула G верна, но в S не выводима. Может показаться, что теорема Геделя потому справедлива для теории S, что первоначально выбранная для этой теории система аксиом оказалась слишком слабой и что, если бы мы усилили теорию S, добавив к ней новые аксиомы, то новая теория могла бы оказаться полной. Так, например, чтобы получить некоторую более сильную теорию S1, мы могли бы добавить к S истинную формулу G. Однако всякая рекурсивная функция, будучи представимой в S, представима также и в такой теории S1. Точно так же и теоремы 6.6, 6.7, 6.8 остаются, очевидно, в силе, если их переформулировать для S1. Но это и есть все, что требуется для того, чтобы получить результат Геделя; и потому, если теория S -непротиворечива, то и она имеет некоторое неразрешимое предложение В, (В имеет ту же форму x2¬ (W)Sl(k,x2), но, разумеется, будет отличаться от G, поскольку отношение W, для S, отлично от отношения W1 для S1 и, следовательно, формула (W)S1, и входящая в В цифра k отличны от формулы l и цифры m в G.)

В теореме Геделя содержится предположение о -непротиворечивости теории S. Однако, как показал Россер [1936], ценой некоторого усложнения доказательства можно с тем же успехом ограничиться предположением об обычной непротиворечивости теории S. Более того, была доказана аналогичная теорема для теории К.

Теорема 6.10. Пусть К есть теория первого порядка с теми же символами, что и теория S, и пусть, кроме того, К удовлетворяет  следующим условиям:

(1) всякое рекурсивное выражение выразимо в К,

(2) множество    геделевых    номеров собственных аксиом теории К рекурсивно,

(3) выполнены условия: имеется формула uv такая, что

(i) для всякой формулы А(х) и дли всякого натурального k.

                   |-kA(0)&A(1)&…&A(k) x(xkA(x))

(ii). для всякою натурального числа

|-kxkvkx.

Тогда для теории К справедлива  теорема Геделя в форме Россера,  т.е. если теория К непротиворечива, то существует неразрешимое в этой теории предложение. (Заметим, что, согласно теореме 6.1, условие (1) выполняется, ели в К представима каждая рекурсивная функция).

Определение   6.11.   Назовем  теорию   К  рекурсивно  аксиоматизируемой, если существует такая теория К' с тем же, что и у К, множеством теорем что множество РrAхk геделевых номеров собственных аксиом К' рекурсивно.

Следствие. Теорема Геделя в форме Россера справедлива для каждого непротиворечивого рекурсивно аксиоматизируемого расширения теории В, т.е. для каждого такого расширения существует предложение,  неразрешимое в нем.

Доказательство. Так как все рекурсивные отношения выразимы в S, то они выразимы и во всяком расширении S. Точно так же и условия (i)-(ii), будучи выполнены в S, выполнены и во всяком расширении S. Поэтому, на основании теоремы 6.10, Теорема Геделя в форме Россера применима к любому непротиворечивому рекурсивно аксиоматизируемому расширению теории S.

При изучении теории алгоритмов можно оценить все правдоподобие гипотезы, согласно которой точное понятие рекурсивного множества соответствует интуитивному понятию эффективно разрешимого множества. Гипотеза эта носит название тезиса Черча. Для всякого, кто принимает этот тезис. Последнее следствие утверждает, что теория S существенно неполна, т. е. Что любое Непротиворечивое эффективно аксиоматизированное расширение теории S имеет неразрешимые предложения.

 

 

 

 

42