{{Template:TIN064 Skripta}}
{{TODO|Zatím jen základní kefry, více viz Strojil.}}
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é.
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 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:''' Nekonečné rekurzivní množiny jsou právě obory hodnot rostoucích ORF, tedy ORF je '''generují'''.
'''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é.
== 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.)
