Dimostrazione: errore da trovare
Ciao, leggevo un libro e mi sono imbattuto nella seguente dimostrazione errata, al lettore era affidato il compito di scovare l'errore ma a me sembra giusta.
Nel libro manca la soluzione. Qualcuno può aiutarmi?
Nel libro manca la soluzione. Qualcuno può aiutarmi?
Risposte
Il passo induttivo non funziona quando $n=1$, quindi la dimostrazione per induzione non funziona.
L’implicazione $P(n) => P(n+1)$ serve a beccare la validità di $P$ per ogni $n in NN$ partendo da $n=1$ (o $n=0$, a seconda dei casi), dunque la dimostrazione dell’implicazione deve esser valida anche e soprattutto per $n=1$ (o $n=0$).
L’implicazione $P(n) => P(n+1)$ serve a beccare la validità di $P$ per ogni $n in NN$ partendo da $n=1$ (o $n=0$, a seconda dei casi), dunque la dimostrazione dell’implicazione deve esser valida anche e soprattutto per $n=1$ (o $n=0$).
Scusa ma non ti seguo. Per n=1 abbiamo A(1): "se a e b sono due numeri interi positivi tali che max(a,b)=1 allora a=b" e gli unici interi positivi che soddisfano la condizione sono 1 e 1... E ovviamente n=0 non funziona perché non esistono due interi positivi che hanno massimo 0.
Buona Pasqua comunque!
Buona Pasqua comunque!
La dimostrazione di $P(n) => P(n+1)$ deve funzionare per tutti gli $n$, in particolare per il primo $n$ disponibile (cioè $0$ o $1$ a seconda dei casi).
In questo caso la dimostrazione di $P(1) => P(2)$ non funziona, dunque la dimostrazione non dimostra.
L’argomento è analogo a quello del problema 7 di questo pdf (testo a pag. 4 e soluzione a pag. 19).
In questo caso la dimostrazione di $P(1) => P(2)$ non funziona, dunque la dimostrazione non dimostra.
L’argomento è analogo a quello del problema 7 di questo pdf (testo a pag. 4 e soluzione a pag. 19).
Ma \( A(1) \) è vera. Infatti se \( a,b \in \mathbb{N}^* \) e \( \max(a,b)=1 \) allora \( a=b=1 \)
Secondo me l'errore sta nel fatto che non dimostri proprio nulla. \( A(n) \) è equivalente a dire che \( \forall a,b \in \mathbb{N}^* \) tale che \( \max(a,b)=n \) allora \( a=b \).
Abbiamo il passo iniziale ( \( A(1) \) ), e supponiamo che sia vera fino a \( A(N) \)
Prendiamo due numeri tale che \( \max(a,b) = N+1 \) vogliamo dimostrare che \( a = b \), quindi passi da \( x=a-1 \) e \( y=b-1 \).
È vero che \( \max(x,y)= N \) ma non hai preso tutte le possibili coppie di numeri tale che \( \max(a,b) = N+1 \), ne hai presa una in particolare quella che ti impone che \( a=b \).
Infatti basta prendere un altra coppia di numeri ( \( \max(a,y) = N+1 \) oppure \( \max(x,b) = N+1 \) ) e hai che i due numeri sono sicuramente diversi se \( x=y \)
Secondo me l'errore sta nel fatto che non dimostri proprio nulla. \( A(n) \) è equivalente a dire che \( \forall a,b \in \mathbb{N}^* \) tale che \( \max(a,b)=n \) allora \( a=b \).
Abbiamo il passo iniziale ( \( A(1) \) ), e supponiamo che sia vera fino a \( A(N) \)
Prendiamo due numeri tale che \( \max(a,b) = N+1 \) vogliamo dimostrare che \( a = b \), quindi passi da \( x=a-1 \) e \( y=b-1 \).
È vero che \( \max(x,y)= N \) ma non hai preso tutte le possibili coppie di numeri tale che \( \max(a,b) = N+1 \), ne hai presa una in particolare quella che ti impone che \( a=b \).
Infatti basta prendere un altra coppia di numeri ( \( \max(a,y) = N+1 \) oppure \( \max(x,b) = N+1 \) ) e hai che i due numeri sono sicuramente diversi se \( x=y \)
"gugo82":
La dimostrazione di $P(n) => P(n+1)$ deve funzionare per tutti gli $n$, in particolare per il primo $n$ disponibile (cioè $0$ o $1$ a seconda dei casi).
In questo caso la dimostrazione di $P(1) => P(2)$ non funziona, dunque la dimostrazione non dimostra.
L’argomento è analogo a quello del problema 7 di questo pdf (testo a pag. 4 e soluzione a pag. 19).
Credo di aver capito cosa intendi, fondamentalmente con quella "dimostrazione" nulla ti assicura che \( x=a-1 \) e/o \( y=b-1 \) siano due numeri interi strettamente positivi, intendi questo?
"3m0o":
[quote="gugo82"]La dimostrazione di $P(n) => P(n+1)$ deve funzionare per tutti gli $n$, in particolare per il primo $n$ disponibile (cioè $0$ o $1$ a seconda dei casi).
In questo caso la dimostrazione di $P(1) => P(2)$ non funziona, dunque la dimostrazione non dimostra.
L’argomento è analogo a quello del problema 7 di questo pdf (testo a pag. 4 e soluzione a pag. 19).
Credo di aver capito cosa intendi, fondamentalmente con quella "dimostrazione" nulla ti assicura che \( x=a-1 \) e/o \( y=b-1 \) siano due numeri interi strettamente positivi, intendi questo?[/quote]
Esatto.
"gugo82":
Esatto.
Esatto a quale mio commento?
Perché sono d'accordo con te che il passo induttivo non è dimostrato in quel modo, (seppur vero), ma secondo me, magari mi sbaglio, c'è un secondo errore nella "dimostrazione" proposta. Indicherò con \( B(n,a,b) \) la proposizione: dati \( a,b \) interi strettamente positivi tale che \( \max(a,b) =n \) allora \( a=b \). Io intendo che per costruzione di \( a,b \), tali che \( \max(a,b)=n+1 \) ed entrambi successivi di coppie \( x, y \) tali che \( B(n,x,y) \) è vera allora forza anche la verità di \( B(n+1,a,b) \), sono equivalenti. \( A(n) \) è equivalente a \( \forall a,b \in \mathbb{N}^* \), \(B(n,a,b)\).
E la dimostrazione proposta fondamentalmente dimostra che \( B(n,a,a) \), è vera \( \forall a \in \mathbb{N}^* \) e per ogni \( n \in \mathbb{N}^* \). Ma questo non è equivalente ad \( A(n) \).
Quindi direi che ci sono almeno 2 errori.
Vi ringrazio 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo