L'insieme dei sottoinsiemi finiti di \( \mathbb{N} \) è numerabile
I sottoinsiemi finiti di \( \mathbb{N} \) sono numerabili o non numberabili?
Allora sebbene io l'abbia risolto in modo diverso avrei una curiosità, se fosse possibile procedere in modo distinto.
Nominiamo \( A \) l'insieme descritto nell'enunciato, io ho trovato la seguente mappa iniettiva \[ f : A \hookrightarrow \mathbb{N} \]
\[a\in A \mapsto f(a)= \prod\limits_{j \in a} p_j \]
Dove \( p_j \) è il \(j-\)esimo numero primo.
La mia domanda è un'altra allora, prima di pensare a questa cosa, avevo pensato che \( A \) contiene tutti gli insiemi di cardinalità \( 1\), chiamiamo \( A_n \subset A \) l'insieme di tutti i sottoinsiemi finiti di \( \mathbb{N} \) di cardinalità \( n \).
Chiaramente esiste una biiezione tra \(\phi_n: A_n \to \mathbb{N}^n \) e mi chiedevo dunque se non avessimo una biiezione
\( \phi : A \to \mathbb{N} \times \mathbb{N}^2 \times \mathbb{N}^3 \times \ldots \)
Le domanda sono le seguenti
1) Ha senso definire il prodotto cartesiano di infiniti numerabili insiemi?
2) Se si, questo dimostra che il prodotto cartesiano di infiniti numerabili insiemi numerabili è di cardinalità numerabile?
3) Se si, si può dimostrare in modo indipendente da come ho svolto l'esercizio che \( \mathbb{N} \times \mathbb{N}^2 \times \mathbb{N}^3 \times \ldots \) è numerabile?
Grazie.
Allora sebbene io l'abbia risolto in modo diverso avrei una curiosità, se fosse possibile procedere in modo distinto.
Nominiamo \( A \) l'insieme descritto nell'enunciato, io ho trovato la seguente mappa iniettiva \[ f : A \hookrightarrow \mathbb{N} \]
\[a\in A \mapsto f(a)= \prod\limits_{j \in a} p_j \]
Dove \( p_j \) è il \(j-\)esimo numero primo.
La mia domanda è un'altra allora, prima di pensare a questa cosa, avevo pensato che \( A \) contiene tutti gli insiemi di cardinalità \( 1\), chiamiamo \( A_n \subset A \) l'insieme di tutti i sottoinsiemi finiti di \( \mathbb{N} \) di cardinalità \( n \).
Chiaramente esiste una biiezione tra \(\phi_n: A_n \to \mathbb{N}^n \) e mi chiedevo dunque se non avessimo una biiezione
\( \phi : A \to \mathbb{N} \times \mathbb{N}^2 \times \mathbb{N}^3 \times \ldots \)
Le domanda sono le seguenti
1) Ha senso definire il prodotto cartesiano di infiniti numerabili insiemi?
2) Se si, questo dimostra che il prodotto cartesiano di infiniti numerabili insiemi numerabili è di cardinalità numerabile?
3) Se si, si può dimostrare in modo indipendente da come ho svolto l'esercizio che \( \mathbb{N} \times \mathbb{N}^2 \times \mathbb{N}^3 \times \ldots \) è numerabile?
Grazie.
Risposte
Come definiresti \(\displaystyle\varphi\)?
1) Sì, ha senso.
2) No, dovresti dimostrarlo.
3) Sì, conosco solo una dimostrazione indipendente dall'equipotenza tra \(\displaystyle S\) (infinito) e \(\displaystyle\mathcal{P}_f(S)\) (insieme delle parti finite di \(\displaystyle S\)).
P.S.: ecco una dimostrazione classica.
1) Sì, ha senso.
2) No, dovresti dimostrarlo.
3) Sì, conosco solo una dimostrazione indipendente dall'equipotenza tra \(\displaystyle S\) (infinito) e \(\displaystyle\mathcal{P}_f(S)\) (insieme delle parti finite di \(\displaystyle S\)).
P.S.: ecco una dimostrazione classica.
"j18eos":
Come definiresti \(\displaystyle\varphi\)?
Per \( \phi_n \) effettivamente la funzione che avevo in mente è una mappa iniettiva e non una biiezione, ordino tutti gli insiemi in ordine crescente e prendo \( a \in A_n \mapsto \phi_n(a)=(a_1, a_2, \ldots, a_n ) \) dove \( a_i \) è l'\(i\)-esimo elemento di \( a \).
Mentre \( \phi \) la definisco come \( a \in A \mapsto \phi_n(a) \Leftrightarrow \operatorname{card}(a)=n \)
Ad esempio con questa definizione non esiste nessun \( a \in A \) tale che \( f(a)= (8,8,8) \)
"j18eos":
1) Sì, ha senso.
2) No, dovresti dimostrarlo.
3) Sì, conosco solo una dimostrazione indipendente dall'equipotenza tra \(\displaystyle S\) (infinito) e \(\displaystyle\mathcal{P}_f(S)\) (insieme delle parti finite di \(\displaystyle S\)).
P.S.: ecco una dimostrazione classica.
1) Visto che ha senso posso dire che è equivalente, nel mio caso, al insieme delle successioni dove l'\( a_i \) è un elemento di \( \mathbb{N}^i \) ?
2) Ok.
3) Grazie per il link.
"3m0o":
Nominiamo \( A \) l'insieme descritto nell'enunciato, io ho trovato la seguente mappa iniettiva \[ f : A \hookrightarrow \mathbb{N} \]
\[a\in A \mapsto f(a)= \prod\limits_{j \in a} p_j \]
Dove \( p_j \) è il \(j-\)esimo numero primo.
Bella questa soluzione.
1) Ha senso definire il prodotto cartesiano di infiniti numerabili insiemi?
2) Se si, questo dimostra che il prodotto cartesiano di infiniti numerabili insiemi numerabili è di cardinalità numerabile?
3) Se si, si può dimostrare in modo indipendente da come ho svolto l'esercizio che \( \mathbb{N} \times \mathbb{N}^2 \times \mathbb{N}^3 \times \ldots \) è numerabile?
1) Si, si può. E il fatto che siano numerabili e/o in quantità numerabile è ininfluente;
2) Assolutamente no, questa cosa è falsa, la cardinalità di un tale prodotto è la stessa di $RR$ (il motivo è che potresti in modo naturale mettere in biezione un suo sottoinsieme con l'insieme $P(NN)$: insieme dato da ${0,1}^NN$ a meno di qualche identificazione (in realtà questo spiega solo una disuguaglianza ma vabbè));
3) Vedi il punto 2.
Comunque mi chiedo come mai ti sembra naturale chiedersi se questi due insiemi siano in biezione dato che $|A_n|=|NN^n|$, $A=uuu_{n\inNN}A_n$, quello che dovrebbe venirti in mente è che $uuu_{n\inNN}NN^n$ è in biezione con $A$ (e infatti questo è vero per i motivi che pensi).
"3m0o":
Per \( \phi_n \) effettivamente la funzione che avevo in mente è una mappa iniettiva e non una biiezione, ordino tutti gli insiemi in ordine crescente e prendo \( a \in A_n \mapsto \phi_n(a)=(a_1, a_2, \ldots, a_n ) \) dove \( a_i \) è l'\( i \)-esimo elemento di \( a \).
Questa non è una funzione bel definita perché quando hai un insieme non puoi immaginarti i suoi elementi in un qualche ordine, sono "alla rinfusa".
P.S. Era meglio se aprivi questa discussione nella sezione di algebra.
-Hai ragione ho preso un abbaglio è la cardinalità dell'unione ad essere in biiezione con \( A \)!
-Ah non posso definire prima una mappa che prende un elemento e lo restituisce ordinato? È una biiezione di \( A \) con \( A \)
Però tu e j18eos mi avete detto due cose diverse, te che ha la cardinalità di \( \mathbb{R} \) e j18eos che è numerabile...
P.S. Era un problema del corso di topologia e siccome ho visto nella descrizione dei temi di Geometria e Algebra Lineare "topologia" credevo fosse la sezione adatta
-Ah non posso definire prima una mappa che prende un elemento e lo restituisce ordinato? È una biiezione di \( A \) con \( A \)
Però tu e j18eos mi avete detto due cose diverse, te che ha la cardinalità di \( \mathbb{R} \) e j18eos che è numerabile...
P.S. Era un problema del corso di topologia e siccome ho visto nella descrizione dei temi di Geometria e Algebra Lineare "topologia" credevo fosse la sezione adatta
@3m0o Ho sbagliato io: il prodotto cartesiano infinito numerabile di insiemi numerabili è un insieme infinito non numerabile;
ciò che è vero riguarda l'unione infinita numerabile di insiemi numerabili, la quale è numerabile.
ciò che è vero riguarda l'unione infinita numerabile di insiemi numerabili, la quale è numerabile.
"3m0o":
-Ah non posso definire prima una mappa che prende un elemento e lo restituisce ordinato? È una biiezione di \( A \) con \( A \)
In realtà si puoi prendere un insieme e mandarlo nella $n$-upla dei suoi elementi disposti in modo decrescente (o crescente). Non so se intendevi questo prima ma quello che avevi scritto era un po' confuso.
P.S. Era un problema del corso di topologia e siccome ho visto nella descrizione dei temi di Geometria e Algebra Lineare "topologia" credevo fosse la sezione adatta
Senz'altro te lo avranno dato in un corso di topologia, ma è un esercizio di teoria degli insiemi.
Bonus: lo stesso risultato vale per qualsiasi insieme infinito.
"otta96":
Bonus: lo stesso risultato vale per qualsiasi insieme infinito.
Intendi che sia \( X \) un insieme di cardinalità infinita (numerabile o non) allora l'insieme dei sottoinsiemi finiti di \( X \) è numerabile?
Se si, penso che la stessa mappa definita nel mio primo commento è valida, sia \( A_X \) l'insieme dei sottinsiemi finiti di \( X \) allora, sia \( g : A_X \to A_g \) una funzione di scelta, che selezione un elemento \( A_X \ni a \) e gli assegna la sua cardinalità. E sia \( A_g \) l'insieme dei rappresentanti, ovvero \( \forall a,b \in A_g\) allora \( a,b \in A_X \) e \( \operatorname{card}(a) \neq \operatorname{card}(b) \).
\[ f : A_g \hookrightarrow \mathbb{N} \]
\[ A_g \ni a \mapsto f(a)= \prod\limits_{j \in \operatorname{card}(a) } p_j \]
è una mappa iniettiva.
Funziona?
"3m0o":
Intendi che sia \( X \) un insieme di cardinalità infinita (numerabile o non) allora l'insieme dei sottoinsiemi finiti di \( X \) è numerabile?
No, intendo che ha la stessa cardinalità di $X$, scusa per non essere stato chiaro. Comunque è chiaro che la cardinalità dell'insieme dei sottoinsiemi finiti di $X$ non può avere cardinalità più piccola di $X$, perché la famiglia dei singoletti di $X$ è in biezione in modo naturale con $X$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo