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.

A transzfinit indukció tétele[szerkesztés | forrásszöveg szerkesztése]

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.

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]