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 $T(\alpha )$ tetszőleges matematikai állítás az $\alpha$ rendszámról. Tegyük fel, hogy teljesül a következő állítás: ha egy $\alpha$ rendszámra igaz, hogy minden $\beta <\alpha$ rendszámra $T(\beta )$ igaz, akkor $T(\alpha )$ igaz. Ekkor $T(\alpha )$ minden $\alpha$ rendszámra teljesül.

Bizonyítás. Tegyük fel, hogy van olyan $\alpha$ rendszám, amire $T(\alpha )$ nem teljesül. Ekkor, a rendszámok jólrendezettsége elve miatt, van legkisebb ilyen $\alpha$ is. Erre az $\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 $(A,\cdot )$ tetszőleges jólrendezett halmaz és legyen hozzárendelve az $A$ halmaz minden $i\in A$ eleméhez egy $A_i$ állítás. Ha valahányszor minden $j<i(j\in A)$ elemre az $A_j$ állítás teljesül, mindannyiszor az $A_i$ állítás is teljesül, akkor minden $A_i(i\in A)$ állítás teljesül.

Bizonyítás. Tegyük fel, hogy valahányszor minden $j<i(j\in A)$ elemre teljesül az $A_j$ állítás, mindannyiszor az $A_i$ állítás is teljesül, és tegyük fel, hogy létezik olyan $A_l(l\in A)$, hogy az $A_l$ állítás nem teljesül. Legyen $A_k(k\in A)$ a legkisebb olyan $A_l$ hogy az $A_l$ állítás nem teljesül. Ekkor minden minden $j<k(j\in A)$ elemre teljesül az $A_j$ állítás, ezért a tétel feltevése értelmében az $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ó.