L'insieme dei numeri razionali è numerabile

Per dimostrarlo consideriamo l’insieme F delle frazioni e rappresentiamolo mediante una tabella.

Numero

0

1

1

-2

2

Denominatore
 1

0/1

-1/1

1/1

-2/1

2/1

2

0/2

-1/2

 1/2

-2/2

2/2

3

0/3

-1/3

1/3

-2/3

2/3

4

0/4

-1/4

1/4

-2/4

2/4

5

0/5

-1/5

1/5

-2/5

2/5

La tabella deve considerarsi infinita. Tale insieme può facilmente essere enumerato seguendo l’ordine indicato dalle frecce colorate. Eliminando da tale successione le frazioni che non sono ridotte ai minimi termini e tutte quelle il cui numeratore è 0 (salvo la prima), otteniamo un’enumerazione del sottoinsieme F’ di F costituito dalle frazioni irriducibili.

Dunque F’ è numerabile; ma l’insieme Q dei numeri razionali può essere posto in corrispondenza biunivoca in modo naturale con F’, e quindi Q è numerabile.