Principio di induzione e buon ordinamento
Ciao, sono qui per chiedervi un aiuto sul comprendere un passo fondamentale della dimostrazione:
principio del buon ordinamento <=> principio d'induzione
In particolare l'autore vuole dimostrare "-->" e procede per assurdo, prende un sottoinsieme T per cui l'affermazione A dipendente da n: A(n) sia falsa e vuole dimostrare che T è vuoto.
Procede per assurdo consideranto T non vuoto e sfrutta il buon ordinamento che garantisce un minimo per arrivare alla contraddizione.
I passaggi sono semplici tuttavia che c'azzecca l'affermazione: "Ogni sottoinsieme non vuoto dell'insieme dei numeri naturali ha un minimo"(1) col principio di induzione?
A me pare abbia dimostrato che, sì, quell'insieme è non vuoto e l'affermazone A(n) vale per tutti i naturali sfruttando il minimo, ma non mi pare di aver dimostrato che affermare "Ogni sottoinsieme non vuoto dell'insieme dei numeri naturali ha un minimo" sia come dire che A(n) vale per tutti i naturali.
Mi sfugge il passaggio logico temo
principio del buon ordinamento <=> principio d'induzione
In particolare l'autore vuole dimostrare "-->" e procede per assurdo, prende un sottoinsieme T per cui l'affermazione A dipendente da n: A(n) sia falsa e vuole dimostrare che T è vuoto.
Procede per assurdo consideranto T non vuoto e sfrutta il buon ordinamento che garantisce un minimo per arrivare alla contraddizione.
I passaggi sono semplici tuttavia che c'azzecca l'affermazione: "Ogni sottoinsieme non vuoto dell'insieme dei numeri naturali ha un minimo"(1) col principio di induzione?
A me pare abbia dimostrato che, sì, quell'insieme è non vuoto e l'affermazone A(n) vale per tutti i naturali sfruttando il minimo, ma non mi pare di aver dimostrato che affermare "Ogni sottoinsieme non vuoto dell'insieme dei numeri naturali ha un minimo" sia come dire che A(n) vale per tutti i naturali.
Mi sfugge il passaggio logico temo
Risposte
Ciao!
Ti è chiaro perché affermare che ogni sottoinsieme dei naturali \(\mathbb N\) ha elemento minimo, implica il principio di induzione[nota]A titolo informativo: nella costruzione di Peano il principio di induzione è assunto come assioma
[/nota]?
Se sì, che utilizzo possiamo farne, appurato che \(\mathbb{N}\) è un insieme ben ordinato? Considera il seguente
esempio:
Teorema: \[{\sum_{i=1}^{n}i} = \frac{n(n+1)}{2}\]
dimostrazione: per \(n=1\) il claim regge (a.k.a. \(1\in\left\{n:\sum_{i=1}^{n}=n(n+1)/2\right\}\)). Sia per $n=r\in\mathbb{N}$ assunta l'ipotesi del teorema; banalmente, vedi subito che tutto ciò vale anche per \(S(n)\), dove con \(S(n)=n^{+}\) intendo ovviamente il successivo di \(n\) (che è \(n+1\)), a.k.a. se \(n \in \left\{n:\sum_{i=1}^{n}=n(n+1)/2\right\}\) pure \(S(n)=n^{+}=n+1\) vi è al suo interno. Questo, per il principio di induzione matematica, significa \(\left\{n:\sum_{i=1}^{n}=n(n+1)/2\right\} = \mathbb{N}\).
Cosa ha ha ce fare in tutto ciò il WEP? Se in un \(\mathbb{N}\) alieno il principio del buon ordinamento non valesse, l'ultima uguaglianza di cui sopra non sarebbe più valida.
"smirne":
non mi pare di aver dimostrato che affermare "Ogni sottoinsieme non vuoto dell'insieme dei numeri naturali ha un minimo" sia come dire che A(n) vale per tutti i naturali.
Ti è chiaro perché affermare che ogni sottoinsieme dei naturali \(\mathbb N\) ha elemento minimo, implica il principio di induzione[nota]A titolo informativo: nella costruzione di Peano il principio di induzione è assunto come assioma
[/nota]?Se sì, che utilizzo possiamo farne, appurato che \(\mathbb{N}\) è un insieme ben ordinato? Considera il seguente
esempio:
Teorema: \[{\sum_{i=1}^{n}i} = \frac{n(n+1)}{2}\]
dimostrazione: per \(n=1\) il claim regge (a.k.a. \(1\in\left\{n:\sum_{i=1}^{n}=n(n+1)/2\right\}\)). Sia per $n=r\in\mathbb{N}$ assunta l'ipotesi del teorema; banalmente, vedi subito che tutto ciò vale anche per \(S(n)\), dove con \(S(n)=n^{+}\) intendo ovviamente il successivo di \(n\) (che è \(n+1\)), a.k.a. se \(n \in \left\{n:\sum_{i=1}^{n}=n(n+1)/2\right\}\) pure \(S(n)=n^{+}=n+1\) vi è al suo interno. Questo, per il principio di induzione matematica, significa \(\left\{n:\sum_{i=1}^{n}=n(n+1)/2\right\} = \mathbb{N}\).
Cosa ha ha ce fare in tutto ciò il WEP? Se in un \(\mathbb{N}\) alieno il principio del buon ordinamento non valesse, l'ultima uguaglianza di cui sopra non sarebbe più valida.
Un modo alternativo (molto alternativo 
) di vedere la cosa …
Il principio di induzione, per funzionare, presuppone che esista una "lista ordinata" ed un "primo" della lista: cosa c'è di meglio dei numeri naturali e del principio del buon ordinamento?
Hai una lista ordinata e hai un "primo" della lista (il minimo garantito dal buon ordinamento)
Cordialmente, ALex
) di vedere la cosa …Il principio di induzione, per funzionare, presuppone che esista una "lista ordinata" ed un "primo" della lista: cosa c'è di meglio dei numeri naturali e del principio del buon ordinamento?
Hai una lista ordinata e hai un "primo" della lista (il minimo garantito dal buon ordinamento)
Cordialmente, ALex
Ciao e vi ringrazio per le risposte.
Mi pare di aver capito il legame. Il principio del buon ordinamento mi garantisce un primo termine che sfrutto come base per il principio di induzione. Questa è l'interpretazione intuitiva.
In sostanza la dimostrazione in apertura sfrutta il principio di buon ordinamento per dimostrare che la proprietà A(n) vale per tutti i naturali. Insomma che il principio del buon ordinamento è sufficiente (-->) per il principio di induzione.
Il fatto è che la dimostrazione e l'inutitività mi paiono viaggiare su due binari differenti.
Nel senso che nella dimostrazione sfrutto il principio del b ordinamento per ottenere il risultato sperato (cioè che l'insiemeT è vuoto, ma non sto cercando nessun termine di "partenza"). Mentre intuitivamente il principio del b. ordinamento è utile perché mi garantisce un primo termine. Non riesco conciliare la visione delle cose.
Non so se mi sono spiegato
Mi pare di aver capito il legame. Il principio del buon ordinamento mi garantisce un primo termine che sfrutto come base per il principio di induzione. Questa è l'interpretazione intuitiva.
In sostanza la dimostrazione in apertura sfrutta il principio di buon ordinamento per dimostrare che la proprietà A(n) vale per tutti i naturali. Insomma che il principio del buon ordinamento è sufficiente (-->) per il principio di induzione.
Il fatto è che la dimostrazione e l'inutitività mi paiono viaggiare su due binari differenti.
Nel senso che nella dimostrazione sfrutto il principio del b ordinamento per ottenere il risultato sperato (cioè che l'insiemeT è vuoto, ma non sto cercando nessun termine di "partenza"). Mentre intuitivamente il principio del b. ordinamento è utile perché mi garantisce un primo termine. Non riesco conciliare la visione delle cose.
Non so se mi sono spiegato
"smirne":
la dimostrazione in apertura sfrutta il principio di buon ordinamento per dimostrare che la proprietà A(n) vale per tutti i naturali.
Dimentica di proprietà A(n) e amici: semplicemente, il principio di buon ordinamento afferma che, in \(\mathbb{N}\) (insieme che è notoriamente totalmente ordinato), ogni sottoinsieme ha elemento minimo. Quello che ricaviamo da lui, è il seguente Principio di induzione matematica, il quale dice che se un sottoinsieme \(S\subset\mathbb{N}\) soddisfa le proprietà
1) L'elemento \(1\in\mathbb{N}\) appartiene a \(S\)
2) Se un \(n\in\mathbb{N}\) implica che anche \(S(n)=n^{+}=n+1\) appartenga a \(S\)
[/list:u:7csk387l]
Allora è \(S=\mathbb{N}\). Da qui ci riallacciamo alla dimostrazione precedente.
"smirne":
Il principio del buon ordinamento mi garantisce un primo termine che sfrutto come base per il principio di induzione.
La situazione intuitiva del post di @axpgn generalizza in realtà il PMI: se un elemento \(\mu\) appartiene all'insieme degli elementi che soddisfano "la proprietà" (è qui che i predicati entrano in gioco, evidentemente) e vale 2), tutti i suoi naturali successivi appartengono a quell'insieme (se hai mai giocato con i pezzetti del domino, un volta allineati, puoi far iniziare da caduta spingendo il primo, ma nessuno ti vieta di iniziare da "più avanti" c:).
"marco2132k":
Quello che ricaviamo da lui, è il seguente Principio di induzione matematica, il quale dice che se un sottoinsieme \(S\in\mathbb{N}\) soddisfa le proprietà
1) L'elemento \(1\in\mathbb{N}\) appartiene a \(S\)
2) Se un \(n\in\mathbb{N}\) implica che anche \(S(n)=n^{+}=n+1\) appartenga a \(S\)
Il problema che questo passaggio non c'è nella dimostrazione.E' una intuizione esterna ad essa. Voglio dire, io in quella dimostrazione dimostro solo che il principio di buon ordinamento mi garantisce il T (insieme sopra definito) non vuoto.
Ma tutta questa deduzione che ho quotato non c'è. E' questo che mi disorientava
In altre parole: non ho dimostrato quanto in quote.
Ancora ti ringrazio.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo