Induzione forte
Giovanni
1) Il "Principio di induzione forte" e' chiamato anche:
Principio di induzione completa o sul decorso dei valori.
2) L'espressione "forte" si riferisce al fatto che, mentre l'induzione
semplice richiede (nel passo induttivo) solo che P(n-1) => P(n), in
quella forte si richiede che tutti gli m < n siano P.
In realta' i due principi sono equivalenti (v. (4))
3) Enunciato formale:
(n) ((m) (m<n => P(m)) => P(n)) => (n) P(n)
[Ho usato (n) come simbolo di quantificazione universale in accordo
con il Mendelson, poiche' si presta meglio ai caratteri standard]
4) Equivalenza con l'induzione semplice.
4.1) Se valgono le condizioni dell'induzione semplice allora P(0).
Siccome e' anche P(n) => P(n+1), allora abbiamo anche P(1) e quindi P
(2), e cosi' via fino a P(n-1) e, naturalmente, vale anche P(n).
Cosi' le condizioni dell'induzione semplice verificano anche quelle
dell'induzione forte.
4.2) Se valgono le condizioni dell'induzione forte allora P(0),
poiche' vale P per tutti i numeri minori di n. E' anche P(n-1), per lo
stesso motivo.
Ma pure P(n), poiche' nell'iduzione forte si dimostra che essendo P
(0), P(1), ..., P(n-1) si ottiene P(n).
Quindi abbiamo: P(n-1) => P(n).
Cosi' le condizioni dell'induzione forte verificano anche quelle
dell'induzione semplice.
C.V.D.
Siete d'accordo ?
.
Giovanni
RADICALE THE BEST
VERSIONE FINALE RIVEDUTA E CORRETTA ! :-)
> Iniziamo con un po' di semantica.
> 1) Il "Principio di induzione forte" e' chiamato anche:
> Principio di induzione completa o sul decorso dei valori.
> 2) L'espressione "forte" si riferisce al fatto che, mentre l'induzione
> semplice richiede (nel passo induttivo) solo che P(n-1) => P(n), in
> quella forte si richiede che tutti gli m < n siano P.
> In realta' i due principi sono equivalenti (v. (4))
Fin qui ho capito.
(omissis)
>Siete d'accordo ?
Non cio' capito niente. :-)
Pero' vorrei dire questo :
Per ogni n,
P(n) => P(n+1)
e' il passo induttivo debole
---------------------------------
Per ogni n, e per ogni m <= n
P(m) => P(n+1)
e' il passo induttivo forte
Dunque ...
Se il passo induttivo debole fosse
falso, per qualche n :
P(n) e' vera e P(n+1) falsa
Prendiamo uno di questi n.
Allora o P(m) e' vera per ogni m <= n
e quindi il passo induttivo forte e' falso, oppure per qualche m <= n,
P(m) e' falsa.
Quindi il passo induttivo forte o e' falso o e' vero solo perche' l'
antecedente e'
falso.
Quindi (NON debole) implica (non forte).
Indi per cui forte implica debole.
Poi :
Se il passo induttivo forte fosse falso, allora vi sarebbe un n per
cui per P(m) e' vera per ogni m <=n, ma P(n+1) e' falsa.
Ma se P(m) e' vera per ogni m <=n, allora e' vera pure per P(n) Dunque
P(n) => P(n+1) e' falsa.
Sunque non forte implica non debole,
per cui debole implica forte.
In finale :
forte => debole
debole => forte
CVD
RADICALE THE BEST
> Quindi il passo induttivo forte o e' falso o e' vero solo perche' l'
> antecedente e'
> falso.
... Pero' mi rendo conto che qui c'e' qualcosa che non va.
RADICALE THE BEST
> Iniziamo con un po' di semantica.
Sei vivo ?
LordBeotian
> 2) L'espressione "forte" si riferisce al fatto che, mentre l'induzione
> semplice richiede (nel passo induttivo) solo che P(n-1) => P(n),
Io direi che nel passo induttivo "si richiede" P(n-1) e "si dimostra" P
(n).
> in
> quella forte si richiede che tutti gli m < n siano P.
Qui "si richiede" P(k) per tutti i k<n e si dimostra P(n).
C'è un ovvio vantaggio nel poter usare come ipotesi P(k) per ogni k<n
anzichè solo P(n-1), e questo vantaggio si "paga" nella dimostrazione
che l'induzione semplice implica quella "forte" (che è non banale).
> 3) Enunciato formale:
> (n) ((m) (m<n => P(m)) => P(n)) => (n) P(n)
> [Ho usato (n) come simbolo di quantificazione universale in accordo
> con il Mendelson, poiche' si presta meglio ai caratteri standard]
Scriviamo pure quella classica
(P(0) e (n) (P(n) => P(n+1)) => (n) P(n)
> 4) Equivalenza con l'induzione semplice.
> 4.1)
Ovvero: assumiamo l'induzione forte e dimostriamo quella semplice.
NB: questa dimostrazione è "banale", richiede solo l'uso della logica
e nessun assioma aritmetico.
> Se valgono le condizioni dell'induzione semplice allora P(0).
Suppongo che intendi dire che sono vere le ipotesi dell'induzione
semplice, cioè
P(0) e (n) (P(n) => P(n+1))
deduci che ovviamente sono vere (separatamente) P(0) e (n)(P(n) => P(n
+1))
> Siccome e' anche P(n) => P(n+1),
O meglio (n)(P(n) => P(n+1))
> allora abbiamo anche P(1) e quindi P
> (2), e cosi' via fino a P(n-1) e, naturalmente, vale anche P(n).
Non mi sembra sensata questa cosa, tu non devi dimostrare che valgono P
(0),... P(n), tu devi dimostrare che (P(0) e... e P(n-1))=>P(n). E'
vero che per le proprietà dell'implicazione se dimostri che sono tutti
veri hai dimostrato anche l'implicazione però hai in realtà dimostrato
di più del necessario e infatti hai dovuto fare un ragionamento
induttivo (come si evince dal tuo "e così via") anzichè farne uno
puramente logico.
Io farei così:
P(0) e (n) (P(n) => P(n+1))
implica
(n) ((m) (m<n => P(m)) => P(n))
poichè:
1) se n=0 chiaramente
P(0)
implica
(m) (m<0 => P(m)) => P(0)
(per motivi di logica spicciola: m<0 è falso, quindi m<0=>P(m) è vero
per ogni m quindi "vero => vero" è vero)
2) se n>0 hai per ipotesi
P(n-1) => P(n)
che implica banalmente
((m) (m<n => P(m)) => P(n))
visto che n-1 sta tra gli m<n
> 4.2)
Ovvero: assumiamo l'induzione semplice e dimostriamo quella forte.
(Questa dimostrazione è per ovvi motivi più difficile della
precedente).
> Se valgono le condizioni dell'induzione forte
Cioè supponi vero
(n) ((m) (m<n => P(m)) => P(n))
>allora P(0),
> poiche' vale P per tutti i numeri minori di n.
Non mi sembra molto corretto: quello che hai come ipotesi è solo una
implicazione ("*se* P vale per tutti i numeri minori di k *allora* P
vale anche per k", non "P vale per tutti i numeri minori di k,
punto").
Io farei così:
da
(n) ((m) (m<n => P(m)) => P(n))
deduciamo
(m) (m<0 => P(m)) => P(0)
Dal fatto che la premessa è m<0 è falsa per ogni m l'implicazione (m<0
=> P(m)) è vera per ogni m e dunque la su conseguenza P(0) è vera.
> E' anche P(n-1), per lo
> stesso motivo.
Stessa cosa di prima. Quello che sai è solamente che *se* P è vera per
tutti gli m<n-1 *allora* è vera anche per n-1.
Dunque per arrivare a dimostrare che è vera per n-1 sfruttando le tue
ipotesi devi prima dimostrare che è vera per tutti gli m<n-1, e per
ora hai dimostrato solo che è vera per 0.
Temo che questo passaggio non sia dimostrabile solo a forza di logica
ma che richieda l'uso del principio di induzione classica (che ora
stai assumendo per ipotesi).
radicale 001
>Io direi che nel passo induttivo "si richiede" P(n-1) >e "si dimostra" P (n).
Eh si.
Ma la mia l' hai letta ?
Giovanni
Anche adesso non ho molto tempo.
Ti rispondo nel merito appena possibile.
Per ora ti ringrazio delle risposte.
Se mi legge, ovviamente ringrazio anche Lord, che poi rispondero'.
.
Ciao
Giovanni
radicale 001
> Scusa, ma non ho potuto risponderti prima.
> Anche adesso non ho molto tempo.
> Ti rispondo nel merito appena possibile.
> Per ora ti ringrazio delle risposte.
Sei veramente simpatico, affabile e gentile.
:-)
LordBeotian
wrote:
> Pero' vorrei dire questo :
>
> Per ogni n,
> P(n) => P(n+1)
> e' il passo induttivo debole
> ---------------------------------
> Per ogni n, e per ogni m <= n
> P(m) => P(n+1)
> e' il passo induttivo forte
>
> Dunque ...
> Se il passo induttivo debole fosse
> falso, per qualche n :
> P(n) e' vera e P(n+1) falsa
>
> Prendiamo uno di questi n.
Fin qui ok.
> Allora o P(m) e' vera per ogni m <= n
Perchè?
radicale 003
Allora
(A)
o P(m) e' vera per ogni m <= n
oppure
per qualche m <= n, P(m) e' falsa.
Semplicemente, non vi sono altre possibilita.
A or B e' una tautologia.
Giovanni
>
> VERSIONE FINALE RIVEDUTA E CORRETTA ! :-)
>
> > Iniziamo con un po' di semantica.
> > 1) Il "Principio di induzione forte" e' chiamato anche:
> > Principio di induzione completa o sul decorso dei valori.
> > 2) L'espressione "forte" si riferisce al fatto che, mentre l'induzione
> > semplice richiede (nel passo induttivo) solo che P(n-1) => P(n), in
> > quella forte si richiede che tutti gli m < n siano P.
> > In realta' i due principi sono equivalenti (v. (4))
>
> Fin qui ho capito.
> (omissis)
>
> >Siete d'accordo ?
>
> Non cio' capito niente. :-)
> Pero' vorrei dire questo :
>
> Per ogni n,
> P(n) => P(n+1)
> e' il passo induttivo debole
> ---------------------------------
> Per ogni n, e per ogni m <= n
> P(m) => P(n+1)
> e' il passo induttivo forte
Andrebbe precisato meglio nella formulazione, ma indicativamente.
.
>
> Dunque ...
> Se il passo induttivo debole fosse
> falso, per qualche n :
> P(n) e' vera e P(n+1) falsa
A rigore, e' falso o quando non P(0) oppure non vale, appunto il passo
induttivo.
.
> Prendiamo uno di questi n.
> Allora o P(m) e' vera per ogni m <= n
> e quindi il passo induttivo forte e' falso, oppure per qualche m <= n,
> P(m) e' falsa.
> Quindi il passo induttivo forte o e' falso o e' vero solo perche' l'
> antecedente e'
> falso.
.
Appunto, si avrebbe l'antecedente falso, ma cio' non falsifica
l'implicazione.
.
>
> Quindi (NON debole) implica (non forte).
> Indi per cui forte implica debole.
>
> Poi :
> Se il passo induttivo forte fosse falso, allora vi sarebbe un n per
> cui per P(m) e' vera per ogni m <=n, ma P(n+1) e' falsa.
.
La falsificazione dell'induzione forte, vedi la formula, comporta
l'esistenza di un n per cui P(n) e' falso mentre P(m) e' vero per
tutti gli m < n.
.
> Ma se P(m) e' vera per ogni m <=n, allora e' vera pure per P(n) Dunque
> P(n) => P(n+1) e' falsa.
>
> Sunque non forte implica non debole,
> per cui debole implica forte.
>
> In finale :
> forte => debole
> debole => forte
>
> CVD
Per il resto, vedo che hai capito bene il concetto di equivalenza,
doppia implicazione e contronominale.
.
Giovanni
LordBeotian
wrote:
> Per ogni n,
> P(n) => P(n+1)
> e' il passo induttivo debole
> ---------------------------------
> Per ogni n, e per ogni m <= n
> P(m) => P(n+1)
> e' il passo induttivo forte
>
> Dunque ...
> Se il passo induttivo debole fosse
> falso, per qualche n :
> P(n) e' vera e P(n+1) falsa
>
> Prendiamo uno di questi n.
> Allora o P(m) e' vera per ogni m <= n
> e quindi il passo induttivo forte e' falso,
ok
> oppure per qualche m <= n,
> P(m) e' falsa.
>
> Quindi il passo induttivo forte o e' falso o e' vero solo perche' l'
> antecedente e'
> falso.
Già, ma il fatto che sia o falso o vero (quale che sia il motivo) non
ci dice molto.
> Quindi (NON debole) implica (non forte).
Questo potevi dirlo se prima avevi dimostrato che il passo induttivo
debole era falso, ma tu hai dimostrato che è o vero o falso.
LordBeotian
> Ho scritto :
> Allora
> (A)
> o P(m) e' vera per ogni m <= n
> e quindi il passo induttivo forte e' falso,
> oppure
> (B)
> per qualche m <= n, P(m) e' falsa.
Ah ok, mi era sfuggito l' "o"...
radicale 003
> A rigore, e' falso o quando non P(0) oppure non vale, appunto il passo
> induttivo.
E no, scusa.
Il passo induttivo e' falso quando e' falsa la implicazione :
P(n) => P(n+1).
E questo accade se esiste un n per cui
P(n) e' VERA, e P(n+1) e' FALSA.
> Appunto, si avrebbe l'antecedente falso, ma cio' non falsifica
> l'implicazione.
Infatti il punto debole e' questo
E' pero' vero che se esistesse un n per cui l' antecedente della
implicazione forte fosse falso, allora per qualche m <= n sarebbe
P(m) falsa.
Preso questo m,
allora vi possono essere 2 casi :
P(j) e' vera per ogni j < m e allora l' implicazione forte e' FALSA.
E staremmo apposto.
Oppure ancora esiste un j per cui P(j) e' falsa.
Andando a ritroso dovrebbe essere possibile perfezionare la
dimostrazione.
Mi capisci ?
> La falsificazione dell'induzione forte, vedi la formula, comporta
> l'esistenza di un n per cui P(n) e' falso mentre P(m) e' vero per
> tutti gli m < n.
Ma e' esattamente quello che ho scritto. Perche' lo ripeti ?
radicale 004
> Ah ok, mi era sfuggito l' "o"...
Ma detto questo, la dimostrazione fa acqua,
perche' in effetti ho dimostrato che l' IF
e' falsa, oppure "degenerativamente" vera.
Ma sara' sufficiente ?
LordBeotian
Certo che no, la logica non fa distinzione tra "vero" e
"degenerativamente vero".
radicale 004
LordBeotian ha scritto:
E' giusto
Giovanni
>
> > 2) L'espressione "forte" si riferisce al fatto che, mentre l'induzione
> > semplice richiede (nel passo induttivo) solo che P(n-1) => P(n),
> Io direi che nel passo induttivo "si richiede" P(n-1) e "si dimostra" P
> (n).
P(n-1) => P(n)
si dimostra assumendo P(n-1) e derivando P(n)
.
> > in
> > quella forte si richiede che tutti gli m < n siano P.
>
> Qui "si richiede" P(k) per tutti i k<n e si dimostra P(n).
>
Certo, ho abbreviato volutamente la scrittura, non va' preso alla
lettera.
.
> C'è un ovvio vantaggio nel poter usare come ipotesi P(k) per ogni k<n
> anzichè solo P(n-1), e questo vantaggio si "paga" nella dimostrazione
> che l'induzione semplice implica quella "forte" (che è non banale).
>
> > 3) Enunciato formale:
> > (n) ((m) (m<n => P(m)) => P(n)) => (n) P(n)
> > [Ho usato (n) come simbolo di quantificazione universale in accordo
> > con il Mendelson, poiche' si presta meglio ai caratteri standard]
>
> Scriviamo pure quella classica
> (P(0) e (n) (P(n) => P(n+1)) => (n) P(n)
>
> > 4) Equivalenza con l'induzione semplice.
> > 4.1)
>
> Ovvero: assumiamo l'induzione forte e dimostriamo quella semplice.
> NB: questa dimostrazione è "banale", richiede solo l'uso della logica
> e nessun assioma aritmetico.
>
> > Se valgono le condizioni dell'induzione semplice allora P(0).
>
> Suppongo che intendi dire che sono vere le ipotesi dell'induzione
> semplice, cioè
> P(0) e (n) (P(n) => P(n+1))
> deduci che ovviamente sono vere (separatamente) P(0) e (n)(P(n) => P(n
> +1))
Si', e' chiamata "Eliminazione della congiunzione".
.
> > Siccome e' anche P(n) => P(n+1),
>
> O meglio (n)(P(n) => P(n+1))
E' uso nei testi di trascurare il quantificatore universale
sottintendendolo.
.
Mah, mi sembra che ricadiamo nel solito problema della *relazione
d'ordine*.
Nell'enunciato dell'induzione forte e' gia' incluso, ma in quella
semplice no.
> > 4.2)
>
> Ovvero: assumiamo l'induzione semplice e dimostriamo quella forte.
> (Questa dimostrazione è per ovvi motivi più difficile della
> precedente).
>
> > Se valgono le condizioni dell'induzione forte
>
> Cioè supponi vero
> (n) ((m) (m<n => P(m)) => P(n))
>
> >allora P(0),
> > poiche' vale P per tutti i numeri minori di n.
>
> Non mi sembra molto corretto: quello che hai come ipotesi è solo una
> implicazione ("*se* P vale per tutti i numeri minori di k *allora* P
> vale anche per k", non "P vale per tutti i numeri minori di k,
> punto").
> Io farei così:
> da
> (n) ((m) (m<n => P(m)) => P(n))
> deduciamo
> (m) (m<0 => P(m)) => P(0)
> Dal fatto che la premessa è m<0 è falsa per ogni m l'implicazione (m<0
> => P(m)) è vera per ogni m e dunque la su conseguenza P(0) è vera.
OK
> > E' anche P(n-1), per lo
> > stesso motivo.
>
> Stessa cosa di prima. Quello che sai è solamente che *se* P è vera per
> tutti gli m<n-1 *allora* è vera anche per n-1.
> Dunque per arrivare a dimostrare che è vera per n-1 sfruttando le tue
> ipotesi devi prima dimostrare che è vera per tutti gli m<n-1, e per
> ora hai dimostrato solo che è vera per 0.
> Temo che questo passaggio non sia dimostrabile solo a forza di logica
> ma che richieda l'uso del principio di induzione classica (che ora
> stai assumendo per ipotesi).
Mi sono lasciato un po' trascinare dalla stringata dimostrazione di
equivalenza di http://it.wikipedia.org/wiki/Principio_di_induzione e
ho saltato qualche passaggio :-)
e non ho controllato il dettaglio.
.
Giovanni