Ogni sottoinsieme di un insieme numerabile è al più numerabile.
Ciao. Ci sono tremila post sui vari forum/MSE/ph che riguardano questa dimostrazione, quindi questo mio intervento è un po' inutile. Voglio solo schiarirmi le idee cercando di scrivere qualcosa di comprensibile qui.
Sia \( A \) infinito numerabile. Allora ogni suo sottoinsieme \( E \) è o finito o infinito numerabile.
Sia \( E\subset A \) infinito. Sia \( x_{{-}}\colon\mathbb{N}\to A \) biiettiva. Definisco una successione \( n_{{-}} \) di naturali come segue. Sia \( n_1 \) il minimo dell'immagine inversa \( x_{{-}}^{-1}(E) \) (tale numero esiste, per il WOP); ammesso di aver definito \( n_{k-1} \), per un \( k\in\mathbb{N} \), pongo \( n_k \) come il primo naturale successivo a \( k-1 \), tale che \( x_{n_k} \) stia in \( E \). L'insieme \( T \) dei naturali per cui \( n_{{-}} \) è definita coincide con \( \mathbb{N} \), per il principio di induzione (vero? \( 0 \) gli appartiene, e se la funzione è definita per \( k \), lo è anche per \( k+1 \). C'è una motivo particolare, e non puramente estetico, per usare l'induzione completa nella definizione?). Ora, la successione \( \mathbb{N}\to E \) data da \( x_{n_{{-}}} \) è banalmente iniettiva. Perché è anche suriettiva?
Sia \( A \) infinito numerabile. Allora ogni suo sottoinsieme \( E \) è o finito o infinito numerabile.
Sia \( E\subset A \) infinito. Sia \( x_{{-}}\colon\mathbb{N}\to A \) biiettiva. Definisco una successione \( n_{{-}} \) di naturali come segue. Sia \( n_1 \) il minimo dell'immagine inversa \( x_{{-}}^{-1}(E) \) (tale numero esiste, per il WOP); ammesso di aver definito \( n_{k-1} \), per un \( k\in\mathbb{N} \), pongo \( n_k \) come il primo naturale successivo a \( k-1 \), tale che \( x_{n_k} \) stia in \( E \). L'insieme \( T \) dei naturali per cui \( n_{{-}} \) è definita coincide con \( \mathbb{N} \), per il principio di induzione (vero? \( 0 \) gli appartiene, e se la funzione è definita per \( k \), lo è anche per \( k+1 \). C'è una motivo particolare, e non puramente estetico, per usare l'induzione completa nella definizione?). Ora, la successione \( \mathbb{N}\to E \) data da \( x_{n_{{-}}} \) è banalmente iniettiva. Perché è anche suriettiva?
Risposte
Vuoi l'assioma della scelta? Se sì, c'è una funzione iniettiva da $E$ in $A$; ora ci sono due casi.
1. Non c'è una funzione iniettiva da $A$ in $E$; allora, \(\#E \lneq \#A\), uguaglianza stretta, quindi $E$ è finito.
2. C'è una funzione iniettiva da $A$ in $E$; per CSB allora $\#A = \#E = \aleph_0$. []
Se non vuoi l'assioma della scelta, nemmeno la dimostrazione con le successioni va bene; in effetti ti serve countable choice per dimostrare che un insieme numerabile ha un sottoinsieme numerabile. Quindi tanto vale farsi andare bene la dimostrazione che ti ho detto sopra, no?
1. Non c'è una funzione iniettiva da $A$ in $E$; allora, \(\#E \lneq \#A\), uguaglianza stretta, quindi $E$ è finito.
2. C'è una funzione iniettiva da $A$ in $E$; per CSB allora $\#A = \#E = \aleph_0$. []
Se non vuoi l'assioma della scelta, nemmeno la dimostrazione con le successioni va bene; in effetti ti serve countable choice per dimostrare che un insieme numerabile ha un sottoinsieme numerabile. Quindi tanto vale farsi andare bene la dimostrazione che ti ho detto sopra, no?
Grazie per la risposta. Sì, con Cantor è più semplice in effetti, però mi piacerebbe anche capire perché \( x_{n_{{-}}} \) è suriettiva. (Lo è, però passato dato per ovvio dove ho guardato).
"caulacau":Sto cercando di dimostrare che se \( E \) è un sottoinsieme infinito di \( A \) numerabile, allora \( E \) è anche lui numerabile. In effetti ci ho messo un attimo prima di accorgermi della roba in quote.
in effetti ti serve countable choice per dimostrare che un insieme numerabile ha un sottoinsieme numerabile.
Fatto 
Dimostrazione. Sia \( A \) infinito numerabile, \( E\subset A \) infinito. Si dispongano gli elementi di \( A \) in una successione \( \left\{x_n\right\}_{n\in\mathbb{N}} \), e sia \( n_{{-}} \) una mappa \( \mathbb{N}\to{x_{{-}}^{-1}(E)} \) definita come segue:
\[
n_{{-}}\colon
\begin{cases}
1\mapsto\min{x_{{-}}^{-1}(E)}\\
k\mapsto\min\left({x_{{-}}^{-1}(E)}\setminus\left\{n_j:j\leqq k-1\right\}\right)
\end{cases}
\] Una funzione \( n_{{-}} \) così pensata è suriettiva. Si supponga che ogni naturale \( k \), minore di un naturale fissato \( n \), ammetta controimmagine secondo \( n_{{-}} \) se appartiene a \( x_{{-}}^{-1}(E) \). Allora anche \( n \), se appartiene a \( x_{{-}}^{-1}(E) \), ammetterà[nota]Come scrissi in un altro post, l'idea è di dimostrare che la funzione \( \mathscr{P}\colon\mathbb{N}\to\left\{\mathrm{vero},\mathrm{falso}\right\} \) che \[ \mathscr{P}\colon n\mapsto\begin{cases}\mathrm{vero}&\text{se $ n\in{x_{{-}}^{-1}(E)} $ implica l'esistenza di un $ k\in\mathbb{N} $ tale che $ n_k=n $}\\\mathrm{falso}&\text{altrimenti}\end{cases} \] mappa sempre \( \mathrm{vero} \), dimostrando che se per ogni \( kprincipio di induzione completa.[/nota] controimmagine secondo \( n_{{-}} \). Sia infatti \( k \) il più grande intero tale che \( n_k
n_{k+1}=\max\left({x_{{-}}^{-1}(E)}\setminus\left\{n_j:j\leqq k-1\right\}\right)
\] E una conclusione viene osservando che tutti gli elementi minori di \( n \) sono contenuti in \( \left\{n_j:j\leqq k-1\right\} \): se \( \lambda \) è un elemento del codominio di \( n_{{-}} \), minore di \( n \), allora \( \lambda=n_{k^{'}} \), per un \( k^{'}\leqq k \), dato che \( k \) è il più grande intero tal che \( n_k
Si consideri la funzione \( k\mapsto x_{n_k} \): essa è iniettiva e suriettiva, perché composizione di una restrizione di una funzione iniettiva (i.e., \( x_{{-}}^{-1} \)) con un altra funzione iniettiva, ed è suriettiva più o meno per le stesse ragioni. Allora \( \mathbb{N}\cong E \). \( \square \)
Come va? (Considerando che la struttura della dimostrazione viene menzionata ovunque, e che il "passaggetto" che è la suriettività di \( n_{{-}} \) viene mostrato come la cosa più banale del mondo, mi domando se non mi stia perdendo qualcosa).
p.s. Si può dare banalmente una relazione d'ordine su \( A \) come \( x_i\leqq y_i \) se e solo se \( i\leqq j \), per ogni \( a=x_i \) e \( b=x_j \) in \( A \). Devo pensarci un attimo quando ho voglia, e vedere se questa roba porta a qualcosa. Se volete buttarmi un hint, volentieri.
Dimostrazione. Sia \( A \) infinito numerabile, \( E\subset A \) infinito. Si dispongano gli elementi di \( A \) in una successione \( \left\{x_n\right\}_{n\in\mathbb{N}} \), e sia \( n_{{-}} \) una mappa \( \mathbb{N}\to{x_{{-}}^{-1}(E)} \) definita come segue:
\[
n_{{-}}\colon
\begin{cases}
1\mapsto\min{x_{{-}}^{-1}(E)}\\
k\mapsto\min\left({x_{{-}}^{-1}(E)}\setminus\left\{n_j:j\leqq k-1\right\}\right)
\end{cases}
\] Una funzione \( n_{{-}} \) così pensata è suriettiva. Si supponga che ogni naturale \( k \), minore di un naturale fissato \( n \), ammetta controimmagine secondo \( n_{{-}} \) se appartiene a \( x_{{-}}^{-1}(E) \). Allora anche \( n \), se appartiene a \( x_{{-}}^{-1}(E) \), ammetterà[nota]Come scrissi in un altro post, l'idea è di dimostrare che la funzione \( \mathscr{P}\colon\mathbb{N}\to\left\{\mathrm{vero},\mathrm{falso}\right\} \) che \[ \mathscr{P}\colon n\mapsto\begin{cases}\mathrm{vero}&\text{se $ n\in{x_{{-}}^{-1}(E)} $ implica l'esistenza di un $ k\in\mathbb{N} $ tale che $ n_k=n $}\\\mathrm{falso}&\text{altrimenti}\end{cases} \] mappa sempre \( \mathrm{vero} \), dimostrando che se per ogni \( k
n_{k+1}=\max\left({x_{{-}}^{-1}(E)}\setminus\left\{n_j:j\leqq k-1\right\}\right)
\] E una conclusione viene osservando che tutti gli elementi minori di \( n \) sono contenuti in \( \left\{n_j:j\leqq k-1\right\} \): se \( \lambda \) è un elemento del codominio di \( n_{{-}} \), minore di \( n \), allora \( \lambda=n_{k^{'}} \), per un \( k^{'}\leqq k \), dato che \( k \) è il più grande intero tal che \( n_k
Si consideri la funzione \( k\mapsto x_{n_k} \): essa è iniettiva e suriettiva, perché composizione di una restrizione di una funzione iniettiva (i.e., \( x_{{-}}^{-1} \)) con un altra funzione iniettiva, ed è suriettiva più o meno per le stesse ragioni. Allora \( \mathbb{N}\cong E \). \( \square \)
Come va? (Considerando che la struttura della dimostrazione viene menzionata ovunque, e che il "passaggetto" che è la suriettività di \( n_{{-}} \) viene mostrato come la cosa più banale del mondo, mi domando se non mi stia perdendo qualcosa).
p.s. Si può dare banalmente una relazione d'ordine su \( A \) come \( x_i\leqq y_i \) se e solo se \( i\leqq j \), per ogni \( a=x_i \) e \( b=x_j \) in \( A \). Devo pensarci un attimo quando ho voglia, e vedere se questa roba porta a qualcosa. Se volete buttarmi un hint, volentieri.
Ma cosa non ti va bene della dimostrazione one-liner che ti ho dato io?
"marco2132k":
Sia \( E\subset A \) infinito. Sia \( x_{{-}}\colon\mathbb{N}\to A \) biiettiva. Definisco una successione \( n_{{-}} \) di naturali come segue. Sia \( n_1 \) il minimo dell'immagine inversa \( x_{{-}}^{-1}(E) \) (tale numero esiste, per il WOP); ammesso di aver definito \( n_{k-1} \), per un \( k\in\mathbb{N} \), pongo \( n_k \) come il primo naturale successivo a \( k-1 \), tale che \( x_{n_k} \) stia in \( E \). L'insieme \( T \) dei naturali per cui \( n_{{-}} \) è definita coincide con \( \mathbb{N} \), per il principio di induzione (vero? \( 0 \) gli appartiene, e se la funzione è definita per \( k \), lo è anche per \( k+1 \). C'è una motivo particolare, e non puramente estetico, per usare l'induzione completa nella definizione?). Ora, la successione \( \mathbb{N}\to E \) data da \( x_{n_{{-}}} \) è banalmente iniettiva. Perché è anche suriettiva?
Non ho letto l'ultimo tuo post ma la funzione è suriettiva perché un elemento $a$ di $E$ lo consideri di sicuro nei primi $x_(-)^(-1)(a)$ passi, cioè $EEk<=x_(-)^(-1)(a)$ tale che $x_(n_k)=a$. Se ci pensi un po' te ne accorgi.
@caulacau Mi dà fastidio lasciare incompiuta quella che ho cominciato io. (Già non so nulla di matematica: almeno imparo qualcosa).
@otta96
@otta96
"otta96":? Cosa vuol dire che considero \( a\in E \) nei primi \( x_{{-}}^{-1}(a) \) passi? È proprio questo (quello in quote) che non comprendo.
cioè \( \exists k\leq x_{{-}}^{−1}(a) \) tale che \( x_{n_k}=a \).
Facciamo che $A=NN$ ok? Tanto poi è uguale.
Quindi abbiamo $E\subseteq A$ infinito, si definisce una funzione $f:NN->E$ per ricorsione: $f(0)=\min E$, $f(n)=\min E\setminus {f(1),...,f(n-1)}$,cioè quello che stiamo facendo non è altro che contare e accorgerci quando il numero che abbiamo in mente sta in $E$ e scartare tutti gli altri.
Quindi il primo numero che troviamo è almeno $0$, necessariamente, mentre il secondo sarà almeno $1$ e così via si ottiene che $f(n)$ non può essere più piccolo di $n$, cioè $f(n)>=n$.
Ora, se consideri un elemento di $E$, chiamiamolo $m$, consideriamo $f(m)$. Cosa sappiamo dire?
Da quello che abbiamo già visto $f(m)>=m$, ma allora vuol dire che per come è definita la funzione (cioè che quando si considerano gli elementi di $E$ lo si fa in ordine, non si lascia nessuno indietro) ci sono due possibilità: o $f(m)=m$ e allora abbiamo finito, oppure $m
Quindi abbiamo $E\subseteq A$ infinito, si definisce una funzione $f:NN->E$ per ricorsione: $f(0)=\min E$, $f(n)=\min E\setminus {f(1),...,f(n-1)}$,cioè quello che stiamo facendo non è altro che contare e accorgerci quando il numero che abbiamo in mente sta in $E$ e scartare tutti gli altri.
Quindi il primo numero che troviamo è almeno $0$, necessariamente, mentre il secondo sarà almeno $1$ e così via si ottiene che $f(n)$ non può essere più piccolo di $n$, cioè $f(n)>=n$.
Ora, se consideri un elemento di $E$, chiamiamolo $m$, consideriamo $f(m)$. Cosa sappiamo dire?
Da quello che abbiamo già visto $f(m)>=m$, ma allora vuol dire che per come è definita la funzione (cioè che quando si considerano gli elementi di $E$ lo si fa in ordine, non si lascia nessuno indietro) ci sono due possibilità: o $f(m)=m$ e allora abbiamo finito, oppure $m
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo