WisFaq!

Er zijn evenveel rationale als natuurlijke getallen

hallo,
Gisteren stelde ik een vraag hoe ik kon bewijzen dat er evenveel natuurlijke als rationale getallen zijn. Maar ik zoek eigenlijk een bewijs met symbolen en getallen. Een relatie tussen beide verzamelingen met symbolen. Met koppels of zo bijvoorbeeld. Kan mij hier iemand antwoord op geven?

Dank u wel!

peter De Zutter
18-10-2002

Antwoord

Hoi,

Als je het heel formeel wil, dan moet de de bijectie definiëren die een rationaal getal p/q afbeeldt op n (en omgekeerd).

Welnu, we definiëren een tabel A met element a_ij=i/j op de i-de rij en de j-de kolom.
We zien dat op de k-de stijgende diagonaal precies k elementen a_ij liggen met de eigenschap i+j=k+1.
Boven de k-de diagonaal liggen er dus 1+2+..+(k-1)=k.(k-1)/2 elementen.

Het bewijs suggereert om de elementen te tellen volgens een 'slangenpatroon':
- op de k-de diagonaal met k even tellen we van rechtsboven naar linksonder.
- op de k-de diagonaal met k oneven tellen we van linksonder naar rechtsboven.

Dus:
Een rationaal getal p/q ligt op de (p+q-1)de diagonaal.
Er zijn (p+q-1)(p+q-2)/2 rationale getallen die op een lagere diagonaal liggen.
Voor p+q oneven is p/q het q-de element op de diagonaal en krijgt dus nummer n(p/q)=(p+q-1)(p+q-2)/2+q.
Voor p+q even is p/q het p-de element op de diagonaal en krijgt dus nummer n(p/q)=(p+q-1)(p+q-2)/2+p.
Hiermee hebben we een eenduidige afbeelding van p/q op n.

Bv.: p/q=2/3
p+q=5 is oneven, dus n(2/3)=4.3/2+3=9
Bv.: p/q=2/4
p+q=6 is even, dus: n(2/4)=5.4/2+2=12

Nu moeten we nog bewijzen dat we van n ook naar p/q kunnen op een eenduidige manier.
Welnu: n ligt op de k-de diagonaal waarbij k het kleinste getal is waarvoor k.(k-1)/2>=n. Aangezien k.(k-1) strikt stijgend is, is k eenduidig bepaald. Hiermee moet dus p+q=k+1.
- Als k even is, dan moet n in de k(k-1)/2-n+1 de kolom. Dus: q=k(k-1)/2-n+1 en p=k+1-q
- Als k oneven is, dan moet n in de k-k(k-1)/2+n de kolom.
Dus: q=k-k(k-1)/2+n en p=k+1-q
Zodat voor elke n we eenduidig p en q en dus p/q kunnen bepalen.

Hiermee is de stelling bewezen...

Zonder die slangbeweging, maar met telling volgens zelfde richting op diagonalen is het iets eenvoudiger...

Groetjes,
Johan

andros
18-10-2002