Trivial Relation is Equivalence

From ProofWiki
Jump to: navigation, search

Theorem

The trivial relation on $S$:

$\mathcal R = S \times S$

is always an equivalence in $S$.


Proof

Let us verify the conditions for an equivalence in turn.


Reflexivity

For $\mathcal R$ to be reflexive means:

$\forall x \in S: \tuple {x, x} \in S \times S$

which is trivial by definition of the Cartesian product $S \times S$.

$\Box$


Symmetry

For $\mathcal R$ to be symmetric means:

$\forall x, y \in S: \tuple {x, y} \in S \times S \land \tuple {y, x} \in S \times S$

Since we have by definition of Cartesian product that:

$\forall x, y \in S: \tuple {y, x} \in S \times S$

this follows by True Statement is implied by Every Statement.

$\Box$


Transitivity

For $\mathcal R$ to be transitive means:

$\tuple {x, y} \in S \times S \land \tuple {y, z} \in S \times S \implies \tuple {x, z} \in S \times S$

By definition of Cartesian product, we have that:

$\forall x, z \in S: \tuple {x, z} \in S \times S$

hence by True Statement is implied by Every Statement, it follows that $\mathcal R$ is transitive.

$\Box$


Having verified all three conditions, we conclude $\mathcal R$ is an equivalence.

$\blacksquare$


Sources