24. Арифметика Пеано. Теорема Геделя о неполноте (В.А. Захаров - Лекции), страница 3

. , n̄k ) .Формальная арифметикаНумералы и арифметизуемые отношенияТеорема Геделя–Тьюринга.Отношение P (k) на множестве натуральных чиселарифметизуемо в том и только том случае, если существуеттакая машина Тьюринга M , которая для любого наборанатуральных чисел (n1 , n2 , . . . , nk ) имеет завершающеесявычисление, преобразующее начальную конфигурациюq1 11. . . 1} 0 11. . . 1} 0 . . .

0 11. . . 1}| {z| {z| {zn1 +1 раз n2 +1 разnk +1 разIв заключительную конфигурацию q0 1 , еслиP (k) (n1 , n2 , . . . , nk ) = true ,Iв заключительную конфигурацию q0 0 , еслиP (k) (n1 , n2 , . . . , nk ) = false .Формальная арифметикаНумерация ГеделяЗакодируем натуральными числами (занумеруем) символыалфавита формальной арифметики, формулы и конечныепоследовательности формул.gn(0) = 3, gn(s) = 5, gn(+) = 7, gn(×) = 9, gn(=) = 11,gn(¬) = 13, gn(&) = 15, gn(∨) = 17, gn(→) = 19,gn(∀) = 21, gn(∃) = 23,gn( ) = 25, gn( ) = 27,gn(x1) = 29, gn(x2) = 31, .

. . , gn(xi) = 27 + 2i, . . . .Геделев номер слова:gn(a )gn(a1 a2 a3 . . . an) = 2gn(a1) 3gn(a2) 5gn(a3) . . . pn n .Геделев номер последовательности слов:gn(α )gn(α1 α2 α3 . . . αm) = 2gn(α1) 3gn(α2) 5gn(α3 . . . pm m .Формальная арифметикаПримеры арифметизуемых отношенийРассмотрим два отношения1. Form(1) : Form(n) = true ⇐⇒ n — геделев номерформулы арифметики Пеано.2. Proof(2) : Proof(n, m) = true ⇐⇒ n — геделев номернекоторой формулы ϕ арифметики Пеано, а m — геделевномер конечной последовательности формул,составляющей доказательство формулы ϕ .ЛеммаОтношения Form и Proof арифметизируемы.Обозначим Proof арифметическую формулу, реализующуюпредикат Proof .Формальная арифметикаСтранные предикатыНу, если вы поверили, что предикат Proof(2) арифметизуем, тосовершенно очевидно, что арифметизуемым является и такойстранный предикат MetaProof(2) :MetaProof(n, m) = truemn — геделев номер некоторой формулы арифметики Пеано,ϕ(x) , зависящей от одной переменной,а m — геделев номер конечной последовательности формул,составляющей доказательство формулы ϕ(n̄) .Но если предикат MetaProof(2) арифметизуем, то существуетарифметическая формула W(x, y ) , выражающая отношениеMetaProof .Формальная арифметикаСтранные предикатыРассмотрим формулу ϕ(x) = ¬∃y W(x, y ) и ее геделев номерn0 = gn(ϕ(x)) .Интересно, а что за высказывание выражает замкнутаяформула ϕ(n̄0 ) ?Это высказывание таково: Нельзя доказать формулу ϕ(n̄0 ) ,т.

е. формула ϕ(n̄0 ) утверждает, что она недоказуема.Таким образом, мы имеем дело со строго сформулированныманалогом «парадокса лжеца».И если эта формула действительно не имеет доказательства варифметике Пеано, то она выражает истинное суждение.Теорема Геделя о неполноте PA(облегченный вариант)Если множество натуральных чисел с операциями сложения иумножения (N0 , +, ×) является моделью для аксиом PA, то PAнеполна.Доказательство.1. Покажем, что PA 6` ϕ(n̄0 ) .Допустим противное PA ` ϕ(n̄0 ) .

Тогда формула ϕ(n̄0 ) имеетдоказательство в PA: ψ1 , ψ2 , . . . , ψN = ϕ(n̄0 ).Пусть m = gn(ψ1 , ψ2 , . . . , ψN ) . Тогда MetaProof (n0 , m) = true .Поэтому, учитывая арифметизуемость предиката MetaProof ,получаем PA ` W(n̄0 , m̄) . Но это означает, чтоPA ` ∃y W(n̄0 , y ) и, следовательно, PA ` ¬ϕ(n̄0 ) .Но это означает, что PA — противоречивая теория, вопрекиусловию теоремы (PA имеет модель).Теорема Геделя о неполноте PA(облегченный вариант)Если множество натуральных чисел с операциями сложения иумножения (N0 , +, ×) является моделью для аксиом PA, то PAнеполна.Доказательство.2. Покажем, что PA 6` ¬ϕ(n̄0 ) .Допустим противное PA ` ¬ϕ(n̄0 ) , т.

е. PA ` ∃y W(n̄0 , y ) .Тогда (почему?) существует такое натуральное число m, длякоторого верно PA ` W(n̄0 , m̄) . Учитывая, что формула Wвыражает отношение MetaProof , приходим к выводу: m — этогеделев номер доказательства формулы ϕ(n̄0 ) в PA. Значит,PA ` ϕ(n̄0 ) .Но это означает, что PA — противоречивая теория, вопрекиусловию теоремы (PA имеет модель).Теорема Геделя о неполноте PA(облегченный вариант)Если множество натуральных чисел с операциями сложения иумножения (N0 , +, ×) является моделью для аксиом PA, то PAнеполна.Доказательство.3.

Итак,PA 6` ϕ(n̄0 )PA 6` ¬ϕ(n̄0 ) .Значит, ϕ(n̄0 ) = ¬∃y W(n̄0 , y ) — это истинное арифметическоеутверждение, которое нельзя ни доказать, ни опровергнуть варифметике Пеано.Значит, арифметика Пеано неполна.Теорема Геделя о неполноте PA(Основной вариант)Пусть запись Consist обозначает арифметическую формулу¬∃X Proof (gn(0 = s(0)), X )Если формальная арифметика PA непротиворечива, тоPA `6ConsistPA `6¬Consist.Это означает, что аксиоматические теории (сколь бывыразительны они ни были) не позволяют построитьдоказательство их собственной непротиворечивости.КОНЕЦ ЛЕКЦИИ 18.