Prove that $\{(a,b):a,b\in\mathbb N, a\geq b\}$ is denumerable.

Question

If $S=\{(a,b):a,b\in\mathbb N, a\geq b\}$, how do I prove that $S$ is denumerable?

Work: Since $S \subseteq\mathbb{N\times N}$ I know that $S$ is denumerable. But I don't know how to structure the proof clearly. I know that the two theorems : every infinite subset of a denumerable set is denumerable and the theorem: If $A$ and $B$ are denumerable sets, then $A\times B$ is denumerable are useful to this proof, but I don't know how to apply it here.

Answer 1

If you're allowed to use than any subset of a denumerable set is denumerable, then just use the fact that $\mathbb{N} \times \mathbb{N}$ is denumerable, and prove it is if necessary by using an injection $f(m,n) = 2^m 3^n$.

Answer 2

We want to prove that $S$ is denumerable. We already know the following things.

1. $\Bbb{N\times N}$ is denumerable.
2. An infinite subset of a denumerable set is denumerable.

So we can conclude their conjunction as a theorem stating "If $A$ is an infinite subset of $\Bbb{N\times N}$, then $A$ is denumerable". So in order to apply this theorem on $S$ we need to show that $S$ satisfies the requirements of this theorem first.

This means we have to show that $S$ is a subset of $\Bbb{N\times N}$ which is quite trivial; and that it satisfies the conditions of the second theorem, i.e. it is infinite.

I'll leave you to show both these facts.

Answer 3

You have a trivial injection to $\Bbb N\times \Bbb N$, and you have a surjection that sends $(a,b)$ with $a\geqslant b$ to $ a-b\in\Bbb N$. Hence if $C$ is the cardinality of your set,

$$\aleph_0\leqslant S\leqslant \aleph_0^2=\aleph_0 $$