💾 Archived View for soviet.circumlunar.space › ayb › notes › cantor_pairing.gmi captured on 2022-06-03 at 23:36:51. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

Cantor's pairing function

Definition

We define the function f as follows:

 2
N      ---> N
             (x + y) (x + y + 1)
(x, y) |--> --------------------- + y
                      2

An alternative expression of f(x, y) is:

                  2                  2
                 x + x + 2xy + 3y + y  
f : (x, y) |--> -----------------------
                          2

Cantor's pairing function

Definition

Proof of bijectivity

Proof of surjectivity

Proof of injectivity

Extension to N^n