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{\le }_T\mathrm{𝟎}$.) Tum est copia $G$ ut $G\oplus B{\equiv }_T{G}^{\prime }$.

Demonstratio

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

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

in qua serie, si $q>p$:

• (a) Cuique $(x_q,y_q,\eta )\in {\mathrm{\Phi }}_q\mathrm{\setminus }{\mathrm{\Phi }}_p$ et $(x_p,y_p,\sigma )\in {\mathrm{\Phi }}_p$, $|\eta |>|\sigma |$,
• (b) ${\mathrm{\Phi }}_p\subseteq {\mathrm{\Phi }}_q$ et ${\overline{X}}_p\subseteq {\overline{X}}_q$,
• (c) Cuique $X\in {\overline{X}}_p$, ${\mathrm{\Phi }}_q(X)={\mathrm{\Phi }}_p(X)$.

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

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

$\overline{Z}\in 𝒵⟺\text{Sit }\mathrm{\Psi }\supseteq \mathrm{\Phi }\text{ quae (a) satisfaciat, tum si }\mathrm{\exists }n<|\mathrm{\Psi }|{\theta }_p(n,\mathrm{\Psi }|n)\text{, tum }\mathrm{\exists }(a,b,X)\in \mathrm{\Psi }\mathrm{\setminus }\mathrm{\Phi }\text{, ut }X\in \overline{Z}$

Sed scilicet ${\overline{X}}_p\cup \{B\}\in 𝒵$, ergo $𝒵\ne \varnothing$. Lemma habemus:

Lemma. (de conis vitandis) Sit collectio non vacua $𝒜$ ut $X\in 𝒜⟺\mathrm{\forall }n\theta (n,X|n)$, in quo $\theta \in {\mathrm{\Delta }}_0$ (vide pagina de hierarchia arithmetica). Sit $D{\le }_T\mathrm{𝟎}$. Tum est $G\in 𝒜$ ut $G{\ge }_{T}D$.

Ergo, sit $\overline{D}=B$, tum est $\overline{Z}\in 𝒵$ ut $\overline{Z}{\ge }_{T}B$, id est, $B\in ̸\overline{Z}$. Igitur sit ${\mathrm{\Phi }}_{p+1}={\mathrm{\Phi }}_p\cup \{(p,0,B)\}$ et ${\overline{X}}_{p+1}:={\overline{X}}_p\cup \overline{Z}$.

Nunc tota serie facta habemus $\mathrm{\Phi }$ ut $\mathrm{\Phi }(B)={\mathrm{\Phi }}^{\prime }$. Ergo $\mathrm{\Phi }\oplus B{\equiv }_T{\mathrm{\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$.