Лекция 13. Теорема Геделя о неполноте

Язык первого порядка L_ называется расширением языка первого по-

рядка L, если каждый нелогический символ из L является нелогическим

символом в L_.

Теория T_ называется расширением теории T, если выполнены следу-

ющие условия.

1. Язык теории T_ является расширением языка теории T.

2. Каждая теорема теории T является теоремой теории T_.

Ясно, что для 2 необходимо и достаточно, чтобы каждая нелогическая ак-

сиома теории была теоремой теории T_ ( но не обязательно, чтобы каждая

нелогическая аксиома теории была нелогической аксиомой теории T_).

Рассмотрим теорию N, которая описываем основные свойства нату-

ральных чисел. Она имеет следующую систему аксиом.

N1. Sx _= 0. N6. x · Sy = (x · y) + x.

N2. Sx = Sy → x = y. N7. ￢(x < 0).

N3. x + 0 = x. N8. x < Sy ↔ x < y ∨ x = y.

N4. x + Sy = S(x + y). N9. x < y ∨ x = y ∨y < x.

N5. x · 0 = 0.

В большинстве математических теорий нам потребуются основные

свойства натуральных чисел. Поэтому вполне естественно считать, что

эти теории являются расширением теории N.

Следующее естественное условие, предъявляемое к теориям – воз-

можность проверять доказательство теорем. Одним из действий при про-

верке доказательства является распознавание аксиом. Обозначим мно-

жество формул теории T через F, а множество аксиом через F1. Мы

должны иметь алгоритм, позволяющий для произвольной формулы A

теории T определять является ли она аксиомой. Такие теории назовем ре-

курсивно аксиоматизированными.

Такая постановка может странной, т.к. в реальных случаях мы имеем

обычно конечный или бесконечный, но достаточно простой список акси-

ом.Однако, такое ограничение не является естественным. Приведем при-

мер, где вид аксиом не столь прозрачен.

Теория структуры A. Пусть T — теории первого порядка с языком

L. Рассмотрим произвольную структуру A для языка L теории T. Введем

новую теорию T_ с языком L. Нужно задать только аксиомы для теории

T

_ . Рассмотрим произвольную формулу A теории T. Считаем ее аксиомой

для теории T_ тогда и только тогда, когда формула A истинна в структуре

A. Полученная теории T_ называется теорией структуры A.

Упражнение. Доказать, что понятие теоремы и аксиомы в теории T_

совпадают.

Теория T называется противоречивой, если каждая формула теории T

является теоремой теории T; в противном случае T называется непроти-

воречивой.

Теория T называется полной, если для каждой замкнутой формулы A

теории T ровно одна из формул A или ￢A является теоремой теории T.

Замкнутая формула A не имеет свободных переменных и не может

иметь разных значений при интерпретациях. В обычной математической

практике мы рассматриваем замкнутую формулу A как некоторое выска-

зывание о объектах теории. Поэтому либо высказывание A, либо выска-

зывание ￢A является истинным высказыванием и мы надеемся получить

A или ￢A как теорему формальной системы. Однако это не всегда дости-

жимо.

ТЕОРЕМА 19 (о неполноте, К.Гедель) Пусть T —рекурсивно ак-

сиоматизированная теории первого порядка T, являющаяся рас-

ширением теории N. Тогда теории T неполна.

Доказательство теоремы достаточно сложное и опускается.

Теорема неполноте имеет важные следствия, касающиеся аксиомати-

ческого метода. Идея аксиоматического метода состоит в следующем.

Пусть имеется некоторая неаксиоматическая теорию T0, для которой

мы хотим построить соответствующую аксиоматическую теорию T. В

теории T0 мы используем некоторые функции и предикаты для выраже-

ния понятий теории T0 о ее объектах.

При переходе к аксиоматическому построению теории мы вводим язык

для выражения утверждений о понятиях теории T0. Для этого вводим

язык первого порядка L теории T.После задания языка мы получаем сле-

дующую ситуацию. Если A –замкнутая формула языка L, то представляя

те функции и предикаты для для конкретных объектов теории T0, мы при-

пишем ей значение истина или ложь. Те формулы, которые имеют значе-

ние истина—это истинные утверждения об объектах неаксиоматической

теории T0. Теперь мы хотим разделить их на два типа: аксиомы и теоремы,

полученные из аксиом с помощью правил вывода теории T. Наше есте-

ственное требование истинные утверждения про объекты неаксиоматиче-

ской теории T0 должны выводиться из аксиом в аксиоматической теории

T.

Требование, чтобы мы могли опознавать доказательство, означает (как

отмечалось ранее), чтобы наша теория T должна быть рекурсивно ак-

сиоматизированной. Естественно мы должны среди аксиом затребовать

простейшие свойства натуральных чисел, выраженные в аксиомах тео-

рии N( т.е. теория должна быть расширением теории N). Однако по тео-

реме К.Геделя о неполноте существует некоторая замкнутая формула A

языка L такая, что ни A ни ￢A не являются теоремой теории T. Поэтому

мы имеем A или ￢A – истинное утверждение об объектах теории T0, кото-

рое нельзя получить средствами вывода в аксиоматической теории T. Это

показывает невыполнимость первоначального замысла Гильберта свести

все содержательное математическое познание к формализму.