Ragionamento per induzione visibilmente fallace... ma perché?
Chi mi aiuta a stanare il granchio che ho preso in questo ragionamento?
Devo dimostrare che un monoide finito che soddisfa la legge di cancellazione è un gruppo.
Per induzione sul numero di $n$ degli elementi del monoide $(A, *)$:
1) Base induttiva: se $n = 1$, allora $A = {e}$ dove $e$ è l'elemento neutro: si verifica che la proposizione è vera
2) Suppongo che la proposizione valga per qualsiasi monoide di $n$ elementi $A = {e, n_2, ... n_n}$.
Per ipotesi induttiva $A$ è un gruppo, quindi tutti i suoi elementi sono invertibili.
3) Sia ora $B = {e, n_2, ... n_n, x}$.
I primi n elementi sono invertibili per il passaggio (2). Se dimostro che anche $x$ è invertibile ho finito.
Prendo allora $A' = {e, n_3, ... n_n, x}$ (cioè tolgo da A un elemento, per esempio $e_2$, e gli metto $x$). Allora $A'$ ha $n$ elementi e per ipotesi induttiva tutti i suoi elementi sono invertibili, perciò anche $x$.
Dove sbaglio? Non ho usato la legge di cancellazione... e poi con questa struttura di ragionamento uno potrebbe dire che, se un singoletto ha una proprietà e se ogni insieme di $n$ elementi ha una proprietà, allora tutti elementi di un insieme finito hanno questa proprietà: basta fare come sopra... ma comunque non mi sembra vero.
Forse la fregatura è proprio nel passaggio che sembrava più "innocuo": la base induttiva. Quando dico "per $n=1$", il fatto che $A$ non è qualsiasi singoletto ma ${e}$ inficia il ragionamento?
p.s. Il ragionamento che riporta il libro è molto più bello e sintetico, ma volevo vedere cosa succede con l'induzione.
Devo dimostrare che un monoide finito che soddisfa la legge di cancellazione è un gruppo.
Per induzione sul numero di $n$ degli elementi del monoide $(A, *)$:
1) Base induttiva: se $n = 1$, allora $A = {e}$ dove $e$ è l'elemento neutro: si verifica che la proposizione è vera
2) Suppongo che la proposizione valga per qualsiasi monoide di $n$ elementi $A = {e, n_2, ... n_n}$.
Per ipotesi induttiva $A$ è un gruppo, quindi tutti i suoi elementi sono invertibili.
3) Sia ora $B = {e, n_2, ... n_n, x}$.
I primi n elementi sono invertibili per il passaggio (2). Se dimostro che anche $x$ è invertibile ho finito.
Prendo allora $A' = {e, n_3, ... n_n, x}$ (cioè tolgo da A un elemento, per esempio $e_2$, e gli metto $x$). Allora $A'$ ha $n$ elementi e per ipotesi induttiva tutti i suoi elementi sono invertibili, perciò anche $x$.
Dove sbaglio? Non ho usato la legge di cancellazione... e poi con questa struttura di ragionamento uno potrebbe dire che, se un singoletto ha una proprietà e se ogni insieme di $n$ elementi ha una proprietà, allora tutti elementi di un insieme finito hanno questa proprietà: basta fare come sopra... ma comunque non mi sembra vero.
Forse la fregatura è proprio nel passaggio che sembrava più "innocuo": la base induttiva. Quando dico "per $n=1$", il fatto che $A$ non è qualsiasi singoletto ma ${e}$ inficia il ragionamento?
p.s. Il ragionamento che riporta il libro è molto più bello e sintetico, ma volevo vedere cosa succede con l'induzione.
Risposte
il problema sta nel fatto che quando togli un elemento non puoi farlo sempre, ma da 3 in poi.
in pratica il passo base dovresti farlo con n=2 e non n=1
in pratica il passo base dovresti farlo con n=2 e non n=1
Mannaggia non ci ho capito molto... 
Il successore deve essere univocamente determinato, p. es. un numero n individua univocamente il suo successore n + 1.
A partire da ogni insieme di n elementi invece ho infiniti insiemi di n+1 elementi... E' per questo?
Il successore deve essere univocamente determinato, p. es. un numero n individua univocamente il suo successore n + 1.
A partire da ogni insieme di n elementi invece ho infiniti insiemi di n+1 elementi... E' per questo?
Il motivo per cui l'induzione fallisce è lo stesso che sta alla base del paradosso dei cavalli: leggi qui.
Non riesco a capire molto, l'unica cosa che mi convince sempre di più è un errore sulla base induttiva 
Prendo:
1) la formulazione (non formale) del principio di induzione
2) un esempio corretto di dimostrazione per induzione
3) il paradosso dei cavalli che hai linkato (Facciamo: "In un insieme in cui esiste un cavallo bianco, tutti i cavalli sono bianchi")
Tesi da dimostrare nei casi 1, 2,3:
A1) La proposizione è vera per ogni n
A2) La somma dei primi n numeri naturali è n(n+1)/2
A3) In un insieme in cui esiste un cavallo bianco, tutti i cavalli sono bianchi
Base induttiva nei casi 1, 2, 3:
B1) La proposizione è vera per n = 1
B2) 1 = 1*2/2
B3) Esiste un insieme con un cavallo bianco (?)
Qual è la differenza fra B2 e B3?
- In B2 so chi è n = 1: è semplicemente il numero 1.
- In B3 sarei tentata di prendere il singoletto cavallo bianco, ma ci sono altri singoletti: a chi corrisponde la proposizione per n=1? Non è definita bene... Se per qualsiasi singoletto il cavallo fosse bianco avrei già la tesi e un circolo vizioso.
Quindi nel principio di induzione dire "vera per n = 1" significa vera per il numero naturale 1: anche quando la proposizione non è sui numeri naturali, è come ricalcata sui numeri naturali ed è come se fosse una dimostrazione riguardante N. Non si capisce un tubo di quello che ho scritto, lo so.... ma non riesco a esprimere questo concetto](/datas/uploads/forum/emoji/eusa_wall.gif "Brick wall")
Prendo:
1) la formulazione (non formale) del principio di induzione
2) un esempio corretto di dimostrazione per induzione
3) il paradosso dei cavalli che hai linkato (Facciamo: "In un insieme in cui esiste un cavallo bianco, tutti i cavalli sono bianchi")
Tesi da dimostrare nei casi 1, 2,3:
A1) La proposizione è vera per ogni n
A2) La somma dei primi n numeri naturali è n(n+1)/2
A3) In un insieme in cui esiste un cavallo bianco, tutti i cavalli sono bianchi
Base induttiva nei casi 1, 2, 3:
B1) La proposizione è vera per n = 1
B2) 1 = 1*2/2
B3) Esiste un insieme con un cavallo bianco (?)
Qual è la differenza fra B2 e B3?
- In B2 so chi è n = 1: è semplicemente il numero 1.
- In B3 sarei tentata di prendere il singoletto cavallo bianco, ma ci sono altri singoletti: a chi corrisponde la proposizione per n=1? Non è definita bene... Se per qualsiasi singoletto il cavallo fosse bianco avrei già la tesi e un circolo vizioso.
Quindi nel principio di induzione dire "vera per n = 1" significa vera per il numero naturale 1: anche quando la proposizione non è sui numeri naturali, è come ricalcata sui numeri naturali ed è come se fosse una dimostrazione riguardante N. Non si capisce un tubo di quello che ho scritto, lo so.... ma non riesco a esprimere questo concetto
Quindi nel principio di induzione dire "vera per n = 1" significa vera per il numero naturale 1: anche quando la proposizione non è sui numeri naturali, è come ricalcata sui numeri naturali ed è come se fosse una dimostrazione riguardante N. Non si capisce un tubo di quello che ho scritto, lo so.... ma non riesco a esprimere questo concetto
Quello che dici è vero e si può anche mettere giù più formalmente, ma adesso vista l'ora tarda mi limito a rispondere all'altro tuo dubbio:
Il punto dove sbagli è che la dimostrazione del passo induttivo (che sia quello dei cavalli o quello del gruppo), vale solo per insiemi con un numero di elementi superiore strettamente a uno, dunque pur essendo valida, per applicare l'induzione hai bisogno di partire da un insieme con più di un elemento, quindi non puoi avere come base per l'induzione il singoletto! Se tu riuscissi a trovare come base per l'induzione un insieme di cardinalità $>=2$ , allora potresti applicarla, il problema è che ovviamente per $n=2$ in nessuno dei due casi riesci ad avere una base per l'induzione.
Il fatto è che nella tua dimostrazione dici: suppongo che valga per qualsiasi monoide di $n$ elementi , ma questo esclude che $n=0$ , visto che un monoide deve avere sempre un elemento neutro.
Questo però non mi sembra il motivo della fallacia, magari un'imprecisione nell'esporre il ragionamento. Anzi... non mi pare errato scrivere "suppongo la proposizione è vera per ogni n", perché il passo induttivo non dice
CHE la proposizione vale per n, ma che SE vale per n va dimostrato valere per n+1.
Quindi, se poni come base induttiva n = 1, si concluderà che la proposizione vale per $n >=1$.
Il problema mi sa che è un altro...
CHE la proposizione vale per n, ma che SE vale per n va dimostrato valere per n+1.
Quindi, se poni come base induttiva n = 1, si concluderà che la proposizione vale per $n >=1$.
Il problema mi sa che è un altro...
Scusa jitter ma nel punto 3 come dimostri che i primi n elementi di B formano un monoide? E come dimostri che A' è un monoide?
"jitter":
... perché il passo induttivo non dice CHE la proposizione vale per n, ma che SE vale per n va dimostrato valere per n+1.
Ma la dimostrazione del passo induttivo deve valere per TUTTI gli $n$, compreso quello del passo base ...
Vedi anche qui
Detto in altro modo, più grossolano: hai dimostrato il passo base, ok; la dimostrazione del passo induttivo funziona (apparentemente), ok; ma il procedimento che hai usato nella dimostrazione del passo induttivo riesci ad usarlo per TUTTI gli $n$?
Cordialmente, Alex
Ciao Martino,
volevo porre come ipotesi induttiva che "la proprietà di essere un gruppo vale per una struttura con n elementi" e cercare di dedurne che "la proprietà di essere un gruppo vale per una struttura con n+1 elementi"...
volevo porre come ipotesi induttiva che "la proprietà di essere un gruppo vale per una struttura con n elementi" e cercare di dedurne che "la proprietà di essere un gruppo vale per una struttura con n+1 elementi"...
Jitter per applicarla ad A' nel passo 3 devi prima mostrare che A' è un monoide (ovviamente!).
"Martino":
Jitter per applicarla ad A' nel passo 3 devi prima mostrare che A' è un monoide (ovviamente!).
E' vero!!!!!
"jitter":
[quote="Martino"]Jitter per applicarla ad A' nel passo 3 devi prima mostrare che A' è un monoide (ovviamente!).
E' vero!!!!!
[/quote]Ma guarda te se dovevo andare a far mille ricerche su cavalli bianchi e donne bionde... Comunque quel paradosso è tosto
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo