Transzfinit indukció

A transzfinit indukció a teljes indukció általánosítása megszámlálható számosságoknál nagyobb végtelen számosságok esetére is. Széles körű alkalmazhatóságát a jólrendezési tételnek, illetve az ezzel ekvivalens kiválasztási axiómának köszönheti.

A transzfinit indukció tétele

Tétel. Legyen ${\displaystyle T(\alpha )}$ tetszőleges matematikai állítás az ${\displaystyle \alpha }$ rendszámról. Tegyük fel, hogy teljesül a következő állítás: ha egy ${\displaystyle \alpha }$ rendszámra igaz, hogy minden ${\displaystyle \beta <\alpha }$ rendszámra ${\displaystyle T(\beta )}$ igaz, akkor ${\displaystyle T(\alpha )}$ igaz. Ekkor ${\displaystyle T(\alpha )}$ minden ${\displaystyle \alpha }$ rendszámra teljesül.

Bizonyítás. Tegyük fel, hogy van olyan ${\displaystyle \alpha }$ rendszám, amire ${\displaystyle T(\alpha )}$ nem teljesül. Ekkor, a rendszámok jólrendezettsége elve miatt, van legkisebb ilyen ${\displaystyle \alpha }$ is. Erre az ${\displaystyle \alpha }$-ra nem teljesül a tétel premisszája, ellentmondás.

• Vagy más megfogalmazásban a rendszám fogalmának használata nélkül:

Tétel. Legyen ${\displaystyle (A,\cdot )}$ tetszőleges jólrendezett halmaz és legyen hozzárendelve az ${\displaystyle A}$ halmaz minden ${\displaystyle i\in A}$ eleméhez egy ${\displaystyle A_{i}}$ állítás. Ha valahányszor minden ${\displaystyle j<i(j\in A)}$ elemre az ${\displaystyle A_{j}}$ állítás teljesül, mindannyiszor az ${\displaystyle A_{i}}$ állítás is teljesül, akkor minden ${\displaystyle A_{i}(i\in A)}$ állítás teljesül.

Bizonyítás. Tegyük fel, hogy valahányszor minden ${\displaystyle j<i(j\in A)}$ elemre teljesül az ${\displaystyle A_{j}}$ állítás, mindannyiszor az ${\displaystyle A_{i}}$ állítás is teljesül, és tegyük fel, hogy létezik olyan ${\displaystyle A_{l}(l\in A)}$, hogy az ${\displaystyle A_{l}}$ állítás nem teljesül. Legyen ${\displaystyle A_{k}(k\in A)}$ a legkisebb olyan ${\displaystyle A_{l}}$ hogy az ${\displaystyle A_{l}}$ állítás nem teljesül. Ekkor minden minden ${\displaystyle j<k(j\in A)}$ elemre teljesül az ${\displaystyle A_{j}}$ állítás, ezért a tétel feltevése értelmében az ${\displaystyle A_{k}}$ állítás is teljesül, ami ellentmondás.

Kapcsolódó szócikkek

• Teljes indukció
• Transzfinit rekurzió

Források

• Rédei László: Algebra I. kötet, Akadémiai Kiadó, Budapest, 1954
• Hajnal András, Hamburger Péter: Halmazelmélet, Nemzeti Tankönyvkiadó.