Абсолютность (логика)

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

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

Вопросы абсолютности особенно важны в теории множеств и теории моделей — областях, где одновременно рассматриваются несколько структур. В теории моделей несколько основных результатов и определений мотивированы абсолютностью. В теории множеств хорошо изучен вопрос о том, какие свойства множеств являются абсолютными. Теорема об абсолютности Шоенфилда , предложенная Джозефом Шоенфилдом (1961), устанавливает абсолютность большого класса формул между моделью теории множеств и ее конструируемой вселенной , что имеет важные методологические последствия. абсолютность больших кардинальных аксиом Также изучается , известны положительные и отрицательные результаты.

В теории моделей

В теории моделей существует несколько общих результатов и определений, связанных с абсолютностью. Фундаментальным примером нисходящей абсолютности является то, что универсальные предложения (те, которые имеют только кванторы универсальности), которые истинны в структуре, также истинны в каждой подструктуре исходной структуры. И наоборот, экзистенциальные предложения абсолютны вверх от структуры к любой структуре, ее содержащей.

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

В теории множеств

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

Определенные свойства абсолютны для всех транзитивных моделей теории множеств, включая следующие (см. Jech (2003, раздел I.12) и Kunen (1980, раздел IV.3)).

x — пустое множество .
х — порядковый номер.
x — конечный ординал.
x является порядковым номером преемника.
x — предельный ординал.
х = ω.
x — это (график) функции .

Другие свойства не являются абсолютными:

Несоблюдение абсолютности для счетности

Парадокс Скулема — это кажущееся противоречие, заключающееся в том, что, с одной стороны, множество действительных чисел несчетно (и это доказывается с помощью ZFC или даже с помощью небольшой конечной подсистемы ZFC' из ZFC), в то время как с другой стороны существуют счетные транзитивные модели. ZFC' (в ZFC это доказуемо), и множество действительных чисел в такой модели будет счетным множеством. Парадокс можно разрешить, заметив, что счетность не является абсолютной для подмоделей конкретной модели ZFC. Возможно, что множество X счетно в модели теории множеств, но несчетно в подмодели, содержащей X , поскольку подмодель может не содержать биекции между X и ω, в то время как определение счетности заключается в существовании такой биекции. Теорема Левенхайма-Скулема в применении к ZFC показывает, что такая ситуация действительно имеет место.

Теорема Шенфилда об абсолютности

Теорема Шенфилда об абсолютности показывает, что $\Pi _{2}^{1}$ и $\Sigma _{2}^{1}$ предложения в аналитической иерархии являются абсолютными между моделью V ZF и конструируемой вселенной L модели, если интерпретировать их как утверждения о натуральных числах в каждой модели. Теорему можно релятивизировать, чтобы позволить предложению использовать наборы натуральных чисел из V в качестве параметров, и в этом случае L необходимо заменить наименьшей подмоделью, содержащей эти параметры и все порядковые номера. Теорема имеет следствия: $\Sigma _{3}^{1}$ предложения являются абсолютными вверх (если такое предложение выполняется в L, то оно выполняется и в V ) ^[1] и $\Pi _{3}^{1}$ предложения являются нисходящими абсолютными (если они выполняются в V, то они выполняются и в L ). Поскольку любые две транзитивные модели теории множеств с одинаковыми порядковыми номерами имеют одну и ту же конструктивную вселенную, теорема Шонфилда показывает, что две такие модели должны соглашаться относительно истинности всех $\Pi _{2}^{1}$ предложения.

Одно из следствий теоремы Шенфилда связано с аксиомой выбора . Гёдель доказал, что конструируемая вселенная L всегда удовлетворяет ZFC, включая аксиому выбора, даже если V предполагается, что удовлетворяет только ZF. Теорема Шенфилда показывает, что если существует модель ZF, в которой задано $\Sigma _{3}^{1}$ утверждение φ ложно, то φ также ложно в конструктивной вселенной этой модели. В противоположность этому это означает, что если ZFC доказывает $\Sigma _{3}^{1}$ предложение, то это предложение также доказуемо в ZF. Тот же аргумент можно применить к любому другому принципу, который всегда выполняется в конструируемой вселенной, например, к комбинаторному принципу ◊ . Даже если эти принципы независимы от ZF, каждый из их $\Sigma _{3}^{1}$ последствия уже доказуемы в ZF. В частности, сюда входят любые их следствия, которые могут быть выражены на языке (первого порядка) арифметики Пеано .

Теорема Шенфилда также показывает, что существуют пределы результатов независимости, которые можно получить, принуждая . В частности, любое предложение арифметики Пеано абсолютно для транзитивных моделей теории множеств с одинаковыми порядковыми номерами. Таким образом, невозможно использовать принуждение для изменения значения истинности арифметических предложений, поскольку принуждение не меняет порядковые номера модели, к которой оно применяется. Многие известные открытые проблемы, такие как гипотеза Римана и проблема P = NP , могут быть выражены как $\Pi _{2}^{1}$ предложения (или предложения более низкой сложности), и поэтому невозможно доказать независимость от ZFC путем принуждения.

Большие кардиналы

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

Один из примеров такой неабсолютной большой кардинальной аксиомы относится к измеримым кардиналам ; Чтобы ординал был измеримым кардиналом, должно существовать другое множество (мера), удовлетворяющее определенным свойствам. Можно показать, что ни одна такая мера не может быть построена.

См. также

Ссылки

Джех, Томас , 2003. Теория множеств: издание третьего тысячелетия, переработанное и расширенное . Спрингер. ISBN 3-540-44085-2 .
Кунен, Кеннет , 1980. Теория множеств: введение в доказательства независимости . Эльзевир. ISBN 0-444-86839-9 .
Шонфилд, Джозеф , 1961. «Проблема предикативности», Очерки по основам математики , Ю. Бар-Хилель и др. , ред., стр. 132–142.

Встроенные цитаты

^ П. Одифредди, Классическая теория рекурсии (1989), стр.430

[1] П. Одифредди, Классическая теория рекурсии (1989), стр.430

[1]