Induzione falsa
Qualcuno per favore potrebbe chiarirmi un dubbio?
Per dimostrare che una proprietà vale per ogni numero naturale, suppongo che sia dimostrata fino ad un certo \(\displaystyle n \), e poi dimostro che allora vale anche per \(\displaystyle n+2 \), \(\displaystyle n+3 \) e \(\displaystyle n+4 \).
È sbagliato concludere che siccome la proprietà vale (per ipotesi) per i numeri immediatamente precendenti ad \(\displaystyle n \) (per esempio \(\displaystyle n-1 \), o \(\displaystyle n-2 \)) allora la proprietà vale anche per \(\displaystyle (n-1)+2 \)...cioè \(\displaystyle n+1 \)? Mi sembra che sia un falso passo induttivo, ma non ne sono certo. Qualcuno mi ragguaglia?
Per dimostrare che una proprietà vale per ogni numero naturale, suppongo che sia dimostrata fino ad un certo \(\displaystyle n \), e poi dimostro che allora vale anche per \(\displaystyle n+2 \), \(\displaystyle n+3 \) e \(\displaystyle n+4 \).
È sbagliato concludere che siccome la proprietà vale (per ipotesi) per i numeri immediatamente precendenti ad \(\displaystyle n \) (per esempio \(\displaystyle n-1 \), o \(\displaystyle n-2 \)) allora la proprietà vale anche per \(\displaystyle (n-1)+2 \)...cioè \(\displaystyle n+1 \)? Mi sembra che sia un falso passo induttivo, ma non ne sono certo. Qualcuno mi ragguaglia?
Risposte
Un passo induttivo del tipo: "Se la proprietà \(\displaystyle P\) vale per i primi numeri fino ad \(\displaystyle n\) \(\Rightarrow\) \(\displaystyle P(n+2)\)" è falso perchè per esempio si potrebbe dimostrare che tutti i numeri sono pari. Infatti assumendo che la proprietà valga per tutti i numeri fino ad \(\displaystyle n\), \(\displaystyle n\) è pari \(\Rightarrow\) \(\displaystyle n+2\) è pari, e per il falso passo induttivo tutti i naturali sarebbero pari.
Non capisco perchè è sbagliato, ma lo posso vedere. Però se una proprietà fosse verificata per i primi \(\displaystyle n\), e si dimostrasse \(\displaystyle P(n+2)\), allora valendo \(\displaystyle P(n-1)\) (per ipotesi), dovrebbe valere \(\displaystyle P(n+1)\) (perchè si è dimostrato che se \(\displaystyle P\) vale fino ad un certo \(\displaystyle n\) \(\Rightarrow\) \(\displaystyle P(n+2)\) ). E quindi si è dimostrato che se \(\displaystyle P\) vale fino ad un certo \(\displaystyle n\) \(\Rightarrow\) \(\displaystyle P(n+1)\). Rientrando nel passo induttivo corretto.
Qualcuno mi può spiegare dov'è l'errore?
E in particolare nel caso in cui il passo induttivo fosse "Se la proprietà \(\displaystyle P\) vale per i primi numeri fino ad \(\displaystyle n\) \(\Rightarrow\) \(\displaystyle P(n+2)\), \(\displaystyle P(n+3)\), \(\displaystyle P(n+4)\)"?
È sbagliato anche questo come quello di sopra?
Non capisco perchè è sbagliato, ma lo posso vedere. Però se una proprietà fosse verificata per i primi \(\displaystyle n\), e si dimostrasse \(\displaystyle P(n+2)\), allora valendo \(\displaystyle P(n-1)\) (per ipotesi), dovrebbe valere \(\displaystyle P(n+1)\) (perchè si è dimostrato che se \(\displaystyle P\) vale fino ad un certo \(\displaystyle n\) \(\Rightarrow\) \(\displaystyle P(n+2)\) ). E quindi si è dimostrato che se \(\displaystyle P\) vale fino ad un certo \(\displaystyle n\) \(\Rightarrow\) \(\displaystyle P(n+1)\). Rientrando nel passo induttivo corretto.
Qualcuno mi può spiegare dov'è l'errore?
E in particolare nel caso in cui il passo induttivo fosse "Se la proprietà \(\displaystyle P\) vale per i primi numeri fino ad \(\displaystyle n\) \(\Rightarrow\) \(\displaystyle P(n+2)\), \(\displaystyle P(n+3)\), \(\displaystyle P(n+4)\)"?
È sbagliato anche questo come quello di sopra?
L'errore non sta nel passo induttivo, ma dovresti aggiustare il caso base: dovresti dimostrare sia $P(0)$ che $P(1)$. In questo modo dovrebbe filare tutto liscio, e la proprietà sarebbe vera per ogni $n\ge 0$
Mm..nell' esempio dei pari che ho fatto in effetti basta verificare il caso base per i primi due naturali per concludere che non tutti i naturali hanno la proprietà di essere pari, perchè già 1 è dispari ed è un controesempio.
Però immaginiamo di avere una proprietà \( \displaystyle P \) per la quale non sia così semplice trovare un controesempio.
Se io verificassi che \( \displaystyle P \) vale per \( \displaystyle n = 0\) e \( \displaystyle n = 1 \) (quindi assumiamo che il caso base sia verificato);
se dimostrassi che se \( \displaystyle P \) vale per i numeri minori o uguali ad \( \displaystyle n \) \( \Rightarrow \) vale per \( \displaystyle n+2 \)...sarebbe corretto dedurre che allora, siccome \( \displaystyle P \) vale per i numeri minori o uguali ad \( \displaystyle (n-1) \), per la dimostrazione di prima \( \Rightarrow\) vale anche per \( \displaystyle (n+1) \)...ovvero che se \( \displaystyle P \) vale per i numeri minori o uguali ad \( \displaystyle n \) \(\Rightarrow\) \( \displaystyle P(n+1) \) (che sarebbe il passo induttivo forte)?
Il problema in sostanza è di aggirare il passo da \( \displaystyle n \) a \( \displaystyle n +1 \), nel contesto del principio di induzione forte, dimostrando che vale l'inferenza da \( \displaystyle n \) a \( \displaystyle n + 2 \), e spostando l' implicazione da \( \displaystyle n -1 \) a \( \displaystyle n +1\). E concludere che allora \( \displaystyle P(n+1) \). È un po' contorto, e a naso mi sembra sbagliato. Vorrei averne una conferma (o una smentita), però se possibile con una spiegazione che mi permetta di capire perchè è sbagliato (o giusto).
In ogni caso, grazie!
Però immaginiamo di avere una proprietà \( \displaystyle P \) per la quale non sia così semplice trovare un controesempio.
Se io verificassi che \( \displaystyle P \) vale per \( \displaystyle n = 0\) e \( \displaystyle n = 1 \) (quindi assumiamo che il caso base sia verificato);
se dimostrassi che se \( \displaystyle P \) vale per i numeri minori o uguali ad \( \displaystyle n \) \( \Rightarrow \) vale per \( \displaystyle n+2 \)...sarebbe corretto dedurre che allora, siccome \( \displaystyle P \) vale per i numeri minori o uguali ad \( \displaystyle (n-1) \), per la dimostrazione di prima \( \Rightarrow\) vale anche per \( \displaystyle (n+1) \)...ovvero che se \( \displaystyle P \) vale per i numeri minori o uguali ad \( \displaystyle n \) \(\Rightarrow\) \( \displaystyle P(n+1) \) (che sarebbe il passo induttivo forte)?
Il problema in sostanza è di aggirare il passo da \( \displaystyle n \) a \( \displaystyle n +1 \), nel contesto del principio di induzione forte, dimostrando che vale l'inferenza da \( \displaystyle n \) a \( \displaystyle n + 2 \), e spostando l' implicazione da \( \displaystyle n -1 \) a \( \displaystyle n +1\). E concludere che allora \( \displaystyle P(n+1) \). È un po' contorto, e a naso mi sembra sbagliato. Vorrei averne una conferma (o una smentita), però se possibile con una spiegazione che mi permetta di capire perchè è sbagliato (o giusto).
In ogni caso, grazie!
Certo che è corretto!
Per rendertene conto puoi fare questa cosa su un foglio:
Scrivi i numeri $0$ e $1$. Ogni numero scritto equivale a dire che hai dimostrato la proprietà per quel numero (infatti stiamo partendo da $0$ e $1$ come casi base)
Adesso cominci a scrivere gli altri numeri: ogni volta puoi scrivere sul foglio un numero $n$ a patto che siano stati già scritti i numeri da $0$ a $n-2$ (mettendo in pratica il nostro passo induttivo)
Ti accorgerai che sei in grado di scrivere tutti i numeri uno dopo l'altro
Per rendertene conto puoi fare questa cosa su un foglio:
Scrivi i numeri $0$ e $1$. Ogni numero scritto equivale a dire che hai dimostrato la proprietà per quel numero (infatti stiamo partendo da $0$ e $1$ come casi base)
Adesso cominci a scrivere gli altri numeri: ogni volta puoi scrivere sul foglio un numero $n$ a patto che siano stati già scritti i numeri da $0$ a $n-2$ (mettendo in pratica il nostro passo induttivo)
Ti accorgerai che sei in grado di scrivere tutti i numeri uno dopo l'altro
Grazie, sembra funzionare. E invece in caso volessi dimostrare che una proprietà vale per tutti i naturali maggiori o uguali ad uno (insomma zero escluso) come dovrei usare il caso base? Mostrando che la proprietà vale per $ 1 $ e per $ 2 $ sarei a posto?
Sì, puoi partire dal valore che vuoi a patto di dimostrare sempre due casi base.
Ok, grazie dell' aiuto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo