Equipotenza tra l'insieme delle parti di $NN$ e $RR$.

[UmbertoM1]

Salve a tutti,
Come quasi tutti sapete non è possibile costruire una funzione biettiva $f:A->P(A)$ ove $P(A)$ è l'insieme delle parti (ossia l'insieme di tutti i sottoinsiemi) di $A$.
Questo è vero sia per gli insiemi finiti, che per quelli infiniti, ed in generale per questi ultimi l'esistenza di una funzione biettiva è necessaria affinché i due insiemi abbiano la stessa cardinalità.
In generale la cardinalità di $NN$ è $|NN|=aleph_0$. Mente $|P(NN)|=aleph_1$. Anche i reali hanno cardinalità $|RR|=aleph_1$ e molto spesso ho sentito che esiste una funzione biettiva $f:RR->P(NN)$, tuttavia non sono riuscito a trovare una dimostrazione di questa asserzione, e spero che qualcuno di voi mi aiuti.
Mi scuso se la sezione scelta non è appropriata.

[j18eos]

Cia0, se fai una ricerca nel forum la trovi questa dimostrazione o discussioni inerenti!

[Studente Anonimo]

[xdom="Martino"]Ritengo che la sezione di Algebra sia più appropriata, quindi sposto.[/xdom]

[UmbertoM1]

Mi spiace, ma non ho trovato nulla che riguardi specificamente quello che sto cercando. Spero che qualcun altro mi possa aiutare.

[PZf]

Provo a inventare una dimostrazione. Spero di non commettere errori.

Osservazioni preliminari: l'insieme delle parti di $\NN$ è equipotente all'insieme $2^\NN$ delle funzioni da $\NN$ a ${0,1}$, mentre $\RR$ è equipotente all'intervallo $[0,1]$, e anche all'intervallo $[0,2[$.

Costruisco prima una funzione suriettiva da $2^\NN$ a $[0,1]$, dimostrando così che \(|\mathcal{P}(\mathbb{N})|\geq|\mathbb{R}|\).
Poi costruirò una funzione suriettiva da $[0,2[$ a $2^\NN$ dimostrando così che \(|\mathcal{P}(\mathbb{N})|\leq|\mathbb{R}|\).

La prima funzione $F:2^\NN->[0,1]$ è definita così: $F(f)=\sum_{k=1}^{+\infty}f(k)2^{-k}$
E' chiaro che preso un qualunque $x\in[0,1]$ esiste una funzione $f_x$ tale che $F(f_x)=x$ (basta che i valori restituiti dalla $f_x$ siano la rappresentazione in base $2$ di $x$).
Nota: l'associazione è suriettiva, ma non è iniettiva, infatti una funzione $f_1$ tale che $f_1(m)=1$ e $f_1(k)=0\ \forall k>m$ è equivalente alla funzione $f_2$ definita da $f_2(k)=f_1(k)\ \forall km$. Ciò segue dal fatto che $\sum_{k=m+1}^{+\infty}2^{-k}=2^{-m}$.

Costruisco ora una funzione suriettiva $G:[0,2[->2^\NN$.
Se $x\in[0,1[$ scriviamo $x$ in base $2$: $x=\sum_{k=1}^{+\infty}b_k2^{-k}$.
Così come è questa non sarebbe una buona definizione per i coefficienti $b_k$ perché esistono degli $x\in[0,1[$ che hanno due rappresentazioni binarie equivalenti. Nella definizione dei $b_k$ data sopra scegliamo i $b_k$ in modo che non siamo definitivamente uguali a $1$ (ma possono essere definitivamente uguali a $0$).
Con questa convenzione i $b_k$ risultano ben definiti.
Per $x\in[0,1[$ poniamo dunque $[G(x)](k)=b_k$. Al variare di $x$ in $[0,1[$ le funzioni $G(x)\in2^\NN$ che risultano non esariscono tutto $2^\NN$, infatti le funzioni definitivamente uguali a $1$ non sono associate a nessun $x\in[0,1[$.
Per $x\in[1,2[$ scriviamo $x-1$ in base $2$, ma questa volta adottando la convenzione per cui i coefficienti non possono essere definitivamente nulli (eccetto per $x=1$): $x-1=\sum_{k=1}^{+\infty}B_k2^{-k}$.
I coefficienti $B_k$ risultano ben definiti. Per $x\in[1,2[$ poniamo allora $[G(x)](k)=B_k$.
Adesso, quando $x$ varia in $[0,2[$, le funzioni $G(x)$ che risultano esauriscono tutto $2^\NN$, quindi $G$ è suriettiva.

[UmbertoM1]

Sembra giusta, anche se non mi è ancora troppo chiara la seconda parte. Comunque se è vero che l'hai inventata di sana pianta, devo farti i complimenti.
In ogni caso se qualcuno conosce un'altra dimostrazione è ben accetto.

[UmbertoM1]

Comunque il problema della non iniettività secondo me si potrebbe risolvere considerando il fatto che $|RR\\QQ|=|RR|$.
Infatti, è vero che ad esempio il numero (in base 2) $0,0bar1=0,1$ è associato a due possibili funzioni: una che ha $f(1)=1$ e $f(k)=0$ $AAx>1$, e l'altra che ha $f(1)=0$ e $f(k)=1AAx>1$. Tuttavia questo problema riguarda solo i numeri razionali, e con lo stratagemma di considerare solo gli irrazionali si potrebbe abbreviare la dimostrazione.

[PZf]

"UmbertoM":Sembra giusta, anche se non mi è ancora troppo chiara la seconda parte. Comunque se è vero che l'hai inventata di sana pianta, devo farti i complimenti.
In ogni caso se qualcuno conosce un'altra dimostrazione è ben accetto.

Grazie
La poca chiarezza della seconda parte è forse causata da quelle scritture tipo $[G(x)](k)$ ?
Se è questo bisogna fare un po' di sforzo con l'immaginazione per pensare che la $G$, valutata in $x$, restituisce una funzione da $\NN$ a ${0,1}$. Quindi $G(x)$ è una funzione e $[G(x)](k)$ è la funzione $G(x)$ valutata nel punto $k$.
E' utile pensare la generica funzione $f\in 2^\NN$ non come una funzione, ma come una stringa di $0$ e $1$ che rappresenta la rappresentazione binaria (solo la parte dopo la virgola) di un numero. Quindi, intuitivamente, la $G(x)$ è una stringa di $1$ e $0$ e $[G(x)](k)$ è la $k$-esima cifra di tale stringa.

"UmbertoM":Comunque il problema della non iniettività secondo me si potrebbe risolvere considerando il fatto che $|RR\\QQ|=|RR|$.
Infatti, è vero che ad esempio il numero (in base 2) $0,0bar1=0,1$ è associato a due possibili funzioni: una che ha $f(1)=1$ e $f(k)=0$ $AAx>1$, e l'altra che ha $f(1)=0$ e $f(k)=1AAx>1$. Tuttavia questo problema riguarda solo i numeri razionali, e con lo stratagemma di considerare solo gli irrazionali si potrebbe abbreviare la dimostrazione.

Concordo con te UmbertoM, considerando che $|\RR\backslash\QQ|=|\RR|$ la dimostrazione sarebbe più corta

Questa era un'idea che avevo preso in considerazione, però non volevo affermare senza dimostrazione che la cardinalità dell'insieme dei reali irrazionali è la stessa dell'insieme di tutti i reali (anche se non sarebbe stata una dimostrazione difficile). Se avessi usato questo fatto avrei sicuramente scritto anche la sua dimostrazione.

[UmbertoM1]

Sono io a dover ringraziare te, una dimostrazione del genere non l'ho trovata da nessuna parte e probabilimente non sarei stato in grado di concepirla autonomamente. Per quanto riguarda $|RR\\QQ|=|RR|$, la dimostrazione dovrebbe essere semplice (dico così e magari è più complicata anche di questa )

[PZf]

In effetti la dimostrazione di $|\RR\backslash\QQ|=|\RR|$ è piuttosto semplice, solo che poteva risultare un po' pesante se l'avessi inserita nel discorso precedente.

Se sei curioso la scrivo qui (è sempre una dimostrazione inventata da me, quindi è possibile che se ne possa trovare in giro una migliore).
Ovvio che $|\RR|>=|\RR\backslash\QQ|$, mi limito a costruire una funzione suriettiva dall'insieme dei reali irrazionali a tutto $\RR$.
Prima a livello intuitivo, poi formalizzo: per $x$ reale irrazionale sia $f(x)$ il numero reale che si ottiene selezionando da $x$ solo le cifre di posto pari.
In modo più formale, per $x\in\RR\backslash\QQ$ scriviamo $x$ nella forma $x=\sum_{k=-m}^{+oo} d_k 10^{-k}$ (in base $10$ dunque), con la convenzione che i $d_k$ non possono essere definitivamente uguali a $9$ (così i $d_k$ risultano ben definiti). Poniamo \(f(x)=\sum_{k=- [m/2]}^{+\infty} d_{2k} 10^{-k}\). E' chiaro che al variare di $x$ in $\RR\backslash\QQ$ la $f(x)$ può assumere qualunque valore in $\RR$, quindi vale $|\RR\backslash\QQ|>=|\RR|$.

[UmbertoM1]

La mia idea per dimostrare che $|RR\\QQ|=|RR|=aleph_1$ è la seguente. Dimostro innanzitutto che $|RR\\QQ|$ non è numerabile, e questo si può fare sfruttando lo stesso metodo che Cantor usa per dimostrare la non numerabilità di $RR$. Perciò $|RR\\QQ|>aleph_0=>|RR\\QQ|=aleph_1$, infatti è un assioma (non dimostrabile, ne' smentibile) che non esista una cardinalità transfinita compresa tra $aleph_0$ e $aleph_1$

[PZf]

Certo, assumendo l'ipotesi del continuo (l'assioma che hai usato), la dimostrazione funzionerebbe.

Si potrebbe anche usare il fatto che se $A$ e $B$ sono due insiemi disgiunti tali che $|A|>=\aleph_0$ e $|B|>=\aleph_0$ allora $|A\cup B|=\max{|A|,|B|}$.
Infatti potremmo scrivere $|\RR|=\max{|\RR\backslash\QQ|,|\QQ|}$ e sapendo che $|\QQ|<|\RR|$ concludere che deve necessariamente essere $|\RR\backslash\QQ|=|\RR|$.
Il punto debole di quest'altra dimostrazione è che per dimostrare che, sotto le ipotesi, vale $|A\cup B|=\max{|A|,|B|}$ bisogna assumere l'assioma della scelta.

Dal momento che il teorema $|\RR\backslash\QQ|=|\RR|$ sarebbe vero anche rigettando sia l'ipotesi del continuo sia l'assioma della scelta, personalmente preferisco dimostrarlo in maniera indipendente da tali assiomi, anche perché, soprattutto l'ipotesi del continuo, non tutti i matematici li accettano.

[UmbertoM1]

Sì, un'altra possibile dimostrazione che prescinde da tali assiomi potrebbe essere questa.
$|RR|=$$|$$[0,1]|>|QQ|$.
Perciò non è sbagliato affermare che $|RR\\[0,1]|<=|RR\\QQ|$
Ma $|RR\\[0,1]|=|RR|$, quindi non potendo essere $|RR\\QQ|>|RR|$ deve essere $|RR\\QQ|=|RR|$

[PZf]

Effettivamente questa è buona

Il pezzo finale della seconda parte della mia dimostrazione può allora essere accorciato facilmente e reso più chiaro.
Ti ringrazio per le idee che hai condiviso.

PS: devo fare una piccola correzione. Per come è definito $\aleph_1$ scrivere che $|\RR|=\aleph_1$ significa che stai già dando per vera l'ipotesi del continuo. Per correttezza dovresti scrivere \(|\mathbb{R}|=\mathfrak{c}\) e quindi ciò che stiamo dimostrando è \(|\mathcal{P}(\mathbb{N})|=\mathfrak{c}\).

[PZf]

Mi piacerebbe fare un rilancio qui.

Dimostrare, in modo indipendente dall'assioma della scelta e dall'ipotesi del continuo, che \(\aleph_0^{\aleph_0}=\mathfrak{c}\).

Da questo segue anche come corollario che \(\mathfrak{c}^{\aleph_0}=\mathfrak{c}\).

[UmbertoM1]

"PZf":PS: devo fare una piccola correzione. Per come è definito $ℵ_1$ scrivere che $|RR|=ℵ_1$ significa che stai già dando per vera l'ipotesi del continuo. Per correttezza dovresti scrivere $|RR|=c$ e quindi ciò che stiamo dimostrando è $|P(N)|=c$.

E' vero, infatti quella dimostrazione non era un granché, ma comunque se ne possono trovare a bizeffe.

"PZf":Dimostrare, in modo indipendente dall'assioma della scelta e dall'ipotesi del continuo, che $aleph_0^(ℵ_0)=c$

In pratica vuoi dimostrare che l'insieme delle funzioni $f:NN->NN$ ha la potenza del continuo. Ci dovrò pensare su.

[PZf]

E' passato un po' di tempo, scrivo la dimostrazione che avevo in mente per l'uguaglianza \(\aleph_0^{\aleph_0}=\mathfrak{c}\).


Intanto è chiaro che \(\aleph_0^{\aleph_0}\ge 2^{\aleph_0}=\mathfrak{c}\), quindi devo solo dimostrare che \(\aleph_0^{\aleph_0}\le\mathfrak{c}\).
Basterà dunque costruire una funzione iniettiva $F\ :\ \NN^\NN->\RR$.
La funzione $F$ deve cioè trasformare la generica funzione $f\ \in\NN^\NN$ in un numero reale $\RR$ e deve anche valere l'implicazione $f_1\ne\f_2=>F(f_1)\ne F(f_2)$.
Presa allora la generica funzione $f\ \in\NN^\NN$ scriviamo il numero $f(i)\in\NN$ nella forma $f(i)=\sum_{j=0}^{\infty} b_{ij} 2^j$ con $b_{ij}\in{0,1}\ \forall j\in\NN$ (in base $2$), dove chiaramente, per ogni fissato $i\in\NN$, i coefficienti $b_{ij}$ sono definitivamente nulli per $j->+oo$ (altrimenti la serie divergerebbe).
Poniamo allora $F(f)=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}b_{ij}2^{-(2^{i+1} j +2^i)}$ e dimostriamo che questa funzione manda $\NN^\NN$ in $\RR$ in modo iniettivo.
Il motivo che mi ha portato, a livello intuitivo, a scegliere la $F(f)$ in questo modo è descritto in spoiler per chi fosse interessato a vedere come mi si è sviluppata l'idea.

Abbiamo la generica funzione $f$ e, a partire da essa, vogliamo costruire un numero reale $\alpha$ che contenga al suo interno tutte le informazioni necessarie per ricostruire la funzione $f$ di partenza.
Allora cominciamo a scrivere $\alpha$ nella forma $\alpha=0,****************...\ $ dove il simbolo $**$ sta a significare che non abbiamo ancora scelto quale cifra (binaria) vada scritta in una specifica posizione. La posizione numerata con $0$ rappresenterà la cifra $0$ presente a sinistra della virgola, le posizioni da $1$ in poi rappresentano le cifre a destra.
Ora consideriamo $f(0)$ e immaginiamolo scritto in binario. Immaginiamo di inserire le cifre di $f(0)$, dalla meno significativa, all'interno di $\alpha$, una cifra si e una cifra no: $\alpha=0,b_{00}**b_{01}**b_{02}**b_{03}**b_{04}**b_{05}**...$.
Ora consideriamo $f(1)$ e immaginiamo di inserire le sue cifre binarie all'interno di $\alpha$, una cifra si e una no considerando solo le cifre ancora indeterminate: $\alpha=0,b_{00}b_{10}b_{01}**b_{02}b_{11}b_{03}**b_{04}b_{12}b_{05}**...$
Immaginiamo quindi di procedere all'infinito prendendo, uno per volta, tutti i valori $f(k)$ al variare di $k$.
Ragionandoci un po', e facendo un po' di prove, si vede che le cifre di $f(k)$ vanno a cadere nelle posizioni numerate con $2^{k+1} j+2^{k}$ con l'indice $j$ che va da $0$ a $+oo$.
Mettendo insieme tutti i pezzi si arriva a scrivere la formula $F(f)=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}b_{ij}2^{-(2^{i+1} j +2^{i})}$ e l'analisi rigorosa di tale formula permette di vedere che effettivamente funziona per lo scopo.

Dimostriamo ora che la funzione $F$ definita sopra è iniettiva.
Supponiamo quindi che $f\ne f\ '$ e dimostriamo che deve essere $F(f)\ne F(f\ ')$.

Ora, fissato un qualunque numero naturale $n\ne 0$ esiste un unico modo per scegliere due indici $i$ e $j$ tali che $n=2^{i+1} j +2^{i}=2^{i}(2j+1)$. Denoterò con $i(n)$ e $j(n)$ tali due indici.
La funzione $F$ può essere riscritta nella forma
$F(f)=\sum_{n=1}^{+\infty}b_{i(n)j(n)}2^{-n}$

Se $f\ne f\ '$ allora esiste almeno un numero $N$ tale che $b_{i(N)j(N)}\ne b'_{i(N)j(N)}$ (con ovvio significato dei simboli).
Sia allora $\bar{n}=\min{N\in\NN|b_{i(N)j(N)}\ne b'_{i(N)j(N)}}$. Possiamo supporre, senza perdere di generalità, che $b_{i(\bar{n})j(\bar{n})}=1$ e $b'_{i(\bar{n})j(\bar{n})}=0$.
Vale $F(f)-F(f\ ')=\sum_{n=1}^{+\infty}(b_{i(n)j(n)}-b'_{i(n)j(n)})2^{-n}=2^{-\bar{n}}+\sum_{n=\bar{n}+1}^{+\infty}(b_{i(n)j(n)}-b'_{i(n)j(n)})2^{-n}=2^{-\bar{n}}+A$, avendo indicato compattamente con $A$ l'ultima serie scritta.
$|A|<=\sum_{n=\bar{n}+1}^{+\infty}2^{-n}=2^{-\bar{n}}$ dove l'uguaglianza vale solo se $b_{i(n)j(n)}=1\wedge b'_{i(n)j(n)}=0\ \forall n>\bar{n}$ oppure $b_{i(n)j(n)}=0\wedge b'_{i(n)j(n)}=1\ \forall n>\bar{n}$. Entrambi questi casi però sono assurdi perché altrimenti, fissato $i$, i $b_{ij}$ non potrebbero essere definitivamente nulli per $j->+oo$ contrariamente all'osservazione fatta quando si è data la definizione di tali coefficienti.
La disuguaglianza vale quindi in senso stretto e si ottieme $-2^{-\bar{n}}

Cita

Segnala