Transzfinit indukció

A Wikipédiából, a szabad lexikonbó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éleskö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 (A, \cdot) tetszőleges jólrendezett halmaz és legyen hozzárendelve az A halmaz minden i\in A eleméhez egy Ai állítás. Ha valahányszor minden j\le i (j\in A) elemre az Aj állítás teljesül, mindannyiszor az Ai á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\le i (j\in A) elemre teljesül az Aj állítás, mindannyiszor az Ai állítás is teljesül, és tegyük fel, hogy létezik olyan A_l (l\in A), hogy az Al állítás nem teljesül. Legyen A_k (k\in A) a legkisebb olyan Al hogy az Al állítás nem teljesül. Ekkor minden minden j\le k (j\in A) elemre teljesül az Aj állítás, ezért a tétel feltevése értelmében az Ak állítás is teljesül, ami ellentmondás.

[szerkesztés] Hivatkozások

  • Rédei, László: Algebra I. kötet, Akadémiai Kiadó, Budapest, 1954