Теорема Тарского о неопределимости

Теорема о неопределимости Тарского , сформулированная и доказанная Альфредом Тарским в 1933 году, является важным ограничительным результатом в математической логике , основах математики и формальной семантики . Неофициально теорема утверждает, что «арифметическая истина не может быть определена в арифметике». ^[1]

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

История

В 1931 году Курт Гёдель опубликовал теоремы о неполноте , которые он частично доказал, показав, как представлять синтаксис формальной логики в рамках арифметики первого порядка . Каждому выражению формального языка арифметики присвоен отдельный номер. Эта процедура известна по-разному как нумерация Гёделя , кодирование и, в более общем смысле, как арифметизация. В частности, различные наборы выражений кодируются как наборы чисел. Для различных синтаксических свойств (таких как формула , предложение и т. д.) эти множества являются вычислимыми . Более того, любой вычислимый набор чисел можно определить некоторой арифметической формулой. Например, в языке арифметики существуют формулы, определяющие набор кодов для арифметических предложений и для доказуемых арифметических предложений.

Теорема о неопределимости показывает, что такое кодирование невозможно выполнить для семантических понятий, таких как истина. Это показывает, что ни один достаточно богатый интерпретируемый язык не может представлять собственную семантику. Следствием этого является то, что любой метаязык, способный выражать семантику некоторого объектного языка (например, в теории множеств Цермело-Френкеля можно определить предикат, определяющий, верны ли формулы на языке арифметики Пеано в стандартной модели арифметики). ^[2]) должен иметь выразительную силу, превышающую выразительную силу объектного языка. Метаязык включает в себя примитивные понятия, аксиомы и правила, отсутствующие в объектном языке, так что существуют теоремы, доказуемые на метаязыке, но не доказуемые на объектном языке.

Теорему о неопределяемости традиционно приписывают Альфреду Тарскому . Гёдель также открыл теорему о неопределимости в 1930 году, доказав при этом свои теоремы о неполноте, опубликованные в 1931 году, и задолго до публикации работы Тарского в 1933 году (Муравски 1998). Хотя Гёдель никогда не публиковал ничего, что имело бы отношение к его независимому открытию неопределимости, он описал это в письме 1931 года Джону фон Нейману . Тарский получил почти все результаты своей монографии 1933 года « Понятие истины в языках дедуктивных наук » между 1929 и 1931 годами и рассказал о них польской аудитории. Однако, как он подчеркнул в статье, теорема о неопределимости была единственным результатом, которого он не получил ранее. Согласно сноске к теореме о неопределимости (Twierdzenie I) монографии 1933 г., теорема и схема доказательства были добавлены в монографию только после того, как рукопись была отправлена в типографию в 1931 г. Тарский сообщает там, что, когда он представил содержание своей монографии Варшавской академии наук 21 марта 1931 года, он высказал здесь лишь некоторые предположения, основанные частично на его собственных исследованиях, а частично на кратком докладе Гёделя о теоремах о неполноте» Некоторые метаматематические результаты об определенности решения и непротиворечивости, Австрийская академия наук , Вена, 1930.

Заявление

Сначала мы сформулируем упрощенную версию теоремы Тарского, а затем сформулируем и докажем в следующем разделе теорему, доказанную Тарским в 1933 году.

Позволять $L$ быть языком арифметики первого порядка . Это теория натуральных чисел , включая их сложение и умножение, аксиоматизированная аксиомами Пеано первого порядка . Это теория « первого порядка »: кванторы распространяются на натуральные числа, но не на множества или функции натуральных чисел. Теория достаточно сильна, чтобы описать рекурсивно определенные целочисленные функции, такие как возведение в степень, факториалы или последовательность Фибоначчи .

Позволять ${\mathcal {N}}$ быть стандартной структурой для $L,$ т.е. ${\mathcal {N}}$ состоит из обычного набора натуральных чисел, их сложения и умножения. Каждое предложение в $L$ можно интерпретировать в ${\mathcal {N}}$ и тогда становится либо истинным, либо ложным. Таким образом $(L,{\mathcal {N}})$ это «интерпретируемый язык арифметики первого порядка».

Каждая формула $\varphi$ в $L$ имеет число Гёделя $g(\varphi ).$ Это натуральное число, которое «кодирует» $\varphi .$ Таким образом, язык $L$ можно говорить о формулах $L,$ не только о цифрах. Позволять $T$ обозначим множество $L$ -предложения верны в ${\mathcal {N}}$ , и $T^{*}$ набор чисел Гёделя предложений в $T.$ Следующая теорема отвечает на вопрос: может ли $T^{*}$ определяться формулой арифметики первого порядка?

Теорема Тарского о неопределимости : не существует $L$ -формула $\mathrm {True} (n)$ что определяет $T^{*}.$ То есть нет $L$ -формула $\mathrm {True} (n)$ такой, что для каждого $L$ -предложение $A,$ $\mathrm {True} (g(A))\iff A$ держится ${\mathcal {N}}$ .

Неформально теорема гласит, что понятие истинности арифметических утверждений первого порядка не может быть определено формулой арифметики первого порядка. Это подразумевает серьезное ограничение сферы «самопредставительства». Можно формулу определить $\mathrm {True} (n)$ чье расширение $T^{*},$ но только путем использования метаязыка , выразительная сила которого выходит за рамки $L$ . Например, предикат истинности для арифметики первого порядка может быть определен в арифметике второго порядка . Однако эта формула сможет определить предикат истинности только для формул на исходном языке. $L$ . Чтобы определить предикат истинности для метаязыка, потребовался бы еще более высокий метаметаязык и так далее.

Для доказательства теоремы поступим от противного и предположим, что $L$ -формула $\mathrm {True} (n)$ существует, что верно для натурального числа $n$ в ${\mathcal {N}}$ тогда и только тогда, когда $n$ - это число Гёделя предложения в $L$ это правда в ${\mathcal {N}}$ . Затем мы могли бы использовать $\mathrm {True} (n)$ определить новый $L$ -формула $S(m)$ что верно для натурального числа $m$ тогда и только тогда, когда $m$ - число Гёделя формулы $\varphi (x)$ (со свободной переменной $x$ ) такой, что $\varphi (m)$ ложно при интерпретации в ${\mathcal {N}}$ (т.е. формула $\varphi (x),$ применительно к собственному числу Гёделя дает ложное утверждение). Если мы теперь рассмотрим число Гёделя $g$ формулы $S(m)$ и спросите, является ли предложение $S(g)$ верно в ${\mathcal {N}}$ , получаем противоречие. (Это известно как диагональный аргумент .)

Эта теорема является следствием теоремы Поста об арифметической иерархии , доказанной через несколько лет после Тарского (1933). Семантическое доказательство теоремы Тарского из теоремы Поста получается методом доведения до абсурда следующим образом. Предполагая $T^{*}$ арифметически определимо, существует натуральное число $n$ такой, что $T^{*}$ определяется формулой на уровне $\Sigma _{n}^{0}$ иерархии арифметической . Однако, $T^{*}$ является $\Sigma _{k}^{0}$ -тяжело для всех $k.$ Таким образом, арифметическая иерархия рушится на уровне $n$ , что противоречит теореме Поста.

Общая форма

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

Теорема Тарского о неопределимости (общая форма) : Пусть $(L,{\mathcal {N}})$ быть любым интерпретируемым формальным языком, который включает отрицание и имеет нумерацию Гёделя. $g(\varphi )$ удовлетворяющее диагональной лемме, т.е. для любого $L$ -формула $B(x)$ (с одной свободной переменной $x$ ) есть предложение $A$ такой, что $A\iff B(g(A))$ держится ${\mathcal {N}}$ . Тогда нет $L$ -формула $\mathrm {True} (n)$ со следующим свойством: для каждого $L$ -предложение $A,$ $\mathrm {True} (g(A))\iff A$ верно в ${\mathcal {N}}$ .

Доказательство теоремы Тарского о неопределимости в этой форме снова проводится методом доведения до абсурда . Предположим, что $L$ -формула $\mathrm {True} (n)$ как указано выше, существовало, т. е. если $A$ является арифметическим предложением, то $\mathrm {True} (g(A))$ держится ${\mathcal {N}}$ тогда и только тогда, когда $A$ держится ${\mathcal {N}}$ . Следовательно для всех $A$ , формула $\mathrm {True} (g(A))\iff A$ держится ${\mathcal {N}}$ . Но диагональная лемма дает контрпример этой эквивалентности, давая формулу «лжеца» $S$ такой, что $S\iff \lnot \mathrm {True} (g(S))$ держится ${\mathcal {N}}$ . Это противоречие. КЭД.

Обсуждение

Формальный механизм приведенного выше доказательства совершенно элементарен, за исключением диагонализации, которую требует диагональная лемма. Доказательство диагональной леммы также удивительно просто; например, он не вызывает рекурсивные функции никоим образом . Доказательство предполагает, что каждый $L$ -формула имеет номер Гёделя , но особенности метода кодирования не требуются. Следовательно, теорему Тарского гораздо легче мотивировать и доказать, чем более знаменитые теоремы Гёделя о метаматематических свойствах арифметики первого порядка.

Смуллян (1991, 2001) убедительно доказывал, что теорема Тарского о неопределимости заслуживает такого же внимания, как и теоремы Гёделя о неполноте . То, что последние теоремы могут многое сказать обо всей математике и, что более спорно, о ряде философских проблем (например, Лукас , 1961), менее чем очевидно. Теорема Тарского, с другой стороны, касается не непосредственно математики, а внутренних ограничений любого формального языка, достаточно выразительного, чтобы представлять реальный интерес. Такие языки обязательно способны к достаточной самореференции , чтобы к ним можно было применить диагональную лемму. Более широкий философский смысл теоремы Тарского более очевиден.

Интерпретируемый язык является строго семантически саморепрезентативным именно тогда, когда язык содержит предикаты и функциональные символы, определяющие все семантические понятия, специфичные для языка. Следовательно, требуемые функции включают в себя «функцию семантической оценки», отображающую формулу $A$ его истинностному значению $||A||,$ и «функция семантического обозначения», отображающая термин $t$ к объекту, который он обозначает. Теорема Тарского затем обобщается следующим образом: ни один достаточно мощный язык не является строго семантически саморепрезентативным .

Теорема о неопределимости не препятствует определению истины в одной теории в более сильной теории. первого порядка Например, набор формул (кодов) арифметики Пеано , которые верны в ${\mathcal {N}}$ определяется формулой арифметики второго порядка . Аналогично множество истинных формул стандартной модели арифметики второго порядка (или $n$ арифметика -го порядка для любого $n$ ) можно определить по формуле в ZFC первого порядка .

См. также

Теорема Чайтина о неполноте - мера алгоритмической сложности.
Теорема Гёделя о полноте - Основная теорема математической логики
Теоремы Гёделя о неполноте - Ограничительные результаты в математической логике

Ссылки

^ Цезарь Цеслинский, «Как Тарский определил неопределимое», European Review 23.1 (2015): 139–149.
^ Джоэл Дэвид Хэмкинс; Ян, Жуйчжи (2013). «Удовлетворение не является абсолютным». arXiv : 1312.0670 [ math.LO ].

Первоисточники

Тарский, А. (1933). Понятие истины в языках дедуктивных наук (на польском языке). Издано Варшавским научным обществом.
Тарский, А. (1936). «Понятие истины в формализованных языках» (PDF) . Studia Philosophica (на немецком языке). 1 :261-405. Архивировано из оригинала (PDF) 9 января 2014 года . Проверено 26 июня 2013 г.
- Тарский, А. (1983). «Понятие истины в формализованных языках» (PDF) . В Коркоран, Дж. (ред.). Логика, семантика, метаматематика . Перевод Дж. Х. Вудгера. Хакетт. Английский перевод статьи Тарского 1936 года.

Дальнейшее чтение

Белл, Дж.Л.; Мачовер, М. (1977). Курс математической логики . Северная Голландия.
Булос, Г .; Берджесс, Дж .; Джеффри, Р. (2002). Вычислимость и логика (4-е изд.). Издательство Кембриджского университета.
Лукас, младший (1961). «Разум, машины и Гёдель» . Философия . 36 (137): 112–27. дои : 10.1017/S0031819100057983 . S2CID 55408480 . Архивировано из оригинала 19 августа 2007 г.
Муравски, Р. (1998). «Неопределенность истины. Проблема приоритета: Тарский против Гёделя» . История и философия логики . 19 (3): 153–160. дои : 10.1080/01445349808837306 . Архивировано из оригинала 8 июня 2011 г.
Смалльян, Раймонд М. (1992). Теоремы Гёделя о неполноте . Оксфорд: Издательство Оксфордского университета, США. ISBN 0-19-504672-2 .
Смуллян, Р. (2001). «Теоремы Гёделя о неполноте». В Гобл, Л. (ред.). Руководство Блэквелла по философской логике . Блэквелл. стр. 72–89. ISBN 978-0-631-20693-4 .

[1] Цезарь Цеслинский, «Как Тарский определил неопределимое», European Review 23.1 (2015): 139–149.

[2] Джоэл Дэвид Хэмкинс; Ян, Жуйчжи (2013). «Удовлетворение не является абсолютным». arXiv : 1312.0670 [ math.LO ].

[1]

[2]

v т и Правда
Общий	Заявление Предложения носитель истины Создатель истины
Теории	Согласованность Консенсус конструктивист Переписка дефляционный Эпистемический Плюралистический Прагматичный Резервирование Семантический