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
Sono solamente dei suggerimenti...
1) se n è il numero di elementi dell'insieme finito, metti l'elemento $r$-esimo dell'insieme finito nel posto $r$-esimo e l'elemento $s$-esimo dell'insieme finito nel posto $(r+s)$-esimo
2) se $n$ è il numero di insiemi numerabili, metti l'elemento $r$-esimo dell'insieme $s$-esimo nel posto $(s+rn)$-simo
3) usa lo stesso metodo usato per $QQ$, in fondo quello che stai cercando di dimostrare è che $ZZ\timesZZ$ è numerabile.
1) se n è il numero di elementi dell'insieme finito, metti l'elemento $r$-esimo dell'insieme finito nel posto $r$-esimo e l'elemento $s$-esimo dell'insieme finito nel posto $(r+s)$-esimo
2) se $n$ è il numero di insiemi numerabili, metti l'elemento $r$-esimo dell'insieme $s$-esimo nel posto $(s+rn)$-simo
3) usa lo stesso metodo usato per $QQ$, in fondo quello che stai cercando di dimostrare è che $ZZ\timesZZ$ è numerabile.
"vict85":Scusa, ma intendi: fare questo nell'insieme unione?
Sono solamente dei suggerimenti...
1) se n è il numero di elementi dell'insieme finito, metti l'elemento $r$-esimo dell'insieme finito nel posto $r$-esimo e l'elemento $s$-esimo dell'insieme finito nel posto $(r+s)$-esimo
Esercizio 1)
Ricordiamo che un inseme numerabile è un insieme che è possibile mettere in corrispondenza biunivoca con $NN$. Sia $U$ un insieme numerabile, per ipotesi esiste $f: U rightarrow NN$ biunivoca. Sia anche $W={x_1,...,x_k}$, allora abbiamo che $UuuW$ è numerabile.
Costruiamo la biezione nella seguente maniera:
$g(t)={(x_t text{ con t<=k}),(f(t-k) text{ con t>k}):}$
$g: UuuW rightarrow NN$ è una biezione ovviamente, quindi $UuuW$ è numerabile!
Ricordiamo che un inseme numerabile è un insieme che è possibile mettere in corrispondenza biunivoca con $NN$. Sia $U$ un insieme numerabile, per ipotesi esiste $f: U rightarrow NN$ biunivoca. Sia anche $W={x_1,...,x_k}$, allora abbiamo che $UuuW$ è numerabile.
Costruiamo la biezione nella seguente maniera:
$g(t)={(x_t text{ con t<=k}),(f(t-k) text{ con t>k}):}$
$g: UuuW rightarrow NN$ è una biezione ovviamente, quindi $UuuW$ è numerabile!
esercizio 2)
$A_1={a_(11), a_(12), a_(13), ... }, A_2={a_(21), a_(22), a_(23), ... }, ... , A_n={a_(n1), a_(n2), a_(n3), ... }$
$f: (A_1uuA_2uu...uuA_n) -> NN " t. c. " f(a_(11))=1, f(a_(12))=n+1, f(a_(13))=2n+1, ... , f(a_(21))=2, f(a_(22))=n+2, ... , f(a_(n1))=n, f(a_(n2))=2n, ... $
naturalmente è una biiezione se e solo se gli insiemi $A_i, i in {1, 2, ... , n}$ sono disgiunti. ma il discorso vale anche se è solo suriettiva (anche nel processo di diagonalizzazione di Cantor le frazioni non sono tutte diverse tra loro.
spero sia chiaro.
esercizio 3)
in maniera analoga (sia alla soluzione precedente sia alla diagonalizzazione di Cantor), puoi immaginare gli elementi dell'unione di un'infinità numerabile di insiemi numerabili, che per il fatto stesso di essere numerabili possono essere "ordinati" sia tra loro sia per quanto riguarda gli elementi di ciascuno, scritti in una tabella (matrice) infinita, però con un "elemento" iniziale:
$A=[ (a_(11), a_(12), a_(13), ... ), (a_(21), a_(22), a_(23), ... ), (................) ]$
e si può procedere "a zig zag" nell'"ordinare" gli elementi, come nel processo di diagonalizzazione di Cantor.
spero di essere stata utile. ciao.
$A_1={a_(11), a_(12), a_(13), ... }, A_2={a_(21), a_(22), a_(23), ... }, ... , A_n={a_(n1), a_(n2), a_(n3), ... }$
$f: (A_1uuA_2uu...uuA_n) -> NN " t. c. " f(a_(11))=1, f(a_(12))=n+1, f(a_(13))=2n+1, ... , f(a_(21))=2, f(a_(22))=n+2, ... , f(a_(n1))=n, f(a_(n2))=2n, ... $
naturalmente è una biiezione se e solo se gli insiemi $A_i, i in {1, 2, ... , n}$ sono disgiunti. ma il discorso vale anche se è solo suriettiva (anche nel processo di diagonalizzazione di Cantor le frazioni non sono tutte diverse tra loro.
spero sia chiaro.
esercizio 3)
in maniera analoga (sia alla soluzione precedente sia alla diagonalizzazione di Cantor), puoi immaginare gli elementi dell'unione di un'infinità numerabile di insiemi numerabili, che per il fatto stesso di essere numerabili possono essere "ordinati" sia tra loro sia per quanto riguarda gli elementi di ciascuno, scritti in una tabella (matrice) infinita, però con un "elemento" iniziale:
$A=[ (a_(11), a_(12), a_(13), ... ), (a_(21), a_(22), a_(23), ... ), (................) ]$
e si può procedere "a zig zag" nell'"ordinare" gli elementi, come nel processo di diagonalizzazione di Cantor.
spero di essere stata utile. ciao.
grazie a tutti, qualcosa l'avevo intuita ma mi mancavano dei passaggi fondamentali
prego.
mi ricollego a questa discussione un po vecchia e in particolare al seguente messaggio che riguarda l'esercizio 2):
Bene, nel caso in cui gli insiemi numerabili non siano disgiunti come funziona la cosa? Cioè, come si dimostra che vi è una corrispondenza biunivoca e quindi un'applicazione invertibile tra $N$ e l'insieme unione (condizione affinchè l'insieme unione sia numerabile)? E' forse corretto dire che se vale nel caso di insiemi numerabili disgiunti allora, a maggior ragione, deve valere anche nel caso di una famiglia di insieme numerabili non necessariamente disgiunti? In altre parole, è intuitivo dire che SE l'unione di una famiglia finita non vuota di insiemi numerabili DISGIUNTI è numerabile allora è numerabile anche l'unione di una famiglia finita non vuota di insiemi numerabili non necessariamente disgiunti, ma come si dimostra lo è un po meno. Infatti nella dimostrazione (nel caso di insiemi disgiunti) viene creata una successione contenente tutti gli elementi di tutti gli insiemi della famiglia, in cui ognuno occupa un determinato "posto". Ma, nel caso in cui due insiemi della famiglia dovessero avere un elemento in comune, questo elemento quale posto occuperebbe nella successione?
"adaBTTLS":
esercizio 2)
A1={a11,a12,a13,...},A2={a21,a22,a23,...},...,An={an1,an2,an3,...}
f:(A1∪A2∪...∪An)→N t. c. f(a11)=1,f(a12)=n+1,f(a13)=2n+1,...,f(a21)=2,f(a22)=n+2,...,f(an1)=n,f(an2)=2n,...
naturalmente è una biiezione se e solo se gli insiemi Ai,i∈{1,2,...,n} sono disgiunti. ma il discorso vale anche se è solo suriettiva (anche nel processo di diagonalizzazione di Cantor le frazioni non sono tutte diverse tra loro.
spero sia chiaro.
Bene, nel caso in cui gli insiemi numerabili non siano disgiunti come funziona la cosa? Cioè, come si dimostra che vi è una corrispondenza biunivoca e quindi un'applicazione invertibile tra $N$ e l'insieme unione (condizione affinchè l'insieme unione sia numerabile)? E' forse corretto dire che se vale nel caso di insiemi numerabili disgiunti allora, a maggior ragione, deve valere anche nel caso di una famiglia di insieme numerabili non necessariamente disgiunti? In altre parole, è intuitivo dire che SE l'unione di una famiglia finita non vuota di insiemi numerabili DISGIUNTI è numerabile allora è numerabile anche l'unione di una famiglia finita non vuota di insiemi numerabili non necessariamente disgiunti, ma come si dimostra lo è un po meno. Infatti nella dimostrazione (nel caso di insiemi disgiunti) viene creata una successione contenente tutti gli elementi di tutti gli insiemi della famiglia, in cui ognuno occupa un determinato "posto". Ma, nel caso in cui due insiemi della famiglia dovessero avere un elemento in comune, questo elemento quale posto occuperebbe nella successione?
Il fatto che gli insiemi numerabili della famiglia finita sui cui si va a fare l'unione siano disgiunti non è determinante ai fini della validità dell'asserto che infatti vale e si dimostra in generale.
Io se devo essere sincero la costruzione proposta a suo tempo da adaBTTLS non credo di averla intesa correttamente perché, da quello che ho capito, mi pare che l'ipotesi che gli insiemi siano disgiunti sia determinante addirittura per fare in modo che quella costruzione sia una funzione.
Io se devo essere sincero la costruzione proposta a suo tempo da adaBTTLS non credo di averla intesa correttamente perché, da quello che ho capito, mi pare che l'ipotesi che gli insiemi siano disgiunti sia determinante addirittura per fare in modo che quella costruzione sia una funzione.
Io se devo essere sincero la costruzione proposta a suo tempo da adaBTTLS non credo di averla intesa correttamente perché, da quello che ho capito, mi pare che l'ipotesi che gli insiemi siano disgiunti sia determinante addirittura per fare in modo che quella costruzione sia una funzione.
Esattamente, anche a me è venuto lo stesso dubbio, e anche secondo me l'ipotesi di insiemi disgiunti è necessaria affinché la $f$ costruita da adaBTTLS sia appunto un'applicazione.
A questo punto ho due questioni:
1) come si dimostra IN GENERALE l'enunciato?
2) è corretto il seguente ragionamento?
Fissato un $K\inN^+$, consideriamo una famiglia finita non vuota di insiemi numerabili $X_1,...,X_K$. Essendo numerabili possiamo rappresentare gli insiemi della famiglia nel modo seguente:
$X_1={x_1,_0, x_1,_1, x_1,_2,...} ;....;X_K={x_K,_0, x_K,_1, x_K,_2,...}$
In generale, $x_s,_n$ rappresenta l'elemento $n-esimo$ dell'insieme $s-esimo$ della famiglia, per ogni $s\in{1,2,...,K}$, e per ogni $n\inN$.
Ora, definisco l'insieme unione, che chiamo $A$, in questo modo: $A=X_1\cup...\cupX_K={x_s,_n : s\in{1,...,K}$ e $n\inN}$.
Infine, per mostrare che l'insieme $A$ è numerabile devo definire un'applicazione invertibile da $A$ in $N$: $g:A\rightarrowN$. A me è venuta questa:
$g={x_s,_n\mapstog(x_s,_n):A\rightarrowN}$, dove $g(x_s,_n)=[nK+(s-1)]$
Riguardo a questo ragionamento ho tre dubbi:
a) implicitamente ho supposto che gli insiemi siano disgiunti e quindi torniamo al problema iniziale
b) la definizione formale dell'insieme $A$ può essere ritenuta corretta?
c) la definizione della funzione $g$ è corretta? Nel caso in cui sia corretta, essa è sicuramente una biiezione tra $A$ e $N$? Cioè che sia una corrispondenza biunivoca, e quindi un'applicazione invertibile, è evidente e intuitivo ma richiede una dimostrazione che sia proprio così?
Adesso sono di fretta, quindi mi limito all'essenziale.
1. La dimostrazione si può produrre in diversi modi: per induzione, costruendo una opportuna applicazione dall'unione della famiglia a \( \mathbb{N}_{0} \) oppure a partire dal fatto che l'unione di una famiglia numerabile di insiemi numerabili è numerabile.
2a-b-c. Mi pare proprio che anche questa strada usi il fatto che gli insiemi sono disgiunti. La definizione dell'unione non è formalmente corretta perché non si capisce da dove si prendano gli elementi \( x_{s,n} \). Ovviamente che l'applicazione costruita sia una biiezione va provato e non lasciato all'intuito.
1. La dimostrazione si può produrre in diversi modi: per induzione, costruendo una opportuna applicazione dall'unione della famiglia a \( \mathbb{N}_{0} \) oppure a partire dal fatto che l'unione di una famiglia numerabile di insiemi numerabili è numerabile.
2a-b-c. Mi pare proprio che anche questa strada usi il fatto che gli insiemi sono disgiunti. La definizione dell'unione non è formalmente corretta perché non si capisce da dove si prendano gli elementi \( x_{s,n} \). Ovviamente che l'applicazione costruita sia una biiezione va provato e non lasciato all'intuito.
Adesso sono di fretta, quindi mi limito all'essenziale.
1. La dimostrazione si può produrre in diversi modi: per induzione, costruendo una opportuna applicazione dall'unione della famiglia a N0 oppure a partire dal fatto che l'unione di una famiglia numerabile di insiemi numerabili è numerabile.
2a-b-c. Mi pare proprio che anche questa strada usi il fatto che gli insiemi sono disgiunti. La definizione dell'unione non è formalmente corretta perché non si capisce da dove si prendano gli elementi xs,n. Ovviamente che l'applicazione costruita sia una biiezione va provato e non lasciato all'intuito.
Riguardo alla definizione dell'insieme unione: si riflettendoci bene non è formalmente corretta perchè devo dire che gli elementi $x_s,_n$ appartengono a qualche insieme della famiglia. Potrei allora definire $A$ in questo modo:
$A={x_s,_n: x_s,_n\inX_s$ e $(s\in{1,...,K}$ e $n\inN)}$
Può essere un modo corretto?
Per quanto riguarda la dimostrazione del punto c) vedo di lavorarci un momentino. Comunque G.D., quando hai più tempo se ti va possiamo approfondire il discorso?!
"17re87":
Comunque G.D., quando hai più tempo se ti va possiamo approfondire il discorso?!
Certamente. Ci mancherebbe. E poi ci sono anche altri utenti che possono intervenire, quindi sicuramente non mancherà l'occasione.
Ho visto in varie dispense e in particolare sul libro "Analisi 1" di Pagani e Salsa che per dimostrare che l'unione di una famiglia finita non vuota di insiemi numerabili è numerabile viene utilizzato, come voi ben sapete, il procedimento diagonale di Cantor. Quindi viene costruita una matrice in cui il numero di righe è pari al numero (finito) di insiemi che costituiscono la famiglia, in cui l'elemento di posto $(i,j)$ rappresenta l'elemento $j-esimo$ dell'insieme $i-esimo$. Dunque, il procedimento diagonale di Cantor indica in quale modo possono essere elencati gli elementi dell'insieme-unione in una successione. A me interessa il caso in cui gli insiemi della famiglia siano non necessariamente disgiunti. Nella dimostrazione del suddetto libro viene specificato che nel caso in cui gli insiemi non siano disgiunti, occorre "saltare" (nel conteggio) gli elementi già comparsi una volta.
La mia domanda è: questo è l'unico modo di trattare la dimostrazione del teorema tenendo conto esplicitamente del caso di insiemi non disgiunti??
La mia domanda è: questo è l'unico modo di trattare la dimostrazione del teorema tenendo conto esplicitamente del caso di insiemi non disgiunti??
Rispondendo alla tua ultima domanda: ovviamente no.
"G.D.":
Rispondendo alla tua ultima domanda: ovviamente no.
riesci a prevedere la mia prossima domanda?????
Vuoi sapere qual è il modo di trattare la questione senza distinguere tra il caso in cui gli insiemi sono disgiunti ed il caso in cui non lo sono.
"G.D.":
Vuoi sapere qual è il modo di trattare la questione senza distinguere tra il caso in cui gli insiemi sono disgiunti ed il caso in cui non lo sono.
esatto
. In realtà ciò che mi interessa maggiormente e trattare la questione nel caso in cui non siano disgiunti. Ah un'altra cosa, la correzione che ho fatto due o tre post fa, in merito alla definizione dell'insieme unione, a tuo giudizio, è giusta! Per quanto riguarda la prima domanda mi accontento anche di qualche dritta, e vedere se riesco da solo.
grazie G.D.!
Allora. Io credo che in questo topic ci siano un bel po' di cose da sistemare perché la questione pare banale ma non lo è. Non tanto per la questione in sé quanto piuttosto per le questioni a cui la questione in oggetto è collegata. E mano a mano che andremo avanti te ne renderai conto. E in verità ti dico anche che proprio prima che tu intervenissi stasera io stavo anche scrivendo una risposta ma ne stava venendo fuori un post di una lunghezza indicibile in cui, proprio a causa della eccessiva lunghezza dell'intervento stesso, quello che scrivevo era scritto male, sicché stavo pensando di cambiare approccio e di chiedere a te da dove volevi iniziare.
Cominciamo allora dalla questione più semplice. Come si definisce l'unione di una famiglia di insiemi.
Innanzitutto quanto sai di Teoria degli Insiemi?
Cominciamo allora dalla questione più semplice. Come si definisce l'unione di una famiglia di insiemi.
Innanzitutto quanto sai di Teoria degli Insiemi?
Allora, di teoria degli insiemi, al momento, conosco sufficientemente quella ingenua. Tra qualche tempo, quando avrò finito di studiarmi alcune cose, studierò quella assiomatica.
Per cui, quando leggo "famiglia di insiemi" mi viene in mente un insieme, i cui elementi sono costituiti da insiemi. Dunque, per unione di una famiglia di insiemi intendo un insieme costituito dagli elementi che appartengono a qualche insieme della famiglia.
Formalmente: sia $F$ una famiglia qualunque di insiemi. L'unione della famiglia $F$, è l'insieme $\bigcup_(X\inF)X={x:(\existsX: X\inF$ e $x\inX)}$.
Per cui, quando leggo "famiglia di insiemi" mi viene in mente un insieme, i cui elementi sono costituiti da insiemi. Dunque, per unione di una famiglia di insiemi intendo un insieme costituito dagli elementi che appartengono a qualche insieme della famiglia.
Formalmente: sia $F$ una famiglia qualunque di insiemi. L'unione della famiglia $F$, è l'insieme $\bigcup_(X\inF)X={x:(\existsX: X\inF$ e $x\inX)}$.
tornando velocemente al ragionamento di qualche post precedente, avrei potuto definire l'insieme unione della famiglia, che avevo indicato con $A$, come segue. Data una famiglia finita non vuota di insiemi numerabili, $F$, definisco l'insieme unione come:
$A={x_s,_n:(\existsX_s:X_s\inF$ e $x_s,_n\inX_s)$ e $(s\in{1,...,K}$ e $n\inN)}$.
Tuttavia, a)mi sembrava un abuso di notazione, b)in tal modo rimane il fatto che sto implicitamente assumendo che gli insiemi della famiglia siano disgiunti.
$A={x_s,_n:(\existsX_s:X_s\inF$ e $x_s,_n\inX_s)$ e $(s\in{1,...,K}$ e $n\inN)}$.
Tuttavia, a)mi sembrava un abuso di notazione, b)in tal modo rimane il fatto che sto implicitamente assumendo che gli insiemi della famiglia siano disgiunti.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo