# set of non-decreasing functions from Q->{0,1}

Given the set $$A= \{f:ℤ→\{0,1\}| if x \geq y, f(x)\geq f(y)\}$$ - set of non-decreasing functions from $$\mathbb{Z}$$ to $$\{0,1\}$$. I want to prove that A is countable, hence I'm trying to build a bijection $$\mathbb{N}→A$$,but I don't know how to proceed. I suppose I need to prove that the point where the function changes its value has countable number of choices. Can anybody help me? And the other question I want to ask is: "Will A still be countable if we replace $$\mathbb{Z}$$ with $$\mathbb{Q}$$?"

## 2 Answers

For $$\Bbb Z$$, most of the nondecreasing functions start with an infinite run of $$0$$s, then step up to $$1$$ at some point and have $$1$$s from there on out. A natural bijection with the integers is the point they step up. There are two more functions you need to worry about, the one that is all $$0$$s and the one that is all $$1$$s. You just need to biject the integers plus two points with $$N$$ and you are done.

No, $$A$$ will not be countable if you replace $$\Bbb Z$$ with $$\Bbb Q$$. Your functions are then Dedekind cuts and you get one for each real.

Your functions are sequences with terms zero or one such that if you have a single one then you have all ones after that.

So the location where the first one appears determines your function uniquely.

Thus you have a one to one function $$G:Z\to A$$ where $$G(k)$$ is the sequence which has all zeros up to $$k-1$$ term and all ones starting at the $$k^{th}$$ term.

Similar argument does not work for $$Q$$ instead of $$Z$$ because you can not make a sequence of all rational numbers where order is preserved.

• You can't really talk about the $k^{th}$ term of a function on the integers, but you can just change to $G(k)$ is all zeros up to $k-1$. This misses the all $0$ and all $1$ functions. – Ross Millikan Oct 1 '18 at 0:02
• @RossMillikan I agree with all 0, but isn't G(1) - the sequence of all 1? – dxdydz Oct 1 '18 at 0:32
• No, $\Bbb Z$ is the integers, so $G(1)$ is the function that is $0$ for any argument less than $1$, the negatives and $0$, and is $1$ for any argument $\ge 1$. $G(-5)$ is the function that is $0$ for any argument $\le -6$ and $1$ for any argument $\ge -5$ – Ross Millikan Oct 1 '18 at 0:34
• I didn't get the part about rational numbers, can you explain again the case with Q by giving an example for Q where order is not preserved? – dxdydz Oct 1 '18 at 1:23
• What l mean is that we can not list rationals from smallest to largest so we do not have the concept of next rational. – Mohammad Riazi-Kermani Oct 1 '18 at 2:10