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

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

Bizonyítás. Tegyük fel, hogy valahányszor minden 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 , hogy az A_l állítás nem teljesül. Legyen a legkisebb olyan A_l hogy az A_l állítás nem teljesül. Ekkor minden minden 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.

[szerkesztés] Lásd még

• Indukció
• Transzfinit rekurzió

[szerkesztés] Hivatkozá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ó.