# Countable set problem

• Feb 16th 2008, 01:14 AM
namelessguy
Countable set problem
Can somebody please give me some help on this analysis problem?
Show that the set of all nondecreasing functions from N on to {0,1,2} is countable?
• Feb 16th 2008, 08:10 AM
CaptainBlack
Quote:

Originally Posted by namelessguy
Can somebody please give me some help on this analysis problem?
Show that the set of all nondecreasing functions from N on to {0,1,2} is countable?

First consider an increasing function from $\mathbb{N}$ to $\{0, 1, 2\}$ which takes all three
values $0, 1, 2$. This is charaterised by two natural numbers $n_1$ and $n_2$,
where the function changes from $0$ to $1$, and from $1$ to $2$. The set of ordered
pairs of naturals is countable (you should already know this, so the set of
increasing functions from $\mathbb{N}$ to $\{0, 1, 2\}$ which take all three values is
countable.

Now the set of all functions that we seek is the union of those that take all
three values as considered above, those that take two of the possible values.
You need to show that this latter set of functions is also countable. Then use
the result that the union of two countable sets is also countable.

RonL