Transzfinit indukció

Ez a közzétett változat, ellenőrizve: 2020. január 11.

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

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.

Kapcsolódó szócikkek

szerkesztés