Ещё одни лекции В.А. Захарова, страница 40

. . }, существует множество Y ,содержащее в точности по одному представителю из каждогомножества X1 , X2 , . . . семейства U.Аксиома выбора используется при доказательстве оченьбольшого числа теорем математики. С ее помощью можнодоказать весьма неожиданные утверждения. К их числуотноситсяТеорема ЦермелоЛюбое множество можно вполне упорядочить, т. е. определитьна этом множестве такое отношение линейного порядка, прикотором не существует бесконечно убывающихпоследовательностей элементов.Теория множеств Цермело–ФренкеляА не привнесет ли аксиома выбора какое-нибудь противоречиев теорию ZF? Этот вопрос остается открытым и по сей день.Есть в теории множеств и другие задачи, для решения которыхнедостаточно аксиом теории множеств ZF.Континуум-гипотеза (CH)Любое подмножество множества вещественных чисел либоявляется счетным, либо равномощно множеству вещественныхчисел (является континуальным).В 1939 г.

К. Гедель доказал теорему:Если теория множеств ZF+CA непротиворечива, то теорияZF+AC+CH также непротиворечива .В 1963 г. П. Коэн доказал теорему:Если теория множеств ZF+CA непротиворечива, то теорияZF+AC+¬CH также непротиворечива .Формальная арифметикаА можно ли полностью аксиоматизировать арифметикунатуральных чисел?В 1889 г. итальянский математик Д. Пеано предложил списокаксиом, при помощи которых можно доказывать утверждения освойствах натуральных чисел.Арифметика Пеано (PA) образуется за счет добавления к ИПРсигнатуры 0, s, +, × следующих аксиом.Здесь s(x) нужно рассматривать как одноместную операцию,реализующую функцию вычисления следующего натуральногочисла x + 1.Формальная арифметика1. ∀x, y (s(x) = s(y ) → x = y );2. ∀x (s(x) = 0);3.

∀x ∃y (x = 0 → x = s(y ));4. ∀x (x + 0 = x);5. ∀x, y (x + s(y ) = s(x + y ));6. ∀x (x × 0 = 0);7. ∀x, y (x × s(y ) = x × y + x);8. ϕ(0) & ∀x (ϕ(x) → ϕ(s(x))) → ∀x ϕ(x).Вопрос о непротиворечивости и полноте этой аксиоматическойтеории долгое время оставался центральной проблемойматематики. В 1931 г. К. Гедель доказал теорему, которая даласовершенно неожиданный ответ на этот вопрос.Формальная арифметикаНумералы и арифметизуемые отношенияНумералом n̄ натурального числа n называется термs(s(. .

. s( 0) . . . )) n разНапример, 4̄ — это терм s(s(s(s(0)))) .Отношение P (k) на множестве натуральных чисел называетсяарифметизуемым , если существует такая формулаϕ(x1 , x2 , . . . , xk ) , что для всякого набора натуральных чисел(n1 , n2 , . . . , nk ) верны соотношенияP (k) (n1 , n2 , . . .

, nk ) = true ⇐⇒ PA ! ϕ(n̄1 , n̄2 , . . . , n̄k ) ,P (k) (n1 , n2 , . . . , nk ) = false ⇐⇒ PA ! ¬ϕ(n̄1 , n̄2 , . . . , n̄k ) .Формальная арифметикаНумералы и арифметизуемые отношенияТеорема Геделя–Тьюринга.Отношение P (k) на множестве натуральных чиселарифметизуемо в том и только том случае, если существуеттакая машина Тьюринга M , которая для любого наборанатуральных чисел (n1 , n2 , . . . , nk ) имеет завершающеесявычисление, преобразующее начальную конфигурацию.

. . 1 0 . . . 0 11. . . 1. . . 1 0 11q1 11 n1 +1 раз n2 +1 разnk +1 разв заключительную конфигурацию q0 1 , еслиP (k) (n1 , n2 , . . . , nk ) = true ,в заключительную конфигурацию 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) = truen — геделев номер некоторой формулы арифметики Пеано,ϕ(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 ! ϕ(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 ! ¬ϕ(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 ! ϕ(n̄0 )PA ! ¬ϕ(n̄0 ) .Значит, ϕ(n̄0 ) = ¬∃y W(n̄0 , y ) — это истинное арифметическоеутверждение, которое нельзя ни доказать, ни опровергнуть варифметике Пеано.Значит, арифметика Пеано неполна.Теорема Геделя о неполноте PA(Основной вариант)Пусть запись Consist обозначает арифметическую формулу¬∃X Proof (gn(0 = s(0)), X )Если формальная арифметика PA непротиворечива, тоPA !ConsistPA !¬Consist.Это означает, что аксиоматические теории (сколь бывыразительны они ни были) не позволяют построитьдоказательство их собственной непротиворечивости.КОНЕЦ ЛЕКЦИИ 18.