Dubbio formale
Stavo svolgendo il seguente esercizio:
Show that every infinite set contains a countable subset
che mi ha portato a chiedermi quale assioma della teoria degli insiemi stessi implicitamente usando.
Premetto che la mia definizione di insieme infinito è quella secondo Dedekind.
Io ho pensato di svolgerlo semplicemente così:
E' sufficiente trovare una bijezione tra un sottoinsieme di un dato insieme infinito \(\displaystyle X_1 \) e \(\displaystyle \mathbb{N} \).
Per farlo si può operare così:
1. si prende un \(\displaystyle x_1 \in X_1 \) si costruisce la coppia ordinata \(\displaystyle (1,x_1) \)
2. si prende un \(\displaystyle x_2 \in X_2=X_1 \setminus \{ x_1\} \) e si costruisce \(\displaystyle (2,x_2) \)
...
n. si prende un \(\displaystyle x_n \in X_n=X_{n-1} \setminus \{ x_{n-1}\} \) e si costruisce \(\displaystyle (n,x_n) \)
...
e così via.
Ogni passaggio è giustificato dal fatto che \(\displaystyle \forall n \in \mathbb{N} \), \(\displaystyle X_n \) è non vuoto (se lo fosse allora \(\displaystyle X_1 \) sarebbe in bijezione con un qualche \(\displaystyle E_n=\{ 1,2,...,n\} \), che si può dimostrare essere finito, contro l'ipotesi iniziale) e quindi si può sempre estrarre un nuovo elemento.
Dunque l'insieme delle coppie \(\displaystyle \{ (n,x_n), n \in \mathbb{N}\} \) rappresenta la mappa biunivoca cercata.
Sperando che non ci siano falle logiche nel mio tentativo di soluzione, chiedo: ogni volta che pesco un elemento da un qualche \(\displaystyle X_n \), sto utilizzando l'assioma di scelta? O questa operazione si può giustificare in altro modo?
Grazie.
Show that every infinite set contains a countable subset
che mi ha portato a chiedermi quale assioma della teoria degli insiemi stessi implicitamente usando.
Premetto che la mia definizione di insieme infinito è quella secondo Dedekind.
Io ho pensato di svolgerlo semplicemente così:
E' sufficiente trovare una bijezione tra un sottoinsieme di un dato insieme infinito \(\displaystyle X_1 \) e \(\displaystyle \mathbb{N} \).
Per farlo si può operare così:
1. si prende un \(\displaystyle x_1 \in X_1 \) si costruisce la coppia ordinata \(\displaystyle (1,x_1) \)
2. si prende un \(\displaystyle x_2 \in X_2=X_1 \setminus \{ x_1\} \) e si costruisce \(\displaystyle (2,x_2) \)
...
n. si prende un \(\displaystyle x_n \in X_n=X_{n-1} \setminus \{ x_{n-1}\} \) e si costruisce \(\displaystyle (n,x_n) \)
...
e così via.
Ogni passaggio è giustificato dal fatto che \(\displaystyle \forall n \in \mathbb{N} \), \(\displaystyle X_n \) è non vuoto (se lo fosse allora \(\displaystyle X_1 \) sarebbe in bijezione con un qualche \(\displaystyle E_n=\{ 1,2,...,n\} \), che si può dimostrare essere finito, contro l'ipotesi iniziale) e quindi si può sempre estrarre un nuovo elemento.
Dunque l'insieme delle coppie \(\displaystyle \{ (n,x_n), n \in \mathbb{N}\} \) rappresenta la mappa biunivoca cercata.
Sperando che non ci siano falle logiche nel mio tentativo di soluzione, chiedo: ogni volta che pesco un elemento da un qualche \(\displaystyle X_n \), sto utilizzando l'assioma di scelta? O questa operazione si può giustificare in altro modo?
Grazie.
Risposte
Direi (ma non sono un esperto) che l'assioma della scelta non lo stai usando quando prendi un elemento in $X_n$, ma piuttosto implicitamente usi l'assioma della scelta (forse ti potrebbe bastare l'assioma della scelta dipendente, ma non ne sono per niente sicuro) quando usi che ${(n,x_n)|n\inNN}$ è un insieme.
Comunque non ho capito quale sarebbe il sottoinsieme di $X$ che hai trovato in biezione con $NN$.
Comunque non ho capito quale sarebbe il sottoinsieme di $X$ che hai trovato in biezione con $NN$.
Ciao Ianero 
Vediamo se riesco a mettermi in mezzo alle tue idee.
La tua definizione di insieme infinito è quella secondo cui dato un insieme $X$ esistono $YsubsetX$ e $f:Y->X$ tale che $f$ sia una biiezione.
Tu hai preso $X_1 subset X$ insieme infinito(?) e poi affermi che se $X_n$ fosse vuoto, allora $X_1$ sarebbe finito.
Usiamo la relazione di equipotenza per insiemi ovvero diremo che,
Ora sappiamo che $X$ è un insieme infinito, quindi possiamo considerare l'insieme
tale insieme è certamente non vuoto nell'ipotesi in cui esso sia Dedekind-infinito, quindi prendiamo $Y inA$
cerchiamo di mostrarlo in modo formale. Vogliamo mostrare che preso
si ha esattamente $U=NN$
chiaramente mostrare che $U=NN$ significa che comunque preso $n in NN$ si può trovare un sottoinsieme proprio di $Y$ che sia equipotente a un sottoinsieme di $NN$
proviamo per induzione.
Chiaramente $0 inU$ poiché sicuramente preso un singoletto $Z={y}, y inY$ si ottiene che $#Z=#I_1$ basta porre $f(y)=1$ e abbiamo finito. Inoltre non può essere $YsetminusZ=emptyset$ poiché se lo fosse allora avremmo che $Y=Z$ ovvero $#Y=#I_1$ ma allora si avrebbe $#X=#I_1$ ovvero $X$ non sarebbe infinito.
mostriamo ora che $n inU=>n+1 inU$
per ipotesi esiste un sottoinsieme $ZsubsetY$ equipotente ad $I_(n+1)$ tale che $YsetminusZ ne emptyset$
sia esso $Z={y_0,y_1,..,y_n}$. Per ipotesi $YsetminusZ ne emptyset$ quindi prendiamo $y inYsetminusZ$ e prendiamo $Zcup{y}$
Sempre per ipotesi $#Z=#I_(n+1)$ da cui esiste una biiezione $f:Z->I_(n+1)$ e ora costruiamo la seguente estensione
chiaramente questa è una biiezione quindi $#Zcup{y}=#I_(n+2)$
Ci manca di mostrare che $Ysetminus(Zcup{y})ne emptyset$ per concludere. Se così non fosse $Y$ sarebbe equipotente ad $I_(n+2)$ poiché sarebbe $Y=Zcup{y}$ e quindi anche $X$ sarebbe equipotente a $I_(n+2)$ e pertanto non sarebbe Dedekind finito.
Quindi abbiamo mostrato che $U=NN$ per induzione.
Penso che questo sia sufficiente a concludere, che di fatto è esattamente quello che hai scritto anche tu in altri termini.
Non penso di aver usato l'assioma della scelta, piuttosto ho usato gli assiomi di $NN$
Non ne sono sicurissimo, però fiducioso si.
Vediamo se riesco a mettermi in mezzo alle tue idee.
La tua definizione di insieme infinito è quella secondo cui dato un insieme $X$ esistono $YsubsetX$ e $f:Y->X$ tale che $f$ sia una biiezione.
Tu hai preso $X_1 subset X$ insieme infinito(?) e poi affermi che se $X_n$ fosse vuoto, allora $X_1$ sarebbe finito.
Usiamo la relazione di equipotenza per insiemi ovvero diremo che,
$#Y=#X <=> existsf:Y->X$ tale che $f$ biunivoca
Ora sappiamo che $X$ è un insieme infinito, quindi possiamo considerare l'insieme
$A={YsubsetX:#Y=#X}$
tale insieme è certamente non vuoto nell'ipotesi in cui esso sia Dedekind-infinito, quindi prendiamo $Y inA$
cerchiamo di mostrarlo in modo formale. Vogliamo mostrare che preso
$U={n inNN|existsZsubsetY:#Z=#I_(n+1):YsetminusZneemptyset}$
si ha esattamente $U=NN$
ponendo $I_k={1,2,..,k}=NNcap[1,k]$
chiaramente mostrare che $U=NN$ significa che comunque preso $n in NN$ si può trovare un sottoinsieme proprio di $Y$ che sia equipotente a un sottoinsieme di $NN$
proviamo per induzione.
Chiaramente $0 inU$ poiché sicuramente preso un singoletto $Z={y}, y inY$ si ottiene che $#Z=#I_1$ basta porre $f(y)=1$ e abbiamo finito. Inoltre non può essere $YsetminusZ=emptyset$ poiché se lo fosse allora avremmo che $Y=Z$ ovvero $#Y=#I_1$ ma allora si avrebbe $#X=#I_1$ ovvero $X$ non sarebbe infinito.
mostriamo ora che $n inU=>n+1 inU$
per ipotesi esiste un sottoinsieme $ZsubsetY$ equipotente ad $I_(n+1)$ tale che $YsetminusZ ne emptyset$
sia esso $Z={y_0,y_1,..,y_n}$. Per ipotesi $YsetminusZ ne emptyset$ quindi prendiamo $y inYsetminusZ$ e prendiamo $Zcup{y}$
Sempre per ipotesi $#Z=#I_(n+1)$ da cui esiste una biiezione $f:Z->I_(n+1)$ e ora costruiamo la seguente estensione
$g:Zcup{y}-> I_(n+2)$ definita come $g(x):={(f(x) if x inZ),(n+2 if x=y):}$
chiaramente questa è una biiezione quindi $#Zcup{y}=#I_(n+2)$
Ci manca di mostrare che $Ysetminus(Zcup{y})ne emptyset$ per concludere. Se così non fosse $Y$ sarebbe equipotente ad $I_(n+2)$ poiché sarebbe $Y=Zcup{y}$ e quindi anche $X$ sarebbe equipotente a $I_(n+2)$ e pertanto non sarebbe Dedekind finito.
Quindi abbiamo mostrato che $U=NN$ per induzione.
Penso che questo sia sufficiente a concludere, che di fatto è esattamente quello che hai scritto anche tu in altri termini.
Non penso di aver usato l'assioma della scelta, piuttosto ho usato gli assiomi di $NN$
Non ne sono sicurissimo, però fiducioso si.
Ciao ragazzi e grazie di essere intervenuti.
Cerco di rispondere per step.
L'insieme \(\displaystyle \{ x_1,x_2,...,x_n,... \} \) che è un sottoinsieme di \(\displaystyle X_1 \) poiché ogni \(\displaystyle x_n \) appartiene a \(\displaystyle X_n \subset X_1 \).
Yes.
No, ho chiamato l'ìnsieme infinito in analisi direttamente \(\displaystyle X_1 \) per avere una notazione unificata.
Esatto.
Come fa $Z \setminus Y$ a essere \(\displaystyle \neq \emptyset \), se $Z \subset Y$
Non è questo l'assioma di scelta?
Qui ho capito cosa vuoi dimostrare (forse anche sopra volevi scrivere $ Y \setminus Z \ne \emptyset $ invece che il contrario) ma non ho capito come l'hai fatto: $f$ da come la stai usando è una funzione che ha \(\displaystyle \mathbb{N} \) come codominio, che c'entra \(\displaystyle X \)
Non hai usato di nuovo l'assioma di scelta?
Se ho capito il tuo discorso è questo:
Parto da $X$, insieme infinito.
Prendo l'insieme di tutti i sottoinsiemi di $X$ che sono in mappa biunivoca con $X$.
Ne considero uno in particolare e lo chiamo $Y$.
Poi dimostro che dentro $Y$ riesco a trovare per ogni $n$ naturale un suo sottoinsieme di $n$ elementi.
A questo punto faccio la bijezione tra i naturali e ognuno di questi insiemi.
Questi però non è ciò che chiede la traccia, perché serve invece una mappa biunivoca tra i naturali e un sottoinsieme di elementi di \(\displaystyle X \) (e non una mappa biunivoca tra i naturali e un insieme di insiemi contenenti elementi di $X$).
Inoltre non capisco a che serve passare da $X$ a $Y$, tutto il discorso non si poteva ripetere uguale usando direttamente $X$?
Comunque, quello che mi sembra di aver capito -ed è il motivo per cui parlo di assioma di scelta- è che da un insieme non si possono selezionare elementi (prendere un sottoinsieme dell'insieme di partenza) se non caratterizzandoli attraverso una proprietà. Questo è l'assioma di separazione.
Mi sembra invece che l'unico modo di pescare un elemento a piacere (senza bisogno di descriverlo attraverso una sua proprietà che lo distingue dagli altri) in un insieme non vuoto sia ricorrere all'assioma di scelta.
Nel frattempo vi ringrazio.
Cerco di rispondere per step.
"otta96":
Comunque non ho capito quale sarebbe il sottoinsieme di X_1 che hai trovato in biezione con N
L'insieme \(\displaystyle \{ x_1,x_2,...,x_n,... \} \) che è un sottoinsieme di \(\displaystyle X_1 \) poiché ogni \(\displaystyle x_n \) appartiene a \(\displaystyle X_n \subset X_1 \).
"anto_zoolander":
La tua definizione di insieme infinito è quella secondo cui dato un insieme X esistono Y⊂X e f:Y→X tale che f sia una biiezione.
Yes.
"anto_zoolander":
Tu hai preso X1⊂X insieme infinito(?)
No, ho chiamato l'ìnsieme infinito in analisi direttamente \(\displaystyle X_1 \) per avere una notazione unificata.
"anto_zoolander":
affermi che se Xn fosse vuoto, allora X1 sarebbe finito
Esatto.
"anto_zoolander":
$ U={n inNN|existsZsubsetY,#Z=#I_(n+1):ZsetminusYneemptyset} $
Come fa $Z \setminus Y$ a essere \(\displaystyle \neq \emptyset \), se $Z \subset Y$
"anto_zoolander":
preso un singoletto $ Z={y}, y inY $
Non è questo l'assioma di scelta?
"anto_zoolander":
Inoltre non può essere $ YsetminusZ=emptyset $ poiché se lo fosse allora avremmo che $ f({y})=X $ e l'unico sottoinsieme proprio è l'insieme vuoto, ma Y non è vuoto.
Qui ho capito cosa vuoi dimostrare (forse anche sopra volevi scrivere $ Y \setminus Z \ne \emptyset $ invece che il contrario) ma non ho capito come l'hai fatto: $f$ da come la stai usando è una funzione che ha \(\displaystyle \mathbb{N} \) come codominio, che c'entra \(\displaystyle X \)
"anto_zoolander":
Per ipotesi $ YsetminusZ ne emptyset $ quindi prendiamo $ y inYsetminusZ $
Non hai usato di nuovo l'assioma di scelta?
"anto_zoolander":
Penso che questo sia sufficiente a concludere, che di fatto è esattamente quello che hai scritto anche tu in altri termini.
Se ho capito il tuo discorso è questo:
Parto da $X$, insieme infinito.
Prendo l'insieme di tutti i sottoinsiemi di $X$ che sono in mappa biunivoca con $X$.
Ne considero uno in particolare e lo chiamo $Y$.
Poi dimostro che dentro $Y$ riesco a trovare per ogni $n$ naturale un suo sottoinsieme di $n$ elementi.
A questo punto faccio la bijezione tra i naturali e ognuno di questi insiemi.
Questi però non è ciò che chiede la traccia, perché serve invece una mappa biunivoca tra i naturali e un sottoinsieme di elementi di \(\displaystyle X \) (e non una mappa biunivoca tra i naturali e un insieme di insiemi contenenti elementi di $X$).
Inoltre non capisco a che serve passare da $X$ a $Y$, tutto il discorso non si poteva ripetere uguale usando direttamente $X$?
Comunque, quello che mi sembra di aver capito -ed è il motivo per cui parlo di assioma di scelta- è che da un insieme non si possono selezionare elementi (prendere un sottoinsieme dell'insieme di partenza) se non caratterizzandoli attraverso una proprietà. Questo è l'assioma di separazione.
Mi sembra invece che l'unico modo di pescare un elemento a piacere (senza bisogno di descriverlo attraverso una sua proprietà che lo distingue dagli altri) in un insieme non vuoto sia ricorrere all'assioma di scelta.
Nel frattempo vi ringrazio.
Mi smentisco: a quanto pare quando la famiglia di insiemi da cui pescare un elemento è finita (nel mio caso un solo insieme, che è \(\displaystyle X_1 \) ) gli altri assiomi della teoria degli insiemi dovrebbero garantire la possibilità di fare questa selezione.
Purtroppo però non ho capito come.
Purtroppo però non ho capito come.
Di quella era $YsetminusZ$ e non il contrario . Modifico.
In realtà io sto solo prendendo un elemento di $Y$.
Se non sbaglio l’assioma della scelta dice che data una famiglia $F={A_i: i inI}$ esiste una funzione $f:F->bigcup_(i inI)A_i$ tale che associa ad ogni insieme della famiglia un unico elemento di quell’insieme.
In realtá a me basta la funzione $id:Y->Y$ che mi associa ad ogni elemento, lo stesso elemento.
Anche se si potrebbe vedere $Y$ come parte di una famiglia, che per l’assioma esistenuna funzione che mi associa a $Y$ un unico elemento di $Y$.
Quello che mi chiedo io è: per scegliere un elemento di un insieme, a caso, è necessario utilizzare l’assioma della scelta? Perché a questo non so rispondere.
Si ho sbagliato. Intendevo dire un’altra cosa.
Se $YsetminusZ=emptyset=>Y=Z$ da cui si avrebbe che $X$ sarebbe equipotenti ad un insieme finito.
Io parto da $Y$ per poi dedurre gli assurdi per il fatto che $X$ è infinito. O almeno mi è saltato in mente di farla così
. Modifico.In realtà io sto solo prendendo un elemento di $Y$.
Se non sbaglio l’assioma della scelta dice che data una famiglia $F={A_i: i inI}$ esiste una funzione $f:F->bigcup_(i inI)A_i$ tale che associa ad ogni insieme della famiglia un unico elemento di quell’insieme.
In realtá a me basta la funzione $id:Y->Y$ che mi associa ad ogni elemento, lo stesso elemento.
Anche se si potrebbe vedere $Y$ come parte di una famiglia, che per l’assioma esistenuna funzione che mi associa a $Y$ un unico elemento di $Y$.
Quello che mi chiedo io è: per scegliere un elemento di un insieme, a caso, è necessario utilizzare l’assioma della scelta? Perché a questo non so rispondere.
Si ho sbagliato. Intendevo dire un’altra cosa.
Se $YsetminusZ=emptyset=>Y=Z$ da cui si avrebbe che $X$ sarebbe equipotenti ad un insieme finito.
Io parto da $Y$ per poi dedurre gli assurdi per il fatto che $X$ è infinito. O almeno mi è saltato in mente di farla così
Quello che mi chiedo io è: per scegliere un elemento di un insieme, a caso, è necessario utilizzare l’assioma della scelta? Perché a questo non so rispondere.
Esattamente, è questo che mi sto chiedendo pure io.
La risposta dovrebbe essere no da come ho capito, proprio perché un insieme $X$ può essere visto come elemento di una famiglia di insiemi contenente un solo elemento ($X$, per l'appunto), e dunque l'assioma di scelta non serve per famiglie di insiemi finite. Non ho capito perché però.
Perché penso che se un insieme è non vuoto allora contiene almeno un elemento e l’affermazione $exists y inY$ non dovrebbe portare a contraddizioni, visto che è conseguenza del non essere insieme vuoto.
Inoltre penso che tutti gli elementi dell’insieme godano della proprietà di appartenere all’insieme e quindi sceglierne uno o un altro in base a questa proprietà sia del tutto indifferente
Inoltre penso che tutti gli elementi dell’insieme godano della proprietà di appartenere all’insieme e quindi sceglierne uno o un altro in base a questa proprietà sia del tutto indifferente
A giudicare dal nome stai usando l'assioma dell'infinito https://en.wikipedia.org/wiki/Axiom_of_infinity
Ma è solo una vaga impressione dettata dal fatto che esso si chiama assioma dell'infinito.
Ma è solo una vaga impressione dettata dal fatto che esso si chiama assioma dell'infinito.
Ma quello non si usa per costruire formalmente $NN$ a partire da ‘cose’ con insiemi vuoti?
Io non penso di averlo usato
Io non penso di averlo usato
Mamma mia, più ci sto pensando e più mi sto incasinando le idee.
Riporto l'assioma di scelta che c'è sul mio libro:
For any family of non-empty sets there exists a set C such that for each set X in the family, $X\bigcap C$ consists of exactly one element.
E se allora prendo gli insiemi:
$A=\{1\}$
$B=\{1,2\}$
$D=\{1,2,3\}$
chi sarebbe questo fantomatico insieme C, di cui l'assioma garantisce l'esistenza?
Riporto l'assioma di scelta che c'è sul mio libro:
For any family of non-empty sets there exists a set C such that for each set X in the family, $X\bigcap C$ consists of exactly one element.
E se allora prendo gli insiemi:
$A=\{1\}$
$B=\{1,2\}$
$D=\{1,2,3\}$
chi sarebbe questo fantomatico insieme C, di cui l'assioma garantisce l'esistenza?
${1}$.
"Ianero":
Mamma mia, più ci sto pensando e più mi sto incasinando le idee.
Riporto l'assioma di scelta che c'è sul mio libro:
For any family of non-empty sets there exists a set C such that for each set X in the family, $X\bigcap C$ consists of exactly one element.
E se allora prendo gli insiemi:
$A=\{1\}$
$B=\{1,2\}$
$D=\{1,2,3\}$
chi sarebbe questo fantomatico insieme C, di cui l'assioma garantisce l'esistenza?
In questo caso va bene \(\{1\}\). Ma ti sei dimenticato che gli insiemi devono essere a due a due disgiunti; questo assicura che in \(\coprod_{i\in I} A_i\) sia sempre possibile scegliere un singolo elemento $x_i\in A_i$ e castare l'insieme \(\{x_i\mid i\in I\}\).
Comunque, ti consiglio di dimenticare quel che ti è stato detto finora e di ripartire dall'inizio.
Vuoi dimostrare che ogni insieme infinito $X$ contiene una copia di $NN$. Innanzitutto dobbiamo metterci d'accordo su cosa significa infinito; l'equivalenza tra Dedekind-infinito (esiste una biiezione $X\to Y$ con \(Y\subset X\) sottoinsieme proprio) e infinito (non esiste una biiezione \(X\to \{1,...,n\}\)) si può dimostrare solo assumendo l'assioma della scelta.
Sostanzialmente il motivo è che la dimostrazione che $X$ contiene una copia di $NN$ si fa "per induzione". $X$ è infinito, quindi non è vuoto; allora contiene un elemento; lo scelgo. Questo elemento è l'immagine di $0$. Dato \(\{x_1,...,x_n\}\) posso sempre trovare un elemento nel suo complementare in $X$, e questo fa procedere l'induzione. Formalizza questo argomento.
Chissà perché mi ero autoconvinto che l'elemento rappresentante di ognuno degli insiemi della famiglia dovesse essere diverso per ogni insieme della famiglia, scusatemi.
Dunque, io ho cercato prima di formalizzare con l'induzione il mio tentativo in [1], non riuscendoci.
Quello che riesco a fare è invece questo (non sono sicuro sia esattamente ciò che mi chiedi, ma lo posto intanto):
Come notazione indico \(\displaystyle E_n=\{1,2,...,n\} \).
Sia $X$ un insieme infinito.
Dimostro per induzione che per ogni n naturale maggiore di 1 esiste un sottoinsieme di $X$, $X_n$ in mappa biunivoca con $E_n$ e della forma $X_n=X_{n-1} \bigcup \{x_n\}$, con un opportuno $x_n \in X \setminus X_{n-1}$.
L'induzione parte da n=2, per cui prima di cominciare noto che $X$ è non vuoto e quindi posso scegliere $\{x_1\} \subset X$ e definire \(\displaystyle X_1=\{x_1\} \).
$n=2$) $X \setminus X_1 \ne \emptyset$ (altrimenti si avrebbe $X$ in bijezione con $E_1$, assurdo) $\Rightarrow$ posso scegliere $\{ x_{2} \} \subset X \setminus X_1 \Rightarrow X_{2}=X_1 \bigcup \{x_{2}\}$ è banalmente in bijezione con \(\displaystyle E_{2} \).
$n\rightarrow n+1$) Sia $X_n =X_{n-1} \bigcup \{x_n\}$, per un opportuno \(\displaystyle x_n \in X \setminus X_{n-1} \) in bijezione con $E_n$. Si ha che $X \setminus X_n \ne \emptyset$ perché se così non fosse si avrebbe $X$ in bijezione con $X_n$ in bijezione con $E_n$ (finito) $\Rightarrow X$ finito $\Rightarrow$ assurdo. Sia allora, per l'assioma di scelta, $\{ x_{n+1} \} \subset X \setminus X_n$, allora $X_{n+1}=X_n \bigcup \{x_{n+1}\}$ è banalmente in bijezione con \(\displaystyle E_{n+1} \).
Ora non resta che costruire la mappa biunivoca tra $\mathbb{N}$ e un sottoinsieme di elementi di $X$, come segue:
$f(1)=X_1$
$f(2)=X_2 \setminus X_1$
...
$f(n)=X_n \setminus X_{n-1}$
C'è un piccolo problema formale qui: la funzione è biunivoca ma il codominio non è $\{x_1,...,x_n,...\}$ bensì \(\displaystyle \{\{x_1\},...,\{x_n\},...\} \), quindi dovrei comporre \(\displaystyle f \) con una funzione \(\displaystyle \(\displaystyle g \) \) definita così: \(\displaystyle g=\{(\{x_n\}, x_n), n \in \mathbb{N}\} \), ma vabbè...
Ogni volta che si legge il grassetto vuol dire che ho usato l'assioma di scelta, è corretto?
Non mi piace moltissimo ma non viene in mente altro per ora.
Dunque, io ho cercato prima di formalizzare con l'induzione il mio tentativo in [1], non riuscendoci.
Quello che riesco a fare è invece questo (non sono sicuro sia esattamente ciò che mi chiedi, ma lo posto intanto):
Come notazione indico \(\displaystyle E_n=\{1,2,...,n\} \).
Sia $X$ un insieme infinito.
Dimostro per induzione che per ogni n naturale maggiore di 1 esiste un sottoinsieme di $X$, $X_n$ in mappa biunivoca con $E_n$ e della forma $X_n=X_{n-1} \bigcup \{x_n\}$, con un opportuno $x_n \in X \setminus X_{n-1}$.
L'induzione parte da n=2, per cui prima di cominciare noto che $X$ è non vuoto e quindi posso scegliere $\{x_1\} \subset X$ e definire \(\displaystyle X_1=\{x_1\} \).
$n=2$) $X \setminus X_1 \ne \emptyset$ (altrimenti si avrebbe $X$ in bijezione con $E_1$, assurdo) $\Rightarrow$ posso scegliere $\{ x_{2} \} \subset X \setminus X_1 \Rightarrow X_{2}=X_1 \bigcup \{x_{2}\}$ è banalmente in bijezione con \(\displaystyle E_{2} \).
$n\rightarrow n+1$) Sia $X_n =X_{n-1} \bigcup \{x_n\}$, per un opportuno \(\displaystyle x_n \in X \setminus X_{n-1} \) in bijezione con $E_n$. Si ha che $X \setminus X_n \ne \emptyset$ perché se così non fosse si avrebbe $X$ in bijezione con $X_n$ in bijezione con $E_n$ (finito) $\Rightarrow X$ finito $\Rightarrow$ assurdo. Sia allora, per l'assioma di scelta, $\{ x_{n+1} \} \subset X \setminus X_n$, allora $X_{n+1}=X_n \bigcup \{x_{n+1}\}$ è banalmente in bijezione con \(\displaystyle E_{n+1} \).
Ora non resta che costruire la mappa biunivoca tra $\mathbb{N}$ e un sottoinsieme di elementi di $X$, come segue:
$f(1)=X_1$
$f(2)=X_2 \setminus X_1$
...
$f(n)=X_n \setminus X_{n-1}$
C'è un piccolo problema formale qui: la funzione è biunivoca ma il codominio non è $\{x_1,...,x_n,...\}$ bensì \(\displaystyle \{\{x_1\},...,\{x_n\},...\} \), quindi dovrei comporre \(\displaystyle f \) con una funzione \(\displaystyle \(\displaystyle g \) \) definita così: \(\displaystyle g=\{(\{x_n\}, x_n), n \in \mathbb{N}\} \), ma vabbè...
Ogni volta che si legge il grassetto vuol dire che ho usato l'assioma di scelta, è corretto?
Non mi piace moltissimo ma non viene in mente altro per ora.
Forse sono riuscito a farla meglio.
Domani la ricontrollo e la posto, ora vado a dormire che non connetto più
Domani la ricontrollo e la posto, ora vado a dormire che non connetto più
Dunque, come dicevo, credo di essere riuscito a farla più pulita.
Innanzitutto specifico un pò di notazione abbreviata che utilizzo per non rendere pesante il discorso:
$E_n={1,2,...,n}$
$A \leftrightarrow B$ := $A$ in bijezione con $B$.
Sia $X$ un insieme infinito.
$X$ infinito $\Rightarrow X$ non vuoto $\Rightarrow$ scelgo $\{x_1\} \subset X$.
Dimostro per induzione che \(\displaystyle \forall n \in \mathbb{N} \setminus \{1\} \exists \{x_n\} \subset X : \{x_n\} \nsubseteq \bigcup_{k=1}^{n-1}\{x_k\} \).
$n=2$) $X \setminus \{x_1\}$ non vuoto (altrimenti $X \leftrightarrow \{x_1\} \leftrightarrow E_1$, assurdo) $\Rightarrow$ scelgo \(\displaystyle \{x_2\} \subset X \setminus \{x_1\} \Rightarrow \{x_2\} \nsubseteq \{x_1\} \);
$n \rightarrow n+1$) \(\displaystyle \exists \{x_n\} \subset X:\{x_n\} \nsubseteq \bigcup_{k=1}^{n-1}\{x_k\} \Rightarrow X \setminus \bigcup_{k=1}^{n-1}\{x_k\} \) non vuoto (altrimenti $X \leftrightarrow \bigcup_{k=1}^{n-1}\{x_k\} \leftrightarrow E_{n-1}$, assurdo) $\Rightarrow$ scelgo \(\displaystyle \{x_{n+1}\} \subset X \setminus \bigcup_{k=1}^{n}\{x_k\} \Rightarrow \{x_{n+1}\} \nsubseteq \bigcup_{k=1}^{n}\{x_k\} \).
Dunque sia \(\displaystyle f: \mathbb{N} \rightarrow \bigcup_{k \in \mathbb{N}} \{x_k\}\) tale che \(\displaystyle f(n)=x_n \Rightarrow f\) biunivoca (si dimostra in un attimo).
Va meglio no?
Di nuovo, ogni volta che c'è il grassetto ho usato l'assioma di scelta, è giusto?
Nota: Ogni volta che ho utilizzato l'assioma di scelta, ho scritto come risultato ottenuto un singoletto contenente un elemento di $X$, e non direttamente un elemento di $X$, perché è ciò che l'assioma di scelta dice. Ho adattato poi il resto della dimostrazione a questa cosa, mi sembra fili.
Innanzitutto specifico un pò di notazione abbreviata che utilizzo per non rendere pesante il discorso:
$E_n={1,2,...,n}$
$A \leftrightarrow B$ := $A$ in bijezione con $B$.
Sia $X$ un insieme infinito.
$X$ infinito $\Rightarrow X$ non vuoto $\Rightarrow$ scelgo $\{x_1\} \subset X$.
Dimostro per induzione che \(\displaystyle \forall n \in \mathbb{N} \setminus \{1\} \exists \{x_n\} \subset X : \{x_n\} \nsubseteq \bigcup_{k=1}^{n-1}\{x_k\} \).
$n=2$) $X \setminus \{x_1\}$ non vuoto (altrimenti $X \leftrightarrow \{x_1\} \leftrightarrow E_1$, assurdo) $\Rightarrow$ scelgo \(\displaystyle \{x_2\} \subset X \setminus \{x_1\} \Rightarrow \{x_2\} \nsubseteq \{x_1\} \);
$n \rightarrow n+1$) \(\displaystyle \exists \{x_n\} \subset X:\{x_n\} \nsubseteq \bigcup_{k=1}^{n-1}\{x_k\} \Rightarrow X \setminus \bigcup_{k=1}^{n-1}\{x_k\} \) non vuoto (altrimenti $X \leftrightarrow \bigcup_{k=1}^{n-1}\{x_k\} \leftrightarrow E_{n-1}$, assurdo) $\Rightarrow$ scelgo \(\displaystyle \{x_{n+1}\} \subset X \setminus \bigcup_{k=1}^{n}\{x_k\} \Rightarrow \{x_{n+1}\} \nsubseteq \bigcup_{k=1}^{n}\{x_k\} \).
Dunque sia \(\displaystyle f: \mathbb{N} \rightarrow \bigcup_{k \in \mathbb{N}} \{x_k\}\) tale che \(\displaystyle f(n)=x_n \Rightarrow f\) biunivoca (si dimostra in un attimo).
Va meglio no?
Di nuovo, ogni volta che c'è il grassetto ho usato l'assioma di scelta, è giusto?
Nota: Ogni volta che ho utilizzato l'assioma di scelta, ho scritto come risultato ottenuto un singoletto contenente un elemento di $X$, e non direttamente un elemento di $X$, perché è ciò che l'assioma di scelta dice. Ho adattato poi il resto della dimostrazione a questa cosa, mi sembra fili.
Secondo me non è quando scegli gli elementi in quei modi che usi l'assioma della scelta perché sai che da un insieme non vuoto un elemento lo puoi sempre scegliere.
"otta96":
Secondo me non è quando scegli gli elementi in quei modi che usi l'assioma della scelta perché sai che da un insieme non vuoto un elemento lo puoi sempre scegliere.
...che è precisamente (una forma del)l'assioma della scelta.
Secondo te non ci sono errori nella mia dimostrazione, killing_buddha?
Grazie per la pazienza che avete.
Grazie per la pazienza che avete.
"otta96":
Secondo me non è quando scegli gli elementi in quei modi che usi l'assioma della scelta perché sai che da un insieme non vuoto un elemento lo puoi sempre scegliere.
Io penso che bisogna partire da cosa significa scegliere un elemento di un insieme.
Perché il fatto che un insieme $X$ sia non vuoto implica che esiste un $x \in X$. Punto. Questo non significa aver scelto un elemento di quell'insieme, ma di star chiamando un generico elemento di quell'insieme con il nome $x$.
In una eventuale dimostrazione che usa questa cosa, da questo punto in poi tutto il discorso varrà per ogni elemento di $X$. In sostanza, non ho scelto un bel niente.
Da cui: cosa vuol dire effettivamente scegliere? Direi che vuol dire trovare un insieme $C$ tale che la sua intersezione con $X$ dia un singoletto. Nell'ultima dimostrazione che ho fatto questo insieme $C$ l'ho trovato? No.
Ho fatto ricorso all'assioma di scelta? Non lo so, perché non ho capito bene se il discorso che ho portato avanti ha la stessa valenza logica anche senza scegliere un elemento, ma soltanto considerandone uno generico, forse si (quindi forse l'assioma di scelta non serve nel mio caso specifico)
Si può scegliere un elemento da un insieme qualsiasi non vuoto $X$ senza ricorrere all'assioma di scelta? (Ovvero quando la famiglia di insiemi di cui parla l'assioma è finita?) Questo vorrei capire. Se si vuole farlo senza AC, allora o si usa l'assioma di separazione (e non va bene se non si conoscono proprietà particolari degli elementi di $X$) o si usa l'assioma di rimpiazzamento (e direi che bisogna concentrarsi su questo se si vuole uscirne almeno nel caso di famiglie finite).
Quello che dicevo io l'ho trovato anche su delle dispense abbastanza ben fatte ovvero quelle di teoria degli insiemi del Prof. Berarducci, dove ad un certo punto (pag. 31) si legge
In rosso una aggiunta mia, comunque mi sembra abbastanza chiaro che ciò che sta dicendo è che l'assioma della scelta serve a dimostrare che certi insiemi sono non vuoti (gli insiemi delle funzioni di scelta), una volta fatto questo possiamo prenderne un elemento a piacere (sceglierlo) per il fatto che è non vuoto.
Per lo meno io l'ho capita così se ho frainteso correggetemi.
L’assioma di scelta asserisce che ne esiste almeno una (di funzioni di scelta), e sapendo che esiste sta poi a noi “sceglierne” una, dove questo secondo passaggio può essere fatto in base alle leggi della logica.
In rosso una aggiunta mia, comunque mi sembra abbastanza chiaro che ciò che sta dicendo è che l'assioma della scelta serve a dimostrare che certi insiemi sono non vuoti (gli insiemi delle funzioni di scelta), una volta fatto questo possiamo prenderne un elemento a piacere (sceglierlo) per il fatto che è non vuoto.
Per lo meno io l'ho capita così se ho frainteso correggetemi.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo