Ceiling Defines Equivalence

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:

Reflexive

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

Symmetric

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

Transitive

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

Thus $x = n - t_x, z = n - t_z$ and $\left \lceil {x}\right \rceil = \left \lceil {z}\right \rceil$.

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

$\blacksquare$