Principio di induzione
Buonasera a tutti, vorrei accertarmi di aver capito bene la dimostrazione del principio di induzione. A questo scopo, vi scrivo quelle che ho capito io essere le ipotesi e la tesi del teorema:
IPOTESI:
1)$P_1$ vera
2) $P_n => P_(n+1)$ vera
3)$P_(n+1)$ vera
TESI: $P_n$ vera.
Sono giuste?
La cosa non banalissima di questo teorema è che, se usassi solo le ipotesi 2) e 3), non necessariamente seguirebbe che $P_n$ sia vera, per questo è fondamentale che anche $P_1$ sia vera (almeno mi sembra di aver capito questo dalla dimostrazione del teorema svolta a lezione).
IPOTESI:
1)$P_1$ vera
2) $P_n => P_(n+1)$ vera
3)$P_(n+1)$ vera
TESI: $P_n$ vera.
Sono giuste?
La cosa non banalissima di questo teorema è che, se usassi solo le ipotesi 2) e 3), non necessariamente seguirebbe che $P_n$ sia vera, per questo è fondamentale che anche $P_1$ sia vera (almeno mi sembra di aver capito questo dalla dimostrazione del teorema svolta a lezione).
Risposte
Bisognerebbe però aggiungere alla 3) 'vera per ogni $n\in mathbb{N}$'.
Per la 1), $P_1$ vera, certo che è fondamentale, perché da qualche parte, da qualche proposizione vera, bisogna pur cominciare.
La 2), non ti dice che $P_n$ e $P_{n+1}$ sono vere, ma che l'implicazione è vera, cioè che dal supporre $P_n$ vera segue che $P_{n+1}$ è vera.
Per la 1), $P_1$ vera, certo che è fondamentale, perché da qualche parte, da qualche proposizione vera, bisogna pur cominciare.
La 2), non ti dice che $P_n$ e $P_{n+1}$ sono vere, ma che l'implicazione è vera, cioè che dal supporre $P_n$ vera segue che $P_{n+1}$ è vera.
"gabriella127":giusto, in questo caso $n$ è generico e non fissato (anche questa distinzione è importante perché una famiglia di proposizioni $P_n$ e la specifica $P_n$ si indicano allo stesso modo).
Bisognerebbe però aggiungere alla 3) 'vera per ogni $n\in mathbb{N}$'.
EDIT: ora che ci penso non credo che bisogna aggiungere "per ogni $n$": nel passo induttivo suppongo vera $P_n$ (quindi una proposizione, non una famiglia di proposizioni) e cerco di dimostrare che anche $P_(n+1)$ è vera. Nella tesi del teorema ci andrebbe il "per ogni n", almeno credo.
"gabriella127":
Per la 1), $P_1$ vera, certo che è fondamentale, perché da qualche parte, da qualche proposizione vera, bisogna pur cominciare.
Esatto, soprattutto perché nella dimostrazione svolta a lezione definisco un insieme $A = {n in NN$ tale che $P_n$ è vera$} sube NN$. Per l'ipotesi 1 ho che $1 in A$, poi dico che se $n in A$ (e questa cosa la posso dire solo perché so che almeno $1$ sta in $A$, e quindi male che vada $n=1$, allora $(n+1) in A$ per l'ipotesi 2)
"gabriella127":
La 2), non ti dice che $P_n$ e $P_{n+1}$ sono vere, ma che l'implicazione è vera, cioè che dal supporre $P_n$ vera segue che $P_{n+1}$ è vera.
Sì infatti ho voluto elencare le ipotesi proprio per avere il teorema nella forma più chiara possibile. Se usassi solo le ipotesi 2) e 3) $P_n$ potrebbe essere anche falsa proprio per come è fatta la tavola di verità dell'implicazione.
"HowardRoark":
Buonasera a tutti, vorrei accertarmi di aver capito bene la dimostrazione del principio di induzione.
No, NON DIMOSTRI il principio di induzione. Semplicemente lo APPLICHI.
Sperabilmente correttamente.
"HowardRoark":
IPOTESI:
1)$P_1$ vera
2) $P_n => P_(n+1)$ vera
3)$P_(n+1)$ vera
TESI: $P_n$ vera.
Sono giuste?
NO, così non lo applichi correttamente, proprio no.
Non farti intimidire dalle notazioni. Pensa a una situazione reale. Vuoi attraversare un torrente (senza finire a mollo). Ci sono delle pietre e puoi pensare di farla franca saltellando da una pietra all'altra.
Per la precisione, ci sono 12 pietre, messe abbastanza in ordine, tanto da suggerire un percorso che ti porti dall'altra parte. Oltretutto la 12ma pietra è già sulla riva opposta!
Cosa ti serve per riuscire ad andare davvero da una parte all'altra?
2 cose.
La prima è la "BASE": devi riuscire a piazzarti sulla prima pietra. Ci riesci? Sì? Bene
La seconda è il "PASSO INDUTTIVO". Riesci a passare dalla prima alla seconda pietra? E dalla seconda alla terza? E avanti così, annoiandoci un po'. In ultimo, riesci a passare dall'undicesima pietra alla dodicesima? Se la risposta a tutte queste domande (sono 11) è SI', allora ce l'hai fatta: ti trovi sulla riva opposta ancora bello asciutto!
COMMENTO: nel passo induttivo è essenziale che tu riesca a passare da n ad n+1 per tutti gli n. Se te ne manca uno (per esempio dalla pietra 8 non riesci ad arrivare alla pietra 9), non arrivi dall'altra parte!
Penso (spero) che questo esempietto sia chiaro, anzi magari ti sei annoiato.
E allora pensiamo in grande.
Voglio sapere se una proprietà vale per tutti gli $n \in NN$ (vedi nota *), e voglio farlo usando il principio di induzione. Usando le tue notazioni, voglio provare che $P_n$ è vera per ogni $n \in NN$.
Allora, devo dimostrare che sono vere due cose:
"BASE": $P_1$ è vera. (Nell'esempio, devo essere sicuro di riuscire a piazzarmi sulla prima pietra)
"PASSO INDUTTIVO": per ogni $n \in NN$, è vera l'implicazione $P_n => P_(n+1)$. Ovvero, assumendo che $P_n$ sia vera, devo riuscire a dimostrare che $P_(n+1)$ è vera. E questo devo riuscire a farlo per ogni $n \in NN$. (Nell'esempio, devo essere sicuro che riesco a passare da una pietra a quella successiva, SEMPRE).
Sono riuscito a dimostrare queste due cose? Sì? Bene. Perché il principio di induzione mi garantisce che la proprietà "P" sia vera per ogni $n \in NN$.
Ripeto, non stiamo dimostrando il principio di induzione! Stiamo semplicemente applicando il principio di induzione. Che è vero per atto di fede (anche per chi sia pastafariano).
*Precisazione, importante per capirci bene: $NN = \{ 1,2,3,...\}$
non stiamo dimostrando il principio di induzione! Stiamo semplicemente applicando il principio di induzione. Che è vero per atto di fede (anche per chi sia pastafariano).che sciocchezza! Certo che il principio di induzione si dimostra...
Il principio di induzione corrisponde al seguente teorema:
L'insieme dei numeri naturali gode della seguente proprietà: se \(S\subseteq\mathbb N\) è un sottoinsieme non vuoto, e chiuso rispetto alla funzione successore, allora \(S=\mathbb N\).
Ne ho scritto diffusamente qui.
L'insieme dei numeri naturali gode della seguente proprietà: se \(S\subseteq\mathbb N\) è un sottoinsieme non vuoto, e chiuso rispetto alla funzione successore, allora \(S=\mathbb N\).
Ne ho scritto diffusamente qui.
Il principio di induzione è equivalente al principio del buon ordinamento dei numeri naturali. Se il principio di induzione si dimostri oppure no dipende da cosa uno prende come assiomi di base. Per esempio qui c'è scritto
"Wikipedia":
In Peano arithmetic, second-order arithmetic and related systems, and indeed in most (not necessarily formal) mathematical treatments of the well-ordering principle, the principle is derived from the principle of mathematical induction, which is itself taken as basic.
Ribadisco che a lezione il teorema lo abbiamo dimostrato, e le ipotesi mi sembrano proprio quelle che ho scritto in precedenza. Comunque, se pensate che le mie ipotesi siano sbagliate, vi sarei grato se mi faceste capire dov'è l'inghippo, perché per me non capire quali siano le ipotesi e la tesi di un teorema equivale a non aver capito nulla.
Scrivo la dimostrazione data a lezione:
PRINCIPIO DI INDUZIONE: sia $P_n$ una famiglia di proposizioni. IPOTESI: 1) $P_1$ è vera 2) se $P_n$ (fissata) vera allora $P_(n+1)$ (fissata) è vera
TESI: $P_n$ (generica) è vera per ogni $n in NN$.
DIM
Definisco $A= {n in NN : P_n$ è vera$} sube NN$.
Le proprietà 1) e 2) implicano che $A$ è induttivo: l'ipotesi 1) mi dice che $1 in A$; l'ipotesi 2) mi dice che se $n in A$, allora $(n+1) in A$.
Siccome abbiamo in precedenza definito $NN$ come intersezione di tutti i possibili insiemi induttivi e abbiamo fatto vedere che $NN$ è induttivo, $A sube NN => A = NN$, e quindi $P_n$ è vera per ogni $n in NN$, che è la tesi che volevo dimostrare.
Scrivo la dimostrazione data a lezione:
PRINCIPIO DI INDUZIONE: sia $P_n$ una famiglia di proposizioni. IPOTESI: 1) $P_1$ è vera 2) se $P_n$ (fissata) vera allora $P_(n+1)$ (fissata) è vera
TESI: $P_n$ (generica) è vera per ogni $n in NN$.
DIM
Definisco $A= {n in NN : P_n$ è vera$} sube NN$.
Le proprietà 1) e 2) implicano che $A$ è induttivo: l'ipotesi 1) mi dice che $1 in A$; l'ipotesi 2) mi dice che se $n in A$, allora $(n+1) in A$.
Siccome abbiamo in precedenza definito $NN$ come intersezione di tutti i possibili insiemi induttivi e abbiamo fatto vedere che $NN$ è induttivo, $A sube NN => A = NN$, e quindi $P_n$ è vera per ogni $n in NN$, che è la tesi che volevo dimostrare.
Ma perché pensi che le ipotesi e la tesi debbano essere sbagliate? Non te le hanno date a lezione? Quelle sono.
A parte che hai aggiunto quel fissata ad abundantiam, forse per qualche dubbio che ti era sorto, ma così sembra che lo dimostri per un solo $n$ fissato, in realtà nella 2) si intende che deve essere vera per $n$ qualsiasi.
E pure quel 'generica' alla fine non serve a niente.
Per quanto riguarda il dimostrare o meno il principio di induzione, oltre a dipendere da quanto dice Martino, evidentemente a te non hanno dato la definizione assiomatica dei naturali (Peano) ma la definizione come 'il più piccolo degli insiemi induttivi di $\mathbb{R}$'.
Questo perché penso (credo tu stia facendo un corso di analisi 1 a matematica, come dicevi) che avete costruito gli insiemi numerici non partendo dai naturali, ma dai reali tramite la costruzione assiomatica.
In questa costruzione vengono prima i reali, si definiscono dopo i naturali come sottoinsieme dei reali, il più piccolo insieme induttivo etc.
Quindi il percorso, con la costruzione assiomatica di $\mathbb{R}$, è invertito rispetto a quando si danno gli assiomi di Peano, tra cui può starci il principio di induzione: prima $\mathbb{R}$ e poi $\mathbb{N}$
E, se si usa la costruzione assiomatica di $\mathbb{R}$, il principio di induzione si dimostra, visto che non abbiamo dato nessun assioma dei naturali.
O meglio: una volta definito l'insieme dei naturali come sottoinsieme di $\mathbb{R}$ poi si dimostra che $\mathbb{N}$ verifica gli assiomi di Peano, principio di induzione incluso.
(Spero di essere stata chiara nonostante l'assalto di zanzare che ho stamattina, feroci con le zanne).
A parte che hai aggiunto quel fissata ad abundantiam, forse per qualche dubbio che ti era sorto, ma così sembra che lo dimostri per un solo $n$ fissato, in realtà nella 2) si intende che deve essere vera per $n$ qualsiasi.
E pure quel 'generica' alla fine non serve a niente.
Per quanto riguarda il dimostrare o meno il principio di induzione, oltre a dipendere da quanto dice Martino, evidentemente a te non hanno dato la definizione assiomatica dei naturali (Peano) ma la definizione come 'il più piccolo degli insiemi induttivi di $\mathbb{R}$'.
Questo perché penso (credo tu stia facendo un corso di analisi 1 a matematica, come dicevi) che avete costruito gli insiemi numerici non partendo dai naturali, ma dai reali tramite la costruzione assiomatica.
In questa costruzione vengono prima i reali, si definiscono dopo i naturali come sottoinsieme dei reali, il più piccolo insieme induttivo etc.
Quindi il percorso, con la costruzione assiomatica di $\mathbb{R}$, è invertito rispetto a quando si danno gli assiomi di Peano, tra cui può starci il principio di induzione: prima $\mathbb{R}$ e poi $\mathbb{N}$
E, se si usa la costruzione assiomatica di $\mathbb{R}$, il principio di induzione si dimostra, visto che non abbiamo dato nessun assioma dei naturali.
O meglio: una volta definito l'insieme dei naturali come sottoinsieme di $\mathbb{R}$ poi si dimostra che $\mathbb{N}$ verifica gli assiomi di Peano, principio di induzione incluso.
(Spero di essere stata chiara nonostante l'assalto di zanzare che ho stamattina, feroci con le zanne).
"megas_archon":non stiamo dimostrando il principio di induzione! Stiamo semplicemente applicando il principio di induzione. Che è vero per atto di fede (anche per chi sia pastafariano).che sciocchezza! Certo che il principio di induzione si dimostra...
oh, ma dai, ma sai che rischiavo di morire senza saperlo!
PS: se vuoi ti regalo un pizzico di ironia con la quale puoi condire la pasta
"gabriella127":
A parte che hai aggiunto quel fissata ad abundantiam, forse per qualche dubbio che ti era sorto, ma così sembra che lo dimostri per un solo $n$ fissato, in realtà nella 2) si intende che deve essere vera per $n$ qualsiasi.
E pure quel 'generica' alla fine non serve a niente.
Il dubbio che ho sta proprio in questo: da quello che ho capito, la $P_n$ della seconda ipotesi non è la stessa $P_n$ che compare nella tesi. Anche perché se così non fosse non avrebbe senso il teorema, cioè dire che $P_n$ è vera per ogni $n$ è la tesi che voglio dimostrare, non posso metterla per ipotesi. Anche perché quando dimostro una famiglia di proposizioni col principio di induzione, dopo aver verificato il passo base, prendo una fissata $P_n$ vera e cerco di far vedere, usando l'ipotesi induttiva, che è vera anche $P_(n+1)$.
Per quanto riguarda il resto, direi che hai perfettamente capito il programma che stiamo seguendo.
"HowardRoark":
[quote="gabriella127"]
A parte che hai aggiunto quel fissata ad abundantiam, forse per qualche dubbio che ti era sorto, ma così sembra che lo dimostri per un solo $n$ fissato, in realtà nella 2) si intende che deve essere vera per $n$ qualsiasi.
E pure quel 'generica' alla fine non serve a niente.
Il dubbio che ho sta proprio in questo: da quello che ho capito, la $P_n$ della seconda ipotesi non è la stessa $P_n$ che compare nella tesi. Anche perché se così non fosse non avrebbe senso il teorema, cioè dire che $P_n$ è vera per ogni $n$ è la tesi che voglio dimostrare, non posso metterla per ipotesi.[/quote]
Attention! Ne faison pas confusion! (Francese di Totò
)Tu nel passo 2), il passo induttivo, non stai dicendo che $P_n$ è vera, stai dicendo che è vera l'implicazione, lo avevi detto anche tu prima no?
Cioè: se, ove mai, se capita che, $P_n$ è vera allora è vera anche $P_{n+1}$.
Cioè stai dicendo: se una proposizione è vera per un $n$ è vera pure per la seguente: ogni volta che una cosa è verde, è verde pure quella dopo.
Ma non stai dando per scontato che la cosa è verde.
Perciò serve il Passo 1), l'ipotesi di una cosa $1$ iniziale verde, è l'unica cosa che sai che per ipotesi è verde: $1$ è verde, vero, quindi (per passo 2)) $2$ che segue è verde, e quindi $3$ che segue è verde, e quindi $4$ che segue è verde, e così via è verde tutto ciò che segue all'infinito.
"gabriella127":
Tu nel passo 2), il passo induttivo, non stai dicendo che $P_n$ è vera, stai dicendo che è vera l'implicazione, lo avevi detto anche tu prima no?
Cioè: se, ove mai, se capita che, $P_n$ è vera allora è vera anche $P_{n+1}$.
Però anche nella dimostrazione che ho riportato del principio di induzione prendo un $n$ per cui una fissata $P_n$ è vera, e quindi nelle ipotesi c'è che una singola $P_n$ sia vera . Prima infatti credo mi stessi confondendo proprio perché $P_n$ compare con due significati diversi nell'enunciato, o almeno così sembra a me.
"gabriella127":
Cioè stai dicendo: se una proposizione è vera per un $n$ è vera pure per la seguente: ogni volta che una cosa è verde, è verde pure quella dopo.
Ma non stai dando per scontato che la cosa è verde.
Non si tratta di dare per scontato che una singola $P_n$ sia vera, ma di avere la possibilità di supporlo perché almeno il passo base lo avrei già verificato, e quindi per $n=1$ $P_n$ è senza dubbio vera.
Però da quello che capisco per te non ha senso distinguere tra $P_n$ fissata e $P_n$ generica[nota]per $P_n$ generica io intendo tutta la famiglia di proposizioni, per ogni $n$, io la chiamo "generica" ma forse non era chiaro cosa intendessi[/nota], quindi immagino che quel $P_n$ abbia lo stesso significato per tutto l'enunciato.
Non sono sicura di riuscire a seguirti, forse in particolare non capisco che intendi quando parli di 'fissata' e 'generica'. Ho l'impressione che stai complicando le cose, lascia stare quei 'fissata' e 'generica'.
Anche questo non lo capisco tanto, neanche quel 'fissata'.
Nella dimostrazione si assume $P_1$ vera, la singola $P_n$ vera è la $P_1$ per ipotesi. Le altre boh, da dimostrare.
Definisci l'insieme $A$, che all'inizio sai solo che ha dentro $P_1$ per ipotesi.
Poi usando l'ipotesi induttiva $2)$ si afferma che $A$ è induttivo.
Poiché $A$ è incluso in $mathbb{N}$ e $mathbb{N}$ è il più piccolo insieme induttivo, ne consegue che $A$ è tutto $mathbb{N}$ (non può essere più piccolo.)
Stop.
Comunque rileggo domani, ora s'è fatto tardi...
"HowardRoark":
Però anche nella dimostrazione che ho riportato del principio di induzione prendo un $ n $ per cui una fissata $ P_n $ è vera, e quindi nelle ipotesi c'è che una singola $ P_n $ sia vera .
Anche questo non lo capisco tanto, neanche quel 'fissata'.
Nella dimostrazione si assume $P_1$ vera, la singola $P_n$ vera è la $P_1$ per ipotesi. Le altre boh, da dimostrare.
Definisci l'insieme $A$, che all'inizio sai solo che ha dentro $P_1$ per ipotesi.
Poi usando l'ipotesi induttiva $2)$ si afferma che $A$ è induttivo.
Poiché $A$ è incluso in $mathbb{N}$ e $mathbb{N}$ è il più piccolo insieme induttivo, ne consegue che $A$ è tutto $mathbb{N}$ (non può essere più piccolo.)
Stop.
Comunque rileggo domani, ora s'è fatto tardi...
"gabriella127":
Nella dimostrazione si assume $ P_1 $ vera, la singola $ P_n $ vera è la $ P_1 $ per ipotesi. Le altre boh, da dimostrare.
Io a un certo punto prendo $n in A$, da quello che ho capito questa cosa non la potrei fare se non avessi verificato che almeno $1 in A$. [nota]Questo corrisponde ad assumere una singola $P_n$ vera in una dimostrazione per induzione, poi, usando questa cosa, se si riesce a dimostrare che anche $P_(n+1)$ è vera si è conclusa la dimostrazione[/nota] Poi per ipotesi del "teorema di induzione" ho che se $P_n$ è vera allora $P_(n+1)$ è vera, e quindi anche $n+1 in A$. Allora $A$ e induttivo e teorema dimostrato.
Quello che vorrei dire è che se la singola $P_n$ che prendo fosse falsa, $P_(n+1)$ può essere sia vera che falsa (per come è fatta la tavola di verità dell'implicazione, questa sarebbe vera sia che $P_n$ è falsa e $P_(n+1)$ è vera, sia che $P_n$ è vera e $P_(n+1)$ è vera, sia che $P_n$ è falsa e $P_(n+1)$ è falsa, quindi mettere solo quest'implicazione nelle ipotesi del principio di induzione non è sufficiente, per questo si assume che $n in A$), quindi non sarebbe tanto utile non assumere per ipotesi che almeno la singola $P_n$ sia vera. Secondo me comunque stiamo dicendo un po' la stessa cosa con parole diverse, però spero di aver chiarito bene come ho afferrato io questa cosa
"Fioravante Patrone":
[quote="megas_archon"]non stiamo dimostrando il principio di induzione! Stiamo semplicemente applicando il principio di induzione. Che è vero per atto di fede (anche per chi sia pastafariano).che sciocchezza! Certo che il principio di induzione si dimostra...
oh, ma dai, ma sai che rischiavo di morire senza saperlo!
PS: se vuoi ti regalo un pizzico di ironia con la quale puoi condire la pasta[/quote] E' un ottimo modo di difendersi dopo aver scritto una minchiata, ma
@HowardRoark: Puoi provare a leggere come si fa una dimostrazione usando il Principio d'Induzione qui.
Per quanto riguarda il resto, quello che enunci non è il vero e proprio Principio d'Induzione, ma una sua declinazione più immediatamente applicabile negli esercizi.
Per quanto riguarda il resto, quello che enunci non è il vero e proprio Principio d'Induzione, ma una sua declinazione più immediatamente applicabile negli esercizi.
"gugo82":
Per quanto riguarda il resto, quello che enunci non è il vero e proprio Principio d'Induzione, ma una sua declinazione più immediatamente applicabile negli esercizi.
Mi sembra già qualcosa!
Comunque grazie mille per il file.
"HowardRoark":
[quote="gugo82"]
Per quanto riguarda il resto, quello che enunci non è il vero e proprio Principio d'Induzione, ma una sua declinazione più immediatamente applicabile negli esercizi.
Mi sembra già qualcosa!
Comunque grazie mille per il file.[/quote]
Inoltre, ne avevo scritto tanto tempo prima qui e qui sul forum.
Anni dopo, ho anche scritto come si può fare a trovare una formula da dimostrare per induzione (vedi qui).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo