Skip to main content
Post Made Community Wiki
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

The Cantor pairing function is the function $p(a,b)= (a+b)(a+b+1)/2 + b$, a polynomial bijection between the pairs of natural numbers and individual numbers. Thus, it is a bijection or isomorphism of the sets $\mathbb{N}\times\mathbb{N}$ and $\mathbb{N}$. Using such a function, one may easily deduce that the set of rational numbers is countable, and more generally, that a countable union of countable sets is countable.