Principio di induzione

Assioma (Assioma del buon ordinamento)

Sia , con , e tale che se , allora anche . Allora .

 



Assioma (Principio di induzione)

Sia una proposizione che abbia senso enunciare per ogni con dove è un fissato intero. Per ogni , supponendo che sia vera, si dimostra . Allora è vera per ogni .

 



Esempio 1.31

Sia un insieme finito, allora il numero di elementi delle parti di è esattamente .


Dim. Se , allora , ha elementi. Supponiamo il risultato vero per insiemi di cardinalità e lo dimostriamo per un insieme di cardinalità .

Sia , allora divido in due blocchi: il blocco dei sottoinsiemi di che contengono (che chiamo ) e il blocco di quelli che non contengono . Questi due sottoinsiemi sono disgiunti, allora . Gli elementi di sono tutti e soli i sottoinsiemi di , e siccome ha elementi, per l'ipotesi induttiva . Gli insiemi di sono i complementari di quelli di , e siccome c'è una corrispondenza biunivoca che associa un insieme al suo complementare, anche ha elementi, quindi

 
 Precedente