Enumerazione esplicita dei razionali

Messaggioda I_U » 18/05/2006, 19:33

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

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
I_U
Starting Member
Starting Member
 
Messaggio: 2 di 4
Iscritto il: 22/04/2006, 15:07

Messaggioda Kroldar » 18/05/2006, 19:38

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
Kroldar
Advanced Member
Advanced Member
 
Messaggio: 320 di 2110
Iscritto il: 11/11/2005, 17:23

Messaggioda I_U » 18/05/2006, 19:54

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?
I_U
Starting Member
Starting Member
 
Messaggio: 3 di 4
Iscritto il: 22/04/2006, 15:07

Messaggioda Giusepperoma » 18/05/2006, 20:39

che Q e' numerabile.
Giusepperoma
Senior Member
Senior Member
 
Messaggio: 911 di 1279
Iscritto il: 29/09/2005, 17:06
Località: ROMA

Messaggioda mircoFN » 19/05/2006, 11:22

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, 18:31, modificato 1 volta in totale.
"La matematica non si capisce, alla matematica ci si abitua" von Neumann.
"The strength of a chain cannot be increased by improving the strongest links" D. Broek.
mircoFN
Advanced Member
Advanced Member
 
Messaggio: 334 di 2656
Iscritto il: 04/03/2006, 13:01

Messaggioda I_U » 21/05/2006, 14:47

grazie mille,cosi' dovrebbe andar bene
I_U
Starting Member
Starting Member
 
Messaggio: 4 di 4
Iscritto il: 22/04/2006, 15:07

Messaggioda Valerio Capraro » 21/05/2006, 15:05

In generale si può dimostrare che per qualunque insieme infinito $X$ risulta $|X\timesN|=|X|$... se ora pensi che $Q^+\subsetN\timesN$...
Valerio Capraro
Advanced Member
Advanced Member
 
Messaggio: 1311 di 2528
Iscritto il: 04/02/2004, 00:58
Località: Southampton (UK)

Messaggioda Camillo » 21/05/2006, 16:24

ubermensch ha scritto: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 ? :D
Camillo
Avatar utente
Camillo
Moderatore globale
Moderatore globale
 
Messaggio: 1457 di 8074
Iscritto il: 31/08/2002, 22:06
Località: Milano -Italy

Messaggioda Valerio Capraro » 21/05/2006, 17:10

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.
Valerio Capraro
Advanced Member
Advanced Member
 
Messaggio: 1315 di 2528
Iscritto il: 04/02/2004, 00:58
Località: Southampton (UK)

Messaggioda Camillo » 21/05/2006, 23:21

Thx :)
Camillo
Avatar utente
Camillo
Moderatore globale
Moderatore globale
 
Messaggio: 1460 di 8074
Iscritto il: 31/08/2002, 22:06
Località: Milano -Italy


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: mario9555 e 13 ospiti