Теорема гаккеля как формулируется

Теорема Гёделя о неполноте за 20 минут

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Как работает доказательство Гёделя

Его теоремы о неполноте разгромили поиск математической теории всего. Почти сто лет спустя мы всё ещё пытаемся осмыслить последствия этого.

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

Математики той эпохи искали неколебимые основы математики: набор базовых фактов, аксиом, которые были бы непротиворечивыми и полными, играя роль строительных блоков всех математических истин.

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

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

За 89 лет, прошедших с открытия Гёделя, математики уже натыкались на подобные вопросы без ответов, существование которых предсказывали его теоремы. К примеру, сам Гёдель помог установить, что континуум-гипотеза, касающаяся мощностей бесконечностей, неразрешима – как и проблема остановки, в которой требуется определить, завершится ли когда-нибудь выполнение компьютерной программы с определёнными входными данными, или она будет работать вечно. Неразрешимые вопросы возникали даже и в физике, что говорит о том, что гёделева неполнота влияет не только на математику, но и в каком-то (не совсем понятном) смысле, на реальность.

Далее идёт краткая, упрощённая и неформальная сводка того, как Гёдель доказал свои теоремы.

Нумерация Гёделя

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

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

Немного исправленная версия нумерации Гёделя, представленная в книге 1958 года «Доказательство Гёделя» за авторством Эрнеста Нагеля и Джеймса Ньюмена, начинается с 12 элементарных символов, служащих словарём для выражения набора базовых аксиом. К примеру, утверждение о существовании чего-либо можно выразить символом ∃, а сложение – символом +. Символ s, обозначающий «следующий элемент», даёт возможность обозначать числа: к примеру, ss0 обозначает двойку.

Затем этим двенадцати символам назначаются номера Гёделя с 1 по 12.

Затем буквы, обозначающие переменные, начиная с x, y и z, сопоставляются с простыми числами, большими 12 (13, 17, 19. ).

Затем каждая из комбинаций этих символов и переменных – то есть, любая арифметическая формула или последовательность формул, которые только можно составить – получает свой номер Гёделя.

Арифметизация математики

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

Рассмотрим сначала формулу

(0 = 0), означающую «ноль не равен нулю». Она явно ложная. Тем не менее, у неё есть номер Гёделя: 2 в степени 1 (номер Гёделя для символа

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

Рассмотрим утверждение «Первый символ формулы

(0 = 0) это тильда». Это истинное метаматематическое утверждение, касающееся

(0 = 0), превращается в утверждение о номере Гёделя конкретной формулы – а именно, что его первая степень равняется 1, то есть, номеру Гёделя для тильды. Иначе говоря, наше утверждение говорит о том, что в 2 1 × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 есть только один множитель «2». Если бы

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

(∃x)(x × ss0 = sss … sss0) ⋅

(∃x)(x × ssss0 = sss … sss0)

Где sss … sss0 обозначает 2 1 × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 копий символа следующего элемента s. Символ ⋅ означает «и», и представляет собой более краткую запись для фундаментального словаря: p ⋅ q означает

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

Преобразовать в символы можно и метаматематические утверждения. „Существует некая последовательность формул с номером Гёделя х, доказывающая формулу с номером Гёделя k“ – или, короче говоря, „формула с номером Гёделя k доказуема“. Именно возможность „арифметизировать“ подобные заявления и заложила основы переворота.

G само по себе

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

Чтобы понять, как работает эта подстановка, рассмотрим формулу (∃x)(x = sy). Она означает „существует переменная x, являющаяся следующим элементом для y“, или, проще говоря, „у »y» есть следующий элемент“. Как и у всех формул, у неё есть свой номер Гёделя – некое большое целое число, назовём его m.

Теперь введём число m в формулу вместо символа y. Получится новая формула (∃x)(x = sm), означающая „у m есть следующий элемент“. Как назвать номер Гёделя для этой формулы? Нам нужно передать три особенности: мы начали с формулы, имеющей номер Гёделя m. В ней мы заменили символ y на символ m. И, согласно ранее описанной схеме сопоставления, номер Гёделя у символа y равен 17. Давайте тогда обозначим номер Гёделя новой формулы sub(m, m, 17).

Подстановка формирует основу доказательства Гёделя.

Студент Курт Гёдель в Вене. Теоремы о неполноте он опубликовал в 1931 году, через год после получения диплома.

Он рассмотрел следующее математическое утверждение: „Формулу с номером Гёделя sub(y, y, 17) нельзя доказать“. Вспоминая только что принятые нами обозначения, мы знаем, что формулу с номером Гёделя sub(y, y, 17) мы получаем, взяв формулу с номером Гёделя y (некая неизвестная переменная) и подставив эту переменную y везде, где в формуле стоит символ с номером Гёделя, равным 17 (то есть, везде, где встречается y).

Голова уже начинает кружиться, но, тем не менее, мы определённо можем перевести наше метаматематическое утверждение, „формулу с номером Гёделя sub(y, y, 17) нельзя доказать“, в формулу с уникальным номером Гёделя. Назовём его n.

И последний этап подстановок: Гёдель создаёт новую формулу, подставляя число n везде, где в предыдущей формуле стоит y. Его новая формула получается следующей: „Формулу с номером Гёделя sub(n, n, 17) нельзя доказать“. Назовём эту формулу G.

У G, естественно, есть номер Гёделя. Каков этот номер? Вуаля – он должен равняться sub(n, n, 17). По определению, sub(n, n, 17) – это номер Гёделя для формулы, которая получается путём взятия формулы с номером Гёделя n и подстановки n везде, где в формуле встречается символ с номером Гёделя, равным 17. И G именно такая формула и есть! Поскольку целые числа раскладываются на простые множители уникальным способом, нам становится понятно, что формула G говорит нам только о самой формуле G, и более ни о какой другой.

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

Но можно ли доказать G? Если бы это было возможно, это означало бы, что существует некая последовательность формул, доказывающих формулу с номером Гёделя, равным sub(n, n, 17). Но это противоположность формулы G, утверждающей, что такого доказательства не существует. Противоположные утверждения, G и

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

Однако, несмотря на то, что G доказать нельзя, она определённо правдива. G говорит, что „формулу с номером Гёделя sub(n, n, 17) нельзя доказать“, а именно это мы и установили! Поскольку G – истинное, но недоказуемое утверждение, существующее в рамках аксиоматической системы, которую мы использовали для его построения, эта система неполна.

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

Отсутствие доказательства непротиворечивости

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

Что означало бы, если бы набор аксиом мог доказать, что он никогда не вызовет противоречий? Это означало бы, что существует последовательность формул, построенных на этих аксиомах, доказывающих формулу, которая метаматематически означает „этот набор аксиом непротиворечив“. Но тогда, согласно первой теореме, этот набор аксиом обязательно был бы неполным.

Однако сказать, что „набор аксиом неполон“, это то же самое, что сказать „существует истинная формула, которую нельзя доказать“. А это равнозначно нашей формуле G. А мы знаем, что аксиомы не могут доказать G.

Так Гёдель построил доказательство от противного: если бы набор аксиом мог доказать собственную непротиворечивость, тогда мы могли бы доказать G. Но мы этого сделать не можем. Следовательно, ни один набор аксиом не доказывает собственную непротиворечивость.

Доказательство Гёделя убило поиски непротиворечивой и полной математической системы. Математики „не смогли осознать всю глубину“ неполноты, писали Нагель и Ньюмен в 1958. И сегодня это утверждение остаётся истинным.

Источник