{{Template:TIN064 Skripta}}
*def: Množina **A je 1-převeditelná na B** (značíme $ A \le_1 B$), jestliže existuje prostá ORF *f* taková, že $ x \in A \Leftrightarrow f(x) \in B$.

*def: Množina **A je m-převeditelná na B** (značíme $ A \le_m B$), jestliže existuje (ne nutně prostá) ORF *f* taková, že $ x \in A \Leftrightarrow f(x) \in B$.
*def: Množina *A* je **1-úplná**, jestliže je rekurzivně spočetná a každá rekurzivně spočetná množina je na ní 1-převeditelná

*def: Množina *A* je **m-úplná**, jestliže je rekurzivně spočetná a každá rekurzivně spočetná množina je na ní m-převeditelná

## Užitečné rekurzivně-spočetné množiny ##

Abychom měli na co převádět, hodí se mít nějaké šikovné třídy funkcí.

*def: $W_x$ (x-tá rekurzivně spočetná množina) = $ dom( \varphi_x) = \{ y, \varphi_x(y) \mbox{je definována} \} $

* důležitá definice, $W_x$ už budeme používat skoro pořád!
* $\varphi_x $ je x-tá ČRF

*def: $K = \{x, x \in W_x\}$

* Jinými slovy $\{x, \varphi_x(x) \mbox{je definovana} \}$, tedy $\{x, \psi_1(x,x) \mbox{je definovana}\}$
* $\psi_1$ je univerzální funkce z Kleeneho věty

*def: $K_0 = \{<y, x> |\ y \in W_x\}$

### Vlastnosti množiny K ###

**Věta:** Množina **K** je rekurzivně spočetná, ale není rekurzivní a její doplněk není rekurzivně spočetný

**Důkaz:**

* **K** je rek. spočetná. Jistě existuje ČRF f(x), která bude vyčíslovat $\psi_1(x,x)$ (f zkonstruujeme pomocí substituce atd.), K je definičním oborem f.
* Nechť doplněk **K** je RSM. Pak $\exists x_0 : \bar{K} = W_{x_0}$. Pokud $x_0 \in \bar{K}$, pak $x_0 \in W_{x_0}$, pak $x_0 \in K$ (z definice **K**). Spor.

**Věta:** K je 1-úplná

**Důkaz:**

*K je rekurzivně spočetná viz [definice](TIN064_Vlastnosti_RSM), dále vezmu libovolnou rek. spočetnou množinu $W_x$, vezmu ČRF fci $\alpha(y,x,w)$, popisující x-tou RSM.

* Pro každou rek.spoč. množinu existuje ČRF, jejímž definičním oborem je daná množina
* Proměnná w je fiktivní proměnná – běžný trik pro obejití nulárnosti

*Tedy $\alpha(y,x,w)\downarrow \Leftrightarrow y \in W_x$
*Vyjádřím si alfu pomocí univerzální funkce $\psi_3(a,y,x,w)$

*s-m-n větou $\psi_1(s_2(a,y,x),w)$ ($s_2$ je z Kleeneho věty PRF (tedy i ORF) a prostá) 
*Položme $h(y,x) = s_2(a,y,x)$

*$\forall y \in W_x: \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$

* Zde jsme mohli za $w$ dosadit $h(y, x)$, neboť hodnota $\alpha$ na $w$ nazáleží

*Tedy $W_x$ je 1-převeditelná na K pomocí funkce $h(y,x)$

**EDIT (Ivan)**: Mně to přijde hezčí takto:

* Chceme pro libovolné x ukázat, že $W_x = dom(\varphi_x) \leq_1 K$. Chceme najít prostou ORF h(y) takovou, že $y \in W_x \Leftrightarrow h(y) \in K$, což dle definice K platí, právě když $h(y) \in W_{h(y)} \Leftrightarrow \Psi_1(h(y),h(y)) \downarrow$.
* $\varphi_x(y) \simeq \Psi_1(x,y) \simeq \Psi_2(e,y,w) \simeq \Psi_1(s_1(e,y),w)$. Položme $h(y) \simeq s_1(e,y)$.
* Uměle jsme přidali proměnnou w, nemající vliv na hodnotu funkce. h(y) je prostá ORF, dokonce rostoucí.
* $y \in W_x \Leftrightarrow \varphi_x(y) \downarrow \Leftrightarrow \Psi_1(h(y),w) \downarrow 

\Leftrightarrow \Psi_1(h(y),h(y)) \downarrow \Leftrightarrow h(y) \in K$

* h(y)-tá funkce jedné proměnné je vlastně konstantní, všude definovaná, tedy h(y) musí být v K.

**EDIT (Jindra): Myslím si, že to jde víc jednoduše - bez použití proměnné x uvnitř důkazu (viz následující důkaz):**

**Alternativní důkaz:**

* K je RSM, což je dokázáno v předchozí větě. Pro libovolnou RSM $W_x$ vezměme její popisující ČRF $\varphi_x$.
* Definujme funkci dvou proměnných $\alpha$(y,w) podle předpisu $\alpha$(y,w)$ \downarrow$ = $\varphi_x(y)$.
    * Tato funkce je jistě ČRF, buď tedy $e$ její index.
    * Proměnná $w$ je použita stejně jako v původním důkazu, tedy jako fiktivní proměnná, na jejíž hodnotě výsledná hodnota funkce nezávisí.
* Platí (*): $\alpha(y,w) \simeq \psi_2(e,y,w) \simeq \psi_1(s_1(e,y),w) \simeq \varphi_{s_1(e,y)}(w)$
* Položme $h = s_1(e,y)$.
    * Tato funkce je podle s-m-n věty prostá a rostoucí ve všech proměnných (nám stačí to, že je prostá).
* Potom $y \in W_x

\Leftrightarrow \alpha(y,w)\downarrow
\Leftrightarrow \varphi_{h(y)}(w)\downarrow

\Leftrightarrow \varphi_{h(y)}(h(y))\downarrow
\Leftrightarrow h(y) \in W_{(h(y)}

\Leftrightarrow h(y) \in K$

* První ekvivalence plyne z definice funkce $\alpha$, druhá z řádku označeného (*), další z toho, že w je fiktivní proměnná a tudíž za ní lze dosadit cokoliv, aniž by se změnil výsledek. Předposlední ekvivalenci dostáváme ze vztahu x-té ČRF a x-té RSM a poslední plyne přímo z definice množiny K.

$\Box$

**EDIT (Jindra): Rozdíl mezi původním a alternativním důkazem je v tom, že alternativní důkaz pro každou RSM W *(s indexem x)* hledá funkci h, a pro každou RSM jí taky najde. Důkaz původní dokazuje trochu silnější tvrzení, a to tak, že najde jednu funkci, která je pak převádějící funkcí pro všechny RSM najednou.**

**Věta:** $K_0$ je 1-úplná

**Důkaz:** Převodem $K$ na $K_0$. Předpis může být $f(x) = (x,x)$ - zakóduji x do dvojice (x,x). Je důležité si uvědomit, že ačkoli je f totální a prostá, nemusí se "trefit" do všech bodů množiny napravo.

Množina $K$ souvisí s Halting problémem (viz definice rekurzivně spočetné množiny) – kdyby $K$ byla rekurzivní => by bylo možné díky tomu, že $K$ je 1-převoditelná na $K_0$, rozhodnout halting problém.