Il Principio di Induzione Matematica (parte 1)

Nel post dedicato al nostro illustre connazionale Giuseppe Peano, abbiamo introdotto i primi quattro assiomi, uno strumento formale per definire l’insieme dei numeri naturali.

Nel post dedicato a Cantor abbiamo messo nella nostra borsa del matematico strumenti di fondamentale importanza: gli insiemi il concetto di appartenenza, le relazioni tra insiemi, il concetto di cardinalità. Con questi ferri del mestiere siamo in grado di costruire modelli che rappresentano realtà piuttosto complesse.

L’insieme dei numeri naturali è il primo esempio di insieme infinito, che sappiamo essere definito enumerabile. Sappiamo che gli infiniti non sono tutti uguali e che questa classe di infinito è estremamente particolare, perché è il primo livello di infinito possibile.

Ma come possiamo trattare gli insiemi infiniti ? Che strumenti abbiamo a disposizione per confrontare efficacemente e, soprattutto, in modo rigoroso e formale gli insiemi infiniti ? Il quinto assioma di Peano è la risposta a tutte queste domande, fornendo uno strumento finito per la dimostrazione di proprietà su insiemi infiniti enumerabili.

Questo è il primo di una breve serie di post dove approfittiamo del  quinto postulato per introdurre uno strumento fondamentale della borsa del matematico: il Principio di Induzione Matematica.

Ci occorono tre oggetti

A: un insieme infinito enumerabile.
P(n): una proprietà che vogliamo verificare per tutto l’insieme A
SUCC: la funzione successore definita come da assiomi di Peano.

Il principio di induzione matematica è formulabile come segue:

Se P(n) è VERA per il primo elemento di A (passo base dell’induzione)

e

supponendo che la proprietà P vale per l’elemento n di A (ipotesi induttiva) allora  P vale anche per P(SUCC(n))

allora

P(n) è VERA per tutti gli elementi di A.

Usiamo il formalismo matematico per descrivere la stessa cosa:

Se

P(0) è vera e P(n) è vera => P(SUCC(n)) è vera

allora

P(n) è vera per ogni n appartenente ad A.

Il principio di induzione si regge su un impianto estremamente semplice: se la proprietà è vera per il primo elemento di un insieme infinito enumerabile e se, supponendola vera per il generico insieme lo è anche per il suo successore, allora deve forzatamente essere vera per tutto l’insieme.

E’ uno strumento potentissimo per verificare proprietà su insiemi infiniti usando un numero finito di passi. E ora, prima di aggiornarci per un esempio pratico a domani, ecco a voi la formulazione matematica più sintetica possibile:

( P(0) AND P(n) => P(SUCC(n)) ) <=> P(n)  per ogni nA

non è meravigliosamente breve ? E pensare che serve a contare l’infinito !

A domani.