Il principio di induzione

Giuseppe Peano fu tra i matematici che, agli inizi del Novecento, misero in discussione i fondamenti della matematica. In particolare egli si dedicò all’aritmetica, riformulando le regole base, conosciute negli ambienti scientifici con il nome di Assiomi di Peano.

Per introdurre i Numeri Naturali, egli si basa su cinque assiomi precisi:

• 1 è un numero;
• Il successivo di un numero è un numero;
• 1 non è successivo di nessun numero;
• Se i successivi di due numeri sono uguali, anche i due numeri sono uguali;
• Se un insieme A⊂ N contiene il numero 1 e il successivo di ogni suo elemento, allora A = N

Tra tutti, essenziali per caratterizzare il sistema dei numeri naturali, quello che ha un ruolo importante nelle definizione delle operazioni con i numeri e nella dimostrazione delle proprietà relative, è il quinto, noto come principio di induzione.
Gli assiomi enunciati riguardano, alla fine, una sola operazione:
il passaggio da un numero intero a al suo successivo, che indicheremo con S(a).
E’ interessante analizzare la definizione della somma e del prodotto, in quanto si utilizza in modo implicito il principio di induzione.

SOMMA

La somma a+b di due numeri naturali è definita dalle relazioni seguenti:

a+1=S(a)
a+(b+1)=(a+b)+1 (A)

A questa definizione Peano aggiunge una nota esplicativa:

Questa definizione si deve leggere così: se a e b sono numeri, e se a+b è un numero, ma a+(b+1) non è stato ancora definito, allora a+(b+1) significa il numero che segue a+b.

Questo è un esempio di definizione ricorsiva. Intuitivamente, la prima relazione definisce la somma a+b per b = 1; la seconda ci dice che se essa è definita per b, lo è anche per b+1. Di conseguenza, la somma è definita per ogni numero b.

Altro esempio di definizione ricorsiva è quella del PRODOTTO.

Il prodotto ab di due numeri naturali è definito dalle relazioni: 

a⋅1=a
a(b+1)=ab+a

Per concludere, riporto come dimostrazione esplicativa, quella della proprietà associativa della somma.

Teorema (Proprietà associativa): Per ogni terna di numeri a, b e c si ha (a+b)+c=a+(b+c) (B)

Dimostrazione. La (B) è vera per c= 1 ; infatti in questo caso non è altro che la (A). Supponiamo ora che sia vera per c e dimostriamola per c+1. Si ha (a+b)+(c+1)≝[(a+b)+c]+1≝[a+(b+c)]+1≝a+[(b+c)+1]≝a+[b+(c+1)]

Per il principio di induzione, la (B) vale per ogni c, e il teorema è dimostrato.