Reflexive contains Diagonal Relation

From ProofWiki

Jump to: navigation, search

Theorem

A relation $\mathcal R \subseteq S \times S$ is reflexive iff it contains the diagonal relation: $\Delta_S \subseteq \mathcal R$.

Then $\exists \left({x, x}\right): \left({x, x}\right) \notin \mathcal R$.

Thus $\exists x \in S: \left({x, x}\right) \notin \mathcal R$

and so $\mathcal R$ is not reflexive.

	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle \forall x \in S: \left({x, x}\right)$	$\in$	$\displaystyle \Delta_S$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Diagonal Relation
	$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle \forall x \in S: \left({x, x}\right)$	$\in$	$\displaystyle \mathcal R$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of Subset

Thus $\mathcal R$ is reflexive.

$\blacksquare$

Some sources use this as the definition of a reflexive relation.

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \forall x \in S: \left({x, x}\right)\)	\(\in\)	\(\displaystyle \Delta_S\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Diagonal Relation
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \forall x \in S: \left({x, x}\right)\)	\(\in\)	\(\displaystyle \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Subset