Induzione transfinita

L'induzione transfinita è una tecnica di dimostrazione matematica analoga all'induzione matematica applicata ad insiemi ben ordinati, ad esempio all'insieme dei numeri ordinali o dei numeri cardinali.

Se si vuole dimostrare che una proprietà P vale per tutti gli ordinali, si può applicare l'induzione transfinita coi seguenti passi:

• Dimostrare che P(0) vale
• Dimostrare che, per ogni ordinale b, se P(a) vale per tutti gli ordinali a<b allora vale anche P(b)

L'ultimo passo viene spesso diviso in due casi: il caso di ordinale successore, dove si può applicare il ragionamento induttivo classico (mostrare che P(a) implica P(a+1)) e il caso di ordinale limite, che non ha predecessore e quindi non può essere trattato con quel ragionamento.

Tipicamente il caso di ordinale limite viene affrontato notando che un ordinale limite b è, per definizione, l'estremo superiore di tutti gli ordinali a<b e usando poi questo fatto per dimostrare che, supponendo che P(a) valga per tutti gli a<b, vale anche P(b).