Einfache Anwendungen des Forcens in der Rekursionstheorie?

Es gibt viele Beispiele. Sehr schnell werden sie ziemlich kompliziert - zB denke ich, dass das Low-Basis-Theorem vielleicht nicht pädagogisch angemessen ist - aber es gibt tatsächlich Beispiele.

Insbesondere der einfachste (meiner Meinung nach) Beweis dafür, dass es unvergleichliche Turing-Grade gibt, ist ein zwingendes Argument. Insbesondere zeigt man dies für jedes Paar endlicher binärer Zeichenfolgen$\sigma,\tau$und alle$e\in\mathbb{N}$, es gibt Erweiterungen$\sigma'\supseteq\sigma$Und$\tau'\supseteq\tau$so dass es keine unendlichen Binärfolgen gibt$f\supseteq\sigma', g\supseteq\tau'$mit$\Phi_e^f=g$. Dies lässt uns induktiv ein Paar unendlicher binärer Folgen aufbauen, die Turing-unvergleichlich sind, indem wir gegen mögliche Reduktionen diagonalisieren (hier wird häufig der Ausdruck "endliche Erweiterungen" verwendet). Das Friedberg-Muchnik-Theorem verbessert dies, indem es die Abschlüsse ce macht, indem es vom "reinen" Erzwingen zum komplizierteren Setzen von Prioritätsargumenten übergeht; siehe diese alte Frage .

Jetzt haben Sie die Frage „generisch“ versus „generisch für eine bestimmte Sammlung dichter Mengen “ (z. B. die re-Einsen) angesprochen. In der Berechenbarkeitstheorie gibt es eine reiche Hierarchie von "Ebenen der Generizität", und dies gilt auch für Nicht-Cohen-Erzwingungsbegriffe (unglücklicherweise bedeutet das Wort "generisch" in der Berechenbarkeitstheorie normalerweise Cohen-generisch). Insbesondere wenn wir das obige Argument untersuchen, sehen wir Folgendes:

• Die dichten Mengen, denen wir begegnen wollen, sind solche der Form „Keine unendliche Erweiterung der linken Saite (bzw. rechts) berechnet irgendeine unendliche Erweiterung der rechten Saite (bzw. links) über$\Phi_e$."

• Auf den ersten Blick ist jedes davon ziemlich kompliziert - nämlich$\Pi^1_1$. Es gibt immer noch nur abzählbar viele solcher dichten Mengen, also können wir sie trivial alle treffen.

• ... Aber vielleicht möchten wir auch sehen, wie einfach wir gehen können! Es gibt zwei Möglichkeiten, wie eine Berechnung "fehlschlagen" kann: Sie kann einen Fehler machen oder überhaupt keine Antwort geben. Dadurch können wir die dichten Mengen, die uns wichtig sind, neu definieren: „ENTWEDER gibt es bereits welche$n$so dass$\Phi_e^{left}(n)$stoppt,$right(n)$definiert ist und$\Phi_e^{left}(n)\not=right(n)$, ODER es gibt einige$n$so dass keine Verlängerung der linken Saite entsteht$\Phi_e^?(n)$halt." (Und ähnlich "links" und "rechts" vertauschen.)

• Diese Definition lässt sich leicht überprüfen$\Sigma^0_2$. Also haben wir:

Wenn$x, y\in 2^{\omega}$sind gegenseitig$\Sigma^0_2$-Cohen generisch - das heißt, wenn das Set$\{(\sigma,\tau)\in 2^{<\omega}\times 2^{<\omega}: \sigma\prec x, \tau\prec y\}$ist ein Filter treffen jeden$\Sigma^0_2$dichte Teilmenge von$2^{<\omega}\times 2^{<\omega}$- Dann$x$Und$y$sind Turing unvergleichlich.

Hier ist ein weiteres Beispiel. Ich bin mir nicht sicher, ob das auf die Rechnung passt - der Beweis ist ziemlich kompliziert, wenn man sich nicht bereits mit dem Erzwingen in der Berechenbarkeitstheorie vertraut gemacht hat -, aber das Erzwingen selbst ist einfach, die Frage ist leicht zu stellen (obwohl die Antwort etwas kompliziert ist). ), und die ganze Situation ist ziemlich interessant.

Nehmen wir an, wir wollen eine schnell wachsende Funktion aufbauen$\omega\rightarrow\omega$. Es gibt einen natürlichen Antrieb, der mir in den Sinn kommt (es gibt viele Variationen dieser Idee) :

• Bedingungen sind Paare$(p, f)$mit$p$eine Karte aus einer endlichen Teilmenge von$\omega$Zu$\omega$, Und$f:\omega\rightarrow\omega$ist total mit$p\subseteq f$.

• Die Bestellung erfolgt durch$(p, f)\le (q, g)$(erinnern, "$\le$" bedeutet "ist stärker als"), wenn:

  • $p\supseteq q$,

  • $f(n)\ge g(n)$für alle$n$, Und

  • für jede$m$In$dom(p)\setminus dom(q)$, wir haben$p(m)\ge g(m)$.

Im Grunde geht es hier um folgendes. Wir versuchen, eine Funktion zu bauen$\omega\rightarrow\omega$. In einem Zustand$(p, f)$, Die$p$-part ist die Menge der Funktion, die wir bisher gebaut haben, und die$f$Teil ist ein "Versprechen", dass die Funktion, die wir bauen, von nun an mindestens so schnell wachsen wird wie$f$.

Dies wird als Hechler-Forcierung bezeichnet . Es ist natürlich nicht das einzige Forcieren, das eine schnell wachsende Funktion hinzufügt, aber es ist meiner Meinung nach das natürlichste (und es hat einige nette mengentheoretische Universalitätseigenschaften - z. B. hat Truss gezeigt, dass if$V[d]$ist eine zwingende Erweiterung des Bodenmodells$V$Wo$d:\omega\rightarrow\omega$beherrscht jede Funktion in$V$, Und$c\in\omega^\omega$ist Cohen generisch vorbei$V[d]$, Dann$d+c$ist Hechler generisch vorbei$V$) .

Nun, eine wichtige Klasse von Fragen in der Berechenbarkeitstheorie hat die Form:

Angenommen, ich kann eine reelle Zahl mit einer bestimmten Eigenschaft berechnen. Was sind die spezifischen reellen Zahlen, die ich garantiert berechnen kann?

Zum Beispiel ist es nicht schwer (wenn man an das obige Argument denkt), zu zeigen, dass zwei hinreichend gegenseitig Cohen-generische reelle Zahlen außer den berechenbaren Mengen nichts gemeinsam berechnen (sie bilden ein "minimales Paar"), also gibt es keine spezifischen reellen Zahlen, die "genügend Cohen-generisch zu sein" lässt mich rechnen.

Eine besonders natürliche Frage dieser Form, im Kontrapositiv formuliert, lautet:

Vermuten$x$ist aus jeder ausreichend schnell wachsenden Funktion berechenbar - das heißt, es gibt welche$f:\omega\rightarrow\omega$so dass irgendwelche$g$dominierend$f$berechnet$x$. Was wissen wir darüber$x$?

Es stellt sich heraus, dass die Menge solcher Realzahlen eine sehr bissige Charakterisierung hat:

Satz . Ein echtes$x$ist aus jeder hinreichend schnell wachsenden Funktion genau dann berechenbar, wenn sie hyperarithmetisch ist .

Die hyperarithmetischen Mengen sind im Wesentlichen solche, die durch wiederholte Turing-Sprünge berechnet werden können – möglicherweise unendlich viele Sprünge, aber nur „berechenbar viele“. (Es gibt auch viele andere Charakterisierungen.) Dies genau zu definieren ist schwierig, aber nicht allzu schwer$(i)$zeigen, dass „die$\omega$Sprung von$0$" hat eine offensichtliche Definition und$(ii)$argumentieren, dass das Zeug wirklich seltsam wird, wenn wir versuchen, das zu nehmen$\alpha$Sprung von$0$für eine wirklich sehr komplizierte zählbare Ordnungszahl$\alpha$(nämlich alle, die keine berechenbare Kopie haben).

Der Beweis des obigen Satzes - von Solovay, wenn ich mich recht erinnere - ist ganz nett. Zu zeigen, dass jede hyperarithmetische Realzahl aus einer ausreichend schnell wachsenden Funktion berechenbar ist, ist ein Beweis durch transfinite Induktion unter Verwendung eines verallgemeinerten Begriffs der Busy Beaver-Funktionen. Das Gegenteil ist die interessante Richtung und beinhaltet eine geschickte Analyse$\Vdash_{Hechler}$. Wenn es Sie interessiert, ist die Diplomarbeit von Peter Gerdes ein guter Anfang, wenn ich mich recht erinnere.