Diagonal Relation Equivalence

From ProofWiki

Jump to: navigation, search

Theorem

The diagonal relation $\Delta_S$ on $S$ is always an equivalence in $S$.

Checking in turn each of the criteria for equivalence:

$\displaystyle $

$\displaystyle \forall x \in S: \left({x, x}\right) \in \Delta_S$

$\displaystyle $

Definition of Diagonal Relation

So $\Delta_S$ is reflexive.

$\Box$

$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $		$\displaystyle \forall x, y \in S: \left({x, y}\right) \in \Delta_S$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle x = y$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of Diagonal Relation
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle y = x$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Equality is Symmetric
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle \left({y, x}\right) \in \Delta_S$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of Diagonal Relation

So $\Delta_S$ is symmetric.

$\Box$

$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $		$\displaystyle \forall x, y, z \in S: \left({x, y}\right) \in \Delta_S \land \left({y, z}\right) \in \Delta_S$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle x = y \land y = z$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of Diagonal Relation
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle x = z$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Equality is Transitive
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle \left({x, z}\right) \in \Delta_S$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of Diagonal Relation

So $\Delta_S$ is transitive.

$\blacksquare$

\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle \forall x, y \in S: \left({x, y}\right) \in \Delta_S\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle x = y\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Diagonal Relation
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle y = x\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Equality is Symmetric
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \left({y, x}\right) \in \Delta_S\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Diagonal Relation

\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle \forall x, y, z \in S: \left({x, y}\right) \in \Delta_S \land \left({y, z}\right) \in \Delta_S\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle x = y \land y = z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Diagonal Relation
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle x = z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Equality is Transitive
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \left({x, z}\right) \in \Delta_S\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Diagonal Relation