Принуждение (математика)

Чтобы узнать об использовании форсирования в теории рекурсии , см. Форсирование (вычислимость) .

В математической дисциплине множеств теории форсирование — это метод доказательства непротиворечивости и независимости результатов. Интуитивно, принуждение можно рассматривать как метод расширения теоретической вселенной. $V$ в большую вселенную $V[G]$ путем введения нового «общего» объекта $G$.

Форсинг был впервые использован Полом Коэном в 1963 году, чтобы доказать независимость аксиомы выбора и гипотезы континуума от теории множеств Цермело – Френкеля . В последующие годы он был значительно переработан и упрощен и с тех пор стал мощным методом как в теории множеств, так и в таких областях математической логики , как теория рекурсии . Описательная теория множеств использует понятия принуждения как из теории рекурсии, так и из теории множеств. Форсирование также использовалось в теории моделей , но в теории моделей принято определять универсальность напрямую, без упоминания о принуждении.

Интуиция

Форсирование обычно используется для создания расширенной вселенной, удовлетворяющей некоторому желаемому свойству. Например, расширенная вселенная может содержать множество новых действительных чисел (по крайней мере $\aleph _{2}$ из них), отождествляемых с подмножествами множества $\mathbb {N}$ натуральных чисел, которых не было в старой Вселенной, и тем самым нарушают гипотезу континуума .

Чтобы интуитивно оправдать такое расширение, лучше всего думать о «старой Вселенной» как о модели. $M$ теории множеств, которая сама является множеством в «реальной вселенной». $V$. По Левенгейма–Скулема теореме $M$ может быть выбрана в качестве «голой» модели, которая является внешне счетной , что гарантирует, что будет много подмножеств (в $V$) из $\mathbb {N}$ которых нет в $M$. В частности, существует порядковый номер $\aleph _{2}^{M}$ который «играет роль кардинала $\aleph _{2}$" в $M$, но на самом деле счетно $V$. Работа в $V$, должно быть легко найти одно отдельное подмножество $\mathbb {N}$ за каждый элемент $\aleph _{2}^{M}$. (Для простоты это семейство подмножеств можно охарактеризовать одним подмножеством $X\subseteq \aleph _{2}^{M}\times \mathbb {N}$.)

Однако в некотором смысле может быть желательно «построить расширенную модель $M[X]$ в пределах $M$". Это поможет гарантировать, что $M[X]$ "похожий" $M$ в определенных аспектах, таких как $\aleph _{2}^{M[X]}$ быть таким же, как $\aleph _{2}^{M}$ (в более общем смысле, кардинального коллапса не происходит) и позволяют точно контролировать свойства $M[X]$. Точнее, каждый член $M[X]$ должно быть присвоено (неуникальное) имя в $M$. Имя можно рассматривать как выражение с точки зрения $X$, как и в простом расширении поля $L=K(\theta )$ каждый элемент $L$ может быть выражено через $\theta$. Основным компонентом принуждения является манипулирование этими именами внутри $M$, поэтому иногда может быть полезно напрямую подумать о $M$ как «Вселенная», зная, что теория принуждения гарантирует, что $M[X]$ будет соответствовать реальной модели.

Тонкий момент принуждения заключается в том, что, если $X$ считается произвольным «недостающим подмножеством» некоторого множества в $M$, тогда $M[X]$ построенный «внутри $M$"может быть, даже не модель. Это потому, что $X$ может кодировать «специальную» информацию о $M$ то, что невидимо внутри $M$ (например счетность , $M$), и тем самым доказать существование множеств, которые «слишком сложны для $M$ описать».

Форсирование позволяет избежать таких проблем, требуя вновь введенного набора $X$ быть общим набором относительно $M$. Некоторые утверждения «вынуждены» выполняться для любого общего $X$: Например, общий $X$ «вынужден» быть бесконечным. Кроме того, любое имущество (описываемое в $M$) общего набора «вынуждено» выполняться при некотором принудительном условии . Понятие «принуждение» можно определить в рамках $M$, и это дает $M$ достаточно аргументов, чтобы доказать это $M[X]$ действительно является моделью, которая удовлетворяет желаемым свойствам.

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

Роль модели

Чтобы описанный выше подход работал бесперебойно, $M$ фактически должна быть стандартной транзитивной моделью в $V$, так что членство и другие элементарные понятия могут обрабатываться интуитивно как в $M$ и $V$. Стандартную транзитивную модель можно получить из любой стандартной модели с помощью леммы о коллапсе Мостовского , но существование любой стандартной модели ${\mathsf {ZFC}}$ (или любой его вариант) само по себе является более сильным предположением, чем непротиворечивость ${\mathsf {ZFC}}$.

Чтобы обойти эту проблему, стандартный метод состоит в том, чтобы позволить $M$ — стандартная транзитивная модель произвольного конечного подмножества ${\mathsf {ZFC}}$ (любая аксиоматизация ${\mathsf {ZFC}}$ имеет хотя бы одну схему аксиом , а значит, и бесконечное число аксиом), существование которых гарантируется принципом отражения . Поскольку целью принуждающего аргумента является доказательство непротиворечивости результатов, этого достаточно, поскольку любое несоответствие в теории должно проявляться в выводе конечной длины и, следовательно, включать только конечное число аксиом.

Принудительные условия и принудительные посеты

Каждое условие воздействия можно рассматривать как конечный фрагмент информации об объекте. $X$ примыкает к модели. Существует множество различных способов предоставления информации об объекте, которые порождают различные понятия принуждения . Общий подход к формализации понятий воздействия состоит в том, чтобы рассматривать условия воздействия как абстрактные объекты с частично заданной структурой.

Форсинговый ЧУМ — это упорядоченная тройка, $(\mathbb {P} ,\leq ,\mathbf {1} )$, где $\leq$ это предзаказ на $\mathbb {P}$, и $\mathbf {1}$ является самым большим элементом. Члены $\mathbb {P}$ являются вынуждающими условиями (или просто условиями ). Отношение порядка $p\leq q$ означает " $p$ сильнее , чем $q$". (Интуитивно понятно, что условие "меньше" дает "больше" информации, точно так же, как меньший интервал $[3.1415926,3.1415927]$ дает больше информации о числе π, чем интервал $[3.1,3.2]$ делает.) Кроме того, предзаказ $\leq$ должен быть безатомным , то есть он должен удовлетворять условию расщепления :

• Для каждого $p\in \mathbb {P}$, есть $q,r\in \mathbb {P}$ такой, что $q,r\leq p$, без $s\in \mathbb {P}$ такой, что $s\leq q,r$.

Другими словами, должна быть возможность усилить любое вынуждающее условие. $p$ как минимум в двух несовместимых направлениях. Интуитивно это происходит потому, что $p$ представляет собой лишь конечный фрагмент информации, тогда как для определения необходим бесконечный фрагмент информации. $X$.

Используются различные соглашения. Некоторые авторы требуют $\leq$ также быть антисимметричным , так что отношение является частичным порядком . Некоторые все равно используют термин «частичный порядок» , что противоречит стандартной терминологии, а некоторые используют термин «предварительный порядок» . Без самого большого элемента можно обойтись. Обратный порядок также используется, особенно Сахароном Шелахом и его соавторами.

Примеры

Позволять $S$ быть любым бесконечным множеством (например, $\mathbb {N}$), и пусть рассматриваемый универсальный объект является новым подмножеством $X\subseteq S$. В исходной формулировке принуждения Коэна каждое условие принуждения представляет собой конечный набор предложений любого вида: $a\in X$ или $a\notin X$, которые являются самосогласованными (т.е. $a\in X$ и $a\notin X$ за ту же стоимость $a$ не появляются в том же состоянии). Это понятие принуждения обычно называют принуждением Коэна .

Принудительный набор для форсинга Коэна можно формально записать как $(\operatorname {Fin} (S,2),\supseteq ,0)$, конечные частичные функции из $S$ к $2~{\stackrel {\text{df}}{=}}~\{0,1\}$ при обратном включении. Форсинг Коэна удовлетворяет условию расщепления, поскольку при любом условии $p$, всегда можно найти элемент $a\in S$ не упоминается в $p$и добавьте либо предложение $a\in X$ или $a\notin X$ к $p$ получить два новых вынуждающих условия, несовместимых друг с другом.

Другой поучительный пример принудительного частичного множества: $(\operatorname {Bor} (I),\subseteq ,I)$, где $I=[0,1]$ и $\operatorname {Bor} (I)$ представляет собой совокупность подмножеств борелевских $I$ имеющая ненулевую меру Лебега . Общий объект, связанный с этим принудительным ЧУУ, представляет собой случайное действительное число. $r\in [0,1]$. Можно показать, что $r$ попадает в каждое борелевское подмножество $[0,1]$ с мерой 1 при условии, что борелевское подмножество «описано» в исходной нерасширенной вселенной (это можно формализовать с помощью концепции борелевских кодов ). Каждое вынуждающее условие можно рассматривать как случайное событие с вероятностью, равной его мере. Из-за интуитивного понимания, которое может обеспечить этот пример, вероятностный язык иногда используется с другими расходящими форсирующими наборами.

Общие фильтры

Несмотря на то, что каждое отдельное принудительное условие $p$ не может полностью определить родовой объект $X$, набор $G\subseteq \mathbb {P}$ всех истинных условий воздействия определяет $X$. В самом деле, без ограничения общности, $G$ обычно считается к родовым объектом, примыкающим $M$, поэтому расширенная модель называется $M[G]$. Обычно достаточно легко показать, что первоначально искомый объект $X$ действительно есть в модели $M[G]$.

В соответствии с этим соглашением концепция «родового объекта» может быть описана в общем виде. В частности, набор $G$ должен быть общий фильтр на $\mathbb {P}$ относительно $M$. Условие « фильтр » означает, что имеет смысл $G$ представляет собой набор всех истинных вынуждающих условий:

• $G\subseteq \mathbb {P} ;$
• $\mathbf {1} \in G;$
• если $p\geq q\in G$, затем $p\in G;$
• если $p,q\in G$, то существует $r\in G$ такой, что $r\leq p,q.$

Для $G$ быть «общим относительно $M$" означает:

• Если $D\in M$ представляет собой «плотное» подмножество $\mathbb {P}$ (то есть для каждого $p\in \mathbb {P}$, существует $q\in D$ такой, что $q\leq p$), затем $G\cap D\neq \varnothing$.

При условии $M$ — счетная модель, существование общего фильтра $G$ следует из леммы Расёвы–Сикорского . На самом деле верно немного большее: при условии $p\in \mathbb {P}$, можно найти общий фильтр $G$ такой, что $p\in G$. Ввиду условия расщепления на $\mathbb {P}$, если $G$ является фильтром, то $\mathbb {P} \setminus G$ плотный. Если $G\in M$, затем $\mathbb {P} \setminus G\in M$ потому что $M$ является моделью ${\mathsf {ZFC}}$. По этой причине универсальный фильтр никогда не используется. $M$.

П-имена и интерпретации

Связано с принудительным частично $\mathbb {P}$ это класс $V^{(\mathbb {P} )}$ из $\mathbb {P}$- имена . А $\mathbb {P}$-имя - это набор $A$ формы

$A\subseteq \{(u,p)\mid u~{\text{is a}}~\mathbb {P} {\text{-name and}}~p\in \mathbb {P} \}.$

Учитывая любой фильтр $G$ на $\mathbb {P}$, карта интерпретации или оценки из $\mathbb {P}$-имена даны

$\operatorname {val} (u,G)=\{\operatorname {val} (v,G)\mid \exists p\in G:~(v,p)\in u\}.$

The $\mathbb {P}$-имена, по сути, являются расширением Вселенной . Данный $x\in V$, один определяет ${\check {x}}$ быть $\mathbb {P}$-имя

${\check {x}}=\{({\check {y}},\mathbf {1} )\mid y\in x\}.$

С $\mathbf {1} \in G$, отсюда следует, что $\operatorname {val} ({\check {x}},G)=x$. В некотором смысле, ${\check {x}}$ это «имя для $x$" это не зависит от конкретного выбора $G$.

Это также позволяет определить «имя для $G$"без прямого упоминания $G$:

${\underline {G}}=\{({\check {p}},p)\mid p\in \mathbb {P} \}$

так что $\operatorname {val} ({\underline {G}},G)=\{\operatorname {val} ({\check {p}},G)\mid p\in G\}=G$.

Строгие определения

Концепции $\mathbb {P}$- имена, интерпретации и ${\check {x}}$ может быть определен трансфинитной рекурсией . С $\varnothing$ пустой набор, $\alpha +1$ порядкового порядковый номер, преемник номера $\alpha$, ${\mathcal {P}}$ оператор набора мощности и $\lambda$ предельный порядковый номер , определите следующую иерархию:

${\begin{aligned}\operatorname {Name} (\varnothing )&=\varnothing ,\\\operatorname {Name} (\alpha +1)&={\mathcal {P}}(\operatorname {Name} (\alpha )\times \mathbb {P} ),\\\operatorname {Name} (\lambda )&=\bigcup \{\operatorname {Name} (\alpha )\mid \alpha <\lambda \}.\end{aligned}}$

Тогда класс $\mathbb {P}$-names определяется как

$V^{(\mathbb {P} )}=\bigcup \{\operatorname {Name} (\alpha )~|~\alpha ~{\text{is an ordinal}}\}.$

Карта интерпретации и карта $x\mapsto {\check {x}}$ аналогичным образом можно определить с помощью иерархической конструкции.

Принуждение

Учитывая общий фильтр $G\subseteq \mathbb {P}$, поступают следующим образом. Подкласс $\mathbb {P}$-имена в $M$ обозначается $M^{(\mathbb {P} )}$. Позволять

$M[G]=\left\{\operatorname {val} (u,G)~{\Big |}~u\in M^{(\mathbb {P} )}\right\}.$

Чтобы сократить изучение теории множеств $M[G]$ к тому из $M$, мы работаем с «языком принуждения», который построен как обычная логика первого порядка , с членством в качестве бинарного отношения и всеми $\mathbb {P}$-имена как константы.

Определять $p\Vdash _{M,\mathbb {P} }\varphi (u_{1},\ldots ,u_{n})$ (читать как « $p$ силы $\varphi$ в модели $M$ с посетом $\mathbb {P}$"), где $p$ это состояние, $\varphi$ — это формула на языке принуждения, а $u_{i}$это $\mathbb {P}$-имена, означающие, что если $G$ это универсальный фильтр, содержащий $p$, затем $M[G]\models \varphi (\operatorname {val} (u_{1},G),\ldots ,\operatorname {val} (u_{n},G))$. Особый случай $\mathbf {1} \Vdash _{M,\mathbb {P} }\varphi$ часто пишется как « $\mathbb {P} \Vdash _{M,\mathbb {P} }\varphi$"или просто" $\Vdash _{M,\mathbb {P} }\varphi$". Такие утверждения верны в $M[G]$, несмотря ни на что $G$ является.

Важно то, что это внешнее определение принуждающего отношения $p\Vdash _{M,\mathbb {P} }\varphi$ эквивалентно внутреннему определению внутри $M$, определяемый трансфинитной индукцией (в частности $\in$-индукция ) по $\mathbb {P}$-имена на экземплярах $u\in v$ и $u=v$, а затем обычной индукцией по сложности формул. Это приводит к тому, что все свойства $M[G]$ действительно являются свойствами $M$, и проверка ${\mathsf {ZFC}}$ в $M[G]$ становится прямым. Обычно это суммируют как следующие три ключевых свойства:

• Правда : $M[G]\models \varphi (\operatorname {val} (u_{1},G),\ldots ,\operatorname {val} (u_{n},G))$ тогда и только тогда, когда это вызвано $G$, то есть для некоторого условия $p\in G$, у нас есть $p\Vdash _{M,\mathbb {P} }\varphi (u_{1},\ldots ,u_{n})$.
• Определимость : утверждение « $p\Vdash _{M,\mathbb {P} }\varphi (u_{1},\ldots ,u_{n})$"определяется в $M$.
• Согласованность : $p\Vdash _{M,\mathbb {P} }\varphi (u_{1},\ldots ,u_{n})\land q\leq p\implies q\Vdash _{M,\mathbb {P} }\varphi (u_{1},\ldots ,u_{n})$.

Внутреннее определение

Существует много разных, но эквивалентных способов определения принуждающего отношения. $\Vdash _{M,\mathbb {P} }$ в $M$. Один из способов упростить определение — сначала определить модифицированное принуждающее соотношение. $\Vdash _{M,\mathbb {P} }^{*}$ это строго сильнее, чем $\Vdash _{M,\mathbb {P} }$. Модифицированное отношение $\Vdash _{M,\mathbb {P} }^{*}$ по-прежнему удовлетворяет трем ключевым свойствам принуждения, но $p\Vdash _{M,\mathbb {P} }^{*}\varphi$ и $p\Vdash _{M,\mathbb {P} }^{*}\varphi '$ не обязательно эквивалентны, даже если формулы первого порядка $\varphi$ и $\varphi '$ эквивалентны. Тогда немодифицированное принуждающее отношение можно определить как $$p\Vdash _{M,\mathbb {P} }\varphi \iff p\Vdash _{M,\mathbb {P} }^{*}\neg \neg \varphi .$$ Фактически, первоначальная концепция принуждения Коэна, по сути, $\Vdash _{M,\mathbb {P} }^{*}$ скорее, чем $\Vdash _{M,\mathbb {P} }$.

Модифицированное принуждающее соотношение $\Vdash _{M,\mathbb {P} }^{*}$ можно определить рекурсивно следующим образом:

1. $p\Vdash _{M,\mathbb {P} }^{*}u\in v$ означает $(\exists (w,q)\in v)(q\geq p\wedge p\Vdash _{M,\mathbb {P} }^{*}w=u).$
2. $p\Vdash _{M,\mathbb {P} }^{*}u\neq v$ означает $(\exists (w,q)\in v)(q\geq p\wedge p\Vdash _{M,\mathbb {P} }^{*}w\notin u)\vee (\exists (w,q)\in u)(q\geq p\wedge p\Vdash _{M,\mathbb {P} }^{*}w\notin v).$
3. $p\Vdash _{M,\mathbb {P} }^{*}\neg \varphi$ означает $\neg (\exists q\leq p)(q\Vdash _{M,\mathbb {P} }^{*}\varphi ).$
4. $p\Vdash _{M,\mathbb {P} }^{*}(\varphi \vee \psi )$ означает $(p\Vdash _{M,\mathbb {P} }^{*}\varphi )\vee (p\Vdash _{M,\mathbb {P} }^{*}\psi ).$
5. $p\Vdash _{M,\mathbb {P} }^{*}\exists x\,\varphi (x)$ означает $(\exists u\in M^{(\mathbb {P} )})(p\Vdash _{M,\mathbb {P} }^{*}\varphi (u)).$

С помощью этих символов можно определить и другие символы языка принуждения: Например, $u=v$ означает $\neg (u\neq v)$, $\forall x\,\varphi (x)$ означает $\neg \exists x\,\neg \varphi (x)$и т. д. Случаи 1 и 2 зависят друг от друга и от случая 3, но рекурсия всегда ссылается на $\mathbb {P}$-имена с меньшими рангами , поэтому трансфинитная индукция позволяет пройти определение.

По конструкции, $\Vdash _{M,\mathbb {P} }^{*}$ (и таким образом $\Vdash _{M,\mathbb {P} }$) автоматически удовлетворяет определению . Доказательство того, что $\Vdash _{M,\mathbb {P} }^{*}$ также удовлетворяет Истине и Согласованности путем индуктивного изучения каждого из пяти вышеперечисленных случаев. Случаи 4 и 5 тривиальны (благодаря выбору $\vee$ и $\exists$ как элементарные символы ), случаи 1 и 2 основаны только на предположении, что $G$ является фильтром, и только случай 3 требует $G$ быть универсальным фильтром.

Формально внутреннее определение принуждающего отношения (например, представленное выше) на самом деле представляет собой преобразование произвольной формулы $\varphi (x_{1},\dots ,x_{n})$ к другой формуле $p\Vdash _{\mathbb {P} }\varphi (u_{1},\dots ,u_{n})$ где $p$ и $\mathbb {P}$ являются дополнительными переменными. Модель $M$ не появляется явно при преобразовании (обратите внимание, что внутри $M$, $u\in M^{(\mathbb {P} )}$ просто означает " $u$ это $\mathbb {P}$-имя"), и действительно, это преобразование можно воспринимать как "синтаксическое" определение принуждающего отношения во вселенной. $V$ всех множеств независимо от какой-либо счетной транзитивной модели. Однако если кто-то хочет применить некоторую счетную транзитивную модель $M$, то последнюю формулу следует интерпретировать как $M$ (т.е. со всеми кванторами, имеющими диапазон только более $M$), и в этом случае оно эквивалентно внешнему «семантическому» определению $\Vdash _{M,\mathbb {P} }$ описано в верхней части этого раздела:

Для любой формулы $\varphi (x_{1},\dots ,x_{n})$ есть теорема $T$ теории ${\mathsf {ZFC}}$ (например, объединение конечного числа аксиом) такое, что для любой счетной транзитивной модели $M$ такой, что $M\models T$ и любой безатомный частичный порядок $\mathbb {P} \in M$ и любой $\mathbb {P}$-общий фильтр $G$ над $M$ $$(\forall a_{1},\ldots ,a_{n}\in M^{\mathbb {P} })(\forall p\in \mathbb {P} )(p\Vdash _{M,\mathbb {P} }\varphi (a_{1},\dots ,a_{n})\,\Leftrightarrow \,M\models p\Vdash _{\mathbb {P} }\varphi (a_{1},\dots ,a_{n})).$$

В этом смысле отношение принуждения действительно «определимо в $M$".

Последовательность

Приведенное выше обсуждение можно резюмировать фундаментальным результатом согласованности, который, учитывая вынуждающее частичное множество $\mathbb {P}$, мы можем предположить существование общего фильтра $G$, не принадлежащий вселенной $V$, такой, что $V[G]$ снова является теоретико-множественной вселенной, которая моделирует ${\mathsf {ZFC}}$. Кроме того, все истины в $V[G]$ может быть сведено к истинам в $V$ включающее принуждающее отношение.

Оба стиля, соседствующие $G$ либо счетной транзитивной модели $M$ или вся вселенная $V$, обычно используются. Реже встречается подход, использующий «внутреннее» определение принуждения, в котором не упоминаются модели множеств или классов. Это был первоначальный метод Коэна, а в одной из его разработок он стал методом булевозначного анализа.

Коэн заставляет

Простейший нетривиальный принудительный ЧУМ — это $(\operatorname {Fin} (\omega ,2),\supseteq ,0)$, конечные частичные функции из $\omega$ к $2~{\stackrel {\text{df}}{=}}~\{0,1\}$ при обратном включении. То есть условие $p$ по существу представляет собой два непересекающихся конечных подмножества ${p^{-1}}[1]$ и ${p^{-1}}[0]$ из $\omega$, которые следует рассматривать как части «да» и «нет» $p$, без предоставления информации о значениях за пределами области $p$. " $q$ сильнее, чем $p$" означает, что $q\supseteq p$Другими словами, части «да» и «нет» $q$ являются надмножествами частей «да» и «нет». $p$и в этом смысле предоставить больше информации.

Позволять $G$ быть общим фильтром для этого частичного множества. Если $p$ и $q$ оба в $G$, затем $p\cup q$ это условие, потому что $G$ является фильтром. Это означает, что $g=\bigcup G$ является четко определенной частичной функцией из $\omega$ к $2$ потому что любые два условия в $G$ договориться об их общем достоянии.

Фактически, $g$ является полной функцией. Данный $n\in \omega$, позволять $D_{n}=\{p\mid p(n)~{\text{is defined}}\}$. Затем $D_{n}$ плотный. (При любом $p$, если $n$ не в $p$домен, добавьте значение для $n$— результат в $D_{n}$.) Условие $p\in G\cap D_{n}$ имеет $n$ в своей области, и поскольку $p\subseteq g$, мы находим это $g(n)$ определяется.

Позволять $X={g^{-1}}[1]$, набор всех «да» членов общих условий. Можно дать имя $X$ напрямую. Позволять

${\underline {X}}=\left\{\left({\check {n}},p\right)\mid p(n)=1\right\}.$

Затем $\operatorname {val} ({\underline {X}},G)=X.$ Теперь предположим, что $A\subseteq \omega$ в $V$. Мы утверждаем, что $X\neq A$. Позволять

$D_{A}=\{p\mid (\exists n)(n\in \operatorname {Dom} (p)\land (p(n)=1\iff n\notin A))\}.$

Затем $D_{A}$ плотный. (При любом $p$, находить $n$ которое не входит в его область действия, и примыкает к значению для $n$ вопреки статусу " $n\in A$".) Тогда любой $p\in G\cap D_{A}$ свидетели $X\neq A$. Подводя итог, $X$ представляет собой «новое» подмножество $\omega$, обязательно бесконечный.

Замена $\omega$ с $\omega \times \omega _{2}$, то есть вместо этого рассмотрим конечные частичные функции, входные данные которых имеют вид $(n,\alpha )$, с $n<\omega$ и $\alpha <\omega _{2}$, и чьи выходные данные $0$ или $1$, человек получает $\omega _{2}$ новые подмножества $\omega$. Все они различны с точки зрения плотности: если $\alpha <\beta <\omega _{2}$, позволять

$D_{\alpha ,\beta }=\{p\mid (\exists n)(p(n,\alpha )\neq p(n,\beta ))\},$

затем каждый $D_{\alpha ,\beta }$ плотно, и условие общего положения в нем доказывает, что α-е новое множество где-то не совпадает с $\beta$новый набор.

Это еще не фальсификация гипотезы континуума. Необходимо доказать, что не было введено никаких новых карт, отображение которых $\omega$ на $\omega _{1}$, или $\omega _{1}$ на $\omega _{2}$. Например, если вместо этого рассматривать $\operatorname {Fin} (\omega ,\omega _{1})$, конечные частичные функции из $\omega$ к $\omega _{1}$, первый неисчисляемый порядковый номер , в который попадает $V[G]$ биекция из $\omega$ к $\omega _{1}$. Другими словами, $\omega _{1}$ рухнул , и в принудительном расширении является счетным порядковым номером.

Таким образом, последний шаг в доказательстве независимости гипотезы континуума — это показать, что воздействие Коэна не приводит к коллапсу кардиналов. Для этого достаточным комбинаторным свойством является счетность всех антицепей форсирующего ЧУМ.

Условие счетной цепи

Основная статья: Состояние счетной цепи

( сильная ) антицепь $A$ из $\mathbb {P}$ является подмножеством таким, что если $p,q\in A$ и $p\neq q$, затем $p$ и $q$ несовместимы написано ( $p\perp q$), то есть нет $r$ в $\mathbb {P}$ такой, что $r\leq p$ и $r\leq q$. В примере с борелевскими множествами несовместимость означает, что $p\cap q$ имеет нулевую меру. В примере с конечными частичными функциями несовместимость означает, что $p\cup q$ не является функцией, другими словами, $p$ и $q$ присвойте разные значения некоторым входным данным домена.

$\mathbb {P}$ удовлетворяет условию счетной цепи (ccc) тогда и только тогда, когда каждая антицепь в $\mathbb {P}$ является счетным. (Название, которое явно неуместно, является пережитком старой терминологии. Некоторые математики пишут «cac» для «счетного условия антицепи».)

Это легко увидеть $\operatorname {Bor} (I)$ удовлетворяет CCC, поскольку в сумме меры составляют не более $1$. Также, $\operatorname {Fin} (E,2)$ удовлетворяет ccc, но доказательство сложнее.

Учитывая несчетное подсемейство $W\subseteq \operatorname {Fin} (E,2)$, сокращать $W$ к бесчисленному подсемейству $W_{0}$ комплектов размера $n$, для некоторых $n<\omega$. Если $p(e_{1})=b_{1}$ для бесчисленного множества $p\in W_{0}$, сократите это до неисчислимого подсемейства $W_{1}$ и повторяем, получая конечное множество $\{(e_{1},b_{1}),\ldots ,(e_{k},b_{k})\}$ и бесчисленная семья $W_{k}$ несовместимых условий размера $n-k$ такой, что каждый $e$ находится в $\operatorname {Dom} (p)$ не более чем счетного числа $p\in W_{k}$. Теперь выберите произвольный $p\in W_{k}$и выберите из $W_{k}$ любой $q$ это не один из счетного числа членов, имеющих общий член домена с $p$. Затем $p\cup \{(e_{1},b_{1}),\ldots ,(e_{k},b_{k})\}$ и $q\cup \{(e_{1},b_{1}),\ldots ,(e_{k},b_{k})\}$ совместимы, поэтому $W$ не является антицепью. Другими словами, $\operatorname {Fin} (E,2)$-антицепи счетны.

Важность антицепей в форсировании заключается в том, что для большинства целей плотные множества и максимальные антицепи эквивалентны. антицепь Максимальная ​ $A$ является такой, которая не может быть расширена до большей антицепи. Это означает, что каждый элемент $p\in \mathbb {P}$ совместим с каким-либо членом $A$. Существование максимальной антицепи следует из леммы Цорна . Учитывая максимальную антицепь $A$, позволять

$D=\left\{p\in \mathbb {P} \mid (\exists q\in A)(p\leq q)\right\}.$

Затем $D$ является плотным, и $G\cap D\neq \varnothing$ тогда и только тогда, когда $G\cap A\neq \varnothing$. И наоборот, если задано плотное множество $D$, лемма Цорна показывает, что существует максимальная антицепь $A\subseteq D$, а потом $G\cap D\neq \varnothing$ тогда и только тогда, когда $G\cap A\neq \varnothing$.

Предположим, что $\mathbb {P}$ соответствует требованиям CCC. $x,y\in V$, с $f:x\to y$ функция в $V[G]$, можно приблизить $f$ внутри $V$ следующее. Позволять $u$ быть именем для $f$ (по определению $V[G]$) и пусть $p$ быть состоянием, которое заставляет $u$ быть функцией от $x$ к $y$. Определить функцию $F:x\to {\mathcal {P}}(y)$, к

$F(a){\stackrel {\text{df}}{=}}\left\{b\left|(\exists q\in \mathbb {P} )\left[(q\leq p)\land \left(q\Vdash ~u\left({\check {a}}\right)={\check {b}}\right)\right]\right\}.\right.$

Учитывая возможность определения принуждения, это определение имеет смысл в рамках $V$. По согласованности принуждения, другое $b$ происходят из несовместимого $p$. По КСС, $F(a)$ является счетным.

В итоге, $f$ неизвестно в $V$ как это зависит от $G$, но это не редкость для форсирования ccc. Можно определить счетный набор предположений о том, каково значение $f$ находится на любом входе, независимо от $G$.

Это имеет следующее очень важное следствие. Если в $V[G]$, $f:\alpha \to \beta$ является сюръекцией одного бесконечного ординала на другой, то существует сюръекция $g:\omega \times \alpha \to \beta$ в $V$, и, следовательно, сюръекция $h:\alpha \to \beta$ в $V$. В частности, кардиналы не могут рухнуть. Вывод заключается в том, что $2^{\aleph _{0}}\geq \aleph _{2}$ в $V[G]$.

Истон форсирует

Точное значение континуума в приведенной выше модели Коэна и таких вариантах, как $\operatorname {Fin} (\omega \times \kappa ,2)$ для кардиналов $\kappa$ в общем, был разработан Робертом М. Соловеем , который также придумал, как нарушить ${\mathsf {GCH}}$ ( обобщенная гипотеза континуума ), только для регулярных кардиналов , конечное число раз. Например, в приведенной выше модели Коэна, если ${\mathsf {CH}}$ держится $V$, затем $2^{\aleph _{0}}=\aleph _{2}$ держится $V[G]$.

Уильям Б. Истон разработал правильную классовую версию нарушения ${\mathsf {GCH}}$ для обычных кардиналов, по сути показывая, что известные ограничения (монотонность, теорема Кантора и теорема Кенига ) были единственными ${\mathsf {ZFC}}$-доказуемые ограничения (см. теорему Истона ).

Работа Истона примечательна тем, что она включала принуждение к соответствующему классу условий. В общем, метод воздействия с соответствующим классом условий не может дать модель ${\mathsf {ZFC}}$. Например, принуждение с помощью $\operatorname {Fin} (\omega \times \mathbf {On} ,2)$, где $\mathbf {On}$ является надлежащим классом всех ординалов, делает континуум собственным классом. С другой стороны, принуждение с $\operatorname {Fin} (\omega ,\mathbf {On} )$ вводит счетное перечисление ординалов. В обоих случаях в результате $V[G]$ явно не является образцом ${\mathsf {ZFC}}$.

Одно время считалось, что более сложное принуждение также позволит произвольно изменять полномочия отдельных кардиналов . Однако это оказалась трудная, тонкая и даже удивительная проблема, и можно доказать еще несколько ограничений. в ней ${\mathsf {ZFC}}$ и с моделями воздействия, зависящими от согласованности различных свойств большой мощности . Остается много открытых проблем.

Случайные числа

Основная статья: Случайная алгебра

Случайное воздействие можно определить как воздействие на множество $P$ всех компактных подмножеств $[0,1]$ положительной меры, упорядоченной соотношением $\subseteq$ (меньший набор в контексте включения означает меньший набор в порядке упорядочения и представляет состояние с большим количеством информации). Есть два типа важных плотных множеств:

1. Для любого положительного целого числа $n$ набор $$D_{n}=\left\{p\in P:\operatorname {diam} (p)<{\frac {1}{n}}\right\}$$ плотный, где $\operatorname {diam} (p)$ диаметр набора $p$.
2. Для любого подмножества Бореля $B\subseteq [0,1]$ меры 1 множество $$D_{B}=\{p\in P:p\subseteq B\}$$ плотный.

Для любого фильтра $G$ и для любого конечного числа элементов $p_{1},\ldots ,p_{n}\in G$ есть $q\in G$ такой, который держит $q\leq p_{1},\ldots ,p_{n}$. В случае такого порядка это означает, что любой фильтр представляет собой набор компактов с конечным свойством пересечения. По этой причине пересечение всех элементов любого фильтра непусто. Если $G$ — фильтр, пересекающий плотное множество $D_{n}$ для любого положительного целого числа $n$, то фильтр $G$ содержит условия сколь угодно малого положительного диаметра. Поэтому пересечение всех условий из $G$ имеет диаметр 0. Но единственными непустыми множествами диаметра 0 являются одиночки. Значит, существует ровно одно действительное число $r_{G}$ такой, что $r_{G}\in \bigcap G$.

Позволять $B\subseteq [0,1]$ — любое борелевское множество меры 1. Если $G$ пересекает $D_{B}$, затем $r_{G}\in B$.

Однако общий фильтр по счетной транзитивной модели $V$ не в $V$. Настоящий $r_{G}$ определяется $G$ доказуемо не является элементом $V$. Проблема в том, что если $p\in P$, затем $V\models$ " $p$ компактен», но с точки зрения некоторой большей вселенной $U\supset V$, $p$ может быть некомпактным и пересечением всех условий из общего фильтра $G$ на самом деле пуст. По этой причине мы рассматриваем множество $C=\{{\bar {p}}:p\in G\}$ топологических замыканий условий из G (т.е. ${\bar {p}}=p\cup \{\inf(p)\}\cup \{\sup(p)\}$). Из-за ${\bar {p}}\supseteq p$ и свойство конечного пересечения $G$, набор $C$ также обладает свойством конечного пересечения. Элементы набора $C$ являются ограниченными замкнутыми множествами как замыкания ограниченных множеств. Поэтому, $C$ представляет собой набор компактов со свойством конечного пересечения и, следовательно, имеет непустое пересечение. С $\operatorname {diam} ({\bar {p}})=\operatorname {diam} (p)$ и наземная модель $V$ наследует метрику из вселенной $U$, набор $C$ имеет элементы сколь угодно малого диаметра. Наконец, существует ровно одно вещественное число, принадлежащее всем членам множества. $C$. Общий фильтр $G$ можно реконструировать из $r_{G}$ как $G=\{p\in P:r_{G}\in {\bar {p}}\}$.

Если $a$ это имя $r_{G}$, и для $B\in V$ держит $V\models$" $B$ является борелевским множеством меры 1", то имеет место

$V[G]\models \left(p\Vdash _{\mathbb {P} }a\in {\check {B}}\right)$

для некоторых $p\in G$. Есть имя $a$ такой, что для любого общего фильтра $G$ держит

$\operatorname {val} (a,G)\in \bigcup _{p\in G}{\bar {p}}.$

Затем

$V[G]\models \left(p\Vdash _{\mathbb {P} }a\in {\check {B}}\right)$

сохраняется при любых условиях $p$.

Каждое борелевское множество может быть построено неоднозначно, начиная с интервалов с рациональными концами и применяя операции дополнения и счетных объединений счетное количество раз. Запись такой конструкции называется борелевским кодом . Учитывая множество Бореля $B$ в $V$, восстанавливается борелевский код, а затем применяется та же последовательность построения в $V[G]$, получая набор Бореля $B^{*}$. Можно доказать, что мы получаем одно и то же множество независимо от построения $B$, и что основные свойства сохраняются. Например, если $B\subseteq C$, затем $B^{*}\subseteq C^{*}$. Если $B$ имеет нулевую меру, то $B^{*}$ имеет меру ноль. Это отображение $B\mapsto B^{*}$ является инъективным.

Для любого набора $B\subseteq [0,1]$ такой, что $B\in V$ и $V\models$" $B$ является борелевским множеством меры 1" $r\in B^{*}$.

Это означает, что $r$ это «бесконечная случайная последовательность нулей и единиц» с точки зрения $V$, что означает, что он удовлетворяет всем статистическим тестам наземной модели. $V$.

Так что учитывая $r$, случайная действительность, можно показать, что

$G=\left\{B~({\text{in }}V)\mid r\in B^{*}~({\text{in }}V[G])\right\}.$

Из-за взаимной взаимоопределяемости между $r$ и $G$, обычно пишут $V[r]$ для $V[G]$.

Иная интерпретация действительности в $V[G]$ было предоставлено Даной Скотт . Рациональные числа в $V[G]$ имеют имена, соответствующие счетному множеству различных рациональных значений, присвоенных максимальной антицепи борелевских множеств – другими словами, некоторой рациональной функции на $I=[0,1]$. Реальные числа в $V[G]$ тогда соответствуют дедекиндовым сечениям таких функций, т. е. измеримым функциям .

Логические модели

Основная статья: Логическая модель

Возможно, более понятно, что этот метод можно объяснить с точки зрения булевых моделей. В них любому утверждению присваивается значение истинности из некоторой полной безатомной булевой алгебры , а не просто значение «истина/ложь». Затем в этой булевой алгебре выбирается ультрафильтр , который присваивает значения true/false утверждениям нашей теории. Дело в том, что полученная теория имеет модель, содержащую этот ультрафильтр, под которой можно понимать новую модель, полученную расширением старой с помощью этого ультрафильтра. Подходящим образом выбрав модель с логическим значением, мы можем получить модель, обладающую желаемым свойством. В нем только утверждения, которые должны быть истинными (которые «вынуждены» быть истинными), будут в некотором смысле истинными (поскольку они обладают свойством расширения/минимальности).

Метаматематическое объяснение

Принуждая, мы обычно стремимся показать, что какое предложение соответствует - то ${\mathsf {ZFC}}$ (или, опционально, какое-то расширение ${\mathsf {ZFC}}$). Один из способов интерпретировать этот аргумент состоит в том, чтобы предположить, что ${\mathsf {ZFC}}$ непротиворечиво, а затем докажите, что ${\mathsf {ZFC}}$ в сочетании с новым предложением также соответствует.

Каждое «условие» представляет собой конечный фрагмент информации. Идея состоит в том, что только конечные фрагменты имеют значение для непротиворечивости, поскольку по теореме о компактности теория выполнима тогда и только тогда, когда выполнимо каждое конечное подмножество ее аксиом. Тогда мы сможем выбрать бесконечный набор непротиворечивых условий, чтобы расширить нашу модель. Поэтому, предполагая согласованность ${\mathsf {ZFC}}$, докажем состоятельность ${\mathsf {ZFC}}$ расширенное этим бесконечным множеством.

Логическое объяснение

По второй теореме Гёделя о неполноте невозможно доказать непротиворечивость какой-либо достаточно сильной формальной теории, такой как ${\mathsf {ZFC}}$, используя только аксиомы самой теории, если теория не противоречива. Следовательно, математики не пытаются доказать непротиворечивость ${\mathsf {ZFC}}$ используя только аксиомы ${\mathsf {ZFC}}$или доказать, что ${\mathsf {ZFC}}+H$ является непротиворечивым для любой гипотезы $H$ используя только ${\mathsf {ZFC}}+H$. По этой причине цель доказательства непротиворечивости состоит в том, чтобы доказать непротиворечивость ${\mathsf {ZFC}}+H$ относительно консистенции ${\mathsf {ZFC}}$. Такие проблемы известны как проблемы относительной непротиворечивости , одна из которых доказывает

$${\mathsf {ZFC}}\vdash \operatorname {Con} ({\mathsf {ZFC}})\rightarrow \operatorname {Con} ({\mathsf {ZFC}}+H).$$ ( ⁎ )

Общая схема доказательств относительной непротиворечивости следующая. Поскольку любое доказательство конечно, оно использует только конечное число аксиом:

${\mathsf {ZFC}}+\lnot \operatorname {Con} ({\mathsf {ZFC}}+H)\vdash (\exists T)(\operatorname {Fin} (T)\land T\subseteq {\mathsf {ZFC}}\land (T\vdash \lnot H)).$

Для любого данного доказательства ${\mathsf {ZFC}}$ может убедиться в справедливости этого доказательства. Это доказывается индукцией по длине доказательства.

${\mathsf {ZFC}}\vdash (\forall T)((T\vdash \lnot H)\rightarrow ({\mathsf {ZFC}}\vdash (T\vdash \lnot H))).$

Затем решите

${\mathsf {ZFC}}+\lnot \operatorname {Con} ({\mathsf {ZFC}}+H)\vdash (\exists T)(\operatorname {Fin} (T)\land T\subseteq {\mathsf {ZFC}}\land ({\mathsf {ZFC}}\vdash (T\vdash \lnot H))).$

Доказав следующее

$${\mathsf {ZFC}}\vdash (\forall T)(\operatorname {Fin} (T)\land T\subseteq {\mathsf {ZFC}}\rightarrow ({\mathsf {ZFC}}\vdash \operatorname {Con} (T+H))),$$ ( ⁎⁎ )

можно сделать вывод, что

${\mathsf {ZFC}}+\lnot \operatorname {Con} ({\mathsf {ZFC}}+H)\vdash (\exists T)(\operatorname {Fin} (T)\land T\subseteq {\mathsf {ZFC}}\land ({\mathsf {ZFC}}\vdash (T\vdash \lnot H))\land ({\mathsf {ZFC}}\vdash \operatorname {Con} (T+H))),$

что эквивалентно

${\mathsf {ZFC}}+\lnot \operatorname {Con} ({\mathsf {ZFC}}+H)\vdash \lnot \operatorname {Con} ({\mathsf {ZFC}}),$

что дает (*). Суть доказательства относительной непротиворечивости — доказательство (**). А ${\mathsf {ZFC}}$ доказательство $\operatorname {Con} (T+H)$ может быть построено для любого заданного конечного подмножества $T$ принадлежащий ${\mathsf {ZFC}}$ аксиомы (по ${\mathsf {ZFC}}$ инструменты, конечно). (Нет универсального доказательства $\operatorname {Con} (T+H)$ конечно.)

В ${\mathsf {ZFC}}$, доказывается, что для любого условия $p$, набор формул (оцениваемых по именам), заданных $p$ является дедуктивно замкнутым. Более того, для любого ${\mathsf {ZFC}}$ аксиома, ${\mathsf {ZFC}}$ доказывает, что эта аксиома вытекает из $\mathbf {1}$. Тогда достаточно доказать, что существует хотя бы одно условие, которое заставляет $H$.

В случае булевого форсирования процедура аналогична: доказывается, что логическое значение $H$ не $\mathbf {0}$.

Другой подход использует теорему отражения. Для любого заданного конечного множества ${\mathsf {ZFC}}$ аксиомы, существует ${\mathsf {ZFC}}$ доказательство того, что этот набор аксиом имеет счетную транзитивную модель. Для любого заданного конечного множества $T$ из ${\mathsf {ZFC}}$ аксиом, существует конечное множество $T'$ из ${\mathsf {ZFC}}$ аксиомы такие, что ${\mathsf {ZFC}}$ доказывает, что если счетная транзитивная модель $M$ удовлетворяет $T'$, затем $M[G]$ удовлетворяет $T$. Доказав, что существует конечное множество $T''$ из ${\mathsf {ZFC}}$ аксиомы такие, что если счетная транзитивная модель $M$ удовлетворяет $T''$, затем $M[G]$ удовлетворяет гипотезе $H$. Тогда для любого заданного конечного множества $T$ из ${\mathsf {ZFC}}$ аксиомы, ${\mathsf {ZFC}}$ доказывает $\operatorname {Con} (T+H)$.

Иногда в (**) более сильная теория $S$ чем ${\mathsf {ZFC}}$ используется для доказательства $\operatorname {Con} (T+H)$. Тогда у нас есть доказательство непротиворечивости ${\mathsf {ZFC}}+H$ относительно консистенции $S$. Обратите внимание, что ${\mathsf {ZFC}}\vdash \operatorname {Con} ({\mathsf {ZFC}})\leftrightarrow \operatorname {Con} ({\mathsf {ZFL}})$, где ${\mathsf {ZFL}}$ является ${\mathsf {ZF}}+V=L$ (аксиома конструктивности).

См. также

• Список принудительных понятий
• Красивое имя

Ссылки

• Белл, Джон Лейн (1985). Булевозначные модели и доказательства независимости в теории множеств . Оксфорд: Издательство Оксфордского университета . ISBN  9780198532415 .
• Коэн, Пол Джозеф (2008) [1966]. Теория множеств и гипотеза континуума . Минеола, Нью-Йорк: Dover Publications. п. 151. ИСБН  978-0-486-46921-8 .
• Гришин, В.Н. (2001) [1994], «Метод принуждения» , Энциклопедия Математики , EMS Press
• Я, Томас Дж. (2013) [1978]. Теория множеств: издание третьего тысячелетия . Спрингер Верлаг . ISBN  9783642078996 .
• Кунен, Кеннет (1980). Теория множеств: введение в доказательства независимости . Издательская компания Северной Голландии . ISBN  978-0-444-85401-8 .
• Шенфилд, младший (1971). «Неразветвленное принуждение». Аксиоматическая теория множеств . Учеб. Симпозиумы. Чистая математика. Том. XIII, Часть I. Провиденс, Род-Айленд: Амер. Математика. Соц. стр. 357–381. МР   0280359 .

Библиография

• Чоу, Тимоти (2008). «Руководство по форсированию для начинающих». arXiv : 0712.1320v2 . Хорошее введение в концепции форсирования, избегающее множества технических подробностей. Он включает раздел, посвященный булевым моделям.
• Коэн, Пол Джозеф (декабрь 1963 г.). «Независимость гипотезы континуума» . Труды Национальной академии наук Соединенных Штатов Америки . 50 (6): 1143–1148. Бибкод : 1963PNAS...50.1143C . дои : 10.1073/pnas.50.6.1143 . ПМК   221287 . ПМИД   16578557 .
• Коэн, Пол Джозеф (январь 1964 г.). «Независимость гипотезы континуума, II» . Труды Национальной академии наук Соединенных Штатов Америки . 51 (1): 105–110. Бибкод : 1964PNAS...51..105C . дои : 10.1073/pnas.51.1.105 . ПМК   300611 . ПМИД   16591132 .
• Коэн, Пол Джозеф (2002). «Открытие принуждения» . Роки Маунтин Дж. Математика . 32 (4): 1071–1100. дои : 10.1216/rmjm/1181070010 . Историческая лекция о том, как он разработал свое доказательство независимости.
• Иасваран, Кенни (2007). «Веселое введение в принуждение и гипотезу континуума». arXiv : 0712.2279 [ math.LO ]. Статья также предназначена для новичков, но содержит больше технических подробностей, чем статья Чоу (2008).
• Гюнтер, Эммануэль; Пэган, Майкл; Санчес Терраф, Питер; Стейнберг, Матиас (май 2020 г.). «Формализация принуждения в Изабель/ZF » формальных доказательств Архив arXiv : 2001.09715 . Получено 20 августа.
• Канамори, Акихиро (2007). «Теория множеств от Кантора до Коэна» (PDF) .
• Уивер, Ник (2014). Форсинг для математиков . Всемирная научная издательская компания с. 153. дои : 10.1142/8962 . ISBN  978-9814566001 . Написано для математиков, желающих изучить основные механизмы воздействия. Никакого опыта в логике не предполагается, за исключением владения формальным синтаксисом, которое должно быть второй натурой любого хорошо подготовленного математика.
• Вайсштейн, Эрик В. «Принуждение» . Математический мир .