Fundovaná rekurze

Fundovaná rekurze je matematický pojem z oblasti teorie množin, který zobecňuje transfinitní rekurzi.

Věta o fundované rekurziEditovat

Věta o fundované rekurzi zní takto:

Nechť R je úzká fundovaná binární relace a G je třídová funkce definovaná na celé univerzální třídě. Pak existuje jediná funkce F definovaná na univerzální třídě splňující   pro všechna x.

Náznak důkazuEditovat

Definujme nejprve třídu P všech „parciálních“ funkcí f, tj. takových, jejichž definiční obor je R-tranzitivní množina (množina uzavřená na R-předchůdce svých prvků) a které splňují   pro všechna x z definičního oboru f. Fundovanou indukcí (podle R) se snadno dokáže, že pro funkce f,g z P a x z průniku jejich definičních oborů je   a dále, že každé x je v definičním oboru nějaké funkce z P. Pak   je funkce definovaná na univerzální třídě vyhovující tvrzení věty.

Související článkyEditovat