Transfinitní indukce

Spirála znázorňující všechna ordinální čísla menší než ωω.

Transfinitní indukce je postup důkazu používaný v teorii množin obdobný jako klasická matematická indukce, ale rozšířený z přirozených čísel na ordinální čísla.

Věty o transfinitní indukci

Přestože princip matematické indukce je uváděn jako součást Peanovy axiomatiky přirozených čísel, je třeba jej v axiomatice teorie množin ZF dokázat jako větu, neboť přirozená čísla v ní nejsou elementární pojem, ale je třeba je zkonstruovat. Stejně tak v případě transfinitní indukce se jedná o věty (i když s poměrně snadným důkazem), které poskytují návod, jak při důkazu postupovat:

Verze první

Je-li X třída ordinálních čísel, pro kterou platí, že každou svou podmnožinu obsahuje zároveň jako prvek, pak je X shodná s třídou On všech ordinálních čísel.
( X ⊆ O n ∧ ( ∀ α ∈ O n ) ( α ⊆ X ⟹ α ∈ X ) ) ⟹ X = O n {\displaystyle (X\subseteq On\land (\forall \alpha \in On)(\alpha \subseteq X\implies \alpha \in X))\implies X=On}

Verze druhá

Pokud je X třída ordinálních čísel, která obsahuje prázdnou množinu, s každým ordinálem α {\displaystyle \alpha \,\!} zároveň ordinál α + 1 {\displaystyle \alpha +1\,\!} a pro každý limitní ordinál α {\displaystyle \alpha \,\!} , který je podmnožinou X platí, že α {\displaystyle \alpha \,\!} je zároveň prvkem X, pak tato třída X obsahuje všechna ordinální čísla, tj. X = On
Jinými slovy pokud platí následující čtyři podmínky, pak X = On:

  1. X ⊆ O n {\displaystyle X\subseteq On}
  2. ∅ ∈ X {\displaystyle \emptyset \in X}
  3. ( ∀ α ∈ O n ) ( α ∈ X ⟹ α ∪ { α } ∈ X ) {\displaystyle (\forall \alpha \in On)(\alpha \in X\implies \alpha \cup \{\alpha \}\in X)}
  4. pro každý limitní ordinál α {\displaystyle \alpha \,\!} platí α ⊆ X ⟹ α ∈ X {\displaystyle \alpha \subseteq X\implies \alpha \in X}

Příklad použití

Transfinitní indukce se používá při důkazu značného množství vět z ordinální aritmetiky, mimo jiné například při důkazu, že mocnění na ordinálních číslech je rozšířením mocnění na přirozených číslech:

  1. ( ∀ α , β , γ ∈ O n ) ( α β + γ = α β . α γ ) {\displaystyle (\forall \alpha ,\beta ,\gamma \in On)(\alpha ^{\beta +\gamma }=\alpha ^{\beta }.\alpha ^{\gamma })}
  2. ( ∀ α , β , γ ∈ O n ) ( α β . γ = ( α β ) γ ) {\displaystyle (\forall \alpha ,\beta ,\gamma \in On)(\alpha ^{\beta .\gamma }=(\alpha ^{\beta })^{\gamma })}

Důsledkem principu transfinitní indukce je princip transfinitní rekurze, tj. možnost jednoznačně definovat zobrazení na ordinálních číslech předpisem, který využívá pro výpočet α {\displaystyle \alpha \,\!} -té hodnoty hodnot pro ordinální čísla menší než α {\displaystyle \alpha \,\!} . (Je tomu obdobně, jako u běžného aritmetického principu matematické indukce, ze kterého vyplývá možnost používat rekurzi na přirozených číslech.)

Související články

Teorie množin
Axiomy
axiom výběru • axiom spočetného výběru • axiom závislého výběru • axiom extenzionality • axiom nekonečna • axiom dvojice • axiom potenční množiny • Axiom regulárnosti • axiom sumy • schéma nahrazení • schéma axiomů vydělení • hypotéza kontinua • Martinův axiom • velké kardinály
 Vennův diagram průniku množin.
Množinové operace
Koncepty
bijekce • kardinální číslo • konstruovatelná množina • mohutnost • ordinální číslo • prvek množiny • rodina množin • transfinitní indukce • třída • Vennův diagram
Množiny
Teorie
Lidé