Теоремы Гёделя о неполноте

Теоремы Гёделя о неполноте

Теоремы Гёделя о неполноте — две теоремы математической логики о принципиальных ограничениях формальной арифметики и, как следствие, всякой достаточно сильной^[1] теории первого порядка.

Первая теорема утверждает, что если формальная арифметика непротиворечива, то в ней существует невыводимая и неопровержимая формула.

Вторая теорема утверждает, что если формальная арифметика непротиворечива, то в ней невыводима некоторая формула, содержательно утверждающая непротиворечивость этой теории.

Эти теоремы были доказаны Куртом Гёделем в 1930 году (опубликованы в 1931) и имеют непосредственное отношение ко второй проблеме из знаменитого списка Гильберта.

Первая теорема Гёделя о неполноте

Утверждение первой теоремы Гёделя о неполноте можно сформулировать следующим образом:

Если формальная арифметика S непротиворечива, то в ней существует такая замкнутая формула G, что ни G, ни её отрицание ¬G не являются выводимыми в S.

Теория, содержащая неразрешимое, то есть невыводимое и неопровержимое, предложение, называется неполной.

При доказательстве теоремы Гёдель построил формулу G в явном виде, иногда её называют гёделевой неразрешимой формулой. В стандартной интерпретации^[2] предложение G утверждает свою собственную невыводимость в S. Следовательно, по теореме Гёделя, если теория S непротиворечива, то эта формула и в самом деле невыводима в S и потому истинна в стандартной интерпретации. Таким образом, для натуральных чисел, формула G верна, но в S невыводима.

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

Для доказательства первой теоремы о неполноте Гёдель сопоставил каждому символу, выражению и последовательности выражений формальной арифметики определенный номер. Поскольку формулы и теоремы являются предложениями арифметики, а формальные выводы теорем являются последовательностями формул, то стало возможным говорить о теоремах и доказательствах в терминах натуральных чисел. Например, пусть гёделева неразрешимая формула G имеет номер m, тогда она эквивалентна следующему утверждению на языке арифметики: "нет такого натурального числа n, что n есть номер вывода формулы с номером m". Подобное сопоставление формул и натуральных чисел называется арифметизацией математики и было осуществлено Гёделем впервые. Эта идея впоследствии стала ключом к решению многих важных задач математической логики.

Набросок доказательства^[3]

Зафиксируем некоторую формальную систему PM, в которой можно представить элементарные математические понятия^[4].

Выражения формальной системы являются, если смотреть извне, конечными последовательностями примитивных символов (переменных, логических постоянных, и скобок или точек) и нетрудно строго уточнить какие последовательности примитивных символов являются формулами, а какие нет. Аналогично, с формальной точки зрения, доказательства есть ни что иное, как конечные последовательности формул (со строго заданными свойствами). Для математического рассмотрения не имеет значения, какие объекты взять в качестве примитивных символов, и мы решаем использовать для этих целей натуральные числа. Соответственно, формула является конечной последовательностью натуральных чисел, вывод формулы - конечной последовательностью конечных последовательностей натуральных чисел. Математические понятия (утверждения) таким образом становятся понятиями (утверждениями) о натуральных числах или их последовательностях, и, следовательно, сами могут быть выражены в символизме системы PM (по крайней мере частично). Может быть показано, в частности, что понятия "формула", "вывод", "выводимая формула" определимы внутри системы PM, то есть можно восстановить, например, формулу F(v) в PM с одной свободной переменной v (тип которой - числовая последовательность) такую, что F(v), в интуитивной интерпретации, означает: v - выводимая формула. Теперь построим неразрешимое предложение системы PM, то есть предложение A, для которого ни A, ни не-A невыводимы, следующим образом:

Формулу в PM с точно одной свободной переменной, тип которой натуральное число (класс классов), будем называть класс-выражением. Упорядочим класс-выражения в последовательность каким-либо образом, обозначим n-е через R(n), и заметим, что понятие "класс-выражение", также как и отношение упорядочения R можно определить в системе PM. Пусть α будет произвольным класс-выражением; через [α;n] обозначим формулу, которая образуется из класс-выражения α заменой свободной переменной на символ натурального числа n. Тернарное отношение x = [y;z] тоже оказывается определимым в PM. Теперь мы определим класс K натуральных чисел следующим образом:

n ∈ K ≡ ¬Bew[R(n);n]    (*)

(где Bew x означает: x - выводимая формула). Так как все понятия, встречающиеся в этом определении, можно выразить в PM, то это же верно и для понятия K, которое из них строится, то есть имеется такое класс-выражение S, что формула [S;n], интуитивно интерпретируемая, обозначает, что натуральное число n принадлежит K. Как класс-выражение, S идентична некоторому определенному R(q) в нашей нумерации, то есть

S = R(q)

выполняется для некоторого определенного натурального числа q. Теперь покажем, что предложение [R(q);q] неразрешимо в PM. Так, если предложение [R(q);q] предполагается выводимым, тогда оно оказывается истинным, то есть, в соответсвии со сказанным выше, q будет принадлежать K, то есть, в соответствии с (*), ¬Bew[R(q);q] будет выполняться, что противоречит нашему предположению. С другой стороны, если бы отрицание [R(q);q] было выводимым, то будет иметь место ¬ n ∈ K, то есть Bew[R(q);q] будет истинным. Следовательно, [R(q);q] вместе со своим отрицанием будет выводимо, что снова невозможно.

Полиномиальная форма

После того, как Юрий Матиясевич доказал диофантовость любого эффективно перечислимого множества, и были найдены примеры универсальных диофантовых уравнений, появилась возможность сформулировать теорему о неполноте в полиномиальной (или диофантовой) форме^[5][6][7]:

Для каждой непротиворечивой теории T можно указать такое целое значение параметра K, что уравнение

$(elg^2 + \alpha - bq^2)^2 + (q - b^{5^{60}})^2 + (\lambda + q^4 - 1 - \lambda b^5)^2 +$

(θ + 2z − b⁵)² + (u + tθ − l)² + (y + mθ − e)² + (n − q¹⁶)² +

((g + eq³ + lq⁵ + (2(e − zλ)(1 + g)⁴ + λb⁵ + λb⁵q⁴)q⁴)(n² − n) +

(q³ − bl + l + θλq³ + (b⁵ − 2)q⁵)(n² − 1) − r)² +

(p − 2ws²r²n²)² + (p²k² − k² + 1 − τ²)² +

(4(c − ksn²)² + η − k²)² + (r + 1 + hp − h − k)² +

(a − (wn² + 1)rsn²)² + (2r + 1 + φ − c)² +

(bw + ca − 2c + 4αγ − 5γ − d)² +

((a² − 1)c² + 1 − d²)² + ((a² − 1)i²c⁴ + 1 − f²)² +

(((a + f²(d² − a))² − 1)(2r + 1 + jc)² + 1 − (d + of)²)² +

(((z + u + y)² + u)² + y − K)² = 0

не имеет решений в неотрицательных целых числах, но этот факт не может быть доказан в теории T. Более того, для каждой непротиворечивой теории множество значений параметра K, обладающих таким свойством, бесконечно и алгоритмически неперечислимо.

Вторая теорема Гёделя о неполноте

В формальной арифметике S можно построить такую формулу, которая в стандартной интерпретации^[2] является истинной в том и только в том случае, когда теория S непротиворечива. Для этой формулы справеливо утверждение второй теоремы Гёделя:

Если формальная арифметика S непротиворечива, то в ней невыводима формула, содержательно утверждающая непротиворечивость S.

Иными словами, непротиворечивость формальной арифметики не может быть доказана средствами этой теории. Однако существуют доказательства непротиворечивости формальной арифметики, использующие средства, невыразимые в ней.

Набросок доказательства

Сначала строится формула Con, содержательно выражающая невозможность вывода в теории S какой-либо формулы вместе с ее отрицанием. Тогда утверждение первой теоремы Гёделя выражается формулой Con ⊃ G, где G — Гёделева неразрешимая формула. Все рассуждения для доказательства первой теоремы могут быть выражены и проведены средствами S, то есть в S выводима формула Con ⊃ G. Отсюда, если в S выводима Con, то в ней выводима и G. Однако, согласно первой теореме Гёделя, если S непротиворечива, то G в ней невыводима. Следовательно, если S непротиворечива, то в ней невыводима и формула Con.

Примечания

1. ↑ Грубо говоря, теория K является достаточно сильной, если понятия натурального числа, 0, 1, сложения и умножения можно определить в K таким образом, чтобы аксиомы формальной арифметики оказывались выводимыми в K.
2. ↑ ^{1 2} Интерпретация формул теории S называется стандартной, если её областью является множество неотрицательных целых чисел, символ 0 интерпретируется числом 0, функциональные буквы ', +, • интерпретируются прибавлением единицы, сложением и умножением соответственно, предикатная буква = интерпретируется отношением тождества.
3. ↑ Gödel, Kurt (1931). On Formally Undecidable Propositions of the Principia Mathematica and Related Systems. I. в сборнике Davis, Martin, editor (1965). The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. pp. 6–8
4. ↑ В своих рассуждениях Гёдель использует несколько расширенную систему Фреге и Рассела Principia Mathematica
5. ↑ Jones J. P., Undecidable diophantine equations
6. ↑ Martin Davis, Diophantine Equations & Computation
7. ↑ К. Подниекс, Теорема Геделя в диофантовой форме

См. также

• Теорема Гёделя о полноте
• Парадокс лжеца
• Недоказуемые утверждения
• Теорема Лёба
• Теорема Тарского о невыразимости истины
• Натуральные числа
• Формальная теория
• Дедуктивная теория

Ссылки

• В. А. Успенский Теорема Гёделя о неполноте. — М.: Наука, 1982. — 110 с. — (Популярные лекции по математике).
• Академик Ю. Л. Ершов «Доказательность в математике», программа А. Гордона от 16 июня 2003 года
• А. Б. Сосинский Теорема Геделя // летняя школа «Современная математика». — Дубна: 2006.
• П. Дж. Коэн Об основаниях теории множеств // Успехи математических наук. — 1974. — Т. 29. — № 5(179). — С. 169–176.
• М. Кордонский Конец истины. — ISBN 5-946448-001-04
• В. А. Успенский Теорема Гёделя о неполноте и четыре дороги, ведущие к ней // летняя школа «Современная математика». — Дубна: 2007.
• Зенкин А. А. Принцип разделения времени и анализ одного класса квазифинитных правдоподобных рассуждений (на примере теоремы Г. Кантора о несчётности) // ДАН. — 1997. — Т. 356. — № 6. — С. 733-735.
• Чечулин В. Л. О кратком варинте доказательства теорем Гёделя // «Фундаментальные проблемы математики и информационных наук», материалы XXXIV Дальневосточной Математической Школы-семинара имени академика Е.В. Золотова. — Хабаровск, Россия: 2009. — С. 60-61.