transfinite induction

transfinite induction (tsz. transfinite inductions)

1. (informatika) A transfinite induction (magyarul: transzfinit indukció) egy olyan matematikai bizonyítási módszer, amely kiterjeszti az általános indukció elvét véges számú lépésekről a végtelen, sőt végtelenül nagy (transzfinit) rendezett halmazokra, például a jól rendezett halmazokra, mint az ordinal számok.

• A matematikai indukció alapvetően a természetes számokra vonatkozó bizonyítási elv:
  1. Bázis lépés: Igaz az állítás 0-ra vagy 1-re.
  2. Indukciós lépés: Ha igaz n-re, akkor igaz n+1-re is.

Ezzel bizonyítható, hogy az állítás minden természetes számra igaz.

• A természetes számok egy speciális jól rendezett halmazt alkotnak.
• A transzfinit indukció általánosítja ezt a módszert olyan jól rendezett halmazokra, ahol az elemek nemcsak véges, hanem transzfinit (ordinal számok) is lehetnek.
• Ezekben a halmazokban minden részhalmaznak van legkisebb eleme, így indukciós érvelés alkalmazható.

Legyen ${\textstyle P(\alpha )}$ egy tulajdonság az ordinal számokra, akkor ha igaz, hogy:

1. Bázis: ${\textstyle P(0)}$ igaz.
2. Sukcesszor lépés: Ha ${\textstyle P(\beta )}$ igaz, akkor ${\textstyle P(\beta +1)}$ is igaz.
3. Limit lépés: Ha ${\textstyle \lambda }$ limit ordinal (nincs elődje), és ${\textstyle P(\gamma )}$ igaz minden ${\textstyle \gamma <\lambda }$ esetén, akkor ${\textstyle P(\lambda )}$ is igaz.

Akkor ${\textstyle P(\alpha )}$ igaz minden ordinal ${\textstyle \alpha }$-ra.

• Halmazelméletben, ordinal számok vizsgálatánál.
• Végtelen struktúrák és hierarchiák bizonyításánál.
• Formális logikában és számelméletben speciális állítások igazolására.

• transfinite induction - Szótár.net (en-hu)
• transfinite induction - Sztaki (en-hu)
• transfinite induction - Merriam–Webster
• transfinite induction - Cambridge
• transfinite induction - WordNet
• transfinite induction - Яндекс (en-ru)
• transfinite induction - Google (en-hu)
• transfinite induction - Wikidata
• transfinite induction - Wikipédia (angol)