Characteristics of Floor and Ceiling Function

From ProofWiki
Jump to navigation Jump to search


This article needs to be tidied.
In particular: Introduce standard $\mathsf{Pr} \infty \mathsf{fWiki}$ style for induction proof -- breaks it down and makes it easier to comprehend visually
Please fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Tidy}} from the code.


Theorem

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 either:

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

or:

$\forall x \in \Q: \map f 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: \map f {x + n} = \map f x + n$

and

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

and therefore, in particular:

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


From $(2)$, we get

\(\ds \map f 0\) \(=\) \(\ds \map f {\map f 0}\)
\(\ds \) \(=\) \(\ds \map f 0 + \map f 0\) using $(3)$ and $f$ being integer valued

Hence

$\map f 0 = 0$


Thus from $(3)$ it follows that:

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

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

Then:

\(\ds k\) \(=\) \(\ds \map f {\dfrac 1 {1 - 2 k} \map f {\dfrac 1 2 - k} }\)
\(\ds \) \(=\) \(\ds \map f {\dfrac 1 {1 - 2 k} \paren {\map f {\dfrac 1 2} - k} }\)
\(\ds \) \(=\) \(\ds \map f 0\)
\(\ds \) \(=\) \(\ds 0\)


We show that in this case, by induction:

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


Induction hypothesis:

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

Then from $(1)$:

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

so:

\(\ds \map f {\dfrac 1 n}\) \(=\) \(\ds \map f {\dfrac 1 n \map f {\dfrac n {n - 1} } }\)
\(\ds \) \(=\) \(\ds \map f {\dfrac 1 {n - 1} }\) using $(2)$
\(\ds \) \(=\) \(\ds 0\)

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

$\map f {\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

$\map f {\dfrac m n} = \map f {\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:

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

Then:

\(\ds \map f {\dfrac m n}\) \(=\) \(\ds \map f {\dfrac 1 m \map f {\dfrac {m k} n} }\)
\(\ds \) \(=\) \(\ds \map f {\dfrac 1 m}\)
\(\ds \) \(=\) \(\ds 0\)


By $(1)$, this shows that

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

for all rational $x$.


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

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

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

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

\(\ds \map g {\dfrac 1 2}\) \(=\) \(\ds 1 - \map f {\dfrac 1 2}\)
\(\ds \) \(\ge\) \(\ds 0\)
\(\ds \leadsto \ \ \) \(\ds \map f x\) \(=\) \(\ds -\map g {-x}\)
\(\ds \) \(=\) \(\ds -\floor {-x}\)
\(\ds \) \(=\) \(\ds \ceiling x\) Floor of Negative equals Negative of Ceiling


Thus:

$\map f {\dfrac 1 2} > 0 \implies \map f 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=451172"