# How can we prove these sets are countable?

• Feb 3rd 2009, 09:35 AM
ninano1205
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.(Headbang)
• Feb 3rd 2009, 10:01 AM
Plato
Quote:

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.
• Feb 3rd 2009, 10:52 AM
ninano1205
Could you give me little more detail?
• Feb 3rd 2009, 11:10 AM
Plato
Quote:

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.
• Feb 3rd 2009, 11:21 AM
ninano1205
??
Where did you get 2^m*3^n??
• Feb 3rd 2009, 11:52 AM
Plato
Quote:

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.
• Feb 3rd 2009, 01:41 PM
ninano1205
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. ??
• Feb 3rd 2009, 02:07 PM
Plato
Quote:

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.