Characteristic function of a the range of a strictly increasing function.

Question

I am trying to prove that the range of a strictly increasing recursive function is a recursive set. And I have found an answer here:

Image of a strictly increasing computable function is computable?

In the post, it is mentioned that:

if $f$ is strictly increasing, doesn't that just immediately provide a bound for existential quantification? So we have $g(y)=1\ iff\ \exists x\leq y: f(x)=y$ be computable as well.

I think it is just to define the characteristic function to be:

$g(y)=1$ if $\exists x\leq y: f(x)=y$

$g(y)=0$ otherwise.

But I have not get it clear. May I please ask for a more explicit explaination on how can we see that $g$ defined in this way is the characteristic function of a strictly increasing $f$. That is, $y\in range(f)\Leftrightarrow g(y)=1$.

Thanks in advance!

Answer 1

Clearly $g$ is the characteristic function of a subset of the range of $f$, so we just have to prove that it's the characteristic function of the whole thing; that is, if $f(x)=y$ for some $x$, then $f(x)=y$ for some $x\le y$.

But this is a general fact about increasing function from $\mathbb{N}$ to $\mathbb{N}$!

Prove that if $f: \mathbb{N}\rightarrow\mathbb{N}$ is increasing, then for all $x$ we have $f(x)\ge x$.

HINT: what's the smallest thing $f(0)$ could be? Given that, what's the smallest thing $f(1)$ could be? Etc. (Note that the statement fails if we replace $\mathbb{N}$ in the codomain with $\mathbb{Z}$.)

Now if $f(x)\ge x$ for all $x$, this means that $f(x)=y$ implies $y\ge x$, so we're done.