Вопрос о существовании бога и теорема Гёделя. Для математиков и логиков. Математическая логика и теорема Курта Гёделя Вторая теорема геделя
Переломным открытием математики ХХ века были теоремы о неполноте Курта Геделя. А в его рукописях, опубликованных после смерти, сохранилось логическое доказательство существования Бога. На последних Рождественских чтениях интересный доклад об этом малоизвестном наследии сделал доцент Тобольской духовной семинарии, кандидат богословия иерей Димитрий КИРЬЯНОВ. «НС» попросил объяснить главные идеи ученого.
Теоремы о неполноте Геделя: Дырка в математике
— Можно как-то популярно объяснить теоремы о неполноте Геделя? Брадобрей бреет только тех, кто не бреется сам. Бреет ли себя брадобрей? Этот знаменитый парадокс имеет к ним отношение?
Главный тезис логического доказательства существования Бога, выдвинутый Куртом Геделем: "Бог существует в мышлении. Но существование в реальности больше, нежели существование только в мысли. Следовательно, Бог должен существовать". На фото: автор теоремы о неполноте Курт Гедель со своим другом, автором теории относительности Альбертом Эйнштейном. Пристон. Америка. 1950
— Да, конечно, имеет. До Геделя существовала проблема аксиоматизации математики и проблема таких парадоксальных предложений, которые формально можно записать на любом языке. Например: «Это утверждение ложно». Какова истинность этого утверждения? Если оно истинно, значит, оно ложно, если оно ложно, значит, истинно; получается языковой парадокс. Гедель исследовал арифметику и показал в своих теоремах, что ее непротиворечивость не может быть доказана, исходя из ее самоочевидных принципов: аксиом сложения, вычитания, деления, умножения и проч. Нам требуются для ее обоснования некоторые дополнительные допущения. Это на самой простейшей теории, а что говорить о более сложных (уравнениях физики и т. п.)! Всегда для обоснования какой-то системы умозаключений мы вынуждены прибегать к некоему дополнительному умозаключению, которое в рамках системы не обосновывается.
Прежде всего это указывает на ограниченность претензий человеческого разума в познании реальности. То есть мы не можем говорить о том, что мы построим какую-то всеобъемлющую теорию мироздания, которая все объяснит, — такая теория не может быть научной.
— Как математики сейчас относится к теоремам Геделя? Никто не пытается их опровергнуть, как-то обойти?
— Это все равно что пытаться опровергнуть теорему Пифагора. Теоремы имеют строгое логическое доказательство. В то же время предпринимаются попытки найти ограничения применимости теорем Геделя. Но главным образом споры идут вокруг философских следствий теорем Геделя.
— Насколько проработано геделево доказательство существования Бога? Оно закончено?
— Оно проработано детально, хотя сам ученый до самой своей смерти так и не решился его опубликовать. Гедель развивает онтологический (метафизический. — «НС» ) аргумент, впервые предложенный Ансельмом Кентерберийским. В сжатой форме этот аргумент можно представить следующим образом: «Бог, по определению, является Тем, больше Кого нельзя ничего помыслить. Бог существует в мышлении. Но существование в реальности больше, нежели существование только в мысли. Следовательно, Бог должен существовать». Аргументацию Ансельма позднее развивали Рене Декарт и Готфрид Вильгельм Лейбниц. Так, по мнению Декарта, мыслить Высшее Совершенное Бытие, которому недостает существования, означает впадать в логическое противоречие. В контексте этих идей Гедель разрабатывает свою версию доказательства, она умещается буквально на двух страничках. К сожалению, изложение его аргументации невозможно без введения в основы очень сложной модальной логики.
Разумеется, логическая безупречность выводов Геделя не принуждает человека становиться верующим под давлением силы доказательств. Не следует быть наивными и полагать, что мы можем убедить любого разумно мыслящего человека уверовать в Бога с помощью онтологического аргумента или других доказательств. Вера рождается тогда, когда человек становится лицом к лицу перед очевидным присутствием высшей трансцендентной Реальности Бога. Но можно назвать по крайней мере одного человека, которого онтологическое доказательство привело к религиозной вере, — это писатель Клайв Стейплз Льюис, он сам признавался в этом.
Отдаленное будущее — это отдаленное прошлое
— Как относились к Геделю современники? Он дружил с кем-то из больших ученых?
— Ассистент Эйнштейна в Принстоне свидетельствует, что единственным человеком, с которым тот дружил в последние годы жизни, был Курт Гедель. Они были различны почти во всем — Эйнштейн общительный, веселый, а Гедель предельно серьезный, совершенно одинокий и недоверчивый. Но они имели общее качество: оба шли прямо и искренне к центральным вопросам науки и философии. Несмотря на дружбу с Эйнштейном, Гедель имел свой специфический взгляд на религию. Он отвергал представление о Боге как безличном существе, каким был Бог для Эйнштейна. По этому поводу Гедель заметил: «Религия Эйнштейна является слишком абстрактной, как у Спинозы и в индийской философии. Бог Спинозы меньше, чем личность; мой Бог больше чем личность; поскольку Бог может играть роль личности». Могут существовать духи, которые не имеют тела, но могут общаться с нами и оказывать влияние на мир».
— Как Гедель оказался в Америке? Бежал от нацистов?
— Да, он приехал в Америку в 1940 году из Германии, несмотря на то что фашисты признали его арийцем и великим ученым, освободив от военной службы. Он с женой Аделе пробирался через Россию по Транссибирской магистрали. Воспоминаний об этом путешествии он не оставил. Аделе вспоминает только о постоянном страхе по ночам, что остановят и вернут обратно. После восьми лет проживания в Америке Гедель стал гражданином США. Как и все подающие на гражданство, он должен был ответить на вопросы, касающиеся американской Конституции. Будучи скрупулезным человеком, он готовился к этому экзамену очень тщательно. Наконец сообщил, что нашел непоследовательность в Конституции: «Я открыл логически законную возможность, при которой США может стать диктатурой». Его друзья признали, что, независимо от логических достоинств аргумента Геделя, эта возможность была чисто гипотетической по своему характеру, и предостерегли от пространных разговоров на эту тему на экзамене.
— Не использовали ли Гедель и Эйнштейн идей друг друга в научной работе?
— В 1949 году Гедель выразил свои космологические идеи в математическом эссе, которое, по мнению Альберта Эйнштейна, являлось важным вкладом в общую теорию относительности. Гедель считал, что время — «эта таинственная и одновременно самопротиворечивая сущность, которая формирует основу мира и нашего собственного существования», — в конце концов станет величайшей иллюзией. Оно «когда-то» перестанет существовать, и наступит иная форма бытия, которую можно назвать вечностью. Такое представление о времени привело великого логика к неожиданному выводу. Он писал: «Я убежден в посмертном существовании, независимо от теологии. Если мир является разумно сконструированным, тогда должно быть посмертное существование».
— «Время – самопротиворечивая сущность». Странно звучит; это имеет какой-то физический смысл?
— Гедель показал, что в рамках уравнения Эйнштейна можно построить космологическую модель с замкнутым временем, где удаленное прошлое и удаленное будущее совпадают. В этой модели становится теоретически возможным путешествие во времени. Это звучит странно, но это математически выразимо — вот в чем дело. Эта модель может иметь экспериментальные следствия, а может и не иметь. Она является теоретической конструкцией, которая может оказаться полезной при построении новых космологических моделей — а может оказаться излишней. Современная теоретическая физика, в частности квантовая космология, обладает столь сложной математической структурой, что этим структурам очень сложно дать однозначное философское осмысление. Более того, некоторые ее теоретические конструкции пока являются экспериментально непроверяемыми по той простой причине, что для своей проверки требуют обнаружения очень высокоэнергетичных частиц. Помните, как народ переполошился по поводу запуска Большого андронного коллайдера: средства массовой информации постоянно пугали людей приближением конца света. На самом деле, ставился серьезный научный эксперимент по проверке моделей квантовой космологии и так называемых «теорий великого объединения». Если бы удалось обнаружить так называемые частицы Хиггса, то это стало бы очередным шагом в нашем понимании самых ранних стадий существования нашей Вселенной. Но пока нет экспериментальных данных, конкурирующие модели квантовой космологии продолжают оставаться просто математическими моделями.
Вера и интуиция
— «…Мой Бог больше чем личность; поскольку Бог может играть роль личности…» Все-таки вера Геделя далека от православного исповедания?
— Сохранилось очень мало высказываний Геделя о его вере, они по крупицам собраны. Несмотря на то что первые наброски собственной версии аргумента Гедель сделал еще в 1941 году, до 1970-го, боясь насмешек своих коллег, он не говорил об этом. В феврале 1970-го, почувствовав приближение смерти, он разрешил своей помощнице скопировать версию своего доказательства. После смерти Геделя в 1978 году в его бумагах была обнаружена несколько иная версия онтологического аргумента. Жена Курта Геделя, Аделе, через два дня после смерти мужа сказала, что Гедель, «хотя и не посещал церковь, был религиозен и читал Библию в кровати каждое воскресное утро».
Когда мы говорим о таких ученых, как Гедель, Энштейн или, скажем, Галилей или Ньютон, важно подчеркнуть то, что они не были атеистами. Они видели, что за Вселенной стоит Разум, некая Высшая Сила. Для многих ученых убежденность в существовании Высшего Разума являлась одним из следствий их научной рефлексии, и не всегда эта рефлексия приводила к возникновению глубокой религиозной связи человека с Богом. В отношении Геделя можно сказать, что он ощущал необходимость этой связи, поскольку подчеркивал, что является теистом, мыслит Бога как личность. Но, разумеется, его веру нельзя назвать ортодоксальной. Он был, так сказать, «домашним лютеранином».
— Вы можете дать исторические примеры: каким путем разные ученые приходят к вере в Бога? Вот генетика Фрэнсиса Коллинза, по его признаниям, к вере в Бога привело исследование структуры ДНК…
— Само по себе естественное богопознание недостаточно для познания Бога. Мало, изучая природу, открыть Бога — важно научиться Его познавать посредством того Откровения, которое Бог дал человеку. Приход человека к вере — независимо от того, ученый он или не ученый, — всегда опирается на что-то, что выходит за рамки просто логических или научных аргументов. Фрэнсис Коллинз пишет, что пришел к вере в 27 лет после продолжительного интеллектуального спора с самим собой и под влиянием Клайва Стейплза Льюиса. Два человека находятся в одной и той же исторической ситуации, в одних исходных условиях: один становится верующим, другой — атеистом. Одного изучение ДНК приводит к убеждению в существовании Бога. Другой изучает — и не приходит к этому. Два человека смотрят на картину: одному она кажется красивой, а другой говорит: «Так себе, обычная картинка!» У одного есть вкус, интуиция, а у другого — нет. Профессор Православного Свято-Тихоновского гуманитарного университета Владимир Николаевич Катасонов, доктор философских наук, математик по первому образованию, говорит: «Никакое доказательство в математике невозможно без интуиции: математик сначала видит картинку, а потом уже формулирует доказательство».
Вопрос о приходе человека к вере — это всегда вопрос, который выходит за рамки просто логического рассуждения. Как объяснить, что тебя привело к вере? Человек отвечает: я ходил в храм, размышлял, читал то-то, увидел гармонию мироздания; но самый главный, самый исключительный момент, в который человек вдруг познает, что он столкнулся с присутствием Бога, не может быть выражен. Это всегда тайна.
— Можно обозначить проблемы, которые не в силах разрешить современная наука?
— Все-таки наука — достаточно уверенное, самостоятельное и хорошо идущее предприятие, чтобы так резко высказываться. Она является хорошим и весьма полезным инструментом в руках человека. Со времени Фрэнсиса Бэкона знание действительно стало силой, изменившей мир. Наука развивается в соответствии со своими внутренними закономерностями: ученый стремится постичь законы мироздания, и можно не сомневаться в том, что этот поиск приведет к успеху. Но в то же время необходимо осознавать и границы науки. Не следует смешивать науку и те мировоззренческие вопросы, которые могут быть поставлены в связи с наукой. Ключевые проблемы сегодня связаны не столько с научным методом, сколько с ценностными ориентациями. Наука в течение долгого ХХ века воспринималась людьми как абсолютное благо, которое способствует прогрессу человечества; а мы видим, что ХХ век стал самым жестоким по человеческим жертвам. И тут возникает вопрос о ценностях научного прогресса, вообще познания. Этические ценности не следуют из самой науки. Гениальный ученый может изобрести оружие для уничтожения всего человечества, и здесь возникает вопрос о нравственной ответственности ученого, на который наука не может ответить. Наука не может указать человеку смысл и предназначение его существования. Наука никогда не сможет ответить на вопрос, почему мы здесь? Почему существует Вселенная? Эти вопросы решаются на другом уровне познания, таком, как философия и религия.
— Кроме теорем Геделя, есть ли еще доказательства того, что научный метод имеет свои пределы? Сами ученые это признают?
— Уже в начале XX века философы Бергсон и Гуссерль указали на относительное значение научного знания природы. Сейчас уже стало почти всеобщим убеждением среди философов науки, что научные теории представляют гипотетические модели объяснения явлений. Один из создателей квантовой механики — Эрвин Шредингер говорил о том, что элементарные частицы являются только образами, но мы вполне можем обойтись и без них. По мысли философа и логика Карла Поппера, научные теории подобны сети, посредством которой мы пытаемся поймать мир, они не похожи на фотографии. Научные теории находятся в постоянном развитии и изменении. О границах научного метода говорили создатели квантовой механики, такие как Паули, Бор, Гейзенберг. Паули писал: «…Физика и психика могут рассматриваться как дополнительные аспекты одной и той же реальности» — и акцентировал внимание на несводимости высших уровней бытия к низшим. Различные объяснения охватывают каждый раз лишь один аспект материи, но всеохватная теория никогда не будет достигнута.
Красота и гармония мироздания предполагает возможность его познания научными методами. Вместе с тем христиане всегда понимали и непостижимость тайны, стоящей за этой материальной вселенной. Вселенная не имеет основания в самой себе и указывает на совершенный источник бытия — Бога.
Экология жизни. Наука и открытия: Теореме Гёделя о неполноте, одной из самых известных теорем математической логики, повезло и не повезло одновременно. В этом она похожа на специальную теорию относительности Эйнштейна. С одной стороны, почти все о них что-то слышали. С другой интерпретации теория Эйнштейна «говорит, что всё в мире относительно».
Теореме Гёделя о неполноте , одной из самых известных теорем математической логики, повезло и не повезло одновременно. В этом она похожа на специальную теорию относительности Эйнштейна.
С одной стороны, почти все о них что-то слышали. С другой - в народной интерпретации теория Эйнштейна , как известно, «говорит, что всё в мире относительно ». А теорема Гёделя о неполноте (далее просто ТГН), в примерно столь же вольной фолк-формулировке, «доказывает, что есть вещи, непостижимые для человеческого разума ».
И вот одни пытаются приспособить её в качестве аргумента против мат ериализма , а другие, напротив, доказывают с её помощью, что бога нет. Забавно не только то, что обе стороны не могут оказаться правыми одновременно, но и то, что ни те, ни другие не удосуживаются разобраться, что же, собственно, эта теорема утверждает.
Итак, что же? Ниже я попытаюсь «на пальцах» рассказать об этом. Изложение моё будет, разумеется нестрогим и интуитивным, но я попрошу математиков не судить меня строго. Возможно, что для нематематиков (к которым, вообще-то, отношусь и я), в рассказанном ниже будет что-то новое и полезное.
Математическая логика - наука действительно довольно сложная, а главное - не очень привычная. Она требует аккуратных и строгих манёвров, при которых важно не перепутать реально доказанное с тем, что «и так понятно». Тем не менее, я надеюсь, что для понимания следующего ниже «наброска доказательства ТГН» читателю понадобится только знание школьной математики/информатики, навыки логического мышления и 15-20 минут времени.
Несколько упрощая, ТГН утверждает, что в достаточно сложных языках существуют недоказуемые высказывания. Но в этой фразе почти каждое слово нуждается в пояснении.
Начнём с того, что попытаемся разобраться, что такое доказательство. Возьмём какую-нибудь школьную задачку по арифметике. Например, пусть требуется доказать верность следующей незамысловатой формулы: «∀x(x−1)(x−2)−2=x(x−3)» (напомню, что символ ∀ читается «для любого» и называется «квантор всеобщности»). Доказать её можно, тождественно преобразуя, скажем, так:
∀x(x−1)(x−2)−2=x(x−3)
∀xx2−3x+2−2=x2−3x
∀xx2−3x–x2+3x=0
∀x0=0
ИСТИНА
Переход от одной формулы к другой происходит по некоторым известным правилам. Переход от 4-й формулы к 5-й произошёл, скажем, потому, что всякое число равно самому себе - такова аксиома арифметики. А вся процедура доказывания, таким образом, переводит формулу в булево значение ИСТИНА. Результатом могла быть и ЛОЖЬ - если бы мы опровергали какую-то формулу. В таком случае мы бы доказали её отрицание. Можно себе представить программу (и такие программы действительно написаны), которые бы доказывали подобные (и более сложные) высказывания без участия человека.
Изложим то же самое чуть более формально. Пусть у нас есть множество, состоящее из строк символов какого-то алфавита, и существуют правила, по которым из этих строк можно выделить подмножество S так называемых высказываний - то есть грамматически осмысленных фраз, каждая из которых истинна или ложна . Можно сказать, что существует функция P, сопоставляющая высказываниям из S одно из двух значений: ИСТИНА или ЛОЖЬ (то есть отображающая их в булево множество B из двух элементов).
Назовём такую пару - множество высказываний S и функция P из >S в B - «языком высказываний» . Заметим, что в повседневном смысле понятие языка несколько шире. Например, фраза русского языка «А ну иди сюда! » не истинна и не ложна, то есть высказыванием, с точки зрения математической логики, не является.
Для дальнейшего нам понадобится понятие алгоритма. Приводить здесь формальное его определение я не буду - это завело бы нас довольно далеко в сторону. Ограничусь неформальным: «алгоритм» - эта последовательность однозначных инструкций («программа»), которая за конечное число шагов переводит исходные данные в результат.
Выделенное курсивом принципиально важно - если на каких-то начальных данных программа зацикливается, то алгоритма она не описывает. Для простоты и в применении к нашему случаю читатель может считать, что алгоритм - это программа, написанная на любом известном ему языке программирования, которая для любых входных данных из заданного класса гарантированно завершает свою работу с выдачей булевого результата.
Спросим себя: для всякой ли функции P существует «доказывающий алгоритм» (или, короче, «дедуктика »), эквивалентный этой функции, то есть переводящий каждое высказывание именно в то булево значение, что и она? Лаконичнее тот же вопрос можно сформулировать так: всякая ли функция над множеством высказываний вычислима?
Как вы уже догадываетесь, из справедливости ТГН следует, что нет, не всякая - существуют невычислимые функции такого типа. Иными словами, не всякое верное высказывание можно доказать.
Очень может быть, что это утверждение вызовет у вас внутренний протест. Связано это с несколькими обстоятельствами. Во-первых, когда нас учат школьной математике, то иногда возникает ложное впечатление почти полной тождественности фраз «теорема X верна» и «можно доказать или проверить теорему X».
Но, если вдуматься, это совершенно не очевидно. Некоторые теоремы доказываются довольно просто (например, перебором небольшого числа вариантов), а некоторые - очень сложно. Вспомним, например, знаменитую Великую теорему Ферма
:
Не существует таких натуральных x,y,z и n>2, что xn+yn=zn,
доказательство которой нашли только через три с половиной века после первой формулировки (и оно далеко не элементарно). Следует различать истинность высказывания и его доказуемость. Ниоткуда не следует, что не существует истинных, но недоказуемых (и не проверяемых в полной мере) высказываний.
Второй интуитивный довод против ТГН более тонок. Допустим, у нас есть какое-то недоказуемое (в рамках данной дедуктики) высказывание. Что мешает нам принять его в качестве новой аксиомы? Тем самым мы чуть усложним нашу систему доказательств, но это не страшно.
Этот довод был бы совершенно верен, если бы недоказуемых высказываний было конечное число. На практике же может произойти следующее - после постулирования новой аксиомы вы наткнётесь на новое недоказуемое высказывание . Примете его в качестве ещё аксиомы - наткнётесь на третье. И так до бесконечности.
Говорят, что дедуктика останется неполной . Мы можем также принять силовые меры, чтобы доказывающий алгоритм заканчивался через конечное число шагов с каким-то результатом для любого высказывания языка. Но при этом он начнёт врать - приводить к истине для неверных высказываний, или ко лжи - для верных.
В таких случаях говорят, что дедуктика противоречива. Таким образом, ещё одна формулировка ТГН звучит так: «Существуют языки высказываний, для которых невозможна полная непротиворечивая дедуктика » - отсюда и название теоремы.
Иногда называют «теоремой Гёделя» утверждение о том, что любая теория содержит проблемы, которые не могут быть решены в рамках самой теории и требуют её обобщения. В каком-то смысле это верно, хотя такая формулировка скорее затуманивает вопрос, чем проясняет его.
Замечу также, что если бы речь шла о привычных функциях, отображающих множество вещественных чисел в него же, то «невычислимость» функции никого бы не удивила (только не надо путать «вычислимые функции» и «вычислимые числа» - это разные вещи).
Курт Гедель
Любому школьнику известно, что, скажем, в случае функции sinx вам должно сильно повезти с аргументом, чтобы процесс вычисления точного десятичного представления значения этой функции окончился за конечное число шагов.
А скорее всего вы будете вычислять её с помощью бесконечного ряда, и это вычисление никогда не приведёт к точному результату, хотя может подойти к нему как угодно близко - просто потому, что значение синуса большинства аргументов иррационально . ТГН просто говорит нам о том, что даже среди функций, аргументами которой являются строки, а значениями - ноль или единица, невычислимые функции, хотя и совсем по другому устроенные, тоже бывают .
Для дальнейшего опишем «язык формальной арифметики». Рассмотрим класс строк текста конечной длины, состоящих из арабских цифр, переменных (букв латинского алфавита), принимающих натуральные значения, пробелов, знаков арифметических действий, равенства и неравенства, кванторов ∃ («существует») и ∀ («для любого») и, быть может, каких-то ещё символов (точное их количество и состав для нас неважны).
Понятно, что не все такие строки осмысленны (например, «12=+∀x>» - это бессмыслица). Подмножество осмысленных выражений из этого класса (то есть строк, которые истинны или ложны с точки зрения обычной арифметики) и будет нашим множеством высказываний.
Примеры высказываний формальной арифметики:
1=1
2×2=5
∃xx>3
∀y∀zy×z>y+ z
и т.д. Теперь назовём «формулой со свободным параметром» (ФСП) строку, которая становится высказыванием, если в качестве этого параметра подставить в неё натуральное число. Примеры ФСП (с параметром x):
x=0
2×2=x
∃yx+y>x
и т.д. Иными словами, ФСП эквивалентны функциям натурального аргумента с булевыми значением.
Обозначим множество всех ФСП буквой F. Понятно, что его можно упорядочить (например, сначала выпишем упорядоченные по алфавиту однобуквенные формулы, за ними - двухбуквенные и т.д.; по какому именно алфавиту будет происходить упорядочивание, нам непринципиально). Таким образом, любой ФСП соответствует её номер k в упорядоченном списке, и мы будем обозначать её Fk.
Перейдём теперь к наброску доказательства ТГН в такой формулировке:
Для языка высказываний формальной арифметики не существует полной непротиворечивой дедуктики.
Доказывать будем от противного.
Итак, допустим, что такая дедуктика существует. Опишем следующий вспомогательный алгоритм A, ставящий в соответствие натуральному числу k булево значение следующим образом :
1. Находим k-ю формулу в списке F.
2. Подставляем в неё число k в качестве аргумента.
3. Применяем к полученному высказыванию наш доказывающий алгоритм (по нашему предположению, он существует), который переводит его в ИСТИНУ или ЛОЖЬ.
4. Применяем логическое отрицание к полученному результату.
Проще говоря, алгоритм приводит к значению ИСТИНА тогда и только тогда, когда результат подстановки в ФСП её собственного номера в нашем списке даёт ложное высказывание.
Тут мы подходим к единственному месту, в котором я попрошу читателя поверить мне на слово.
Очевидно, что, при сделанном выше предположении, любой ФСП из F можно сопоставить алгоритм, содержащий на входе натуральное число, а на выходе – булево значение.
Менее очевидно обратное утверждение:
Лемма: Любому алгоритму, переводящему натуральное число в булево значение, соответствует какая-то ФСП из множества F.
Доказательство этой леммы потребовало бы, как минимум, формального, а не интуитивного, определения понятия алгоритма. Однако, если немного подумать, то она довольно правдоподобна.
В самом деле, алгоритмы записываются на алгоритмических языках, среди которых есть такие экзотические, как, например, Brainfuck, состоящий из восьми односимвольных слов, на котором, тем не менее, можно реализовать любой алгоритм. Странно было бы, если бы описанный нами более богатый язык формул формальной арифметики оказался бы беднее - хотя, без сомнения, для обычного программирования он не очень подходит.
Пройдя это скользкое место, мы быстро добираемся до конца.
Итак, выше мы описали алгоритм A. Согласно лемме, в которую я попросил вас поверить, существует эквивалентная ему ФСП. Она имеет какой-то номер в списке F - скажем, n. Спросим себя, чему равно Fn(n)? Пусть это ИСТИНА. Тогда, по построению алгоритма A (а значит, и эквивалентной ему функции Fn), это означает, что результат подстановки числа n в функцию Fn - ЛОЖЬ.
Аналогично проверяется и обратное: из Fn(n)=ЛОЖЬ следует Fn(n)=ИСТИНА. Мы пришли к противоречию, а значит, исходное предположение неверно. Таким образом, для формальной арифметики не существует полной непротиворечивой дедуктики. Что и требовалось доказать.
Здесь уместно вспомнить Эпименида, который, как известно, заявил, что все критяне - лжецы, сам являясь критянином. В более лаконичной формулировке его высказывание (известное как «парадокс лжеца») можно сформулировать так: «Я лгу ». Именно такое высказывание, само превозглашающее свою ложность, мы и использовали для доказательства.
В заключение я хочу заметить, что ничего особенного удивительного ТГН не утверждает. В конце концов, все давно привыкли, что не все числа представимы в виде отношения двух целых (помните, у этого утверждения есть очень изящное доказательство, которому больше двух тысяч лет?). И корнями полиномов с рациональными коэффициентами являются т оже не все числа . А теперь вот выяснилось, что не все функции натурального аргумента вычислимы.
Приведённый набросок доказательства относился к формальной арифметике, но нетрудно понять, что ТГН применима и к многим другим языкам высказываний. Разумеется, не всякие языки таковы. Например, определим язык следующим образом:
«Любая фраза китайского языка является верным высказыванием, если она содержится в цитатнике товарища Мао Дзе Дуна, и неверна, если не содержится».
Тогда соответствующий полный и непротиворечивый доказывающий алгоритм (его можно назвать «догматической дедуктикой») выглядит примерно так:
«Листай цитатник товарища Мао Дзе Дуна, пока не найдёшь искомое высказывание. Если оно найдено, то оно верно, а если цитатник закончился, а высказывание не найдено, то оно неверно».
Здесь нас спасает то, что любой цитатник, очевидно, конечен, поэтому процесс «доказывания» неминуемо закончится. Таким образом, к языку догматических высказываний ТГН неприменима. Но мы ведь говорили о сложных языках, правда? опубликовано
на тему: «ТЕОРЕМА ГЁДЕЛЯ»
Курт Гёдель
Курт Гёдель – крупнейший специалист по математической логике – родился 28 апреля 1906 г. В Брюнне (ныне г. Брно, Чехия). Окончил Венский университет, где защитил докторскую диссертацию, был доцентом в 1933–1938 гг. После аншлюса эмигрировал в США. С 1940 по 1963 г. Гёдель работал в Принстонском институте высших исследований. Гёдель – почетный доктор Йельского и Гарвардского университетов, член Национальной академии наук США и Американского философского общества.
В 1951 г. Курт Гёдель был удостоен высшей научной награды США – Эйнштейновской премии. В статье, посвященной этому событию, другой крупнейший математик нашего времени Джон фон Нейман писал : «Вклад Курта Гёделя в современную логику поистине монументален. Это – больше, чем просто монумент. Это веха, разделяющая две эпохи… Без всякого преувеличения можно сказать, что работы Гёделя коренным образом изменили сам предмет логики как науки».
Действительно, даже сухой перечень достижений Гёделя в математической логике показывает, что их автор по существу заложил основы целых разделов этой науки: теории моделей (1930 г.; так называемая теорема о полноте узкого исчисления предикатов, показывающая, грубо говоря, достаточность средств «формальной логики» для доказательства всех выражаемых на ее языке истинных предложений), конструктивной логики (1932–1933 гг.; результаты о возможности сведения некоторых классов предложений классической логики к их интуиционистским аналогам, положившие начало систематическому употреблению «погружающих операций», позволяющих осуществлять такое сведение различных логических систем друг другу), формальной арифметики (1932–1933 гг.; результаты о возможности сведения классической арифметики в интуиционистскую, показывающие в некотором смысле непротиворечивость первой относительно второй), теории алгоритмов и рекурсивных функций (1934 г.; определение понятия общерекурсивной функции, сыгравшего решающую роль в установлении алгоритмической неразрешимости ряда важнейших проблем математики, с одной стороны. И в реализации логико-математических задач на электронно-вычислительных машинах – с другой), аксиоматической теории множеств (1938 г.; доказательство относительной непротиворечивости аксиомы выбора и континуум-гипотезы Кантора от аксиом теории множеств, положившее начало серии важнейших результатов об относительной непротиворечивости и независимости теоретико-множественных принципов).
Теорема Гёделя о неполноте
Введение
В 1931 г. В одном из немецких научных журналов появилась сравнительно небольшая статья с довольно устрашающим названием «О формально неразрешимых предложениях Principia Mathematica и родственных систем». Автором ее был двадцатипятилетний математик из Венского университета Курт Гедель, впоследствии работавший в Принстонском институте высших исследований. Работа эта сыграла решающую роль в истории логики и математики. В решении Гарвардского университета о присуждении Гёделю почетной докторской степени (1952) она была охарактеризована как одно из величайших достижений современной логики.
Однако в момент опубликования ни название гёделевской работы. Ни содержание ее ничего не говорили большинству математиков. Упомянутые в ее названии Principia Mathematica – это монументальных трехтомный трактат Альфреда Норта Уайтхеда и Бертрана Рассела, посвященный математической логике и основаниям математики; знакомство с трактатом отнюдь не являлось необходимым условием для успешной работы в большей части разделов математики. Интерес к разбираемым в работе Гёделя вопросам всегда был уделом весьма немногочисленной группы учёных. В то же время рассуждения, приведенные Гёделем в его доказательствах, были для своего времени столь необычными. Что для полного их понимания требовалось исключительное владение предметом и знакомство с литературой, посвященной этим весьма специфическим проблемам.
Первая теорема о неполноте
Первая теорема Гёделя о неполноте , по всей видимости, является наиболее знаменательным результатом в математической логике. Она звучит следующим образом:
Для произвольной непротиворечивой формальной и вычислимой теории, в которой можно доказать базовые арифметические высказывания, может быть построено истинноеарифметическое высказывание, истинность которого не может быть доказана в рамках теории . Другими словами, любая вполне полезная теория, достаточная для представления арифметики, не может быть одновременно непротиворечивой и полной.
Здесь слово «теория» обозначает «бесконечное множество» высказываний, некоторые из которых полагаются истинными без доказательств (такие высказывания называются аксиомами), а другие (теоремы) могут быть выведены из аксиом, а потому полагаются (доказываются) истинными. Словосочетание «доказуемый в теории» обозначает «выводимый из аксиом и примитивов теории (константных символов алфавита) при помощи стандартной логики (первого порядка)». Теория является непротиворечивой (согласованной), если в ней невозможно доказатьпротиворечивое высказывание. Словосочетание «может быть построено» обозначает, что существует некоторая механическая процедура (алгоритм), которая может построить высказывание на основе аксиом, примитивов и логики первого порядка. «Элементарная арифметика» заключается в наличии операций сложения и умножения над натуральными числами. Результирующее истинное, но недоказуемое высказывание часто обозначается для заданной теории как «последовательность Гёделя», однако существует бесконечно количество других высказываний в теории, которые имеют такое же свойство: недоказуемая в рамках теории истинность.
Предположение о том, что теория вычислима, обозначает, что в принципе возможно реализовать компьютерный алгоритм (компьютерную программу), которая (если ей разрешено вычислять произвольно долгое врея, вплоть до бесконечности) вычислит список всех теорем теории. Фактически, достаточно вычислить только список аксиом, и все теоремы могут быть эффективно получены из такого списка.
Первая теорема о неполноте была озаглавлена как «Теорема VI» в статье Гёделя от 1931 года On Formally Undecidable Propositions in Principia Mathematica and Related Systems I . В оригинальной записи Гёделя она звучала как:
«Общий вывод о существовании неразрешимых пропозиций заключается в следующем:
Теорема VI .
Для каждого ω-согласованного рекурсивного класса k ФОРМУЛ существуют рекурсивные ЗНАКИ r такие, что ни (v Genr ), ни ¬(v Genr )не принадлежат Flg (k )(где v есть СВОБОДНАЯ ПЕРЕМЕННАЯ r ) ».
Обозначение Flg происходит от нем. Folgerungsmenge – множество последовательностей, Gen происходит от нем. Generalisation – обобщение.
Грубо говоря, высказывание Гёделя G утверждает: «истинность G не может быть доказана». Если бы G можно было доказать в рамках теории, то в таком случае теория содержала бы теорему, которая противоречит сама себе, а потому теория была бы противоречива. Но если G недоказуемо, то оно истинно, а потому теория неполна (высказывание G невыводимо в ней).
Это пояснение на обычном естественном языке, а потому не совсем математически строго. Для предоставления строгого доказательства, Гёдель пронумеровал высказывания при помощи натуральных чисел. В этом случае теория, описывающая числа, также принадлежит множеству высказываний. Вопросы о доказуемости высказываний представимы в данном случае в виде вопросов о свойствах натуральных чисел, которые должны быть вычислимы, если теория полна. В этих терминах высказывание Гёделя гласит, что не существует числа с некоторым определённым свойством. Число с этим свойством будет являться доказательством противоречивости теории. Если такое число существует, теория противоречива вопреки первоначальному предположению. Так что предполагая, что теория непротиворечива (как предполагается в посылке теоремы), получается, что такого числа не существует, и высказывание Гёделя истинно, но в рамках теории этого доказать невозможно (следовательно, теория неполна). Важное концептуальное замечание состоит в том, что необходимо предположить, что теория непротиворечива, для того чтобы объявить высказывание Гёделя истинным.
Вторая теорема Гёделя о неполноте
Вторая теорема Гёделя о неполноте звучит следующим образом:
Для любой формально рекурсивно перечислимой (то есть эффективно генерируемой) теории T, включая базовые арифметические истинностные высказывания и определённые высказывания о формальной доказуемости, данная теория T включает в себя утверждение о своей непротиворечивости тогда и только тогда, когда теория T противоречива.
Иными словами, непротиворечивость достаточно богатой теории не может быть доказана средствами этой теории. Однако вполне может оказаться, что непротиворечивость одной конкретной теории может быть установлена средствами другой, более мощной формальной теории. Но тогда встаёт вопрос о непротиворечивости этой второй теории, и т.д.
Использовать эту теорему для доказательства того, что разумная деятельность не сводится к вычислениям, пытались многие. Например, еще в 1961 году известный логик Джон Лукас (John Lucas) выступал с подобной программой. Его рассуждения оказались довольно уязвимыми – однако он и задачу ставил более широко. Роджер Пенроуз использует несколько другой подход, который излагается в книге полностью, «с нуля».
Дискуссии
Следствия теорем затрагивают философию математики, особенно такие формализмы, которые используют формальную логику для определения своих принципов. Можно перефразировать первую теорему о неполноте следующим образом: «невозможно найти всеохватывающую систему аксиом, которая была бы способна доказать все математические истины, и ни одной лжи ». С другой стороны, с точки зрения строгой формальности, эта переформулировка не имеет особого смысла, поскольку она предполагает понятия «истина» и «ложь» определёнными в абсолютном смысле, нежели в относительном для каждой конкретной системы.
Идея доказательства заключается в том, чтобы построить такое выражение, которое свидетельствовало бы о своей
собственной недоказуемости. Такое построение может быть выполнено в три этапа:
Первый этап - установление соответствия между формальной арифметикой и множеством целых чисел (гедели-зации);
Второй этап - построение некоторого специального свойства о котором неизвестно, является ли оно теоремой формальной арифметики или нет;
Третий этап - подстановка в вместо х определенного целого числа, связанного с самим т. е. замещение этими числами всех
Первый этап. Геделизация формальной арифметики
Формальная арифметика может быть арифметизирована (т. е. геделизирована) следующим образом: каждой ее теореме ставится в соответствие некоторое число. Однако так как всякое число также является теоремой, то всякая теорема может рассматриваться, с одной стороны, в качестве теоремы формальной арифметики, а с другой - как теорема над множеством теорем формальной арифметики, т. е. в качестве метатеоремы, соответствующей доказательству некой теоремы.
Таким образом, можно сделать вывод, что система формальной арифметики содержит также и свою собственную метасистему.
Теперь более конкретно и подробно изложим полученные результаты.
Во-первых, мы можем связать с каждым символом и формальной арифметики специальное кодовое обозначение, называемое в данном случае геделевым номером
Во-вторых, каждой последовательности символов мы ставим в соответствие тот же геделев номер с помощью некоторой функции композиции Пусть где представляют собой последовательности символов, которые образуют
В-третьих (и это существенно), каждому доказательству последовательности аксиом и правил подстановки (или правил замещения) ставится в соответствие число где обозначает последовательность теорем, используемых при доказательстве
Таким образом, всякому доказательству в формальной арифметике соответствует некоторое число - его геделев номер Всякое рассуждение формальной ариметики преобразуется в вычисления на множестве натуральных чисел.
Итак, вместо того чтобы производить манипуляции с символами, теоремами, доказательствами, можно воспользоваться
вычислениями на множестве целых чисел. Всякое выражение, подобное, например, следующему: доказуемо в формальной арифметике", теперь соответствует определенному числу, которое будем обозначать как
Сформулируем следующее положение.
Формальная метаарифметика содержится в множестве натуральных чисел, а оно само содержится в интерпретации формальной арифметики.
Эта ситуация с формальной арифметикой напоминает ситуацию с естественным языком: ведь нам ничто не мешает использовать его и для того, чтобы формулировать на нем основные его понятия и правила.
Надлежащий выбор функции позволяет осуществить однозначный переход от А к т. е. присвоить два разных числа-номера двум различным доказательствам. Например, можно так выбрать геделевы номера, чтобы каждому символу алфавита формальной арифметики соответствовало свое простое число, как показано, например, в табл. 3.2.
Таблица 3.2
Каждая формула (состоящая из символов изменяющимся от 1 до в свою очередь кодируется последовательностью, состоящей из первых простых чисел, т. е. числом
где простое число.
В свою очередь доказательство, т. е. последовательность из формул будет закодирована аналогичным образом числом
И наоборот, благодаря такому способу построения номеров становится возможным, исходя из некоторого числа, с помощью разложения его на простые множители (в силу единственности разложения натуральных чисел в произведения степеней простых чисел) возвратиться за два шага к показателям степени т. е. к примитивным символам формальной арифметики. Конечно, это имеет в основном лишь теоретическое значение, так как номера быстро становятся слишком большими
для того, чтобы ими можно было манипулировать. Однако следует отметить, что существенным является принципиальная возможность этой операции.
Пример. Пусть задано число Т, соответствующее некоторому доказательству и представляющее собой произведение простых чисел:
Это разложение означает, что доказательство теоремы содержит два этапа: один соответствует числу 1981027125 253, а другой - числу 1981027125 211. Разлагая снова на простые множители каждое из этих чисел, получим
Из таблицы кодирования алфавита формальной арифметики (табл. 3.2) находим, что нашим геделевым номерам для Этих двух чисел
будет соответствовать следующее доказательство:
Из формулы следует формула
Таким образом, в метаарифметике получено значение исходного числа из формальной арифметики.
Второй этап. Лемма Геделя
Всякому числу Т, связанному с доказательством, соответствует теорема доказуемая в формальной арифметике. “Геделизированную” формальную арифметику называют арифметизированной формальной арифметикой. Поскольку каждая аксиома и каждое правило арифметизированной формальной арифметики соответствуют какой-нибудь арифметической операции, то с помощью систенатизированной проверки можно определить, соответствует ли данное число Т доказательству какой-то теоремы Числа Т и образуют в этом случае пару сопряженных чисел. Выражение и являются сопряженными” Представимо внутри самой арифметизированной формальной арифметики. Это означает, что существует геделев номер который выражает в цифровой форме это утверждение.
Мы подошли к критическому пункту доказательства Геделя. Пусть А является выражением арифметизированной формальной арифметики, которое содержит какую-то свободную переменную. Вместо нее можно сделать подстановку какого-нибудь терма. В частности, можно заменить выражение А самим выражением А. В этом случае номер-выражение А выполняет одновременно две различные роли (см. выше построения
Кантора и Ришара): оно одновременно является истинным выражением для подстановки и результирующим термом. Эту специальную подстановку будем обозначать как Так формула означает, что число есть геделев номер, получаемый при выполнении подстановки - к выражению А:
Затем Гедель строит выражение (о котором неизвестно, представляет ли оно собой теорему или не-теорему), в которое вводит эту подстановку. Выражение имеет следующий вид:
Третий этап. Завершающая подстановка
В арифметизированной формальной арифметике это выражение представлено в цифровой форме. Пусть Е - его геделев номер. Так как выражение содержит свободную переменную то мы имеем право выполнить подстановку - над замещая числом Е и обозначая -замещение Е:
Это второе выражение обозначим через а его геделев номер через Е. Дадим интерпретации выражения е.
Первая интерпретация. Не существует такой пары для которой одновременно выполнялось бы следующее: с одной стороны, Т - номер арифметизированного доказательства теоремы арифметизированной ею самой, а с другой - было бы есть замещение Но так как есть такое же преобразование, как и другие, то оно представимо в термах и в их кодовых обозначениях - геделевых номерах и, следовательно, такой номер существует. Тогда, возможно, номер Т не существует.
Вторая интерпретация. Не существует арифметизированного доказательства Т теоремы которое было бы -замещением Е. Итак, если не существует доказательства, то потому, что само по себе не является теоремой. Отсюда вытекает третья интерпретация.
Третья интерпретация. Выражение, для которого геделев номер есть -замещение Е, не является теоремой арифметизированной формальной арифметики. Но в этом и заключается противоречие, так как по построению именно само является -замещением Е и номер есть не что иное по построению, как сам номер Е. Отсюда вытекает последняя интерпретация е.
доказательство которой нашли только через три с половиной века после первой формулировки (и оно далеко не элементарно). Следует различать истинность высказывания и его доказуемость. Ниоткуда не следует, что не существует истинных, но недоказуемых (и не проверяемых в полной мере) высказываний.
Второй интуитивный довод против ТГН более тонок. Допустим, у нас есть какое-то недоказуемое (в рамках данной дедуктики) высказывание. Что мешает нам принять его в качестве новой аксиомы? Тем самым мы чуть усложним нашу систему доказательств, но это не страшно. Этот довод был бы совершенно верен, если бы недоказуемых высказываний было конечное число. На практике же может произойти следующее - после постулирования новой аксиомы вы наткнётесь на новое недоказуемое высказывание. Примете его в качестве ещё аксиомы - наткнётесь на третье. И так до бесконечности. Говорят, что дедуктика останется неполной . Мы можем также принять силовые меры, чтобы доказывающий алгоритм заканчивался через конечное число шагов с каким-то результатом для любого высказывания языка. Но при этом он начнёт врать - приводить к истине для неверных высказываний, или ко лжи - для верных. В таких случаях говорят, что дедуктика противоречива . Таким образом, ещё одна формулировка ТГН звучит так: «Существуют языки высказываний, для которых невозможна полная непротиворечивая дедуктика» - отсюда и название теоремы.
Иногда называют «теоремой Гёделя» утверждение о том, что любая теория содержит проблемы, которые не могут быть решены в рамках самой теории и требуют её обобщения. В каком-то смысле это верно, хотя такая формулировка скорее затуманивает вопрос, чем проясняет его.
Замечу также, что если бы речь шла о привычных функциях, отображающих множество вещественных чисел в него же, то «невычислимость» функции никого бы не удивила (только не надо путать «вычислимые функции» и «вычислимые числа» - это разные вещи). Любому школьнику известно, что, скажем, в случае функции вам должно сильно повезти с аргументом, чтобы процесс вычисления точного десятичного представления значения этой функции окончился за конечное число шагов. А скорее всего вы будете вычислять её с помощью бесконечного ряда, и это вычисление никогда не приведёт к точному результату, хотя может подойти к нему как угодно близко - просто потому, что значение синуса большинства аргументов иррационально. ТГН просто говорит нам о том, что даже среди функций, аргументами которой являются строки, а значениями - ноль или единица, невычислимые функции, хотя и совсем по другому устроенные, тоже бывают.
Для дальнейшего опишем «язык формальной арифметики». Рассмотрим класс строк текста конечной длины, состоящих из арабских цифр, переменных (букв латинского алфавита), принимающих натуральные значения, пробелов, знаков арифметических действий, равенства и неравенства, кванторов («существует») и («для любого») и, быть может, каких-то ещё символов (точное их количество и состав для нас неважны). Понятно, что не все такие строки осмысленны (например, « » - это бессмыслица). Подмножество осмысленных выражений из этого класса (то есть строк, которые истинны или ложны с точки зрения обычной арифметики) и будет нашим множеством высказываний.
Примеры высказываний формальной арифметики:
и т.д. Теперь назовём «формулой со свободным параметром» (ФСП) строку, которая становится высказыванием, если в качестве этого параметра подставить в неё натуральное число. Примеры ФСП (с параметром ):
и т.д. Иными словами, ФСП эквивалентны функциям натурального аргумента с булевыми значением.
Обозначим множество всех ФСП буквой . Понятно, что его можно упорядочить (например, сначала выпишем упорядоченные по алфавиту однобуквенные формулы, за ними - двухбуквенные и т.д.; по какому именно алфавиту будет происходить упорядочивание, нам непринципиально). Таким образом, любой ФСП соответствует её номер в упорядоченном списке, и мы будем обозначать её .
Перейдём теперь к наброску доказательства ТГН в такой формулировке:
- Для языка высказываний формальной арифметики не существует полной непротиворечивой дедуктики.
Доказывать будем от противного.
Итак, допустим, что такая дедуктика существует. Опишем следующий вспомогательный алгоритм , ставящий в соответствие натуральному числу булево значение следующим образом:
Проще говоря, алгоритм приводит к значению ИСТИНА тогда и только тогда, когда результат подстановки в ФСП её собственного номера в нашем списке даёт ложное высказывание.
Тут мы подходим к единственному месту, в котором я попрошу читателя поверить мне на слово.
Очевидно, что, при сделанном выше предположении, любой ФСП из можно сопоставить алгоритм, содержащий на входе натуральное число, а на выходе – булево значение. Менее очевидно обратное утверждение:
Доказательство этой леммы потребовало бы, как минимум, формального, а не интуитивного, определения понятия алгоритма. Однако, если немного подумать, то она довольно правдоподобна. В самом деле, алгоритмы записываются на алгоритмических языках, среди которых есть такие экзотические, как, например, Brainfuck , состоящий из восьми односимвольных слов, на котором, тем не менее, можно реализовать любой алгоритм. Странно было бы, если бы описанный нами более богатый язык формул формальной арифметики оказался бы беднее - хотя, без сомнения, для обычного программирования он не очень подходит.
Пройдя это скользкое место, мы быстро добираемся до конца.
Итак, выше мы описали алгоритм . Согласно лемме, в которую я попросил вас поверить, существует эквивалентная ему ФСП. Она имеет какой-то номер в списке - скажем, . Спросим себя, чему равно ? Пусть это ИСТИНА. Тогда, по построению алгоритма (а значит, и эквивалентной ему функции ), это означает, что результат подстановки числа в функцию - ЛОЖЬ. Аналогично проверяется и обратное: из ЛОЖЬ следует ИСТИНА. Мы пришли к противоречию, а значит, исходное предположение неверно. Таким образом, для формальной арифметики не существует полной непротиворечивой дедуктики. Что и требовалось доказать.
Здесь уместно вспомнить Эпименида (см. портрет в заголовке), который, как известно, заявил, что все критяне - лжецы, сам являясь критянином. В более лаконичной формулировке его высказывание (известное как «парадокс лжеца») можно сформулировать так: «Я лгу». Именно такое высказывание, само превозглашающее свою ложность, мы и использовали для доказательства.
В заключение я хочу заметить, что ничего особенного удивительного ТГН не утверждает. В конце концов, все давно привыкли, что не все числа представимы в виде отношения двух целых (помните, у этого утверждения есть очень изящное доказательство , которому больше двух тысяч лет?). И корнями полиномов с рациональными коэффициентами являются тоже не все числа . А теперь вот выяснилось, что не все функции натурального аргумента вычислимы.
Приведённый набросок доказательства относился к формальной арифметике, но нетрудно понять, что ТГН применима и к многим другим языкам высказываний. Разумеется, не всякие языки таковы. Например, определим язык следующим образом:
- «Любая фраза китайского языка является верным высказыванием, если она содержится в цитатнике товарища Мао Дзе Дуна, и неверна, если не содержится».
Тогда соответствующий полный и непротиворечивый доказывающий алгоритм (его можно назвать «догматической дедуктикой») выглядит примерно так:
- «Листай цитатник товарища Мао Дзе Дуна, пока не найдёшь искомое высказывание. Если оно найдено, то оно верно, а если цитатник закончился, а высказывание не найдено, то оно неверно».
Здесь нас спасает то, что любой цитатник, очевидно, конечен, поэтому процесс «доказывания» неминуемо закончится. Таким образом, к языку догматических высказываний ТГН неприменима. Но мы ведь говорили о сложных языках, правда?