Mengden av rasjonale tall er tellbar

Hvordan bevise at mengden av rasjonale tall er tellbar?

En mengde er tellbar om vi kan 'telle' den med de naturlige tallene $\{1,2,3,\mathrm{...}\}$. Med å 'telle' mener vi å sette i en-til-en-korrespondanse, altså knytte et naturlig tall til hvert element i mengden. Det koker ned til å liste opp elementene i mengden, og man kan altså gjøre det med brøker (selv om det kanskje ikke virker som det burde være riktig til å begynne med!)

En måte å liste brøker på tar utgangspunkt i dette oppsettet av rasjonale brøker:

Du kan nå lage en liste ut av tallene ved å følge en bestemt slags kronglete sti gjennom, jeg lister opp de første brøkene i stien, hvis du tegner det opp ser du nok mønsteret:

$\frac{1}{1},\frac{1}{2},\frac{2}{1},\frac{3}{1},\frac{2}{2},\frac{1}{3},\frac{1}{4},\frac{2}{3},\frac{3}{2},\frac{4}{1},\mathrm{...}$

Her teller du noen brøker flere ganger, men det er ikke noe problem. Dermed får vi listet opp alle de rasjonale brøkene, og har vist at mengden av rasjonale tall er tellbar.