Esercizio banale: cardinalità di Q

[giorgiobusoni87]

Mi è venuto in mente questo esercizio, perchè a lezione più volte ce lo hanno affermato, ma mai dimostrato, eppure la dimostrazione non è molto difficile: dimostrale che N e Q hanno la stessa cardinalità

PS: vietato agli esperti

[jordan]

punti di vista.....

[SiRiLi0N]

si fa tramite una tabella, è abbastanza facile...ma non me lo ricordo.

[killing_buddha]

QUesta cosa si deve a Cantor, e non è affatto banale. Non sono un matematico ma mi piace molto: fate così, pensate Q come insieme di coppie ordinate di numeri in Z:
Conta così
(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7)...

(1,0) (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7)...

(2,0) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (2,7) ...

(3,0) (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (3,7) ...

(4,0) (4,1) (4,2) (4,3) (4,4) (4,5) (4,6) (4,7)...

(5,0) (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (5,7)...
+la biezione da Z in Q che cerchi la trovi associando lo 0 allo 0, l'uno a (0,1), il due a (1,0), il 3 a (2,0), il 4 a (1,1), il 5 a (0,2) e così via. Finirai i numeri interi solo quando finirai i razionali.

[edriv]

Faccio notare che $ ~ \frac{1}{2} = \frac 24 = \frac 36 $ etc... tu hai dimostrato che c'è una corrispondenza biunivoca tra l'insieme di coppie ordinate di numeri naturali e l'insieme dei numeri naturali, ma non hai mostrato una corrispondenza biunivoca tra le coppie di naturali e i razionali.

E comunque concordo sul fatto che non è banale!

[Il_Russo]

Faccio notare che $ ~ \frac{1}{2} = \frac 24 = \frac 36 $ etc... tu hai dimostrato che c'è una corrispondenza biunivoca tra l'insieme di coppie ordinate di numeri naturali e l'insieme dei numeri naturali, ma non hai mostrato una corrispondenza biunivoca tra le coppie di naturali e i razionali.

Basta eliminare le ripetizioni e far seguire ogni razionale rimasto dal suo opposto (inverso addittivo, chiamatelo come volete). Non so se è banale. Provate poi anche un giorno a dimostrare che R ha cardinalità maggiore di N.

[pic88]

Provate poi anche un giorno a dimostrare che R ha cardinalità maggiore di N.

Rilancio, provateci senza scrivere gli elementi di [0,1] nella loro espressione decimale.. anzi già che ci siete, dimostrate che ogni chiuso nonvuoto i cui punti sono tutti di accumulazione è più che numerabile... ma fatelo in MNE

[albert_K]

Il metodo migliore secondo me è di elencare i razionali scrivendoli in questo modo

0, 1, 1/2, 2, 1/3, 3, 2/3, 3/2, 1/4, 4, 3/4, 4/3, .............

evito ripetizioni e non ne manco nessuno!

[Cammy87]

Si può anche dimostrare che $ \displaystyle \mathbb{Q} $ e $ \displaystyle \mathbb{N} $ sono equipotenti utilizzando il teorema di Cantor-Bernstein:
"Dati X e Y insiemi, f:X-->Y iniettiva e g:Y-->X iniettiva allora X e Y sono equipotenti."

L'immersione dei naturali nei razionali è una funzione iniettiva, quindi mi basta esibire un funzione iniettiva da $ \displaystyle \mathbb{Q} $ a $ \displaystyle \mathbb{N} $.
Sia $ \displaystyle f: \mathbb{Q} \rightarrow \mathbb{Z} $ tale che $ f(\frac{a}{b})=2^a \cdot (2b+1) $ dove $ \displaystyle a,b \in\mathbb{Z} $ coprimi e b non nullo (tanto posso ridurre ogni razionale a questa forma).
f è iniettiva per la fattorizzazione unica degli elementi di $ \displaystyle \mathbb{Z} $. Componendola con la funzione bigettiva da $ \displaystyle \mathbb{Z} $ a $ \displaystyle \mathbb{N} $ che manda i numeri negativi in quelli pari e i positivi in quelli dispari ottengo una funzione iniettiva da $ \displaystyle \mathbb{Q} $ a $ \displaystyle \mathbb{N} $.