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[forrásszöveg szerkesztése]

Tétel. Legyen 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 igaz, akkor igaz. Ekkor minden rendszámra teljesül.

Bizonyítás. Tegyük fel, hogy van olyan rendszám, amire 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 halmaz minden eleméhez egy állítás. Ha valahányszor minden elemre az állítás teljesül, mindannyiszor az á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 állítás, mindannyiszor az állítás is teljesül, és tegyük fel, hogy létezik olyan , hogy az állítás nem teljesül. Legyen a legkisebb olyan hogy az állítás nem teljesül. Ekkor minden minden elemre teljesül az állítás, ezért a tétel feltevése értelmében az állítás is teljesül, ami ellentmondás.

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

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