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
[szerkesztés]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
[szerkesztés]Tétel
[szerkesztés]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
Megjegyzés
[szerkeszté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ó:
Bizonyítás
[szerkesztés]Egyértelműség
[szerkesztés]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
- ,
azaz a két operáció φ-n felvett értéke is megegyezik, ami ellentmond φ definíciójának.
Létezés
[szerkesztés]Jelölje Fα azt a { β | β < α } = α halmazon értelmezett függvényt, amelyre minden β < α esetén , 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:
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
[szerkesztés]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
[szerkesztés]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
[szerkesztés]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
[szerkesztés]- Hajnal András, Hamburger Péter: Halmazelmélet, Nemzeti Tankönyvkiadó.