Cardinalita' prodotto cartesiano numerabile
Considero una famiglia numerabile di insiemi numerabili $(A_i)_(i \in I)$ e chiamo $A=\prod_{i \in I}A_i$ il prodotto cartesiano degli $A_i$.
Come posso dimostrare che in generale $A$ non e' numerabile?
Ovviamente se $I$ e' finito oppure se gli $A_i$ sono finiti allora $A$ e' numerabile, vorrei far vedere che non lo e' se $I$ e' infinito numerabile e gli $A_i$ sono infiniti numerabili.
Come posso dimostrare che in generale $A$ non e' numerabile?
Ovviamente se $I$ e' finito oppure se gli $A_i$ sono finiti allora $A$ e' numerabile, vorrei far vedere che non lo e' se $I$ e' infinito numerabile e gli $A_i$ sono infiniti numerabili.
Risposte
A non è numerabile se gli Ai sono finiti. Pensa alla rappresentazione decimale dei numeri reali.
Giusto, nella rappresentazione decimale dei numeri reali ciascuna cifra appartiene all'insieme finito ${0,1,2,3,4,5,6,7,8,9}$ e il numero di cifre e' numerabile ma la quantita' di numeri reali che si possono esprimere e' piu' che numerabile.
Ritiro quanto detto sul caso degli $A_i$ finiti quindi.
Potrei allora sfruttare il tuo esempio dei numeri reali per confutare il fatto che un prodotto cartesiano numerabile di insiemi numerabili e' numerabile, ma si riesce ad ottenere questo risultato lavorando su insiemi generici (senza portare un controesempio particolare quindi)?
Ritiro quanto detto sul caso degli $A_i$ finiti quindi.
Potrei allora sfruttare il tuo esempio dei numeri reali per confutare il fatto che un prodotto cartesiano numerabile di insiemi numerabili e' numerabile, ma si riesce ad ottenere questo risultato lavorando su insiemi generici (senza portare un controesempio particolare quindi)?
Prendi due elementi in ogni $A_i$. Ottieni un sottoinsieme del tipo $2^{NN}$ che quindi non è numerabile.
Ottimo, era proprio questo che intendevo!
In questo modo posso "riciclare" la tua idea anche per il prodotto di gruppi o di altre strutture.
Non mi e' pero' chiarissimo il perche', nel caso in cui ciascun $A_i$ abbia 2 elementi si ottenga un prodotto $A$ di cardinalita' $2^(|NN|)$, lo vedi come insieme delle funzioni da $NN$ a $A_i$? Se si, vale anche nel caso infinito la relazione $|B^A|=|B|^(|A|)$?
In questo modo posso "riciclare" la tua idea anche per il prodotto di gruppi o di altre strutture.
Non mi e' pero' chiarissimo il perche', nel caso in cui ciascun $A_i$ abbia 2 elementi si ottenga un prodotto $A$ di cardinalita' $2^(|NN|)$, lo vedi come insieme delle funzioni da $NN$ a $A_i$? Se si, vale anche nel caso infinito la relazione $|B^A|=|B|^(|A|)$?
"thedarkhero":Sì, è la definizione di elevamento a potenza per cardinali.
Non mi e' pero' chiarissimo il perche', nel caso in cui ciascun $A_i$ abbia 2 elementi si ottenga un prodotto $A$ di cardinalita' $2^(|NN|)$, lo vedi come insieme delle funzioni da $NN$ a $A_i$? Se si, vale anche nel caso infinito la relazione $|B^A|=|B|^(|A|)$?
Perfetto, grazie!
Ora tornando al caso generale in cui $I$ è numerabile e ciascun $A_i$ è numerabile suppongo di fissare un elemento $(\bara_i)_{i \in I}$ del prodotto cartesiano.
Considero $B={(a_i)_{i \in I} \in A | a_i != \bara_i " per un numero finito di indici"}$.
Mi chiedo se è vero che $B$ è sempre numerabile oppure no...
Ora tornando al caso generale in cui $I$ è numerabile e ciascun $A_i$ è numerabile suppongo di fissare un elemento $(\bara_i)_{i \in I}$ del prodotto cartesiano.
Considero $B={(a_i)_{i \in I} \in A | a_i != \bara_i " per un numero finito di indici"}$.
Mi chiedo se è vero che $B$ è sempre numerabile oppure no...
Praticamente stai facendo l'analogo della somma diretta [tex]\oplus[/tex] (dove il tuo elemento fissato corrisponde allo zero). Una somma diretta numerabile di strutture numerabili è numerabile perché le famiglie che consistono delle somme con un dato numero di termini sono numerabili e la somma diretta è l'unione (sull'insieme degli indici) di tutte queste famiglie. Quindi la risposta è sì.
"Martino":
le famiglie che consistono delle somme con un dato numero di termini sono numerabili
Se ho capito bene mi stai dicendo che $B_k={(a_i)_{i \in I} | a_i != \bara_i " per esattamente k indici"}$ è numerabile, immagino che sia perchè è isomorfo al prodotto cartesiano di $k$ insiemi numerabili e quindi è numerabile, giusto?
"Martino":
la somma diretta è l'unione (sull'insieme degli indici) di tutte queste famiglie
Dunque l'unione numerabile di famiglie numerabili è numerabile? Non mi è chiaro il perchè...
"thedarkhero":Se ho capito bene mi stai dicendo che $B_k={(a_i)_{i \in I} | a_i != \bara_i " per esattamente k indici"}$ è numerabile, immagino che sia perchè è isomorfo al prodotto cartesiano di $k$ insiemi numerabili e quindi è numerabile, giusto?[/quote]No, direi piuttosto che è un'unione numberabile di prodotti cartesiani di $k$ insiemi numerabili quindi è numerabile (vedi qui sotto).
[quote="Martino"]le famiglie che consistono delle somme con un dato numero di termini sono numerabili
Per esempio vedi qui."Martino":Dunque l'unione numerabile di famiglie numerabili è numerabile? Non mi è chiaro il perchè...
la somma diretta è l'unione (sull'insieme degli indici) di tutte queste famiglie
Grazie mille!
Andrò in cerca del [url=https://proofwiki.org/wiki/Book:Steven_A._Gaal/Point_Set_Topology]Point Set Topology[/url] che è citato dalla pagina che mi hai linkato ma penso che la tua spiegazione sia stata esauriente
A presto!
Andrò in cerca del [url=https://proofwiki.org/wiki/Book:Steven_A._Gaal/Point_Set_Topology]Point Set Topology[/url] che è citato dalla pagina che mi hai linkato ma penso che la tua spiegazione sia stata esauriente
A presto!
"Martino":Se ho capito bene mi stai dicendo che $B_k={(a_i)_{i \in I} | a_i != \bara_i " per esattamente k indici"}$ è numerabile, immagino che sia perchè è isomorfo al prodotto cartesiano di $k$ insiemi numerabili e quindi è numerabile, giusto?[/quote]No, direi piuttosto che è un'unione numberabile di prodotti cartesiani di $k$ insiemi numerabili quindi è numerabile (vedi qui sotto).[/quote]
[quote="thedarkhero"][quote="Martino"]le famiglie che consistono delle somme con un dato numero di termini sono numerabili
Rivedendo un po il discorso in generale mi sono accorto che un punto non mi è ancora del tutto chiaro.
Abbiamo detto che $B=\bigcup_{k \in NN}B_k$ è numerabile perchè è unione numerabile di insiemi numerabili. Questo mi è chiaro.
Ma per vedere che ciascun $B_k$ è numerabile mi hai consigliato di vedere $B_k$ come un'unione numerabile di prodotti cartesiani di $k$ insiemi numerabili...chi sono questi $k$ insiemi numerabili?
Fissato un insieme di $k$ indici questi $k$ insiemi numerabili di cui parli sono gli $A_i$ corrispondenti a questi $k$ indici $i$.
In pratica si tratta di questo: se hai un insieme numerabile $I$ (l'insieme degli indici) allora l'insieme dei sottoinsiemi di $I$ di $k$ elementi è numerabile anch'esso (questo è un fatto ben noto, anzi addirittura l'insieme dei sottoinsiemi finiti di $I$ è numerabile), e a ciascun sottoinsieme [tex]J \subseteq I[/tex] di $k$ elementi fai corrispondere il prodotto degli $A_i$ al variare di $i in J$.
In pratica si tratta di questo: se hai un insieme numerabile $I$ (l'insieme degli indici) allora l'insieme dei sottoinsiemi di $I$ di $k$ elementi è numerabile anch'esso (questo è un fatto ben noto, anzi addirittura l'insieme dei sottoinsiemi finiti di $I$ è numerabile), e a ciascun sottoinsieme [tex]J \subseteq I[/tex] di $k$ elementi fai corrispondere il prodotto degli $A_i$ al variare di $i in J$.
Ok, ora mi hai convinto completamente! 
Mi indicheresti un riferimento dove posso trovare una dimostrazione del fatto che l'insieme dei sottoinsiemi finiti di un insieme numerabile è numerabile?
Mi indicheresti un riferimento dove posso trovare una dimostrazione del fatto che l'insieme dei sottoinsiemi finiti di un insieme numerabile è numerabile?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo