N x N is aftelbaar oneindig | Wiskunde is leuk

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)$