# Thread: Proving a set denumerable

1. ## Proving a set denumerable

Hi

I my book, it says: To prove that a set $\displaystyle A$ is denumerable you should find a bijection $\displaystyle f : \mathbb{N} \to \mathbb{A}$.

Now, I need to prove that $\displaystyle \mathbb{Q}$ is denumerable.
So I replace my $\displaystyle A$ with $\displaystyle \mathbb{Q}$ in the previous paragraph. Now I need to find a bijection $\displaystyle f$.

Would it be equivalent to find a bijection $\displaystyle f: \mathbb{Q} \to \mathbb{N}$ ?
If so, I need to find a function that takes the rational numbers to $\displaystyle \mathbb{N}$. Also, it need to be injective.
It should be suffiecient to find a bijection $\displaystyle f: \mathbb{Q} \to G \subseteq \mathbb{N}$ ?

What could $\displaystyle f$ look like?

Thanks

2. Originally Posted by ecnanif

I my book, it says: To prove that a set $\displaystyle A$ is denumerable you should find a bijection $\displaystyle f : \mathbb{N} \to \mathbb{A}$.

Now, I need to prove that $\displaystyle \mathbb{Q}$ is denumerable.
So I replace my $\displaystyle A$ with $\displaystyle \mathbb{Q}$ in the previous paragraph. Now I need to find a bijection $\displaystyle f$.

Would it be equivalent to find a bijection $\displaystyle f: \mathbb{Q} \to \mathbb{N}$ ?
If so, I need to find a function that takes the rational numbers to $\displaystyle \mathbb{N}$. Also, it need to be injective.
It should be suffiecient to find a bijection $\displaystyle f: \mathbb{Q} \to G \subseteq \mathbb{N}$ ?

What could $\displaystyle f$ look like?
no it would not be equivalent to find a bijection $\displaystyle f: \mathbb{Q} \to \mathbb{N}$ becuase Q contains N so a trivial function would be $\displaystyle f: \mathbb{N} \to \mathbb{N}$. You need to find a function $\displaystyle f : \mathbb{N} \to \mathbb{Q}$. Also bijection means both injection and surjection. so u don't need to single out injective.

for example, to prove that $\displaystyle \mathbb{Q^{+}}$ is denumerable. notice you can break $\displaystyle \mathbb{Q^{+}}$ into classes depending on what the numerator and denominator adds up to like class{2} = 1/1, class{3} = 1/2, 2/1 class{4} = 3/1, 1/3 etc.... and each of these classes is finite...

3. Consider the cross product of positive integers, $\displaystyle \mathbb{Z}^+\times \mathbb{Z}^+$.
Map that set to $\displaystyle \mathbb{Z}^+$ by $\displaystyle \phi(m,n)=2^{m-1}(2m-1)$
It can be shown that $\displaystyle \phi$ is a bijection.
The positive rational can be seen as a subset of $\displaystyle \mathbb{Z}^+\times \mathbb{Z}^+$.
So they are denumerable. Clearly we can extend this to the entire set of rationals.