💾 Archived View for soviet.circumlunar.space › ayb › notes › cantor_pairing.gmi captured on 2022-06-11 at 21:28:58. Gemini links have been rewritten to link to archived content

View Raw

More Information

⬅️ Previous capture (2021-12-03)

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

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

Proof of bijectivity

Proof of surjectivity

Proof of injectivity

Extension to N^n