Enumerazione esplicita dei razionali

salve,ho trovato questo esercizio sul libro che pero' mi sta dando dei grattacapi,sopratutto perche non c'e' la soluzione

cmq il testo e' questo:
trovare un modo esplicito per enumerare i razionali.
suggerimento:se r=m/n e' razionale positivo, m,n primi fra loro ,definiamo altezza di r il numero intero m+n. Possiamo numerare i razionali cominciando con quelli di altezza 1,2,3 e cosi' via.

alche' ho pensato al metodo utilizzato per enumerare i numeri interi,ovvero porli in corrispondenza biunivoca con l'insieme dei numeri naturali in questa maniera

Z N
0 <----------->0
1 <----------->1
-1<----------->2
2<-----------> 3
.. ..
n <----------->2n-1
-n<----------->2n

applicando questo procedimento ed utlizzando il suggerimento non viene una gran cosa...
conoscete un diversivo?
grazie dell'attenzione

il primo a farlo fu Cantor: crea una matrice $NN x NN$ in cui il generico elemento $a_(i,j)$ è un numero razionale il cui numeratore è l'$i$-esimo numero naturale e il cui denominatore è il $j$-esimo numero naturale; parti da $a_(1,1)$ e percorri la matrice a zig-zag... vedrai come è possibile numerare i razionali

io sapevo che la diagonale si usa per la dimostrazione della non numerabilita' dell'insieme R.
cosa dimostro creando una matrice NxN come tu mi dici?

che Q e' numerabile.

Numerare significa metterli in ordine. Una possibile strategia di numerazione è la seguente (spiegata in modo molto grossolano ma credo sostanzialmente corretta)

I razionali sono le frazioni, consideriamo solo i numeri compresi tra 0 1 (per gli altri vediamo dopo).

prendo le frazioni proprie con denominatore 1 (1/1)
poi quelle con denominatore 2 (1/2 e 2/2) e scarto quelle già trovate: 1/2
........................................ 3 (1/3, 2/3, 3/3)....................................: 1/3, 2/3
........................................ 4 (1/4, 2/4, 3/4, 4/4)....................................: 1/4, 3/4

ecc.

così posso numerare tutti i razionali tra 0 e 1 e allo stesso modo tutti i razionali tra qualsiasi coppia di interi consecutivi.

A questo punto li metto tutti in fila prendendo per primo lo 0 poi il secondo dall'intervallo con origine in 0, il terzo con origine in -1, il quarto +1, ---.-2,+2 ........

Non sono ovviamente ordinati in modo crescente ma li ho trovati tutti e soli.
Quindi Q è numerabile.

Ultima modifica di mircoFN il 22/05/2006, 17:31, modificato 1 volta in totale.

grazie mille,cosi' dovrebbe andar bene

In generale si può dimostrare che per qualunque insieme infinito $X$ risulta $|X\timesN|=|X|$... se ora pensi che $Q^+\subsetN\timesN$...

In generale si può dimostrare che per qualunque insieme infinito $X$ risulta $|X\timesN|=|X|$... se ora pensi che $Q^+\subsetN\timesN$...

Non ho proprio capito.....puoi spiegarlo in modo meno telegrafico ?

ok...
il teorema è chiaro e dice che facendo il prodotto cartesiano fra un insieme infinito e uno numerabile, non aumento l'infinito. In particolare il prodotto di due insiemi numerabili è anch'esso numerabile. Ora $Q^+$ può essere immerso in $N\timesN$ associando alla frazione $a/b$ la coppia $(a,b)$, per cui $Q^+$ ha cardinalità al più uguale di quella di $N\timesN$, che è appunto numerabile. Dunque $Q^+$ è numerabile, ne segue che anche $Q^-$ è numerabile e quindi anche la loro unione.

Thx