Tag archieven: Cantor

N x N is aftelbaar oneindig

Geplaatst op door

Om te bewijzen dat \mathbb{N} \times \mathbb{N} aftelbaar oneindig is, moeten we een bijectie opstellen tussen \mathbb{N} \times \mathbb{N} en \mathbb{N}. We kunnen dit doen via de diagonaalmethode van Cantor :

De volgende tekening spreekt voor zich:

Met volgende formule kan je het rangnummer bepalen van een bepaald punt (x,y):

    \[f(x,y)=\dfrac{1}{2}((x+y)^2+2(x+y)+(-1)^{x-y})\]

Het is wel moeilijker om met één natuurlijk getal z een koppel natuurlijke getallen te laten overeenkomen.

  • De diagonalen bevatten achtereenvolgens 1,2,3,… getallen, zodat de som S_n van de eerste n natuurlijke getallen zal verschijnen op elke diagonaal ( de omcirkelde rangnummers) .
  • Aangezien z gelegen is tussen twee opeenvolgende waarden van S_n, moet n gelijk zijn aan het aantal gehelen n_0 van de positieve wortel van de vierkantsvergelijking n^2+n-2z=0.
  • Als n_0 even is, dan behoort (x,y) tot een dalende diagonaal en is x=z-f(0,n_0)=S_{n_0} en y=n_0-x.
  • Als n_0 oneven is, dan behoort (x,y) tot een stijgende diagonaal en is y=z-f(n_0,0)=S_{n_0} en x=n_0-y.

Neem bijvoorbeeld het getal z met rangnummer 32. De vierkantsvergelijking n^2+n-64=0 heeft bij benadering als oplossingen -8,52 en 7,52. Dus is n_0=7. Het corresponderend punt in het vlak is (3,4).

Neem als tweede voorbeeld het getal z met rangnummer 38. De bijhorende vierkantsvergelijking n^2+n-76=0 heeft bij benadering als oplossingen -9,23 en 8,23 zodat n_0=8. Het corresponderend punt in het vlak is (2,6)