Эрнст Нагель - Teopeма Гёделя

• Название: Teopeма Гёделя
• Автор: Эрнст Нагель
• Издательство: КРАСАНД
• Жанр: Математика
• Год: 2010
• ISBN: 978-5-396-00092-6

Нагель Эрнест, Ньюмен Джеймс Рой. Теорема Гёделя: Пер. с англ. Изд. 2-е, испр. — М.: КРАСАНД, 2010. — 120 с. (НАУКУ — ВСЕМ! Шедевры научно-популярной литературы.)

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

Для специалистов по математической логике, студентов и аспирантов, а также всех заинтересованных читателей.

---

Другое направление исследований, тесно связанное с разработкой математиками XIX столетия проблематики оснований анализа, также оказалось близким программе Буля. Целью нового направления было представить всю чистую математику как часть формальной логики. Классическое выражение эта линия развития логики и математики получила в Principia Mathematica Уайтхеда и Рассела (1910–1913). Математикам XIX-го столетия удалось «арифметизировать» алгебру и так называемое «исчисление бесконечно малых», показав, что различные понятия, используемые в математическом анализе, определимы исключительно в арифметических терминах (т. е. в терминах целых чисел и арифметических операций над ними). Например, вместо того чтобы допускать мнимое число √-1 в качестве некоей мистической «сущности», его стали определять как упорядоченную пару целых чисел (0,1), причем над такими парами разрешено было производить определенного рода операции «сложения» и «умножения». Аналогично, иррациональное число √2 теперь стали определять как некоторый класс рациональных чисел, а именно, как класс рациональных чисел, квадраты которых меньше 2. Рассел же (а еще ранее немецкий математик Готтлоб Фреге) поставил своей целью показать, что все арифметические понятия можно определить в чисто логических терминах, а все аксиомы арифметики вывести из небольшого числа предложений, которые можно было бы квалифицировать как чисто логические истины.

Приведем пример. В логике имеется понятие класса. Два класса, по определению, «подобны», если между их членами можно установить взаимно-однозначное соответствие (причем понятие взаимно-однозначного соответствия само может быть определено в терминах других логических понятий). Класс, имеющий единственный член, называется «единичным классом» (таков, например, класс естественных спутников Земли); кардинальное (количественное) число 1 определяется как класс всех классов, подобных какому-либо единичному классу. Аналогично можно определить и другие кардинальные числа; различные арифметические операции (сложение, умножение и т. д.) также можно определить через понятия формальной логики. Произвольное арифметическое утверждение (скажем, «1 + 1 = 2») можно теперь представить как сокращенную запись некоторого утверждения, составленного исключительно из выражений, принадлежащих обычной логике, и все такие чисто логические утверждения, как можно показать, выводимы из некоторой системы логических аксиом.

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

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

5 Один пример абсолютного доказательства непротиворечивости

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

Мы покажем здесь коротко, как можно формализовать элементарную логику высказываний, являющуюся некоторым фрагментом системы, описанной в Principia Mathematica. В результате формализации упомянутый фрагмент Principia станет исчислением, состоящим из неинтепретированных символов. После этого мы уже сможем провести нужнее нам доказательство.

Формализация проходит в четыре этапа. Прежде всего нам понадобится полный перечень символов, которые используются в нашем исчислении, они составят так называемый алфавит системы. Далее нам надо будет сформулировать «правила образования», согласно которым из «букв» алфавита составляются «формулы» (причем только такие, «правильно составленные», сочетания символов мы будем считать предложениями нашей системы). Можно было бы считать совокупность правил «грамматикой» исчисления. Затем мы отбираем некоторые формулы нашей системы в качестве ее аксиом (или «исходных формул»), аксиомы служат «базисом» системы. И, наконец, мы сформулируем «правила преобразования», точно описывающие, каким образом из одних формул некоторого вида «выводятся» другие формулы определенного вида; иначе говоря, правила эти — не что иное, как правила вывода. Теоремой нашей системы мы будем называть теперь любую формулу, получаемую посредством последовательного применения правил преобразования к аксиомам. Формальным «доказательством» мы будем называть любую конечную последовательность формул рассматриваемого исчисления, каждая из которых либо является аксиомой, либо выводима из предшествующих формул данной последовательности с помощью правил преобразования[1].

Алфавит логики высказываний (называемой часто «пропозициональным исчислением») очень несложен. Он состоит из переменных и констант. Переменные, поскольку вместо них можно подставлять предложения (sentences) системы, называют сентенциональными (чаще — пропозициональными) переменными. В качестве переменных мы будем использовать буквы «p», «q», «r», …, «p1», «p2» …, «q1», «q2» ….

Постоянные символы (константы) — это «пропозициональные» связки и знаки препинания. Мы будем употреблять следующие пропозициональные связки: «~» читается как «не»; ˅ — «или»; «ﬤ» — «если…, то…»; «·» — «и»; знаки препинания: «(» — «левая скобка», «)» — «правая скобка».

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

Правила образования указывают, какие именно комбинации элементарных символов алфавита мы будем считать формулами нашего исчисления. Прежде всего формулой, по определению, является каждая пропозициональная переменная. Далее, если «S» обозначает некоторую формулу[2], то ее «формальное отрицание» «~ (S)» также есть формула. Аналогично, если «S1» и «S2»суть обозначения некоторых формул, то выражения «(S1) ˅ (S2)», «(S1) ﬤ (S2)» и «(S1)·(S2)» также суть формулы.

Примеры формул:

«p», «~ p», «(р) ﬤ (q)», «((q) ˅ (r)) ﬤ (p)».

Однако выражения «(p)(~ q)» или «((р)ﬤ(q))˅» формулами не являются, так как они не удовлетворяют приведенному здесь определению формулы[3].