Prove that sets are denumerable

**ecnanif** · June 28th 2010, 03:48 AM

Hi!

Problem:

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

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

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

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

Help appreciated!

**Plato** · June 28th 2010, 04:11 AM

Assuming that $\mathbb{N}=\{0,1,2,\cdots\}$ then a set is denumerable if it bijects with $\mathbb{N}$ .
$f:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ by $f<img src=$ j,k)\mapsto 2^j3^k" alt="f

j,k)\mapsto 2^j3^k" /> is an injection.
Because any infinite subset of a denumerable set is denumerable, we are done.

**ecnanif** · June 28th 2010, 04:26 AM

Thanks for the definition.

Why did you choose just 2 and 3?

**Plato** · June 28th 2010, 04:37 AM

They work.
Prove that function is an injection.

**ecnanif** · June 28th 2010, 06:58 AM

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

**roninpro** · June 28th 2010, 07:20 AM

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

**Plato** · June 28th 2010, 07:28 AM

Originally Posted by ecnanif

But how can this be a bijection? Doesn´t bijective also mean surjective? Can $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:
$(0,0)\mapsto 0~\&~(j,k)\mapsto 2^j(2k-1)$ .
But that is harder to prove.

**ecnanif** · June 28th 2010, 08:51 AM

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

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

Thanks again

**HallsofIvy** · July 1st 2010, 11:26 AM

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, $Q^+$ , can be written in the form $\frac{m}{n}$ where m and n are relatively prime integers in N. The mapping $\frac{m}{n}\to (m, n)$ is an injection from $Q^+$ to NxN showing the $Q^+$ is denumerable. The set of negative rationals can be handled in the same way and the union of two denumerable sets is denumerable.

**ecnanif** · July 4th 2010, 12:02 PM

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.

Thread: Prove that sets are denumerable

LinkBack

Thread Tools

Display

Prove that sets are denumerable

Similar Math Help Forum Discussions

Prove if two sets are denumerable then their union is denumerable

finite and infinite sets...denumerable

Denumerable sets...

denumerable sets

denumerable sets

Search Tags