Теорема Тарскиса о неопределенности - Tarskis undefinability theorem

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

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

История

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

Теорема о неопределенности показывает, что такое кодирование не может быть выполнено для семантический такие понятия, как правда. Это показывает, что ни один достаточно богатый интерпретируемый язык не может представлять свою собственную семантику. Следствие состоит в том, что любой метаязык способны выражать семантику некоторых объектный язык должен обладать выразительной силой, превышающей силу объектного языка. Метаязык включает примитивные понятия, аксиомы и правила, отсутствующие в объектном языке, так что существуют теоремы, которые можно доказать на метаязыке, а не на объектном языке.

Теорема о неопределенности условно приписывается Альфред Тарский. Гёдель также открыл теорему о неопределенности в 1930 году, одновременно доказав свои теоремы о неполноте, опубликованные в 1931 году, но задолго до публикации в 1933 году работы Тарского (Murawski 1998). Хотя Гёдель никогда не публиковал ничего, относящегося к его независимому открытию неопределимости, он описал это в письме 1931 г. Джон фон Нейман. Тарский получил почти все результаты своей монографии 1933 г. "Pojęcie Prawdy w Językach Nauk Dedukcyjnych" ("Понятие истины на языках дедуктивных наук") между 1929 и 1931 годами, и рассказывал о них польской аудитории. Однако, как он подчеркивал в статье, теорема о неопределенности была единственным результатом, которого он не получил ранее. Согласно сноске к теореме о неопределенности (Twierdzenie I) монография 1933 года, теорема и набросок доказательства были добавлены к монографии только после того, как рукопись была отправлена в типографию в 1931 году. Тарский сообщает там, что, когда он представил содержание своей монографии Варшавской академии наук в марте 21 декабря 1931 г. он высказал здесь лишь некоторые предположения, основанные частично на его собственных исследованиях и частично на кратком отчете Гёделя о теоремах о неполноте «Einige metamat Mathematische Resultate über Entscheidungsdefinitheit und Widerspruchsfreiheit», Akademie der Wissenschaften, 1930.

Заявление

Сначала мы сформулируем упрощенную версию теоремы Тарского, а затем сформулируем и докажем в следующем разделе теорему, доказанную Тарским в 1933 году. L быть языком арифметика первого порядка, и разреши N быть стандартом структура за L. Таким образом (L, N) является «интерпретируемым языком арифметики первого порядка». Каждое предложение Икс в L имеет Число Гёделя грамм(Икс). Позволять Т обозначим множество L-предложения верны в N, и Т* набор чисел Гёделя предложений в Т. Следующая теорема отвечает на вопрос: может ли Т* определяться формулой арифметики первого порядка?

Теорема Тарского о неопределенности: Здесь нет L-формула Истинный(п) что определяет Т*. То есть нет L-формула Истинный(п) такой, что для каждого L-формула А, Истинный(грамм(А)) ↔ А держит.

Неформально в теореме говорится, что при некоторой формальной арифметике понятие истины в этой арифметике не может быть определено с помощью выразительных средств, которые предоставляет эта арифметика. Это подразумевает серьезное ограничение объема «саморепрезентации». Это является можно определить формулу Истинный(п), расширение которого Т*, но только путем рисования метаязык чья выразительная сила превосходит L. Например, предикат истины для арифметики первого порядка можно определить в арифметика второго порядка. Однако эта формула сможет определить предикат истинности только для предложений на исходном языке. L. Чтобы определить предикат истинности для метаязыка, потребуется метаметаязык еще более высокого уровня и так далее.

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

Общая форма

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

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

Доказательство теоремы Тарского о неопределенности в этой форме снова проводится сокращение до абсурда. Предположим, что L- формула Истинный(п) определяет Т*. В частности, если А это арифметическое предложение, тогда Истинный(грамм(А)) выполняется в N если и только если А верно в N. Следовательно, для всех А, Тарский Т-приговор Истинный(грамм(А)) ↔ А верно в N. Но диагональная лемма дает контрпример к этой эквивалентности, давая предложение "лжеца" S такой, что S ↔ ¬Истинный(грамм(S)) выполняется в N. Таким образом, нет L-формула Истинный(п) можно определить Т*. QED.

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

Обсуждение

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

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

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

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

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

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