Relation Intersection Inverse is Greatest Symmetric Subset of Relation

Theorem

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

Let $\powerset \RR$ be the power set of $\RR$.

By definition, $\powerset \RR$ is the set of all relations on $S$ that are subsets of $\RR$.

Then the greatest element of $\powerset \RR$ that is symmetric is:

$\RR \cap \RR^{-1}$

$\RR \cap \RR^{-1}$ is a symmetric relation.

Suppose for some $\SS \in \powerset \RR$ that $S$ is symmetric and not equal to $\RR \cap \RR^{-1}$.

We will show that it is a proper subset of $\RR \cap \RR^{-1}$.

Suppose $\tuple {x, y} \in \SS$.

Then as $\SS \subseteq \RR$:

$\tuple {x, y} \in \RR$

As $\SS$ is symmetric:

$\tuple {x, y} \in \SS$

So as $\SS \subseteq \RR$:

$\tuple {x, y} \in \RR$

By definition of inverse relation:

$\tuple {x, y} \in \RR^{-1}$

By definition of intersection:

$\tuple {x, y} \in \RR \cap \RR^{-1}$

Thus:

$\tuple {x, y} \in \SS \implies \tuple {x, y} \in \RR \cap \RR^{-1}$

By definition of subset:

$\SS \subseteq \RR \cap \RR^{-1}$

Finally, as we assumed $\SS \ne \RR \cap \RR^{-1}$:

$\SS \subset \RR \cap \RR^{-1}$

Hence the result.

$\blacksquare$