Reflexive Closure is Closure Operator

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $R$ be the set of all endorelations on $S$.


Then the reflexive closure operator on $R$ is a closure operator.


Proof 1

Let $\mathcal Q$ be the set of reflexive relations on $S$.

By Intersection of Reflexive Relations is Reflexive, the intersection of any subset of $\mathcal Q$ is in $Q$.

By the definition of reflexive closure as the intersection of reflexive supersets:

The reflexive closure of a relation $\mathcal R$ on $S$ is the intersection of elements of $\mathcal Q$ that contain $S$.

From Closure Operator from Closed Sets we conclude that reflexive closure is a closure operator.

$\blacksquare$


Proof 2

Reflexive Closure is Inflationary

Let $\mathcal R \in R$.

The reflexive closure $\mathcal R^=$ of $\mathcal R$ is defined as:

$\mathcal R^= := \mathcal R \cup \Delta_S$

From Set is Subset of Union:

$\mathcal R \subseteq \mathcal R^=$

Hence the reflexive closure operator is an inflationary mapping.

$\Box$


Reflexive Closure is Order Preserving

Let $\mathcal R, \mathcal S \in R$.

Suppose:

$\mathcal R \subseteq \mathcal S$

Their respective reflexive closures $\mathcal R^=$ and $\mathcal S^=$ are defined as:

$\mathcal R^= := \mathcal R \cup \Delta_S$
$\mathcal S^= := \mathcal S \cup \Delta_S$

Hence by Corollary to Set Union Preserves Subsets:

$\mathcal R^= \subseteq S^=$

$\Box$


Reflexive Closure is Idempotent

Let $\mathcal R \in R$.

By the definition of reflexive closure:

$\mathcal R^= = \mathcal R \cup \Delta_S$
$\left ({\mathcal R^=}\right )^= = \left( {\mathcal R \cup \Delta_S} \right ) \cup \Delta_S$

By Union is Associative:

$\left ({\mathcal R^=}\right )^= = \mathcal R \cup \left ( {\Delta_S \cup \Delta_S } \right )$

By Union is Idempotent:

$\left ({\mathcal R^=}\right )^= = \mathcal R \cup \Delta_S$

Hence:

$\forall \mathcal R \in R: \mathcal R^= = \left ({\mathcal R^=}\right )^=$

$\Box$


Thus by the definition of closure operator, reflexive closure is a closure operator.

$\blacksquare$