Введение

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

В математической дисциплине теории множеств форсирование является методом доказательства результатов о непротиворечивости и независимости. Интуитивно, форсирование можно представить как метод расширения теоретической вселенной множеств до большей вселенной путем введения нового "общего" объекта.

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

Интуиция

Принуждение обычно используется для построения расширенной вселенной, удовлетворяющей некоторым желаемым свойствам. Например, расширенная вселенная может содержать множество новых вещественных чисел (по крайней мере, континуум из них), отождествляемых с подмножествами множества натуральных чисел, которых не было в старой вселенной, и тем самым нарушать гипотезу континуума. Чтобы интуитивно обосновать такое расширение, лучше всего рассматривать «старую вселенную» как модель теории множеств, которая сама по себе является множеством в «реальной вселенной». По теореме Лёвенхайма — Сколема, можно выбрать модель «минимального набора», которая является внешне счётной, что гарантирует существование множества подмножеств (в ) из , которых нет в . В частности, существует ординал, который «играет роль кардинала » в , но на самом деле счётен в . Работая в , должно быть легко найти одно отличное подмножество для каждого элемента (для простоты это семейство подмножеств можно охарактеризовать одним подмножеством). Однако в некотором смысле желательно «построить расширенную модель внутри ». Это поможет обеспечить, чтобы «похожа» на в определенных аспектах, например, чтобы была такой же, как (в более общем смысле, чтобы не происходило кардинального коллапса), и позволит точно контролировать свойства . В частности, каждому элементу из должно быть дано (не единственное) имя в . Имя можно рассматривать как выражение в терминах , как и в простом расширении поля, где каждый элемент можно выразить в терминах . Важным компонентом принуждения является манипулирование этими именами внутри , поэтому иногда может быть полезно напрямую рассматривать как «вселенную», зная, что теория принуждения гарантирует, что будет соответствовать фактической модели. Тонкий момент принуждения заключается в том, что если принять за произвольное «отсутствующее подмножество» некоторого множества в , то построенная «внутри » может даже не быть моделью. Это связано с тем, что может кодировать «специальную» информацию о , которая не видна внутри (например, счётность ), и таким образом доказывать существование множеств, которые «слишком сложны для описания ». Принуждение позволяет избежать таких проблем, требуя, чтобы вновь введенное множество было генерическим множеством относительно . Некоторые утверждения «вынуждены» выполняться для любого генерического : например, генерическое «вынуждено» быть бесконечным. Кроме того, любое свойство (описываемое в ) генерического множества «вынуждено» выполняться при определенных условиях принуждения. Понятие «принуждение» можно определить внутри , и оно дает достаточно сил для рассуждений, чтобы доказать, что действительно является моделью, удовлетворяющей желаемым свойствам. Оригинальная техника Коэна, теперь называемая разветвленным принуждением, немного отличается от неразветвленного принуждения, изложенного здесь. Принуждение также эквивалентно методу булевозначных моделей, который, по мнению некоторых, концептуально более естественен и интуитивно понятен, но обычно гораздо сложнее применить.

Роль модели

Для того чтобы вышеуказанный подход работал корректно, необходимо, чтобы действительно была стандартной транзитивной моделью в , чтобы членство и другие элементарные понятия могли быть обработаны интуитивно как в , так и в . Стандартная транзитивная модель может быть получена из любой стандартной модели посредством леммы коллапса Мостовского, однако существование любой стандартной модели (или любого её варианта) само по себе является более сильным предположением, чем согласованность . Чтобы обойти эту проблему, стандартной техникой является принятие за стандартную транзитивную модель произвольного конечного подмножества (любая аксиоматизация имеет как минимум одну аксиоматическую схему и, следовательно, бесконечное число аксиом), существование которой гарантируется принципом отражения. Поскольку целью построения принуждения является доказательство результатов о согласованности, этого достаточно, так как любое противоречие в теории должно проявиться в виде вывода конечной длины и, следовательно, задействовать лишь конечное число аксиом.

Форсирующие условия и форсирующие позиты

Каждое условие принуждения можно рассматривать как конечный фрагмент информации об объекте, присоединяемом к модели. Существует множество различных способов предоставления информации об объекте, что порождает различные понятия принуждения. Общий подход к формализации понятий принуждения заключается в рассмотрении условий принуждения как абстрактных объектов с позитной структурой. Форсирующий посет – это упорядоенная тройка (P, ≤, 1), где ≤ – предзаказ на P, а 1 – наибольший элемент. Элементами P являются условия принуждения (или просто условия). Отношение порядка ≤ означает "сильнее, чем". (Интуитивно, "меньшее" условие предоставляет "больше" информации, так же как меньший интервал предоставляет больше информации о числе, чем больший интервал.) Кроме того, предзаказ должен быть без атомов, то есть удовлетворять условию расщепления:

Для каждого p ∈ P существуют q, r ∈ P такие, что p ≤ q и p ≤ r, при этом не существует s ∈ P такого, что q ≤ s ≤ r.

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

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

Примеры

Пусть – любое бесконечное множество (например, ), и пусть рассматриваемый общий объект будет новым подмножеством. В оригинальной формулировке Коэна принуждения каждое принуждающее условие является конечным множеством предложений, либо вида либо , которые самосогласованы (т.е. и для одного и того же значения не встречаются в одном и том же условии). Это понятие принуждения обычно называется принуждением Коэна. Принуждающее множество для принуждения Коэна может быть формально записано как , то есть конечные частичные функции из в с обратным включением. Принуждение Коэна удовлетворяет условию расщепления, поскольку для любого условия всегда можно найти элемент, не упомянутый в , и добавить либо предложение либо к , чтобы получить два новых принуждающих условия, несовместимых друг с другом. Другим поучительным примером принуждающего множества является , где и – это коллекция подмножеств Бореля множества с ненулевой мерой Лебега. Общий объект, связанный с этим принуждающим множеством, – это случайное вещественное число. Можно показать, что оно попадает в каждое подмножество Бореля множества с мерой 1, при условии, что подмножество Бореля "описано" в исходной нерасширенной вселенной (это можно формализовать с помощью понятия кодов Бореля). Каждое принуждающее условие можно рассматривать как случайное событие с вероятностью, равной его мере. Благодаря интуитивности этого примера, вероятностный язык иногда используется и с другими дивергентными принуждающими множествами.

Принуждение

При заданном общем фильтре, рассуждают следующим образом. Подкласс имен в обозначается Let. Чтобы свести изучение теории множеств к теории множеств , используют "язык принуждения", который строится как обычная логика первого порядка, с отношением принадлежности в качестве бинарного отношения и всеми именами в качестве констант. Определим (читается как "принуждает в модели с poset"), где – условие, – формула на языке принуждения, а – имена, чтобы означать, что если – общий фильтр, содержащий , то. Частный случай часто записывается как "" или просто "". Такие утверждения истинны в , независимо от значения . Важно, что это внешнее определение отношения принуждения эквивалентно внутреннему определению внутри , заданному трансфинитной индукцией (в частности, -индукцией) по именам на экземплярах и , а затем обычной индукцией по сложности формул. Это приводит к тому, что все свойства на самом деле являются свойствами , а проверка в становится прямой. Обычно это суммируется следующими тремя ключевыми свойствами: Истинность: если и только если оно принуждено , то есть для некоторого условия , у нас есть Определимость: Утверждение "" определимо в Согласованность: .

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

Вышеприведенное обсуждение можно суммировать фундаментальным результатом о согласованности: для заданного форсирующего позита мы можем предположить существование общего фильтра, не принадлежащего вселенной, такого что является снова теоретико-множественной вселенной, моделирующей . Более того, все истины в могут быть сведены к истинам в , включающим форсировочное отношение. Оба подхода – присоединение к счетной транзитивной модели или ко всей вселенной – обычно используются. Реже встречается подход, использующий "внутреннее" определение форсирования, в котором не делается упоминаний о моделях множеств или классов. Это был оригинальный метод Коэна, и в одной из его разработок он превращается в метод булевозначного анализа.

Коэн принуждает

Самый простой нетривиальный форсирующий набор – это , конечные частичные функции из в под обратным включением. То есть, условие по существу представляет собой два непересекающихся конечных подмножества и из , которые следует рассматривать как части "да" и "нет" , без предоставления информации о значениях за пределами области определения. "Условие сильнее, чем " означает, что , другими словами, части "да" и "нет" являются надмножествами частей "да" и "нет" , и в этом смысле предоставляют больше информации. Пусть – общий фильтр для этого poset. Если и оба принадлежат , то является условием, поскольку – фильтр. Это означает, что – хорошо определенная частичная функция из в , потому что любые два условия согласуются в их общей области определения. Фактически, – функция общего числа. Пусть тогда плотен. (Для любого , если не принадлежит области определения , добавьте значение для – результат будет принадлежать .) Условие имеет в своей области определения, и поскольку , мы находим, что определено. Пусть , множество всех элементов, которым присвоено значение "да" в общих условиях. Можно дать имя непосредственно. Пусть

Тогда . Теперь предположим, что принадлежит . Мы утверждаем, что . Пусть

Тогда плотен. (Для любого , найдите , который не принадлежит его области определения, и добавьте значение для , противоположное значению "".) Тогда любое подтверждает. Чтобы суммировать, – "новое" подмножество , обязательно бесконечное. Заменяя на , то есть, рассматривая вместо этого конечные частичные функции, входные данные которых имеют вид , где и , а выходные данные – или , мы получаем новых подмножеств . Они все различны, согласно аргументу о плотности: для любого , пусть

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

Состояние считываемой цепи

(Сильная) антицепочка в – это подмножество, такое, что если и , то и несовместимы (обозначается ), то есть не существует такого , что и . В примере с борелевскими множествами несовместимость означает, что имеет нулевую меру. В примере с конечными частичными функциями несовместимость означает, что не является функцией, другими словами, и присваивают разные значения одному и тому же элементу из области определения. удовлетворяет условию счётной цепи (c. c. c.), если и только если каждая антицепочка в счётна. (Название, очевидно неудачное, является пережитком старой терминологии. Некоторые математики пишут "c. a. c." для "условия счётной антицепи".) Легко видеть, что удовлетворяет c. c. c., поскольку меры в сумме дают не более . Также удовлетворяет c. c. c., но доказательство сложнее. Пусть дана несчётная подсемья , сузим её до несчётной подсемьи множеств размера , для некоторого . Если для несчётного числа , сузим это до несчётной подсемьи и повторим, получив конечное множество и несчётную семью несовместимых условий размера , таких что каждый принадлежит не более чем счётном числе раз. Теперь выберем произвольный , и выберем из любой , который не является одним из счётного числа элементов, имеющих общий элемент области определения с . Тогда и совместимы, следовательно, не является антицепочкой. Иными словами, антицепочки счётны. Важность антицепочек в форсировании заключается в том, что для большинства целей плотные множества и максимальные антицепочки эквивалентны. Максимальная антицепочка – это такая, которую нельзя расширить до большей антицепочки. Это означает, что каждый элемент совместим с некоторым элементом из . Существование максимальной антицепочки следует из леммы Зорна. Пусть дана максимальная антицепочка , тогда плотна, и если и только если . И наоборот, пусть дано плотное множество , лемма Зорна показывает, что существует максимальная антицепочка , и тогда если и только если . Предположим, что удовлетворяет c. c. c. Пусть – имя для (по определению ) и – условие, которое форсирует быть функцией из в . Определим функцию , по формуле

По определимости форсирования, это определение имеет смысл в . По согласованности форсирования, разные происходят из несовместимых . По c. c. c., счётна. В итоге, неизвестно в , поскольку это зависит от , но это не слишком неизвестно для форсирования с c. c. c. Можно определить счётное множество предположений о том, чему равно значение в любой точке, независимо от . Это имеет следующее очень важное следствие. Если в , – сюръекция с одного бесконечного ординала на другой, то существует сюръекция в , и, следовательно, сюръекция в . В частности, кардиналы не могут коллапсировать. Следовательно, в .

Форсировка Истона

Точное значение континуума в вышеуказанной модели Коэна и варианты для кардиналов в целом были установлены Робертом М. Соловаем, который также разработал способ нарушения (обобщенной гипотезы континуума) лишь конечное число раз, и только для регулярных кардиналов. Например, в вышеуказанной модели Коэна, если выполняется в , то выполняется в . Уильям Б. Истон разработал версию нарушения для регулярных кардиналов, основанную на правильном классе, по сути показав, что известные ограничения (монотонность, теорема Кантора и теорема Кёнига) являются единственными доказуемыми ограничениями (см. теорему Истона). Работа Истона была примечательна тем, что в ней использовалось форсирование с правильным классом условий. В общем случае, метод форсирования с использованием правильного класса условий не позволяет построить модель . Например, форсирование с , где – правильный класс всех ординалов, делает континуум правильным классом. С другой стороны, форсирование с вводит счетное перечисление ординалов. В обоих случаях, полученное очевидно не является моделью . В свое время считалось, что более сложное форсирование позволит произвольное изменение степеней сингулярных кардиналов. Однако это оказалось сложной, тонкой и даже неожиданной проблемой, с несколькими дополнительными доказуемыми ограничениями и с форсирующими моделями, зависящими от непротиворечивости различных свойств больших кардиналов. Многие вопросы остаются открытыми.

Модели с булевой величиной

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

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

При принуждении мы обычно стремимся показать, что некоторое предложение согласуется с (или, опционально, с некоторым расширением). Один из способов интерпретации аргумента – предположить, что согласовано, а затем доказать, что вместе с новым предложением также согласовано. Каждое "условие" представляет собой конечный фрагмент информации – идея состоит в том, что для согласованности релевантны только конечные фрагменты, поскольку, согласно теореме о компактности, теория выполнима тогда и только тогда, когда каждый конечный подмножество её аксиом выполнимо. Затем мы можем выбрать бесконечное множество согласованных условий для расширения нашей модели. Следовательно, предполагая согласованность , мы доказываем согласованность расширенного этим бесконечным множеством.