Confronto tra insiemi - (2)

[Gianmaster08]

Dati due sottoinsiemi X1 e X2 di N, definiamo φ(X1,X2) come il sottoinsieme X di
N definito da:

per ogni k appartenente ad N,

2k appartiene ad X se e solo se k appartiene ad X1
2k+1 appartiene ad X se e solo se k appartiene ad X2

Dimostrare che φ è una funzione biiettiva da PN × PN su PN (dove con PN si indica l’insieme costituito da tutti i sottoinsiemi di N, insieme dei numeri naturali).

Grazie per le eventuali proposte di soluzione.

[gugo82]

Non basta usare il fatto che la famiglia ${P,D}$, ove $P$ è l'insieme dei pari e $D$ quello dei dispari, è una partizione di $NN$?

[Gianmaster08]

D'accordo...ma come lo dimostro? Te ne sarei grato!

[gugo82]

Innanzitutto dovresti specificare pure che $phi(\emptyset,\emptyset)=\emptyset$... poi $phi$ è biiettiva: infatti, fissato $X in P(NN)$, se $X=\emptyset$ allora evidentemente $(\emptyset,\emptyset)$ è l'unico elemento di $P(NN)\times P(NN)$ ad avere $X$ come immgine; d'altra parte, se $X!=\emptyset$ allora almeno uno tra $Xcap P$ ed $X cap D$ è non vuoto e quindi, visto che per il l'algoritmo della divisione ogni elemento di $Xcap P$ [risp. $X cap D$] si scrive in unico modo come $2k_1$ [$2k_2+1$] con $k_1 in NN$ [$k_2 in NN$], $X$ è immagine tramite $phi$ della coppia avente coordinate $X_1={k_1 in NN:quad 2k_1 in X}$ ed $X_2={k_2 in NN:quad 2k_1+1 in X}$ e di nessun altra coppia di $P(NN) times P(NN)$.