Гедель теорема о неполноте

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

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

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

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

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

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

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

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

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

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

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

n ∈ K ≡ ¬Bew (*)

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

S = R(q)

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

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

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

Для каждой непротиворечивой теории T можно указать такое целое значение параметра K, что уравнение(θ + 2z − b5)2 + (u + tθ − l)2 + (y + mθ − e)2 + (n − q16)2 + ((g + eq3 + lq5 + (2(e − zλ)(1 + g)4 + λb5 + λb5q4)q4)(n2 − n) + (q3 − bl + l + θλq3 + (b5 − 2)q5)(n2 − 1) − r)2 + (p − 2ws2r2n2)2 + (p2k2 − k2 + 1 − τ2)2 + (4(c − ksn2)2 + η − k2)2 + (r + 1 + hp − h − k)2 + (a − (wn2 + 1)rsn2)2 + (2r + 1 + φ − c)2 + (bw + ca − 2c + 4αγ − 5γ − d)2 + ((a2 − 1)c2 + 1 − d2)2 + ((a2 − 1)i2c4 + 1 − f2)2 + (((a + f2(d2 − a))2 − 1)(2r + 1 + jc)2 + 1 − (d + of)2)2 + (((z + u + y)2 + u)2 + y − K)2 = 0 не имеет решений в неотрицательных целых числах, но этот факт не может быть доказан в теории T. Более того, для каждой непротиворечивой теории множество значений параметра K, обладающих таким свойством, бесконечно и алгоритмически неперечислимо.

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

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

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

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

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

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

В первоначальной форме

В своей формулировке теоремы о неполноте Гёдель использовал понятие ω-непротиворечивой формальной системы — более сильное условие, чем просто непротиворечивость. Формальная система называется ω-непротиворечивой, если для всякой формулы A(x) этой системы невозможно одновременно вывести формулы А(0), А(1), А(2), … и ∃x ¬A(x) (другими словами, из того, что для каждого натурального числа n выводима формула A(n), следует невыводимость формулы ∃x ¬A(x)). Легко показать, что ω-непротиворечивость влечёт простую непротиворечивость (то есть, любая ω-непротиворечивая формальная система непротиворечива).

В процессе доказательства теоремы строится такая формула A арифметической формальной системы S, что:

Если формальная система S непротиворечива, то формула A невыводима в S; если система S ω-непротиворечива, то формула ¬A невыводима в S. Таким образом, если система S ω-непротиворечива, то она неполна и A служит примером неразрешимой формулы.

Формулу A иногда называют гёделевой неразрешимой формулой.

Интерпретация неразрешимой формулы

В стандартной интерпретации формула A означает «не существует вывода формулы A», то есть утверждает свою собственную невыводимость в S. Следовательно, по теореме Гёделя, если только система S непротиворечива, то эта формула и в самом деле невыводима в S и потому истинна в стандартной интерпретации. Таким образом, для натуральных чисел формула A верна, но в S невыводима.

В форме Россера

В процессе доказательства теоремы строится такая формула B арифметической формальной системы S, что:

Если формальная система S непротиворечива, то в ней невыводимы обе формулы B и ¬B; иначе говоря, если система S непротиворечива, то она неполна, и B служит примером неразрешимой формулы.

Формулу B иногда называют россеровой неразрешимой формулой. Эта формула немного сложнее гёделевой.

В стандартной интерпретации формула B означает «если существует вывод формулы B, то существует вывод формулы ¬B». Согласно же теореме Гёделя в форме Россера, если формальная система S непротиворечива, то формула B в ней невыводима; поэтому, если система S непротиворечива, то формула B верна в стандартной интерпретации.

Обобщённые формулировки

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

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

В частности, теорема Гёделя справедлива для каждого непротиворечивого конечно аксиоматизируемого расширения арифметической формальной системы S.

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

Для каждой непротиворечивой теории T можно указать такое целое значение параметра K, что уравнение ( e l g 2 + α − ( b − x y ) q 2 ) 2 + ( q − b 5 60 ) 2 + ( λ + q 4 − 1 − λ b 5 ) 2 + ( θ + 2 z − b 5 ) 2 + ( u + t θ − l ) 2 + ( y + m θ − e ) 2 + ( n − q 16 ) 2 + ( ( g + e q 3 + l q 5 + ( 2 ( e − z λ ) ( 1 + x b 5 + g ) 4 + λ b 5 + λ b 5 q 4 ) q 4 ) ( n 2 − n ) + ( q 3 − b l + l + θ λ q 3 + ( b 5 − 2 ) q 5 ) ( n 2 − 1 ) − r ) 2 + ( p − 2 w s 2 r 2 n 2 ) 2 + ( p 2 k 2 − k 2 + 1 − τ 2 ) 2 + ( 4 ( c − k s n 2 ) 2 + η − k 2 ) 2 + ( r + 1 + h p − h − k ) 2 + ( a − ( w n 2 + 1 ) r s n 2 ) 2 + ( 2 r + 1 + ϕ − c ) 2 + ( b w + c a − 2 c + 4 α γ − 5 γ − d ) 2 + ( ( a 2 − 1 ) c 2 + 1 − d 2 ) 2 + ( ( a 2 − 1 ) i 2 c 4 + 1 − f 2 ) 2 + ( ( ( a + f 2 ( d 2 − a ) ) 2 − 1 ) ( 2 r + 1 + j c ) 2 + 1 − ( d + o f ) 2 ) 2 + ( ( ( z + u + y ) 2 + u ) 2 + y − K ) 2 = 0 {\displaystyle {\begin{aligned}&(elg^{2}+\alpha -(b-xy)q^{2})^{2}+(q-b^{5^{60}})^{2}+(\lambda +q^{4}-1-\lambda b^{5})^{2}+\\&(\theta +2z-b^{5})^{2}+(u+t\theta -l)^{2}+(y+m\theta -e)^{2}+(n-q^{16})^{2}+\\&((g+eq^{3}+lq^{5}+(2(e-z\lambda )(1+xb^{5}+g)^{4}+\lambda b^{5}+\lambda b^{5}q^{4})q^{4})(n^{2}-n)+\\&(q^{3}-bl+l+\theta \lambda q^{3}+(b^{5}-2)q^{5})(n^{2}-1)-r)^{2}+\\&(p-2ws^{2}r^{2}n^{2})^{2}+(p^{2}k^{2}-k^{2}+1-\tau ^{2})^{2}+\\&(4(c-ksn^{2})^{2}+\eta -k^{2})^{2}+(r+1+hp-h-k)^{2}+\\&(a-(wn^{2}+1)rsn^{2})^{2}+(2r+1+\phi -c)^{2}+\\&(bw+ca-2c+4\alpha \gamma -5\gamma -d)^{2}+\\&((a^{2}-1)c^{2}+1-d^{2})^{2}+((a^{2}-1)i^{2}c^{4}+1-f^{2})^{2}+\\&(((a+f^{2}(d^{2}-a))^{2}-1)(2r+1+jc)^{2}+1-(d+of)^{2})^{2}+\\&(((z+u+y)^{2}+u)^{2}+y-K)^{2}=0\end{aligned}}}не имеет решений в неотрицательных целых числах, но этот факт не может быть доказан в теории T. Более того, для каждой непротиворечивой теории множество значений параметра K, обладающих таким свойством, бесконечно и алгоритмически неперечислимо.

Степень данного уравнения может быть понижена до 4 ценой увеличения количества переменных.

В своей статье Гёдель даёт набросок основных идей доказательства, который приведён ниже с незначительными изменениями.

Каждому примитивному символу, выражению и последовательности выражений некоторой формальной системы S поставим в соответствие определённое натуральное число. Математические понятия и утверждения таким образом становятся понятиями и утверждениями о натуральных числах, и, следовательно, сами могут быть выражены в символизме системы S. Можно показать, в частности, что понятия «формула», «вывод», «выводимая формула» определимы внутри системы S, то есть можно восстановить, например, формулу F(v) в S с одной свободной натурально-числовой переменной v такую, что F(v), в интуитивной интерпретации, означает: v — выводимая формула. Теперь построим неразрешимое предложение системы S, то есть предложение A, для которого ни A, ни не-A невыводимы, следующим образом:

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

n∈K ≡ ¬Bew (*)

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

C = R(q)

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

Связь с парадоксами

В стандартной интерпретации гёделева неразрешимая формула A означает «не существует вывода формулы A», то есть утверждает свою собственную невыводимость в системе S. Таким образом, A является аналогом парадокса лжеца. Рассуждения Гёделя в целом очень похожи на парадокс Ришара. Более того, для доказательства существования невыводимых утверждений может быть использован любой семантический парадокс.

Следует отметить, что выражаемое формулой A утверждение не содержит порочного круга, поскольку изначально утверждается только, что некоторая конкретная формула, явную запись которой получить несложно (хоть и громоздко), недоказуема. «Только впоследствии (и, так сказать, по воле случая) оказывается, что эта формула в точности та, которой выражено само это утверждение».

История

Ещё в начале XX века Давид Гильберт провозгласил цель аксиоматизировать всю математику, и для завершения этой задачи оставалось доказать непротиворечивость и логическую полноту арифметики натуральных чисел. 7 сентября 1930 года в Кёнигсберге проходил научный конгресс по основаниям математики, и на этом конгрессе 24-летний Курт Гёдель впервые обнародовал две фундаментальные теоремы о неполноте, показавшие, что программа Гильберта не может быть реализована: при любом выборе аксиом арифметики существуют теоремы, которые невозможно ни доказать, ни опровергнуть простыми (финитными) средствами, предусмотренными Гильбертом, а финитное доказательство непротиворечивости арифметики невозможно.

Это выступление не было заявлено заранее и произвело ошеломляющий эффект, Гёдель сразу стал всемирной знаменитостью, а программа Гильберта по формализации основ математики потребовала срочного пересмотра. 23 октября 1930 года результаты Гёделя были представлены Венской академии наук Хансом Ханом. Статья с обеими теоремами («О принципиально неразрешимых положениях в системе Principia Mathematica и родственных ей системах») была опубликована в научном ежемесячнике Monatshefte für Mathematik und Physik в 1931 году. Хотя доказательство второй теоремы Гёдель дал только в виде идеи, его результат было настолько ясен и неоспорим, что не вызвал сомнений ни у кого. Гильберт сразу признал ценность открытий Гёделя; первые полные доказательства обеих теорем были опубликованы в книге Гильберта и Бернайса «Основания математики» (1938). В предисловии ко второму тому авторы признали, что для достижения поставленной цели финитных методов недостаточно, и добавили в число логических средств трансфинитную индукцию; в 1936 году Герхард Генцен сумел доказать с помощью этой аксиомы непротиворечивость арифметики, однако логическая полнота так и осталась недостижимой

Историческое влияние

Специалисты дают самые разные, иногда даже полярные оценки исторической значимости теорем Гёделя. Часть учёных считает, что эти теоремы «перевернули» основания математики или даже всю теорию познания, и значение гениального открытия Гёделя будет постепенно открываться ещё долгое время. Другие же (например, Бертран Рассел) призывают не преувеличивать, поскольку теоремы опираются на финитный формализм Гильберта.

Вопреки распространенному заблуждению, теоремы о неполноте Гёделя не предполагают, что некоторые истины так и останутся навеки непознанными. Кроме того, из этих теорем не следует, что человеческие способности к познанию так или иначе ограниченны. Нет, теоремы всего лишь показывают слабости и недостатки формальных систем.

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

Допустим, что аксиоматика Пеано для арифметики противоречива. Тогда из неё можно вывести любое утверждение, в том числе ложное. Однако все аксиомы Пеано очевидным образом истинны, а из истинных утверждений не могут следовать ложный вывод — получаем противоречие. Следовательно, арифметика непротиворечива.

С точки зрения повседневной человеческой логики, это доказательство приемлемо и убедительно. Но оно не может быть записано по правилам теории доказательств Гильберта, поскольку в этих правилах семантика заменена на синтаксис, а истинность — на «выводимость». В любом случае теоремы Гёделя подняли философию математики на новый уровень.

  • Антиномия
  • Натуральное число
  • Недоказуемые утверждения
  • Парадокс лжеца
  • Теорема Гёделя о полноте
  • Теорема Гудстейна
  • Теорема Лёба
  • Теорема Тарского о невыразимости истины
  • Теорема Хайтина о неполноте
  • Формальная теория
  1. Иногда упоминается как вторая теорема Гёделя «о доказательствах непротиворечивости», «о неполноте», «о неполноте арифметики».
  2. 1 2 Формальная система, содержащая неразрешимую, то есть невыводимую и неопровержимую, формулу, называется неполной.
  3. 1 2 3 4 Интерпретация формул теории S называется стандартной, если её областью является множество неотрицательных целых чисел, символ 0 интерпретируется числом 0, функциональные буквы ‘, +, • интерпретируются прибавлением единицы, сложением и умножением соответственно, предикатная буква = интерпретируется отношением тождества.
  4. Гёдель использовал систему Principia Mathematica Уайтхеда и Рассела с оговоркой, что рассуждения применимы к широкому классу формальных систем
  5. Подобное сопоставление формул и натуральных чисел называется арифметизацией математики и было осуществлено Гёделем впервые. Эта идея впоследствии стала ключом к решению многих важных задач математической логики. См. Гёделева нумерация
  6. «Bew» сокр. от нем. «Beweisbar» — доказуемый, выводимый
  1. Клини 1957 с.513
  2. чл.-корр. РАН Лев Дмитриевич Беклемишев в «Введении в математическую логику»
  3. Толковый словарь по вычислительным системам — Page 205
  4. Доклады Академии наук СССР, Volume 262 — Page 799 (1982)
  5. Известия Академии наук СССР, Volume 50 — Page 1140 (1986)
  6. 1 2 Клини 1957 с.187
  7. Мендельсон 1971 с.165
  8. Это рассуждение заимствовано из Мендельсон 1971 с.160
  9. См., например, Клини 1957 с.188
  10. Мендельсон 1971 с.162
  11. Мендельсон 1971 с.162-163
  12. Мендельсон 1971 с.176
  13. Jones J. P., Undecidable diophantine equations
  14. Martin Davis, Diophantine Equations & Computation
  15. Martin Davis, The Incompleteness Theorem
  16. К. Подниекс, Теорема Геделя в диофантовой форме
  17. Gödel, Kurt. On Formally Undecidable Propositions of the Principia Mathematica and Related Systems. I. — 1931. в книге Davis, Martin (ed.). The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. — New York: Raven Press, 1965. — С. 6-8.
  18. 1 2 Гёдель 1931
  19. 1 2 Пиньейро, 2015, с. 13, 48—49, 66, 89—90.
  20. Stephen Hawking. Godel and the End of the Universe. Дата обращения 8 апреля 2018.
  21. Михайлова Н. В. Проблема обоснования современной математики в контексте новых философско-методологических кризисов // Философия математики: актуальные проблемы. Математика и реальность. Тезисы Третьей всероссийской научной конференции; 27-28 сентября 2013 г.. — М.: Центр стратегической конъюнктуры, 2013. — С. 187. — 270 с. — ISBN 978-5-906233-39-4.
  22. Музыкантский А..
  23. Ливио, Марио. Был ли Бог математиком? Глава «Истина в неполноте». — М.: АСТ, 2016. — 384 с. — (Золотой фонд науки). — ISBN 978-5-17-095136-9.
  24. 1 2 Пиньейро, 2015, с. 155—162.

Литература

  • Бирюков Б. В., Тростников В. Н. Жар холодных чисел и пафос бесстрастной логики. Формализация мышления от античных времен до эпохи кибернетики. — М.: Едиториал УРСС, 2004. — 232 с. — ISBN 5-354-00310-5.
  • Ершов Ю. Л. Доказательность в математике, программа А. Гордона от 16 июня 2003 года.
  • Ершов Ю. Л., Палютин Е.А. Математическая логика. — М.: Наука, 1987. — 336 с.
  • Клини Стефен Коул. Введение в метаматематику. — М.: ИЛ, 1957. — 526 с.
  • Клини Стефен Коул. Математическая логика. — М.: «Мир», 1973. — 480 с.
  • Кордонский М. Конец истины. — ISBN 5-946448-001-04.
  • Коэн П. Дж. Об основаниях теории множеств // Успехи математических наук. — 1974. — Т. 29, № 5(179). — С. 169–176.
  • Мендельсон Эллиот. Введение в математическую логику. — М.: «Наука», 1971. — 320 с.
  • Паршин А. Н. Размышления над теоремой Гёделя // Историко-математические исследования. — М.: Янус-К, 2000. — № 40 (5). — С. 26—55.
  • Пиньейро Г. Э. У интуиции есть своя логика. Гёдель. Теоремы о неполноте // Наука. Величайшие теории. — М.: Де Агостини, 2015. — Вып. 17. — ISSN 2409-0069.
  • Сосинский А. Б. Теорема Геделя // Летняя школа «Современная математика». — Дубна, 2006.
  • Успенский В. А. Теорема Гёделя о неполноте. — М.: Наука, 1982. — 110 с. — (Популярные лекции по математике).
  • Успенский В. А. Теорема Гёделя о неполноте и четыре дороги, ведущие к ней // Летняя школа «Современная математика». — Дубна, 2007.
  • Davis, Martin (ed.). The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. — New York: Raven Press, 1965. — 440 p.
  • Heijenoort, Jean van (ed.). From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931. — Cambridge, Massachusetts: Harvard University Press, 1967. — 660 p.

> Ссылки

  • Музыкантский А. Теория противоречивости бытия. Дата обращения 10 сентября 2017.

> Библиография — статьи Гёделя

Оригинальный немецкий текст с параллельным английским переводом, с элементарным введением, написанным Стивеном Клини.

БОГ И ТЕОРЕМА ГЕДЕЛЯ

А началось все с того, что в десять лет я случайно наткнулся на научно-фантастический роман про межпланетные путешествия, прочел залпом — и увлекся астрономией. Начал читать популярную, а затем и более серьезную литературу, делал простейшие астрономические приборы, наблюдал за звездным небом.Но астрономия неотделима от математики и физики — и я стал изучать их по книгам, в каких-то областях оставив далеко позади школьную программу. К старшим классам я уже проникся внутренней красотой математики. И когда решил связать свою судьбу с педагогикой, с учительством — колебаний у меня не было. Преподавать буду именно математику!

Так я в 1983 году оказался на математическом факультете МГПИ имени В. И. Ленина. Надо сказать, что преподавание высшей математики там отвечало самым высоким требованиям. Я до сих пор с благодарностью вспоминаю своих преподавателей, которые не просто обучали своему предмету, но раскрывали его внутреннюю гармонию.

Впрочем, ближе к делу. В советское время среди прочих атеистических штампов очень популярна была идея о том, что религия — это торжество абсурда, что она никак не совместима с логическим мышлением, а логическое мышление — это основа основ, в мире есть только то, что описывается логикой. И вот я изучаю математическую логику, изучаю теорию числовых систем. Что же оказывается? Наши обыденные представления о логике поверхностны! Эта привычная нам логика неплохо работает на бытовом уровне, но если копнуть глубже — возникают неразрешимые парадоксы. И более того: оказалось, что с помощью логики невозможно доказать истинность самой логики! Об этом говорит знаменитая теорема Гёделя о неполноте формальных систем. Цепочка логических доказательств может тянуться сколь угодно далеко, но у нее все равно есть начало, все равно есть некие исходные посылки, доказать которые невозможно. Невозможно в принципе!

Это был серьезный удар по моему атеизму. Во всяком случае, по той версии атеизма, которую нам вдалбливали. Логика, оказывается, не абсолютна, у нее, оказывается, есть границы применимости. И более того — «мощность множества истинных утверждений больше мощности множества доказуемых утверждений». А если перевести с математического на человеческий — есть бесконечно много утверждений, доказать которые принципиально невозможно, но которые тем не менее верны!

Так можно ли требовать от верующих доказательств существования Бога и, не получив таковые, утверждать, будто Бога нет? Сейчас мне все это кажется банальностью, но лет в двадцать было настоящим открытием!

И еще был такой расхожий атеистический штамп — каверзный вопрос, звучащий со времен средневековья: «Может ли Бог создать такой камень, который не смог бы поднять?». Этот простейший парадокс призван был доказать, что, говоря о всемогуществе Божием, верующие несут чушь. Но если взглянуть на математическую подоплеку этого парадокса, окажется, что это лишь один из примеров тех парадоксов, которые возникли в конце XIX века в теории множеств, когда вошло в оборот понятие «универсального множества». Попробую объяснить «на пальцах». Множество — это совокупность каких-либо объектов, они, эти объекты, называются элементами множества. Множества бывают конечные, а бывают бесконечные. Есть понятие универсального множества — то есть совокупности любых множеств. И есть понятие дополнения множества — то есть совокупности всего того, что в данное множество не входит. Теперь вопрос: а у универсального множества есть дополнение? Если есть — то какое же оно тогда «универсальное»? Получается, что-то в него не входит? А если нет у него дополнения — то опять-таки оно получается не универсальным. Должно ведь включать в себя всё, в том числе и собственное дополнение!

Да, парадокс есть. Но о чем он свидетельствует? Да о том, что наши обывательские представления о бесконечности нуждаются в коррекции. Я тогда впервые задумался: а в каком же смысле верующие понимают всемогущество Божие? Потом были и книги, и споры, и сейчас мне смешно становится, когда я слышу претензии вроде «если Бог всемогущ, почему Он не может сделать так, чтобы все немедленно стали счастливы?». Как мечтал сталкер Шухарт у Стругацких в «Пикнике на обочине»: «Счастья для всех, даром, и чтобы никто не ушел обиженным». Да потому и не может, отвечаю я, что задавать подобные вопросы — значит неправильно понимать Его всемогущество, пытаться описать бесконечность в категориях конечного, применять инструмент там, где он неприменим. Топором хорошо дрова колоть, но не трепанацию черепа делать.

А тут необходимо сказать, что в математике есть два разных понимания бесконечности. Есть «потенциальная бесконечность» — это когда просто нет какого-то конца, нет границы. Например, нет самого большого числа — потому что к любому числу можно прибавить единицу и получится большее число. Но есть и «актуальная бесконечность» — это когда бесконечный объект понимается как нечто единое, цельное, когда с ним делают то же, что и, например, с числами: то есть бесконечности складывают и вычитают, преобразовывают, сравнивают… Именно «актуальная бесконечность» и порождает всяческие парадоксы. Именно идеей актуальной бесконечности мы — не всегда осознанно! — пользуемся, когда рассуждаем о Боге и о том, что Он всемогущ, вездесущ и всеведущ. Именно тут и возникает «камень, который нельзя поднять». Но эти парадоксы если что и доказывают — так только то, что мир гораздо сложнее, чем те модели, с помощью которых мы его описываем. И что мышление наше далеко от идеала, не всё мы можем постичь.

Это знание мне помогло, когда я размышлял над непостижимостью Бога. Ведь, с точки зрения советского атеиста, непостижимость — это очень обидно, это унизительно! Мы же так были уверены, что человек — это венец мироздания, что «в мире много сил великих, // но сильнее человека // нет в природе ничего». И тут оказывается, что есть вещи, которые мы не только сейчас, при нынешнем уровне науки познать не сможем, но и при любом уровне не сможем никогда! Оказывается, что наше мышление не универсально, что не охватить им всего сущего, а то, что мы называем «научной картиной мира» — это всего лишь модель. И все познание наше — это замена одних моделей другими, более совершенными, но все равно только приблизительно описывающими реальность.

Теперь оказалось, что эта наша ограниченность — вовсе не злобная выдумка церковников с их любимой присказкой «неисповедимы пути Господни», а объективный факт, подтверждаемый самой что ни на есть объективной наукой — математикой.

А еще оказалось, что математика может помочь лучше уяснить некоторые богословские утверждения, найти для них какие-то зримые аналогии. К примеру, ересь ариан, утверждавших, что Христос — это не Бог по Своей сути, а лишь первое, наиболее совершенное творение Божие. Тут аналогия — луч. То есть часть прямой: есть начало, нет конца. «Полубесконечность» такая. А православный ответ: не луч, а прямая. Нет начала. Настоящая бесконечность. Или — что такое «теозис» («обожение»)? Как человек, существо конечное, может уподобиться бесконечному Богу? Тут на помощь приходит понятие потенциальной бесконечности — то есть, соединяясь с Богом, человек преодолевает свою ограниченность, возрастает, ему открываются новые горизонты, и конца этому процессу нет. Однако нет и тождества с Богом — подобно тому, как принципиально невозможно взаимнооднозначное соответствие* между множеством натуральных чисел (то есть 1, 2, 3…) и множеством действительных чисел (то есть вообще всех чисел, известных человеку со школьным образованием — включая всяческие квадратные корни, число и так далее).

Математика не заставила меня уверовать в Бога, она всего лишь сняла те умственные барьеры, которые дало атеистическое воспитание, она расчистила дорогу к вере. Уверовал я позднее, пройдя через сомнения и шатания. Но это уже совсем другая история.

*Представьте себе множество кресел в кинотеатре — и множество зрителей. Если каждому зрителю найдется кресло и при этом все места будут заняты, тогда между этими двумя множествами есть «взаимнооднозначное соответствие». — Ред.

Теоремы о неполноте Геделя: Дырка в математике

— Можно как-то популярно объяснить теоремы о неполноте Геделя? Брадобрей бреет только тех, кто не бреется сам. Бреет ли себя брадобрей? Этот знаменитый парадокс имеет к ним отношение?

Главный тезис логического доказательства существования Бога, выдвинутый Куртом Геделем: «Бог существует в мышлении. Но существование в реальности больше, нежели существование только в мысли. Следовательно, Бог должен существовать». На фото: автор теоремы о неполноте Курт Гедель со своим другом, автором теории относительности Альбертом Эйнштейном. Пристон. Америка. 1950

— Да, конечно, имеет. До Геделя существовала проблема аксиоматизации математики и проблема таких парадоксальных предложений, которые формально можно записать на любом языке. Например: «Это утверждение ложно». Какова истинность этого утверждения? Если оно истинно, значит, оно ложно, если оно ложно, значит, истинно; получается языковой парадокс. Гедель исследовал арифметику и показал в своих теоремах, что ее непротиворечивость не может быть доказана, исходя из ее самоочевидных принципов: аксиом сложения, вычитания, деления, умножения и проч. Нам требуются для ее обоснования некоторые дополнительные допущения. Это на самой простейшей теории, а что говорить о более сложных (уравнениях физики и т. п.)! Всегда для обоснования какой-то системы умозаключений мы вынуждены прибегать к некоему дополнительному умозаключению, которое в рамках системы не обосновывается.

Прежде всего это указывает на ограниченность претензий человеческого разума в познании реальности. То есть мы не можем говорить о том, что мы построим какую-то всеобъемлющую теорию мироздания, которая все объяснит, — такая теория не может быть научной.

— Как математики сейчас относится к теоремам Геделя? Никто не пытается их опровергнуть, как-то обойти?

— Это все равно что пытаться опровергнуть теорему Пифагора. Теоремы имеют строгое логическое доказательство. В то же время предпринимаются попытки найти ограничения применимости теорем Геделя. Но главным образом споры идут вокруг философских следствий теорем Геделя.

— Насколько проработано геделево доказательство существования Бога? Оно закончено?

— Оно проработано детально, хотя сам ученый до самой своей смерти так и не решился его опубликовать. Гедель развивает онтологический (метафизический. — «НС») аргумент, впервые предложенный Ансельмом Кентерберийским. В сжатой форме этот аргумент можно представить следующим образом: «Бог, по определению, является Тем, больше Кого нельзя ничего помыслить. Бог существует в мышлении. Но существование в реальности больше, нежели существование только в мысли. Следовательно, Бог должен существовать». Аргументацию Ансельма позднее развивали Рене Декарт и Готфрид Вильгельм Лейбниц. Так, по мнению Декарта, мыслить Высшее Совершенное Бытие, которому недостает существования, означает впадать в логическое противоречие. В контексте этих идей Гедель разрабатывает свою версию доказательства, она умещается буквально на двух страничках. К сожалению, изложение его аргументации невозможно без введения в основы очень сложной модальной логики.

Разумеется, логическая безупречность выводов Геделя не принуждает человека становиться верующим под давлением силы доказательств. Не следует быть наивными и полагать, что мы можем убедить любого разумно мыслящего человека уверовать в Бога с помощью онтологического аргумента или других доказательств. Вера рождается тогда, когда человек становится лицом к лицу перед очевидным присутствием высшей трансцендентной Реальности Бога. Но можно назвать по крайней мере одного человека, которого онтологическое доказательство привело к религиозной вере, — это писатель Клайв Стейплз Льюис, он сам признавался в этом.

Отдаленное будущее — это отдаленное прошлое

— Как относились к Геделю современники? Он дружил с кем-то из больших ученых?

— Ассистент Эйнштейна в Принстоне свидетельствует, что единственным человеком, с которым тот дружил в последние годы жизни, был Курт Гедель. Они были различны почти во всем — Эйнштейн общительный, веселый, а Гедель предельно серьезный, совершенно одинокий и недоверчивый. Но они имели общее качество: оба шли прямо и искренне к центральным вопросам науки и философии. Несмотря на дружбу с Эйнштейном, Гедель имел свой специфический взгляд на религию. Он отвергал представление о Боге как безличном существе, каким был Бог для Эйнштейна. По этому поводу Гедель заметил: «Религия Эйнштейна является слишком абстрактной, как у Спинозы и в индийской философии. Бог Спинозы меньше, чем личность; мой Бог больше чем личность; поскольку Бог может играть роль личности». Могут существовать духи, которые не имеют тела, но могут общаться с нами и оказывать влияние на мир».

— Как Гедель оказался в Америке? Бежал от нацистов?

— Да, он приехал в Америку в 1940 году из Германии, несмотря на то что фашисты признали его арийцем и великим ученым, освободив от военной службы. Он с женой Аделе пробирался через Россию по Транссибирской магистрали . Воспоминаний об этом путешествии он не оставил. Аделе вспоминает только о постоянном страхе по ночам, что остановят и вернут обратно. После восьми лет проживания в Америке Гедель стал гражданином США. Как и все подающие на гражданство, он должен был ответить на вопросы, касающиеся американской Конституции. Будучи скрупулезным человеком, он готовился к этому экзамену очень тщательно. Наконец сообщил, что нашел непоследовательность в Конституции: «Я открыл логически законную возможность, при которой США может стать диктатурой». Его друзья признали, что, независимо от логических достоинств аргумента Геделя, эта возможность была чисто гипотетической по своему характеру, и предостерегли от пространных разговоров на эту тему на экзамене.

— Не использовали ли Гедель и Эйнштейн идей друг друга в научной работе?

— В 1949 году Гедель выразил свои космологические идеи в математическом эссе, которое, по мнению Альберта Эйнштейна, являлось важным вкладом в общую теорию относительности . Гедель считал, что время — «эта таинственная и одновременно самопротиворечивая сущность, которая формирует основу мира и нашего собственного существования», — в конце концов станет величайшей иллюзией. Оно «когда-то» перестанет существовать, и наступит иная форма бытия, которую можно назвать вечностью. Такое представление о времени привело великого логика к неожиданному выводу. Он писал: «Я убежден в посмертном существовании, независимо от теологии. Если мир является разумно сконструированным, тогда должно быть посмертное существование».

— «Время – самопротиворечивая сущность». Странно звучит; это имеет какой-то физический смысл?

— Гедель показал, что в рамках уравнения Эйнштейна можно построить космологическую модель с замкнутым временем, где удаленное прошлое и удаленное будущее совпадают. В этой модели становится теоретически возможным путешествие во времени. Это звучит странно, но это математически выразимо — вот в чем дело. Эта модель может иметь экспериментальные следствия, а может и не иметь. Она является теоретической конструкцией, которая может оказаться полезной при построении новых космологических моделей — а может оказаться излишней. Современная теоретическая физика, в частности квантовая космология, обладает столь сложной математической структурой, что этим структурам очень сложно дать однозначное философское осмысление. Более того, некоторые ее теоретические конструкции пока являются экспериментально непроверяемыми по той простой причине, что для своей проверки требуют обнаружения очень высокоэнергетичных частиц. Помните, как народ переполошился по поводу запуска Большого андронного коллайдера: средства массовой информации постоянно пугали людей приближением конца света. На самом деле, ставился серьезный научный эксперимент по проверке моделей квантовой космологии и так называемых «теорий великого объединения». Если бы удалось обнаружить так называемые частицы Хиггса, то это стало бы очередным шагом в нашем понимании самых ранних стадий существования нашей Вселенной. Но пока нет экспериментальных данных, конкурирующие модели квантовой космологии продолжают оставаться просто математическими моделями.

Вера и интуиция

— «…Мой Бог больше чем личность; поскольку Бог может играть роль личности…» Все-таки вера Геделя далека от православного исповедания?

— Сохранилось очень мало высказываний Геделя о его вере, они по крупицам собраны. Несмотря на то что первые наброски собственной версии аргумента Гедель сделал еще в 1941 году, до 1970-го, боясь насмешек своих коллег, он не говорил об этом. В феврале 1970-го, почувствовав приближение смерти, он разрешил своей помощнице скопировать версию своего доказательства. После смерти Геделя в 1978 году в его бумагах была обнаружена несколько иная версия онтологического аргумента. Жена Курта Геделя, Аделе, через два дня после смерти мужа сказала, что Гедель, «хотя и не посещал церковь, был религиозен и читал Библию в кровати каждое воскресное утро».

Когда мы говорим о таких ученых, как Гедель, Энштейн или, скажем, Галилей или Ньютон, важно подчеркнуть то, что они не были атеистами. Они видели, что за Вселенной стоит Разум, некая Высшая Сила. Для многих ученых убежденность в существовании Высшего Разума являлась одним из следствий их научной рефлексии, и не всегда эта рефлексия приводила к возникновению глубокой религиозной связи человека с Богом. В отношении Геделя можно сказать, что он ощущал необходимость этой связи, поскольку подчеркивал, что является теистом, мыслит Бога как личность. Но, разумеется, его веру нельзя назвать ортодоксальной. Он был, так сказать, «домашним лютеранином».

— Вы можете дать исторические примеры: каким путем разные ученые приходят к вере в Бога? Вот генетика Фрэнсиса Коллинза, по его признаниям, к вере в Бога привело исследование структуры ДНК…

— Само по себе естественное богопознание недостаточно для познания Бога. Мало, изучая природу, открыть Бога — важно научиться Его познавать посредством того Откровения, которое Бог дал человеку. Приход человека к вере — независимо от того, ученый он или не ученый, — всегда опирается на что-то, что выходит за рамки просто логических или научных аргументов. Фрэнсис Коллинз пишет, что пришел к вере в 27 лет после продолжительного интеллектуального спора с самим собой и под влиянием Клайва Стейплза Льюиса. Два человека находятся в одной и той же исторической ситуации, в одних исходных условиях: один становится верующим, другой — атеистом. Одного изучение ДНК приводит к убеждению в существовании Бога. Другой изучает — и не приходит к этому. Два человека смотрят на картину: одному она кажется красивой, а другой говорит: «Так себе, обычная картинка!» У одного есть вкус, интуиция, а у другого — нет. Профессор Православного Свято-Тихоновского гуманитарного университета Владимир Николаевич Катасонов, доктор философских наук, математик по первому образованию, говорит: «Никакое доказательство в математике невозможно без интуиции: математик сначала видит картинку, а потом уже формулирует доказательство».

Вопрос о приходе человека к вере — это всегда вопрос, который выходит за рамки просто логического рассуждения. Как объяснить, что тебя привело к вере? Человек отвечает: я ходил в храм, размышлял, читал то-то, увидел гармонию мироздания; но самый главный, самый исключительный момент, в который человек вдруг познает, что он столкнулся с присутствием Бога, не может быть выражен. Это всегда тайна.

— Можно обозначить проблемы, которые не в силах разрешить современная наука?

— Все-таки наука — достаточно уверенное, самостоятельное и хорошо идущее предприятие, чтобы так резко высказываться. Она является хорошим и весьма полезным инструментом в руках человека. Со времени Фрэнсиса Бэкона знание действительно стало силой, изменившей мир. Наука развивается в соответствии со своими внутренними закономерностями: ученый стремится постичь законы мироздания, и можно не сомневаться в том, что этот поиск приведет к успеху. Но в то же время необходимо осознавать и границы науки. Не следует смешивать науку и те мировоззренческие вопросы, которые могут быть поставлены в связи с наукой. Ключевые проблемы сегодня связаны не столько с научным методом, сколько с ценностными ориентациями. Наука в течение долгого ХХ века воспринималась людьми как абсолютное благо, которое способствует прогрессу человечества; а мы видим, что ХХ век стал самым жестоким по человеческим жертвам. И тут возникает вопрос о ценностях научного прогресса, вообще познания. Этические ценности не следуют из самой науки. Гениальный ученый может изобрести оружие для уничтожения всего человечества, и здесь возникает вопрос о нравственной ответственности ученого, на который наука не может ответить. Наука не может указать человеку смысл и предназначение его существования. Наука никогда не сможет ответить на вопрос, почему мы здесь? Почему существует Вселенная? Эти вопросы решаются на другом уровне познания, таком, как философия и религия.

— Кроме теорем Геделя, есть ли еще доказательства того, что научный метод имеет свои пределы? Сами ученые это признают?

— Уже в начале XX века философы Бергсон и Гуссерль указали на относительное значение научного знания природы. Сейчас уже стало почти всеобщим убеждением среди философов науки, что научные теории представляют гипотетические модели объяснения явлений. Один из создателей квантовой механики — Эрвин Шредингер говорил о том, что элементарные частицы являются только образами, но мы вполне можем обойтись и без них. По мысли философа и логика Карла Поппера, научные теории подобны сети, посредством которой мы пытаемся поймать мир, они не похожи на фотографии. Научные теории находятся в постоянном развитии и изменении. О границах научного метода говорили создатели квантовой механики, такие как Паули, Бор, Гейзенберг. Паули писал: «…Физика и психика могут рассматриваться как дополнительные аспекты одной и той же реальности» — и акцентировал внимание на несводимости высших уровней бытия к низшим. Различные объяснения охватывают каждый раз лишь один аспект материи, но всеохватная теория никогда не будет достигнута.

Красота и гармония мироздания предполагает возможность его познания научными методами. Вместе с тем христиане всегда понимали и непостижимость тайны, стоящей за этой материальной вселенной. Вселенная не имеет основания в самой себе и указывает на совершенный источник бытия — Бога.

Священник Димитрий КИРЬЯНОВ родился в 1972 году в Тюмени, окончил Тюменский государственный университет, физический факультет (1994); Тобольскую духовную семинарию (1999); Московскую духовную академию (2002). Клирик Покровского кафедрального собора города Тобольска.

Теорема Гёделя о неполноте (Курт Гедель)

Теорема о неполноте и доказательство, утверждает примерно следующее: при определенных условиях в любом языке существуют истинные, но недоказуемые утверждения.
Первая теорема Гёделя о неполноте
Во всякой достаточно богатой непротиворечивой теории первого порядка (в частности, во всякой непротиворечивой теории, включающей формальную арифметику), существует такая замкнутая формула F, что ни F, ни -,F не являются выводимыми в этой теории.
Иначе говоря, в любой достаточно сложной непротиворечивой теории существует утверждение, которое средствами самой теории невозможно ни доказать, ни опровергнуть. Например, такое утверждение можно добавить к системе аксиом, оставив её непротиворечивой.
Теорема была доказана Куртом Гёделем в 1931-ом году.
Вторая теорема Гёделя о неполноте
Во всякой достаточно богатой непротиворечивой теории первого порядка (в частности, во всякой непротиворечивой теории, включающей формальную арифметику), формула F, утверждающая непротиворечивость этой теории, не является выводимой в ней.
Иными словами, непротиворечивость достаточно богатой теории не может быть доказана средствами этой теории. Однако вполне может оказаться, что непротиворечивость одной конкретной теории может быть установлена средствами другой, более мощной формальной теории. Но тогда встаёт вопрос о непротиворечивости этой второй теории, и т. д.
Использовать эту теорему для доказательства того, что разумная деятельность не сводится к вычислениям, пытались многие. Например, еще в 1961 году известный логик Джон Лукас (John Lucas) выступал с подобной программой. Его рассуждения оказались довольно уязвимыми — однако он и задачу ставил более широко. Роджер Пенроуз использует несколько другой подход, который излагается в книге полностью, «с нуля.