Trivial Relation is Equivalence
Jump to navigation
Jump to search
Theorem
The trivial relation on $S$:
- $\RR = S \times S$
is always an equivalence in $S$.
Proof
Let us verify the conditions for an equivalence in turn.
Reflexivity
For $\RR$ 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 $\RR$ 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 $\RR$ 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 $\RR$ is transitive.
$\Box$
Having verified all three conditions, we conclude $\RR$ is an equivalence.
$\blacksquare$
Sources
- 1960: Paul R. Halmos: Naive Set Theory ... (previous) ... (next): $\S 7$: Relations
- 1967: George McCarty: Topology: An Introduction with Application to Topological Groups ... (previous) ... (next): Chapter $\text{I}$: Sets and Functions: Relations
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Appendix $\text{A}.3$: Equivalence Relations: Problem Set $\text{A}.3$: $15$