Λειτουργία αντιστοίχισης του Cantor08
17

Εκτός από τα διαγώνια ορίσματα , ο Georg Cantor ανέπτυξε επίσης τη συνάρτηση αντιστοίχισης 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\) αναλαμβάνει όλους τους φυσικούς αριθμούς.

---

Αποδεικνύουμε την ειδική δομή του παρακάτω πίνακα:

Έτσι για \(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
$
Αυτό σημαίνει ότι επιτυγχάνονται όλοι οι φυσικοί αριθμοί.