Provare che ${0,1,2,3,ldots,n}$ è finito.
Come da titolo, è possibile provare che ${0,1,2,3,ldots,n}$ è finito?
Io avevo pensato di provarlo per induzione: per $k=0$ si ha ${0}$ e più finito di così si muore.
Per $k=1$ si ha ${0,1}$ e ho provato che ${0,1}cap NN=emptyset$.
Poi supposto vero che ${0,1,2,3,ldots,n}$ sia finito, per ${0,1,2,3,ldots,n,n+1}$ si ha che questo insieme è uguale all'unione ${0,1,2,3,ldots,n}cup{n+1}$ che è finita essendo finiti gli insiemi da unire.
Commenti, proposte di ban, ammonizioni, ho cercato di provare una cosa non possibile da provare, ho cercato di provare una cosa accettata assiomaticamente... ???
Io avevo pensato di provarlo per induzione: per $k=0$ si ha ${0}$ e più finito di così si muore.
Per $k=1$ si ha ${0,1}$ e ho provato che ${0,1}cap NN=emptyset$.
Poi supposto vero che ${0,1,2,3,ldots,n}$ sia finito, per ${0,1,2,3,ldots,n,n+1}$ si ha che questo insieme è uguale all'unione ${0,1,2,3,ldots,n}cup{n+1}$ che è finita essendo finiti gli insiemi da unire.
Commenti, proposte di ban, ammonizioni, ho cercato di provare una cosa non possibile da provare, ho cercato di provare una cosa accettata assiomaticamente... ???
Risposte
io ne so decisamente poco, però ho delle dispense di teoria degli insiemi e nel primo capitolo dice: "un insieme si dice finito se è equipotente con l'insieme ${1,...,n}$ per qualche $n in NN$ oppure se è vuoto. Quindi ${1,...,n}$ è finito per definizione. Questo è quanto sostenuto dalle dispense di più non so dirti! ciao
Direi che rubik ha perfettamente ragione.
Nei corsi (di base) di Algebra che ho seguito io, abbiamo sempre usato la parola finito come sinonimo di non infinito. Poi non so quanto si complichino le cose andando nei dettagli...
Nei corsi (di base) di Algebra che ho seguito io, abbiamo sempre usato la parola finito come sinonimo di non infinito. Poi non so quanto si complichino le cose andando nei dettagli...
La definizione che conosco io di insieme finito è la seguente: "un insieme si dice finito se non è equipotente ad alcun suo sottoinsieme proprio". A questo punto la dimostrazione del fatto che ${1,...,n}$ è finito è o astrusa e basata sui mille assiomi di ZF oppure logico-intuitiva del tipo "è così e basta" (un po' farcito con qualche considerazione ausiliaria). Ma potrei sbagliare, e lascio la parola a chi ne sa più di me.
Ben, Martino, le mie piccole conoscenze coincidono con le tue.
Per quelle che sono le mie conoscenze, un insieme di dice infinito se esiste un'applicazione biiettiva dell'insieme su una sua parte propria. Si dice finito se non è infinito. Quindi la definizione di finito e infinito gioca sulle applicazioni di un insieme su una sua parte propria.
Poi so che un insieme $I$ si dice possedere $k$ elementi se e solo se è equipotente all'insieme ${1,2,3,ldots,k}$ per qualche $k in NN$ (*), quindi se $I$ possiede $k$ elementi è finito e, viceversa, se è finito allora possiede $k$ elementi.
Tutto questo è bellismo se non fosse per il fatto che si usa implicitamente il fatto che ${1,2,3,ldots,k}$ è finito: infatti se $I$ è equipotente a ${1,2,3,ldots,k}$ allora ha $k$ elementi, dove questo modo di dire è giustificato dalla definizione di equipotenza, ma questo presuppone la nozione che ${1,2,3,ldots,k}$ abbia $k$ elementi, cioè un numero finito di elementi, ed infatti poi è possibile dire che $I$ è finito se e solo se possiede $k$ elementi.
A questo punto sorge in me una domanda spontanea: chi ci dice che ${1,2,3,ldots,k}$ è finito?
Uno potrebbe essere tentato di rispondere che questo ci è detto dal fatto che i naturali di ${1,2,3,ldots,k}$ sono $1,2,3,ldots,k$, ma una risposta del genre mi pare tautologica, in quanto altro non si fa che dire che un insieme è formato dagli elementi di cui è formato. A questo uno potrebbe ribattere che in ${1,2,3,ldots,k}$ ci sono l'unità e i suoi successori fino a $k$, per questo l'insieme è finito, al che nuova domanda: chi mi dice che i successori di $1$ fino a $k$ siano finiti? Non potrebbe accadere che tra $1$ e $k$ ci sono infiniti successori?
La risposta dell'intuizione è ovviamente no, ma la risposta formale qual è?
La risposta formale è un no perché così è per assioma, è un no perché così ci piace, è un no perché così si conviene, è no per così deve essere in virtù degli assiomi di Peano (e quindi con questi assiomi si prova il "misfatto"), è un no perché c'è una dimostrazione precisa che non deriva dalla costruzione di $NN$...
Da quì la domanda.
Io ho provato a darne una giustificazione per via deduttiva con una dimostrazione induttiva, facendo uso della definizione di $NN$ come insieme induttivo di $RR$ (**), ovvero, preso $RR$ definisco $NN$ come intersezione di tutte le parti induttive di $RR$, ove per parte induttiva di $RR$ intendo un insieme che abbia le seguenti due proprietà:
1) $1 \in RR$
2) $x in RR => x+1 in RR$
Se $\mathcal{I}$ denota l'insieme delle parti induttive di $NN$ allora $NN:=\bigcup_{X in \mathcal{I}}X$; da questa definizione segue immediatamente che $NN$ contiene l'unità $1$ e gli elementi del tipo $x+1$ costruiti a partire dall'unità, e solo questi, poiché solo questi sono quelli comuni a tutte le parti induttive.
A questo punto, preso $NN supe A := {x in NN | 1<=x<=n}={1,2,3,ldots,n}$ la domanda è: $A$ è finito o infinito?
E' un poco come chidersi $RR supe B := {y in RR | -10 <=x<=sqrt{3}}$ è finito o infinito? La risposta è che esso è infinito ed è motiva dall'assioma di completezza.
La risposta alla domanda su $A$ è, ovviamente, "$A$ è finito!" al che la domanda è "Perché?".
Io ho cercato di provarlo per induzione. Prima ho provato che tra due naturali consecutivi non ce ne sono altri. Dato l'intervallo naturale $]1;2[**$ la sua intersezione con $NN$ è vuota, i.e. $]1;2[ ** cap NN = emptyset$; prova: se fosse $]1;2[** cap NN != emptyset$ allora $exists psi in ]1;2[** cap NN$, quindi $NN sup NN' = NN \\ {psi} != emptyset$. Ma risulterebbe anche se $NN'$ è induttivo, difatti $1 in NN$ e $1 != psi$ essnedo $1 k in NN => k>=1 => k+1>=2>psi$, sicché $NN'$ è induttio, dunque $NN subseteq NN'$, contro il fatto che $N' subset NN$: assurdo. #
Il passo induttivo gioca sullo stesso fatto e procede per assurdo.
Provato questo, posso prendere ${1,2,3,ldots,k}$ (***) e scriverlo come ${1,2,3,ldots,k-1,k}$ dove la presenza di $k-1$ è assicurata dal fatto che $k-1
"That's all Folks" direbbe Bugs Bunny.
E dopo avervi chiesto scusa per avervi tediato, vi chiedo: che ne dite?
______________________________
(*) $NN$ è l'insieme dei naturali privi dello $0$.
(**) E' chiaro quindi che sto introducendo $NN$ a partire da $RR$ dopo una presentazione assiomatica di quest'ultimo.
(***) Notiamo che in tutto questo la scrittura ${1,2,3,ldots,k}$ è un abuso di notazione, dacché già usa e rimanda all'idea che ${1,2,3,ldots,k}$ sia finito.
Per quelle che sono le mie conoscenze, un insieme di dice infinito se esiste un'applicazione biiettiva dell'insieme su una sua parte propria. Si dice finito se non è infinito. Quindi la definizione di finito e infinito gioca sulle applicazioni di un insieme su una sua parte propria.
Poi so che un insieme $I$ si dice possedere $k$ elementi se e solo se è equipotente all'insieme ${1,2,3,ldots,k}$ per qualche $k in NN$ (*), quindi se $I$ possiede $k$ elementi è finito e, viceversa, se è finito allora possiede $k$ elementi.
Tutto questo è bellismo se non fosse per il fatto che si usa implicitamente il fatto che ${1,2,3,ldots,k}$ è finito: infatti se $I$ è equipotente a ${1,2,3,ldots,k}$ allora ha $k$ elementi, dove questo modo di dire è giustificato dalla definizione di equipotenza, ma questo presuppone la nozione che ${1,2,3,ldots,k}$ abbia $k$ elementi, cioè un numero finito di elementi, ed infatti poi è possibile dire che $I$ è finito se e solo se possiede $k$ elementi.
A questo punto sorge in me una domanda spontanea: chi ci dice che ${1,2,3,ldots,k}$ è finito?
Uno potrebbe essere tentato di rispondere che questo ci è detto dal fatto che i naturali di ${1,2,3,ldots,k}$ sono $1,2,3,ldots,k$, ma una risposta del genre mi pare tautologica, in quanto altro non si fa che dire che un insieme è formato dagli elementi di cui è formato. A questo uno potrebbe ribattere che in ${1,2,3,ldots,k}$ ci sono l'unità e i suoi successori fino a $k$, per questo l'insieme è finito, al che nuova domanda: chi mi dice che i successori di $1$ fino a $k$ siano finiti? Non potrebbe accadere che tra $1$ e $k$ ci sono infiniti successori?
La risposta dell'intuizione è ovviamente no, ma la risposta formale qual è?
La risposta formale è un no perché così è per assioma, è un no perché così ci piace, è un no perché così si conviene, è no per così deve essere in virtù degli assiomi di Peano (e quindi con questi assiomi si prova il "misfatto"), è un no perché c'è una dimostrazione precisa che non deriva dalla costruzione di $NN$...
Da quì la domanda.
Io ho provato a darne una giustificazione per via deduttiva con una dimostrazione induttiva, facendo uso della definizione di $NN$ come insieme induttivo di $RR$ (**), ovvero, preso $RR$ definisco $NN$ come intersezione di tutte le parti induttive di $RR$, ove per parte induttiva di $RR$ intendo un insieme che abbia le seguenti due proprietà:
1) $1 \in RR$
2) $x in RR => x+1 in RR$
Se $\mathcal{I}$ denota l'insieme delle parti induttive di $NN$ allora $NN:=\bigcup_{X in \mathcal{I}}X$; da questa definizione segue immediatamente che $NN$ contiene l'unità $1$ e gli elementi del tipo $x+1$ costruiti a partire dall'unità, e solo questi, poiché solo questi sono quelli comuni a tutte le parti induttive.
A questo punto, preso $NN supe A := {x in NN | 1<=x<=n}={1,2,3,ldots,n}$ la domanda è: $A$ è finito o infinito?
E' un poco come chidersi $RR supe B := {y in RR | -10 <=x<=sqrt{3}}$ è finito o infinito? La risposta è che esso è infinito ed è motiva dall'assioma di completezza.
La risposta alla domanda su $A$ è, ovviamente, "$A$ è finito!" al che la domanda è "Perché?".
Io ho cercato di provarlo per induzione. Prima ho provato che tra due naturali consecutivi non ce ne sono altri. Dato l'intervallo naturale $]1;2[**$ la sua intersezione con $NN$ è vuota, i.e. $]1;2[ ** cap NN = emptyset$; prova: se fosse $]1;2[** cap NN != emptyset$ allora $exists psi in ]1;2[** cap NN$, quindi $NN sup NN' = NN \\ {psi} != emptyset$. Ma risulterebbe anche se $NN'$ è induttivo, difatti $1 in NN$ e $1 != psi$ essnedo $1
Il passo induttivo gioca sullo stesso fatto e procede per assurdo.
Provato questo, posso prendere ${1,2,3,ldots,k}$ (***) e scriverlo come ${1,2,3,ldots,k-1,k}$ dove la presenza di $k-1$ è assicurata dal fatto che $k-1
"That's all Folks" direbbe Bugs Bunny.
E dopo avervi chiesto scusa per avervi tediato, vi chiedo: che ne dite?
______________________________
(*) $NN$ è l'insieme dei naturali privi dello $0$.
(**) E' chiaro quindi che sto introducendo $NN$ a partire da $RR$ dopo una presentazione assiomatica di quest'ultimo.
(***) Notiamo che in tutto questo la scrittura ${1,2,3,ldots,k}$ è un abuso di notazione, dacché già usa e rimanda all'idea che ${1,2,3,ldots,k}$ sia finito.
si potrebbe anche pensare di farlo così: i naturali sono l'insieme infinito "più piccolo" e ogni insieme infinito deve avere almeno la cardinalità del numerabile. Dal momento che ogni applicazione $\mathbb{N}->\{1,2,...n\}$ è suriettiva ma non iniettiva mentre l'inclusione fornisce mappa iniettiva $\{1,2,...n\}->\mathbb{N}$ si ha la disuguaglianza stretta $|\{1,2,...n\}|<|\mathbb{N}|$ pertanto tale insieme non può essere infinito.
WiZ, se hai già provato che l'unione di due insiemi finiti è finita allora la dimostrazione per induzione mi pare semplice.
Infatti, $\{ 0\}$ è finito (ha come unica parte propria l'insieme vuoto, che non si può mettere in corrispondenza biunivoca con $\{ 0\}$), ed analogamente ogni singleton del tipo $\{ n\}$ è finito; questa è la base dell'induzione.
Per il passo induttivo, fissato che sia $n\in \NN$, hai ${ 0,\ldots ,n+1\} = \{ 0,\ldots ,n\} \cup \{ n+1\}$ con ognuno dei due "addendi" al secondo membro finito: per la proprietà richiamata all'inizio, $\{ 0,\ldots ,n+1\}$ è finito e ciò completa la dimostrazione.
Come al solito ricordo che non sono un algebrista.
P.S.: Ah, non avevo letto l'ultimo tuo post... La strada che abbiamo preso è la stessa.
Permettimi una considerazione di tipo "economico": visto che per costruire $\NN$ puoi usare gli assiomi di Peano, che la costruzione dei reali è fatta a partire da $\NN$ e che in questa parte della Teoria degli Insiemi non serve l'insieme $\RR$, secondo me è un po' troppo il pensare $\NN$ come parte di $\RR$... Insomma, ne puoi fare ampiamente a meno, tanto più che è provabile anche con gli assiomi di Peano che tra due numeri naturali consecutivi non ve ne sono altri.
Infatti, $\{ 0\}$ è finito (ha come unica parte propria l'insieme vuoto, che non si può mettere in corrispondenza biunivoca con $\{ 0\}$), ed analogamente ogni singleton del tipo $\{ n\}$ è finito; questa è la base dell'induzione.
Per il passo induttivo, fissato che sia $n\in \NN$, hai ${ 0,\ldots ,n+1\} = \{ 0,\ldots ,n\} \cup \{ n+1\}$ con ognuno dei due "addendi" al secondo membro finito: per la proprietà richiamata all'inizio, $\{ 0,\ldots ,n+1\}$ è finito e ciò completa la dimostrazione.
Come al solito ricordo che non sono un algebrista.
P.S.: Ah, non avevo letto l'ultimo tuo post... La strada che abbiamo preso è la stessa.
Permettimi una considerazione di tipo "economico": visto che per costruire $\NN$ puoi usare gli assiomi di Peano, che la costruzione dei reali è fatta a partire da $\NN$ e che in questa parte della Teoria degli Insiemi non serve l'insieme $\RR$, secondo me è un po' troppo il pensare $\NN$ come parte di $\RR$... Insomma, ne puoi fare ampiamente a meno, tanto più che è provabile anche con gli assiomi di Peano che tra due numeri naturali consecutivi non ve ne sono altri.
"Gugo82":
WiZ, se hai già provato che l'unione di due insiemi finiti è finita allora la dimostrazione per induzione mi pare semplice.
Infatti, $\{ 0\}$ è finito (ha come unica parte propria l'insieme vuoto, che non si può mettere in corrispondenza biunivoca con $\{ 0\}$), ed analogamente ogni singleton del tipo $\{ n\}$ è finito; questa è la base dell'induzione.
Per il passo induttivo, fissato che sia $n\in \NN$, hai ${ 0,\ldots ,n+1\} = \{ 0,\ldots ,n\} \cup \{ n+1\}$ con ognuno dei due "addendi" al secondo membro finito: per la proprietà richiamata all'inizio, $\{ 0,\ldots ,n+1\}$ è finito e ciò completa la dimostrazione.
Come al solito ricordo che non sono un algebrista.
P.S.: Ah, non avevo letto l'ultimo tuo post... La strada che abbiamo preso è la stessa.
Permettimi una considerazione di tipo "economico": visto che per costruire $\NN$ puoi usare gli assiomi di Peano, che la costruzione dei reali è fatta a partire da $\NN$ e che in questa parte della Teoria degli Insiemi non serve l'insieme $\RR$, secondo me è un po' troppo il pensare $\NN$ come parte di $\RR$... Insomma, ne puoi fare ampiamente a meno, tanto più che è provabile anche con gli assiomi di Peano che tra due numeri naturali consecutivi non ve ne sono altri.
Sì, la strada che abbiamo preso è la stessa, ma ho preferito costruire $NN$ come intersezione della famiglia induttiva di $RR$ perché per potere scrivere ${1,2,3,ldots,k}={1,2,3,ldots,k-1}cup{k}$ devi sapere che tra $k-1$ e $k$ non ci sono altri naturali, cosa che ho provato con l'intervallo naturale $]k;k+1[**$ intersecato con $NN$. Se si parte dagli assiomi di Peano questa prova che ho prodotto per $]1;2[**$ è buona?
Inoltre in $ZF$ (non vorrei però dire castronerie) un modello di $NN$ è l'intersezione della famiglia degli insiemi induttivi la cui esistenza è data dall'assioma dell'infinito e la cui definizione è
Un insieme $A$ è detto induttivo se e solo se:
1) $\emptyset \in A$
2) $X \in A => X \cup {X} \in A$
Quindi se $\mathcal{I}$ è l'intersezione delle parti induttive dell'insieme infinito, $NN := \bigcup_{X \in \mathcal{I}}X$. Insomma torniamo allo stesso punto, ma dimenticandoci di $RR$.
Quanto agli assiomi di Peano credo che la prova del fatto che $]k;k+1[** \in NN = \emptyset$ sia ancora buona così come l'ho data: che dici?
@alberto86
La Teoria dei Cardinali ancora non la conosco, quindi non avevo proprio pensato a una prova del genere. Mi piace anche questa.
Grazie a tutti.
Grazie a tutti.
premetto che non ho avuto la pazienza di leggere tutto con calma, però volevo dire qualche mia impressione sia sul quesito sia su qualche risposta.
innanzitutto la domanda mi pare sia "viziata" per il semplice fatto che invoca il principio d'induzione, cioè "quella cosa" che permette di passare dal finito all'infinito: ti pare normale chiedere: "n è finito per infiniti n?" ?
per quanto riguarda il metodo generale di Martino, sicuramente è corretto, ma mi pare poco praticabile per dimostrare la "finitezza" di un insieme: piuttosto si usa, trovando un opportuno controesempio, per dimostrare che un insieme è "infinito"...
per quanto riguarda il suggerimento di alberto86, non so, ma mi pare che non funzioni perché ad esempio quello stesso tipo di funzione (da $NN$ a $NN$) si usa anche per dimostrare che un insieme infinito è equipotente ad una sua parte propria...
sul fatto che si possono prendere anche numeri irrazionali a intervalli regolari, non c'è assolutamente alcun problema, però, ripeto, non ho avuto la pazienza di leggere tutto con calma, per cui non mi pare che l'ultimo intervento di WiZaRd sia risolutivo rispetto al problema precedente...
ciao.
innanzitutto la domanda mi pare sia "viziata" per il semplice fatto che invoca il principio d'induzione, cioè "quella cosa" che permette di passare dal finito all'infinito: ti pare normale chiedere: "n è finito per infiniti n?" ?
per quanto riguarda il metodo generale di Martino, sicuramente è corretto, ma mi pare poco praticabile per dimostrare la "finitezza" di un insieme: piuttosto si usa, trovando un opportuno controesempio, per dimostrare che un insieme è "infinito"...
per quanto riguarda il suggerimento di alberto86, non so, ma mi pare che non funzioni perché ad esempio quello stesso tipo di funzione (da $NN$ a $NN$) si usa anche per dimostrare che un insieme infinito è equipotente ad una sua parte propria...
sul fatto che si possono prendere anche numeri irrazionali a intervalli regolari, non c'è assolutamente alcun problema, però, ripeto, non ho avuto la pazienza di leggere tutto con calma, per cui non mi pare che l'ultimo intervento di WiZaRd sia risolutivo rispetto al problema precedente...
ciao.
ho continuato a leggere le dispense, qualche spunto:
un insieme si dice D-finito se non è equipotente ad alcun suo sottoinsieme proprio (da Dedekind)
si dice finito se è equipotente all'insieme ${1,...n}$ per qualche $n in NN$
proposizione: Se vale l'assioma della scelta, allora le nozioni di finito e D-finito sono equivalenti.
A parte che io definirei il concetto di infinito come non finito (però mi pare di capire che le cose non vadano così ) la finitezza (si dice?) di ${1,...,n}$ deriva sempre dalla definizione di D-finito anche senza assioma della scelta (che serve per l'implicazione inversa).
Non aggiungo altro perchè mi muovo in un terreno a me poco famigliare!
un insieme si dice D-finito se non è equipotente ad alcun suo sottoinsieme proprio (da Dedekind)
si dice finito se è equipotente all'insieme ${1,...n}$ per qualche $n in NN$
proposizione: Se vale l'assioma della scelta, allora le nozioni di finito e D-finito sono equivalenti.
A parte che io definirei il concetto di infinito come non finito (però mi pare di capire che le cose non vadano così
) la finitezza (si dice?) di ${1,...,n}$ deriva sempre dalla definizione di D-finito anche senza assioma della scelta (che serve per l'implicazione inversa).Non aggiungo altro perchè mi muovo in un terreno a me poco famigliare!
Io intanto ho aperto il Prodi.
Da quanto riportato mi pare di capire che il punto di vista di rubik sia più che legttimo: definiamo un insieme infinito a partire dalla definizone di insieme finito.
Partendo da questa prospettiva, l'insieme $I_n$ è usato come definizione di inseme finito, ma, nonostante ciò, si prova comunque, come teorema, che $I_n$ non può essere messo in corrispondenza biunivoca con una sua parte propria, perché, qulora ciò fosse possibile, la definizione di insieme finito non sarebbe ben posta.
Prodi dimostarerà poi, un paio di pagine avanti che un insieme è infinito se e solo se esiste una biiezione dell'insieme su una sua parte propria: quindi quella che alcuni di noi assume come definizione di infinito insiemistico, diviene, per Prodi, un teorema.
Quindi, assumendo come definizione di finito l'esistenza della biiezione tra $X$ e $I_n$ si prova che $I_n$ non può essere posto in corrispondenza biunivoca con una sua parte propria, al fine di rendere ben posta la definizione data. L'esistenza della biiezione tra $X$ e una parte propria diviene una caratterizzazione per gli insiemi infiniti da dimostare come teorema.
Sviluppando una teoria che parta dal punto opposto, cioè che assumo come definizione di partenza quella di insieme infinito, dicendo che $X$ è infinito se e solo se esste una biiezione tra $X$ e una sua parte propria, la definizione di insieme finito diviene la negazione di quella di insieme finito e, dunque, il fatto che un insieme sia finito se e solo se esiste $n$ tale che $X$ è ponibile in corrispondenza biunivoca con $I_n$, diviene una caretterizzazione del finito insiemistico, ragone per cui è da provare il fatto che $I_n$ sia finito.
Se questa mia linea di pensiero è corretta, allora non credo di essere d'accordo con adaBTTLS quando dice
Dunque, tornando alla domanda di partenza, bisogna provare che $I_n$ è finito.
Provare che $I_n$ (*) senza passare per il recupero di $NN$ a partire dall'assiomatizzazione di $RR$, quindi utilizzando i soli assiomi di Peano, come suggeriva Gugo82 nel suo P.S., credo presupponga una doppia prova per induzione.
Difatti, per provare che $I_n$ è finito, sia io che Gugo82 spezziamo $I_n$ in $I_{n-1} cup {n}$, ma per fare ciò lecitamente è necessario sapere che tra $n-1$ e $n$ non vi sono altri naturali. Dunque bisogna provare che ${x in NN | n-1
Assiomi di Peano.
1) $0 in NN$
2) $exists sigma : NN to NN | forall x_1, x_2 in NN, x_1!=x_2 => sigma(x_1)!=sigma(x_2)$
3) $0 notin sigma(NN)$
4) $(S subseteq NN ^^^ (0 in S) ^^^ (x in S => x+1 in S))=> S=NN$
Sia ora da provare che ${x in NN | 0 0 NN'!=NN$. Per applicare il principio di induzione ho però bisogno del fatto che $NN' subseteq NN$, mentre so che è $NN' subset NN$. Ma $NN' subseteq NN$ deriva da $NN' subset NN$ per definizione di $subset$, quindi procedo con l'induzione. $0 != xi ^^^ 0 in NN$, dunque $0 in NN'$. Se $x in NN'$, allora $x in NN ^^^ x != xi$, inoltre $x in NN => x >=0 => x+1 >= 1>xi$ il che comporta che $x+1 in NN ^^^ x+1 !=xi$, dunque $x+1 in NN \\ {xi} =: NN'$, per cui $x in NN' => x+1 in NN'$, quindi $NN'=NN$: assurdo. #
Il punto che mi lascia perplesso è proprio questa derivazione di $NN' subseteq NN$ da $NN' subset NN$: mi pare una forzatura, anche se $subseteq$ deriva dalla definizione di $subset$; voi che ne dite? E' ammissibile o è una forzatura che toglie validità alla prova?
"Prodi, Analisi Matematica, Bollati Boringhieri":
DEFINIZIONE. Dati due insiemi, si dice che essi hanno lo stesso numero cardinale se essi possono essere messi in corrispondenza biunivoca.
Per indicare che due insiemi $X$ e $Y$ hanno lo stesso numero cardinale, scriveremo $c(X)=c(Y)$. Questa relazione gode delle proprietà riflessiva, simmetrica, transitiva.
OSSERVAZIONE.Se tutti gli insiemi che si considerano in una certa teoria matematica sono contenuti in uno stesso insieme $E$ (che fa da "universo"), il simbolo $c(X)$ assume il significato di classe di equivalenza in $\wp(E)$ (cioè indica la famiglia di tutti i sottoinsiemi di $E$ che si possono porre in corrispondenza biunivoca con $X$). Ma, se non si fa una tale convenzione, dal momento che, come sappiamo, non esiste "l'insieme di tutti gli insiemi", l'espressione $c(X)=c(Y)$ deve essere intesa, globalmente, come un predicato binario (relazione, ma non in senso insiemistico) tra $X$ e $Y$.
Comnciamo ad applicare la definizione precedente ai casi più semplici. Preso un $n in NN$ consideriamo l'insieme degli interi che precedono $n$, cioè $I_n={0,1,2,3,ldots,n-1}$. Gli insiemi $I_n$ si presentano bene come insiemi-campione.
DEFINIZIONE. Si dice che un inseme $X$ è finito se esiste un $n in NN$ tale che $X$ si possa mettere in corrispondenza biunivoca con $I_n$; in questo caso si dice che $X$ ha numero cardnale $n$, e si scrive $c(X)=n$. Se non esiste alcun $n$ per cui questo è possibile, si dice che $X$ è infinito.
Perché l'attribuzione del numero cardinale $n$ all'insieme $X$ sia legittima, occorre dimostrare che, se $X$ è finito, è unico l'intero $n$ tale che $X$ e $I_n$ si possono far corrispondere biunivocamente. Supponiamo, pr assurdo, che $X$ si possa mettere in corrispondenza biunivoca sia con $I_n$ sia con $I_m$, con $n!=m$. Allora è chiaro che $I_m$ e $I_n$ si possono porre in corrispondenza biunivoc fra di loro. Ma ciò escluso dal seguente teorema, che ha una portata un poco più generale di quanto quì occorra:
TEOREMA. Per ogni intero $n=1$, l'insieme $I_n$ non può essere posto in corrispondenza biunivoca con una sua parte propria.
Da quanto riportato mi pare di capire che il punto di vista di rubik sia più che legttimo: definiamo un insieme infinito a partire dalla definizone di insieme finito.
Partendo da questa prospettiva, l'insieme $I_n$ è usato come definizione di inseme finito, ma, nonostante ciò, si prova comunque, come teorema, che $I_n$ non può essere messo in corrispondenza biunivoca con una sua parte propria, perché, qulora ciò fosse possibile, la definizione di insieme finito non sarebbe ben posta.
Prodi dimostarerà poi, un paio di pagine avanti che un insieme è infinito se e solo se esiste una biiezione dell'insieme su una sua parte propria: quindi quella che alcuni di noi assume come definizione di infinito insiemistico, diviene, per Prodi, un teorema.
Quindi, assumendo come definizione di finito l'esistenza della biiezione tra $X$ e $I_n$ si prova che $I_n$ non può essere posto in corrispondenza biunivoca con una sua parte propria, al fine di rendere ben posta la definizione data. L'esistenza della biiezione tra $X$ e una parte propria diviene una caratterizzazione per gli insiemi infiniti da dimostare come teorema.
Sviluppando una teoria che parta dal punto opposto, cioè che assumo come definizione di partenza quella di insieme infinito, dicendo che $X$ è infinito se e solo se esste una biiezione tra $X$ e una sua parte propria, la definizione di insieme finito diviene la negazione di quella di insieme finito e, dunque, il fatto che un insieme sia finito se e solo se esiste $n$ tale che $X$ è ponibile in corrispondenza biunivoca con $I_n$, diviene una caretterizzazione del finito insiemistico, ragone per cui è da provare il fatto che $I_n$ sia finito.
Se questa mia linea di pensiero è corretta, allora non credo di essere d'accordo con adaBTTLS quando dice
"adaBTTLS":
ti pare normale chiedere: "n è finito per infiniti n?" ?
Dunque, tornando alla domanda di partenza, bisogna provare che $I_n$ è finito.
Provare che $I_n$ (*) senza passare per il recupero di $NN$ a partire dall'assiomatizzazione di $RR$, quindi utilizzando i soli assiomi di Peano, come suggeriva Gugo82 nel suo P.S., credo presupponga una doppia prova per induzione.
Difatti, per provare che $I_n$ è finito, sia io che Gugo82 spezziamo $I_n$ in $I_{n-1} cup {n}$, ma per fare ciò lecitamente è necessario sapere che tra $n-1$ e $n$ non vi sono altri naturali. Dunque bisogna provare che ${x in NN | n-1
Assiomi di Peano.
1) $0 in NN$
2) $exists sigma : NN to NN | forall x_1, x_2 in NN, x_1!=x_2 => sigma(x_1)!=sigma(x_2)$
3) $0 notin sigma(NN)$
4) $(S subseteq NN ^^^ (0 in S) ^^^ (x in S => x+1 in S))=> S=NN$
Sia ora da provare che ${x in NN | 0
Il punto che mi lascia perplesso è proprio questa derivazione di $NN' subseteq NN$ da $NN' subset NN$: mi pare una forzatura, anche se $subseteq$ deriva dalla definizione di $subset$; voi che ne dite? E' ammissibile o è una forzatura che toglie validità alla prova?
il tuo non essere d'accordo con la frase estrapolata dal mio messaggio riguarda l'ammissibilità della domanda o il fatto che la mia domanda "provocatoria" significhi una cosa sostanzialmente diversa dalla tua richiesta iniziale, quando hai citato il principio d'induzione?
a parte il fatto che io sono perfettamente d'accordo con quanto affermato da rubik,
il ragionamento di Gugo82, che non fa una piega, parte da "un generico ma preciso valore di n": ho qualche perplessità, dato il contenuto della domanda del topic, ad usare il principio d'induzione per generalizzare il ragionameno di Gugo82. il motivo è sostanzialmente il fatto che, pur essendo vero che ogni numero naturale è finito, l'insieme dei numeri naturali è infinito (ed il fatto dipende proprio dal principio d'induzione).
sull'ultima cosa che hai chiesto, sono curiosa anch'io di sentire altri pareri, ma mentre non mi sembra difficile "aggiustare" i formalismi perché sia valido il ragionamento per assurdo, non vedo come ti possa aiutare il principio d'induzione (se ti sei posto il problema della possibile esistenza di un certo $xi$ in $NN$, affermando che $xinotinNN$ non sei garantito che $(xi+1)notinNN$, casomai il principio d'induzione ti avrebbe aiutato ad affermare il contrario!).
ciao.
a parte il fatto che io sono perfettamente d'accordo con quanto affermato da rubik,
il ragionamento di Gugo82, che non fa una piega, parte da "un generico ma preciso valore di n": ho qualche perplessità, dato il contenuto della domanda del topic, ad usare il principio d'induzione per generalizzare il ragionameno di Gugo82. il motivo è sostanzialmente il fatto che, pur essendo vero che ogni numero naturale è finito, l'insieme dei numeri naturali è infinito (ed il fatto dipende proprio dal principio d'induzione).
sull'ultima cosa che hai chiesto, sono curiosa anch'io di sentire altri pareri, ma mentre non mi sembra difficile "aggiustare" i formalismi perché sia valido il ragionamento per assurdo, non vedo come ti possa aiutare il principio d'induzione (se ti sei posto il problema della possibile esistenza di un certo $xi$ in $NN$, affermando che $xinotinNN$ non sei garantito che $(xi+1)notinNN$, casomai il principio d'induzione ti avrebbe aiutato ad affermare il contrario!).
ciao.
Penso di aver compreso il dubbio che poni sulla generalizzazione tramite principio di induzione. Al momento però non so proprio cosa aggiungere per cercare di far quadrare il tutto, quindi lascio la parola a chi eventualmente ne sa di più e ha voglia di "illuminarci".
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo