Тарский: истина невыразима изнутри

Вторая столица

Между войнами столиц логики было две. Одна — Гёттинген и Вена. Другая — Польша.

Варшавско-львовская школа выросла из семинара Казимежа Твардовского и к двадцатым годам стала явлением без аналогов: логику здесь занимались десятки людей одновременно, и занимались профессионально.

• Ян Лукасевич — трёхзначная логика (1920): между «истинно» и «ложно» вводится третье значение, и получается работающее исчисление. Его же изобретение — бесскобочная запись формул, «польская нотация», которой пользуются калькуляторы и стековые машины.
• Станислав Лесневский — три собственные формальные системы; учитель Тарского.
• Мойжеш Пресбургер — на семинаре 1929 года доказывает, что арифметика со сложением, но без умножения полна и разрешима. Магистерская работа, ставшая классикой; сам он погиб в Холокосте.
• Стефан Банах и Тарский — парадокс о разрезании шара (1924), львовская часть той же школы.

Альфред Тарский (1901–1983) родился в Варшаве под фамилией Тайтельбаум, сменил её в 1924-м. Докторскую защитил в двадцать три года у Лесневского.

Вопрос, который считался не математическим

«Что значит, что предложение истинно?» — вопрос философский, и две тысячи лет он оставался у философов. Тарский заметил, что для формального языка на него можно ответить математически.

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

Предложение «снег бел» истинно тогда и только тогда, когда снег бел.

Это конвенция T. В общем виде: для каждого предложения $\varphi$ языка определение истины обязано давать

$$\mathrm{Ист}(\ulcorner \varphi \urcorner) \leftrightarrow \varphi.$$

Слева стоит утверждение о предложении (о его номере, о тексте), справа — само предложение, утверждение о мире. Определение истины — это то, что связывает два этих уровня.

Дальше Тарский строит само определение. Ключевой ход: определять не «истинно», а более общее «набор значений переменных удовлетворяет формуле», и делать это индукцией по построению формулы:

• набор удовлетворяет формуле $x < y$, если первое число меньше второго;
• набор удовлетворяет $\neg\psi$, если он не удовлетворяет $\psi$;
• набор удовлетворяет $\psi \wedge \chi$, если удовлетворяет обеим;
• набор удовлетворяет $\forall x\, \psi$, если ему удовлетворяет любой набор, отличающийся разве что значением $x$.

Предложение (формула без свободных переменных) истинно, если ему удовлетворяет любой набор. Всё.

Определение выглядит почти тавтологией — и именно поэтому оно правильное. Из него, между прочим, выросла теория моделей: «формула истинна в структуре» — это ровно то, что здесь определено, и на этом определении стоит вся дальнейшая работа Мальцева, Робинсона и самого Тарского в Беркли.

Теорема о невыразимости

А теперь главное. Определение истины построено на метаязыке — снаружи. Тарский доказывает, что иначе и быть не может.

Теорема (1933). Пусть язык достаточно богат (содержит арифметику). Тогда множество номеров истинных предложений этого языка не задаётся никакой формулой этого же языка.

Доказательство — в две строчки, если уже есть лемма о неподвижной точке из предыдущей точки. Пусть формула $\mathrm{Ист}(x)$ выражает истинность. Построим по лемме предложение $L$ с

$$L \leftrightarrow \neg\,\mathrm{Ист}(\ulcorner L \urcorner).$$

$L$ говорит: «я не истинно». Если $L$ истинно, то по конвенции T истинна и правая часть, то есть $L$ не истинно. И наоборот. Противоречие — значит, формулы $\mathrm{Ист}$ не существует. $\blacksquare$

Это парадокс лжеца Евбулида в чистом виде, обращённый из курьёза в инструмент.

Почему это важнее, чем кажется

Сравните две теоремы:

	Доказуемость	Истинность
Выразима внутри арифметики?	да ($\exists p\ \mathrm{Dok}(p,f)$)	нет (Тарский)
Проверяется перебором?	да: перебирай доказательства	нет

Вот в этой разнице — весь смысл. Доказуемость арифметична, истина нет. Поэтому «я недоказуемо» — законное арифметическое предложение (и оно даёт теорему ГёделяКурт Гёдельавстрийский и американский логик · 1906–1978Доказал, что в любой достаточно богатой формальной системе есть истинные утверждения, которые она не может доказать, — и тем закрыл программу Гильберта в двадцать пять лет.), а «я ложно» записать невозможно (и парадокса не выходит).

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

Лечение, предложенное Тарским, — иерархия языков. Об истинности предложений языка $L_0$ говорят на языке $L_1$, о его истинности — на $L_2$, и так далее вверх. Ни один язык не содержит собственного понятия истины; каждый содержит понятие истины предыдущего.

Что было дальше

Дальше — история одного отъезда.

В августе 1939 года Тарский отплыл в США на конгресс по единству науки в Гарварде. Это был один из последних рейсов; конгресс открылся 3 сентября, через два дня после начала войны. Жена и двое детей остались в Польше — они уцелели, скрываясь под чужими именами. Почти вся остальная его семья погибла.

Варшавско-львовская школа была уничтожена: часть логиков погибла в Холокосте, часть — во время оккупации и Варшавского восстания; библиотеки и рукописи сгорели. Из логиков первого ряда уцелели немногие; Лукасевич закончил жизнь в Ирландии.

Тарский осел в Беркли и создал там третью столицу логики. Его собственные результаты после войны:

• разрешимость элементарной геометрии и вещественно замкнутых полей (1948–1951) — алгоритм, который по любому утверждению школьной планиметрии отвечает, верно ли оно. Точная граница гёделевской области снизу;
• теория моделей как самостоятельная дисциплина;
• аксиоматизация геометрии в первопорядковом языке, где переменные — только точки.

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

Следующая точка: Принстон, 1936 — где на вопрос ГильбертаДавид Гильбертнемецкий математик · 1862–1943Человек, сделавший Гёттинген столицей математики и задавший ей повестку на весь XX век — двадцатью тремя проблемами и одной программой, которую сам же и не смог спасти. ответят «нет», пользуясь языком, в котором нет ни чисел, ни машин.