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
La scelta non serve a generare gli elementi, ma a invocare la funzione che assume in \(n\) il valore \(x_n\). Se \(X\) è infinito, esiste una funzione suriettiva \(p : X\to \mathbb N\). E certo, "sopra" ogni elemento di \(\mathbb N\) esiste una fibra \(p^\leftarrow(n) \neq\varnothing\), ma come fai a sapere che questo definisce una funzione \(\mathbb N \to \coprod_{n\in \mathbb N}p^\leftarrow(n)\) senza dire che stai "intersecando \(\coprod_{n\in \mathbb N}p^\leftarrow(n)\) in esattamente un unico elemento, per ogni \(n\in\mathbb N\)"?
Nota che questa costruzione, chiaramente, usa un fottio di altri assiomi, tipo l'assioma di comprensione (che è quello che ti permette di dire che l'insieme che hai determinato prendendo un taglio trasversale di \(\coprod_{n\in \mathbb N}p^\leftarrow(n)\) è effettivamente tale).
Nota che questa costruzione, chiaramente, usa un fottio di altri assiomi, tipo l'assioma di comprensione (che è quello che ti permette di dire che l'insieme che hai determinato prendendo un taglio trasversale di \(\coprod_{n\in \mathbb N}p^\leftarrow(n)\) è effettivamente tale).
Ma infatti penso che sia inevitabile usare l'assioma della scelta (sul fatto he sto usando molti altri assiomi non ci sono dubbi), sto solo dicendo che secondo me non si sta usando l'assioma della scelta NEL MOMENTO IN CUI si considera $x_n\inp^(<-)(n)$ perché qualcosa in questo insieme posso prenderlo visto che non è vuoto, mentre invece lo si sta usando nel passaggio "allora ${x_n|n\inNN}$ è un insieme".
"otta96":
lo si sta usando nel passaggio "allora ${x_n|n\inNN}$ è un insieme".
Ho riflettuto un bel pò su questa cosa e alla fine, dopo qualche ricerca extra, ho capito come deve funzionare la questione.
Insomma, il problema sta nel mio ultimo passaggio:
"Ianero":
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).
Con l'induzione io avevo dimostrato che:
\( \displaystyle \forall n \in \mathbb{N} \exists x_n \in X : x_n \notin \bigcup_{k=1}^{n-1}\{x_k\} \)
cioè vuol dire che per ogni n naturale (quindi finito) posso costruire un insieme $\{x_1,...,x_n\} \subset X$ e di conseguenza una funzione biunivoca tra un sottoinsieme di $X$ e $E_n=\{1,2,...,n\}$. Non mi consente di estendere la cosa a $\mathbb{N}$.
Per farlo c'è bisogno dell'assioma di scelta, magari in una sua forma equivalente più utile per questo caso.
Ho studiato un pò e sono arrivato alla dimostrazione che l'assioma di scelta in questa forma:
Per ogni famiglia $F$ di insiemi $X$ non vuoti a coppie disgiunti, esiste un insieme $C$ di scelta.
è equivalente a quest'altra forma:
Per ogni famiglia $F$ di insiemi $X$ non vuoti, esiste una funzione $g$ di scelta.
Dicendo di scelta significa che $C$ è tale che $C \bigcap X$ consiste in un solo elemento per ogni $X$ della famiglia, mentre nella seconda forma vuol dire che la funzione $g:F \rightarrow \bigcup F$ è tale che per ogni insieme $X$ della famiglia si abbia $g(X) \in X$.
A questo punto la dimostrazione che volevo fare si può formalizzare in questo modo...
Sia $X$ un insieme infinito, allora $\mathcal{P}(X) \setminus \emptyset$ (insieme delle parti) è una famiglia infinita di insiemi.
Dunque per l'assioma di scelta esiste una funzione di scelta $g:\mathcal{P}(X) \rightarrow X$.
Sia allora $f:\mathbb{N} \rightarrow X$ tale che:
\(\displaystyle f(n)=\left\{\begin{matrix}
g(X)\;\;\text{se}\;\; n=0\\
g(X \setminus \left \{ f(0),f(1),...,f(n-1) \right \})\;\;\text{se}\;\; n\neq 0
\end{matrix}\right. \)
E' un attimo vedere che $f$ è iniettiva, allora restringendo il codominio alla sua immagine si ha: $f:\mathbb{N} \rightarrow \text{Im}(f) \subset X$ biunivoca.
"Ianero":
per ogni n naturale (quindi finito) posso costruire un insieme $\{x_1,...,x_n\} \subset X$ e di conseguenza una funzione biunivoca tra un sottoinsieme di $X$ e $E_n=\{1,2,...,n\}$. Non mi consente di estendere la cosa a $\mathbb{N}$.
Per farlo c'è bisogno dell'assioma di scelta, magari in una sua forma equivalente più utile per questo caso.
Eh no, se ricordi ci eravamo detti che non serve AC per trovare gli elementi $x_n$, quanto piuttosto per invocare la funzione che assume il valore $x_n$ in $n$. Per essere piu formali, \(\{x_n\mid n\in \mathbb N\}\) e' un insieme solo in conseguenza dell'esistenza di una funzione $f \subseteq NN\times X$, la cui esistenza e' garantita da (un pacco di altri assiomi e) da AC.
Sì, fino a qui l'assioma di scelta non serve:
Entra in gioco perchè la famiglia $F=\bigcup_{n \in \mathbb{N}} p^\leftarrow(n)$ contiene insiemi che contengono in generale più di un elemento (la funzione $p$ potrebbe non essere iniettiva) e inoltre non si conoscono particolari proprietà di tali elementi che ne consentirebbero una estrazione mirata. Dunque l'assioma di scelta, in questa costruzione, dovrebbe intervenire qui ($F$ è composta da insiemi a coppie disgiunti) per selezionare, con un insieme di scelta $C$, un elemento da ogni fibra $p^\leftarrow(n)$.
Dico bene?
Inoltre in quanto a questo:
vorrei capire meglio quali sono tutti questi assiomi necessari.
A me sembra che si possa dimostrare facilmente per assurdo che la funzione che prima abbiamo chiamato \( p : X\to \mathbb N \) esista solo come conseguenza che $X$ è infinito. Se così non fosse infatti allora si avrebbe $X \leftrightarrow E_n$ (bijezione) che è assurdo. Cosa mi sono perso?
"killing_buddha":
Se \( X \) è infinito, esiste una funzione suriettiva \( p : X\to \mathbb N \). E certo, "sopra" ogni elemento di \( \mathbb N \) esiste una fibra \( p^\leftarrow(n) \neq\varnothing \)
Entra in gioco perchè la famiglia $F=\bigcup_{n \in \mathbb{N}} p^\leftarrow(n)$ contiene insiemi che contengono in generale più di un elemento (la funzione $p$ potrebbe non essere iniettiva) e inoltre non si conoscono particolari proprietà di tali elementi che ne consentirebbero una estrazione mirata. Dunque l'assioma di scelta, in questa costruzione, dovrebbe intervenire qui ($F$ è composta da insiemi a coppie disgiunti) per selezionare, con un insieme di scelta $C$, un elemento da ogni fibra $p^\leftarrow(n)$.
Dico bene?
Inoltre in quanto a questo:
"killing_buddha":
Eh no, se ricordi ci eravamo detti che non serve AC per trovare gli elementi $x_n$, quanto piuttosto per invocare la funzione che assume il valore $x_n$ in $n$. Per essere piu formali, \( \{x_n\mid n\in \mathbb N\} \) e' un insieme solo in conseguenza dell'esistenza di una funzione $ f \subseteq NN\times X $, la cui esistenza e' garantita da (un pacco di altri assiomi e) da AC.
vorrei capire meglio quali sono tutti questi assiomi necessari.
A me sembra che si possa dimostrare facilmente per assurdo che la funzione che prima abbiamo chiamato \( p : X\to \mathbb N \) esista solo come conseguenza che $X$ è infinito. Se così non fosse infatti allora si avrebbe $X \leftrightarrow E_n$ (bijezione) che è assurdo. Cosa mi sono perso?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo