Gauss1991 ha scritto:non capisco questa catena in pratica dopo aver dimostrato che la proprietà vale per un numero n+1 cosa succede??
perchè la tesi dovrebbe essere vera?
e perchè è necessario dimostrare la proprietà anche per un n generico tipo 0 o 1??
non sarebbe lo stesso saltare questo passaggio e dimostrare la proprietà per n+1 direttamente??
Il principio d'induzione matematica (in breve PIM) non si capisce se non si studia la teoria (come tutta la Matematica, direi).
Il PIM è uno degli assiomi dei numeri naturali e recita quanto segue:
Se \( \displaystyle T\subseteq \mathbb{N} \) è un insieme tale che:
1. \( \displaystyle 0\in T \) ,
2. per ogni \( \displaystyle n\in T \) si ha anche \( \displaystyle n+1\in T \) ,
allora \( \displaystyle T=\mathbb{N} \) .
(di solito, più correttamente, al posto di \( \displaystyle n+1 \) si usa la funzione consecutivo \( \displaystyle c(n) \) , però non l'ho definita e mi sono arrangiato così).
Come interpretare il PIM?
Testo nascosto, fai click qui per vederlo
Il PIM si può interpretare come una condizione necessaria e sufficiente affinché un sottoinsieme \( \displaystyle T \) di \( \displaystyle \mathbb{N} \) coincida con tutto \( \displaystyle \mathbb{N} \) .
Tale interpretazione non è campata in aria, ma si basa su un'intuizione sensata: se un insieme di numeri naturali contiene il primo numero naturale, cioè \( \displaystyle 0 \) , e se esso contiene il consecutivo di ogni suo elemento, allora tale insieme coincide con \( \displaystyle \mathbb{N} \) . Infatti per 1 \( \displaystyle 0\in T \) , e da ciò e 2 segue che \( \displaystyle 1=0+1\in T \) ; ma dalla 2 allora segue che anche \( \displaystyle 2=1+1\in T \) ; ed ancora dalla 2 segue che pure \( \displaystyle 3=2+1\in T \) ... E si continua così ad libitum.
Più semplicemente, si può contestualizzare il discorso così: se domani faccio colazione col cornetto e se mi impongo di fare colazione col cornetto ogni giorno seguente ad un giorno in cui ho fatto colazione col cornetto, allora continuerò a mangiare cornetti a colazione per il resto della mia vita.
Se la mia vita (e quella dell'universo in cui ci troviamo) fosse infinita, continuerei a mangiare cornetti a colazione per sempre.
Tale interpretazione non è campata in aria, ma si basa su un'intuizione sensata: se un insieme di numeri naturali contiene il primo numero naturale, cioè \( \displaystyle 0 \) , e se esso contiene il consecutivo di ogni suo elemento, allora tale insieme coincide con \( \displaystyle \mathbb{N} \) . Infatti per 1 \( \displaystyle 0\in T \) , e da ciò e 2 segue che \( \displaystyle 1=0+1\in T \) ; ma dalla 2 allora segue che anche \( \displaystyle 2=1+1\in T \) ; ed ancora dalla 2 segue che pure \( \displaystyle 3=2+1\in T \) ... E si continua così ad libitum.
Più semplicemente, si può contestualizzare il discorso così: se domani faccio colazione col cornetto e se mi impongo di fare colazione col cornetto ogni giorno seguente ad un giorno in cui ho fatto colazione col cornetto, allora continuerò a mangiare cornetti a colazione per il resto della mia vita.
Se la mia vita (e quella dell'universo in cui ci troviamo) fosse infinita, continuerei a mangiare cornetti a colazione per sempre.
Come si usa il PIM?
Testo nascosto, fai click qui per vederlo
In maniera brutale, di solito si dice: "Verifica che la tua proprietà è vera per \( \displaystyle n=0 \) ; poi dimostra che la proprietà è verificata per \( \displaystyle n+1 \) se essa è vera per \( \displaystyle n \) ; allora la proprietà è vera per ogni numero naturale \( \displaystyle n \) ".
Questa è una versione semplicistica di porre la questione, ma esprime il succo del ragionamento induttivo.
Ora vediamo un po' cosa accade davvero.
Diciamo che è assegnata una certa proposizione \( \displaystyle \mathcal{P} (n) \) che ha come variabile un numero naturale (ad esempio: \( \displaystyle \mathcal{P}(n)=\text{"} 3^{2^{n+1}} \text{ è una potenza di } 9\text{"} \) , oppure \( \displaystyle \mathcal{P}(n) =\text{"} (n+1)^n \geq (n+1)! \text{"} \) ) e si vuole dimostrare che tale proposizione è vera per ogni numero naturale.
Come procedere? Ebbene, innanzitutto si definisce un insieme:
\( \displaystyle T:=\{ n\in \mathbb{N}:\ \mathcal{P}(n) \text{ è vera}\} \) ;
evidentemente se \( \displaystyle \mathcal{P}(n) \) è sempre falsa (e.g. \( \displaystyle \mathcal{P}(n)=\text{"} 2n \text{ è dispari"} \) ), allora \( \displaystyle T \) è vuoto ed è inutile continuare. Ora, si deve far vedere che \( \displaystyle T=\mathbb{N} \) : visto che il PIM è una condizione necessaria e sufficiente affinche l'uguaglianza \( \displaystyle T=\mathbb{N} \) sia vera, basterà dimostrare che \( \displaystyle T \) verifica il PIM, ossia che $T$ soddisfa le condizioni 1 e 2.
- La 1 si verifica "a mano": cioè si scrive esplicitamente \( \displaystyle \mathcal{P}(0) \) e si vede se essa è una proposizione vera; se è vera si va avanti, altrimenti ci si ferma concludendo che \( \displaystyle T\neq \mathbb{N} \) .
Se \( \displaystyle \mathcal{P}(0) \) è vera, tale proposizione si chiama base dell'induzione.
- Ora bisogna verificare la 2. Per fare ciò, si deve fissare \( \displaystyle n\in T \) e si deve mostrare che \( \displaystyle n+1\in T \) : data la definizione di \( \displaystyle T \) , ciò equivale a dire che fissato \( \displaystyle n \) tale che \( \displaystyle \mathcal{P}(n) \) è vera si deve dimostrare che anche \( \displaystyle \mathcal{P}(n+1) \) è vera. Se si riesce a fare questa dimostrazione, allora scatta il PIM ed abbiamo \( \displaystyle T=\mathbb{N} \) ; altrimenti concludiamo che \( \displaystyle T\neq \mathbb{N} \) .
La proprietà 2 si chiama di solito passo induttivo, e l'ipotesi " \( \displaystyle \mathcal{P}(n) \) è vera" di solito si chiama ipotesi induttiva.
Questa è una versione semplicistica di porre la questione, ma esprime il succo del ragionamento induttivo.
Ora vediamo un po' cosa accade davvero.
Diciamo che è assegnata una certa proposizione \( \displaystyle \mathcal{P} (n) \) che ha come variabile un numero naturale (ad esempio: \( \displaystyle \mathcal{P}(n)=\text{"} 3^{2^{n+1}} \text{ è una potenza di } 9\text{"} \) , oppure \( \displaystyle \mathcal{P}(n) =\text{"} (n+1)^n \geq (n+1)! \text{"} \) ) e si vuole dimostrare che tale proposizione è vera per ogni numero naturale.
Come procedere? Ebbene, innanzitutto si definisce un insieme:
\( \displaystyle T:=\{ n\in \mathbb{N}:\ \mathcal{P}(n) \text{ è vera}\} \) ;
evidentemente se \( \displaystyle \mathcal{P}(n) \) è sempre falsa (e.g. \( \displaystyle \mathcal{P}(n)=\text{"} 2n \text{ è dispari"} \) ), allora \( \displaystyle T \) è vuoto ed è inutile continuare. Ora, si deve far vedere che \( \displaystyle T=\mathbb{N} \) : visto che il PIM è una condizione necessaria e sufficiente affinche l'uguaglianza \( \displaystyle T=\mathbb{N} \) sia vera, basterà dimostrare che \( \displaystyle T \) verifica il PIM, ossia che $T$ soddisfa le condizioni 1 e 2.
- La 1 si verifica "a mano": cioè si scrive esplicitamente \( \displaystyle \mathcal{P}(0) \) e si vede se essa è una proposizione vera; se è vera si va avanti, altrimenti ci si ferma concludendo che \( \displaystyle T\neq \mathbb{N} \) .
Se \( \displaystyle \mathcal{P}(0) \) è vera, tale proposizione si chiama base dell'induzione.
- Ora bisogna verificare la 2. Per fare ciò, si deve fissare \( \displaystyle n\in T \) e si deve mostrare che \( \displaystyle n+1\in T \) : data la definizione di \( \displaystyle T \) , ciò equivale a dire che fissato \( \displaystyle n \) tale che \( \displaystyle \mathcal{P}(n) \) è vera si deve dimostrare che anche \( \displaystyle \mathcal{P}(n+1) \) è vera. Se si riesce a fare questa dimostrazione, allora scatta il PIM ed abbiamo \( \displaystyle T=\mathbb{N} \) ; altrimenti concludiamo che \( \displaystyle T\neq \mathbb{N} \) .
La proprietà 2 si chiama di solito passo induttivo, e l'ipotesi " \( \displaystyle \mathcal{P}(n) \) è vera" di solito si chiama ipotesi induttiva.
Questo è; niente di più, niente di meno.
***
Esempio:
Testo nascosto, fai click qui per vederlo
Ad esempio, dimostriamo che \( \displaystyle \mathcal{P}(n)=\text{"} 3^{2^{n+1}} \text{ è una potenza di } 9 \text{"} \) è vera per ogni $n\in \mathbb{N}$.
Controlliamo la base dell'induzione: abbiamo \( \displaystyle \mathcal{P}(0)=\text{"} 3^{2^1} \text{ è una potenza di } 9 \text{"} \) è una proposizione vera, perchè \( \displaystyle 3^{2^1}=3^2=9 \) è una potenza di \( \displaystyle 9 \) .
Dimostriamo il passo induttivo: assumiamo come ipotesi induttiva che \( \displaystyle \mathcal{P}(n)=\text{"} 3^{2^{n+1}} \text{ è una potenza di } 9 \text{"} \) sia vera e facciamo vedere che pure \( \displaystyle \mathcal{P}(n+1)=\text{"} 3^{2^{(n+1)+1}} \text{ è una potenza di } 9 \text{"} \) è vera; per le proprietà delle potenze abbiamo \( \displaystyle 3^{2^{(n+1)+1}}=3^{2\ 2^{n+1}}=(3^2)^{2^{n+1}}= 9^{2^{n+1}} \) ; quindi è vero che \( \displaystyle 3^{2^{(n+1)+1}} \) è una potenza di \( \displaystyle 9 \) , ossia è vera \( \displaystyle \mathcal{P}(n+1) \) .
Conseguentemente, essendo verificato il PIM, l'insieme \( \displaystyle T=\{ n\in \mathbb{N}:\ \mathcal{P} (n) \text{ è vera}\} \) coincide con tutto \( \displaystyle \mathbb{N} \) , come volevamo. \( \displaystyle \square \)
Controlliamo la base dell'induzione: abbiamo \( \displaystyle \mathcal{P}(0)=\text{"} 3^{2^1} \text{ è una potenza di } 9 \text{"} \) è una proposizione vera, perchè \( \displaystyle 3^{2^1}=3^2=9 \) è una potenza di \( \displaystyle 9 \) .
Dimostriamo il passo induttivo: assumiamo come ipotesi induttiva che \( \displaystyle \mathcal{P}(n)=\text{"} 3^{2^{n+1}} \text{ è una potenza di } 9 \text{"} \) sia vera e facciamo vedere che pure \( \displaystyle \mathcal{P}(n+1)=\text{"} 3^{2^{(n+1)+1}} \text{ è una potenza di } 9 \text{"} \) è vera; per le proprietà delle potenze abbiamo \( \displaystyle 3^{2^{(n+1)+1}}=3^{2\ 2^{n+1}}=(3^2)^{2^{n+1}}= 9^{2^{n+1}} \) ; quindi è vero che \( \displaystyle 3^{2^{(n+1)+1}} \) è una potenza di \( \displaystyle 9 \) , ossia è vera \( \displaystyle \mathcal{P}(n+1) \) .
Conseguentemente, essendo verificato il PIM, l'insieme \( \displaystyle T=\{ n\in \mathbb{N}:\ \mathcal{P} (n) \text{ è vera}\} \) coincide con tutto \( \displaystyle \mathbb{N} \) , come volevamo. \( \displaystyle \square \)
***
Evidentemente, poi, il principio può essere messo in varie forme, oppure generalizzato: una generalizzazione che torna utile in pratica è la seguente:
Se \( \displaystyle T\subseteq \mathbb{N} \) è un insieme tale che:
1. esiste un \( \displaystyle b\in T \) (ossia \( \displaystyle T \) è non vuoto),
2. per ogni \( \displaystyle n\in T \) si ha anche \( \displaystyle n+1\in T \) ,
allora \( \displaystyle \mathbb{N}\setminus \{ 0,\ldots ,b-1\} =\{ b, b+1, b+2,\ldots \} \subseteq T \) .
che ti assicura che l'insieme \( \displaystyle T \) contiene almeno tutti i numeri che seguono \( \displaystyle b \) .
Ciò si può leggere anche alla maniera che segue: se hai assegnata una proposizione \( \displaystyle \mathcal{P}(n) \) e (1) sai che \( \displaystyle \mathcal{P}(b) \) è vera e (2) è verificato il passo induttivo per \( \displaystyle n\geq b \) , allora \( \displaystyle \mathcal{P}(n) \) è vera almeno per ogni \( \displaystyle n\geq b \) .
Questa è la forma del PIM che si applica al discorso delle colazioni con cornetto che ho fatto più su.
