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?

Printable View

- Feb 16th 2008, 01:14 AMnamelessguyCountable 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 AMCaptainBlack
First consider an increasing function from $\displaystyle \mathbb{N}$ to $\displaystyle \{0, 1, 2\}$ which takes all three

values $\displaystyle 0, 1, 2$. This is charaterised by two natural numbers $\displaystyle n_1$ and $\displaystyle n_2$,

where the function changes from $\displaystyle 0$ to $\displaystyle 1$, and from $\displaystyle 1$ to $\displaystyle 2$. The set of ordered

pairs of naturals is countable (you should already know this, so the set of

increasing functions from $\displaystyle \mathbb{N}$ to $\displaystyle \{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