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

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

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

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

История

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

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

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

Заявление

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

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

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

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

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

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

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

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

Общая форма

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

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

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

Обсуждение

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

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

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

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

Смотрите также

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

Рекомендации

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

Основные источники

• Тарский, А. (1933). Pojęcie Prawdy w Językach Nauk Dedukcyjnych (на польском языке). Nakładem Towarzystwa Naukowego Warszawskiego.
• Тарский, А. (1936). «Der Wahrheitsbegriff в формальном разговоре» (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 г.
• Смалльян, Р. (1991). Теоремы Гёделя о неполноте . Оксфордский университет. Нажимать.
• Смуллян, Р. (2001). «Теоремы Гёделя о неполноте». В Гобл, Л. (ред.). Руководство Блэквелла по философской логике . Блэквелл. стр. 72–89.