Теория алгоритмов. Зюзысов В.М. - 45 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Формулу F: «F недоказуема в EA» мы могли бы получить из леммы о рефлексии,
если бы сумели изобразить в виде формулы EA свойство «формулу с номером x можно
доказать в EA».
Определим отношение на множестве замкнутых термов в элементарной
арифметике Prove(d, t):
« формула с гёделевым номером t имеет доказательство
с номером d».
Разумеется, по номеру можно определить, является ли он номером доказательства,
принадлежащего теории EA. В самом деле, по номеру последовательности можно
восстановить все входящие в нее формулы и порядок их расположения. Затем мы можем
проверить, является ли каждая из этих формул аксиомой EA (логической или собственной)
или же
она получена из предыдущих формул последовательности с помощью правил
вывода. Если для всех формул это так – анализируемый номер представляет
доказательство. Можно построить даже программу, реализующую эту процедуру
проверки без всякого вмешательства человека.
Геделева нумерация формул и доказательств элементарной арифметики проводится
таким образом, чтобы было выразимым отношение Prove, т.е. чтобы выполнялось
утверждение
«теорема y имеет доказательство x тогда и только тогда, когда |– Prove(g(x),g(y))».
Введем формулу Pr(t) как сокращение для формулы ∃d Prove(d,t). Предикат Pr(t)
утверждает доказуемость теоремы с гёделевым номером t.
Описанную выше гёделеву нумерацию можно провести таким образом, чтобы для
любой формулы A элементарной арифметики из |– A следует |– Pr(g(A)).
Нам понадобится следующее определение.
ω-противоречие
Формула в теории первого порядка C(y) с одной свободной переменной y такая, что
а) |– ∃yC(y),
б) для каждого n: |– ¬C(n)
называется ω-противоречием.
Формула C(y) не дает «настоящего» противоречия (доказательства формулы вместе с ее
отрицанием). Однако, если подобная формула C(y) имеется, это означает все же, что в
теории «не все в порядке».
Можно доказать, что «настоящее» противоречие (т.е. формула D такая, что |– D и
одновременно |– ¬D) означает также ω-противоречие
.
Теорема 23 (теорема Гёделя о неполноте, 1931). Можно построить замкнутую
формулу G из языка EA, такую, что
1) если G доказуема в EA, то теория EA противоречива,
2) если ¬G доказуема в EA, то теория EA ω-противоречива.
Доказательство. Взяв в лемме о рефлексии формулу ¬Pr(t) («формула с номером t
не имеет доказательства в EA»), получим замкнутую формулу G, такую, что
|– G ~ ¬Pr(g(G)).
Формула G утверждает, что она недоказуема в EA. Теперь можно попытаться выяснить
какое из двух утверждений |– G или |– ¬G выполнено. Разбор случаев приводит
соответственно к утверждениям, что теория EA противоречива или ω-противоречива. Но
мы не можем узнать, как «на самом деле» обстоит с доказуемостью G.
Если теория EA ω-непротиворечива, то теорема Гёделя утверждает, что обе
формулы G и ¬G нельзя доказать средствами EA. Но тогда недоказуемая формула G при
стандартной интерпретации на универсуме натуральных чисел является истинной,
поскольку она утверждает свою недоказуемость.

Страницы