{{Template:TIN064 Skripta}}
Funkce <math>f</math> je '''úseková''', je-li jejím definičním obor "počáteční úsek" <math>\mathbb{N}</math> (nebo celé <math>\mathbb{N}</math>). Tedy když je definovaná pro "prvních <math>k</math> čísel". Všimněme si, že PRF a ORF jsou vždycky úsekové (jsou totiž totální), zatímco ČRF jsou samozřejmě úsekové jen některé.
Nápad na formalismus: pro úsekovou f platí <math>\forall k: f(k)\uparrow \Leftrightarrow \forall j>k: f(j)\uparrow</math> (XXX je f s prázdným def. oborem úseková?)
Ukazuje se, že na některé věci nepotřebujeme totální funkce a stačí nám pouze úsekovost. Konkrétně umíme pěknými úsekovými ČRF efektivně spočítat všechny množiny rekurzivní (prostá a rostoucí ČRF) a rekurzivně spočetné (prostá ČRF).
==Generátory PRM==
'''Věta:''' ''Rekurzivní'' množiny jsou právě obory hodnot ''rostoucích'' úsekových ČRF.
'''Důkaz:''' Klasický ekvivalenční, každou implikaci dokážeme zvlášť.
* Máme <math>M</math>, potřebujeme najít <math>f</math> aby <math>M = rng(f)</math>
** Jednoduše minimalizací postupně očíslujeme prvky <math>M</math>, <math>f(k)</math> vybere <math>k</math>-tý nejmenší prvek. To zřejmě vyrobí funkci, která je úseková a rostoucí.
** Formálně: <math>f(0) = \mu_x (x \in M)</math>, <math>f(k+1) = \mu_y (y > f(k) | y \in M)</math>
* Máme <math>f</math>, je <math>M=rng(f)</math> rekurzivní? Musíme umět u <math>f(x)=y</math> snadno (bez minimalizace) najít pro každé <math>y</math> odpovídající <math>x</math>.
** Pokud <math>f</math> není totální, má konečný definiční obor a jde to omezeným forcyklem (primitivní rekurzí).
** Pokud <math>f</math> je totální, využijeme úsekovosti a monotónnosti - nutně <math>x \le y</math>, jinak jsme museli nějaké <math>x</math> přeskočit (spor s úsekovostí) nebo prohodit (spor s růstem). Zase nám stačí primitivní rekurze, strčíme jí <math>y</math>.
** Pozor! Jestli je <math>f</math> totální nemusíme umět efektivně zjistit.
'''Věta:''' (Strojil) Nekonečné rekurzivní množiny jsou právě obory hodnot rostoucích ORF.
'''Důkaz:''' Žádná věda, snadno plyne z předchozí věty!
* Pomněte, že ORF je úseková ČRF a lze snadno (z prostoty funkcí) nahlédnout, že ČRF s konečným úsekem generují konečné rekurzivní množiny, zatímco ČRF s nekonečným úsekem (tedy totální, tedy ORF) musejí generovat ty nekonečné.
'''Věta:''' (Lenka) Nekonečné rekurzivně spočetné množiny jsou právě obory hodnot prostých ORF.
'''Důkaz:''' Obdobně plyne naopak z následující věty.
== Generátory RSM ==
'''Věta:''' ''Rekurzivně spočetné'' množiny jsou právě obory hodnot ''prostých'' úsekových ČRF.
* Rostoucí ČRF byla také prostá, takže jsme jen podmínku zmírnili - a dostali tak širší sadu množin.
'''Důkaz:''' Zase dvě implikace, druhá možná maličko náročnější.
* Máme ČRF <math>f</math>. Již dříve jsme ukazovali větu, že obor hodnot každé ČRF je RSM.
* Máme RSM <math>M</math>, víme, že je oborem hodnot nějakých ČRF; vezměme kteroukoliv <math>\varphi</math>. Ale je mezi nimi pak i hledaná <math>f</math> prostá a úseková? Samozřejmě ji musíme z <math>\phi</math> vyrobit!
** Chce to Cimrmanův krok stranou - vyrobit si z <math>\varphi</math> množinu <math>B=\{(x,s)|\varphi(x)\downarrow\mbox{po s krocich}\}</math>.
*** Připomínka formálního zápisu: <math>T_1(\varphi,x,s) \land \forall p<s: \neg T_1(\varphi,x,p)</math>
** To je evidentně rekurzivní množina, a jak jsme si právě dokázali, má generátor <math>h</math> - rostoucí úsekovou ČRF. Obecně vzato <math>h</math> je nějaké vzestupné úsekové očíslování párů <math>(x,s)</math>.
** <math>f(x) = h(x)_1</math> - vezmeme pár s daným číslem a vydělíme z něj <math>x</math>! <math>f(0)</math> bude <math>x</math> z prvního páru, atd. <math>f</math> je zjevně stejně úsekové jako <math>h</math>, a sice již není rostoucí, ale stále je prosté (a pokrývá celou RSM) - každé <math>x</math> bylo evidentně právě v jednom páru.
== Embedování PRM v RSM ==
'''Důsledek:''' Každá nekonečná RSM obsahuje nekonečnou rekurzivní podmnožinu.
'''Důkaz:''' Rehash předchozích číslovacích důkazů.
* V RSM vybereme rostoucí podposloupnost, tu si minimalizací setřídíme a očíslujeme a tohle očíslování je rekurzivní podmnožina.
* Formálně: <math>g(0) = f(0)</math>, <math>g(k+1) = f(\mu_j(f(j) > g(k))</math>
* <math>g</math> je rostoucí úseková ČRF, tedy její obor hodnot je rekurzivní množina, ta je zároveň evidentně podmnožinou <math>M</math>. Co víc si v životě přát?
