Ugrás a tartalomhoz

Transzfinit rekurzió

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából

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:

Mértékelmélet:

Algebra:

Topológia:

Ö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ó.