«Begriffsschrift»: вся современная логика в 88 страницах

Что было не так со старой логикой

Силлогистика Аристотеля разбирала высказывания вида «всякий $S$ есть $P$». Алгебра Буля научилась считать со связками «и», «или», «не». Ни та ни другая не умели записать простейшее утверждение математического анализа:

для всякого $\varepsilon > 0$ найдётся $\delta > 0$ такое, что при $|x - a| < \delta$ выполнено $|f(x) - f(a)| < \varepsilon$.

Здесь два разных квантора, и порядок их существен: поменяйте местами «для всякого» и «найдётся» — получите равномерную непрерывность, совсем другое свойство. Ни одна логика до 1879 года не умела выразить эту разницу. Математики пользовались кванторами интуитивно и путались (история с равномерной сходимостью, стоившая КошиОгюстен Луи Кошифранцузский математик · 1789–1857Первым потребовал от анализа доказательств вместо очевидности — и первым написал учебник, по которому это можно было выучить. ошибочной теоремы, — из этого ряда).

Готлоб Фреге, тридцатилетний приват-доцент Йенского университета, издаёт в 1879 году книжку в 88 страниц: «Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens» — «Понятийное письмо, язык формул чистого мышления, построенный по образцу арифметического».

Название точное: он действительно строит язык, а не сокращённую запись.

Три хода

Первый: функция и аргумент вместо подлежащего и сказуемого.

АристотельАристотельгреческий философ · 384–322 до н. э.Не был математиком, но задал математике две вещи, которыми она пользуется до сих пор: определение науки как вывода из недоказуемых начал и открытие, что правильность рассуждения зависит только от его формы. разбирал «Сократ смертен» на субъект и предикат — то есть по грамматике. Фреге предлагает разбирать по образцу математики: есть функция «… смертен» и аргумент «Сократ». Пишем $\text{Смертен}(\text{Сократ})$.

Выигрыш мгновенный: функция может иметь два аргумента и больше. «$x$ есть голова $y$», «$x$ больше $y$», «$x$ лежит между $y$ и $z$». Тот самый разряд утверждений — про отношения, — на котором ломалась силлогистика, здесь не составляет никакой трудности.

Второй: кванторы.

Фреге вводит знак общности («для всякого») и определяет через него и отрицание существование: «найдётся $x$» — это «неверно, что для всякого $x$ неверно». Кванторы можно навешивать друг на друга в любом порядке, и порядок меняет смысл. Определение непрерывности записывается однозначно и проверяется механически.

Третий: формальное доказательство.

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

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

Нотация, которую никто не осилил

И вот здесь Фреге совершил ошибку, стоившую ему двадцати лет.

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

Формулы разрастались на полстраницы вширь и вниз. Наборщики страдали, читатели сдавались. Эрнст Шрёдер, тогдашний авторитет в алгебре логики, в рецензии 1880 года отозвался снисходительно: нотация неудобна, а по существу перед нами едва ли не пересказ БуляДжордж Бульанглийский математик и логик · 1815–1864Сын сапожника, не проучившийся в университете ни дня, превратил логику в алгебру — и через девяносто лет выяснилось, что это в точности алгебра электрических переключателей..

Рецензия несправедлива дважды. У Буля не было кванторов — то есть не было главного. Но именно эта оценка определила судьбу книги: её сочли вариацией на известную тему.

Победила нотация Пеано, появившаяся десятью годами позже: линейная, набирается в строчку, читается слева направо. Мы пишем $\forall x\,\big(F(x) \to G(x)\big)$ значками ПеаноДжузеппе Пеаноитальянский математик и логик · 1858–1932Аксиоматизировал натуральный ряд, векторное пространство и математическую запись — и построил кривую, которая проходит через каждую точку квадрата. — но смысл, который за ними стоит, придумал Фреге.

Что он строил дальше

Кванторы были не целью, а инструментом. Цель — логицизм: показать, что арифметика есть часть логики, что число — понятие не более загадочное, чем «и» или «не».

Программа выглядела так.

• «Grundlagen der Arithmetik» (1884) — замысел, изложенный словами, почти без формул. Одна из самых читаемых философских книг о математике: там разбирается вопрос «что такое число 4» и показывается, почему все привычные ответы негодны.
• «Grundgesetze der Arithmetik», том I (1893), том II (1903) — то же самое, но выведенное формально, до последнего шага.

Определение числа у Фреге хитрое и красивое: число понятия $F$ — это класс всех понятий, которые можно поставить с $F$ во взаимно однозначное соответствие. «Четыре» — то общее, что есть у всех четвёрок. А чтобы получить натуральный ряд, нужно уметь сказать «$n$ получается из нуля конечным числом прибавлений единицы», — и здесь Фреге в третьей части «Begriffsschrift» строит конструкцию, которую сегодня называют транзитивным замыканием, и получает из неё математическую индукцию как теорему логики. Это место в книжке — до сих пор образец.

Развязка

В 1902 году, когда второй том «Grundgesetze» был уже в типографии, Фреге получил письмо от Бертрана Рассела с указанием на противоречие в его аксиомах.

Собственную научную судьбу Фреге пережил тяжело. Ординарным профессором он так и не стал: экстраординарным — с 1879 года, почётным — с 1896-го. РасселБертран Расселанглийский логик, философ и общественный деятель · 1872–1970Тремя строчками разрушил дело чужой жизни, десять лет чинил сломанное, а потом ушёл из математики в философию и политику — и получил Нобелевскую премию по литературе. писал, что до 1903 года, когда он сам привлёк к Фреге внимание, тот оставался попросту неизвестен.

Сегодня «Begriffsschrift» считается самой важной книгой в истории логики со времён Аристотеля. При жизни автора её тираж не разошёлся.

Следующая точка: Турин — где натуральный ряд получит пять аксиом, и одна из них знакома каждому десятикласснику.