Transzfinit rekurzió

A transzfinit rekurzió a sorozatok elméletéből ismert rekurzív megadási mód halmazelméleti általánosítása. Bizonyításokban és konstrukciókban fontos segédeszköz, elsősorban a halmazelmélet, az algebra és a mértékelmélet területén.

A rekurzió leírása

Transzfinit rekurzióval rendszámokon értelmezett hozzárendelést lehet definiálni: ha már egy α rendszámnál kisebbekre megvan, hogy mit rendelünk hozzájuk, akkor ez alapján egy "képzési szabály" segítségével megkapjuk, hogy mit rendelünk hozzá α-hoz.

Pontosabban: a rendszámok osztályán értelmezett hozzárendelés egy operáció lesz. Nem függvény, mivel az értelmezési tartománya nem halmaz. Viszont minden α-ra az α-nál kisebb rendszámokra (ezek halmazt alkotnak) megszorított operáció már függvény, tehát a képzési szabályunk egy olyan operáció kell, hogy legyen, ami minden ilyen függvényhez hozzárendel valamit, és ez a valami lesz a rendszámokon értelmezett operáció α-beli értéke. Az egyszerűség kedvéért föltehetjük, hogy a képzésiszabály-operációnk a világ összes függvényeinek az osztályán van értelmezve.

Az viszont egyáltalán nem nyilvánvaló, hogy ezen a módon valóban tudunk operációt definiálni a rendszámokon. Ezt biztosítja a transzfinit rekurzió tétele.

Transzfinit rekurzió tétele

Tétel

Ha adott egy G operáció, ami a függvények osztályán van értelmezve, akkor pontosan egy olyan F operáció létezik, ami a rendszámok osztályán van értelmezve, és tetszőleges α rendszámon fölvett értéke megegyezik G-nek az F operáció α-nál kisebb rendszámokra való megszorításával kapott függvényen fölvett értékével. Azaz minden α rendszámra teljesül, hogy

$F\left(\alpha \right)=G\left(F\mid \left\{\beta \mid \beta <\alpha \right\}\right)$

Megjegyzés

A Neumann-féle definíció szerint minden rendszám megegyezik a nála kisebb rendszámok halmazával, tehát a fönti képlet egyszerűbben is írható:

$F\left(\alpha \right)=G\left(F\mid \alpha \right)$

Bizonyítás

Egyértelműség

Tegyük fel, hogy két különböző ilyen operáció is létezik, F illetve F'. Mivel különbözőek, van olyan rendszám, hogy azon fölvett értékük különbözik egymástól. A rendszámok jólrendezettsége miatt van legkisebb ilyen rendszám is, jelölje ezt φ. Tehát F( α )=F'( α ) minden α < φ esetén, de F(φ)≠ F'(φ). Azonban

$F\left(\phi \right)=G\left(F\mid \left\{\alpha \mid \alpha <\phi \right\}\right)=G\left(F'\mid \left\{\alpha \mid \alpha <\phi \right\}\right)=F'\left(\phi \right)$,

azaz a két operáció φ-n felvett értéke is megegyezik, ami ellentmond φ definíciójának.

Létezés

Jelölje F_α azt a { β | β < α } = α halmazon értelmezett függvényt, amelyre minden β < α esetén $F_{\alpha }\left(\beta \right)=G\left(F_{\alpha }\mid \beta \right)$, ha van ilyen. Az egyértelműség bizonyításának lemásolásával igazolható, hogy minden α-ra legföljebb egy ilyen függvény létezik.

• Ha α < β és F_β létezik, akkor F_α is létezik, és F_α = F_β|α. F_β|α ugyanis megfelel az F_α-ra tett követelményeknek és az egyértelműség miatt más ilyen függvény nincs.
• F_α minden α rendszámra létezik. Ezt transzfinit indukcióval igazoljuk. Jelölje T(α) azt a tulajdonságát α-nak, hogy F_α létezik. A rendszámok három típusára ellenőrizzük az indukció feltételeit.
  • α = 0 -ra az üres halmaz, mint függvény megfelel, tehát T(0) igaz.
  • α = β + 1 -re definiáljuk F_α-t így: γ < β -ra F_α( γ ) := F_β( γ ) és F_α( β ) := G ( F_β ). Az így definiált függvény teljesíti a követelményeket, tehát T( β + 1 ) következik T( β ) -ból.
  • α limeszrendszám és a nála kisebb rendszámokra igaz T. Ekkor definiálhatjuk F_α -t a következőképp: tetszőleges α-nál kisebb γ rendszámhoz található γ < β < α rendszám. F_α( γ ) := F_β ( γ ). Ez a definíció értelmes, mert - könnyen ellenőrizhető a létezés bizonyításának 1. pontja alapján - nem függ β választásától, és a definiált függvény megfelel F_α-nak. Tehát limeszrendszám esetén is igaz, hogy T( α ) következik abból, hogy α-nál kisebb rendszámokra igaz T.

A transzfinit indukció tételének teljesül a feltétele, így a tétel szerint minden rendszámra igaz T, tehát létezik F_α.
Utolsó lépésként definiáljuk F -et:

$F\left(\alpha \right):=F_{\beta }\left(\alpha \right)$

tetszőleges α < β választással. Az előzőekhez hasonlóan könnyen ellenőrizhető, hogy ez nem függ β választásától, tehát F jól definiált, továbbá teljesíti a tétel követelményét.

Alkalmazása

A módszernek már az alapoknál nagy jelentősége van: a jólrendezési tételt transzfinit rekurzió segítségével lehet levezetni a kiválasztási axiómából. A jólrendezési tétel szerint minden halmaz jólrendezhető, és ez a tény megnöveli a transzfinit rekurzió hatáskörét: így tetszőlegesen nagy számosságú halmazokra lehet függvényt definiálni rekurzívan. Az így definiált függvények bizonyos speciális tulajdonságai ezután transzfinit indukcióval igazolhatók.
A transzfinit indukciós bizonyítások egy részében kényelmesebb indukció helyett Zorn-lemmát alkalmazni.

Példák a használatára

Halmazelmélet:

• Jólrendezési tétel bizonyítása
• Zorn-lemma bizonyítása
• A halmazok kumulatív hierarchiája

Mértékelmélet:

• Generált szigma-algebra előállítása

Algebra:

• Minden vektortérnek van bázisa.
• Tetszőleges polinomhalmaznak létezik felbontási teste az alaptest fölött, speciálisan minden testnek van algebrai lezártja.

Topológia:

• Létezik összefüggő, T2, lokálisan Euklideszi térrel homeomorf, de nem M2 topologikus tér, "hosszúegyenes".

Összehasonlítása a sorozatok rekurziójával

A sorozatok rekurzív definiálásával ellentétben transzfinit rekurziónál nincs szükség kezdőértékre, ugyanis azt megadja G-nek az üres halmazon, mint függvényen fölvett értéke. Viszont amíg sorozatoknál elég néhány (rögzített számú) elemet ismerni a sorozatból a következő kiszámításához, transzfinit rekurziónál az összes megelőző rendszámon fölvett értékre szükség van a soron következő érték meghatározásához. És más a céljuk is: a transzfinit rekurzió egy segédeszköz, a segítségével fölépített konstrukciók nem is tekinthetők konstrukcióknak, mert konkrétan kiszámolni őket rendszerint a megszámlálhatónál nagyobb számosságok miatt lehetetlen. Emiatt a transzfinit rekurziós bizonyítások rendszerint egzisztenciabizonyítások.

Hivatkozások

• Hajnal András, Hamburger Péter: Halmazelmélet, Nemzeti Tankönyvkiadó.