Prima di tutto c’è un po’ di confusione di forma nella domanda posta: i punti argomentativi del principio di induzione sono infatti solo due, e non tre come sembrerebbe dal testo della domanda; in particolare i punti b) e c) sono lo stesso punto, in sostanza. Infatti, b e c costituiscono una sola implicazione che va dimostrata, e precisamente:
proprietà vera per n ⇒ proprietà vera per n+1.
È vero che va supposta per ipotesi la validità della proprietà assegnata per un generico n, ma bisogna poi dimostrare che quindi la proprietà vale anche per il numero successivo: questo meccanismo permette di innescare un ragionamento iterativo che sta alla base concettuale del principio di induzione. Il principio di induzione correttamente formulato afferma quanto segue. Sia P(n) una proposizione che dipende da n naturale e supponiamo di voler dimostrare che P(n) è vera per ogni scelta di n. Basta quindi mostrare che
1) P(0) vera (o P(1) o P(n0) essendo n0 il primo naturale per cui ha senso formulare la proposizione P);
2) P(n) vera ⇒ P(n+1) vera.
Come mai il principio di induzione funziona? Le condizioni 1 e 2 dicono che P(0) è vera (la 1), quindi P(1) è vera (la 2 applicata con n=0), quindi P(2) è vera (la 2 applicata con n=1), quindi P(3) è vera (la 2 applicata con n=2), e così via.
Vediamo un semplice esempio che illustra come funziona una dimostrazione per induzione. Supponiamo di voler dimostrare che per ogni n naturale si ha che 10n-1 è divisibile per 9. Cominciamo a mostrare che tale proprietà vale per n=1, il primo intero che rende la proprietà non banale. Si ha 101-1=10-1=9 e quindi la proprietà è vera. Dimostriamo ora la condizione 2): supponiamo quindi che 10n-1 sia divisibile per 9 e dimostriamo che 10n+1-1 è divisibile per 9. Equivalentemente va mostrato che esiste un naturale h tale che 10n+1-1=9h, cioé 10n+1=9h+1. Essendo 10n-1 divisibile per 9 si ha che esiste un naturale k tale che 10n-1=9k, ovvero 10n=9k+1. Dunque
10n+1=10·10n=10(9k+1)=90k+10=90k+9+1=9(10k+1)+1
e quindi basta porre h=10k+1 per avere che 10n+1=9h+1, che è la tesi.
Concludiamo con un approfondimento teorico, ovvero discutendo da dove ha origine il principio di induzione e come è collocato oggi nella matematica. Il principio di induzione è oggi un teorema di teoria degli insiemi ma che originariamente fu preso, dal matematico italiano G. Peano (1858-1932), come assioma, assieme ad altri, a fondamento dell’aritmetica: si tratta di un fatto molto intuitivo, che in sostanza formalizza l’atto del contare. Nella sua forma insiemistica esso dice che se un insieme A ⊆ N, essendo N l’insieme dei numeri naturali, è tale per cui:
1) 0 ∈ A;
2) n ∈ A ⇒ n+1 ∈ A
allora A=N.
La variante operativa già descritta si ottiene adesso facilmente. Infatti, se P(n) è una proposizione che dipende da n e vogliamo dimostrare che P(n) è vera per ogni scelta di n ∈ N allora possiamo fare in questo modo. Sia A:={n ∈ N : P(n) è vera} e dimostriamo, usando il principio di induzione, che A=N. Basta quindi mostrare che
1) P(0) vera;
2) P(n) vera ⇒ P(n+1) vera
che coincide con quanto illustrato poco fa.
Per quanto sia intuitivo, il principio di induzione può essere dimostrato all’interno della teoria degli insiemi, anche se sostanzialmente esso è già compreso in uno degli assiomi della teoria stessa (adottiamo qui la teoria degli insiemi di Zermelo-Fraenkel), e precisamente l’assioma di infinità, che dice quanto segue:
Assioma di infinità: Esiste un insieme X tale che:
A) ∅ ∈ X;
B) x ∈ X ⇒ x ∪ {x} ∈ X.
L’idea dell’assioma di infinità è quella di definire i numeri naturali a partire dall’insieme vuoto, e questo si può fare in realtà senza bisogno di assiomi. Infatti, la A e la B precedenti ci dicono come fare: poniamo
0:=∅, 1:=∅ ∪ {∅}, 2:=1 ∪ {1}, 3:=2 ∪ {2}, …
I "numeri" così definiti sono noti in letteratura anche come interi di Von Neumann; l’assioma di infinità dice sostanzialmente che esiste un insieme X che contiene gli interi di Von Neumann. Tale insieme non è ancora l’insieme dei numeri naturali, in quanto quest’ultimo vorremmo che sia unico mentre A e B non bastano per l’unicità: basta chiamare N l’intersezione di tutti gli insiemi che soddisfano A e B. È facile mettere su N l’operazione di successivo, ovvero si pone
s(n):=n ∪ {n}.
In tal modo per ricorsione si definisce la somma tra naturali, ma non entriamo nel dettaglio di ciò: basta osservare che si ha n+1=s(n). Si controlla poi facilmente che N soddisfa al principio di induzione: la tesi discende dal fatto che N è il più piccolo insieme che soddisfa A e B.