Теоремы геделя о неполноте философский смысл. Теорема Гёделя о неполноте формальной арифметики

20.09.2019

1. Формальные аксиоматические теории и натуральные числа

2. Формальная арифметика и ее свойства

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

4. Гёдель и его роль в математической логике XX в

Эта теорема, уже неоднократно встречавшаяся нам, утверждает, что любая непротиворечивая формальная аксиоматическая теория, формализующая арифметику натуральных чисел, не является (абсолютно) полной. В настоящем параграфе дается доказательство этой теоремы, опирающееся на идеи и методы теорий алгоритмов. Тем самым будет еще раз продемонстрирована на самом высоком уровне теснейшая связь математической логики и теории алгоритмов - двух математических дисциплин, образующих фундамент всей современной математики. Наше изложение будет основываться на доказательстве, разработанном М.Арбибом.

После доказательства теоремы 35.7 о том, что существует перечислимое, но неразрешимое множество натуральных чисел, было заявлено, что она фактически включает в себя в неявном виде теорему Гёделя о неполноте формальной арифметики. Цель настоящего параграфа состоит в том, чтобы обосновать это заявление. Таким образом, в рамках общей теории алгоритмов, кроме тех теорем, которые были доказаны в двух предыдущих параграфах, будет продемонстрировано продвижение теории алгоритмов в направлении решения чисто логических проблем. Для этого сначала предстоит увязать терминологию логической проблемы о неполноте формальной арифметики с методологической терминологией общей теории алгоритмов, методами которой эта проблема будет решена. При этом утверждение теоремы 35.7 о существовании перечислимого, но неразрешимого множества натуральных чисел будет основополагающей предпосылкой для доказательства теоремы Гёделя, которую мы докажем в следующей формулировке: "Каждая адекватная со-непротиворечивая формальная арифметика неполна". Далее, мы поясним, что будем понимать под формальной арифметикой, а также определим и разъясним те понятия, которые участвуют в приведенной формулировке теоремы Гёделя. Начнем с формальных аксиоматических теорий.

Формальные аксиоматические теории и натуральные числа

Ранее было определено понятие формальной аксиоматической теории. Чтобы задать такую теорию T , нужно задать алфавит (счетное множество символов); в множестве всех слов, составленных из букв данного алфавита, выделить подмножество, элементы которого будут называться формулами (или правильно построенными выражениями) данной теории; в множестве формул выделить те, которые будут называться аксиомами теории; наконец, должно быть задано конечное число отношений между формулами, называемых правилами вывода. При этом должны существовать эффективные процедуры (алгоритмы) для определения того, являются ли данные слова (выражения) формулами (т.е. правильно построенными выражениями), являются ли данные формулы аксиомами и, наконец, получается ли одна данная формула из ряда других Данных формул с помощью данного правила вывода. Это означает, что множество всех формул разрешимо и множество всех аксиом разрешимо. Следовательно, каждое из этих множеств перечислимо.

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

Все теоремы, приводимые в настоящей лекции, в соответствии с нашей терминологией являются фактически метатеоремами, т.е. теоремами о свойствах (формальных) аксиоматически* теорий. Но поскольку здесь никакой конкретной аксиоматической теории мы не рассматриваем, никаких теорем такой теории не доказываем, т.е. никаких теорем, кроме метатеорем, здесь не будет, то мы метатеоремы будем называть просто теоремами.

Теорема 37.1. Множество всех теорем формальной аксиоматической теории Т перечислимо.

Доказательство. Мы уже отметили, что множество аксиом формальной теории перечислимо, т. е. мы можем их эффективно перенумеровать A_1,A_2,A_3,\ldots . Поскольку все формулы состоят из конечного числа букв (символов), все выводы содержат конечное число формул и каждый вывод использует лишь конечное число аксиом, то ясно, что для каждого натурального п существует лишь конечное число выводов, имеющих не более чем п формул (шагов) и использующих только аксиомы \{A_1,A_2,\ldots,A_n\} . Следовательно, двигаясь от n=1 к n=2,~ n=3 и т.д., можно эффективно перенумеровать все теоремы данной теории. Это и означает, что множество теорем перечислимо.

Теперь от произвольных формальных теорий будем переходить к таким, которые так или иначе имеют дело с натуральными числами. Если мы хотим в нашей теории говорить о подмножестве Q множества натуральных чисел, то мы должны иметь эффективный способ выписывания для каждого натурального п формулы W_n , означающей, что n\in Q . Более того, если мы сможем доказать, что формула W_n является теоремой теории T тогда и только тогда, когда n\in Q , то будем говорить, что теория T полуполна для Q (или что в T имеется полуполное описание Q ). Точнее, это определение сформулируем так.

Определение 37.2. Теория T называется полуполной для множества натуральных чисел Q\subseteq \mathbb{N} , если существует перечислимое множество формул W_0,W_1,\ldots,W_n,\ldots , такое, что .

Определение 37.3. Теория T называется полной для Q , если она полуполна для Q и мы также имеем формулу \lnot W_n , которая интерпретируется как n\notin Q , и мы можем доказать, что \lnot W_n является теоремой теории T тогда и только тогда, когда n\notin Q . Другими словами, теория T полна для Q , если в T для каждого п мы можем установить, принадлежит оно Q или нет. Точнее, это означает, что теория T называется полной для множества натуральных чисел T , если она полуполна для Q и полуполна для его дополнения \overline{Q} .

Теорема 37.4. Если теория T полуполна для множества Q , то Q перечислимо.

Доказательство. По определению полуполноты T для Q множество Q есть множество номеров тех формул из некоторого перечислимого множества \{W_0,W_1,\ldots,W_n,\ldots\} формул, которые являются теоремами теории T , т.е. принадлежит и множеству \operatorname{Th}(T) . Таким образом, Q есть множество номеров всех формул из множества \operatorname{Th}(T)\cap \{W_0,W_1,\ldots,W_n,\ldots\} . Каждое из этих пересекаемых множеств перечислимо: первое - по предыдущей теореме 37.1, второе - по сказанному в начале доказательства. Следовательно, и их пересечение, по теореме 35.5, перечислимо. Но тогда пере-цислимо и множество номеров тех формул, которые входят в это пересечение.

Следствие 37.5. Если Q перечислимое, но неразрешимое множество натуральных чисел, то никакая формальная теория не может быть полной для Q .

Доказательство. Если множество Q перечислимо, но неразрешимо, то в силу теоремы 35.6 его дополнение \overline{Q} неперечис-лимо. Тогда по теореме 37.4 никакая теория T не является полуполной для \overline{Q} . Следовательно, никакая теория T неполна для Q .

От этого следствия до теоремы Гёделя совсем недалеко. Для этого нужно средствами некоторой формальной теории T развить теорию натуральных чисел, причем так, чтобы принадлежность чисел данному множеству Q можно было трактовать адекватно (т. е. число п принадлежит Q тогда и только тогда, когда некоторая эффективно сопоставленная ему формула теории T является теоремой этой теории). Это возможно только тогда, когда Q по меньшей мере перечислимо.

Формальная арифметика и ее свойства

Формальная арифметика как формальная аксиоматическая теория строится на базе формализованного исчисления предикатов, рассмотренного ранее. Предметные переменные здесь будем называть числовыми, потому что вместо них будем подставлять натуральные числа.

Предметная переменная называется свободной в формуле, если она не стоит под знаком квантора (общности или существования), и связанной - в противном случае. Формула называется замкнутой, если все ее предметные переменные связаны, и открытой, если в ней имеются свободные переменные. Замыканием формулы F называется формула C(F) , получающаяся из F дописыванием спереди кванторов общности по всем переменным, свободным в F . Ясно, что для любой F формула C(F) замкнута. Если F замкнута, то C(F)=F .

Функция C(F) вычислима. Отсюда следует, что класс замкнутых формул разрешим, поскольку.Рему принадлежит тогда и только тогда, когда C(F)=F , и для распознавания этого равенства существует вычислительная процедура.

С понятием подстановки в формулу мы уже знакомы. Если в формулу F вместо символа (слова) X везде, где он входит в F , вставить слово (формулу) H , то получим новое слово (формулу), обозначаемое S_X^HF и называемое результатом подста-новки в F слова H вместо слова X . Тогда ясно, что

\begin{gathered}S_X^H(\lnot F)\equiv \lnot S_X^HF;\qquad S_X^H(F\to G)\equiv S_X^HF\to S_X^HG;\\ \text{esli}~ i\ne j,~ \text{to}~ S_{x_i}^N(\forall x_j)(F)\equiv (\forall x_j)S_{x_i}^NF,~ S_{x_i}^N(\exists x_j)(F)\equiv (\exists x_j)S_{x_i}^NF. \end{gathered}

Имея дело с натуральными числами, мы хотели бы иметь возможность подставлять их в формулы формальной теории (арифметики), т.е. иметь возможность говорить о числах на языке нашей формальной теории. Для этой цели в формальной теории необходимо иметь слова, которые служили бы названиями натуральных чисел. Такие слова называются нумералами. Нумерал числа п обозначается n^{\ast} . Требование к этим названиям (именам) вполне естественное: различные числа должны называться различными именами, т.е. если m\ne n , то m^{\ast}\ne n^{\ast} . (Идея введения нумералов состоит в том, чтобы разделить вещи и имена этих вещей.)

Таким образом, в формулы арифметики мы будем подставлять вместо числовых переменных x_1,x_2,x_3,\ldots не сами натуральные числа m,n,k,\ldots , а их нумералы (имена) m^{\ast},n^{\ast},k^{\ast},\ldots соответственно.

Наконец, мы можем сформулировать последнее требование (аксиому), которое мы предъявляем к формальной арифметике. Назовем его аксиомой арифметики: если предметная переменная jc, не связана в F , то

\text{(AA)}\colon~ S_{x_i}^{n^{\ast}}F\to (\exists x_i)(F).

Если ввести для S_{x_i}^{n^{\ast}}F обозначение F(n^{\ast}) , то эта аксиома принимает вид:

\text{(AA)}\colon~ F(n^{\ast})\to (\exists x_i)(F).

Это исключительно естественное требование: если формула F превращается в истинное высказывание при подстановке в нее вместо переменной x_i какого-нибудь натурального числа n^{\ast} , то истинно и высказывание (\exists x_i)(F) .

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

Итак, определившись с понятием формальной арифметики, посвятим оставшуюся часть этого пункта понятиям ю-непротиво-речивости, адекватности и полноты этой формальной теории, участвующим в точной формулировке теоремы Гёделя.

Начнем с понятия непротиворечивости. Как и всякая аксиоматическая теория, формальная арифметика называется непротиворечивой, если в ней нельзя доказать какое-либо утверждение и его отрицание, т.е. если не существует такой формулы F , что одновременно \vdash F и \vdash\lnot F .

Предположим теперь, что для некоторой формулы G(x) , содержащей свободно единственную предметную переменную х, установ-дено, что для всех натуральных чисел n=0,1,2,3,\ldots . Даже если в формальной арифметике невозможно доказать \vdash (\forall x)(G(x)) , мы конечно же можем считать это утверждение следствием приведенного списка теорем. Следовательно, если в теории удастся доказать теорему , то такую формальную арифметику следует считать противоречивой.

Определение 37.6. Формальная арифметика называется ω-непротиворечивой, если в ней нет такой формулы G(x) с единственной свободной предметной переменной x , что для всех натуральных чисел n справедливы теоремы \vdash G(n^{\ast}) и \vdash\lnot (\forall x)(G(x)) .

Теорема 37.7. Если формальная арифметика ^-непротиворечива, то она непротиворечива.

Доказательство. В самом деле, если бы она была противоречива, то, как доказано в §27, после определения 27.1, все ее формулы были бы теоремами, в том числе и те, которые создают ω-противоречивость формальной арифметики, и последняя была бы ω-противоречива.

Определение 37.8. Назовем n-местный предикат P(x_1,\ldots,x_n) над множеством натуральных чисел N вполне представимым в формальной арифметике, если существует такая формула F(x_1,\ldots,x_n) , свободными предметными переменными которой являются п переменных x_1,\ldots,x_n (и только они), что:

а) для каждого набора n натуральных чисел (a_1,\ldots,a_n) , для которого предикат P превращается в истинное высказывание P(a_1,\ldots,a_n) , имеет место теорема: \vdash F(a_1^{\ast},\ldots,a_n^{\ast}) ;

б) для каждого набора n натуральных чисел (a_1,\ldots,a_n) , для которого предикат P превращается в ложное высказывание P(a_1,\ldots,a_n) , имеет место теорема: \vdash\lnot F(a_1^{\ast},\ldots,a_n^{\ast}) .

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

Разъясним теперь понятие адекватности формальной арифметики, участвующее в формулировке теоремы Гёделя. Мы хотели бы иметь возможность отвечать на вопросы о перечислимых множествах в такой арифметике. В теореме 37.4 мы показали, что лишь перечислимые множества чисел могут иметь полуполное описание в формальной теории, т.е. существует перечислимое множество формул W_0,W_1,W_2,\ldots , такое, что Q=\{n\colon \vdash W_n\} . Адекватность нашей формальной теории (арифметики) могла бы означать, что она является полуполной для каждого перечислимого Множества натуральных чисел, т.е. что в ней имеет полуполное описание всякое множество, которое вообще может иметь такое описание хотя бы в какой-нибудь теории.

В теореме 37.1 мы установили, что множество всех теорем фор. мальной теории перечислимо, т.е. все теоремы и, значит, приво-дящие к ним выводы (доказательства) могут быть эффективно перенумерованы. Возьмем наше множество Q и соответствующее ему множество теорем \{W_0,W_1,W_2,\ldots\} . Рассмотрим следующий предикат P(x,y)\colon " y - номер доказательства теоремы W_x ". Если высказывание P(m,n) истинно, то это означает, что n есть номер вывода теоремы W_m , что, в свою очередь, означает, что m\in Q , т.е. n есть номер вывода о том, что m\in Q . Обратно, взяв конкретные числа m и n , мы можем эффективно построить теорему (формулу) W_m и эффективно построить n-й вывод, после чего эффективно определить, является ли построенный вывод выводом теоремы W_m , т.е. эффективно узнать, истинно ли высказывание P(m,n) . Следовательно, P(x,y) - такой вычислимый предикат, что .

Сформулируем теперь определение.

Определение 37.9. Формальная арифметика называется адекватной, если для каждого перечислимого множества Q натуральных чисел существует вполне представимый в этой арифметике предикат P(x,y) такой, что Q=\bigl\{x\colon (\exists y)(\lambda =1)\bigr\} .

Под полнотой формальной арифметики будем понимать абсолютную полноту, т.е. если для каждой замкнутой формулы F этой теории либо она сама, либо ее отрицание является теоремой этой теории: \vdash F или \vdash\lnot F .

Теперь мы можем перейти непосредственно к формулировке и доказательству теоремы Гёделя.

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

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

▼ Доказательство

Согласно теореме 35.7, выберем такое множество Q натуральных чисел, которое перечислимо, но неразрешимо. Так как наша формальная арифметика адекватна, то существует вполне представимый в ней перидикат P(x,y) такой, что

Q= \bigl\{x\colon\, (\exists y)\bigl(\lambda =1\bigr)\bigr\}.

Вполне представимость предиката P(x,y) в формальной арифметике означает, что найдется такая формула F(x,y) этой теории, содержащая лишь две свободных предметных переменных, что для каждой пары натуральных чисел (a,b) , для которой , имеет место теорема: \vdash F(a^{\ast},b^{\ast}) , а для каждой пары натуральных чисел (a,b) , для которой \lambda =1 , имеет место теорема: \vdash\lnot F(a^{ast},b^{\ast}) .

Применим к формуле F(x,y) квантор общности по переменной y . Получим формулу с единственной свободной предметной переменной x\colon\, G(x)\equiv (\exists y)(F(x,y)) . Покажем, что

Q= \bigl\{x\colon\, \vdash G(x^{\ast})\bigr\}.

Предположим, что m\in Q . Тогда (согласно (*)) найдется такое натуральное n , что высказывание P(m,n) истинно. Следовательно, имеет место теорема: \vdash F(m^{\ast},n^{\ast}) В силу аксиомы арифметики \text{AA} имеем теорему:

\vdash F(m^{\ast},n^{\ast})\to (\exists y)\bigl(F(m^{\ast},y)\bigr).

Из двух последних теорем по правилу МР заключаем:

\vdash (\exists y)\bigl(F(m^{\ast},y)\bigr) , то есть .

Это означает, что m\in \bigl\{x\colon \vdash G(x^{\ast})\bigr\} . Таким образом, Q \subseteq \bigl\{x\colon\vdash G(x^{\ast})\bigr\} .

Обратно, предположим, что m\in \bigl\{x\colon\vdash G(x^{\ast})\bigr\} , то есть \vdash G(m^{\ast}) , то есть \vdash (\exists y)(F(m^{\ast},y)) . Отсюда, в силу известного выражения (по закону де Моргана) квантора существования через квантор общности, заключаем, что

\vdash\lnot (\forall y)\bigl(\lnot F(m^{\ast},y)\bigr).

Поскольку наша формальная арифметика, кроме того, со-непро-тиворечива, то, ввиду наличия в ней последней теоремы, должно существовать такое натуральное число n_0 , что формула - \lnot F(m^{\ast},n^{\ast}_0) не является теоремой этой арифметики. А раз так, то высказывание P(m,n_0) истинно (если бы оно было ложно, то мы имели бы теорему \vdash\lnot F(m^{\ast},n^{\ast}_0) , что не так). По определению (*) множества Q , это означает, что m\in Q . Таким образом, \{x\colon\vdash G(x^{\ast})\}\subseteq Q . Итак, равенство (**) доказано.

Теперь выясним, в каком отношении находятся между собой множества \overline{Q} (дополнение Q ) и \{x\colon\vdash G(x^{\ast})\} . Пусть me m\in \{x\colon\vdash\lnot G(x^{\ast})\} , то есть \vdash\lnot G(x^{\ast}) . Тогда m\in \overline{Q} , ибо если бы m\in Q , то в силу (**) мы имели бы \vdash G(m^{\ast}) и наша формальная арифметика была бы противоречивой, но это не так в силу ее ©-непротиворечивости (по условию) и теоремы 37.7. Таким образом, \{x\colon\vdash G(x^{\ast})\}\subseteq \overline{Q} .

Покажем, что последнее включение является строгим. Напомним, что мы выбрали множество Q перечислимым, но не являющимся разрешимым. Тогда согласно следствию 37.5 из теоремы 37.4, никакая формальная теория не может быть полной для Q . Равенство (**) говорит, что наша формальная арифметика полуполна для Q . Если бы имело место равенство \overline{Q}= \{x\colon\vdash G(x^{\ast})\} , то это означало бы, что наша формальная арифметика полуполна и для \overline{Q} и, значит, она была бы полной для Q . Последнее невозможно в силу следствия 37.5 из теоремы_37.4. Следовательно, \{x\colon\vdash G(x^{\ast})\}\ne \overline{Q} .

Итак, \{x\colon\vdash\lnot G(x^{\ast})\}\subset \overline{Q} . Следовательно, существует такое число m_0\in \overline{Q} , что m_0\notin \{x\colon\vdash\lnot G(x^{\ast})\} , т. е. неверно, что \vdash\lnot G(m_0^{\ast}) . В тоже время неверно также, что \vdash G(m_0^{\ast}) , поскольку это, в силу (**), означало бы, что m_0\in Q , а это не так. Следовательно, мы нашли формулу G(m_0^{\ast}) , такую, что ни она сама, ни ее отрицание не являются теоремами нашей формальной арифметики. Это и означает, что данная формальная арифметика не является полной.

Теорема Гёделя полностью доказана.

Обратимся еще раз к высказыванию \lnot G(m_0^{\ast}) . Согласно равенству (**), его можно интерпретировать как m_0\on \overline{Q} и, следовательно, оно обязательно является "истинным" высказыванием. Но тем не менее оно не является теоремой нашей формальной арифметики. Если добавить формулу G(m_0^{\ast}) к списку аксиом и рассмотреть новую формальную арифметику, то положение не изменится: для вновь полученной формальной арифметики верны все те предпосылки, которые привели нас к теореме Гёделя. Значит, мы снова найдем такое число m_1 , что высказывание \lnot G(m_1^{\ast}) истинно, но не является теоремой новой формальной арифметики и т.д.

Гёдель и его роль в математической логике XX в

Курт Гёдель родился 28 апреля 1906 г. в г. Брюнне (ныне г. Брно в Чехии). Окончил Венский университет, где защитил докторскую диссертацию и был доцентом в период 1933- 1938 гг. После оккупации Австрии фашистской Германией эмигрировал в США. С 1940 по 1963 г. Гёдель работает в Принстонском институте высших исследований (с 1953 г. он профессор этого института). Гёдель - почетный доктор Йельского и Гарвардского университетов, член Национальной академии наук США и Американского философского общества. В 1951 г. Гёдель удостоен высшей научной награды США - Эйнштейновской премии. В статье, посвященной этому событию, другой крупнейший математик нашего времени Джон фон Нейман писал: "Вклад Курта Гёделя в современную логику поистине монументален. Это - больше, чем просто монумент, это веха, разделяющая две эпохи... Без всякого преувеличения можно сказать, что работы Гёделя коренным образом изменили сам предмет логики как науки". Гёдель заложил основы целых разделов математической логики: теории моделей (1930), конструктивной логики (1932-1933), формальной арифметики (1932-1933), теории алгоритмов и рекурсивных функций (1934), аксиоматической теории множеств (1938). Гёдель умер в Принстоне (США) 14 января 1978 г.

В вашем браузере отключен Javascript.
Чтобы произвести расчеты, необходимо разрешить элементы ActiveX!

Одной из самых известных теорем математической логики, повезло и не повезло одновременно. В этом она похожа на специальную теорию относительности Эйнштейна. С одной стороны, почти все о них что-то слышали. С другой - в народной интерпретации теория Эйнштейна, как известно, «говорит, что всё в мире относительно» . А теорема Гёделя о неполноте (далее просто ТГН), в примерно столь же вольной фолк-формулировке, «доказывает, что есть вещи, непостижимые для человеческого разума» . И вот одни пытаются приспособить её в качестве аргумента против материализма , а другие, напротив, доказывают с её помощью, что бога нет . Забавно не только то, что обе стороны не могут оказаться правыми одновременно, но и то, что ни те, ни другие не удосуживаются разобраться, что же, собственно, эта теорема утверждает.

Итак, что же? Ниже я попытаюсь «на пальцах» рассказать об этом. Изложение моё будет, разумеется нестрогим и интуитивным, но я попрошу математиков не судить меня строго. Возможно, что для нематематиков (к которым, вообще-то, отношусь и я), в рассказанном ниже будет что-то новое и полезное.

Математическая логика - наука действительно довольно сложная, а главное - не очень привычная. Она требует аккуратных и строгих манёвров, при которых важно не перепутать реально доказанное с тем, что «и так понятно». Тем не менее, я надеюсь, что для понимания следующего ниже «наброска доказательства ТГН» читателю понадобится только знание школьной математики/информатики, навыки логического мышления и 15-20 минут времени.

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

Начнём с того, что попытаемся разобраться, что такое доказательство. Возьмём какую-нибудь школьную задачку по арифметике. Например, пусть требуется доказать верность следующей незамысловатой формулы: « » (напомню, что символ читается «для любого» и называется «квантор всеобщности»). Доказать её можно, тождественно преобразуя, скажем, так:

Переход от одной формулы к другой происходит по некоторым известным правилам. Переход от 4-й формулы к 5-й произошёл, скажем, потому, что всякое число равно самому себе - такова аксиома арифметики. А вся процедура доказывания, таким образом, переводит формулу в булево значение ИСТИНА. Результатом могла быть и ЛОЖЬ - если бы мы опровергали какую-то формулу. В таком случае мы бы доказали её отрицание. Можно себе представить программу (и такие программы действительно написаны), которые бы доказывали подобные (и более сложные) высказывания без участия человека.

Изложим то же самое чуть более формально. Пусть у нас есть множество, состоящее из строк символов какого-то алфавита, и существуют правила, по которым из этих строк можно выделить подмножество так называемых высказываний - то есть грамматически осмысленных фраз, каждая из которых истинна или ложна. Можно сказать, что существует функция , сопоставляющая высказываниям из одно из двух значений: ИСТИНА или ЛОЖЬ (то есть отображающая их в булево множество из двух элементов).

Назовём такую пару - множество высказываний и функция из в - «языком высказываний» . Заметим, что в повседневном смысле понятие языка несколько шире. Например, фраза русского языка «А ну иди сюда!» не истинна и не ложна, то есть высказыванием, с точки зрения математической логики, не является.

Для дальнейшего нам понадобится понятие алгоритма. Приводить здесь формальное его определение я не буду - это завело бы нас довольно далеко в сторону. Ограничусь неформальным: «алгоритм» - эта последовательность однозначных инструкций («программа»), которая за конечное число шагов переводит исходные данные в результат. Выделенное курсивом принципиально важно - если на каких-то начальных данных программа зацикливается, то алгоритма она не описывает. Для простоты и в применении к нашему случаю читатель может считать, что алгоритм - это программа, написанная на любом известном ему языке программирования, которая для любых входных данных из заданного класса гарантированно завершает свою работу с выдачей булевого результата.

Спросим себя: для всякой ли функции существует «доказывающий алгоритм» (или, короче, «дедуктика» ), эквивалентный этой функции, то есть переводящий каждое высказывание именно в то булево значение, что и она? Лаконичнее тот же вопрос можно сформулировать так: всякая ли функция над множеством высказываний вычислима ? Как вы уже догадываетесь, из справедливости ТГН следует, что нет, не всякая - существуют невычислимые функции такого типа. Иными словами, не всякое верное высказывание можно доказать.

Очень может быть, что это утверждение вызовет у вас внутренний протест. Связано это с несколькими обстоятельствами. Во-первых, когда нас учат школьной математике, то иногда возникает ложное впечатление почти полной тождественности фраз «теорема верна» и «можно доказать или проверить теорему ». Но, если вдуматься, это совершенно не очевидно. Некоторые теоремы доказываются довольно просто (например, перебором небольшого числа вариантов), а некоторые - очень сложно. Вспомним, например, знаменитую Великую теорему Ферма :

доказательство которой нашли только через три с половиной века после первой формулировки (и оно далеко не элементарно). Следует различать истинность высказывания и его доказуемость. Ниоткуда не следует, что не существует истинных, но недоказуемых (и не проверяемых в полной мере) высказываний.

Второй интуитивный довод против ТГН более тонок. Допустим, у нас есть какое-то недоказуемое (в рамках данной дедуктики) высказывание. Что мешает нам принять его в качестве новой аксиомы? Тем самым мы чуть усложним нашу систему доказательств, но это не страшно. Этот довод был бы совершенно верен, если бы недоказуемых высказываний было конечное число. На практике же может произойти следующее - после постулирования новой аксиомы вы наткнётесь на новое недоказуемое высказывание. Примете его в качестве ещё аксиомы - наткнётесь на третье. И так до бесконечности. Говорят, что дедуктика останется неполной . Мы можем также принять силовые меры, чтобы доказывающий алгоритм заканчивался через конечное число шагов с каким-то результатом для любого высказывания языка. Но при этом он начнёт врать - приводить к истине для неверных высказываний, или ко лжи - для верных. В таких случаях говорят, что дедуктика противоречива . Таким образом, ещё одна формулировка ТГН звучит так: «Существуют языки высказываний, для которых невозможна полная непротиворечивая дедуктика» - отсюда и название теоремы.

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

Замечу также, что если бы речь шла о привычных функциях, отображающих множество вещественных чисел в него же, то «невычислимость» функции никого бы не удивила (только не надо путать «вычислимые функции» и «вычислимые числа» - это разные вещи). Любому школьнику известно, что, скажем, в случае функции вам должно сильно повезти с аргументом, чтобы процесс вычисления точного десятичного представления значения этой функции окончился за конечное число шагов. А скорее всего вы будете вычислять её с помощью бесконечного ряда, и это вычисление никогда не приведёт к точному результату, хотя может подойти к нему как угодно близко - просто потому, что значение синуса большинства аргументов иррационально. ТГН просто говорит нам о том, что даже среди функций, аргументами которой являются строки, а значениями - ноль или единица, невычислимые функции, хотя и совсем по другому устроенные, тоже бывают.

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

Примеры высказываний формальной арифметики:

и т.д. Теперь назовём «формулой со свободным параметром» (ФСП) строку, которая становится высказыванием, если в качестве этого параметра подставить в неё натуральное число. Примеры ФСП (с параметром ):

и т.д. Иными словами, ФСП эквивалентны функциям натурального аргумента с булевыми значением.

Обозначим множество всех ФСП буквой . Понятно, что его можно упорядочить (например, сначала выпишем упорядоченные по алфавиту однобуквенные формулы, за ними - двухбуквенные и т.д.; по какому именно алфавиту будет происходить упорядочивание, нам непринципиально). Таким образом, любой ФСП соответствует её номер в упорядоченном списке, и мы будем обозначать её .

Перейдём теперь к наброску доказательства ТГН в такой формулировке:

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

Доказывать будем от противного.

Итак, допустим, что такая дедуктика существует. Опишем следующий вспомогательный алгоритм , ставящий в соответствие натуральному числу булево значение следующим образом:

Проще говоря, алгоритм приводит к значению ИСТИНА тогда и только тогда, когда результат подстановки в ФСП её собственного номера в нашем списке даёт ложное высказывание.

Тут мы подходим к единственному месту, в котором я попрошу читателя поверить мне на слово.

Очевидно, что, при сделанном выше предположении, любой ФСП из можно сопоставить алгоритм, содержащий на входе натуральное число, а на выходе – булево значение. Менее очевидно обратное утверждение:

Доказательство этой леммы потребовало бы, как минимум, формального, а не интуитивного, определения понятия алгоритма. Однако, если немного подумать, то она довольно правдоподобна. В самом деле, алгоритмы записываются на алгоритмических языках, среди которых есть такие экзотические, как, например, Brainfuck , состоящий из восьми односимвольных слов, на котором, тем не менее, можно реализовать любой алгоритм. Странно было бы, если бы описанный нами более богатый язык формул формальной арифметики оказался бы беднее - хотя, без сомнения, для обычного программирования он не очень подходит.

Пройдя это скользкое место, мы быстро добираемся до конца.

Итак, выше мы описали алгоритм . Согласно лемме, в которую я попросил вас поверить, существует эквивалентная ему ФСП. Она имеет какой-то номер в списке - скажем, . Спросим себя, чему равно ? Пусть это ИСТИНА. Тогда, по построению алгоритма (а значит, и эквивалентной ему функции ), это означает, что результат подстановки числа в функцию - ЛОЖЬ. Аналогично проверяется и обратное: из ЛОЖЬ следует ИСТИНА. Мы пришли к противоречию, а значит, исходное предположение неверно. Таким образом, для формальной арифметики не существует полной непротиворечивой дедуктики. Что и требовалось доказать.

Здесь уместно вспомнить Эпименида (см. портрет в заголовке), который, как известно, заявил, что все критяне - лжецы, сам являясь критянином. В более лаконичной формулировке его высказывание (известное как «парадокс лжеца») можно сформулировать так: «Я лгу». Именно такое высказывание, само превозглашающее свою ложность, мы и использовали для доказательства.

В заключение я хочу заметить, что ничего особенного удивительного ТГН не утверждает. В конце концов, все давно привыкли, что не все числа представимы в виде отношения двух целых (помните, у этого утверждения есть очень изящное доказательство , которому больше двух тысяч лет?). И корнями полиномов с рациональными коэффициентами являются тоже не все числа . А теперь вот выяснилось, что не все функции натурального аргумента вычислимы.

Приведённый набросок доказательства относился к формальной арифметике, но нетрудно понять, что ТГН применима и к многим другим языкам высказываний. Разумеется, не всякие языки таковы. Например, определим язык следующим образом:

«Любая фраза китайского языка является верным высказыванием, если она содержится в цитатнике товарища Мао Дзе Дуна, и неверна, если не содержится».

Тогда соответствующий полный и непротиворечивый доказывающий алгоритм (его можно назвать «догматической дедуктикой») выглядит примерно так:

«Листай цитатник товарища Мао Дзе Дуна, пока не найдёшь искомое высказывание. Если оно найдено, то оно верно, а если цитатник закончился, а высказывание не найдено, то оно неверно».

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

Переломным открытием математики ХХ века были теоремы о неполноте Курта Геделя. А в его рукописях, опубликованных после смерти, сохранилось логическое доказательство существования Бога. На последних Рождественских чтениях интересный доклад об этом малоизвестном наследии сделал доцент Тобольской духовной семинарии, кандидат богословия иерей Димитрий КИРЬЯНОВ. «НС» попросил объяснить главные идеи ученого.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если формальная арифметика 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 ] обозначим формулу, которая образуется из класс-выражения α заменой свободной переменной на символ натурального числа 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 ] вместе со своим отрицанием будет выводимо, что снова невозможно.

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

Для каждой непротиворечивой теории T можно указать такое целое значение параметра K, что уравнение (θ + 2z − 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 + 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 − 2w 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 + (2r + 1 + φ − c ) 2 + (b w + c a − 2c + 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)(2r + 1 + j c ) 2 + 1 − (d + o f ) 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 .

Примечания

См. также

Ссылки

В. А. Успенский Теорема Гёделя о неполноте . - М.: Наука, 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.

Wikimedia Foundation . 2010 .

Смотреть что такое "Теоремы Гёделя о неполноте" в других словарях:

У этого термина существуют и другие значения, см. Теорема Гёделя. Теорема Гёделя о неполноте и вторая теорема Гёделя[ 1] две теоремы математической логики о принципиальных ограничениях формальной арифметики и, как следствие, всякой… … Википедия

Теоремы Гёделя о неполноте две теоремы математической логики о неполноте формальных систем определённого рода. Содержание 1 Первая теорема Гёделя о неполноте 2 Вторая теорема Гёделя о неполноте … Википедия

У этого термина существуют и другие значения, см. Теорема Гёделя. Теорема Гёделя о полноте исчисления предикатов является одной из фундаментальных теорем математической логики: она устанавливает однозначную связь между логической истинностью… … Википедия

Общее название двух теорем, установленных К. Гёделем . Первая Г. т. о н. утверждает, что в любой непротиворечивой формальной системе, содержащей минимум арифметики (знаки и обычные правила обращения с ними), найдется формально неразрешимое… … Математическая энциклопедия

Давно интересовался, что собой представляет нашумевшая теорема Гёделя. И чем она полезна для жизни. И наконец смог разобраться.

Самая популярная формулировка теоремы звучит так:
"Всякая система математических аксиом начиная с определенного уровня сложности либо внутренне противоречива, либо неполна ."

На человеческий нематематический язык я перевёл бы это так (аксиома - исходное положение какой-либо теории, принимаемое в рамках данной теории истинным без требования доказательства и используемое в основе доказательства других ее положений). В жизни аксиома - это принципы, которым следуют человек, общество, научное направление, государства. У представителей религии аксиомы называются догмами. Следовательно, любые наши принципы, любая система взглядов, начиная с некоторого уровня, становится внутренне противоречива, или неполна. Для того, чтобы убедиться в истинности некоего утверждения, придётся выйти за рамки данной системы взглядов и построить новую. Но она также будет несовершенной. Т.е., ПРОЦЕСС ПОЗНАНИЯ БЕСКОНЕЧЕН. Мир нельзя познать до конца, пока мы не достигнем первоисточника.

"...если считать умение логически рассуждать основной характеристикой человеческого разума или, по крайней мере, главным его инструментом, то теорема Гёделя прямо указывает на ограниченность возможностей нашего мозга. Согласитесь, что человеку, воспитанному на вере в бесконечное могущество мысли, очень трудно принять тезис о пределах ее власти... Многие специалисты полагают, что формально-вычислительные, «аристотелевские» процессы, лежащие в основе логического мышления, составляют лишь часть человеческого сознания. Другая же его область, принципиально «невычислительная», отвечает за такие проявления, как интуиция, творческие озарения и понимание. И если первая половина разума подпадает под гёделевские ограничения, то вторая от подобных рамок свободна... Физик Роджер Пенроуз — пошел еще дальше. Он предположил существование некоторых квантовых эффектов невычислительного характера, обеспечивающих реализацию творческих актов сознания... Одним их многочисленных следствий гипотезы Пенроуза может стать, в частности, вывод о принципиальной невозможности создания искусственного интеллекта на основе современных вычислительных устройств, даже в том случае, если появление квантовых компьютеров приведет к грандиозному прорыву в области вычислительной техники. Дело в том, что любой компьютер может лишь всё более детально моделировать работу формально-логической, «вычислительной» деятельности человеческого сознания, но «невычислительные» способности интеллекта ему недоступны."

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

Следующий вывод. Добро и зло - это всего лишь 2 стороны одной медали, без которых она не может существовать. А исходит оно из принципа, что во Вселенной есть только один источник всего: добра и зла, любви и ненависти, жизни и смерти.

Любое объявление законченности системы - ложно. Нельзя опираться на догмы, потому что рано или поздно они будут опровергнуты.

В этом смысле, современные религии находятся в критическом положении: догматы церкви противятся развитию наших представлений о мире. Пытаются всё втиснуть в рамки жёстких концепций. Но это приводит к тому, что от Единобожия, от единого источника всех природных процессов они переходят к язычеству, где есть силы добра и силы зла, есть бог добра где-то далеко в небесах, а есть дьявол (бог зла), который давно уже наложил лапу на всё, что есть на Земле. Такой подход приводит к делению всех людей на своих и чужих, на праведников и грешников, на верующих и еретиков, на друзей и врагов.

Вот ещё один небольшой текст , популярно раскрывающий суть, вытекающую из теоремы Гёделя:
"Мне представляется, что это теорема несет важный философский смысл. Возможны лишь два варианта:

а) Теория неполна, т.е. в терминах теории можно сформулировать такой вопрос, на который невозможно вывести из аксиом/постулатов теории ни положительный, ни отрицательный ответ. При этом ответы на все такие вопросы можно дать в рамках более всеобъемлющей теории, в которой старая будет частным случаем. Но эта новая теория будет иметь свои собственные "вопросы без ответов" и так до бесконечности.

б) Полна, но противоречива. Можно ответить на любой вопрос, но на некоторые вопросы можно вывести и положительный и отрицательный ответ одновременно.

Научные теории относятся к первому типу. Они непротиворечивы, но из этого означает, что не описывают все. Не может быть никакой "окончательной" научной теории. Любая теория неполна и что-то не описывает, даже если мы пока не знаем, что именно. Можно только создавать все более и более всеобъемлющие теории. Для меня лично это повод для оптимизма, ведь это означает, что движение науки вперед никогда не остановится.

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

В общем, научное знание верно (непротиворечиво), но в любой момент времени описывает не все. При этом ничто не мешает раздвигать границы познанного до бесконечности, все далее и далее и рано или поздно любое непознанное становится познанным. Религия же претендует на полное описание мира "прямо сейчас", но при этом автоматически неверна (абсурдна)."

В своё время, когда я только начинал свою взрослую жизнь, я занимался программированием. И там был такой принцип: если в программу вносится много исправлений, её надо переписать заново. Этот принцип, на мой взгляд, соответствует теореме Гёделя. Если программа усложняется, она становится противоречивой. И работать правильно не будет.

Ещё один пример из жизни. Мы живём в эпоху, когда чиновники заявляют, что главным принципом существования должен быть закон. Т.е., правовая система. Но как только начинается усложнение законодательства и процветание нормотворчества, законы начинают противоречить друг другу. Что мы сейчас и наблюдаем. Никогда нельзя создать такую правовую систему, которая прописала бы все стороны жизни. И с другой стороны, была бы справедливой для всех. Потому что всегда будет вылезать ограниченность нашего представления о мире. И человеческие законы начнут в какой-то момент входить в противоречие с законами Вселенной. Многие вещи мы понимаем интуитивно. Также интуитивно мы должны судить и о поступках других людей. Государству достаточно иметь конституцию. И опираясь на статьи этой конституции, регулировать взаимоотношения в обществе. Но рано или поздно, придётся менять и конституцию.

ЕГЭ - это ещё один пример ошибочности наших представлений о возможностях человека. Мы пытаемся проверять на экзамене вычислительные возможности мозга. Но интуитивные возможности в школе перестали развивать. Но человек - не биоробот. Нельзя создать систему баллов, которая бы смогла выявить все возможности, заложенные в человеке, в его сознании, в его подсознании и в его психике.

Почти 100 лет назад Гёдель сделал невероятной шаг в понимании законов Вселенной. А мы до сих пор не смогли этим воспользоваться, рассматривая эту теорему как узкоспециализированную математическую задачку для узкого же круга людей, занимающихся какими-то отвлечёнными темами в своём кругу. Вместе с квантовой теорией и учением Христа теорема Гёделя даёт возможность нам вырваться из плена ложных догм, преодолеть тот кризис, который пока ещё сохраняется в нашем мировоззрении. А времени остаётся всё меньше.