Characteristics of Floor and Ceiling Function

From ProofWiki
Jump to: navigation, search

Theorem

Let $f: \R \to \Z$ be an integer-valued function which satisfies both of the following:

$(1): \quad f \paren {x + 1} = f \paren x + 1$
$(2): \quad \forall n \in \Z_{> 0}: f \paren x = f \paren {\dfrac {f \paren {n x} } n}$


Then either:

$\forall x \in \Q: f \paren x = \floor x$

or:

$\forall x \in \Q: f \paren x = \ceiling x$


Real Domain

Let $f: \R \to \Z$ be an integer-valued function which satisfies both of the following:

$(1): \quad \map f {x + 1} = \map f x + 1$
$(2): \quad \forall n \in \Z_{> 0}: \map f x = \map f {\dfrac {\map f {n x} } n}$


Then it is not necessarily the case that either:

$\forall x \in \R: \map f x = \floor x$

or:

$\forall x \in \R: \map f x = \ceiling x$


Proof

From $(1)$, by induction we have:

$\forall n \in \N: f \paren {x + n} = f \paren x + n$

and

$\forall n \in\N: f \paren {x - n} = f \paren x - n$

and therefore, in particular:

$(3): \quad \forall n \in \Z: f \paren n = f \paren 0 + n$


From $(2)$, we get

\(\displaystyle f \paren 0\) \(=\) \(\displaystyle f \paren {f \paren 0}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle f \paren 0 + f \paren 0\) $\quad$ using $(3)$ and $f$ being integer valued $\quad$

Hence

$f \paren 0 = 0$


Thus from $(3)$ it follows that:

$\forall n \in \Z: f \paren n = n$

Suppose that $f \paren {\dfrac 1 2} = k \le 0$.

Then:

\(\displaystyle k\) \(=\) \(\displaystyle f \paren {\dfrac 1 {1 - 2 k} f \paren {\dfrac 1 2 - k} }\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle f \paren {\dfrac 1 {1 - 2 k} \paren {f \paren {\dfrac 1 2} - k} }\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle f \paren 0\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 0\) $\quad$ $\quad$


We show that in this case, by induction:

$f \paren {\dfrac 1 n} = 0$ for all $n \in \N$


Induction hypothesis:

$f \paren {\dfrac 1 {n - 1} } = 0$

Then from $(1)$:

$f \paren {\dfrac n {n - 1} } = f \paren {\dfrac 1 {n - 1} + 1} = 0 + 1 = 1$

so:

\(\displaystyle f \paren {\dfrac 1 n}\) \(=\) \(\displaystyle f \paren {\dfrac 1 n f \paren {\dfrac n {n - 1} } }\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle f \paren {\dfrac 1 {n - 1} }\) $\quad$ using $(2)$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 0\) $\quad$ $\quad$

Finally, we show by induction on $m$ that even:

$f \paren {\dfrac m n} = 0$

for $m \in \set {1, \ldots, n - 1}$.


Above we have shown this for $m = 1$.

Let $1 \le m < n$.

If $m \divides n$, then

$f \paren {\dfrac m n} = f \paren {\dfrac 1 {n / m} } = 0$

Otherwise, write:

$ n = \paren {k - 1} m + r$

Then:

$k > 1$

and:

$1 \le r \le m - 1$

We therefore have:

$k m = n + m - r$

so by the induction hypothesis:

$f \paren {\dfrac {k m} n} = f \paren {1 + \dfrac {m - r} n} = 1 + f \paren {\dfrac {m - r} n} = 1$

Then:

\(\displaystyle f \paren {\dfrac m n}\) \(=\) \(\displaystyle f \paren {\dfrac 1 m f \paren {\dfrac {m k} n} }\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle f \paren {\dfrac 1 m}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 0\) $\quad$ $\quad$


By $(1)$, this shows that

$f \paren {\dfrac 1 2} \le 0 \implies f \paren x = \floor x$

for all rational $x$.


Suppose that $f \paren {\dfrac 1 2} = k > 0$.

Then the integer-valued function $g: \R \to \Z$ satisfies:

$g \paren x = -f \paren {-x}$

satisfies $(1)$ and $(2)$, and also:

\(\displaystyle g \paren {\dfrac 1 2}\) \(=\) \(\displaystyle 1 - f \paren {\dfrac 1 2}\) $\quad$ $\quad$
\(\displaystyle \) \(\ge\) \(\displaystyle 0\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle f \paren x\) \(=\) \(\displaystyle -g \paren {-x}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle -\floor {-x}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \ceiling x\) $\quad$ Floor of Negative equals Negative of Ceiling $\quad$


Thus:

$f \paren {\dfrac 1 2} > 0 \implies f \paren x = \ceiling x$

for all rational $x$.

$\blacksquare$


Historical Note

The result Characteristics of Floor and Ceiling Function was presented by Peter Eisele and Karl Peter Hadeler in $1990$.

The previous work done in $1905$ by Georg Hamel to establish that the result does not necessarily hold in the real domain is to be noted.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Characteristics_of_Floor_and_Ceiling_Function&oldid=368901"