Главная » Авто / Мото » Суть теоремы к геделя в. Исповедание великого логика

Суть теоремы к геделя в. Исповедание великого логика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Успенский В.А.

Пожалуй, теорема Геделя о неполноте является воистину уникальной. Уникальной в том, что на нее ссылаются, когда хотят доказать "все на свете" - от наличия богов до отсутствия разума. Меня всегда интересовал более "первичный вопрос" - а кто из ссылающихся на теорему о неполноте смог-бы не только сформулировать ее, но и доказать? Я публикую данную статью по той причине, что в ней изложена вполне доступная формулировка теоремы Геделя. Рекомендую предварительно ознакомиться со статьей Туллио Редже Курт Гедель и его знаменитая теорема

Вывод о невозможности универсального критерия истины является непосредственным следствием результата, полученного Тарским путем соединения теоремы Геделя о неразрешимости с его собственной теорией истины, согласно которому универсального критерия истины не может быть даже для относительно узкой области теории чисел, а значит, и для любой науки, использующей арифметику. Естественно, что этот результат применим a fortiori к понятию истины в любой нематематической области знания, в которой широко используется арифметика.

Карл Поппер

Успенский Влaдимиp Aндpеевич pодился 27 ноябpя 1930 г. в г. Москве. Окончил мехaнико-мaтемaтический фaкультет МГУ (1952). Доктоp физико-мaтемaтических нaук (1964). Пpофессоp, заведующий кaфедpой мaтемaтической логики и теоpии aлгоpитмов мехaнико-мaтемaтического фaкультетa (1966). Читает курсы лекций "Введение в математическую логику", "Вычислимые функции", "Теорема Геделя о полноте". Подготовил 25 кандидатов и 2 докторов наук

1. Постановка задачи

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

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

1.1. Язык

Мы не будем давать наиболее общее из возможных определений языка, предпочтя ограничиться теми языковыми концепциями, которые нам понадобятся впоследствии. Есть два таких понятия: "алфавит языка" и "множество истинных утверждений языка".

1.1.1. Алфавит

Под алфавитом мы понимаем конечный набор элементарных знаков (то есть - вещей, которые невозможно разбить на составные части). Эти знаки называются буквами алфавита. Под словом алфавита мы понимаем конечную последовательность букв. Например, обыкновенные слова в английском языке (включая имена собственные) являются словами 54-хбуквенного алфавита (26 маленьких букв, 26 прописных, тире и апостроф). Другой пример - натуральные числа в десятичной записи являются словами 10-тибуквенного алфавита, чьи буквы - знаки: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Для обозначения алфавитов мы будем использовать обыкновенные заглавные буквы. Если L - алфавит, то L? будет обозначать множество всех слов алфавита L, - слов, образованных из его букв. Мы предположим, что любой язык имеет свой алфавит, так что все выражения этого языка (т. е. - имена различных объектов, утверждения относительно этих объектов и т.д.) являются словами этого алфавита. Например, любое предложение английского языка, равно как и любой текст, написанный по-английски, может рассматриваться как слово расширенного алфавита из 54-х букв, включающего также знаки пунктуации, междусловный пробел, знак красной строки и, возможно, некоторые другие полезные знаки. Предполагая, что выражения языка являются словами некоторого алфавита, мы, таким образом, исключаем из рассмотрения "многослойные" выражения типа???f(x)dx. Однако, это ограничение не слишком существенно, так как любое подобное выражение, при использовании подходящих конвенций, может быть "растянуто" в линейную форму. Любое множество М, содержащееся в L? называется словным множеством алфавита L. Если мы просто говорим, что М - словное множество, то мы подразумеваем, что оно является словом некоторого алфавита. Теперь сформулированное выше предположение о языке может быть перефразировано следующим образом: в любом языке любое множество выражений является словным множеством.

1.1.2. Множество истинных утверждений

Мы предположим, что нам задано подмножество Т множества L? (где L алфавит некоторого рассматриваемого нами языка), которое называется множеством "истинных утверждений" (или просто "истин"). Переходя непосредственно к подмножеству Т, мы опускаем следующие промежуточные шаги рассуждения: во-первых, какие именно слова алфавита L являются корректно образованными выражениями языка, то есть - имеющими определенное значение в нашей интерпретации этого языка (например, 2+3, х+3, х=у, х=3, 2=3, 2=2 являются корректно образованными выражениями, в то время как выражения типа +=х таковыми не являются); во-вторых, какие именно выражения являются формулами, т.е. могут зависеть от параметра (например, х=3, х=у, 2=3, 2=2); в третьих, какие именно из формул являются закрытыми формулами, т.е. утверждениями, не зависящими параметров (например, 2=3, 2=2); и наконец, какие именно закрытые формулы являются истинными утверждениями (например, 2=2).

1.1.3. Фундаментальная пара языка

1.2. "Недоказуемые"

"Недоказуемые" значит не имеющие доказательства.

1.3. Доказательство

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

Будучи записано, доказательство становится словом в некотором алфавите Р, так же как любой английский текст является словом алфавита L, пример которого был приведен выше. Множество всех доказательств образуют подмножество (и довольно-таки обширное подмножество) множества Р?. Мы не будем пытаться дать точное определение этой одновременно "наивной" и "абсолютной" концепции доказательства, или - что равносильно - дать определение соответствующему подмножеству Р?. Вместо этого мы рассмотрим формальный аналог этого смутного понятия, для обозначения которого в дальнейшем мы все же будем пользоваться термином "доказательство". Этот аналог имеет две весьма важные особенности, кои отличают его от интуитивного понятия (хотя интуитивная идея доказательства все же отражает в некоторой степени эти особенности). Прежде всего мы допустим, что существуют разные концепции доказательства, то есть - допустимы разные подмножества доказательств в Р?, и даже больше того: мы, на деле, будем допускать, что сам алфавит доказательств Р может изменяться. Далее мы потребуем, чтобы для каждой такой концепции доказательства существовал эффективный метод, другими словами, алгоритм, который бы с необходимостью определял, является ли данное слово алфавита Р доказательством или нет. Мы также предположим, что существует алгоритм, с помощью которого всегда можно определить, какое именно утверждение доказывает данное доказательство. (Во многих ситуациях доказываемым утверждением просто является последнее утверждение в последовательности шагов, образующих доказательство.)

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

(1) У нас имеются алфавит L (алфавит языка) и алфавит Р (алфавит доказательства).

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

(3) Также у нас есть функция? (для нахождения того, что именно было доказано), чья область определения? удовлетворяет условию Р???Р?, и чья область значений находится в Р?. Мы предполагаем, что у нас есть алгоритм, который вычисляет эту функцию (точное значение слов "алгоритм вычисляет функцию" следующее: значения функции получаются при помощи этого алгоритма - набора специальных правил преобразования). Мы будем говорить, что элемент р? Р есть доказательство слова?(р) алфавита L.

Тройка <Р, Р, ?>, удовлетворяющая условиям (1)-(3) называется дедуктивной системой над алфавитом L.

Для читателя, знакомого с обычным способом определения "доказательства" в терминах "аксиома" и "правило вывода", мы сейчас поясним, как этот метод может рассматриваться в качестве специального случая определения, данного в параграфе 1.3.2. То есть - доказательство обычно определяется как последовательность таких выражений языка, каждое из которых является либо аксиомой, либо ранее полученным из уже существующих утверждений при помощи одного из правил вывода. Если мы добавим новое слово * к алфавиту нашего языка, то мы сможем записать такое доказательство в виде слова составленного при помощи полученного в результате такой модификации алфавита: последовательность выражений становится словом C1*C2*...*Cn. В таком случае, функция, определяющая, что именно было доказано, своим значением имеет часть этого слова, стоящую сразу за последней в последовательности буквой *. Алгоритм, существование которого требуется в части 1.3.2. определения, может легко быть сконструирован, как только мы точно определим какое-либо из принятых значений слов "аксиома" и "правила вывода".

1.4.Попытки точной формулировки теоремы о неполноте

1.4.1. Первая попытка

"При определенных условиях для фундаментальной пары языка алфавита L и дедуктивной системы <Р, Р, ?> над L - всегда существует слово в Т, не имеющее доказательства". Этот вариант все еще выглядит смутным. В частности, мы могли бы запросто придумать сколько угодно дедуктивных систем, имеющих очень немного доказуемых слов. Например, в пустой дедуктивной системе (где Р = ?) совсем нет слов, у которых были бы доказательства.

1.4.2. Вторая попытка

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

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

Однако такое утверждение, очевидно, ложно, так как необходимо лишь взять такую дедуктивную систему, в которой Р = L, Р = Р? и?(р) = р для всех р из Р?; тогда каждое слово из L? является тривиально доказуемым. Следовательно, нам нужно принять некоторое ограничение на то, какими дедуктивными системами мы пользуемся.

1.5. Непротиворечивость

Было бы вполне естественно потребовать, что только "истинные утверждения", то есть только слова из Т, могут быть доказаны. Мы будем говорить, что дедуктивная система <Р, Р, ?> является непротиворечивой относительно фундаментальной пары, если?(Р)?Т. Во всех последующих рассуждениях нас будут интересовать только такие непротиворечивые дедуктивные системы. Если же нам задан язык, то было бы чрезвычайно соблазнительно найти такую непротиворечивую дедуктивную систему, в которой каждое истинное утверждение имело бы доказательство. Интересующий нас вариант теоремы Геделя в точности утверждает, что при определенных условиях относительно фундаментальной пары, невозможно найти такую дедуктивную систему.

1.6. Полнота

Говорится, что дедуктивная система <Р,Р,?> полна относительно фундаментальной пары, при условии если?(Р)?Т. Тогда наша формулировка теоремы о неполноте приобретает следующий вид:

При определенных условиях относительно фундаментальной пары, не существует такой дедуктивной системы <Р,Р,?> над L, которая была бы одновременно полна и непротиворечива относительно.

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://filosof.historic.ru

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Успенский В.А.

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

Theoretical Computer Science 130,1994, pp.273-238.

Вывод о невозможности универсального критерия истины является

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

теоремы Геделя о неразрешимости с его собственной теорией истины, согласно

которому универсального критерия истины не может быть даже для относительно

узкой области теории чисел, а значит, и для любой науки, использующей

арифметику. Естественно, что этот результат применим a fortiori к понятию истины

в любой нематематической области знания, в которой широко

используется арифметика.

Карл Поппер

1. Постановка задачи

1.1.1. Алфавит

1.1.2. Множество истинных утверждений

1.1.3. Фундаментальная пара языка

1.2. "Недоказуемые"

"Недоказуемые" значит не имеющие доказательства.

1.3. Доказательство

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

(1) У нас имеются алфавит L (алфавит языка) и алфавит Р (алфавит доказательства).

Тройка, удовлетворяющая условиям (1)-(3) называется дедуктивной системой над алфавитом L.

1.4.Попытки точной формулировки теоремы о неполноте

1.4.1. Первая попытка

"При определенных условиях для фундаментальной пары языка алфавита L и дедуктивной системы над L - всегда существует слово в Т, не имеющее доказательства". Этот вариант все еще выглядит смутным. В частности, мы могли бы запросто придумать сколько угодно дедуктивных систем, имеющих очень немного доказуемых слов. Например, в пустой дедуктивной системе (где Р = ?) совсем нет слов, у которых были бы доказательства.

1.4.2. Вторая попытка

1.5. Непротиворечивость

Было бы вполне естественно потребовать, что только "истинные утверждения", то есть только слова из Т, могут быть доказаны. Мы будем говорить, что дедуктивная система является непротиворечивой относительно фундаментальной пары, если?(Р)?Т. Во всех последующих рассуждениях нас будут интересовать только такие непротиворечивые дедуктивные системы. Если же нам задан язык, то было бы чрезвычайно соблазнительно найти такую непротиворечивую дедуктивную систему, в которой каждое истинное утверждение имело бы доказательство. Интересующий нас вариант теоремы Геделя в точности утверждает, что при определенных условиях относительно фундаментальной пары, невозможно найти такую дедуктивную систему.

1.6. Полнота

Говорится, что дедуктивная система полна относительно фундаментальной пары, при условии если?(Р)?Т. Тогда наша формулировка теоремы о неполноте приобретает следующий вид:

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