5
$\begingroup$

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$?

$\endgroup$

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
5
  • $\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$ Jul 14, 2016 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$ Jul 14, 2016 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, 2016 at 13:42
  • 1
    $\begingroup$ @BigbearZzz I'd be surprised if there actually existed a drastically different proof! $\endgroup$ Jul 14, 2016 at 13:49
  • $\begingroup$ @AlexProvost You actually have a point here. I can't think of a different method either! $\endgroup$
    – BigbearZzz
    Jul 14, 2016 at 13:53
2
$\begingroup$

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$.

$\endgroup$
4
  • $\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$ Jul 14, 2016 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, 2016 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$ Jul 14, 2016 at 14:04
  • $\begingroup$ Fixed :) This should look better, I hope. $\endgroup$
    – BigbearZzz
    Jul 14, 2016 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.