Relation Intersection Inverse is Greatest Symmetric Subset of Relation

From ProofWiki
Jump to: navigation, search

Theorem

Let $\mathcal R$ be a relation on a set $S$.

Let $\mathcal P \left({\mathcal R}\right)$ be the power set of $\mathcal R$.

By definition, $\mathcal P \left({\mathcal R}\right)$ is the set of all relations on $S$ that are subsets of $\mathcal R$.

Then the greatest element of $\mathcal P \left({\mathcal R}\right)$ that is symmetric is:

$\mathcal R \cap \mathcal R^{-1}$


Proof

By Intersection of Relation with Inverse is Symmetric Relation:

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


Suppose for some $\mathcal S \in \mathcal P \left ({\mathcal R} \right)$ that $S$ is symmetric and not equal to $\mathcal R \cap \mathcal R^{-1}$.

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

Suppose $\left({x, y}\right) \in \mathcal S$.

Then as $\mathcal S \subseteq \mathcal R$:

$\left({x, y}\right) \in \mathcal R$

As $\mathcal S$ is symmetric:

$\left({y, x}\right) \in \mathcal S$

So as $\mathcal S \subseteq \mathcal R$:

$\left({y, x}\right) \in \mathcal R$

By definition of inverse relation:

$\left({x, y}\right) \in \mathcal R^{-1}$

By definition of intersection:

$\left({x, y}\right) \in \mathcal R \cap \mathcal R^{-1}$

Thus:

$\left({x, y}\right) \in \mathcal S \implies \left({x, y}\right) \in \mathcal R \cap \mathcal R^{-1}$

By definition of subset:

$\mathcal S \subseteq \mathcal R \cap \mathcal R^{-1}$

Finally, as we assumed $\mathcal S \ne \mathcal R \cap \mathcal R^{-1}$:

$\mathcal S \subset \mathcal R \cap \mathcal R^{-1}$

Hence the result.

$\blacksquare$