Symmetric and Transitive Relation is not necessarily Reflexive
Theorem
Let $S$ be a set.
Let $\alpha \subseteq S \times S$ be a relation on $S$.
Let $\alpha$ be both symmetric and transitive.
Then it is not necessarily the case that $\alpha$ is also reflexive.
Proof 1
Let $S = \set {a, b, c}$.
Let:
- $\alpha = \set {\tuple {a, a}, \tuple {a, b}, \tuple {b, a}, \tuple {b, b} }$
By inspection it is seen that $\alpha$ is both symmetric and transitive.
However, we have:
- $\neg c \mathrel \alpha c$
Hence $\alpha$ is both symmetric and transitive but not reflexive.
$\blacksquare$
Proof 2
Let $S = \Z$ be the set of integers.
Let $\alpha$ be the relation on $S$ defined as:
- $\forall x, y \in S: x \mathrel \alpha y \iff x = y = 0$
\(\ds x\) | \(\alpha\) | \(\ds y\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds x\) | \(=\) | \(\ds y = 0\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds y\) | \(=\) | \(\ds x = 0\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds y\) | \(\alpha\) | \(\ds x\) |
Thus $\alpha$ is symmetric.
Now let $x \mathrel \alpha y$ and $y \mathrel \alpha z$
Then:
- $x = y = 0, y = z = 0$
and so
- $x \mathrel \alpha z$
Now let $x = \Z$ such that $x \ne 0$.
Then it is not the case that:
- $x \mathrel \alpha x$
and so $\alpha$ is not reflexive.
Hence $\alpha$ is both symmetric and transitive but not reflexive.
$\blacksquare$
Proof 3
Let $S = \set {1, 2}$ be a set.
Let $\RR$ be the relation on $S$ defined as:
- $\forall x, y \in S: x \mathrel \RR y \iff x = y = 2$
\(\ds x\) | \(\RR\) | \(\ds y\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds x\) | \(=\) | \(\ds y = 2\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds y\) | \(=\) | \(\ds x = 2\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds y\) | \(\RR\) | \(\ds x\) |
Thus $\alpha$ is symmetric.
Now let $x \mathrel \RR y$ and $y \mathrel \RR z$
Then:
- $x = y = 2, y = z = 2$
and so:
- $x \mathrel \RR z$
Now let $x = 1$.
Then it is not the case that:
- $x \mathrel \RR x$
and so $\RR$ is not reflexive.
Hence $\RR$ is both symmetric and transitive but not reflexive.
$\blacksquare$
Examples
Subset of Cartesian Plane
The subset of the Cartesian plane defined as:
- $\RR := \set {\tuple {x, y} \in \R^2: -1 \le x \le 1, -1 \le y \le 1}$
determines a relation on $\R^2$ which is symmetric and transitive but not reflexive.
Sources
- 1979: John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation ... (previous) ... (next): Chapter $1$: Preliminaries: Exercises: $1.9$