0
$\begingroup$

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}$?"

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Oct 1 '18 at 0:02
  • $\begingroup$ @RossMillikan I agree with all 0, but isn't G(1) - the sequence of all 1? $\endgroup$ – dxdydz Oct 1 '18 at 0:32
  • $\begingroup$ 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$ $\endgroup$ – Ross Millikan Oct 1 '18 at 0:34
  • $\begingroup$ 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? $\endgroup$ – dxdydz Oct 1 '18 at 1:23
  • $\begingroup$ What l mean is that we can not list rationals from smallest to largest so we do not have the concept of next rational. $\endgroup$ – Mohammad Riazi-Kermani Oct 1 '18 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.