Принуждение (вычислимость)

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

В этой статье отсутствует информация об отношении принуждения . Пожалуйста, разверните статью, чтобы включить эту информацию. Более подробная информация может быть на странице обсуждения . ( Апрель 2021 г. )${\ displaystyle \ Vdash}$

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

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

Терминология [ править ]

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

настоящий

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

нить

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

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

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

условие

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

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

Данные условия говорят, что и являются совместимыми, если есть условие с и .${\displaystyle p,q}$${\displaystyle p}$${\displaystyle q}$${\displaystyle r}$${\displaystyle p\succ _{P}r}$${\displaystyle q\succ _{P}r}$

${\displaystyle p\mid q}$

значит и несовместимы.${\displaystyle p}$${\displaystyle q}$

Фильтр

Подмножество понятия принуждения - это фильтр if , и . Другими словами, фильтр - это совместимый набор условий, закрывающийся при ослаблении условий.${\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 C}$${\displaystyle 2^{<\omega }}$${\displaystyle (\tau \succ _{C}\sigma \iff \sigma \supset \tau }$

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

Общие объекты [ править ]

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

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

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

Ссылки [ править ]

• Мелвин Фиттинг (1981), Основы обобщенной теории рекурсии .
• Пьерджиоргио Одифредди (1999), Классическая теория рекурсии , т. 2.