Ceiling defines Equivalence Relation

From ProofWiki
Jump to: navigation, search

Theorem

Let $\mathcal R$ be the relation defined on $\R$ such that:

$\forall x, y, \in \R: \left({x, y}\right) \in \mathcal R \iff \left \lceil {x}\right \rceil = \left \lceil {y}\right \rceil$

where $\left \lceil {x}\right \rceil$ is the ceiling of $x$.


Then $\mathcal R$ is an equivalence, and $\forall n \in \Z$, the $\mathcal R$-class of $n$ is the half-open interval $\left({n - 1 \,.\,.\, n}\right]$.


Proof

Checking in turn each of the critera for equivalence:


Reflexivity

$\forall x \in \R: \left \lceil {x}\right \rceil = \left \lceil {x}\right \rceil$

Thus the ceiling function is reflexive.

$\Box$


Symmetry

$\forall x, y \in \R: \left \lceil {x}\right \rceil = \left \lceil {y}\right \rceil \implies \left \lceil {y}\right \rceil = \left \lceil {x}\right \rceil$

Thus the ceiling function is symmetric.

$\Box$


Transitivity

Let:

$\left \lceil {x}\right \rceil = \left \lceil {y}\right \rceil$
$\left \lceil {y}\right \rceil = \left \lceil {z}\right \rceil$

Let:

$n = \left \lceil {x}\right \rceil = \left \lceil {y}\right \rceil = \left \lceil {z}\right \rceil$

which follows from transitivity of $=$.

Thus:

$x = n - t_x, y = n - t_y, z = n - t_z: t_x, t_y, t_z \in \left[{0 \,.\,.\, 1}\right)$

from Real Number is Ceiling minus Difference‎.

So:

$x = n - t_x$

and:

$z = n - t_z$

and so:

$\left \lceil {x}\right \rceil = \left \lceil {z}\right \rceil$

Thus the ceiling function is transitive.

$\Box$


Thus we have shown that $\mathcal R$ is an equivalence.


Now we show that the $\mathcal R$-class of $n$ is the interval $\left({n - 1 \,.\,.\, n}\right]$.


Defining $\mathcal R$ as above, with $n \in \Z$:

\(\displaystyle x\) \(\in\) \(\displaystyle \left[\!\left[{n}\right]\!\right]_\mathcal R\)
\(\displaystyle \implies \ \ \) \(\displaystyle \left \lceil {x}\right \rceil\) \(=\) \(\displaystyle \left \lceil {n}\right \rceil = n\)
\(\displaystyle \implies \ \ \) \(\displaystyle \exists t \in \left({0 \,.\,.\, 1}\right]: x\) \(=\) \(\displaystyle n - t\)
\(\displaystyle \implies \ \ \) \(\displaystyle x\) \(\in\) \(\displaystyle \left({n - 1 \,.\,.\, n}\right]\)

$\blacksquare$