# Thread: Prove that sets are denumerable

1. ## Prove that sets are denumerable

Hi!

Problem:

Prove that the sets $\displaystyle \mathbb{N} \times \mathbb{N} = \left\{ (i,j): i,j \in \mathbb{N} \right\}$ and $\displaystyle \mathbb{Q}$ are denumerable.

(If someone wants to give a precise definition of denumerable please do).

For a fixed $\displaystyle j \in \mathbb{N}$ the set $\displaystyle \left\{ (i,j): i,j \in \mathbb{N} \right\}$ is denumerable since $\displaystyle \mathbb{N}$ is denumerable.
If we change $\displaystyle j$ to $\displaystyle j'$, the set $\displaystyle \left\{ (i,j'): i,j' \in \mathbb{N} \right\}$ is also denumerable.
So we have a denumerable amount of denumerable sets, which gives that $\displaystyle \mathbb{N} \times \mathbb{N}$ is denumerable?

I tried proving $\displaystyle \mathbb{Q}$ in a similar way.

Help appreciated!

2. Assuming that $\displaystyle \mathbb{N}=\{0,1,2,\cdots\}$ then a set is denumerable if it bijects with $\displaystyle \mathbb{N}$.
$\displaystyle f:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ by $\displaystyle fj,k)\mapsto 2^j3^k$ is an injection.
Because any infinite subset of a denumerable set is denumerable, we are done.

3. Thanks for the definition.

Why did you choose just 2 and 3?

4. They work.
Prove that function is an injection.

5. But how can this be a bijection? Doesn´t bijective also mean surjective? Can $\displaystyle 2^{j}3^{k} = 5$ ?

6. It's not a bijection with $\displaystyle \mathbb{N}$. It is a bijection with the set $\displaystyle \{2^i3^j\ |\ i,j\in \mathbb{N}\}$.

7. Originally Posted by ecnanif
But how can this be a bijection? Doesn´t bijective also mean surjective? Can $\displaystyle 2^{j}3^{k} = 5$ ?
Well of course it is not a bijection! All it has to is an injection.
Because an infinite subset of a denumerable set is denumerable

But if you are required to have a bijection, here is one:
$\displaystyle (0,0)\mapsto 0~\&~(j,k)\mapsto 2^j(2k-1)$.
But that is harder to prove.

8. So if $\displaystyle (i,j) \neq (x,y)$ and
$\displaystyle \begin{array}{ccc} 2^{j}3^{k}=A \\ 2^{x}3^{y}=A \end{array}$
We get that $\displaystyle 2^{j}3^{k}=2^{x}3^{y} \Leftrightarrow 2^{j-x}3^{k-y}=1$
And this implies $\displaystyle j=x \mbox{ and } k=y$

So $\displaystyle f$ is an injection.
What have we shown? The codomain of $\displaystyle f$ is a subset of $\displaystyle \mathbb{N}$ ?

Thanks again

9. The codomain is an infinite subset of N- and so denumerable.

As Plato said before, "an infinite subset of a denumerable set is denumerable".

As for showing that Q is denumerable, now you can use: every positive number in Q, $\displaystyle Q^+$, can be written in the form $\displaystyle \frac{m}{n}$ where m and n are relatively prime integers in N. The mapping $\displaystyle \frac{m}{n}\to (m, n)$ is an injection from $\displaystyle Q^+$ to NxN showing the $\displaystyle Q^+$ is denumerable. The set of negative rationals can be handled in the same way and the union of two denumerable sets is denumerable.

10. Originally Posted by HallsofIvy
As Plato said before, "an infinite subset of a denumerable set is denumerable".
Thanks all! This was a very important point.