Teorema sulla numerabilità di sottoinsiemi finiti
Salve a tutti.
Premetto di essere un neofita di ritorno, per la matematica, sono al secondo anno di una specialistica in Filosofia, e devo sostenere un esame di Teoria della Calcolabilità. Ho un problema con un teorema che dovrei dimostrare, e chiedo il vostro aiuto, se vorrete dedicarmi tempo...
Il teorema è il seguente:
"Se S è un insieme numerabile, il numero cardinale dell'insieme Fs={x | x ⊆ S e x è un insieme finito} è Aleph-0"
Il che equivale a dire, mi sembra di capire, che devo dimostrare che l'insieme che contiene tutti i sottoinsiemi finiti di un insieme numerabile, è numerabile anch'esso. Come potrei dimostrarlo nella maniera più semplice possibile? vi ringrazio in anticipo.
Edit: So che alla fine devo arrivare alla conclusione che |Fs|$>=$ |aleph-0| ;
che |S| $>=$ |Fs|
E di conseguenza che |Fs|=|aleph-0|
Ho pensato che i sottoinsiemi finiti di un insieme numerabile saranno almeno aleph-0, in quanto contengono almeno tutti i singoletti dell'insieme, più tutte le coppie, triple, ecc ecc, n-uple. Questo basta a dimostrare che
|Fs| $>=$ |aleph-0| ?
Non so invece come muovermi per la seconda parte...
Premetto di essere un neofita di ritorno, per la matematica, sono al secondo anno di una specialistica in Filosofia, e devo sostenere un esame di Teoria della Calcolabilità. Ho un problema con un teorema che dovrei dimostrare, e chiedo il vostro aiuto, se vorrete dedicarmi tempo...
Il teorema è il seguente:
"Se S è un insieme numerabile, il numero cardinale dell'insieme Fs={x | x ⊆ S e x è un insieme finito} è Aleph-0"
Il che equivale a dire, mi sembra di capire, che devo dimostrare che l'insieme che contiene tutti i sottoinsiemi finiti di un insieme numerabile, è numerabile anch'esso. Come potrei dimostrarlo nella maniera più semplice possibile? vi ringrazio in anticipo.
Edit: So che alla fine devo arrivare alla conclusione che |Fs|$>=$ |aleph-0| ;
che |S| $>=$ |Fs|
E di conseguenza che |Fs|=|aleph-0|
Ho pensato che i sottoinsiemi finiti di un insieme numerabile saranno almeno aleph-0, in quanto contengono almeno tutti i singoletti dell'insieme, più tutte le coppie, triple, ecc ecc, n-uple. Questo basta a dimostrare che
|Fs| $>=$ |aleph-0| ?
Non so invece come muovermi per la seconda parte...
Risposte
Non sono molto esperto di queste cose, ma procederei in modo un po' diverso.
E' noto (se non è noto basta molto poco per dimostrarlo) che unione numerabile di insiemi numerabili è anch'essa numerabile.
Dunque $\forall n \in \NN$ consideriamo $A_n = \{ X \subset S $ tale che $|X| = n \}$. E' immediato che ognuno di questi $A_n$ è numerabile.
Inoltre $Fs = \bigcup _{n \in \NN} A_n $.
In questo modo si conclude che anche $Fs$ è numerabile.
Proprio perché non mi sono mai occupato in modo approfondito di questi argomenti, non garantisco che la dimostrazione sia proprio esatta, ma penso che come argomento sia più facile di quello proposto da te.
Si attendono critiche e lamentele XD
E' noto (se non è noto basta molto poco per dimostrarlo) che unione numerabile di insiemi numerabili è anch'essa numerabile.
Dunque $\forall n \in \NN$ consideriamo $A_n = \{ X \subset S $ tale che $|X| = n \}$. E' immediato che ognuno di questi $A_n$ è numerabile.
Inoltre $Fs = \bigcup _{n \in \NN} A_n $.
In questo modo si conclude che anche $Fs$ è numerabile.
Proprio perché non mi sono mai occupato in modo approfondito di questi argomenti, non garantisco che la dimostrazione sia proprio esatta, ma penso che come argomento sia più facile di quello proposto da te.
Si attendono critiche e lamentele XD
In parte l'idea l'hai già avuta.
Fissa un intero $n$ e chiama $P_n$ l'insieme delle parti con esattamente $n$ elementi (se $P_1$ sono tutti i singoletti, $P_2$ le coppie e così via).
Vedi che ogni $P_n$ ha cardinalità numerabile (mi pare che questo ti tornasse)
Ora l'insieme delle parti finite altro non è che l'unione di tutti i $P_n$, al variare di $n$ in $NN$. Dovresti ora sapere che unione numerabile di numerabili è numerabile....
OOPS sono stato preceduto (egregiamente).
Fissa un intero $n$ e chiama $P_n$ l'insieme delle parti con esattamente $n$ elementi (se $P_1$ sono tutti i singoletti, $P_2$ le coppie e così via).
Vedi che ogni $P_n$ ha cardinalità numerabile (mi pare che questo ti tornasse)
Ora l'insieme delle parti finite altro non è che l'unione di tutti i $P_n$, al variare di $n$ in $NN$. Dovresti ora sapere che unione numerabile di numerabili è numerabile....
OOPS sono stato preceduto (egregiamente).
Capito perfettamente, vi ringrazio tantissimo!
Ma non è possibile che l'unione di tutti i Pn (ovvero l'insieme Fs) sia maggiore o uguale ad Aleph-0 e che per questo sia necessario dimostrare che |S| ≥ |Fs| , per poterne concludere che |Fs|=|aleph-0| ?
Non lo chiedo perchè non mi convince la spiegazione (anzi, mi sembra perfetta), ma perchè nel mio testo è presente unicamente la soluzione (per il professore significa dimostrazione, vallo a capire...), ed è riportato:
|S| ≥ |Fs|≥ aleph-0 = aleph-0
Ha senso? è ridondante?è sbagliato?
Ma non è possibile che l'unione di tutti i Pn (ovvero l'insieme Fs) sia maggiore o uguale ad Aleph-0 e che per questo sia necessario dimostrare che |S| ≥ |Fs| , per poterne concludere che |Fs|=|aleph-0| ?
Non lo chiedo perchè non mi convince la spiegazione (anzi, mi sembra perfetta), ma perchè nel mio testo è presente unicamente la soluzione (per il professore significa dimostrazione, vallo a capire...), ed è riportato:
|S| ≥ |Fs|≥ aleph-0 = aleph-0
Ha senso? è ridondante?è sbagliato?
Il tuo testo è un po' criptico ....
Forse lui parte da un enunciato un po' diverso, che potrebbe essere:
(*) Se per ogni $n$ si ha $|A_n|\leq\aleph_0$, allora $|\bigcup_{n\in NN} A_n|\leq\aleph0$.
Se usi questo devi poi garantirti che ad $\aleph_0$ arrivi veramente; per questo ti basta notare che in $FS$ ci sono i singoletti $S$ da cui $|FS|geq|S|=\aleph_0$.
Questa seconda parte è abbastanza ovvia, quella più difficile è la precedente (*), che ti garantisce che non vai OLTRE $\aleph_0$, cioè che $|Fs|leq\aleph_0$.
EDIT ho riletto il tuo ultimo messaggio e non ho capito bene chi è $S$ (prima pensavo che fossero i singoletti - ma poi ho visto che la tua disuguaglianza va nell'altro verso ...)
EDIT 2 Ho visto che $S$ è l'insieme di partenza (che ovviamenta ha la stessa cardinalità dei singoletti e quindi il mio discorso sopra va bene lo stesso). Non so proprio come il tuo libro
possa affermare "tout court" che $|S|\geq|FS|$ ...
Forse lui parte da un enunciato un po' diverso, che potrebbe essere:
(*) Se per ogni $n$ si ha $|A_n|\leq\aleph_0$, allora $|\bigcup_{n\in NN} A_n|\leq\aleph0$.
Se usi questo devi poi garantirti che ad $\aleph_0$ arrivi veramente; per questo ti basta notare che in $FS$ ci sono i singoletti $S$ da cui $|FS|geq|S|=\aleph_0$.
Questa seconda parte è abbastanza ovvia, quella più difficile è la precedente (*), che ti garantisce che non vai OLTRE $\aleph_0$, cioè che $|Fs|leq\aleph_0$.
EDIT ho riletto il tuo ultimo messaggio e non ho capito bene chi è $S$ (prima pensavo che fossero i singoletti - ma poi ho visto che la tua disuguaglianza va nell'altro verso ...)
EDIT 2 Ho visto che $S$ è l'insieme di partenza (che ovviamenta ha la stessa cardinalità dei singoletti e quindi il mio discorso sopra va bene lo stesso). Non so proprio come il tuo libro
possa affermare "tout court" che $|S|\geq|FS|$ ...
Scusate la mia ignoranza:
Poniamo di fissare un intero n e chiamare Pn l'insieme delle parti con esattamente n elementi:
L'insieme Fs sarà allora l'unione di tutti i Pn al variare di n, qui ci siamo, quindi
Fs:P1uP2uP3u...uPn
Ma P1, per esempio, avendo cardinalità 1, non conterrà un solo elemento? e quindi di P1 in realtà non ce ne sarà uno solo, ma n?
Poniamo di fissare un intero n e chiamare Pn l'insieme delle parti con esattamente n elementi:
L'insieme Fs sarà allora l'unione di tutti i Pn al variare di n, qui ci siamo, quindi
Fs:P1uP2uP3u...uPn
Ma P1, per esempio, avendo cardinalità 1, non conterrà un solo elemento? e quindi di P1 in realtà non ce ne sarà uno solo, ma n?
"Edwardbloom":
Scusate la mia ignoranza:
Poniamo di fissare un intero n e chiamare Pn l'insieme delle parti con esattamente n elementi:
L'insieme Fs sarà allora l'unione di tutti i Pn al variare di n, qui ci siamo, quindi
Fs:P1uP2uP3u...uPn
Ma P1, per esempio, avendo cardinalità 1, non conterrà un solo elemento? e quindi di P1 in realtà non ce ne sarà uno solo, ma n?
Attenzione $P_1$ non ha cardinalità $1$, dato che contiene tutti i possiblili singoletti - in effetti $|P_1|=|S|$ (ora che ho capito chi è $S$ ....).
Infatti per ogni elemento $s$ in $S$ il singoletto ${s}$ è un elemento di $P_1$.
Se $|S|=\aleph_0$ anche $|P_1|=\aleph_0$ e tanto più avranno cardinalità infinita $P_2,P_3,...$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo