% Přednáška: Vyčíslitelnost
% Přednášející: Doc. RNDr. Antonín Kučera, CSc.
% Přepsal: Ladislav Strojil
%
\documentclass[10pt,fleqn,a4paper]{article}
\usepackage[latin2]{inputenc}
\usepackage[czech]{babel}
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\newtheorem{definice}{Definice}
\newtheorem{dusledek}{Důsledek}
\newtheorem{tvrzeni}{Tvrzení}
\newtheorem{veta}{Věta}
\newtheorem{fakt}{Fakt}
\newtheorem{lemma}{Lemma}
\renewcommand{\labelenumi}{\arabic{enumi})}
\renewcommand{\labelenumii}{\alph{enumii})}
\def\minussteckou{\hbox{{}--\kern-0.75ex\raise1ex\hbox{.}\kern .65ex}}
\begin{document}
\begin{titlepage}
\begin{center}

\vspace{5in}
\huge
Vyčíslitelnost

\Large
přednášející: Doc. RNDr. Antonín Kučera, CSc.
 
\par
\vspace{2in}

\normalsize

VERZE 1.0
 
Do formátu \TeX\space převedl Ladislav Strojil 

Připomínky, dotazy, opravy na emailu: Ladislav@Strojil.cz

Nejnovější verze k nalezení vždy na http://ladislav.strojil.cz/vycislitelnost.php
\end{center}
\end{titlepage}
\newpage
\tableofcontents
\newpage
\section{Základní definice}
\subsection{Výpočetní model}
\begin{definice}[Turingův stroj]
\ \par
Deterministický Turingův stroj (DTS) $M$ s $k$-páskami, kde $k$ je konstanta, je pětice
\begin{equation}
M=(Q,\Sigma,\delta,q_0,F)
\end{equation}

$Q = $ konečná množina stavů řídící jednotky

$\Sigma = $ konečná pásková abeceda

$\delta: Q \times \Sigma^k \mapsto Q \times \Sigma^{k} \times \{L,N,R\}^k $ je přechodová funkce (částečná)

$q_0 \in Q = $ počáteční stav

$F \subseteq Q = $ množina přijímajících stavů
\end{definice}

\begin{veta}[Kleenova o normální formě]
Pro každé $k \geq 1$ existují
\begin{itemize}
\item ČRF $\Psi_k$ $k+1$ proměnných
\item PRP $T_k$ $k+2$ proměnných
\item PRF $U$ jedné proměnné
\item PRF $s_k$ $k+1$ proměnných
\end{itemize}
takové, že
\begin{enumerate}
\item $\Psi_k$ je univerzální funkcí pro třídu všech ČRF $k$ proměnných.

$\Psi_k(e,x_1,\ldots,x_k)$ vyčísluje $e$-tou ČRF $k$ proměnných.

Navíc z odvození ČRF lze efektivně 
získat $e$ a naopak z $e$ lze efektivně získat odvození příslušné ČRF.
\item $\Psi_k(e,x_1,\ldots,x_k) \simeq U(\mu_y T_k(e,x_1,\ldots,x_k,y))$
\item $s_k$ jsou prosté funkce rostoucí ve všech proměnných.

$\lambda x_1,\ldots,x_k\ s_k(e,x_1,\ldots,x_k)$
\item 
$\Psi_{m+n}(e,z_1,\ldots,z_m,x_1,\ldots,x_n) \simeq \Psi_n(s_m(e,z_1,\ldots,z_m),x_1,\ldots,x_n)$

$T_{m+n}(e,\vec{z},\vec{x}) \equiv T_n(s_m(e,\vec{z}),\vec{x})$
\item $T_k(e,x_1,\ldots,x_k,y)\ \&\ T_k(e,x_1,\ldots,x_k,z) \Rightarrow y=z$
\end{enumerate}
\end{veta}
\begin{proof}
Oklikou přes Turingovy stroje (univerzální stroj). 

Univerzální TS Y blok1 Y blok2 $\Delta$ blok3 $\times O_1 \times O_2 \ldots $ Y. Čísla kódujeme unárně ($x$ jako $x+1$ čar).

Základní idea: bez dat Y M Y blok2 $\Delta$ blok3 $\times O_1 \times O_2 \ldots $ Y (očekáváme data).

Y $||\ldots| \lambda ||\ldots|\lambda \ldots \lambda ||\ldots|M$

Konstrukce $s_m(e,x_1,\ldots,x_m)$. Chceme PRF. Zkontrolujeme, zda $e$ po roz\-kó\-do\-vá\-ní obsahuje M, jestliže ne, je výsledkem nulová funkce. Jestliže ano, nej\-le\-věj\-ší výskyt
M nahradíme $||\ldots| \lambda ||\ldots|\lambda \ldots \lambda ||\ldots|M$. 
\end{proof}
\begin{veta}[]
Predikát $\Psi_k(e,x_1,\ldots,x_k)\!\!\downarrow$ je rekurzivně spočetný, není rekurzivní, jeho negace není rekurzivně spočetná. Dále $\Psi_k$ nelze rozšířit do ORF.

Dokonce pokud $\alpha$ je ČRF, která je rozšířením $\Psi_k$, potom lze efektivně nalézt vstup $\vec{z}$ takový, že $\alpha(\vec{z})\!\!\uparrow$.
\end{veta}
\begin{proof}
Z definice je zřejmé, že $\Psi_k(\ldots)\!\!\downarrow$ je rekurzivně spočetný predikát.

Stačí ukázat, že $\neg \Psi_k(\ldots)\!\!\downarrow$ není rekurzivně spočetný. Z toho přímo plyne, že $\Psi_k(\ldots)\!\!\downarrow$ není rekurzivní.

Bez újmy na obecnosti uvažujme $k\!\!=\!\!1$. Použijeme Cantorovu diagonální metodu. 

Kdyby $\Psi_1(\ldots)\!\!\downarrow$ byl rekurzivní, potom by $\neg \Psi_1(x,x)\!\!\downarrow$ byl také rekurzivní, tím spíše rekurzivně spočetný.
Tedy pro nějakou ČRF $\varphi$ by platilo $\neg \Psi_1(x,x)\!\!\downarrow \Leftrightarrow \varphi(x)\!\!\downarrow$.
Vezmeme-li index funkce $\varphi$ (označme jej $x_0$), dostáváme $\Psi_1(x,x)\!\!\downarrow \Leftrightarrow \Psi_1(x_0,x)\!\!\downarrow$, po dosazení $x=x_0$ dostáváme
$\neg \Psi_1(x_0,x_0)\!\!\downarrow\Leftrightarrow\Psi_1(x_0,x_0)\!\!\downarrow$. Spor.

Pro důkaz zbytku tvrzení předpokládejme, že $h(e,x)$ je ORF rozšířením $\Psi_1(e,x)$. Potom $1\minussteckou h(x,x)$ je ORF $g$. Nechť $g$ má index $x_0$, tj. $g(x)\simeq \Psi_1(x_0,x)$. Protože $g$ je ORF,
	pro všechna $x$ platí $\Psi_1(x_0,x)\!\!\downarrow$, tím spíše $\Psi_1(x_0,x_0)\!\!\downarrow$. Tedy dostáváme $h(x_0,x_0)=\Psi_1(x_0,x_0)$. Což ovšem vede ke sporu:
	$1\minussteckou \Psi_1(x_0,x_0) \simeq h(x_0,x_0) \simeq \Psi_1(x_0,x_0)$.

Dodatek: Ke každé ČRF $\varphi(e,x)$, která je rozšířením univerzální ČRF, lze efektivně najít $x_0$ takové, že $\varphi(x_0,x_0)\!\!\uparrow$. Důkaz je totožný.
\end{proof}

Myšlenka obsažená v předchozím důkazu je založená na Cantorově dia\-go\-nál\-ní metodě. Spor na diagonále si vynutí divergenci, neboť rovnost funkcí je jenom podmíněná, tedy v případě divergence je vše v pořádku. 
	
Univerzální funkce pro danou třídu funkcí buď nemůže patřit do této třídy, nebo nemůže být totální. 

\section{Rekurzivně spočetné množiny}
\begin{definice}[]
$W_x$ ($x$-tá rekurzivně spočetná množina) $= dom(\varphi_x) = \{y:\varphi_x(y)\!\!\downarrow\}$
\end{definice}

\begin{definice}[K]
$K = \{x:x\in W_x\} = \{x:\varphi_x(x)\!\!\downarrow\} = \{x:\Psi_1(x,x)\!\!\downarrow\}$
\end{definice}

Množina $K$ souvisí s tzv. \emph{halting problémem}, neboli problémem zastavení Tu\-rin\-go\-va stroje. Platí o ní následující tvrzení.
\begin{veta}[] 
Množina $K$ je rekurzivně spočetná, není rekurzivní, $\overline K$ není rekurzivně spočetná.
\end{veta}
\begin{proof}
$K$ není rekurzivní, neboť $\overline K$ není rekurzivně spočetná. $\overline K$ není rekurzivně spočetná, neboť kdyby byla, měla by index $x_0$.
Jednoduchou diagonalizací dos\-tá\-vá\-me $x_0 \in \overline{K} \Leftrightarrow x_0 \in W_{x_0} \Leftrightarrow x_0 \in K$. Spor.
\end{proof}
\subsection{$1$-převeditelnost, $m$-převeditelnost}
\begin{definice}[]
Množina $A$ je 1-převedilná na $B$ (značíme $A\leq_1 B$), jestliže existuje prostá ORF $f$ taková, že $x \in A \Leftrightarrow f(x) \in B$.

Množina $A$ je $m$-převedilná na $B$ (značíme $A\leq_m B$), jestliže existuje ORF $f$ (ne nutně prostá) taková, že $x \in A \Leftrightarrow f(x) \in B$.

Množina $M$ je 1-úplná, jestliže $M$ je rekurzivně spočetná a každá rekurzivně spočetná množina je na ni 1-převedilná.

Množina $M$ je $m$-úplná, jestliže $M$ je rekurzivně spočetná a každá rekurzivně spočetná množina je na ni m-převedilná.
\end{definice}
Následující věta ukazuje, že \emph{halting problem} je vzhledem k $1$ a $m$-pře\-vo\-di\-tel\-nos\-ti nejtěžší mezi rekurzivně spočetnými problémy.
\begin{veta}[]
$K$ je 1-úplná.
\end{veta}
\begin{proof}
Mějme libovolnou rekurzivně spočetnou množinu $W_x$. 

Mějme ČRF $\alpha(y,x,w)$, popisující $x$-tou rekurzivně spočetnou množinu. Tedy
\begin{eqnarray}
\alpha(y,x,w)\!\!\downarrow\ \Leftrightarrow y \in W_x \Leftrightarrow \Psi_1(x,y)\!\!\downarrow\ \Leftrightarrow \varphi_x(y)\!\!\downarrow.
\end{eqnarray}
Provádíme obvyklý trik s fiktivní proměnnou, funkce $\alpha$ na hodnotě $w$ nezáleží. Z s-m-n věty dostáváme:
\begin{eqnarray}
\alpha(y,x,w) \simeq \Psi_3(a,y,x,w) \simeq \Psi_1(s_2(a,y,x),w) \simeq \varphi_{s_2(a,y,x)}(w).
\end{eqnarray}
Označme $h(y,x)=s_2(a,y,x)$ ($s_2$ je PRF, tím spíše ORF).
\begin{eqnarray}
y \in W_x \Leftrightarrow \alpha(y,x,w)\!\!\downarrow\ \Leftrightarrow \varphi_{h(y,x)}(w)\!\!\downarrow\ \Leftrightarrow \varphi_{h(y,x)}(h(y,x))\!\!\downarrow\ \Leftrightarrow h(y,x) \in K
\end{eqnarray}
Zde jsme mohli za $w$ dosadit $h(y,x)$, neboť hodnota $\alpha$ na $w$ nezáleží!
Tedy $W_x \leq_1\!K$ pomocí funkce $\lambda y\:h(y,x)$.
\end{proof}
\begin{lemma}[]
$K_0 = \{\left<y,x\right>: y \in W_x\}$ je 1-úplná. 
\end{lemma}
\begin{proof}
Zřejmé. $K \leq_1 K_0$ a $K$ je $1$-úplná.
\end{proof}
\begin{lemma}[Poznámky k 1-převeditelnosti]\ 
\begin{enumerate}
\item Relace $\leq_1$ a $\leq_m$ jsou tranzitivní, reflexivní.
\item $A \leq_1 B \Rightarrow A \leq_m B$ 
\item $B$ rekurzivní, $A \leq_m B \Rightarrow A$ rekurzivní.
\item $B$ rekurzivně spočetná, $A \leq_m B \Rightarrow A$ rekurzivně spočetná.
\end{enumerate}
\end{lemma}
\begin{proof}\ 
\begin{enumerate}
\item Zřejmé.
\item Zřejmé.
\item Složením funkce dokazující $\leq_m$ s procedurou, která rozhoduje o $x \in B$ dostaneme proceduru rozhodující o $A$. Dostáváme $c_A(x)=c_B(f(x))$.
\item Stejně.
\end{enumerate}
\end{proof}
\begin{dusledek}[]
$K$ a $\overline K$ jsou $m$-nesrovnatelné. 
\end{dusledek}
\begin{proof}
Plyne z faktu, že $K$ je rekurzivně spočetná, $\overline K$ není a z bodu 4 před\-cho\-zí\-ho lemma.
\end{proof}
\begin{definice}[Rekurzivní permutace]
Permutace na $\mathbb{N}$, která je ORF, se nazývá rekurzivní permutace.
\end{definice}
\begin{definice}[Rekurzivní isomorfismus]
Množiny $A$ a $B$ jsou rekurzivně isomorfní, jestliže existuje rekurzivní permutace $p$ taková, že $p(A)=B$. Značíme $A \equiv B$.
\end{definice}
\begin{definice}[]\ 

$A \equiv_1 B$, jestliže $A \leq_1 B\ \&\ B\leq_1 A$.

$A \equiv_m B$, jestliže $A \leq_m B\ \&\ B\leq_m A$.
\end{definice}
\begin{veta}[Myhill]
$A \equiv B \Leftrightarrow A \equiv_1 B$
\end{veta}
\begin{proof}
Jedná se o efektivní verzi Cantor-Bernsteinovy věty.

$\Rightarrow$ Triviální. 

$\Leftarrow$ Z předpokladů máme dvě prosté ORF převádějící vzájemně $A$ na $B$ a opačně. Chceme sestrojit rekurzivní permutaci $h$ takovou, že $h(A)=B$.

Plán: v krocích budeme generovat graf $h$ tak, že v kroce $n$ bude platit
\begin{eqnarray}
\nonumber
\{0,\ldots,n\} \subseteq dom(h), \qquad \{0,\ldots,n\} \subseteq rng(h).
\end{eqnarray}

Z toho plyne, že $h$ bude definovaná na celém $\mathbb{N}$ a bude na. Současně zajistíme, že $h$ bude prostá. 

Navíc budeme chtít, aby platilo $y \in A \Leftrightarrow h(y) \in B$, tedy aby $h$ převáděla $A$ na $B$.

Začneme v bodě 0 a položíme $h(0)=f(0)$. Rozlišíme následující případy:
\begin{enumerate}
\item $f(0)=0$: vše je v pořádku, $h(0)=f(0)=0$ a $0 \in A \Leftrightarrow 0 \in B$, pok\-ra\-ču\-je\-me dalším prvkem.
\item $f(0)\neq 0$: rozlišíme dva podpřípady
\begin{enumerate}
\item $g(0)\neq 0$: vše v pořádku, definujeme $h(g(0))=0$. 

Tedy $0 \in dom(h) \cap rng(h)$.
\item $g(0)=0$: nemůžeme použít $h(g(0))=0$, protože v bodě 0 je již $h$ definována. Najdeme tedy volný bod. Definujme $h(g(f(0)))=0$. Určitě $g(f(0))\neq 0$, protože $g$ je prostá a $f(0)\neq 0$.
Tímto jsme opět dostali bod 0 do definičního oboru $h$ i oboru hodnot. Zároveň funkci $h$ definujeme podle $f$ a $g$, tedy převádí vzájemně $A$ na $B$.
\end{enumerate}\end{enumerate}
Indukční krok: nechť v kroce $k$ je $z$ první volný prvek. Všechna čísla menší jak $z$ máme v $dom(h)\cap rng(h)$. Podíváme se, zda je $f(z)$ volný. Jestliže ano, položíme $h(z)=f(z)$. 
Jestliže $f(z)$ není volný, hledám zig-zag další volný. Maximálně $z$ prvků je blokovaných.
\end{proof}
\begin{dusledek}[]
$K \equiv K_0$
\end{dusledek}
\begin{proof}
Zřejmé, neboť $K \equiv_1 K_0$.
\end{proof}

Množin, které jsou ekvivalentní množině $K$, je však mnohem více. Ještě jich mnoho uvidíme v dalším textu. Ukažme si však nyní alespoň jednu takovou.
Uvažme množinu $A = \{x: W_x \neq \emptyset\}$, tedy množinu programů, které konvergují alespoň na jednom vstupu. 

$A$ je rekurzivně spočetná, $A=\{x:\exists y,s\ (y \mbox{ patří do } W_x \mbox{ za $s$ kroků})\}$.

Ukážeme, že $A \equiv K$. Protože $K$ je 1-úplná, zřejmě platí $A \leq_1 K$.

Pro opačný směr chceme prostou ORF $h$ takovou, že
\begin{eqnarray}
x \in W_x \Leftrightarrow x \in K \Leftrightarrow h(x) \in A \Leftrightarrow W_{h(x)}\neq \emptyset
\end{eqnarray}
Idea. Vytvoříme program, který čeká, zda $x$ padne do $K$, jestliže ano, dá $\varphi_{h(x)}$ všude definované. Jinak nedělá nic.
\begin{eqnarray}
\alpha(x,w)\!\!\downarrow &\Leftrightarrow& \varphi_x(x)\!\!\downarrow \\
\alpha(x,w) &\simeq& \varphi_{h(x)}(w)
\end{eqnarray}
Tedy $x \in K$ znamená $W_{h(x)}=\mathbb{N}$. Naopak $x \notin K$ znamená $W_{h(x)}=\emptyset$. 
\begin{lemma}[]
$Q$ je ORF, potom $\exists y Q$ je rekurzivně spočetný predikát.
\end{lemma}
\begin{proof}
$\mu_y Q$ je ČRF, její definiční obor je $\exists y\:Q$.
\end{proof}
\begin{veta}[]
Predikát $\exists y T_k(e,x_1,\ldots,x_k,y)$ je univerzálním RSP pro třídu RSP $k$ proměnných.
\end{veta}
\begin{proof}
Z věty o normální formě. 
\end{proof}
\begin{dusledek}[]
Lze definovat index (Gödelovo číslo) rekurzivně spočetného pre\-di\-ká\-tu.
\end{dusledek}
\begin{veta}[]
Konjukce a disjunkce zachovávají rekurzivní spočetnost. Tedy průnik a sjednocení rekurzivně spočetných množin je rekurzivně spočetná množina. Stejně pro predikáty.
\end{veta}
\begin{proof}
Pro průnik spustíme oba programy současně a čekáme, až se oba zastaví. Pro sjednocení čekáme, až se zastaví alespoň jeden.

Formálně pro průnik.
\begin{eqnarray}
\exists s_1 T_1(x,z,s_1)\ \&\ \exists s_2 T_1(y,z,s_2) \Leftrightarrow 
\exists w (T_1(x,z,(w)_{2,1})\ \&\ T_1(y,z,(w)_{2,2}))
\end{eqnarray}
Uvedený predikát je rekurzivně spočetný, tedy má nějaký index.
\begin{eqnarray}
\nonumber
\exists s T_3(e,x,y,z,s) \Leftrightarrow \exists s T_1(s_2(e,x,y),z,s)
\end{eqnarray}
\end{proof}
\begin{veta}[]
Omezená kvantifikace $(\forall y)_{y \leq t}$ a existenční kvantifikace (pro $k\!\!\geq\!\!2$) zachovávají rekurzivní spočetnost.
\end{veta}
\begin{proof}
Neformálně: omezený kvantifikátor lze zkontrolovat for cyklem.

Formálně: 
\begin{eqnarray}
(\forall y)_{y \leq t}\ \exists s\ T_k(e,x_1,\ldots,x_{k-1},y,s) \Leftrightarrow  \\
\Leftrightarrow \exists \mbox{ kód $(k\!+\!1)$-tice } w\ (\forall y)_{y \leq t}\ T_k(e,x_1,\ldots,x_{k-1},y,(w)_{t+1,y})
\end{eqnarray}

Část s omezeným kvantifikátorem je PRP, včetně existenčního kvantifikátoru je to rekurzivně spočetný predikát, tedy má nějaký
index $b$. 
\begin{eqnarray}
\exists s\ T_{k+1}(b,e,x_1,\ldots,x_{k-1},t,s) \Leftrightarrow \exists s\ T_k(s_1(b,e),x_1,\ldots,x_{k-1},t,s).
\end{eqnarray}

Pro existenční kvantifikátor je situace ještě jednodušší. Kvantifikaci přes dvě proměnné převedeme na kvantifikaci přes jednu, kterou budeme
považovat za kód dvojice a v predikátu potom vydělíme jednotlivé složky. Dostáváme predikát $k\!-\!1$ proměnných, proto požadavek na minimální velikost $k$!
\begin{eqnarray}
\exists y \exists s\ T_k(e,x_1,\ldots,x_{k-1},y,s) \Leftrightarrow \exists w\ T_k(e,x_1,\ldots,x_{k-1},(w)_{2,1},(w)_{2,2}) \\
\Leftrightarrow \exists s\ T_k(d,e,x_1,\ldots,x_{k-1},s) \Leftrightarrow \exists s\ T_{k-1}(s_1(d,e),x_1,\ldots,x_{k-1},s)
\end{eqnarray}
\end{proof}

\begin{veta}[]\label{selektor}
Něchť $Q$ je RSP $k+1$ proměnných. Potom existuje ČRF $\varphi$ $k$ pro\-měn\-ných taková, že 
\begin{eqnarray}
\varphi(x_1,\ldots,x_k)\!\!\downarrow\ &\Leftrightarrow& \exists y\ Q(x_1,\ldots,x_k,y) \\
\varphi(x_1,\ldots,x_k)\!\!\downarrow\ &\Rightarrow& Q(x_1,\ldots,x_k,\varphi(x_1,\ldots,x_k)) 
\end{eqnarray}
\end{veta}
\begin{proof}
Věta říká, že pro každý rekurzivně spočetný predikát existuje ČRF taková, že konverguje právě, když existuje $y$ splňující predikát. Tato funkce navíc
přímo vrací jedno takové $y$, pro které predikát platí. Tato $\varphi$ je selektor na grafu $Q$.

Pro $k=1$. Dáno $x$, hledáme nejmenší dvojici $(y,s)$ takovou, že za $s$ kroků ověříme, že $Q(x,y)$ (tj. program pro 
		$Q$ konverguje za $s$ kroků). Pak vydáme $y$.

Obecně: univerzální vyjádření RSP $\exists s\ T_2(e,x,y,s)$, hledáme nejmenší $w$ (kód dvojice) tak, že 
\begin{eqnarray}
\varphi(x) \simeq (\mu_w T_2(e,x,(w)_{2,1},(w)_{2,2}))_{2,1}.
\end{eqnarray}

Funkce $\varphi$ tedy vrací první složku z první dvojice, kterou najde (v uspořádání daném naším kódováním dvojic).
\end{proof}
\begin{veta}[]
Funkce je ČRF $\Leftrightarrow$ má rekurzivně spočetný graf.
\end{veta}
\begin{proof}
Je-li $\varphi$ ČRF, je její graf rekurzivně spočetný: $\left<x_1,\ldots,x_k,y\right> \in \mbox{Graf} \Leftrightarrow \exists
s$ za $s$ kroků program konverguje.

Opačně, je-li graf funkce $\varphi$ rekurzivně spočetný, je selektor na něm ČRF, ale selektor na grafu funkce je 
přímo ona funkce.
\end{proof}
\begin{veta}[Postova]\ 

Množina $M$ je rekurzivní právě, když $M$ i $\overline M$ jsou rekurzivně spočetné.

Predikát $Q$ je ORP právě, když $Q$ i $\neg Q$ jsou RSP.
\end{veta}
\begin{proof}
"$\Rightarrow$": Triviální. 

"$\Leftarrow$": Intuitivně: $M=dom(P_1)$, $\overline M=dom(P_2)$. Pustíme oba programy sou\-čas\-ně a čekáme, který se zastaví. 
Zastaví se právě jeden.

Formálně: $(x \in M\ \&\ y=1) \lor (x \in \overline M\ \&\ y=0)$ je rekurzivně spočetný predikát, selektor na něm je ORF, která je charakteristickou funkcí pro $M$.
\end{proof}
\begin{lemma}[]
Každá rekurzivně spočetná množina je oborem hodnot nějaké ČRF.
\end{lemma}
\begin{proof}
Vytvoříme množinu dvojic $R=\{\left<z,y\right>:z \in W_x\ \& \ y=z\}$. Množina $R$ je rekurzivně spočetná, tedy má
ČRF selektor $\varphi$, platí $dom(\varphi)=rng(\varphi)=W_x$.

Myšlenka toho důkazu je, že body, kde $\varphi_x$ konverguje, vyneseme na diagonálu a vytvoříme selektor. Jeho definiční obor bude zárověň jeho oborem hodnot.
\end{proof}
\begin{veta}[]
Každý obor hodnot ČRF je rekurzivně spočetná množina.
\end{veta}
\begin{proof}
Zkontruujeme pseudoinverzní funkci $h$ k ČRF $\varphi$.
\end{proof}
\subsection{Generování rekurzivně spočetných množin}
\begin{definice}[]
Funkce $f$ je úseková, jestliže jejím definičním oborem je počáteční úsek $\mathbb N$ (nebo celé $\mathbb N$).
\end{definice}
\begin{veta}[]
Rekurzivní množiny jsou právě obory hodnot rostoucích úsekových ČRF.
\end{veta}
\begin{proof}
Definujeme ČRF $f$, která bude rostoucí a úseková. 

Začneme $f(0) \simeq \mu_x(x\in M)$.

Dále $f(n+1) \simeq \mu_y(y > f(n)\ \& \ y \in M)$

Opačně. Máme $f$ rostoucí úsekovou ČRF. V případě, že je $f$ konečná (tohle ale nejsme schopni efektivně rozpoznat!), víme jak, známe $D=dom(f)$ a tedy $rng(f)$ je rekurzivní.

V případě, že je $f$ totální
\begin{eqnarray}
y \in M=rng(f) \Leftrightarrow \exists x(f(x)=y)) \Leftrightarrow \exists x\!\leq\!y(f(x)=y)
\end{eqnarray}
Poslední ekvivalence platí, protože $f$ je rostoucí a úseková. Tedy 
\begin{eqnarray}
y \in M \Leftrightarrow y \in \{f(0),\ldots,f(y)\}.
\end{eqnarray}
\end{proof}
\begin{veta}[]
Množina $M$ je nekonečná a rekurzivní právě, když je oborem hodnot rostoucí ORF. Tedy $M$ lze generovat prostou ORF.
\end{veta}
\begin{proof}
Důsledek následující věty.
\end{proof}
\begin{veta}[]
Rekurzivně spočetné množiny jsou právě obory hodnot prostých ú\-se\-ko\-vých ČRF.
\end{veta}
\begin{proof}
"$\Leftarrow$": Víme, obor hodnot ČRF je rekurzivně spočetná množina.

"$\Rightarrow$": Mějme ČRF $\varphi$. 

Důkaz provedeme pomocí rekurzivní množiny 
\begin{eqnarray}
B=\{\left<x,s\right>:\varphi(x)\!\!\downarrow \mbox{ přesně za $s$ kroků}\}. 
\end{eqnarray}

Množinu $B$ lze, protože je rekurzivní,
generovat pomocí rostoucí úsekové ČRF $h$. Funkce $h$ generuje dvojice, definujeme tedy $g(x) \simeq (h(x))_{2,1}$. Zřejmě $g$ je prostá, úseková a ČRF (a generuje $dom(\varphi)$).
\end{proof}
\begin{dusledek}[]
Každá nekonečná rekurzivně spočetná množina obsahuje ne\-ko\-neč\-nou rekurzivní podmnožinu.
\end{dusledek}
\begin{proof}
Mějme $f$, která prostě generuje $M$. Vyber rostoucí podposloupnost. Ta je rekurzivní.
\begin{eqnarray}
g(0)&=&f(0) \\
g(n+1)&=&f(\mu_j (f(j)>g(n)))
\end{eqnarray}
Obor hodnot $g$ je nekonečné rekurzivní množina a je podmnožinou $M$. 
\end{proof}
\begin{definice}[Imunní množina]
Množina $M$ je imunní, jestliže $M$ je ne\-ko\-neč\-ná a neobsahuje nekonečnou rekurzivně spočetnou podmnožinu.
\end{definice}
\begin{definice}[Simple množina]
Množina $A$ je simple, jestliže $A$ je rekurzivně spočetná a $\overline A$ je imunní. 
\end{definice}
\begin{lemma}[]
Existuje imunní množina.
\end{lemma}
\begin{proof}
Nejprve neefektivní konstrukce. Budeme požadovat, aby $M$ byla ne\-ko\-neč\-ná a od každé nekonečné rekurzivně spočetné se lišila alespoň v jednom bodě.
Naše strategie bude dát do $M$ mnoho prvků a potom, kdykoliv je $W_x$ nekonečná, vzít nějaký prvek z $W_x$, který je ještě volný, a ten dát do $\overline M$.

Krok $s$. Nějaký volný prvek dáme do $M$. Vezmu $W_s$, zeptám se, zda je $W_s$ nekonečná (neefektivní krok!), pokud ano, vezmu nějaký volný prvek z $W_s$ a dám
jej do $\overline M$. V kroce $s$ je blokováno nejvýše $2s\!+\!2$ prvků, tedy vždy můžeme volit.

Nyní si ukážeme efektivní konstrukci.

Problém je rozhodnout, zda $W_x$ je nekonečná. Nebudeme se tedy ptát, zda je nekonečná, ale odstraníme všechny "hodně velké" množiny. V kroce $s$ odstraníme 
množinu $W_s$, jestliže $W_s$ obsahuje prvek větší jak $2s$.
\begin{eqnarray}
Q(x,y) \Leftrightarrow y \in W_x\ \& \ y > 2x
\end{eqnarray}
$Q$ je rekurzivně spočetná relace, její selektor $\varphi$ je ČRF. Nechť $A=rng(\varphi)$, potom $\overline A$ je hledaná množina.

Ověření, že $\overline A$ splňuje požadované vlastnosti. Pro $j \geq x$ platí $\varphi(j)>2x$ (pokud konverguje). Tedy příspěvky do $W_x, W_{x+1},\ldots$ jsou všechny větší než $2x$.
Do množiny ${0,\ldots,2x}$ mohou tedy přispět jenom množiny $W_0,\ldots,W_{x-1}$. Máme tedy $2x+1$ čísel, šanci má jenom $x$, tedy nejméně $x+1$ z nich zůstane mimo $A$, tj. padnou do
$\overline A$. Tedy $\overline A$ je nekonečná.

Ověřme druhou podmínku. Je-li $W_x$ nekonečná, potom nemůže být pod\-mno\-ži\-nou $\overline A$. Dokonce platí $W_x\subseteq \overline A \Rightarrow W_x\subseteq \{0,\ldots,2x\}$.
\end{proof}

Výše uvedená konstrukce dokonce dává konstrukci \emph{simple} množiny množiny..

\begin{definice}[]
\begin{eqnarray}
Tot & = & \{x: W_x=\mathbb N\} \\
Inf & = & \{x: W_x \mbox{ nekonečná}\} \\
Fin & = & \{x: W_x \mbox{ konečná}\}
\end{eqnarray}
\end{definice}
\begin{veta}[]
Tot $\equiv$ Inf
\end{veta}
\begin{proof}
Stačí dokázat Tot $\leq_1 $ Inf a Inf $\leq_1$ Tot.

Definujme $\alpha(x,w)\!\!\downarrow\ \Leftrightarrow \forall j\!=\!0,\ldots,w\ \varphi_x(j)\!\!\downarrow$

Z s-m-n věty dostaneme $\alpha(x,w)\simeq \varphi_{h(x)}(w)$. 

Jestliže $x \!\in\! Tot$, potom $W_{h(x)}=\mathbb N$. Naopak pro $x \!\notin\! Tot$ je $W_{h(x)}$ konečná.

Naopak, definujme $\beta(x,w)\!\!\downarrow\ \Leftrightarrow W_x$ obsahuje alespoň $w$ prvků.

Z s-m-n věty dostaneme $\beta(x,w)\simeq \varphi_{g(x)}(w)$. 

Jestliže $w \!\in\! Inf$, potom $g(x) \in Tot$. Naopak pro $w \!\notin\! Inf$ je $g(x) \notin Tot$.
\end{proof}






\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%ř
% Druhý semestr
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%ř
\begin{definice}[Hyperimunní množina]
Množina $B$ je hyperimunní, jestliže je nekonečná a neexistuje ORF $f$ taková, že majorizuje množinu $B$.
\end{definice}
\begin{definice}[]
Říkáme, že ORF $f$ majorizuje nekonečnou množinu $B$, jestliže $B=\{x_0,x_1,x_2,\ldots\}$ je rostoucí seznam prvků $B$ a platí $f(n)\geq x_n$.
\end{definice}
\begin{definice}[Hypersimple množina]
Množina $A$ je hypersimple, jestliže $A$ je simple a $\overline A$ je hyperimunní.
\end{definice}
\begin{lemma}[]
Hyperimunní množina je imunní.
\end{lemma}
\begin{proof}
Sporem. Nechť hyperimunní $A$ není imunní. Potom mám nekonečnou rekurzivně spočetnou množinu $W_z$, kterou $A$ obsahuje. 

Definujeme $D_{f(i)}=i$-tý bod $W_z$. 
Dostali jsme nekonečnou posloupnost konečných (jednobodových) množin, které všechny protínají $A$. Spor.
\end{proof} 
\begin{veta}[]
Množina $A$ je hyperimunní $\Leftrightarrow$ $A$ je nekonečná a neexistuje ORF $f$ taková, že 
\begin{eqnarray}
\forall n (D_{f(n)}\cap A \neq \emptyset)\ \& \ \forall i,j\ ( i\!\neq\!j\  \Rightarrow D_{f(i)}\cap D_{f(j)}=\emptyset).
\end{eqnarray}
Zde $D_x$ označuje $x$-tou konečnou množinu. Požadujeme tedy, aby neexistovala ORF vybírající prostým způsobem konečné množiny tak, aby 
všechny vybrané měly neprázdný průnik s $A$.
\end{veta}
\begin{proof}
"$\Rightarrow$": Dokážeme, že negace pravé strany implikuje negaci levé strany. Tedy $A$ je konečná nebo existuje ORF taková, že 
\begin{eqnarray}
\forall n (D_{f(n)}\cap A \neq \emptyset)\ \& \ \forall i,j\ ( i\!\neq\!j\  \Rightarrow D_{f(i)}\cap D_{f(j)}=\emptyset).
\end{eqnarray}
Je-li $A$ konečná, nemůže být hyperimunní. Existuje-li taková $f$, zvolme 
$g(n)=max(\bigcup_{j=0}^n D_{f(j)})$. Potom $g(n)$ majorizuje $A$. Zřejmé.

Opačnou implikaci budeme opět dokazovat jako převrácenou implikaci negací. Nechť $A$ není hyperimunní, tedy máme $g$, která ji majorizuje.
Položme 
\begin{eqnarray}
h(0)&=&g(0) \\
h(n+1)&=&g(h(n)+1)\qquad (\mbox{platí }g(h(n)+1)\geq x_{h(n)+1})
\end{eqnarray}
Zvolíme $f$ následovně
\begin{eqnarray}
D_{f(0)}&=&\{0,\ldots,h(0)\} \\
D_{f(n+1)}&=&\{h(n)+1,\ldots,h(n+1)\}
\end{eqnarray}
Protože platí $g(h(n)+1)\geq x_{h(n)+1}$, což je $h(n)+2$ prvků, je každá $D_{f(n)}$ neprázdná.
\end{proof}
\begin{veta}[Existence hypersimple množiny]
Existuje hypersimple množina.
\end{veta}
\begin{proof}
Pracný, pokud se provádí přímo diagonalizací.
\end{proof}
\begin{veta}[Dekker]
Nechť množina $A$ je rekurzivně spočetná, nerekurzivní, potom existuje $B$ hypersimple.
\end{veta}
\begin{proof}
Množina $A$ je zřejmě nekonečná. Existuje $f$ prostá ORF generující $A$.
Definujeme
\begin{eqnarray}
B&=&\{x: \exists y (y>x \land f(y)<f(x))\} \\
\overline B&=&\{x: \forall y (y>x \Rightarrow f(y)>f(x))\} 
\end{eqnarray}
Lze ukázat, že $\overline B$ je nekonečná (plyne to z faktu, že $f$ generuje množinu $A$ prostě).

Neexistuje ORF majorizující $B$. Kdyby ano, potom by $A$ byla rekurzivní. Tj. $g$ nechť je ORF majorizující $\overline B$.
\begin{eqnarray}
x\in A \Leftrightarrow x \in rng(f) \Leftrightarrow x \in \{f(0),\ldots,f(g(x))\}.
\end{eqnarray}
Spor.

Ukažme ještě, že $A$ a $B$ jsou stejně složité ve smyslu vyčíslitelnosti, tedy že z jedné vypočítám druhou.

Mám-li $B$ a potřebuji rozhodnout o $x\in A$, najdu prvních $x+1$ prvků z $\overline B$, nechť poslední z nich je $w$.
\begin{eqnarray}
x \in A \Leftrightarrow z \in \{f(0),\ldots,f(w)\}
\end{eqnarray}

Naopak, mám-li $A$ a rozhoduji, zda $x \in B$.
\begin{eqnarray}
x \in B &\Leftrightarrow& \exists y (y>x \land f(y)<f(x)) \\
x \in B &\Leftrightarrow& (\{0,\ldots,f(x)\}\setminus\{f(0),\ldots,f(x)\})\cap A\neq \emptyset.
\end{eqnarray}
\end{proof}

\begin{veta}[Matijasevič]
Predikát $P$ je rekurzině spočetný právě, když je diofantický, tj. existují 2 polynomy s přirozenými koeficienty $p_1$, $p_2$ takové,
	že
\begin{eqnarray}
P(y_1,\ldots,y_n) \Leftrightarrow \exists x_1,\ldots,x_k (p_1(\vec{y},\vec{x})=p_2(\vec{y},\vec{x}))
\end{eqnarray}
\end{veta}





\section{Věty o rekurzi}
\begin{veta}[O rekurzi]
Jestliže $f$ je ČRF jedné proměnné, potom existuje $a$ takové, že $\varphi_{f(a)}(x)\simeq \varphi_a(x)$ pro všechna $x$.
\end{veta}
\begin{proof}
\begin{eqnarray}
\lambda z,\!x\ (\varphi_{f(s_1(z,z))}(x)) \simeq \Psi_2(e,z,x) \simeq \varphi_{s_1(e,z)}(x)
\end{eqnarray}
Dosadíme $z=e$ a dostáváme hledané $a=s_1(e,e)$. Platí totiž
\begin{eqnarray}
\varphi_{f(s_1(e,e))}(x) \simeq \Psi_2(e,e,x) \simeq \varphi_{s_1(e,e)}(x).
\end{eqnarray}
\end{proof}
Funkce $f$ zobrazuje program na program. Bod $a$ je pevný bodem zobrazení $f$. Jak vypadají programy $a$ a $f(a)$? 
Který z nich počítá déle? Uvidíme, že program $a$ počítá déle, než $f(a)$.

Co dělá program $e$ na datech $(z,x)$? Počítá $\varphi_{f(s_1(z,z))}$, tj. vezme $z$ a spočítá neprve $s_1(z,z)$, potom $f(s_1(z,z))$, který 
ale nemusí konvergovat. Jestliže $f(s_1(z,z))\!\!\downarrow$, spustí se na vstup $x$.

Co dělá program $a$? Program $a$ vznikne jako $s_1(e,e)$. Mějme na vstupu $x$. Program $a$ vezme $e$ a přidá ho k $x$ a spustí
program $e$ na $(e,x)$. Co udělá program $e$ na těchto datech? Spočítá $s_1(e,e)$ (tedy spočítá $a$), potom $f(s_1(e,e))=f(a)$ a spustí program $f(a)$ na $x$.

Program $a$ tedy neprve spočítá $a$, potom spočítá $f(a)$ (pokud konverguje) a ten simuluje na vstupu $x$. Program $a$ je tedy složitější než $f(a)$ a počítá déle.
\begin{veta}[O generování pevných bodů]
Pro každou $f \in \mbox{ČRF}$ existuje prostá rostoucí PRF $g$ taková, že platí:
\begin{equation}
\varphi_{f(g(j))}(x)\simeq\varphi_{g(j)}(x)
\end{equation}
Tedy $g$ rostoucím způsobem generuje nekonečně mnoho pevných bodů funkce $f$.
\end{veta}
\begin{proof}
\begin{math}
\varphi_{f(s_2(z,z,j))}(x)\simeq\psi(e,z,j,x)\simeq\varphi_{s_2(e,z,j)}(x)
\end{math}.

Zvolme $g(j)=s_2(e,e,j)$.
\end{proof}
\begin{veta}[??]
Nechť $h$ je ČRF $n+1$ proměnných. Potom existuje číslo $a$ takové, že $a$ je indexem funkce $\lambda_{x_1,\ldots,x_n}h(a,x_1,\ldots,x_n)$, 
	tedy platí $\varphi_a(x_1,\ldots,x_n)\simeq h(a,x_1,\ldots,x_n)$
\end{veta}
\begin{proof}
\begin{math}
h(v,x_1,\ldots,x_n)\simeq \psi_{n+1}(b,v,x_1,\ldots,x_n)\simeq \varphi_{s_1(b,v)}(x_1,\ldots,x_n)
\end{math}

Následně aplikujeme větu o rekurzi na $s_1(b,v)$ v proměnné $v$ a dostáváme hledané $a$.
\end{proof}
\begin{veta}[Věta o rekurzi v závislosti na parametrech]
Jestliže $f$ je ČRF $n+1$ proměnných, potom existuje PRF $g$ $n$ proměnných taková, že

\begin{math}
\varphi_{h(g(y_1,\ldots,y_n),y_1,\ldots,y_n)}(x)\simeq \varphi_{g(y_1,\ldots,y_n)}(x)
\end{math}
\end{veta}
\begin{proof}
\begin{equation}
\nonumber
\varphi_{h(s_{n+1}(z,z,y_1,\ldots,y_n),y_1,\ldots,y_n)}(x) \simeq \psi_{n+2}(e,z,y_1,\ldots,y_n,x) \simeq
\varphi_{s_{n+1}(e,z,y_1,\ldots,y_n)}(x)
\end{equation}

Zvolme $g(y_1,\ldots,y_n)=s_{n+1}(e,e,y_1,\ldots,y_n)$.
\end{proof}

\begin{veta}[Rice]
Jestliže $\mathcal{A}$ je třída ČRF (jedné proměnné), která je netriviální, potom
$A_{\mathcal{A}} = \{ x : \varphi_x \in \mathcal{A}\}$ je nerekurzivní.
\end{veta}
\begin{proof}
Sporem. Nechť $A$ je rekurzivní. Potom lze vytvořit ORF $f$ takovou, že všechny prvky z $A$ zobrazí na nějaký 
prvek $b \notin A$ a všechny prvky mimo $A$ zobrazí na nějaký prvek $a \in A$. Podle věty o rekurzi existuje pevný bod $f$ $u_0$, tedy platí:
\begin{equation}
\varphi_{u_0}=\varphi_{f(u_0)}
\end{equation}
Tedy
\begin{eqnarray}
u_0 \in A \Rightarrow f(u_0)=b \notin A \\
u_0 \notin A \Rightarrow f(u_0)=a \in A
\end{eqnarray}
To je ovšem spor, protože $u_0$ a $f(u_0)$ jsou indexy stejné funkce, a tedy buď obě čísla v $A$ leží nebo obě neleží.

Pozor, nejedná se o třídu programů, ale třídu funkcí. Tedy i pro jednoprvkovou $\mathcal{A}$ bude $A_{\mathcal A}$ nekonečná a nerekurzivní (každá funkce 
		je vyčíslovaná nekonečně mnoha programy a rozhodnout o jejich ekvivalenci je nelze efektivně). Viz následující důsledek.
\end{proof}
\begin{dusledek}
Nechť $\mathcal{A}=\{\varphi_e\}$, potom 
$A=\{x:\varphi_x=\varphi_e\}$ je nerekurzivní. Rozhodnout o rovnosti funkcí vyčíslovaných dvěma programy nelze algoritmicky.
\end{dusledek}
\section{Produktivní a kreativní množiny}

\begin{definice}[Produktivní množina]
Množina $B$ je \emph{produktivní}, jestliže existuje ČRF $\varphi$ taková, že $W_x \subseteq B \Rightarrow \varphi(x)\!\!\downarrow \;\&\; \varphi(x) \in B \setminus W_x$
\end{definice}
\begin{definice}[Kreativní množina]
Množina $A$ je \emph{kreativní}, jestliže $A$ je rekurzivně spočetná a $\overline{A}$ je produktivní.
\end{definice}
\begin{veta}[O produktivní funkci]
Každá produktivní množina má produktivní funkci, která je ORF.
\end{veta}
\begin{proof}
Mějme nějakou ČRF $f$ produktivní pro $B$. 

\begin{math}
W_{g(y)}=\left\{\begin{array}{ll}
	W_y & \mbox{jestliže } f(g(y))\!\!\downarrow \\
		\\
	\emptyset & \mbox{jestliže } f(g(y))\!\!\uparrow 
\end{array}
\right.
\end{math} %}

$f(g(y))$ nemůže divergovat, protože potom by $W_{g(y)}$ bylo rovno prázdné množině, která je ale triviálně podmnožinou $B$. Tedy by $f(g(y))$ muselo konvergovat a vracet prvek mimo $B$. Což by byl spor.

$f(g(y))$ tedy konverguje a $W_g(y)=W_y$, tedy pokud $W_y \subseteq B$, potom také $W_{g(y)} \subseteq B$ a tedy $f(g(y))$ musí konvergovat a vracet prvek mimo $W_{g(y)}$ (což je rovno $W_y$), tedy nový prvek $f(g(y)) \in B \setminus W_y$.

Konstrukci $g$ provedeme pomocí věty o rekurzi. Mějme pomocnou ORF $h$ takovou, že platí
\begin{eqnarray}
W_{h(x,y)} = \left\{\begin{array}{ll}
	W_y & \mbox{jestliže } f(x)\!\!\downarrow \\
		\\
	\emptyset & \mbox{jestliže } f(x)\!\!\uparrow 
\end{array}\right.%}
\end{eqnarray}
Takovou $h$ získáme pomocí s-m-n věty následovně.
\begin{eqnarray}
\alpha(x,y,w)\!\!\downarrow\Leftrightarrow f(x)\!\!\downarrow\ \&\ w\in W_y
\end{eqnarray}
Aplikací s-m-n věty dostaneme $h$. Nyní použijeme větu o rekurzi.
\begin{eqnarray}
\exists \mbox{ PRF } g: W_{g(y)}=W_{h(g(y),y)}=\left\{\begin{array}{ll}
	W_y & \mbox{jestliže } f(g(y))\!\!\downarrow \\
		\\
	\emptyset & \mbox{jestliže } f(g(y))\!\!\uparrow 
\end{array}\right.%}
\end{eqnarray}
\end{proof}
\begin{veta}[]
Každá produktivní množina obsahuje nekonečnou rekursivně spo\-čet\-nou množinu.
\end{veta}
\begin{proof}
Neformálně. Mějme množinu $A$ a její produktivní funkci $f$. Začneme s $W_{z_0}=\emptyset$ a aplikujeme $f$. Dostáváme první prvek $f(z_0) \in A$.
	$W_{z_1} = \{f(z_0)\}$ atd.
\end{proof}
\begin{dusledek}[]
Produktivní množiny nejsou imunní, imunní nejsou produktivní.
\end{dusledek}
\begin{veta}[O rekurzivní permutaci]
Každá produktivní množina má produktivní funkci, která je rekurzivní permutací, tj. je prostá a na.
\end{veta}
\begin{proof}
Mějme funkci $f$ produktivní pro množinu $A$.

Dvě strategie, jedna pro \emph{na} a jedna pro \emph{prostá}.

\emph{na}:

Snadno nalezneme nekonečnou rekurzivní množinu $M$ takovou, že $x \in M \Rightarrow W_x = \mathbb N$ a tedy jistě $x \in M \Rightarrow W_x \nsubseteq A$. 


Definujeme 
\begin{eqnarray}
g(x)=\left\{\begin{array}{ll}
	f(x) & x \notin M \\
	j & x \in M \;\&\; x \mbox{ je $j$-tým prvkem }M.
	\end{array}
	\right. %}
\end{eqnarray}

Takto definovaná $g$ je jistě produktivní ($W_x \subseteq A \Rightarrow x \notin M$ a tedy platí $g(x)=f(x)$) a na ($M$ je nekonečná).

\emph{prostá}: 
\begin{eqnarray}
h(0) &=& f(0) \\
h(n+1)&=&\left\{\begin{array}{ll}
	f(n+1) & \qquad f(n+1) \notin \{h(0),\ldots,h(n)\}\\
	? & \qquad f(n+1) \in \{h(0),\ldots,h(n)\}
	\end{array}
	\right. %}
\end{eqnarray}

V případě, že je $f(n+1)$ již blokovaná, přidáme k $W_{n+1}$ prvek $f(n+1)$ a aplikujeme na index této množiny funkci $f$. V případě, že platilo 
$W_{n+1} \subseteq A$, dostáváme iterací tohoto postupu prostou posloupnost prvků, z nichž maximálně $n$ je blokovaných. První neblokovaný zvolíme jako $h(n+1)$.
V případě, že opakováním nedostaneme neblokovaný prvek, muselo platit $W_{n+1}\nsubseteq A$, tedy můžeme volit libovolně (ale prostě).

Spojením těchto dvou strategií dostáváme funkci, která je na a prostá.
\end{proof}

\begin{veta}[O ekvivalenci pojmů]
$A$ je kreativní $\Leftrightarrow$ $A$ je $1$-úplná $\Leftrightarrow$ $A$ je $m$-úplná.
\end{veta}
\begin{proof}
Plyne přímo z následující věty.
\end{proof}

\begin{veta}[O ekvivalenci pojmů II]
$B$ je produktivní $\Leftrightarrow$ $\overline{K} \leq_1 B$ $\Leftrightarrow$ $\bar{K} \leq_m B$ 
\end{veta}
\begin{proof}
2 $\Rightarrow$ 3: triviální

3 $\Rightarrow$ 1:  
\begin{lemma}[]
Jestliže množina $C$ je produktivní a $C \leq_m B$, potom i $B$ je produktivní. Produktivita se tedy zachovává směrem vzhůru při $\leq_m$.
\end{lemma}
\begin{proof}
Neformálně: nechť $W_x \subseteq B$, hledáme nový bod mimo $W_x$. Vezmeme vzor $W_x$ při $f$, kde $h$ je 
funkce dokazující $\leq_m$.

Platí $h^{-1}(W_x) \subseteq C$, protože $h$ musí převádět $C$ na $B$. Tedy můžeme na index množiny $h^{-1}(W_x)$ aplikovat 
funkci $f$, která je produktivní pro $C$. Dostáváme bod mimo $h^{-1}(W_x)$ a tedy jeho obraz při $h$ musí padnout mimo $W_x$.

Formálně: Existuje ORF $g$ taková, že složení $h \circ f \circ g$ je hledaná produktivní funkce pro $B$. (Funkce $g$ vrací index
		množiny $h^{-1}(W_x)$.)
$W_{g(x)} = h^{-1}(W_x) = \{y: h(y) \in W_x\}$ ($g$ ze s-m-n věty)
\begin{equation}
W_x \subseteq B \Rightarrow W_{g(x)} \subseteq C \Rightarrow f(g(x)) \in C\setminus W_{g(x)} \Rightarrow hfg(x) \in B \setminus W_x
\end{equation}
	
\end{proof}

Protože $\overline{K}$ je produktivní, je i $B$ dle předchozího lemma produktivní.

1 $\Rightarrow$ 2: ($B$ produktivní $\Rightarrow$ $\overline{K} \leq_1 B$)
Cíl: prostá ORF $g$ taková, že 
\begin{equation}
W_{g(x)}=\left\{\begin{array}{ll}
	\{f(g(x))\} & \qquad x \in K \\
		\\
	\emptyset & \qquad x \notin K
	\end{array}
	\right. %}
\end{equation}

Potom platí:
\begin{eqnarray}
x \in \overline{K} &\Rightarrow& W_{g(x)}=\emptyset \subseteq B \Rightarrow fg(x) \in B \setminus W_{g(x)} \Rightarrow fg(x) \in B \\
x \in K &\Rightarrow& W_{g(x)}=\{f(g(x))\}
\end{eqnarray}

Situace $f(g(x)) \in B$ nemůže nastat, protože potom by 
\begin{eqnarray}
W_{g(x)}\subseteq B \Rightarrow f(g(x)) \in B \setminus W_{g(x)}, 
\end{eqnarray}
	ale protože platí $W_{g(x)}=\{f(g(x))\}$, muselo by platit $f(g(x)) \in B \setminus \{f(g(x))\}$, což nelze. Proto musí platit 
	$f(g(x)) \in \overline{B}$.

Tedy $h=f\circ g$ $1$-převádí $\overline{K}$ do $B$.

Pro pořádek ukážeme konstrukci $g$. Pomocí s-m-n věty a věty o rekurzi. 
\begin{equation}
W_{\alpha(x,y)}=\left\{\begin{array}{ll}
	\{f(y)\} & \qquad x \in K \\
		\\
	\emptyset & \qquad x \notin K
	\end{array}
	\right. %}
\end{equation}
Potřebné $\alpha$ dostaneme pomocí s-m-n věty následovně.
\begin{equation}
\beta(x,y,w)\!\!\downarrow\ \Leftrightarrow\ y\in K \;\&\;w=f(y)
\end{equation}

Nyní použijeme větu o rekurzi.
\begin{equation}
W_{g(x)}=W_{\alpha(x,g(x))}=\left\{\begin{array}{ll}
	\{f(g(x))\} & \qquad x \in K \\
		\\
	\emptyset & \qquad x \notin K
	\end{array}
	\right. %}
\end{equation}
\end{proof}
\begin{definice}[Úplně produktivní množina]
Množinu $A$ nazveme \emph{úplně produktivní} množinou, když existuje ORF $f$ taková, že 
\begin{equation}
f(x) \in A \setminus W_x \mbox{  nebo  } f(x) \in W_x \setminus A
\end{equation}
\end{definice}
\begin{lemma}[]
Úplná produktivita implikuje produktivitu.
\end{lemma}
\begin{proof}
Zřejmé. Jestliže platí $W_x \subseteq A$, potom $W_x \setminus A=\emptyset$ a tedy musí nastat případ $f(x)\in A \setminus W_x$, což dokazuje produktivitu $A$.
\end{proof}
\begin{veta}[O úplné produktivitě]
$A$ je produktivní $\Leftrightarrow$ $A$ je úplně produktivní.
\end{veta}
\begin{proof}
Produktivita se zachovává při $\leq_m$ a $\leq_1$. Stejně tak se zachovává úplná produktivita (důkaz je totožný).

$\overline{K}$ je úplně produktivní (a to dokonce při identické funkci - snadno se ověří, že $(x \in \overline{K} \setminus W_x) \lor (x \in W_x \setminus \overline{K})$. Zbytek je zřejmý.
\end{proof}

\begin{dusledek}
Protože $\overline{K} \leq_m Tot = \{x:\varphi_x \mbox{ totální }\} = \{ x : W_x=\mathbb{N}\}$, platí $Tot$ je produktivní.
\end{dusledek}
\section{Dvojice množin}
\begin{definice}[Rekurzivní neoddělitelnost]
Dvojice množin $A$, $B$ ($A \cap B=\emptyset$) je rekurzivně neoddělitelná, jestliže neexistuje rekurzivní množina $M$ taková, že
\begin{equation}
A \subseteq M, M \cap B=\emptyset \;(\mbox{tj. }B \subseteq \overline{M})
\end{equation}
\end{definice}
\begin{definice}[Efektivní neoddělitelnost]
Dvojice množin $A$, $B$ ($A \cap B=\emptyset$) je efektivně neoddělitelná, jestliže existuje ČRF $\varphi$ taková, že
\begin{equation}
\left.
\begin{array}{r}
A \subseteq W_x \\
B \subseteq W_y \\
W_x \cap W_y = \emptyset
\end{array}\right\}
\Rightarrow \varphi(x,y)\!\!\downarrow\;\&\;\varphi(x,y)\notin W_x \cup W_y
\end{equation}

Jinými slovy, z indexů aproximace $A$ a $B$ efektivně naleznu další bod, který leží mimo tuto aproximaci.
\end{definice}
\begin{lemma}[]
Efektivní neoddělitelnost je silnější než rekurzivní neoddělitelnost
\end{lemma}
\begin{proof}
Sporem. Zvolme $W_x=M$ a $W_y=\overline{M}$, kde $M$ je rekurzivní množina vyvracející rekurzivní neoddělitelnost. Funkce dokazující efektivní ne\-od\-dě\-li\-tel\-nost by 
musela nelézt bod mimo $M \cup \overline M$, což nelze.
\end{proof}
\begin{lemma}[]
Existuje dvojice rekurzivně spočetných disjunktních množin $A$, $B$ taková, že $A$, $B$ jsou rekurzivně neoddělitelné, ale nejsou efektivně neoddělitelné.
\end{lemma}
\begin{proof}
Těžký.
\end{proof}
\begin{veta}[Existence efektivně neoddělitelné dvojice]
Existují disjunktní rekurzivně spočetné množiny $A$ a $B$, které jsou efektivně neoddělitelné.
\end{veta}
\begin{proof}
Definujeme:
\begin{equation}
A=\{x:\varphi_x(x)\simeq 0\} \\
B=\{x:\varphi_x(x)\simeq 1\}
\end{equation}

$A$ a $B$ jsou zřejmě disjunktní a rekurzivně spočetné. Podle s-m-n věty existuje PRF $\alpha$ taková, že
\begin{equation}
\varphi_{\alpha(x,y)}(w)\simeq \left\{\begin{array}{ll}
	1 & \qquad \mbox{$w$ padne dříve do $W_x$ než do $W_y$} \\
	0 & \qquad \mbox{$w$ padne dříve do $W_y$ než do $W_x$} \\
	\uparrow & \qquad w \notin W_x \cup W_y
	\end{array}
	\right. %}
\end{equation}
Prostou diagonalizací nalezneme bod, na kterém musí $\varphi_{\alpha(x,y)}$ divergovat, pro\-to\-že jinak bychom došli ke sporu. Divergence $\alpha$ ale znamená, že 
daný bod leží mimo $W_x \cup W_y$.

Formálně. Co udělá $\varphi_{\alpha(x,y)}(\alpha(x,y))$? Kdyby $\alpha(x,y)$ padlo do $W_x$, potom zřejmě padne dříve do $W_x$ než do $W_y$, 
$\varphi_{\alpha(x,y)}(\alpha(x,y))$ by zakonvergovalo a vrátilo $1$ a tedy by muselo $\alpha(x,y)$ padnout do $B$. To nelze. 
Symetricky se ukáže, že $\alpha(x,y)$ nemůže padnout do $W_y$. Tedy padne mimo tyto dvě množiny.
\end{proof}
\begin{definice}[1-úplnost dvojic]
Disjunktní dvojice rekurzivně spočetných množin $A$, $B$ je $1$-úplná, jestliže pro libovolnou disjunktní dvojici rekurzivně spočetných množin
$C$, $D$ existuje prostá ORF $f$ taková, že 
\begin{eqnarray}
x \in C & \Leftrightarrow & f(x) \in A \\
x \in D & \Leftrightarrow & f(x) \in B \\
x \notin C \cup D & \Leftrightarrow & f(x) \notin A \cup B 
\end{eqnarray}
Značíme $(C,D)\leq_1 (A,B)$.
\end{definice}
\begin{veta}[Dvojná forma věty o rekurzi]
Pro libovolné ORF $f$, $g$ existují $m$ a $n$ takové, že 
\begin{eqnarray}
\varphi_m=\varphi_{f(m,n)} \qquad 
\varphi_n=\varphi_{g(m,n)} 
\end{eqnarray}
Obecnější znění: pro libovolné ORF $f$, $g$ obě $k\!+\!2$ proměnných existují PFR $\omega_1$, $\omega_2$ obě $k$ proměnných takové, že 
\begin{eqnarray}
\varphi_{\omega_1(y_1,\ldots,y_k)}=\varphi_{f(\omega_1(y_1,\ldots,y_k),\omega_2(y_1,\ldots,y_k),y_1,\ldots,y_k)} \\
\varphi_{\omega_2(y_1,\ldots,y_k)}=\varphi_{g(\omega_1(y_1,\ldots,y_k),\omega_2(y_1,\ldots,y_k),y_1,\ldots,y_k)}
\end{eqnarray}
\end{veta}
\begin{proof}
Mějme $\varphi_{f(x,y)}$, pomocí věty o rekurzi dostaneme funkci $\alpha$ takovou, že $\varphi_{f(\alpha(y),y)}=\varphi{\alpha(y)}$.
Vezmeme $\varphi_{g(\alpha(y),y)}$, aplikujeme na $g$ větu o rekurzi a dostáváme $n$ takové, že $\varphi_n=\varphi_{g(\alpha(n),n)}$.
Nyní stačí volit $m=\alpha(n)$.

Jinými slovy, nalezneme funkci $\alpha$, která nám bude počítat pevné body v závilosti na druhé proměnné. Potom opětovnou aplikací věty o rekurzi 
získáme pevný bod této funkce. Jako $m$ volíme hodnotu $\alpha$ v pevném bodě.
\end{proof}
\begin{veta}[]
$1$-úplné dvojice rekurzivně spočetných množin jsou právě efektivně neoddělitelné dvojice rekurzivně spočetných množin.
\end{veta}
\begin{proof}
1-úplnost $\Rightarrow$ efektivní neoddělitelnost

Mějme $(A,B)$ efektivně neoddělitelné (s funkcí $f$, která to dokazuje), $(C,D)$ 1-úplná, tedy platí $(A,B)\leq_1 (C,D)$ (via $h$). 
Vezmeme vzory $W_x$ a $W_y$ při $h$, aplikujeme $f$ a opět aplikujeme $h$.


efektivní neoddělitelnost $\Rightarrow$ 1-úplnost 

Nechť $(A,B)$ jsou efektivě neoddělitelné, tj. existuje ČRF $f$, která to do\-ka\-zu\-je. Budeme hledat dvojici ORF funkcí $\omega_1$, $\omega_2$ takové, že
\begin{eqnarray}
W_{\omega_1(x)}=\left\{\begin{array}{ll}
	A \cup \{f(\omega_1(x),\omega_2(x))\} & \qquad x \in D \\
	A & \qquad x \notin D 
	\end{array}\right. %}
\end{eqnarray}
\begin{eqnarray}
W_{\omega_2(x)}=\left\{\begin{array}{ll}
	B \cup \{f(\omega_1(x),\omega_2(x))\} & \qquad x \in C \\
	B & \qquad x \notin C 
	\end{array}\right. %}
\end{eqnarray}
Snadno se nahlédne, že potom platí:
\begin{eqnarray}
x\notin C \cup D \Rightarrow \left.\begin{array}{l}
	W_{\omega_1(x)=A} \\
	W_{\omega_2(x)=B} 
	\end{array}\right\}
	\Rightarrow f(\omega_1(x),\omega_2(x)) \notin A \cup B
\end{eqnarray}
\begin{eqnarray}
x\in C \Rightarrow x \notin D \Rightarrow \begin{array}{l}
	W_{\omega_1(x)=A} \\
	W_{\omega_2(x)=B \cup \{f(\omega_1(x),\omega_2(x))\}}
	\end{array}
\end{eqnarray}
Kdyby $f(\omega_1(x),\omega_2(x)) \notin A$, potom by $W_{\omega_1(x)},W_{\omega_2(x)}$ byly korektní nadobaly množin $A$ a $B$, tedy by funkce $f$ na jejich indexech 
musela vracet nový bod, tj. 
\begin{eqnarray}
f(\omega_1(x),\omega_2(x)) \notin W_{\omega_1(x)} \cup W_{\omega_2(x)},
\end{eqnarray}
ale to je spor, protože 
$f(\omega_1(x),\omega_2(x)) \in W_{\omega_2(x)}$. Tedy platí $f(\omega_1(x),\omega_2(x)) \in A$.

Analogicky se ukáže případ $x \in D$.

Zbývá ukázat konstrukci funkcí $\omega_1$ a $\omega_2$. Ty dostaneme pomocí dvojné formy věty o rekurzi.
\begin{eqnarray}
W_{\alpha(y_1,y_2,x)}&=&\left\{\begin{array}{ll}
	A \cup \{f(y_1,y_2)\} & x \in D \\
	A & x \notin D 
	\end{array}\right. %} 
	\\
W_{\beta(y_1,y_2,x)}&=&\left\{\begin{array}{ll}
	B \cup \{f(y_1,y_2)\} & x \in C \\
	B & x \notin C 
	\end{array}\right. %}
\end{eqnarray}
\end{proof}
\section{Gödelovy věty}
\begin{veta}[Gödelova věta o neúplnosti - 1. část]
V rozumných teoriích je množina dokazatelných a vyvratitelných formulí efektivně neoddělitelná dvojice.
\end{veta}
\begin{definice}[Základní aritmetická síla]
Jazyk prvního řádu:

$\overline{0}$ - numerál pro nulu

$\overline{1}$ - numerál pro jedničku (aby neexistoval jednoprvkový model)

$+, \times$ - funkční symboly

konečně mnoho axiomů 
\end{definice}

\begin{definice}[Axiomatizovatelnost]
Teorie $T$ je axiomatizovatelná, jestliže množina dokazatelných formulí v $T$ je rekurzivně spočetná.
\end{definice}

\begin{veta}[Gödelova věta]
Jestliže teorie $T$ 1. řádu má základní aritmetickou sílu a je bezesporná, pak

\begin{enumerate}
\item
množina formulí dokazatelných v $T$ není rekurzivní
\item
je-li $T$ navíc axiomatizovatelná, pak
\begin{enumerate}
\item existuje uzavřená formule $F$ taková, že $F$ je nerozhodnutelná v $T$
(tj. $T \nvdash F,\; T \nvdash \neg F$)
\item v $T$ nelze dokázat vlastní bezespornost (za nepatrně silnějších předpokladů o teorii $T$).
\end{enumerate}
\end{enumerate}
\end{veta}
\section{Reprezentovatelnost ČRF v teoriích ZAS}
\begin{definice}[Reprezentovatelnost]
ČRF $f$ je reprezentovatelná v teorii $T$, která má základní aritmetickou sílu, jestliže existuje formule $F$ taková, že
\begin{eqnarray}
f(x_1,\ldots,x_n)\simeq y \; \Rightarrow \; \vdash_T F(\overline{x_1},\ldots,\overline{x_n},\overline{y}) \\
\vdash_T F(\alpha_1,\ldots,\alpha_n,\beta) \; \& \; \vdash_T F(\alpha_1,\ldots,\alpha_n,\gamma) \; \Rightarrow \beta=\gamma
\end{eqnarray}
\end{definice}
\begin{veta}[O reprezentovatelnosti]
Každá ČRF je reprezentovatelná v libovolné teorii ZAS, dokonce existuje pro každou ČRF formule, která ji reprezentuje ve všech
teoriích ZAS současně, je to dokonce $\Sigma_1$-formule.
\end{veta}
\begin{proof}
Pomocí Matijasevičovy věty.
\end{proof}
\begin{dusledek}[]
Jsou-li $A$ a $B$ disjunktní rekurzivně spočetné množiny, potom existuje $\Sigma_1$-formule $G$ taková, že 
\begin{eqnarray}
x \in A &\Rightarrow& \vdash_T G(\overline{x}) \\
x \in B &\Rightarrow& \vdash_T \neg G(\overline{x})
\end{eqnarray}
\end{dusledek}
\begin{proof}
Návod:
\begin{equation}
\varphi(x)\simeq \left\{\begin{array}{ll}
	1 & \qquad x \in A \\
	0 & \qquad x \in B \\
	\uparrow & \qquad x \notin A \cup B
	\end{array}
	\right. %}
\end{equation}
\end{proof}
\begin{proof}
Nyní dokážeme Gödelovu větu. Vezmeme $A$, $B$ rekurzivně spočetné, efektivně neoddělitelné. Mějme formuli $G$, která je popisuje ve 
smyslu před\-cho\-zí\-ho lemmatu.
\begin{eqnarray}
A_1 &=& \{x :\ \vdash_T G(\overline{x})\} \quad (A \subseteq A_1) \\ 
B_1 &=& \{x :\ \vdash_T \neg G(\overline{x})\} \quad (B \subseteq B_1)
\end{eqnarray}
Z bezespornosti plyne, že $A_1 \cap B_1=\emptyset$, navíc ani jedna nemůže být rekurzívní, protože by separovala $A,B$ a tedy 
vztah dokazatelnosti v $T$ není rekurzivní.

Přidáme-li navíc předpoklad axiomatizovatelnosti $T$, jsou $A_1, B_1$ rekurzivně spočetné a tedy z předpokladu efektivní neoddělitelnosti
$A,B$ dostáváme, že lze efektivně nalézt bod $k \notin A_1 \cup B_1$. Číslo $k$ je kódem formule, která není dokazatelná v $T$ a od které není v $T$ dokazatelná ani její negace.

Částí $2b$, která patří spíše do matematické logiky, se zde nezabýváme.
\end{proof}
\section{Numerace}
\begin{definice}[Numerace]
Mějme spočetnou třídu funkcí $\mathcal{F}$. Numerací ro\-zu\-mí\-me indexaci funkcí z $\mathcal{F}$, tj. $\{\varphi_i\}_i$.
\end{definice}
\begin{definice}[Vlastnosti numerací] \ 
\begin{itemize}
\item
Numerace je \emph{vyčíslitelná}, jestliže existuje ČRF $\alpha$ taková, že platí 

$\alpha(i,x)  \simeq \varphi_i(x)$.
\item
Numerace je \emph{přípustná}, jestliže existuje ORF $h$ taková, že 

$\varphi_{h(i,j)}=\varphi_i \circ \varphi_j$
\item
Numerace je \emph{hlavní}, jestliže libovolná jiná numerace ČRF je na ni 1-převedilná, tj. existuje prostá ORF $g$: $\varkappa_i=\varphi_{g(i)}$.
\end{itemize}
\end{definice}
\begin{lemma}[]
Lze ukázat, že je-li $\{\varphi_i\}_i$ vyčíslitelná, pak je následující ekvivatelní:
\begin{enumerate}
\item je přípustná;
\item je hlavní;
\item platí pro ni s-m-n věta;
\item je rekurzivně isomorfní nějaké standardní numeraci ČRF vzniklé efektivním očíslováním programů.
\end{enumerate}
\end{lemma}
\begin{veta}[]
Nechť $\mathcal{F}$ je třída ČRF. Potom
\begin{enumerate}
\item $\exists f \in \mathcal{F}\ \exists g \supseteq f\ \; g \notin \mathcal F$
\item $\mathcal F \neq \emptyset$ a neobsahuje žádnou ORF
\item $f \in \mathcal F$, ale pro každé $p\;f \upharpoonright p \notin \mathcal F$
\end{enumerate}
Každá z těchto podmínek implikuje
\begin{math}
\overline{K} \leq_1 G(\mathcal F) = \{x:\varphi_{x} \in \mathcal F\}
\end{math}.
Speciálně to znamená, že $G(\mathcal F)$ není rekursivně spočetná.
\end{veta}
\begin{proof}\ 
\begin{enumerate}
\item Máme $f \in \mathcal F$, máme $g$ ČRF, $g \supseteq f, g \notin \mathcal F$. Chceme nalézt ORF $h$ takovou, že 
\begin{eqnarray}
z \notin K \Rightarrow \varphi_{h(z)}=f \\
z \in K \Rightarrow \varphi_{h(z)}=g 
\end{eqnarray}
Pomocí s-m-n věty:
\begin{eqnarray}
\varphi_{h(z)}(x)\simeq y \Leftrightarrow (f(x)\simeq y) \lor (z \in K\ \&\ g(x)\simeq y)
\end{eqnarray}
Funkce $h$ převádí $\overline{K}$ na $G(\mathcal F)$.

Poznámka: $\varphi_{h(z)}$ je definovaná tak, že pro $z\notin K$ musí platit $f(x)\simeq y$, pro $z \in K$ bude rozšířena o body $g(x)$. Jedná se o 
korektní definici, protože z předpokladů je $g$ rozšířením $f$, tedy nemůže dojít ke kolizi.
\item
Mějme nějakou $f$ z $\mathcal F$, která z předpokladu není ORF (pouze ČRF). Definujeme rekurzivně spočetnou relaci
\begin{eqnarray}
P(z,x,y) \Leftrightarrow (f(x)\simeq y) \lor (z \in K\ \&\ y = 0)
\end{eqnarray}
Vezmeme selektor, tedy prostou ORF $h$.
\begin{eqnarray}
z \notin K &\Rightarrow& \varphi_{h(z)}=f \\
z \in K &\Rightarrow& \varphi_{h(z)} \mbox{totální}
\end{eqnarray}
Opět platí, že $h$ převádí $\overline K$ na $G(\mathcal F)$.

Poznámka: zde vystupuje v roli $g$ z předchozího bodu nulová funkce. Ta ale není rozšířením funkce $f$, tedy musíme postupovat opatrněji, nelze přímo definovat 
funkci $h(x)$ jako v předchozím bodě. 

Místo toho použijeme graf relace (může obsahovat kolize, tedy dvě různá $y$ pro jedno $x$ (a to při $z\in K$)), na grafu vezmeme selektor,
	který existuje podle věty \ref{selektor}. V případě, že $z \in K$, bude tento selektor totální (protože nulová funkce je totální, ale nebude obecně roven nulové funkci). Totální 
	funkce určitě padne mimo $\mathcal F$, protože $\mathcal F$ neobsahuje žádnou ORF.
	V případě $z \notin K$ bude selektor roven funkci $f$, tedy padne do $\mathcal F$.
\item
Mějme $f \in \mathcal F$, s-m-n věta (prostá) ORF $h$.
\begin{eqnarray}
\varphi_{h(z)}(x) \simeq y \Leftrightarrow f(x) \simeq y\ \&\ z \notin K_x
\end{eqnarray}
Poznámka: v případě, že $z \notin K$, je $\varphi_{h(z)}=f$ a tedy padne do $\mathcal F$. V případě, že $z \in K$, je $\varphi_{h(z)}=f\!\!\upharpoonright\!\!p$ pro nějaké $p$ a tedy $\varphi_{h(z)}$ nepadne do $\mathcal F$. Tedy $h(z)$ převádí $\overline K$ na $G(\mathcal F)$.
\end{enumerate}
\end{proof}
\begin{dusledek}[]
Tedy pokud platí, že $G(\mathcal F)$ je rekurzivně spočetná, potom musí $\mathcal F$ s každou $f$ obsahovat i všechna její rozšíření (plyne z podmínky 1) a pro každou
$f$ musí obsahovat nějaký její počáteční úsek (podmínka 3).
\end{dusledek}
\section{Relativní vyčíslitelnost}
\begin{definice}[$B$-ČRF]
$\varphi$ je $B$-ČRF, jestliže existuje $B$-odvození. $A$ je $B$-rekurzivní, jestliže $c_A$ je $B$-ORF. $A$ je $B$-rekurzivně 
spočetná, jestliže $A$ je definiční obor $\alpha$, kde $\alpha$ je nějaká $B$-ČRF.
\end{definice}
\begin{definice}[String]
String (řetízek) je konečná posloupnost nul a jedniček. Označení
\begin{eqnarray}
\sigma \ast \tau  && \mbox{konkatenace} \\
\sigma \subseteq \tau && \sigma \mbox{ je prefixem }\tau \\
\sigma \subseteq B && \sigma \mbox{ je prefixem } c_B
\end{eqnarray}
\end{definice}
\begin{definice}[Funkcionální vlastnost]
Rekurzivně spočetná množina $\Phi$ má \emph{funkcionální vlastnost}, jestliže
\begin{eqnarray}
\left<\sigma, x, y\right> \in \Phi \; \land \; \left<\overline{\sigma},x,\overline{y}\right> \in \Phi \; \land \; \sigma \subseteq \overline{\sigma} \Rightarrow y=\overline{y}
\end{eqnarray}
\end{definice}
\begin{definice}[Částečně rekurzivní funkcionál]
Částečně rekurzivní funk\-cio\-nál $\Phi$ je rekurzivně spočetná množina s funkcionální vlastností. Částečně
rekurzivní funkcionál určuje zobrazení (parciální):
\begin{eqnarray}
\Phi(\sigma)(x)\simeq y &\Leftrightarrow& \left<\sigma,x,y\right> \in \Phi \\
\Phi(\tau)(x)\simeq y &\Leftrightarrow& \mbox{ pro nějaké } \sigma \subseteq \tau \; \Phi(\sigma)(x)\simeq y \\
\Phi(B)(x)\simeq y &\Leftrightarrow& \mbox{ pro nějaké } \sigma \subseteq B \; \Phi(\sigma)(x)\simeq y
\end{eqnarray}
\end{definice}
\begin{lemma}[Regularizační funkce]
Existuje PRF $\varrho$ taková, že pro libovolné $z$ platí, že $W_{\varrho(z)}$ má funkcionální vlastnost a navíc platí, že je-li $W_z$ již regulární, potom $W_z=W_{\varrho(z)}$.
\end{lemma}
\begin{proof}
Idea. Efektivně generujeme $W_z$ a každý prvek kontrolujeme, zda není v kolizi s nějakým již přidaným do $W_{\varrho(z)}$.
\end{proof}
\begin{definice}[Numerace částečně rekurzivních funkcionálů] \ 

$\Phi_i(B)(x)\simeq y \;\Leftrightarrow\; \exists \sigma \; \left(\left<\sigma,x,y\right>\in W_{\varrho(i)} \land \sigma \subseteq B\right)$
\end{definice}
\begin{definice}[B-rekurzivita]
$A$ je $B$-rekurzivní (značíme $A \leq_T B$), jestliže pro nějaké $i$ platí $A=\Phi_i(B)$, tj. $\forall x \;c_A(x)=\Phi_i(B)(x)$

$A$ je $B$-rekursivně spočetná, jestliže $A=dom(\Phi_i(B))$.
\end{definice}
\begin{definice}[Značení]\ 

$\Phi_{i,s}(\sigma)(x)$ je výsledek za $s$ kroků.

$\Phi_{i,s}(\sigma)(x)\downarrow \;\Leftrightarrow\; \exists \tau,y\left(\left<\tau,x,y\right> \in W_{\varrho(i),s} \land length(\tau)\leq s \land \tau \subseteq \sigma \right)$ 

$\Phi_{i,s}(\sigma)(x)\simeq y\;\Leftrightarrow\; \exists \tau\left(\left<\tau,x,y\right> \in W_{\varrho(i),s} \land length(\tau)\leq s \land \tau \subseteq \sigma \right)$ 
\end{definice}
\begin{definice}[Numerace B-r.s.]\ 

$W^B_z = dom(\Phi_z(B))$

$W^B_{z,s} = dom(\Phi_{z,s}(B))$
\end{definice}
\begin{veta}[]
$\Phi_z(B)(x_1,\ldots,x_n)$ je univerzální funkce pro třídu všech $B$-ČRF $k$ proměnných a platí s-m-n věta. To znamená, že existují 
PRF $\overline{s_m}$ takové, že pro libovolnou $B$ platí:
\begin{eqnarray}
\Phi_{\overline{s_m}(z,x_1,\ldots,x_m)}(B)(y_1,\ldots,y_n) \simeq \Phi_z(B)(x_1,\ldots,x_m,y_1,\ldots,y_n).
\end{eqnarray}
\end{veta}
\begin{proof}
Důkaz pro jednoduchost jenom pro $m=n=1$. Vypočítáme pomocnou rekurzivně spočetnou množinu
\begin{eqnarray}
W=\{\left<\sigma,y,t\right>:\left<\sigma,\left<x,y\right>,t\right> \in W_{\varrho(z)}\}
\end{eqnarray}
Tedy máme ČRF $\alpha$
\begin{eqnarray}
\alpha(z,x,w)\!\!\downarrow \;\Leftrightarrow\; w=\left<\sigma,y,t\right> \land \left<\sigma,\left<x,y\right>,t\right> \in W_{\varrho(z)}
\end{eqnarray}
Zbývá ukázat:
\begin{eqnarray}
\Phi_{\overline{s}_1(z,x)}(B)(y)\simeq \Phi_z(B)(x,y) 
\end{eqnarray}
Nechť
\begin{eqnarray}
\alpha(z,x,w) \simeq \varphi_{s_2(a,z,x)}(w)
\end{eqnarray}
Protože $W_{\varrho(z)}$ je regulární, je regulární i $W_{s_2(a,z,w)}$.
\begin{eqnarray}
\overline{s}_1(z,x) = s_2(a,z,x) \\
W_{\varrho(s_2(a,z,x))}=W_{s_2(a,z,x)}
\end{eqnarray}
\end{proof}

Jelikož s-m-n věta platí absolutně (stejnoměrně), dostáváme okamžitě platnost věty o rekurzi.
\begin{veta}[O rekurzi II]
Nechť $f$ je ČRF dvou proměnných, potom existuje PRF $p$ taková, že $\forall B \forall x \; \Phi_{f(p(y),y)}(B)(x)\simeq \Phi_{p(y)}(B,x)$.
\end{veta}
\section{Operace skoku}
\begin{definice}[Relativizovaný halting problem]
\begin{eqnarray}
A' = \{x : \Phi_x(A)(x)\downarrow\} = \{x : x \in W_x^A\} 
\end{eqnarray}
Dále induktivně definujeme
\begin{eqnarray}
A^0 &=& A \\
A^{n+1}&=&(A^{n})'
\end{eqnarray}
\end{definice}
\begin{veta}[]
\begin{enumerate}
\item $A'$ je $A$-rekursivně spočetná
\item $A' \nleq_T A$  ($A'$ není $A$-rekurzivní)
\item $B$ je $A$-rekursivně spočetná $\Leftrightarrow \; B \leq_1 A'$
\item $A$ je $B$-rekrusivně spočetná a $B \leq_T C \Rightarrow A$ je $C$-rekurzivně spočetná
\item $A \leq_T B \Leftrightarrow A'\leq_1 B'$
\item $A \equiv_T B \Leftrightarrow A'\equiv_1 B'$
\end{enumerate}
\end{veta}
\begin{proof}
\begin{enumerate}
\item z definice $A'=\{x: \Phi_x(A)(x) \downarrow\}$
\item Cantorova diagonální metoda
\item $\Leftarrow$  zřejmé

$\Rightarrow$  stejně jako u $K$
\begin{eqnarray}
\Phi_a(A)(x,w) \downarrow \Leftrightarrow x \in B \ldots\qquad \mbox{(použití fiktivní proměnné)}
\end{eqnarray}

\item $A$ je definičním oborem nějaké $B$-ČRF $f$, $B$ je rekurzivní v $C$ (via $g$), tedy s pomocí $f$ a $g$ dostáváme, že 
$A$ je definičním oborem nějaké $C$-ČRF.
\begin{eqnarray}
A = dom(\Phi_z(B)),\; B \leq_T C \Rightarrow A = dom(\Phi_{\mbox{něco}}(C))
\end{eqnarray}
\item Nechť $A \leq_T B$. Potom z faktu, že $A'$ je $A$-rekurzivně spočetná, a $A \leq_T B$ dostáváme, že $A'$ je $B$-rekurzivně spočetná (podle bodu $4$ této věty). 
A protože $B'$ je úplná pro $B$-rekurzivně spočetné, dostáváme okamžitě $A' \leq_1 B'$.

Opačný směr. Mějmě $A' \leq_1 B'$. Zřejmě platí, že $A$ i $\overline A$ jsou $A$-rekurzivní, tím spíše jsou $A$-rekurzivně spočetné.
Tedy jsou obě 1-převedilné na $A'$. Ale dle předpokladu $A' \leq_1 B'$ a tedy $A \leq_1 B'$ i $\overline A \leq_1 B'$ a tedy dle relativizované 
Postovy věty je $A$ $B$-rekurzivní.
\item Plyne okamžitě z bodu 5.
\end{enumerate}
\end{proof}
\begin{dusledek}[]
Operace skoku je korektně definována na T-stupních. Tedy platí
\begin{eqnarray}
A \equiv_T B \Rightarrow A' \equiv_1 B'\ \ (\Rightarrow A' \equiv_T B')
\end{eqnarray}
Lze tedy definovat skok stupně $a$ jako stupeň obsahující skok libovolného prvku stupně $a$.
\end{dusledek}
\begin{veta}[Stejnoměrnost]
Existuje $z_0$ takové, že $A'=W_{z_0}^A$ pro všechna $A$.
\end{veta}
\begin{proof}
\begin{eqnarray}
W_{z_0}=\{\left<\sigma,x,y\right>:\left<\sigma,x,y\right> \in W_{\varrho(x)}\} 
\end{eqnarray}
Protože $W_{\varrho(x)}$ je regulární, je i $W_{z_0}$ je regulární a tedy $W_{z_0}=W_{\varrho(z_0)}$.
\begin{eqnarray}
\nonumber
x \in A'& \Leftrightarrow & \Phi_x(A)(x)\!\!\downarrow\ \Leftrightarrow\ \exists \sigma\!\subseteq\!A\ (\Phi_x(\sigma)(x)\!\!\downarrow) \Leftrightarrow \\
\nonumber
	& \Leftrightarrow & \exists\sigma\!\subseteq\!A \exists y\ (\Phi_x(\sigma)(x)\simeq y) \Leftrightarrow \\
\nonumber
	& \Leftrightarrow & \exists \sigma\!\subseteq\!A \exists y\ (\left<\sigma,x,y\right> \in W_{\varrho(x)}) \Leftrightarrow \\
\nonumber
	& \Leftrightarrow & x \in W_{z_0}^A
\end{eqnarray}
Tato složitě vypadající konstrukce je přirozeným zobecněním definice množiny $K=\{x:x \in W_x\}$. Akorát nyní konstruujeme množinu trojic obsahujících 
aproximaci orákula $\sigma$, proměnné $x$ a $y$. Navíc musíme aplikovat regularizační funkci $\varrho$. Jinak zapsáno 
\begin{eqnarray}
W_{z_0}=\{w:w \in W_{\varrho((w)_{3,2})}\}.
\end{eqnarray}

\end{proof}
\begin{lemma}[]
$\emptyset' \equiv K$
\end{lemma}
\begin{proof}
\begin{enumerate}
\item $K$ je rekurzivně spočetná a tedy $K \leq_1 \emptyset'$
\item $\emptyset' = \{x: x\in W_x^{\emptyset}\} \Rightarrow \emptyset'$ je rekurzivně spočetná v $\emptyset$, ale $\emptyset$ je rekurzivní a tedy
$\emptyset'$ je absolutně rekurzivně spočetná a tedy je $\leq_1 K$, protože $K$ je 1-úplná. 
\end{enumerate}
\end{proof}
\section{Limitní vyčíslitelnost}
\begin{definice}[Limitní vyčíslitelnost]
Množina $M$ je limitně vyčíslitelná, jestliže existuje ORF $h$ taková, že $M(x) \simeq \lim_s h(x,s)$.

Funkce $f$ je limitně vyčíslitelná, jestliže existuje ORF $h$ taková, že $f(x) \simeq \lim_s h(x,s)$.
\end{definice}
\begin{veta}[]
$M$ je rekurzivní v $\emptyset'$ právě, když $M$ je limitně vyčíslitelná.
\end{veta}
\begin{proof}\ 

"$\Rightarrow$" 
$M \leq_T \emptyset' \Rightarrow \exists z \; M(x)=\Phi_z(\emptyset')(x)$. Tedy existuje program $z$, který z $\emptyset'$ počítá $M$. K tomu používá nerekurzivní
orákulum, které ale můžeme efektivně generovat. Definujeme
\begin{eqnarray}
h(x,s)=\left\{\begin{array}{ll}
	\Phi_{z,s}(\emptyset'_s)(x) & \mbox{jestliže } \Phi_{z,s}(\emptyset'_s)(x)\!\!\downarrow \\
		\\
	0 & \mbox{jinak}
	\end{array}\right.%}
\end{eqnarray}

Ukážeme, že $M(x)=\lim_s h(x,s)$. Je-li pro dané $x$ $M(x)$ definováno, znamená to, že $\Phi_z(\emptyset')(x)\!\!\downarrow$ a tedy
existuje počáteční úsek $\sigma \subseteq \emptyset'$, pro který platí $\Phi_z(\sigma)(x)\!\!\downarrow$.

Z $\sigma \subseteq \emptyset'$ plyne, že existuje $t_0$ takové, že $\forall t\!>\!t_0\ \ \emptyset'_{t_0}\!\!\upharpoonright\!lh(\sigma)=\emptyset'_{t}\!\!\upharpoonright\!lh(\sigma)$, tedy od 
určitého kroku $t_0$ počáteční úsek aproximace $\emptyset'$ o délce řetízku $\sigma$ již pravdivě aproximuje $\emptyset'$.

Dále existuje $t_1$ takové, že $\Phi_{z,t_1}(\sigma)(x)\!\!\downarrow$, tedy vlastní výpočet se $\sigma$ jako aproximací orákula konverguje za $t_1$ kroků.

Položme $s_0=\max(t_0,t_1)$. Od kroku $s_0$ už nemůže dojít ke změně, neboť aproximace (v tuto chvíli již pravdivá) se již nemění a výpočet již zakonvergoval.

"$\Leftarrow$" 
Nechť $M(x)$ je limitně vyčíslitelná. Chceme s pomocí $\emptyset'$ vyčíslovat $M$. While cyklem najdeme 
nejmenší $s_0$ takové, že $\forall s\geq s_0\; h(x,s)=h(x,s_0)$. Jedná se o otázku rekurzivní v $\emptyset'$. Tedy máme $\mu_{s_0}(\emptyset'\mbox{-rekurzivní otázka})$. To je $\emptyset'$-ČRF, navíc $M(x)$ je totální, tedy tato minimalizace je $\emptyset'$-ORF. Z toho plyne, že
$M \leq_T \emptyset'$.
\end{proof}

V předchozí větě bylo podstatné, že $M$ je totální. Nyní tvrzení pro parciální funkce.

\begin{veta}[]\ 
\begin{enumerate}
\item Jestliže $f$ je ORF, potom $\lim_s f(x,s)$ je $\emptyset'$-ČRF.
\item Jestliže $F$ je $\emptyset'$-ČRF, pak existuje ORF $f$ taková, že $F(x)\simeq lim_s f(x,s)$.

Přesněji: $\Phi_z(\emptyset')(x) \simeq \lim_s h(z,x,s)$ pro nějakou ORF $h$.
\end{enumerate}
\end{veta}
\begin{proof}

\begin{enumerate}
\item Provedeme stejnou minimalizaci $s$ jako v důkazu předchozí věty. Tentokrát ale nemusí minimalizace konvergovat.
\item V tomto případě použijeme stejnou ideu, ale musíme dát pozor, aby $F(x)\!\!\downarrow$. Naším cílem bude stabilizace celého výpočtu. Definujeme
\begin{eqnarray}
h_0(z,x,s)=\left\{\begin{array}{ll}
	\left<\sigma,x,y\right> & \mbox{jestliže } \left<\sigma,x,y\right> \in W_{\varrho(z),s}\ \&\ \sigma \subseteq \emptyset'_{s} \\
		\\
	s+1 & \mbox{jinak}
	\end{array}\right. %}
\end{eqnarray}

Nelze pouze vydělit $y$ a stabilizovat $y$ (výsledek výpočtu), je třeba stabilizovat celý výpočet, protože se může stát, že se mění aproximace orákula.
\begin{eqnarray}
h(z,x,s)=\left\{\begin{array}{ll}
	(h_0(x,z,s))_{3,3} &  \mbox{jestliže } h_0(z,x,s)=h_0(z,x,s+1) \\
		\\
	s & \mbox{jinak}
	\end{array}\right. %}
\end{eqnarray}
$\lim_s h(z,x,s)$ existuje právě, když existuje $\lim_s h_0(z,x,s)$. 

$F(x)\!\!\downarrow\ \Rightarrow\ \Phi_z(\sigma)(x)\!\!\downarrow$ pro nějaké $\sigma \subseteq \emptyset'$.

Tedy $\lim_s h(z,x,s) = F(x)$.

Jestliže existuje $\lim_s h(z,x,s)$, potom existuje $\lim_s h_0(z,x,s)$ a tedy máme nějaké $\left<\sigma,x,y\right>$ a $s_0$ takové, že 
$\forall s\geq s_0 $ je $\left<\sigma,x,y\right>$ stabilní. Z toho plyne $\Phi_{z,s}(\sigma)(x) \simeq y\ \&\ \sigma \subseteq \emptyset'_s$. Jinými slovy
$\left<\sigma,x,y\right>$ a $s_0$ je limitní výpočet a $\Phi_z(\emptyset')(x)\!\!\downarrow \&=y$.
\end{enumerate}
\end{proof}

Ukažme si případ, který demonstruje, proč je potřeba trvat na stabilizaci celého výpočtu a nejen výsledku.
Snadno vytvoříme program $z$ takový, že 
\begin{eqnarray}
\Phi_z(A)(x)\!\!\downarrow\ \Leftrightarrow\ \emptyset'\setminus A\neq \emptyset\quad (\mbox{a }\Phi_z(A)(x)\!\!\downarrow\ \Rightarrow \mbox{výsledek}=0)
\end{eqnarray}

Program pracuje tak, že postupně generuje $\emptyset'$ a pro každý nový prvek $w$ se ptá, zda $w \in A$. V okamžiku, kdy nějaký takový nalezne,
	zastaví se a vydá $\emptyset$.

Je zřejmé, že $\Phi_z(\emptyset')(\ldots)\!\!\uparrow$, zatímco $\forall s\ \Phi_z(\emptyset'_s)(\ldots)\!\!\downarrow$. Plyne to z toho, že žádná aproximace $\emptyset'$ 
nemůže zajistit, aby program nenalezl prvek, který do této aproximace nepatří. Tedy neexistuje limitní výpočet, ale prostou stabilizací výsledku (vždy $\emptyset$) bychom dostali, že 
limita existuje, což by bylo špatně.

\begin{veta}[]
Pro každé $n$ existuje ORF $h$ taková, že 
\begin{eqnarray}
\Phi_z(\emptyset^{n+1})(x) \simeq \lim_{s_0}\ldots\lim_{s_n} h(z,x,s_0,\ldots,s_n),
\end{eqnarray}
kde všechny limity $s_1,\ldots,s_n$ existují, limita pro $s_0$ nemusí.
\end{veta}

\section{Aritmetická hierarchie}
\subsection{Definice a základní vlastnosti}
\begin{definice}[$\Sigma_n, \Pi_n$ prefix]
$\Sigma_n$ (resp. $\Pi_n$) prefix je skupina kvantifikátorů, která má $n$ skupin stejných kvantifikátorů, sousední skupiny se střídají a začíná $\exists$ (resp. $\forall$).
\end{definice}
\begin{definice}[]
Predikát patří do třídy $\Sigma_n$ (resp. $\Pi_n$), jestliže lze vyjádřit ve tvaru $\Sigma_n$ prefix na rekurzivní základ (resp. $\Pi_n$ prefix).
\end{definice}
\begin{lemma}[]
$\Sigma_0 = \Pi_0$ jsou právě rekurzivní predikáty.
\end{lemma}
\begin{proof}
Zřejmé.
\end{proof}
\begin{definice}[]
Prefikát je \emph{aritmetický}, jestliže jej lze vyjádřit pomocí spojek predikátového počtu nad rekurzivními relacemi.
\end{definice}
\begin{lemma}[]
Aritmetické predikáty jsou právě všechny predikáty ve třídách $\Sigma_n, \Pi_n, n\in \mathbb{N}$.
\end{lemma}
\begin{proof}
$\Leftarrow$ Zřejmé.

$\Rightarrow$ Úprava logického výrazu do prenexního tvaru.
\end{proof}
\begin{lemma}[Základní vlastnosti] \ 

\begin{enumerate}
\item $A \in \Sigma_n \Leftrightarrow \overline A \in \Pi_n$
\item $\Sigma_n \cup \Pi_n \subseteq \Sigma_m \cap \Pi_m$ pro $m>n$.
\item $A \leq_m B$ a $B \in \Sigma_n$ (resp. $\Pi_n$), potom $A$ je $\Sigma_n$ (resp. $\Pi_n$).
\end{enumerate}
\end{lemma}
\begin{proof}\ 
\begin{enumerate}
\item Zřejmé.
\item Kvantifikací přes fiktivní proměnnou přidáme potřebný kvantifikátor buď na konec nebo na začátek.
\item Transformace převodní funkcí nezmění aritmetickou složitost.
\end{enumerate}
\end{proof}

\begin{veta}[O numeraci, univerzálním predikátu]
Pro každou třídu $\Sigma_n$ (resp. $\Pi_n$) pro $n\geq1$ existuje univerzální $\Sigma_n$ (resp. $\Pi_n$) predikát.
\end{veta}
\begin{proof}
Nejprve případ $\Sigma_n$, kde $n$ je liché. Máme predikát tvaru $\exists\forall\ldots\exists(\mbox{rek})$. Kvantifikátory kromě posledního odřízneme. 
Dostáváme $\Sigma_1$ predikát, tj. re\-kur\-ziv\-ně spočetný predikát. Pro něj existuje univerzální predikát $\exists T_n(e,x,\ldots)$. Nyní vrátíme kvantifikátory
$\exists\forall\ldots\exists T_n(e,x,\ldots)$.

Případ pro $\Sigma_n$ a $n$ sudé. Po odříznutí dostáváme $\forall(\mbox{rek})$, negací $\exists T_n$, o\-pě\-tov\-nou negací $\forall \neg T_n$.

Pro případ $\Pi_n$ analogicky (obráceně).
\end{proof}
\begin{dusledek}[]
Pro $n \geq 1$ platí $\Sigma_n \setminus \Pi_n \neq \emptyset$.
\end{dusledek}
\begin{proof}
Máme univerzální $\Sigma_n$ predikát $U(e,x) \in \Sigma_n$. Kdyby $U(e,e) \in \Pi_n$, potom by $\neg U(e,e) \in \Sigma_n$, vezmeme jeho index $a$ a dosadíme $e=a$. Dostáváme spor ($U(a,a)\Leftrightarrow \neg U(a,a)$), $U(e,e)$ tedy musí být mimo $\Pi_n$.
\end{proof}
\begin{veta}[O hierarchii]\ 

\begin{enumerate}
\item $A$ je rekurzivně spočetná v $\emptyset^{(n)} \Leftrightarrow A \in \Sigma_{n+1}$
\item $\emptyset^{n+1}$ je $\Sigma_{n+1}$-úplná
\item $B\leq_T \emptyset^{(n)} \Leftrightarrow B \in \Sigma_{n+1}\cap \Pi_{n+1}$
\end{enumerate}
\end{veta}
\begin{proof}\ 
\begin{enumerate}
\item Pro $n=0$ to víme. Indukcí pro všechna $n$. Nechť $A \in \Sigma_{n+1}$, tedy $A$ je tvaru $\exists (\Pi_n)$. Negace toho $\Pi_n$ je $\Sigma_n$ a dle indukčního předpokladu je tedy rekurzivně
spočetná v $\emptyset^{(n-1)}$. Z toho plyne $\leq_1 \emptyset^{(n)} \Rightarrow \leq_T \emptyset^{(n)} \Rightarrow$ původní predikát (před negací) je 
$\leq_T \emptyset^{(n)}$. Dostáváme $\exists(\mbox{rekurzivní v }\emptyset^{(n)})$, což je rekurzivně spočetné v $\emptyset^{(n)}$.

Nyní nechť $A$ je rekurzivně spočetná v $\emptyset^{(n)}$, tedy $A$ je definiční obor nějaké $g$, která je $\emptyset^{(n)}$-ČRF. Dle věty o limitní vyčíslitelnosti je 
$g \simeq \lim_s f(x,s)$, kde $f$ je $\emptyset^{(n-1)}$-ORF.

$x\in A \Leftrightarrow g(x)\!\!\!\downarrow\ \Leftrightarrow \exists s_0 \forall s\!\!\!\geq\!\!\!s_0\ (f(x,s)=f(x,s_0))$

Výraz v závorkách je rekurzivní v $\emptyset^{(n-1)}$ a tedy 
podle bodu 3 této věty patří do $\Sigma_n \cap \Pi_n$. Dostáváme tedy $\exists \forall \Pi_n$, což je $\exists \Pi_n$, tedy $\Sigma_{n+1}$.
\item Plyne z bodu 1.
\item Plyne z bodu 1 pomocí Postovy věty.
\end{enumerate}
Poznámka: v důkazu bodu 1 se odvoláváme na bod 3, který naopak dokazujeme z bodu 1. Nejde ale o nekorektní důkaz, protože v bodě 1 použijeme platnost bodu
3 pro $n-1$ a důkaz stavíme induktivně, tedy platnost pro $m<n$ už máme zaručenu.
\end{proof}
\begin{veta}[O úplnosti]
Pro $n \geq 1$ je $\emptyset^{(n)}$ $\Sigma_n$-úplná
\end{veta}
\begin{proof}
Nechť $M$ je $\Sigma_n$, potom $M$ je $\emptyset^{(n-1)}$-rekurzivně spočetná a dle vlastnosti operace skoku je $\leq_1 \emptyset^{(n)}$.
\end{proof}
\subsection{$\Sigma_2$ a $\Pi_2$ úplné množiny}
\begin{veta}[Tot je $\Pi_2$-úplná]
Tot$=\{x:\varphi_x \mbox{ je totální}\}$ je $\Pi_2$-úplná.
\end{veta}
\begin{proof}
Tot je zřejmě $\Pi_2$. Mějmě $B \in \Pi_2$, tedy 
\begin{eqnarray}
x \in B \Leftrightarrow \forall y \exists s\ Q(x,y,s).
\end{eqnarray}

Chceme nalézt ORF $f$ takovou, že 
\begin{eqnarray} 
x \in B \Leftrightarrow f(x) \in Tot \Leftrightarrow \varphi_{f(x)} \mbox{ je totální}
\end{eqnarray}
Zkonstruujeme funkci, která bude pro $y$ vracet $s$ ($\Sigma_1$ svědka).
\begin{eqnarray}
\alpha(x,y) \simeq \mu_s Q(x,y,s) \simeq \Psi_2(a,x,y) \simeq \Psi_1(s_1(a,x),y) \simeq \varphi_{f(x)}(y)
\end{eqnarray}
Je zřejmé, že $x \in B \Leftrightarrow f(x) \in$ Tot.
\end{proof}
$\Sigma_2$-úplné množiny: $\emptyset^{(2)}$, Fin

$\Pi_2$-úplné množiny: $\overline{\emptyset^{(2)}}$, Tot, Inf
\begin{veta}[Relativizace]
$A$ je $\Sigma^{B}_{n+1} \Leftrightarrow$ $A$ je rekurzivně spočetná v $B^{(n)}$

$A \leq_T B^{(n)} \Leftrightarrow A \in \Sigma^{B}_{n+1} \cap \Pi^{B}_{n+1}$
\end{veta}


\begin{lemma}[]
Fin $= \{x | W_x \mbox{ je končená}\}$ je $\Sigma_2$ úplná.
\end{lemma}
\begin{proof}
Množina je konečná, jestliže má horní závoru, tedy prvek, pro který platí, že všechny větší jsou mimo tuto množinu. 
\begin{eqnarray}
x \in Fin \Leftrightarrow \exists y\ \forall y'\!\!>\!\!y\ \forall s\ \neg(y' \in W_{x,s})
\end{eqnarray}
Mějme libovolnou $A \in \Sigma_2$. Platí
\begin{eqnarray}
x \in A \Leftrightarrow \exists z\ \forall y\ Q(x,z,y).
\end{eqnarray}
Definujeme
\begin{eqnarray}
\alpha(x,z)\!\!\downarrow \Leftrightarrow \forall j\!\leq\!z\ \exists y\ (\neg Q(x,z,y)).
\end{eqnarray}
Podle s-m-n věty:
\begin{eqnarray}
\alpha(x,z)\simeq \varphi_{f(x)}(z)
\end{eqnarray}
\begin{eqnarray}
x \in A \Rightarrow \exists z\ \forall z'\!>\!z\ \varphi_{f(x)}(z')\!\!\uparrow 
\end{eqnarray}
a tedy $W_{f(x)}$ je konečný počáteční úsek.
\begin{eqnarray}
x \notin A \Rightarrow \forall z \varphi_{f(x)}(z)\!\!\downarrow\ \Rightarrow W_{f(x)}=\mathbb{N}
\end{eqnarray}
\end{proof}





















\end{document}