Thread: Proving a set denumerable

1. Proving a set denumerable

Hi

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

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

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

What could $f$ look like?

Thanks

2. Originally Posted by ecnanif

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

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

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

What could $f$ look like?
no it would not be equivalent to find a bijection $f: \mathbb{Q} \to \mathbb{N}$ becuase Q contains N so a trivial function would be $f: \mathbb{N} \to \mathbb{N}$. You need to find a function $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 $\mathbb{Q^{+}}$ is denumerable. notice you can break $\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, $\mathbb{Z}^+\times \mathbb{Z}^+$.
Map that set to $\mathbb{Z}^+$ by $\phi(m,n)=2^{m-1}(2m-1)$
It can be shown that $\phi$ is a bijection.
The positive rational can be seen as a subset of $\mathbb{Z}^+\times \mathbb{Z}^+$.
So they are denumerable. Clearly we can extend this to the entire set of rationals.