# Thread: How can we prove these sets are countable?

1. ## How can we prove these sets are countable?

a) The set of all numbers with two distinct decimal expansions(like 0.5000..., and 0.4999...)

b) The set of all rational points in the plane

c) The set of all rational intervals

d) The set of all polynomials with rational coefficients

I've seen the proof of "the set Q of all rational numbers is countable"
but can't figure out the above.

2. Originally Posted by ninano1205
a) The set of all numbers with two distinct decimal expansions(like 0.5000..., and 0.4999...)
b) The set of all rational points in the plane
c) The set of all rational intervals
d) The set of all polynomials with rational coefficients
Let $\mathbb{N} = \left\{ {0,1,2, \cdots } \right\}$, the non-negative integers.
Define $f:\mathbb{N} \times \mathbb{N} \mapsto \mathbb{N}$ as $f(m,n) = 2^m \cdot 3^n$.
It is easy to show that $f$ is an injection which implies that $\mathbb{N} \times \mathbb{N}$ is a countable set.
That idea can be extended to $\underbrace {\mathbb{N} \times \mathbb{N} \times \mathbb{N} \cdots \times \mathbb{N} \times \mathbb{N}}_k$ by using a ordered listing of the primes as we used $2\;\&\;3$ above. Hence that set is countable.
Of course this can be extended set of all integers and to the set of all rational numbers.

Now all your questions are proven by a simple application of this basic idea.

3. ## Could you give me little more detail?

Not easy to comprehend...

4. Originally Posted by ninano1205
Not easy to comprehend.
Show that $f:\mathbb{N} \times \mathbb{N} \mapsto \mathbb{N}$ as $f(m,n) = 2^m \cdot 3^n$ is an injection.

5. ## ??

Where did you get 2^m*3^n??

6. Originally Posted by ninano1205
Where did you get 2^m*3^n??
You are just stalling! Do you know how to show that function is one-to-one?
It matters not where the numbers came from. We need to know where you are.

7. ## one to one

If we can invert a function, it is one to one. After inverting it and if it possess a non-empty domain in the real numbers , then it is one to one, or injective. ??

8. Originally Posted by ninano1205
If we can invert a function, it is one to one. After inverting it and if it possess a non-empty domain in the real numbers , then it is one to one, or injective. ??
Thank you for your reply. I now see the problems you are having.
My advice to you is simple: “Drop this current sequence of questions”.
Go back to the basics. Learn how one proves a function is an injection, a surjection, and/or a bijection.
Learn how compositions of such function work.
Unless one has a through and complete understanding of that material, the idea of doing a proof involving cardinalities of set is out of the question.