Let $f,g: [0,1] \to \mathbb{R}$ be increasing functions such that $f<g$.
I am interested in obtaining an increasing function $s:[0,1] \to \mathbb{R}$ which is discrete (i.e. $s([0,1])$ countable) with $f \le s < g$.
I can think of a way to do this with Zorn's lemma; by transfinite induction on the following succession of steps:
- Firstly, start at $x = 1$.
- As $f(x) < g(x)$, we can find $0 < q < g(x)-f(x)$. Define $s(t) = g(x) $ on $[1-q, 1]$. (Then, $f \le s < g$ on $[1-q,1]$.)
- Repeat, but now starting at $x = 1-q$.
It is quite easy to see that the obvious poset satisfies the condition for Zorn's lemma (simply take the union of the partially constructed functions) and that the resulting maximal element will then be defined on $[0,1]$. Further, $s$ is seen to be discrete, since each value in its image may be associated to an interval of width $q$, which contains a rational. Thus, $s([0,1]) \hookrightarrow \mathbb{Q}$, and so the image is countable.
Question: Is it possible to demonstrate that such a function $s$ exists without the Axiom of (Dependent) Choice? If so, how?
It feels natural to try something like $s = 2^{-n} \lceil 2^n f \rceil$, but this doesn't quite work since, for any $n$, there may exist $t$ such that $g(t)-f(t) < 2^{-n}$. It seems to me that constructing $s$ requires a certain level of flexibility for which Choice is needed.
You don't need any choice.
Enumerate the rational numbers, then $s(x)$ is the least rational number (in the enumeration!) which lies in the interval $(f(x), g(x))$.
Do note, however, that "discrete" is not synonymous with "countable". At all.