Transzfinit indukció

A Wikipédiából, a szabad enciklopédiából

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.

[szerkesztés] 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 UNIQ4285850e780bb871-math-0000000B-QINU-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.