Il principio di induzione è un assioma dei numeri naturali, cioè una proposizione considerata vera e che ci permette di dimostrare alcune proprietà dei numeri naturali e verificare che alcune operazioni o proposizioni sono vere per tutti i numeri naturali. Poiché i numeri naturali sono infiniti, questo principio ci aiuta a verificare una proposizione senza dovere ripetere i passaggi all’infinito.
Questo principio si basa sul fatto che se una proposizione è vera per il numero 0 e preso un qualsiasi numero, la proposizione è valida anche per il suo successore, allora vale sempre.
\[ P(0) \land \forall n \in \mathbb{N} \quad (P(n) \implies P(n + 1)) \implies \forall n \in \mathbb{N} \quad P(n) \]Altra definizione:
\[ P(n), \quad n \in \mathbb{N} : n \implies P(0) \implies P(n + 1) \implies P(n) \]Le due definizioni qui riportate sono equivalenti. Nel secondo caso stiamo dicendo: sia un proposizione sui numeri naturali; se la proposizione è vera per 0 e di conseguenza è vera anche per il successore di qualsiasi numero allora vale per tutti i numeri naturali.
Vediamo un esempio abbastanza semplice: dimostriamo che qualunque numero sommato all’elemento neutro, lo 0, dà quel numero.
\[ P(n): n + 0 = n, \forall n \in \mathbb{N} \]Per il principio di induzione dobbiamo intanto verificare che valga per il numero 0.
\[ P(0): 0 + 0 = 0 \]Ora dobbiamo verificare che se vale per un qualsiasi numero, allora vale anche per il suo successore.
\[ P(n): n + 0 = n \implies P(n + 1): (n + 1) + 0 = n + 1 \]Per la definizione di somma di numeri naturali:
\[ (n + 1) + 0 = (n + 0) + 1 = n + 1 \]Oppure:
\[ n^+ + 0 = (n + 0)^+ = n^+ \]Quindi abbiamo dimostrato che qualunque numero sommato allo 0 dà quel numero.