Esercizio banale: cardinalità di Q
-
- Messaggi: 112
- Iscritto il: 28 feb 2005, 00:27
- Località: Livorno
Esercizio banale: cardinalità di Q
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
PS: vietato agli esperti
-
- Messaggi: 209
- Iscritto il: 20 mag 2007, 12:39
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.
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.
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!
E comunque concordo sul fatto che non è banale!
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.edriv ha scritto: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.
Presidente della commissione EATO per le IGO
-
- Messaggi: 741
- Iscritto il: 16 apr 2006, 11:34
- Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...
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 MNEIl_Russo ha scritto:Provate poi anche un giorno a dimostrare che R ha cardinalità maggiore di N.
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} $.
"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} $.
>>> Io sono la gomma e tu la colla! <<<
-----
-----