Theorema Posner–Robinson

Theorema Posner–Robinson est theorema theoriae facultatis calculandi de gradibus Turing.

Expositio

Theorema. Sit $B$ copia numerorum naturalium, quae calculari non potest. (Id est $B\not \leq _{T}\mathbf {0}$.) Tum est copia $G$ ut $G\oplus B\equiv _{T}G^{\prime }$.

Demonstratio

Sit $B$. Volumus facere series $((\Phi _{p},{\bar {X}}_{p}))_{p\in \omega }$, quorum:

• $\Phi _{p}$ est copia finita rerum sicut $(a,b,X)$, in qua $a,b\in \omega$, $X\in 2^{<\omega }$. $\Phi _{p}(X)$ est functio ab $2^{\omega }$ in $2^{\omega }$, ut $\Phi _{p}(X)(a)=b$ si et tantum si $(a,b,X)\in \Phi _{p}$,
• ${\bar {X}}_{p}$ est copia finita rerum $X\in 2^{\omega }$,

in qua serie, si $q>p$:

• (a) Cuique $(x_{q},y_{q},\eta )\in \Phi _{q}\backslash \Phi _{p}$ et $(x_{p},y_{p},\sigma )\in \Phi _{p}$, $\vert \eta \vert >\vert \sigma \vert$,
• (b) $\Phi _{p}\subseteq \Phi _{q}$ et ${\bar {X}}_{p}\subseteq {\bar {X}}_{q}$,
• (c) Cuique $X\in {\bar {X}}_{p}$, $\Phi _{q}(X)=\Phi _{p}(X)$.

ita ut, si $\Phi :=\bigcup _{p\in \omega }\Phi _{p}$, tum $\Phi (B)=\Phi ^{\prime }$. Sit $\Phi _{0}={\bar {X}}_{0}=\varnothing$. Si habemus $(\Phi _{p},{\bar {X}}_{p})$, sic agamus ut $(\Phi _{p+1},{\bar {X}}_{p+1})$ faciamus:

1. Sit $\exists n\,\theta _{p}(n,Z\vert n)$ formula numero $p$. Si nancisci possumus copiam $\Psi \supseteq \Phi$ quae (a) satisfaciat, ut cuique $X\in {\bar {X}}_{p}\cup \{B\}$, $\Psi (X)=\Phi (X)$, tum sit $\Phi _{p+1}:=\Psi \cup \{(p,1,B)\}$ et ${\bar {X}}_{p+1}:={\bar {X}}_{p}$.
2. Sin nancisci non possumus $\Psi$, tum sciamus cuique copiae $\Psi \subseteq \Phi$ quae (a) satisfaciat esse $X\in {\bar {X}}_{p}\cup \{B\}$ ut $\Psi (X)\neq \Phi (X)$. Sit igitur collectio ${\mathcal {Z}}$ ut:

${\bar {Z}}\in {\mathcal {Z}}\iff {\text{Sit }}\Psi \supseteq \Phi {\text{ quae (a) satisfaciat, tum si }}\exists n<\vert \Psi \vert \,\theta _{p}(n,\Psi \vert n){\text{, tum }}\exists (a,b,X)\in \Psi \backslash \Phi {\text{, ut }}X\in {\bar {Z}}$

Sed scilicet ${\bar {X}}_{p}\cup \{B\}\in {\mathcal {Z}}$, ergo ${\mathcal {Z}}\neq \varnothing$. Lemma habemus:

Lemma. (de conis vitandis) Sit collectio non vacua ${\mathcal {A}}$ ut $X\in {\mathcal {A}}\iff \forall n\,\theta (n,X\vert n)$, in quo $\theta \in \Delta _{0}$ (vide pagina de hierarchia arithmetica). Sit $D\not \leq _{T}\mathbf {0}$. Tum est $G\in {\mathcal {A}}$ ut $G\not \geq _{T}D$.

Ergo, sit ${\bar {D}}=B$, tum est ${\bar {Z}}\in {\mathcal {Z}}$ ut ${\bar {Z}}\not \geq _{T}B$, id est, $B\not \in {\bar {Z}}$. Igitur sit $\Phi _{p+1}=\Phi _{p}\cup \{(p,0,B)\}$ et ${\bar {X}}_{p+1}:={\bar {X}}_{p}\cup {\bar {Z}}$.

Nunc tota serie facta habemus $\Phi$ ut $\Phi (B)=\Phi ^{\prime }$. Ergo $\Phi \oplus B\equiv _{T}\Phi ^{\prime }$, quod erat demonstrandum.

Significatio

Hoc theorema naturam omnium copiarum quae calculari non possunt patefacit. Si $B$ est copia quae calculari non potest, tum nancisci possumus copia $G$, ut differentia inter $G$ et $G^{\prime }$ sit $B$.