Cardinalità del continuo
Ciao a tutti. Vi chiedo un aiuto per capire la dimostrazione del fatto che la cardinalità continua di $ R $ è maggiore di quella numerabile. La versione che riporta il mio testo è la seguente:
I miei dubbi riguardano principalmente i due punti evidenziati:
1) riguardo il primo punto (se fosse $ Card(N) = Card(R) $ allora avremmo $ [0, 1) $ numerabile), assumendo l'ipotesi avremmo sicuramente una g biunivoca da N a R, ma cosa c'entra $ [0, 1) $?
2) riguardo il secondo punto mi chiedo a cosa corrisponda $ Cn(f(n − 1)) $ quando non abbiamo neppure definito la legge di f.
Grazie
I miei dubbi riguardano principalmente i due punti evidenziati:
1) riguardo il primo punto (se fosse $ Card(N) = Card(R) $ allora avremmo $ [0, 1) $ numerabile), assumendo l'ipotesi avremmo sicuramente una g biunivoca da N a R, ma cosa c'entra $ [0, 1) $?
2) riguardo il secondo punto mi chiedo a cosa corrisponda $ Cn(f(n − 1)) $ quando non abbiamo neppure definito la legge di f.
Grazie
Risposte
1) Se un sottoinsieme di un insieme non è numerabile neanche l'insieme completo può esserlo. Si lavora con \([0, 1)\) perché è più pratico.
2) Non ha importanza la \(f\colon \mathbb{N}\to\mathbb{R}\) scelta, quel metodo trova sempre un elemento che non appartiene a \(Im(f)\).
2) Non ha importanza la \(f\colon \mathbb{N}\to\mathbb{R}\) scelta, quel metodo trova sempre un elemento che non appartiene a \(Im(f)\).
"vict85":
1) Se un sottoinsieme di un insieme non è numerabile neanche l'insieme completo può esserlo. Si lavora con \([0, 1)\) perché è più pratico.
Non mi è molto chiaro. A me è stata definita la numerabilità come $ Card(N) $, e stando al tuo ragionamento il sottoinsieme $ {1, 2} $ di N deve avere stessa cardinalità di N, ma è chiaro che non esiste una funzione biunivoca da N a $ {1, 2} $.
"vict85":
2) Non ha importanza la \(f\colon \mathbb{N}\to\mathbb{R}\) scelta, quel metodo trova sempre un elemento che non appartiene a \(Im(f)\).
Ok. Proverò ora ad essere più esplicito
dato che quel passaggio (che è il fulcro della dimostrazione ovviamente) non mi è chiaro per nulla, ti chiedo di fornirmi qualche esempio, o semplicemente di esplicitarmi il ragionamento un po' meglio.
Ti pare la stessa scrittura? Paragoni $[0,1)$ con ${1, 2}$ ovvero un intervallo di numeri reali (e quindi un insieme con infiniti elementi) con un insieme (non un intervallo) con due elementi (ovvero un insieme di cardinalità finita).
È possibile mettere in corrispondenza biunivoca l'insieme dei numeri reali $RR$ con l'intervallo $[0,1)$.
Ciò significa che hanno la stessa cardinalità.
Provaci.
È possibile mettere in corrispondenza biunivoca l'insieme dei numeri reali $RR$ con l'intervallo $[0,1)$.
Ciò significa che hanno la stessa cardinalità.
Provaci.
"axpgn":
Ti pare la stessa scrittura? Paragoni $[0,1)$ con ${1, 2}$ ovvero un intervallo di numeri reali (e quindi un insieme con infiniti elementi) con un insieme (non un intervallo) con due elementi (ovvero un insieme di cardinalità finita).
È possibile mettere in corrispondenza biunivoca l'insieme dei numeri reali $RR$ con l'intervallo $[0,1)$.
Ciò significa che hanno la stessa cardinalità.
Provaci.
D'accordo. Dunque mi stai dicendo che ogni sottoinsieme infinito di un insieme numerabile è a sua volta numerabile? (ovviamente vale lo stesso per la cardinalità continua immagino).
Comunque ho provato così:
Definisco $ {x_n}_(x>=1) $ con $ x_(n+1)=x_n/2 $ e $ x_0=1/2 $.
Definisco $ S(n): mathbb(N) rarr (0;1) $ t.c. $ S(n)=sum_(k=0)^(n)(x_k) $. Ora trovo la funzione biunivoca $ f: (0;1) rarr [0;1) $ che ha legge: $ f(x)={ ( x if x !inIm(S) ),(x-x_n if x=S(n)):} $
(per qualche $ n in mathbb(N) $).
Definisco ora $ g: mathbb(R) rarr (0;1) $ t.c. $ g(x)=1/pi*arctan(x) +1/2 $. Noto che $ f @ g: mathbb(R) rarr [0;1) $ è biunivoca.
Riguardo la costruzione di f ho cercato aiuto online, non credo che altrimenti ci sarei mai arrivato (e di sicuro esisteranno anche metodi più semplici del mio). Comunque nel caso in cui avessi sbagliato qualche particolare di notazione o linguaggio vi prego di correggermi.
Dunque (assumendo che il mio ragionamento sia corretto) esiste una f biunivoca da R a $ [0;1) $, quindi i due hanno stessa cardinalità, dunque basta dimostrare che $ Card(mathbb(N)) != Card([0;1)) $. Chiaro
"ProPatria":
D'accordo. Dunque mi stai dicendo che ogni sottoinsieme infinito di un insieme numerabile è a sua volta numerabile? (ovviamente vale lo stesso per la cardinalità continua immagino).
No, \(\mathbb{N}\) e \(\mathbb{Q}\) sono sottoinsiemi infiniti e numerabili di \(\mathbb{R}\). Allo stesso modo, \(\mathbb{R}\) possiede sottoinsiemi che hanno la cardinalità del continuo. Il punto è che un insieme non può contenere un sottoinsieme che ha una cardinalità maggiore della sua.
"vict85":
[quote="ProPatria"]D'accordo. Dunque mi stai dicendo che ogni sottoinsieme infinito di un insieme numerabile è a sua volta numerabile? (ovviamente vale lo stesso per la cardinalità continua immagino).
No, \(\mathbb{N}\) e \(\mathbb{Q}\) sono sottoinsiemi infiniti e numerabili di \(\mathbb{R}\). Allo stesso modo, \(\mathbb{R}\) possiede sottoinsiemi che hanno la cardinalità del continuo. Il punto è che un insieme non può contenere un sottoinsieme che ha una cardinalità maggiore della sua.[/quote]
D'accordo... Quindi il primo punto della discussione fa perno sul fatto che la cardinalità numerabile è la più piccola possibile per un insieme infinito (cioè poiché [0;1) è sottoinsieme di R allora $ Card([0;1))<=Card(mathbb(R)) $ ma [0;1) è infinito dunque numerabile se R numerabile) o sbaglio?
"ProPatria":
ma [0;1) è infinito dunque numerabile se R numerabile) o sbaglio?
$[0,1)$ sarebbe al massimo numerabile se $RR$ fosse numerabile ma dato che $RR$ ha la cardinalità del continuo allora l'intervallo $[0,1)$ può avere la cardinalità del continuo (che in effetti ha).
"axpgn":
[quote="ProPatria"]ma [0;1) è infinito dunque numerabile se R numerabile) o sbaglio?
$[0,1)$ sarebbe al massimo numerabile se $RR$ fosse numerabile ma dato che $RR$ ha la cardinalità del continuo allora l'intervallo $[0,1)$ può avere la cardinalità del continuo (che in effetti ha).[/quote]
Chiaro, grazie mille
Mi rimane ora qualche dubbio riguardo il secondo punto evidenziato, spero che possiate aiutarmi.
"Sergio":
[quote="ProPatria"]Definisco la funzione inclusione $ i : N → R $ e noto che i è iniettiva, quindi abbiamo $ Card(N) <= Card(R) $. [highlight]Se fosse $ Card(N) = Card(R) $ allora avremmo che l’intervallo $ [0, 1) $ sarebbe un insieme numerabile.[/highlight] Proviamo che non vale l’uguaglianza sopra mostrando che nessuna funzione $ f : N → [0, 1) $ può essere suriettiva. Identifichiamo ogni numero reale in $ [0, 1) $ con la sua scrittura posizionale in base 10 e indichiamo con $ Cn(x) $ la n-esima cifra decimale del numero x. Costruiamo un numero reale che non appartiene a $ Im(f) $. [highlight]Sia y il numero reale in $ [0, 1) $ tale che, per ogni $ n ≥ 1 $, $ Cn(y) = 2 $ se $ Cn(f(n − 1)) != 2 $ e $ Cn(y) = 1 $ se $ Cn(f(n−1)) = 2 $.[/highlight] Tale numero y differisce da ciascun numero reale appartenente a $ Im(f) $ in almeno una cifra decimale e quindi $ y !in Im(f) $. Dunque f non è suriettiva, dunque $ Card(N) <= Card(R) $.
[...]
2) riguardo il secondo punto mi chiedo a cosa corrisponda $ Cn(f(n − 1)) $ quando non abbiamo neppure definito la legge di f.
Definire \(f\) non serve, basta che \(f\) sia una qualsiasi funzione da \(N\) in \([0,1)\), una funzione che mandi ciascun numero naturale in un numero reale compreso tra \(0.0000...\) e \(0.9999...\) (ricorda l'obiettivo: «Proviamo che non vale l’uguaglianza sopra mostrando che nessuna funzione $ f : N → [0, 1) $ può essere suriettiva»).
Le cifre in ciascuno di quei numeri reali sono infinite (numerabili) e possiamo indicizzarle con i naturali: la prima, la seconda, la \(n\)-esima, ecc.
Quanto a \(Cn(x)\), si tratta di una notazione alternativa per \(C(n,x)\): la \(C\)ifra \(n\)-esima del numero reale \(x\): dati un numero reale \(x\in[0,1)\) e un numero naturale \(n\), \(Cn(x)\) li trasforma nella \(n\)-esima cifra decimale di \(x\). Mi prendo la libertà di preferire la notazione \(C(n,x)\).
Quale che sia \(f\), abbiamo che, data un numero reale \(x\in[0,1)\), dovrebbe esistere un \(n\in N\) tale che \(f(n)=x\). Ma possiamo costruire un numero reale che sicuramente non appartiene all'immagine di \(f\).
Proviamo a costruire un numero reale \(y\in[0,1)\) in questo modo: per ogni \(n\ge 1\):
a) \(C(n,y)=2\) se \(C(n,f(n-1))\ne 2\): la cifra \(n\)-esima è \(2\) se la cifra \(n\)-esima del numero \(f(n-1)\) è diversa da \(2\), ad esempio, supponendo di essere arrivati a \(y=0.12\),
\[ f(2)=0.123..., C(3,f(3-1))=3 \to y=0.122 \]b) \(C(n,y)=1\) se \(C(n,f(n-1))= 2\): la cifra \(n\)-esima è \(1\) se la cifra \(n\)-esima del numero \(f(n-1)\) è uguale a \(2\), ad esempio, supponendo di essere arrivati a \(y=0.122\),
\[ f(3)=0.1222..., C(4,f(4-1))=2 \to y=0.1221 \]Dato che le cifre di ciascun \(x\in[0,1)\) sono infinite (numerabili), in ciascun \(x\) hai tante cifre quanti sono i possibili valori di \(f(n)\). In pratica, scorrendo tutte le cifre di \(y\) scorri tutti i reali in \(\mathrm{Im}f\).
Se costruisci un numero reale \(y\in[0,1)\) tale che ciascuna delle sue cifre sia diversa dalla corrispondente cifra di un \(x=f(n)\), ottieni un numero che differisce da tutti quelli generati da \(f(n)\) almeno per una cifra. Infatti:
1) la prima cifra di \(y\) sarà diversa dalla prima cifra di \(f(0)\);
2) la seconda cifra di \(y\) sarà diversa dalla seconda cifra di \(f(1)\);
3) la terza cifra di \(y\) sarà diversa dalla terza cifra di \(f(2)\);
4) la quarta cifra di \(y\) sarà diversa dalla quarta cifra di \(f(3)\);
5) la quinta cifra di \(y\) sarà diversa dalla quinta cifra di \(f(4)\);
ecc.[/quote]
Leggo solo ora... Ti ringrazio per la pazienza. Mi è stato molto utile
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo