Форсинг (вычислимость)

Эта статья требует внимания эксперта по математике или логике . Конкретная проблема: статья неполная. WikiProject Mathematics  или WikiProject Logic могут помочь нанять эксперта. ( Апрель 2021 )

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

Концептуально эти два метода довольно похожи: в обоих методах одна пытается построить общие объекты (интуитивно объекты, которые каким-то образом «типичны»), встречая плотные множества . Оба метода описываются как отношение (обычно обозначаемое ) между «условиями» и предложениями. Однако, в то время как теоретико-множественное принуждение обычно заинтересовано в создании объектов, которые удовлетворяют каждому плотному множеству условий в базовой модели, теоретико-вычислимое принуждение нацелено только на удовлетворение плотных множеств, которые являются арифметически или гиперарифметически определимыми. Следовательно, некоторые из более сложных механизмов, используемых в теоретико-множественном принуждении, могут быть устранены или существенно упрощены при определении принуждения в вычислимости. Но хотя механизмы могут несколько отличаться, теоретико-вычислимое и теоретико-множественное принуждение правильно рассматривать как применение одного и того же метода к разным классам формул.${\displaystyle \Vdash}$

В данной статье мы используем следующую терминологию.

настоящий

элемент . Другими словами, функция, которая сопоставляет каждое целое число либо с 0, либо с 1.${\displaystyle 2^{\омега}}$

нить

элемент . Другими словами, конечное приближение к вещественному.${\displaystyle 2^{<\омега}}$

понятие принуждения

Понятие принуждения представляет собой множество и частичный порядок на с наибольшим элементом .${\displaystyle P}$${\displaystyle P}$${\displaystyle \succ _{P}}$ ${\displaystyle 0_{P}}$

состояние

Элемент в понятии принуждения. Мы говорим, что условие сильнее условия, только когда .${\displaystyle p}$${\displaystyle д}$${\displaystyle q\succ _{P}p}$

совместимые условия

При данных условиях утверждается, что и совместимы, если существует условие, при котором относительно и могут быть одновременно удовлетворены, если они истинны или могут сосуществовать.${\displaystyle p,q}$${\displaystyle p}$${\displaystyle д}$${\displaystyle r}$${\displaystyle r}$${\displaystyle p}$${\displaystyle д}$

${\displaystyle p\mid q}$

средства и несовместимы.${\displaystyle p}$${\displaystyle д}$

Фильтр

Подмножество понятия принуждения является фильтром, если , и . Другими словами, фильтр является совместимым набором условий, замкнутым относительно ослабления условий.${\displaystyle F}$${\displaystyle P}$${\displaystyle p,q\in F\implies p\nmid q}$${\displaystyle p\in F\land q\succ _{P}p\implies q\in F}$

Ультрафильтр

Максимальный фильтр, т.е. является ультрафильтром, если является фильтром и не существует фильтра, надлежащим образом содержащего .${\displaystyle F}$${\displaystyle F}$${\displaystyle F'}$${\displaystyle F}$

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

Понятие принуждения , где условия являются элементами и )${\displaystyle С}$${\displaystyle 2^{<\омега}}$${\displaystyle (\tau \succ _{C}\sigma \если \sigma \supset \tau }$

Обратите внимание, что для Коэна принуждение является обратным отношению включения. Это приводит к досадной путанице в обозначениях, когда некоторые теоретики вычислимости меняют направление частичного порядка принуждения (заменяя на , что более естественно для принуждения Коэна, но противоречит обозначениям, используемым в теории множеств).${\displaystyle \succ_{C}}$${\displaystyle \succ _{P}}$${\displaystyle \prec_{P}}$

Интуиция, стоящая за принуждением, заключается в том, что наши условия являются конечными приближениями к некоторому объекту, который мы хотим построить, и это сильнее, чем когда согласуется со всем, что говорит об объекте, который мы строим, и добавляет некоторую собственную информацию. Например, в принуждении Коэна условия можно рассматривать как конечные приближения к реальному числу, и если тогда сообщает нам значение реального числа в большем количестве мест.${\displaystyle \сигма}$${\displaystyle \тау}$${\displaystyle \сигма}$${\displaystyle \тау}$${\displaystyle \тау \сукц _{C}\сигма }$${\displaystyle \сигма}$

Через мгновение мы определим отношение (читай силы ), которое имеет место между условиями (элементами ) и предложениями, но сначала нам нужно объяснить язык , который является предложением для. Однако, принуждение — это метод, а не определение, и язык для будет зависеть от приложения, которое вы имеете в виду, и выбора .${\displaystyle \sigma \Vdash _{P}\psi }$${\displaystyle \сигма}$${\displaystyle \пси}$${\displaystyle P}$${\displaystyle \пси}$${\displaystyle \пси}$${\displaystyle P}$

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

Отношение принуждения было разработано Полом Коэном , который представил принуждение как метод доказательства независимости определенных утверждений от стандартных аксиом теории множеств, в частности от гипотезы континуума (ГК).${\displaystyle \Vdash}$

Обозначение используется для выражения того, что определенное условие или общий набор заставляет определенное предложение или формулу быть истинными в результирующем расширении принуждения. Здесь представляет исходную вселенную множеств (основную модель), обозначает отношение принуждения и является утверждением в теории множеств. Когда , это означает, что в подходящем расширении принуждения утверждение будет истинным.${\displaystyle V\Vdash \phi }$${\displaystyle \фи}$${\displaystyle V}$${\displaystyle \Vdash}$${\displaystyle \фи}$${\displaystyle V\Vdash \phi }$${\displaystyle \фи}$

• Фитинг, Мелвин (1981). Основы обобщенной теории рекурсии . Исследования по логике и основаниям математики. Т. 105. Амстердам, Нью-Йорк и Оксфорд: North-Holland Publishing Company. С. 1078–1079. doi :10.2307/2273928. JSTOR  2273928. S2CID  118376273.
• Одифредди, Пьерджорджио (1999). Классическая теория рекурсии. Том II . Исследования по логике и основаниям математики. Том 143. Амстердам: North-Holland Publishing Company. ISBN 978-0-444-50205-6. МР  1718169.