Transitive Closure of Symmetric Relation is Symmetric

Theorem

Let $S$ be a set.

Let $\RR$ be a symmetric relation on $S$.

Let $\TT$ be the transitive closure of $\RR$.

The $\TT$ is symmetric.

Proof

Let $a, b \in S$ with $a \mathrel \TT b$.

By the definition of transitive closure, there is an $n \in \N$ such that $a \mathrel {\RR^n} b $.

Thus there are $x_0, x_1, \dots x_n \in S$ such that:

$x_0 = a$

$x_n = b$

For $k = 0, \dots, n-1$: $x_k \mathrel \RR x_{k + 1}$

For $k = 0, \dots, n$, let $y_k = x_{n - k}$.

Then:

$y_0 = x_n = b$

$y_n = x_0 = a$

For $k = 0, \dots, n - 1$:

$x_{n - k - 1} \mathrel \RR x_{n - k}$

Thus:

$y_{k + 1} \mathrel \RR y_k$

Since $\RR$ is symmetric:

For $k = 0, \dots, n - 1$: $y_k \mathrel \RR y_{k + 1}$

Thus $b \mathrel {\RR^n} a$, so $b \mathrel \TT a$.

$\blacksquare$