$f:N \to Z | f(1)=0 $ and $n<m \Rightarrow f(n) < f(m)$. Prove $\forall x\in N$, there are unique $n,p \in N$ s.t $f(n) < x \leq f(n+1)$ x = f(n) + p.

Question

Let $f:\mathbb{N} \to \mathbb{N} \cup \{ 0 \} $ be a function.Suppose that $f(1)=0$, and that if $n<m$ then $f(n) < f(m)$ for all $n,m \in $ $\mathbb{N}.$Prove for each $x\in \mathbb{N}$, there are unique $n,p \in \mathbb{N}$ such that $f(n) < x \leq f(n+1)$ and $x = f(n) +$ $p$.

Firstly, I thought we have to show the existence of $x$ and $p$, and then we should show that they are unique.

For the first part, we know that f is a strictly increasing function from the definition, so since $x = f(n) + p$, if we plug x into the inequality $f(n) < x \leq f(n+1)$, we get $$f(n) + p \leq f(n+1),$$ which tells us that there is some p satisfying the conditions if there is x satisfying the necessary conditions.However, after that, I couldn't find how to show the existence of x.

As the second part, I think there is a problem in the theorem abut the uniqueness because from the inequality $$f(n) + p \leq f(n+1)$$ we can deduce that if the difference between $f(n+1)$ and $f(n)$ is more than $1$, is not unique.

To sum up, How can we show the existence of $x$ and the uniqueness of $x$ and $p$ ?

Note: Please the answer be in the level of first year of mathematics studies.

Answer 1

Note: Based on your question, you are given $x$ and have to show the existence of $n$ and $p$.

Given $x \in \mathbb{N}$, define the set $$S_x=\{a \in \mathbb{N}\, | \, f(a) < x\}$$ Due to the increasing nature of $f$ this set is finite, hence it has a unique maximum element. Let $n=\max{S_x}$, then $f(n)<x$. So now you have the existence of $n$. For getting $p$, we just define $p=x-f(n)$.

Answer 2

By induction on $n\in \mathbb N$ show that $f(n)\geq n-1.$ So for $x\in \mathbb N$ there exists $m$ with $f(m)\geq x,$ because $f(x+1)\geq x.$

Let $n_x'$ be the least $m\in \mathbb N$ such that $f(m)\geq x.$ Then $n_x'>1,$ otherwise $0=f(1)=f(n_x')\geq x\geq 1.$ So $n_x'-1\in \mathbb N,$ so $f(n_x'-1)$ exists.

Let $n_x=n_x'-1 .$ Since $n'_x>n_x\in \mathbb N,$ the def'n of $n_x'$ implies $x>f(n_x).$ So $$f(n_x)<x\leq f(n'_x)=f(n_x+1).$$ We can't have $f(n^*)<x\leq f(n^*+1)$ for $n^*\ne n_x,$ because $$(i).\; n^*<n_x\implies n^*+1\leq n_x\implies f(n^*+1)\leq f(n_x)<x,$$ $$(ii).\; n^*>n_x\implies n^*\geq n_x+1\implies f(n^*)\geq f(n_x+1)\geq x.$$ Since $n_x$ is uniquely determined by $x,$ so also is $p_x=x-f(n_x)$.