Ogni sottoinsieme di un insieme numerabile è al più numerabile.

[marco2132k]

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?

[caulacau]

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?

[marco2132k]

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).

in effetti ti serve countable choice per dimostrare che un insieme numerabile ha un sottoinsieme numerabile.

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.

[marco2132k]

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๠controimmagine secondo \( n_{{-}} \). Sia infatti \( k \) il più grande intero tale che \( n_k<n \). Dico che \( n_{k+1}=n \). Si ha
\[
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<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.

---

Note

1. 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 \), con \( n\in\mathbb{N} \) fissato, la \( \mathscr{P} \) mappa in \( \mathrm{vero} \), allora lo farà anche \( \mathscr{P}(n) \). Questo è quello che conosco come principio di induzione completa. ↑

[caulacau]

Ma cosa non ti va bene della dimostrazione one-liner che ti ho dato io?

[otta96]

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.

[marco2132k]

@caulacau Mi dà fastidio lasciare incompiuta quella che ho cominciato io. (Già non so nulla di matematica: almeno imparo qualcosa).

@otta96

cioè \( \exists k\leq x_{{-}}^{−1}(a) \) tale che \( x_{n_k}=a \).

? Cosa vuol dire che considero \( a\in E \) nei primi \( x_{{-}}^{-1}(a) \) passi? È proprio questo (quello in quote) che non comprendo.

[otta96]

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<f(m)$, ma allora per definizione di $f$, $EE0<=k<m$ tale che $f(k)=m$ e abbiamo la tesi.
Spero che ora sia più chiaro, comunque se ti sembra di non capire, prova a sforzarti di capire ancora e ancora, perché tanto tutto quello di cui hai bisogno è in questo post