Vynucení (teorie rekurze) - Forcing (recursion theory) - Wikipedia

Nutí v teorie rekurze je modifikace Paul Cohen originál set-teoretický technika nutit řešit účinné obavy v teorie rekurze. Koncepčně jsou obě techniky velmi podobné: v obou se pokouší stavět obecný objekty (intuitivně objekty, které jsou nějakým způsobem „typické“) splněním hustých množin. Obě techniky jsou popsány jako relace (obvykle označována ${ displaystyle Vdash}$) mezi „podmínkami“ a větami. Avšak tam, kde je teoretické vynucování množin obvykle zajímáno o vytváření objektů, které splňují všechny husté podmínky v základním modelu, je cílem rekurzivně-teoretické vynucování splnění hustých množin, které jsou aritmeticky nebo hyperaritmeticky definovatelné. Proto lze některé z obtížnějších mechanismů používaných při množinově-teoretickém nucení eliminovat nebo podstatně zjednodušit při definování nucení v teorii rekurze. I když se strojní zařízení může poněkud lišit, teoreticko-rekurzivní a množinově-teoretické vynucování se správně považuje za aplikaci stejné techniky na různé třídy vzorců.

Terminologie

V tomto článku používáme následující terminologii.

nemovitý

prvek ${ displaystyle 2 ^ { omega}}$. Jinými slovy, funkce, která mapuje každé celé číslo na 0 nebo 1.

tětiva

prvek ${ displaystyle 2 ^ {< omega}}$. Jinými slovy, konečné přiblížení ke skutečnému.

pojem nucení

Pojem vynucení je množina ${ displaystyle P}$ a a částečná objednávka na ${ displaystyle P}$, ${ displaystyle succ _ {P}}$ s největší prvek ${ displaystyle 0_ {P}}$.

stav

Prvek v pojmu nutit. Říkáme podmínku ${ displaystyle p}$ je silnější než podmínka ${ displaystyle q}$ právě když ${ displaystyle q succ _ {P} p}$.

kompatibilní podmínky

Za daných podmínek ${ displaystyle p, q}$ říkají, že ${ displaystyle p}$ a ${ displaystyle q}$ jsou kompatibilní, pokud existuje podmínka ${ displaystyle r}$ s ${ displaystyle p succ _ {P} r}$ a ${ displaystyle q succ _ {P} r}$.

${ displaystyle p mid q}$

prostředek ${ displaystyle p}$ a ${ displaystyle q}$ jsou nekompatibilní.

Filtr

Podmnožina ${ displaystyle F}$ pojmu nutit ${ displaystyle P}$ je filtr, pokud ${ Displaystyle p, q in F implikuje p nmid q}$, a ${ Displaystyle p in F land q succ _ {P} p implikuje q in F}$. Jinými slovy, filtr je kompatibilní sada podmínek uzavřených za oslabení podmínek.

Ultrafiltr

Maximální filtr, tj. ${ displaystyle F}$ je ultrafiltr, pokud ${ displaystyle F}$ je filtr a není tam žádný filtr ${ displaystyle F '}$ správně obsahující ${ displaystyle F}$.

Cohen nutit

Pojem nutit ${ displaystyle C}$ kde jsou podmínky prvky ${ displaystyle 2 ^ {< omega}}$ a ${ displaystyle ( tau succ _ {C} sigma iff sigma supset tau}$)

Všimněte si, že pro Cohen nutit ${ displaystyle succ _ {C}}$ je zvrátit relace zadržení. To vede k nešťastnému notovému zmatku, kdy někteří teoretici rekurze obracejí směr vynuceného dílčího řádu (výměna ${ displaystyle succ _ {P}}$ s ${ displaystyle prec _ {P}}$, což je pro Cohenovo vynucování přirozenější, ale je v rozporu s notací používanou v teorii množin).

Obecné objekty

Intuice za vynucením je, že naše podmínky jsou konečné aproximace nějakého objektu, který si přejeme postavit, a to ${ displaystyle sigma}$ je silnější než ${ displaystyle tau}$ když ${ displaystyle sigma}$ souhlasí se vším ${ displaystyle tau}$ říká o objektu, který stavíme, a přidává několik vlastních informací. Například v Cohenově vynucení lze podmínky považovat za konečné přiblížení ke skutečnému a pokud ${ displaystyle tau succ _ {C} sigma}$ pak ${ displaystyle sigma}$ nám říká hodnotu reálného na více místech.

Za okamžik definujeme vztah ${ displaystyle sigma Vdash _ {P} psi}$ (číst ${ displaystyle sigma}$ síly ${ displaystyle psi}$), který platí mezi podmínkami (prvky ${ displaystyle P}$) a věty, ale nejprve musíme vysvětlit Jazyk že ${ displaystyle psi}$ je věta pro. Vynucování je však technika, nikoli definice, a jazyk pro ${ displaystyle psi}$ bude záviset na aplikaci, kterou má člověk na mysli, a na výběru ${ displaystyle P}$.

Myšlenka je, že náš jazyk by měl vyjadřovat fakta o objektu, který chceme postavit pomocí naší nucené konstrukce.

Reference

• Melvin Fitting (1981), Základy zobecněné teorie rekurze.
• Piergiorgio Odifreddi (1999), Teorie klasické rekurze, v. 2.