Fundovaná relace

Fundovaná relace je matematický pojem z oboru teorie množin, který popisuje druh relace podobný dobrému uspořádání.

Definice

Relace R je fundovaná na třídě A, jestliže každá její neprázdná podmnožina $\mathrm{\varnothing }\ne B\subseteq A$ má R-minimální prvek označovaný symbolem $mi{n}_R(B)$ .
Prvek $x=mi{n}_R(B)$ označíme za R-minimální prvek množiny B, pokud platí
$x\in B\wedge (\mathrm{\forall }y\in B)\mathrm{\neg }([y,x]\in R)$

Vysvětlení a vlastnosti pojmu

R-minimální prvek je takový prvek nějaké podmnožiny B, pro který neexistuje žádný menší (ve smyslu relace R) v této podmnožině. Důvod, proč nemluvíme rovnou o minimálním prvku je ten, že nikde není řečeno, že fundovaná relace R je uspořádání – což ostatně opravdu nemusí být pravda.

Fundovaná relace totiž opravdu nemusí být uspořádání, i když na první pohled trochu připomíná ostré uspořádání. Problém je v tom, že fundovaná relace nemusí být (na rozdíl od uspořádání) tranzitivní.

Příklad: Na tříprvkové množině $\{1,2,3\}$ definujme relaci $R=\{[1,2],[2,3]\}$. Snadno se dá ověřit, že taková relace je fundovaná, ale není tranzitivní – to by totiž musela obsahovat i uspořádanou dvojici $[1,3]$.

Fundovaná relace nesmí obsahovat žádný konečný cyklus (v tom se podobá ostrému uspořádání).
Kdybychom v předchozím příkladě přidali dvojici $[3,1]$, vznikla by relace $R=\{[1,2],[2,3],[3,1]\}$, která již není fundovaná – množina $\{1,2,3\}$ nemá v tomto případě žádný R-minimální prvek.

Fundovaná relace nesmí obsahovat žádnou nekonečnou klesající posloupnost (v tom se podobá dobrému uspořádání).
Pokud najdu posloupnost prvků $a_0,a_1,a_2,\dots$ takových že pro každé i je $[a_{i+1},a_i]\in R$, pak množina $\{a_0,a_1,a_2,\dots \}$ nemá žádný R-minimální prvek.

Konečný cyklus je zvláštní případ, vedoucí na nekonečnou klesající posloupnost - pokud se vrátím k předchozímu příkladu s relací $R=\{[1,2],[2,3],[3,1]\}$, můžu sestrojit nekonečnou klesající posloupnost $\{3,2,1,3,2,1,3,2,1,3,\dots \}$.

Z axiomu výběru se dá ukázat, že relace R je fundovaná tehdy a jen tehdy, když neobsahuje nekonečnou klesající posloupnost.

Význam pojmu

Axiom fundovanosti

Motivace k zavedení pojmu a jeho význam vyplývá z axiomu fundovanosti.

Tento axiom lze v ekvivalentní podobě zapsat jako $𝕎𝔽=𝕍$, kde $𝕎𝔽$ je fundované jádro a $𝕍$ univerzální třída, tj. třída všech množin.

Podstatou důkazu výše uvedené ekvivalence, je věta, podle které je $𝕎𝔽$ největší tranzitivní třída, na které je relace $\in$ fundovaná.

Transfinitní indukce a rekurze

Na každé třídě s fundovanou relací takovou, že levým obrazem každého prvku je množina (a ne vlastní třída), se dá provádět fundovaná indukce a fundovaná rekurze, jejichž speciálním případem je transfinitní indukce a transfinitní rekurze přes fundovanou operaci náležení na ordinálních číslech; ještě speciálnějšími případy jsou matematická indukce a rekurze přes přirozená čísla.

Související články

• Axiom fundovanosti
• Axiom výběru
• Fundované jádro
• Dobré uspořádání
• Mostowského kolaps