# 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$