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
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
Risposte
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?
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.
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.
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$...
"ubermensch":
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.
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 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo