4
$\begingroup$

In order to show that $\mathbb{N} \times \mathbb{N}$ is countable, we can define a bijection $f : \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}$ like this one:

  • $0 \rightarrow (0, 0)$
  • $1 \rightarrow (1, 0)$
  • $2 \rightarrow (0, 1)$
  • $3 \rightarrow (2, 0)$
  • $4 \rightarrow (1, 1)$
  • $5 \rightarrow (0, 2)$
  • $6 \rightarrow (3, 0)$
  • $7 \rightarrow (2, 1)$
  • $8 \rightarrow (1, 2)$
  • ...

I need to prove that a set is countable, I know how to use this proof method, but I can't remember its name. Any hints?

Improve this question
$\endgroup$
  • $\begingroup$ You are just establishing a bijection between $\mathbb{N}\times \mathbb{N}$ and $\mathbb{N}$. You can call this enumeration of $\mathbb{N}\times \mathbb{N}$. $\endgroup$ – baharampuri May 16 '15 at 10:04
  • $\begingroup$ @ChristianBlatter: fixed that $\endgroup$ – hey hey May 16 '15 at 14:27
  • $\begingroup$ @baharampuri: in my context this is only one of a few possible enumerations. This is why I needed a name for it. $\endgroup$ – hey hey May 16 '15 at 14:28
6
$\begingroup$

Aha, I found it! The $f$ function I'm using is Cantor's pairing function.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.