Archive

Posts Tagged ‘bijection’

The Cantor Pairing Function

May 8, 2011 8 comments

The objective of this post is to construct a pairing function, that presents us with a bijection between the set of natural numbers, and the lattice of points in the plane with non-negative integer coordinates.

\pi\colon \mathbb{N} \cup \{ 0 \} \to \big( \mathbb{N} \cup \{ 0 \} \big)^2.

We will accomplish this by creating the corresponding map (and its inverse), that takes each natural number z and drops it at a location in the lattice, as the following diagram suggests:

gCpf

Read more…