Insiemi numerabili e finiti
mi date una mano con le seguenti dimostrazioni. Come posso provare che:
1) L'unione di un insieme numerabile ed uno finito è numerabile
2)l'unione di un numero finito di insiemi numerabili da luogo a un insieme numerabile
3) l'unione di un'infinità numerabile di insiemi numerabili è un insieme numerabile
----------------------------------------------------------
Admin
Insiemi
1) L'unione di un insieme numerabile ed uno finito è numerabile
2)l'unione di un numero finito di insiemi numerabili da luogo a un insieme numerabile
3) l'unione di un'infinità numerabile di insiemi numerabili è un insieme numerabile
----------------------------------------------------------
Admin
Insiemi
Risposte
G.D. mi prendo un po di tempo per leggere il tuo post e per capirlo in quanto non ho fatto la teoria assiomatica. Poi andremo avanti ok?
"Indrjo Dedej":
Io ho definito i numeri naturali a partire da quel ragionamento. Andando come hai detto tu, un numero naturale a un "certo punto all'infinito" è uguale al suo successivo. Assurdo.
scusami ma non ho ben capito quest'ultimo post..ma sono curioso...puoi spiegarti un po meglio? scusami di nuovo
Per quanto riguarda la definizione di insieme numerabile:
• in Curzio, Longobardi, Maj - Lezioni di Algebra si definisce numerabile un insieme che sia equipotente a \( \mathbb{N} \);
• in De Giovanni, Franciosi - Elementi di Algebra si definisce numerabile un insieme che sia equipotente a \( \mathbb{N} \);
• in Rudin - Principi di Analisi Matematica si definisce numerabile un insieme che sia equipotente a \( \mathbb{N} \);
• in Acerbi, Buttazzo - Primo Corso di Analisi Matematica si definisce numerabile un insieme che sia equipotente a \( \mathbb{N} \);
• in De Marco - Analisi Uno si definisce numerabile un insieme che sia equipotente a \( \mathbb{N} \);
• in Prodi - Analisi Matematica si definisce numerabile un insieme che sia equipotente a \( \mathbb{N} \);
Quando si usa l'aggettivo numerabile in questa accezione si usa la locuzione al più numerabile per indicare un insieme che o è finito o è numerabile. Si distingue allora chiaramente tra gli insiemi finiti e quelli numerabili, com'è nel post di apertura di questo topic.
La non uniformità di nomenclatura nasce per mezzo dei testi in inglese (soprattutto di Matematica Discreta). Qui si utilizza il termine countable e alcuni lo utilizzano come sopra è stato usato il termine numerabile (sempre Rudin nella versione inglese dei Principi), altri lo utilizzano come nel senso di al più numerabile (e.g. in Rosen - Discrete Mathematics) e specificano countably infinite per indicare un insieme equipotente a \( \mathbb{N} \): in italiano ciò andrebbe reso più correttamente con la dicitura contabile, come in Lolli - Guida Alla Teoria degli Insiemi.
Non c'è quindi una universale uniformità di nomenclatura. Tuttavia nel post di apertura si distingue tra numerabile e finito.
• in Curzio, Longobardi, Maj - Lezioni di Algebra si definisce numerabile un insieme che sia equipotente a \( \mathbb{N} \);
• in De Giovanni, Franciosi - Elementi di Algebra si definisce numerabile un insieme che sia equipotente a \( \mathbb{N} \);
• in Rudin - Principi di Analisi Matematica si definisce numerabile un insieme che sia equipotente a \( \mathbb{N} \);
• in Acerbi, Buttazzo - Primo Corso di Analisi Matematica si definisce numerabile un insieme che sia equipotente a \( \mathbb{N} \);
• in De Marco - Analisi Uno si definisce numerabile un insieme che sia equipotente a \( \mathbb{N} \);
• in Prodi - Analisi Matematica si definisce numerabile un insieme che sia equipotente a \( \mathbb{N} \);
Quando si usa l'aggettivo numerabile in questa accezione si usa la locuzione al più numerabile per indicare un insieme che o è finito o è numerabile. Si distingue allora chiaramente tra gli insiemi finiti e quelli numerabili, com'è nel post di apertura di questo topic.
La non uniformità di nomenclatura nasce per mezzo dei testi in inglese (soprattutto di Matematica Discreta). Qui si utilizza il termine countable e alcuni lo utilizzano come sopra è stato usato il termine numerabile (sempre Rudin nella versione inglese dei Principi), altri lo utilizzano come nel senso di al più numerabile (e.g. in Rosen - Discrete Mathematics) e specificano countably infinite per indicare un insieme equipotente a \( \mathbb{N} \): in italiano ciò andrebbe reso più correttamente con la dicitura contabile, come in Lolli - Guida Alla Teoria degli Insiemi.
Non c'è quindi una universale uniformità di nomenclatura. Tuttavia nel post di apertura si distingue tra numerabile e finito.
Ho considerato appunto una classe di insiemi e tra questi insiemi ho esguito una partizione in classi nel seguente modo:
1)una di queste classi conterrà "tutti" gli insiemi vuoti: questi insiemi hanno la caratteristica di avere 0 elementi. Chiamerò questa classe di equivalenza 0;
2) un'altra classe conterrà tutti gli insiemi unitari: questi insiemi hanno la proprietà di avere un elemento. Questa classe di equivalenza prende il nome di 1;
3) ciascuna delle altre classi sarà costituita da tutti gli insemi in corrispondenza biunivoca a uno dato che è da scegliersi tra gli insiemi che si costruiscono aggiungendo di volta in volta un elemento.
In questo modo non è difficile definire le operazioni di addizione( e poi dopo quellla di moltiplicazione) e le proprietà attraverso la consueta operazione di unione di insiemi. Per quanto riguarda la relazione di $<$ è facile da definire: dati due insiemi $A$ e $B$ con $A\subset B$, si dice che la classe di equivalenza di $A$ (cardinalità di $A$ o numero naturale $A$) è minore di quella di $B$. (Questo è un linguaggio che io ho inventato e che spero comprendiate.)
Quessta è una idea rafforzata da quanto avete detto voi, ma anche un po' messa in dubbio da quei "paradossi" che mi avete appena esposto sopprattutto per quanto riguarda la relazione di disuguaglianza stretta.
1)una di queste classi conterrà "tutti" gli insiemi vuoti: questi insiemi hanno la caratteristica di avere 0 elementi. Chiamerò questa classe di equivalenza 0;
2) un'altra classe conterrà tutti gli insiemi unitari: questi insiemi hanno la proprietà di avere un elemento. Questa classe di equivalenza prende il nome di 1;
3) ciascuna delle altre classi sarà costituita da tutti gli insemi in corrispondenza biunivoca a uno dato che è da scegliersi tra gli insiemi che si costruiscono aggiungendo di volta in volta un elemento.
In questo modo non è difficile definire le operazioni di addizione( e poi dopo quellla di moltiplicazione) e le proprietà attraverso la consueta operazione di unione di insiemi. Per quanto riguarda la relazione di $<$ è facile da definire: dati due insiemi $A$ e $B$ con $A\subset B$, si dice che la classe di equivalenza di $A$ (cardinalità di $A$ o numero naturale $A$) è minore di quella di $B$. (Questo è un linguaggio che io ho inventato e che spero comprendiate.)
Quessta è una idea rafforzata da quanto avete detto voi, ma anche un po' messa in dubbio da quei "paradossi" che mi avete appena esposto sopprattutto per quanto riguarda la relazione di disuguaglianza stretta.
ok G.D. credo di esserci. una cosa, ho letto sul de marco "Analisi 1" che una famiglia di elementi di $X$, indicizzata da $I$, è una funzione $x:I\rightarrowX$. Questa definizione coincide con la tua no!?!? infine, i quattro punti finali del tuo post credo di averli capiti, in realtà qualcosa sapevo già superficialmente.
In Dizionario di matematica elementare-Stella Baruk, Zanichelli leggo:
"Un insieme si dice numerabile se è equipotente all'insieme dei numeri naturali"(che lo 0 lo sia o meno poco importa, come G.D. ha affermato).
"Un insieme si dice numerabile se è equipotente all'insieme dei numeri naturali"(che lo 0 lo sia o meno poco importa, come G.D. ha affermato).
allora, Indrjo Dedej ho letto velocemente il tuo ultimo post, non ho approfondito ma mi sembra una cosa interessante. io consiglio di andare con ordine altrimenti rischiamo di fare una confusione allucinante. quindi propongo di proseguire con la prima questione e poi affrontare la tua. ok? 
"Indrjo Dedej":
In Dizionario di matematica elementare-Stella Baruk, Zanichelli leggo:
"Un insieme si dice numerabile se è equipotente all'insieme dei numeri naturali"(che lo 0 lo sia o meno poco importa, come G.D. ha affermato).
dunque in base a questa definizione un insieme finito non è numerabile......?
Io come definizione di insieme numerabile userei quella del dizionario. Proporrei il nome di insieme numerabile finito per gli insiemi finiti. Però è una cosa su cui bisogna sicuramente riflettere. Tanto per... nella proprietà di Archimede $mathbb N$ contiene o no lo $0$?
infatti non è immediato. l'importante è sempre mettersi d'accordo. perchè se vale la locuzione "al più numerabile" allora si dovrebbe distinguere tra insiemi finiti numerabili e insiemi infiniti numerabili. in caso contrario, secondo me, parlare di un insieme numerabile, sottintende il fatto che questo insieme sia infinito.
scusate, rileggendo i post precedenti mi sono accorto che il mio ultimo post è abbastanza inutile in quanto avevo interpretato male una frase scritta da G.D.
per cui, atteniamoci alle definizioni dei vari libri citati, compreso il dizionario menzionato da Indrjo Dedej.
riassumendo:
1) un insieme si dice numerabile se è equipotente a $N$
2) la locuzione "un insieme al più numerabile" indica un insieme che sia o finito o numerabile.
Infine, G.D. ho riletto per bene il tuo post, e devo dire che è molto chiaro. In particolare, si, l'esistenza del concetto di famiglia indicizzata, intesa come applicazione come da te definita, permette di usare le due definizioni di insieme-unione in maniera equivalente. Inoltre dal Prodi (pag. 35) ho letto una cosa, che secondo me, seppur non esplicitamente, è abbastanza simile a quanto detto riguardo all'applicazione $x:I\rightarrowX$, in cui si richiede esclusivamente la suriettività.
Per cui, G.D., quando vuoi possiamo andare avanti
per cui, atteniamoci alle definizioni dei vari libri citati, compreso il dizionario menzionato da Indrjo Dedej.
riassumendo:
1) un insieme si dice numerabile se è equipotente a $N$
2) la locuzione "un insieme al più numerabile" indica un insieme che sia o finito o numerabile.
Infine, G.D. ho riletto per bene il tuo post, e devo dire che è molto chiaro. In particolare, si, l'esistenza del concetto di famiglia indicizzata, intesa come applicazione come da te definita, permette di usare le due definizioni di insieme-unione in maniera equivalente. Inoltre dal Prodi (pag. 35) ho letto una cosa, che secondo me, seppur non esplicitamente, è abbastanza simile a quanto detto riguardo all'applicazione $x:I\rightarrowX$, in cui si richiede esclusivamente la suriettività.
Per cui, G.D., quando vuoi possiamo andare avanti
Ciao!
Non ricordavo più questa discussione... con il nuovo browser e con i colori delle pagine che non riesco a gestire, non vedo più vari pulsanti, tra cui "cita", per cui mi arrangio a memoria...
Evidentemente (riguardo alle obiezioni sul mio vecchio intervento) quando una corrispondenza è biunivoca non si nota la "comodità" di considerare uno dei due insiemi come dominio e l'altro come codominio, e quindi io ho trascurato di dire che per generalizzare al caso di insiemi non necessariamente disgiunti si costruisce una funzione suriettiva da $NN$ all'unione degli insiemi numerabili (chiamiamo $U$ tale insieme), dimostrando di fatto che $|NN|>=|U|$.
Il fatto che siano numerabili dipende dal fatto che la "numerabilità" è ilprimo grado di infinito, o, se vogliamo, manca la dimostrazione del fatto che $|NN|<=|U|$ o dell'impossibilità che sia $|NN|>|U|$: se gli insiemi che costituiscono $U$ possono anche essere tutti finiti, questo può succedere, ma in tal caso abbiamo chiamato "numerabili" insiemi finiti, e stiamo solo dimostrando che la loro unione è finita o al più numerabilmente infinita.
Questo può dirlo solo chi ha posto il quesito o l'obiezione!
Correggetemi se sbaglio.
Non ricordavo più questa discussione... con il nuovo browser e con i colori delle pagine che non riesco a gestire, non vedo più vari pulsanti, tra cui "cita", per cui mi arrangio a memoria...
Evidentemente (riguardo alle obiezioni sul mio vecchio intervento) quando una corrispondenza è biunivoca non si nota la "comodità" di considerare uno dei due insiemi come dominio e l'altro come codominio, e quindi io ho trascurato di dire che per generalizzare al caso di insiemi non necessariamente disgiunti si costruisce una funzione suriettiva da $NN$ all'unione degli insiemi numerabili (chiamiamo $U$ tale insieme), dimostrando di fatto che $|NN|>=|U|$.
Il fatto che siano numerabili dipende dal fatto che la "numerabilità" è ilprimo grado di infinito, o, se vogliamo, manca la dimostrazione del fatto che $|NN|<=|U|$ o dell'impossibilità che sia $|NN|>|U|$: se gli insiemi che costituiscono $U$ possono anche essere tutti finiti, questo può succedere, ma in tal caso abbiamo chiamato "numerabili" insiemi finiti, e stiamo solo dimostrando che la loro unione è finita o al più numerabilmente infinita.
Questo può dirlo solo chi ha posto il quesito o l'obiezione!
Correggetemi se sbaglio.
"17re87":
ok G.D. credo di esserci. una cosa, ho letto sul de marco "Analisi 1" che una famiglia di elementi di $X$, indicizzata da $I$, è una funzione $x:I\rightarrowX$. Questa definizione coincide con la tua no!?!? infine, i quattro punti finali del tuo post credo di averli capiti, in realtà qualcosa sapevo già superficialmente.
Sì: concettualmente è la stessa definizione.
"17re87":
Inoltre dal Prodi (pag. 35) ho letto una cosa, che secondo me, seppur non esplicitamente, è abbastanza simile a quanto detto riguardo all'applicazione $x:I\rightarrowX$, in cui si richiede esclusivamente la suriettività.
Il Prodi richiede la suriettività dell'applicazione \( x \colon I \to X \) per un motivo molto semplice: a pagina 27 definisce l'unione per una famiglia qualunque di insiemi e vuole che la famiglia indiciata di insiemi sia solo un modo diverso di vedere la famiglia qualunque, un modo per riscriverne gli insiemi che ne sono elementi per mezzo di un insieme di indici, per questo fa l'ipotesi che l'applicazione \( x \colon I \to X \) sia suriettiva, per poter dotare di un indice tutti gli insiemi che sono elementi della famiglia qualunque.
"G.D.":
[quote="17re87"]ok G.D. credo di esserci. una cosa, ho letto sul de marco "Analisi 1" che una famiglia di elementi di $ X $, indicizzata da $ I $, è una funzione $ x:I\rightarrowX $. Questa definizione coincide con la tua no!?!? infine, i quattro punti finali del tuo post credo di averli capiti, in realtà qualcosa sapevo già superficialmente.
Sì: concettualmente è la stessa definizione.
"17re87":
Inoltre dal Prodi (pag. 35) ho letto una cosa, che secondo me, seppur non esplicitamente, è abbastanza simile a quanto detto riguardo all'applicazione $ x:I\rightarrowX $, in cui si richiede esclusivamente la suriettività.
Il Prodi richiede la suriettività dell'applicazione \( x \colon I \to X \) per un motivo molto semplice: a pagina 27 definisce l'unione per una famiglia qualunque di insiemi e vuole che la famiglia indiciata di insiemi sia solo un modo diverso di vedere la famiglia qualunque, un modo per riscriverne gli insiemi che ne sono elementi per mezzo di un insieme di indici, per questo fa l'ipotesi che l'applicazione \( x \colon I \to X \) sia suriettiva, per poter dotare di un indice tutti gli insiemi che sono elementi della famiglia qualunque.[/quote]
Perfetto, qui ci siamo. In realtà avevo pensato anche io a questo fatto, cioè la richiesta della suriettività per quel motivo preciso.
"adaBTTLS":
Ciao!
Non ricordavo più questa discussione... con il nuovo browser e con i colori delle pagine che non riesco a gestire, non vedo più vari pulsanti, tra cui "cita", per cui mi arrangio a memoria...
Evidentemente (riguardo alle obiezioni sul mio vecchio intervento) quando una corrispondenza è biunivoca non si nota la "comodità" di considerare uno dei due insiemi come dominio e l'altro come codominio, e quindi io ho trascurato di dire che per generalizzare al caso di insiemi non necessariamente disgiunti si costruisce una funzione suriettiva da $ NN $ all'unione degli insiemi numerabili (chiamiamo $ U $ tale insieme), dimostrando di fatto che $ |NN|>=|U| $.
Il fatto che siano numerabili dipende dal fatto che la "numerabilità" è ilprimo grado di infinito, o, se vogliamo, manca la dimostrazione del fatto che $ |NN|<=|U| $ o dell'impossibilità che sia $ |NN|>|U| $: se gli insiemi che costituiscono $ U $ possono anche essere tutti finiti, questo può succedere, ma in tal caso abbiamo chiamato "numerabili" insiemi finiti, e stiamo solo dimostrando che la loro unione è finita o al più numerabilmente infinita.
Questo può dirlo solo chi ha posto il quesito o l'obiezione!
Correggetemi se sbaglio.
il fatto è che nella tua costruzione, l'ipotesi di insiemi disgiunti è vitale affinchè la $f$ sia una funzione. infatti nel caso in cui, ad esempio, $a_1,_1=a_2,_3$, succede che a un elemento del dominio corrispondono due elementi distinti.
Ciao G.D. Quando vuoi possiamo continuare con la
Questione
Questione
E allora.
Si vuole provare che l'unione di un numero finito di insiemi numerabili è anch'essa numerabile.
La costruzione a suo tempo proposta da adaBTTLS prevede, se l'ho bene interpretata, di disporre gli elementi dei vari insiemi numerabili in una sorta di matrice infinita avente una infinità numerabile di colonne e tante righe quanti sono gli insiemi numerabili da unire di modo che sulla \( n \)-esima riga siano disposti gli elementi dell'insieme \( n \)-esimo: a questo punto si scorre la matrice per colonne e gli elementi degli insiemi da unire risultano così disposti in successione. Sic stantibus rebus concordo con 17re87: il problema è che se gli insiemi non sono disgiunti tale procedura non solo non definisce un'applicazione biiettiva ma non definisce nemmeno un'applicazione. Il problema presentato da tale procedura (concettualmente simile all'argomento diagonale di Cantor) si aggira "saltando" gli elementi che eventualmente si ripetono, come suggerito dal Pagani-Salsa citato da 17re87. Tale soluzione è intuitivamente più che accettabile. Tuttavia per "aggiustare il tiro" si può fare di meglio che proporre di "saltare" gli elementi che si ripetono. L'asserto si può inoltre provare anche in altro modo.
Iniziamo allora ad "aggiustare il tiro" con qualcosa di meglio del "saltare" gli elementi che eventualmente si ripetono.
Si supponga quindi di aver provato che l'unione di un numero finito \( n \) di insiemi numerabili a due a due disgiunti è numerabile (magari proprio con la costruzione proposta da adaBTTLS). Si lasci ora cadere l'ipotesi che gli insiemi siano a due a due disgiunti. Poiché si sta unendo un numero finito \( n \) di insiemi, è lecito supporre di avere una famiglia di insiemi numerabili indiciata dall'insieme \( I_{n} := \left \{ 1, 2, 3, \ldots, n \right \} \): siano quindi \( X_{1}, X_{2}, X_{3}, \ldots, X_{n} \) gli \( n \) insiemi numerabili da unire. Si ponga allora:
\[
\begin{align*}
&Y_{1} = X_{1} \\
&Y_{2} = X_{2} \setminus X_{1} \\
&Y_{3} = X_{3} \setminus \left \{ X_{1} \cup X_{2} \right \} \\
&\ldots \\
&Y_{n} = X_{n} \setminus \left \{ X_{1} \cup X_{2} \cup \cdots \cup X_{n-1} \right \} \\
\end{align*}
\]
Sono allora evidenti (o per lo meno dovrebbero esserlo: in alternativa li si può facilmente dimostrare) i seguenti fatti:
• la famiglia di insiemi \( \displaystyle \left ( Y_{i} \right )_{i \in I_{n}} \) è una famiglia di insiemi a due a due disgiunti;
• \( \displaystyle \bigcup_{i \in I_{n}} X_{i} = \bigcup_{i \in I_{n}} Y_{i} \);
• \( \forall i \in I_{n}, Y_{i} \) o è finito o è numerabile ed in particolare \( Y_{1} \) è numerabile.
Si considerino allora gli insiemi \( A = \left \{ i \in I_{n} \mid Y_{i} \text{ è numerabile} \right \} \) e \( B = \left \{ i \in I_{n} \mid Y_{i} \text{ è finito} \right \} \); sono evidenti (o per lo meno dovrebbero esserlo: in alternativa li si può facilmente dimostrare) i seguenti fatti:
• \( A \) e \( B \) sono insiemi finiti;
• \( \displaystyle \bigcup_{i \in I_{n}} Y_{i} = \left ( \bigcup_{i \in A} Y_{i} \right ) \cup \left ( \bigcup_{i \in B} Y_{i} \right ) \);
• \( A \neq \varnothing \);
• \( \displaystyle \bigcup_{i \in A} Y_{i} \) è numerabile (essendo l'unione di un numero finito di insiemi numerabili a due a due disgiunti);
• \( \displaystyle \bigcup_{i \in B} Y_{i} \) è finita.
Allora \( \displaystyle \bigcup_{i \in I_{n}} Y_{i} \) è l'unione di un insieme numerabile e di un insieme finito (eventualmente vuoto), sicché, se preliminarmente è stato dimostrato che l'unione di un insieme numerabile e di un insieme finito è numerabile, si conclude che \( \displaystyle \bigcup_{i \in I_{n}} X_{i} = \bigcup_{i \in I_{n}} Y_{i} \) è numerabile.
Si può anche procede in altro modo.
Si dimostra preliminarmente che:
1. dati due insiemi \( S \) e \( T \), se esistono un'applicazione iniettiva \( f \colon S \to T \) ed un'applicazione iniettiva \( g \colon T \to S \), allora esiste un'applicazione biiettiva \( h \colon S \to T \) (questo fatto è noto come Teorema di Cantor-Bernstein-Schröder);
2. \( \mathbb{N} \times \mathbb{N} \) è numerabile.
A questo punto si prova che l'unione di una famiglia numerabile \( \displaystyle \left ( X_{i} \right )_{i \in \mathbb{N}} \) di insiemi numerabili è numerabile. Poiché \( \forall i \in \mathbb{N}, X_{i} \) è numerabile, allora \( \forall i \in \mathbb{N} \) esiste un'applicazione \( \phi_{i} \colon X_{i} \to \mathbb{N} \) biiettiva. Posto \( \displaystyle X = \bigcup_{i \in \mathbb{N}} X_{i} \), si consideri allora l'applicazione \( \phi \colon X \to \mathbb{N} \times \mathbb{N} \) definita ponendo per ogni \( x \in X, \phi(x) = \left ( n_{x}, m_{x} \right ) \) dove:
• \( n_{x} \) è il minimo dell'insieme \( \left \{ i \in \mathbb{N} \mid \exists X_{i} : x \in X_{i} \right \} \);
• \( \displaystyle m_{x} = \phi_{\textstyle n_{x}} (x) \).
Questa applicazione è ben posta ed è iniettiva; infatti:
• ogni \( x \in X \) deve appartenere a qualche \( X_{i} \), quindi per ogni \( x \in X \) si riesce a trovare almeno una coppia \( \displaystyle \left ( n_{x}, m_{x} \right )\);
• il minimo di un insieme è unico, sicché per ogni \( x \in X \), la prima coordinata della coppia \( \displaystyle \left ( n_{x}, m_{x} \right )\) è unica;
• per ogni \( x \in X \) anche la seconda coordinata della coppia \( \displaystyle \left ( n_{x}, m_{x} \right )\) è unica poiché \( m_{x} \) è l'immagine di \( x \) tramite un'applicazione;
• poiché ogni applicazione \( \phi_{i} \) è biiettiva e quindi iniettiva, se due elementi distinti \( x \) e \( y \) di \( X \) sono tali per cui \( n_{x} = n_{y} \), risulta \( m_{x} \neq m_{y} \), sicché \( \phi(x) \neq \phi(y) \) per la seconda coordinata.
Allora esiste un'applicazione iniettiva di \( X \) in \( \mathbb{N} \times \mathbb{N} \) ed essendo \( \mathbb{N} \times \mathbb{N} \) numerabile, esiste allora un'applicazione iniettiva di \( X \) in \( \mathbb{N} \).
Ma \( \mathbb{N} \) è equipotente a ciascuno degli \( X_{i} \), essendo ciascuno degli \( X_{i} \) numerabile: quindi esiste un'applicazione iniettiva di \( \mathbb{N} \) in \( X_{i} \), qualunque sia \( i \in \mathbb{N} \); inoltre ciascuno degli \( X_{i} \) è una parte di \( X \), sicché per ciascuno degli \( X_{i} \) esiste un'applicazione iniettiva (l'immersione) dell'insieme \( X_{i} \) considerato in \( X \). Ma allora esiste un'applicazione iniettiva di \( \mathbb{N} \) in \( X \).
Per il Teorema di Cantor-Bernstein-Schröder, esiste un'applicazione biiettiva di \( X \) in \( \mathbb{N} \).
A questo punto l'asserto da provare è un corollario di quanto appena provato: volendo provare che l'unione della famigli finita di insiemi numerabili \( \displaystyle \left ( Y_{j} \right )_{j \in I_{n}} \) è numerabile occorre e basta prendere la famiglia numerabile di insiemi numerabili \( \displaystyle \left ( X_{i} \right )_{i \in \mathbb{N}} \) dove \( Y_{1} = X_{0}, Y_{2} = X_{1}, Y_{3} = X_{2}, \ldots, Y_{n} = X_{n - 1} \) e \( Y_{n} = X_{m}, \forall m \geq n \).
Ma ovviamente questo non è tutto.
Non è tutto perché per esempio si può ovviare al problema degli insiemi disgiunti anche in un altro modo: se due insiemi \( S \) e \( T \) non sono disgiunti, lo sono invece gli insiemi \( S' = S \times \left \{ 1 \right \} \) e \( T' = T \times \left \{ 2 \right \} \); inoltre \( S \) e \( S' \) sono equipotenti, così come \( T \) e \( T' \). Quindi anziché lavorare con \( S \) e \( T \) si può lavorare con \( S' \) e \( T' \).
Non è tutto perché si potrebbe pensare di provare prima che l'unione di due insiemi numerabili è numerabile e poi andare per induzione sul numero degli insiemi: essendo ovvio il passo base (l'unione di un solo insieme numerabile è numerabile perché coincide con l'insieme numerabile stesso), assunta l'ipotesi induttiva (l'unione di \( n \) insiemi numerabili è numerabile), allora l'unione di \( n + 1 \) insiemi numerabili si scrive come \( \left ( X_{1} \cup X_{2} \cup \cdots \cup X_{n} \right ) \cup X_{n+1} \), al che \( \left ( X_{1} \cup X_{2} \cup \cdots \cup X_{n} \right ) \) è numerabile per ipotesi induttiva e la conclusione segue per mezzo di quanto preliminarmente provato.
Il punto si sposta allora su come provare che l'unione di due insiemi numerabili è numerabile. Le strategie sono sempre le stesse: o si passa per gli insiemi disgiunti prima e per quelli non disgiunti poi, oppure si procede come segue:
1. si prova preliminarmente che dati due insiemi \( S \) e \( T \), esiste un'applicazione iniettiva di \( S \) in \( T \) se e solo se esiste un'applicazione suriettiva di \( T \) in \( S \);
2. si dimostra preliminarmente che l'insieme \( \mathbb{N} \times \left \{ 0, 1 \right \} \) è numerabile;
3. a questo punto, dati due insiemi numerabili \( X \) e \( Y \), poiché essi sono numerabili, esistono due applicazioni \( \phi_{X} \colon X \to \mathbb{N} \) e \( \phi_{Y} \colon Y \to \mathbb{N} \) entrambe biiettive;
4. la biiettività (in particolare la suriettività) di \( \phi_{X} ( \cdot ) \) e \( \phi_{Y} ( \cdot ) \) garantisce che l'applicazione \( \phi \colon \mathbb{N} \times \left \{ 0, 1 \right \} \to X \cup Y \) definita ponendo \( \phi ( n, 0) = \phi_{X}(n) \) e \( \phi ( n, 1) = \phi_{Y}(n) \) è suriettiva, sicché esiste un'applicazione iniettiva di \( X \cup Y \) in \( \mathbb{N} \times \left \{ 0, 1 \right \} \) e quindi in \( \mathbb{N} \);
5. l'inclusione di \( X \) (o anche di \( Y \)) in \( X \cup Y \) garantisce l'esistenza di un'applicazione iniettiva di \( X \) in \( X \cup Y \) e, poiché \( X \) è numerabile, l'esistenza di un'applicazione iniettiva di \( \mathbb{N} \in X \cup Y \);
6. per il Teorema di Cantor-Bernstein-Schröder si conclude.
Insomma: esistono vari modi per dimostrare l'asserto o per aggirare il problema rappresentato dagli insiemi eventualmente non disgiunti.
Si vuole provare che l'unione di un numero finito di insiemi numerabili è anch'essa numerabile.
La costruzione a suo tempo proposta da adaBTTLS prevede, se l'ho bene interpretata, di disporre gli elementi dei vari insiemi numerabili in una sorta di matrice infinita avente una infinità numerabile di colonne e tante righe quanti sono gli insiemi numerabili da unire di modo che sulla \( n \)-esima riga siano disposti gli elementi dell'insieme \( n \)-esimo: a questo punto si scorre la matrice per colonne e gli elementi degli insiemi da unire risultano così disposti in successione. Sic stantibus rebus concordo con 17re87: il problema è che se gli insiemi non sono disgiunti tale procedura non solo non definisce un'applicazione biiettiva ma non definisce nemmeno un'applicazione. Il problema presentato da tale procedura (concettualmente simile all'argomento diagonale di Cantor) si aggira "saltando" gli elementi che eventualmente si ripetono, come suggerito dal Pagani-Salsa citato da 17re87. Tale soluzione è intuitivamente più che accettabile. Tuttavia per "aggiustare il tiro" si può fare di meglio che proporre di "saltare" gli elementi che si ripetono. L'asserto si può inoltre provare anche in altro modo.
Iniziamo allora ad "aggiustare il tiro" con qualcosa di meglio del "saltare" gli elementi che eventualmente si ripetono.
Si supponga quindi di aver provato che l'unione di un numero finito \( n \) di insiemi numerabili a due a due disgiunti è numerabile (magari proprio con la costruzione proposta da adaBTTLS). Si lasci ora cadere l'ipotesi che gli insiemi siano a due a due disgiunti. Poiché si sta unendo un numero finito \( n \) di insiemi, è lecito supporre di avere una famiglia di insiemi numerabili indiciata dall'insieme \( I_{n} := \left \{ 1, 2, 3, \ldots, n \right \} \): siano quindi \( X_{1}, X_{2}, X_{3}, \ldots, X_{n} \) gli \( n \) insiemi numerabili da unire. Si ponga allora:
\[
\begin{align*}
&Y_{1} = X_{1} \\
&Y_{2} = X_{2} \setminus X_{1} \\
&Y_{3} = X_{3} \setminus \left \{ X_{1} \cup X_{2} \right \} \\
&\ldots \\
&Y_{n} = X_{n} \setminus \left \{ X_{1} \cup X_{2} \cup \cdots \cup X_{n-1} \right \} \\
\end{align*}
\]
Sono allora evidenti (o per lo meno dovrebbero esserlo: in alternativa li si può facilmente dimostrare) i seguenti fatti:
• la famiglia di insiemi \( \displaystyle \left ( Y_{i} \right )_{i \in I_{n}} \) è una famiglia di insiemi a due a due disgiunti;
• \( \displaystyle \bigcup_{i \in I_{n}} X_{i} = \bigcup_{i \in I_{n}} Y_{i} \);
• \( \forall i \in I_{n}, Y_{i} \) o è finito o è numerabile ed in particolare \( Y_{1} \) è numerabile.
Si considerino allora gli insiemi \( A = \left \{ i \in I_{n} \mid Y_{i} \text{ è numerabile} \right \} \) e \( B = \left \{ i \in I_{n} \mid Y_{i} \text{ è finito} \right \} \); sono evidenti (o per lo meno dovrebbero esserlo: in alternativa li si può facilmente dimostrare) i seguenti fatti:
• \( A \) e \( B \) sono insiemi finiti;
• \( \displaystyle \bigcup_{i \in I_{n}} Y_{i} = \left ( \bigcup_{i \in A} Y_{i} \right ) \cup \left ( \bigcup_{i \in B} Y_{i} \right ) \);
• \( A \neq \varnothing \);
• \( \displaystyle \bigcup_{i \in A} Y_{i} \) è numerabile (essendo l'unione di un numero finito di insiemi numerabili a due a due disgiunti);
• \( \displaystyle \bigcup_{i \in B} Y_{i} \) è finita.
Allora \( \displaystyle \bigcup_{i \in I_{n}} Y_{i} \) è l'unione di un insieme numerabile e di un insieme finito (eventualmente vuoto), sicché, se preliminarmente è stato dimostrato che l'unione di un insieme numerabile e di un insieme finito è numerabile, si conclude che \( \displaystyle \bigcup_{i \in I_{n}} X_{i} = \bigcup_{i \in I_{n}} Y_{i} \) è numerabile.
Si può anche procede in altro modo.
Si dimostra preliminarmente che:
1. dati due insiemi \( S \) e \( T \), se esistono un'applicazione iniettiva \( f \colon S \to T \) ed un'applicazione iniettiva \( g \colon T \to S \), allora esiste un'applicazione biiettiva \( h \colon S \to T \) (questo fatto è noto come Teorema di Cantor-Bernstein-Schröder);
2. \( \mathbb{N} \times \mathbb{N} \) è numerabile.
A questo punto si prova che l'unione di una famiglia numerabile \( \displaystyle \left ( X_{i} \right )_{i \in \mathbb{N}} \) di insiemi numerabili è numerabile. Poiché \( \forall i \in \mathbb{N}, X_{i} \) è numerabile, allora \( \forall i \in \mathbb{N} \) esiste un'applicazione \( \phi_{i} \colon X_{i} \to \mathbb{N} \) biiettiva. Posto \( \displaystyle X = \bigcup_{i \in \mathbb{N}} X_{i} \), si consideri allora l'applicazione \( \phi \colon X \to \mathbb{N} \times \mathbb{N} \) definita ponendo per ogni \( x \in X, \phi(x) = \left ( n_{x}, m_{x} \right ) \) dove:
• \( n_{x} \) è il minimo dell'insieme \( \left \{ i \in \mathbb{N} \mid \exists X_{i} : x \in X_{i} \right \} \);
• \( \displaystyle m_{x} = \phi_{\textstyle n_{x}} (x) \).
Questa applicazione è ben posta ed è iniettiva; infatti:
• ogni \( x \in X \) deve appartenere a qualche \( X_{i} \), quindi per ogni \( x \in X \) si riesce a trovare almeno una coppia \( \displaystyle \left ( n_{x}, m_{x} \right )\);
• il minimo di un insieme è unico, sicché per ogni \( x \in X \), la prima coordinata della coppia \( \displaystyle \left ( n_{x}, m_{x} \right )\) è unica;
• per ogni \( x \in X \) anche la seconda coordinata della coppia \( \displaystyle \left ( n_{x}, m_{x} \right )\) è unica poiché \( m_{x} \) è l'immagine di \( x \) tramite un'applicazione;
• poiché ogni applicazione \( \phi_{i} \) è biiettiva e quindi iniettiva, se due elementi distinti \( x \) e \( y \) di \( X \) sono tali per cui \( n_{x} = n_{y} \), risulta \( m_{x} \neq m_{y} \), sicché \( \phi(x) \neq \phi(y) \) per la seconda coordinata.
Allora esiste un'applicazione iniettiva di \( X \) in \( \mathbb{N} \times \mathbb{N} \) ed essendo \( \mathbb{N} \times \mathbb{N} \) numerabile, esiste allora un'applicazione iniettiva di \( X \) in \( \mathbb{N} \).
Ma \( \mathbb{N} \) è equipotente a ciascuno degli \( X_{i} \), essendo ciascuno degli \( X_{i} \) numerabile: quindi esiste un'applicazione iniettiva di \( \mathbb{N} \) in \( X_{i} \), qualunque sia \( i \in \mathbb{N} \); inoltre ciascuno degli \( X_{i} \) è una parte di \( X \), sicché per ciascuno degli \( X_{i} \) esiste un'applicazione iniettiva (l'immersione) dell'insieme \( X_{i} \) considerato in \( X \). Ma allora esiste un'applicazione iniettiva di \( \mathbb{N} \) in \( X \).
Per il Teorema di Cantor-Bernstein-Schröder, esiste un'applicazione biiettiva di \( X \) in \( \mathbb{N} \).
A questo punto l'asserto da provare è un corollario di quanto appena provato: volendo provare che l'unione della famigli finita di insiemi numerabili \( \displaystyle \left ( Y_{j} \right )_{j \in I_{n}} \) è numerabile occorre e basta prendere la famiglia numerabile di insiemi numerabili \( \displaystyle \left ( X_{i} \right )_{i \in \mathbb{N}} \) dove \( Y_{1} = X_{0}, Y_{2} = X_{1}, Y_{3} = X_{2}, \ldots, Y_{n} = X_{n - 1} \) e \( Y_{n} = X_{m}, \forall m \geq n \).
Ma ovviamente questo non è tutto.
Non è tutto perché per esempio si può ovviare al problema degli insiemi disgiunti anche in un altro modo: se due insiemi \( S \) e \( T \) non sono disgiunti, lo sono invece gli insiemi \( S' = S \times \left \{ 1 \right \} \) e \( T' = T \times \left \{ 2 \right \} \); inoltre \( S \) e \( S' \) sono equipotenti, così come \( T \) e \( T' \). Quindi anziché lavorare con \( S \) e \( T \) si può lavorare con \( S' \) e \( T' \).
Non è tutto perché si potrebbe pensare di provare prima che l'unione di due insiemi numerabili è numerabile e poi andare per induzione sul numero degli insiemi: essendo ovvio il passo base (l'unione di un solo insieme numerabile è numerabile perché coincide con l'insieme numerabile stesso), assunta l'ipotesi induttiva (l'unione di \( n \) insiemi numerabili è numerabile), allora l'unione di \( n + 1 \) insiemi numerabili si scrive come \( \left ( X_{1} \cup X_{2} \cup \cdots \cup X_{n} \right ) \cup X_{n+1} \), al che \( \left ( X_{1} \cup X_{2} \cup \cdots \cup X_{n} \right ) \) è numerabile per ipotesi induttiva e la conclusione segue per mezzo di quanto preliminarmente provato.
Il punto si sposta allora su come provare che l'unione di due insiemi numerabili è numerabile. Le strategie sono sempre le stesse: o si passa per gli insiemi disgiunti prima e per quelli non disgiunti poi, oppure si procede come segue:
1. si prova preliminarmente che dati due insiemi \( S \) e \( T \), esiste un'applicazione iniettiva di \( S \) in \( T \) se e solo se esiste un'applicazione suriettiva di \( T \) in \( S \);
2. si dimostra preliminarmente che l'insieme \( \mathbb{N} \times \left \{ 0, 1 \right \} \) è numerabile;
3. a questo punto, dati due insiemi numerabili \( X \) e \( Y \), poiché essi sono numerabili, esistono due applicazioni \( \phi_{X} \colon X \to \mathbb{N} \) e \( \phi_{Y} \colon Y \to \mathbb{N} \) entrambe biiettive;
4. la biiettività (in particolare la suriettività) di \( \phi_{X} ( \cdot ) \) e \( \phi_{Y} ( \cdot ) \) garantisce che l'applicazione \( \phi \colon \mathbb{N} \times \left \{ 0, 1 \right \} \to X \cup Y \) definita ponendo \( \phi ( n, 0) = \phi_{X}(n) \) e \( \phi ( n, 1) = \phi_{Y}(n) \) è suriettiva, sicché esiste un'applicazione iniettiva di \( X \cup Y \) in \( \mathbb{N} \times \left \{ 0, 1 \right \} \) e quindi in \( \mathbb{N} \);
5. l'inclusione di \( X \) (o anche di \( Y \)) in \( X \cup Y \) garantisce l'esistenza di un'applicazione iniettiva di \( X \) in \( X \cup Y \) e, poiché \( X \) è numerabile, l'esistenza di un'applicazione iniettiva di \( \mathbb{N} \in X \cup Y \);
6. per il Teorema di Cantor-Bernstein-Schröder si conclude.
Insomma: esistono vari modi per dimostrare l'asserto o per aggirare il problema rappresentato dagli insiemi eventualmente non disgiunti.
Ops...mi ero perso questo bel papiro!!! 
Per prima cosa G.D. vorrei ringraziarti per il tempo dedicato alla questione. Leggerò con attenzione tutto il messaggio.
Per prima cosa G.D. vorrei ringraziarti per il tempo dedicato alla questione. Leggerò con attenzione tutto il messaggio.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo