عملکرد جفت سازی Cantor

علاوه بر استدلال های مورب ، گئورگ کانتور همچنین عملکرد جفت سازی کانتور را ایجاد کرد \(\mathbb{N}^2 \to \mathbb{W}, \quad c(x,y) = \binom{x+y+1}{2}+x = z\) ، که هر دو شماره \(x,y \in \mathbb{N}\) در یک شماره جدید رمزگذاری می کند \(z \in \mathbb{N}\) . به عنوان مثال ، \(c(3,4)=\binom{3+4+1}{2}+3 = \binom{8}{2}+3=\frac{8!}{6!\cdot 2!} +3 = 31 = z\) یک کدگذاری منحصر به فرد از اعداد \(3\) و \(4\) در شماره \(31\) . نمایش: مجموعه مقادیر \(\mathbb{W} = \mathbb{N}\) ، یعنی \(z\) تمام اعداد طبیعی را فرض می کند.


ما ساختار خاص جدول زیر را اثبات می کنیم:

  0 1 2 3 ...
0 0 2 5 9 ...
1 1 4 8 13 ...
2 3 7 12 18 ...
3 6 11 17 24 ...
... ... ... ... ... ...

بنابراین برای \(x > 0, y \geq 0\)
$ $
c (x + 1 ، y) -c (x ، y + 1) =
$ $
$ $
\ binom {x + 1 + y + 1} {2} + x + 1 - \ چپ (\ binom {x + y + 1 + 1} {2} + x \ سمت راست)) = \ binom {x + y + 2} {2} - \ binom {x + y + 2} {2} + x - x + 1 = 1
$ $
و همچنین برای \(x \geq 0\)
$ $
c (0 ، x + 1) -c (x ، 0) =
$ $
$ $
\ binom {0 + x + 1 + 1} {2} + 0 - \ binom {x + 0 + 1} {2} - x = \ binom {x + 2} {2} - \ binom {x + 1} {2} - x =
$ $
$ $
\ frac {(x + 2)!} {2! x!} - \ frac {(x + 1)!} {2! (x-1)!} - x =
$ $
$ $
\ frac {(x + 2) (x + 1)} {2} - \ frac {(x + 1) x} {2} - x = \ frac {(x + 1) \ سمت چپ ((x + 2) - x \ راست)} {2} - x = x + 1 - x = 1
$ $
با این کار به همه اعداد طبیعی می رسیم.

بازگشت