# Proving that $\lceil f(x) \rceil$ $=$ $\lceil f(\lceil x \rceil )\rceil$ when $f(x) =$ integer $\implies x =$ integer

On P. 71 in 'Concrete Mathematics' the following Theorem is given:

Let $f$ be any continuous, monotonically increasing function on an interval of the real numbers, with the property that \begin{equation}f(x) = \mathit{integer}\ \ \ \implies\ \ \ x = \mathit{integer} . \end{equation} Then we have \begin{equation} \lfloor f(x) \rfloor = \lfloor f(\lfloor x \rfloor )\rfloor\ \ \ \ and\ \ \ \lceil f(x) \rceil = \lceil f(\lceil x \rceil )\rceil, \end{equation} whenever $f(x)$, $f(\lfloor x \rfloor)$, and $f(\lceil x \rceil)$ are defined.

The proof for the second equation goes as follows:

If $x = \lceil x\rceil$, there's nothing to prove. Otherwise $x < \lceil x\rceil$, and $f(x) < f(\lceil x \rceil)$ since $f$ is increasing. Hence $\lceil f(x)\rceil \leq \lceil f(\lceil x\rceil)\rceil$, since $\lceil \cdot\rceil$ is nondecreasing. If $\lceil f(x) \rceil < \lceil f(\lceil x\rceil)\rceil$, there must be a number $y$ such that $x \leq y < \lceil x\rceil$ and $f(y) = \lceil f(x)\rceil$, since $f$ is continuous. This $y$ is an integer, because of $f$'s special property. But there cannot be an integer strictly between $\lfloor x\rfloor$ and $\lceil x\rceil$ . This contradiction implies that we must have $\lceil f(x) \rceil = \lceil f(\lceil x \rceil )\rceil$.

The part of the proof that I don't understand:

If $\lceil f(x) \rceil < \lceil f(\lceil x\rceil)\rceil$, there must be a number $y$ such that $x \leq y < \lceil x\rceil$ and $f(y) = \lceil f(x)\rceil$, since $f$ is continuous.

Why is $f(y)=\lceil f(x) \rceil$?

Note that the condition $\lceil f(x) \rceil < \lceil f(\lceil x\rceil)\rceil$ implies $\lceil f(x) \rceil < f(\lceil x\rceil)^{(*)}$, as otherwise $\lceil f(x) \rceil \geq f(\lceil x\rceil)$, which, by virtue of $\lceil f(x) \rceil$ being an integer, is equivalent to $\lceil f(x) \rceil \geq \lceil f(\lceil x\rceil)\rceil$, a contradiction. Since $f$ is continuous, it satisfies the intermediate value theorem. Therefore, since $f(x) \leq \lceil f(x) \rceil < f(\lceil x\rceil)$, there exists $y$ such that $x \leq y < \lceil x\rceil$ and $f(y) = \lceil f(x) \rceil$.

$^{(*)}$ There is no reason for the inequality $\lceil f(x) \rceil < f(\lceil x \rceil)$ to hold otherwise, as illustrated by $f(x) = x$, which satisfies the conditions of the theorem.

• Why is $\lceil f(x) \rceil \geq f(\lceil x \rceil)$ equivalent to $\lceil f(x) \rceil \geq \lceil f(\lceil x \rceil) \rceil$?? – Peter G. Chang Jul 14 '16 at 13:26
• @PeterG.Chang In general, if $x$ is real and $n$ is an integer, $x \leq n \iff \lceil x \rceil \leq n$. – Alex Provost Jul 14 '16 at 13:27
• I have just noticed that your answer is almost identical to mine. This is quite surprising. +1 anyway :) – BigbearZzz Jul 14 '16 at 13:42
• @BigbearZzz I'd be surprised if there actually existed a drastically different proof! – Alex Provost Jul 14 '16 at 13:49
• @AlexProvost You actually have a point here. I can't think of a different method either! – BigbearZzz Jul 14 '16 at 13:53

Consider the case where $x< \lceil x\rceil$ and assume that$\lceil f(x)\rceil <\lceil f(\lceil x\rceil)\rceil$.

Firstly, $f(x)$ cannot be an integer or we'd have that $x$ must be an integer, a contradiction to $x< \lceil x\rceil.$ Hence $$f(x)<\lceil f(x)\rceil.$$ Also, since $\lceil f(x)\rceil$ is an integer, $\lceil f(x)\rceil <\lceil f(\lceil x\rceil)\rceil$ implies that $$\lceil f(x)\rceil<f(\lceil x\rceil).$$

Combining the above 2 inequalities, we have $f(x)<\lceil f(x)\rceil <f(\lceil x\rceil)$.

By the intermidiate value theorem, there is a $y\in(x,\lceil x\rceil)$ such that $f(y)=\lceil f(x)\rceil$.

• I'd remove this part of the second sentence: "Assuming that$\lceil f(x)\rceil <\lceil f(\lceil x\rceil)\rceil$" because, as, phrased like that, it seems like it somehow help us conclude that $f(x)$ cannot be an integer. – Alex Provost Jul 14 '16 at 13:55
• Oh, I see it now. It was a part of my old proof that contained some errors before I rewrite it. Thank you for pointing that out. – BigbearZzz Jul 14 '16 at 14:02
• What I mean is that writing "Assuming $X$, we cannot have $Y$ as otherwise $Z$, a contradiction" makes it seem like you're proving the implication $X \implies \neg Y$, which is not what you're doing here! – Alex Provost Jul 14 '16 at 14:04
• Fixed :) This should look better, I hope. – BigbearZzz Jul 14 '16 at 14:12