{{Template:TIN064 Skripta}}
* množina '''A je 1-převedilná na B''' (značíme <math> A \le_1 B</math>), jestliže existuje prostá ORF f taková, že <math> x \in A </math> právě tehdy když <math> f(x) \in B</math>
* množina '''A je m-převedilná na B''' (značíme <math> A \le_m B</math>), jestliže existuje ORF (ne nutně prostá) f taková, že <math> x \in A </math> právě tehdy když <math> 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á
==K je 1-úplná==
důkaz:
*K je rekurzivně spočetná viz [[TIN064_Vlastnosti_RSM|definice]], dále vezmu libovolnou rek. spočetnou množinu <math>W_x</math>, vezmu ČRF fci <math>\alpha(y,x,w)</math>, která ji popisuje (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). Nyní <math>\alpha(y,x,w)</math> je definována <=> <math>y \in W_x</math>
*Vyjádřím si alfu pomocí univerzální funkce <math>\psi_3(a,y,x,w)</math>, díky s-m-n větě vím, že ta se podmíněně rovná <math>\psi_1(s_2(a,y,x),w)</math>, kde <math>s_2</math> je z Kleeneho věty PRF, tedy i ORF (<math>s_k</math> je prostá fce – dle Kleeneho věty)
*Pro libovolné y z <math>W_x</math> platí, že <math>\alpha(y,x,w)</math> je definována a to je <=> <math>\varphi_h(y,x)(w)\downarrow </math><=> <math>\varphi_h(y,x)(h(y,x))\downarrow </math><=> <math> h(y,x) \in K (h(y,x) \mbox{ vyjadřuje } s_2(a,y,x))</math>
*Tedy <math>W_x</math> je 1-převeditelná na K pomocí funkce h(y,x)
{{TODO|doplnit dalšími údaji}}
