Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


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


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




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


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


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


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


Теорема 37.1. Множество [math]\operatorname{Th}(T)[/math] всех теорем формальной аксиоматической теории Т перечислимо.


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


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


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


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


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


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


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


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


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




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


Формальная арифметика как формальная аксиоматическая теория строится на базе формализованного исчисления предикатов, рассмотренного ранее. Предметные переменные [math]x_1,x_2,x_3,\ldots[/math] здесь будем называть числовыми, потому что вместо них будем подставлять натуральные числа.


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


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


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


[math]\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}[/math]

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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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




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


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


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

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


[math]Q= \bigl\{x\colon\, (\exists y)\bigl(\lambda [P(x,y)]=1\bigr)\bigr\}.[/math]
(*)

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


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


[math]Q= \bigl\{x\colon\, \vdash G(x^{\ast})\bigr\}.[/math]
(**)

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


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

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


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

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


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


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

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


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


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


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


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


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




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


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


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved