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

*def: Množina A je m-převeditelná na B (značíme <math> A \le_m B</math>), jestliže existuje (ne nutně prostá) ORF f taková, že <math> x \in A \Leftrightarrow f(x) \in B</math>. *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: <math>W_x</math> (x-tá rekurzivně spočetná množina) = <math> dom( \varphi_x) = \{ y, \varphi_x(y) \mbox{je definována} \} </math>

  • důležitá definice, <math>W_x</math> už budeme používat skoro pořád!

  • <math>\varphi_x </math> je x-tá ČRF

*def: <math>K = \{x, x \in W_x\}</math>

  • Jinými slovy <math>\{x, \varphi_x(x) \mbox{je definovana} \}</math>, tedy <math>\{x, \psi_1(x,x) \mbox{je definovana}\}</math>

  • <math>\psi_1</math> je univerzální funkce z Kleeneho věty

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

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 <math>\psi_1(x,x)</math> (f zkonstruujeme pomocí substituce atd.), K je definičním oborem f.

  • Nechť doplněk K je RSM. Pak <math>\exists x_0 : \bar{K} = W_{x_0}</math>. Pokud <math>x_0 \in \bar{K}</math>, pak <math>x_0 \in W_{x_0}</math>, pak <math>x_0 \in K</math> (z definice K). Spor.

Věta: K je 1-úplná

Důkaz:

*K je rekurzivně spočetná viz definice, dále vezmu libovolnou rek. spočetnou množinu <math>W_x</math>, vezmu ČRF fci <math>\alpha(y,x,w)</math>, 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 <math>\alpha(y,x,w)\downarrow \Leftrightarrow y \in W_x</math> *Vyjádřím si alfu pomocí univerzální funkce <math>\psi_3(a,y,x,w)</math>

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

*<math>\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</math>

  • Zde jsme mohli za <math>w</math> dosadit <math>h(y, x)</math>, neboť hodnota <math>\alpha</math> na <math>w</math> nazáleží

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

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

  • Chceme pro libovolné x ukázat, že <math>W_x = dom(\varphi_x) \leq_1 K</math>. Chceme najít prostou ORF h(y) takovou, že <math>y \in W_x \Leftrightarrow h(y) \in K</math>, což dle definice K platí, právě když <math>h(y) \in W_{h(y)} \Leftrightarrow \Psi_1(h(y),h(y)) \downarrow</math>.

  • <math>\varphi_x(y) \simeq \Psi_1(x,y) \simeq \Psi_2(e,y,w) \simeq \Psi_1(s_1(e,y),w)</math>. Položme <math>h(y) \simeq s_1(e,y)</math>.

  • Uměle jsme přidali proměnnou w, nemající vliv na hodnotu funkce. h(y) je prostá ORF, dokonce rostoucí.

  • <math>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</math>

  • 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 <math>W_x</math> vezměme její popisující ČRF <math>\varphi_x</math>.

  • Definujme funkci dvou proměnných <math>\alpha</math>(y,w) podle předpisu <math>\alpha</math>(y,w)<math> \downarrow</math> = <math>\varphi_x(y)</math>.

    • Tato funkce je jistě ČRF, buď tedy <math>e</math> její index.

    • Proměnná <math>w</math> 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í (*): <math>\alpha(y,w) \simeq \psi_2(e,y,w) \simeq \psi_1(s_1(e,y),w) \simeq \varphi_{s_1(e,y)}(w)</math>

  • Položme <math>h = s_1(e,y)</math>.

    • 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 <math>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</math>

  • První ekvivalence plyne z definice funkce <math>\alpha</math>, 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.

<math>\Box</math>

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: <math>K_0</math> je 1-úplná

Důkaz: Převodem <math>K</math> na <math>K_0</math>. Předpis může být <math>f(x) = (x,x)</math> - 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 <math>K</math> souvisí s Halting problémem (viz definice rekurzivně spočetné množiny) – kdyby <math>K</math> byla rekurzivní => by bylo možné díky tomu, že <math>K</math> je 1-převoditelná na <math>K_0</math>, rozhodnout halting problém.