Jump to content

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

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

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

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

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

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

Заявление

[ редактировать ]

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

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

Позволять быть стандартной структурой для т.е. состоит из обычного набора натуральных чисел, их сложения и умножения. Каждое предложение в можно интерпретировать в и тогда становится либо истинным, либо ложным. Таким образом это «интерпретируемый язык арифметики первого порядка».

Каждая формула в имеет число Гёделя Это натуральное число, которое «кодирует» Таким образом, язык можно говорить о формулах не только о цифрах. Позволять обозначим множество -предложения верны в , и набор чисел Гёделя предложений в Следующая теорема отвечает на вопрос: может ли определяться формулой арифметики первого порядка?

Теорема Тарского о неопределимости : не существует -формула что определяет То есть нет -формула такой, что для каждого -предложение держится .

Неформально теорема гласит, что понятие истинности арифметических утверждений первого порядка не может быть определено формулой арифметики первого порядка. Это подразумевает серьезное ограничение сферы «самопредставительства». Можно формулу определить чье расширение но только путем использования метаязыка , выразительная сила которого выходит за рамки . Например, предикат истинности для арифметики первого порядка может быть определен в арифметике второго порядка . Однако эта формула сможет определить предикат истинности только для формул на исходном языке. . Чтобы определить предикат истинности для метаязыка, потребовался бы еще более высокий метаметаязык и так далее.

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

Эта теорема является следствием теоремы Поста об арифметической иерархии , доказанной через несколько лет после Тарского (1933). Семантическое доказательство теоремы Тарского из теоремы Поста получается методом доведения до абсурда следующим образом. Предполагая арифметически определимо, существует натуральное число такой, что определяется формулой на уровне иерархии арифметической . Однако, является -тяжело для всех Таким образом, арифметическая иерархия рушится на уровне , что противоречит теореме Поста.

Общая форма

[ редактировать ]

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

Теорема Тарского о неопределимости (общая форма) : Пусть быть любым интерпретируемым формальным языком, который включает отрицание и имеет нумерацию Гёделя. удовлетворяющее диагональной лемме, т.е. для любого -формула (с одной свободной переменной ) есть предложение такой, что держится . Тогда нет -формула со следующим свойством: для каждого -предложение верно в .

Доказательство теоремы Тарского о неопределимости в этой форме снова проводится методом доведения до абсурда . Предположим, что -формула как указано выше, существовало, т. е. если является арифметическим предложением, то держится тогда и только тогда, когда держится . Следовательно для всех , формула держится . Но диагональная лемма дает контрпример этой эквивалентности, давая формулу «лжеца» такой, что держится . Это противоречие. КЭД.

Обсуждение

[ редактировать ]

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

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

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

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

См. также

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

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

[ редактировать ]

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

[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 4a6a2e1cc878e78c7c90fa066d5861d2__1711210860
URL1:https://arc.ask3.ru/arc/aa/4a/d2/4a6a2e1cc878e78c7c90fa066d5861d2.html
Заголовок, (Title) документа по адресу, URL1:
Tarski's undefinability theorem - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)