Принуждение (теория рекурсии) - Forcing (recursion theory) - Wikipedia

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

Терминология

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

настоящий

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

нить

элемент ${\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}$ несовместимы.

Фильтр

Подмножество ${\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 }$)

Обратите внимание, что для форсирования Коэна ${\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.