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.

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

  • $\begingroup$ 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. $\endgroup$ – Alex Provost Jul 14 '16 at 13:55
  • $\begingroup$ 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. $\endgroup$ – BigbearZzz Jul 14 '16 at 14:02
  • $\begingroup$ 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! $\endgroup$ – Alex Provost Jul 14 '16 at 14:04
  • $\begingroup$ Fixed :) This should look better, I hope. $\endgroup$ – BigbearZzz Jul 14 '16 at 14:12

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.