closure of a relation with respect to a property

Introduction

Fix a set $A$. A property $𝒫$ of $n$-ary relations on a set $A$ may be thought of as some subset of the set of all $n$-ary relations on $A$. Since an $n$-ary relation is just a subset of $A^n$, $𝒫\subseteq P(A^n)$, the powerset of $A^n$. An $n$-ary relation is said to have property $𝒫$ if $R\in 𝒫$.

For example, the transitive property is a property of binary relations on $A$; it consists of all transitive binary relations on $A$. Reflexive and symmetric properties are sets of reflexive and symmetric binary relations on $A$ correspondingly.

Let $R$ be an $n$-ary relation on $A$. By the closure of an $n$-ary relation $R$ with respect to property $𝒫$, or the $𝒫$-closure of $R$ for short, we mean the smallest relation $S\in 𝒫$ such that $R\subseteq S$. In other words, if $T\in 𝒫$ and $R\subseteq T$, then $S\subseteq T$. We write ${\mathrm{Cl}}_{𝒫}(R)$ for the $𝒫$-closure of $R$.

Given an $n$-ary relation $R$ on $A$, and a property $𝒫$ on $n$-ary relations on $A$, does ${\mathrm{Cl}}_{𝒫}(R)$ always exist? The answer is no. For example, let $𝒫$ be the anti-symmetric property of binary relations on $A$, and $R=A^2$. For another example, take $𝒫$ to be the irreflexive property, and $R=\mathrm{\Delta }$, the diagonal relation on $A$.

However, if $A^n\in 𝒫$ and $𝒫$ is closed under arbitrary intersections, then $𝒫$ is a complete lattice according to this fact (http://planetmath.org/CriteriaForAPosetToBeACompleteLattice), and, as a result, ${\mathrm{Cl}}_{𝒫}(R)$ exists for any $R\subseteq A^n$.

Reflexive, Symmetric, and Transitive Closures

From now on, we concentrate on binary relations on a set $A$. In particular, we fix a binary relation $R$ on $A$, and let $𝒳$ the reflexive property, $𝒮$ the symmetric property, and $𝒯$ be the transitive property on the binary relations on $A$.

Proposition 1.

Arbitrary intersections are closed in $\mathrm{X}$, $\mathrm{S}$, and $\mathrm{T}$. Furthermore, if $R$ is any binary relation on $A$, then

• $R^{=}:={\mathrm{Cl}}_{𝒳}(R)=R\cup \mathrm{\Delta }$, where $\mathrm{\Delta }$ is the diagonal relation on $A$,

• $R^{\leftrightarrow }:={\mathrm{Cl}}_{𝒮}(R)=R\cup R^{-1}$, where $R^{-1}$ is the converse of $R$, and

• $R^{+}:={\mathrm{Cl}}_{𝒯}(R)$ is given by

  $$\bigcup _{n\in \mathbb{N}}{R}^n=R\cup (R\circ R)\cup \mathrm{\cdots }\cup \underset{n\mathit{\text{-fold power}}}{\underbrace{(R\circ \mathrm{\cdots }\circ R)}}\cup \mathrm{\cdots },$$

  where $\circ$ is the relational composition operator.

• $R^{*}:=R^{=+}=R^{+=}$.

$R^{=}$, $R^{\leftrightarrow }$, $R^{+}$, and $R^{*}$ are called the reflexive closure, the symmetric closure, the transitive closure, and the reflexive transitive closure of $R$ respectively. The last item in the proposition permits us to call $R^{*}$ the transitive reflexive closure of $R$ as well (there is no difference to the order of taking closures). This is true because $\mathrm{\Delta }$ is transitive.

Remark. In general, however, the order of taking closures of a relation is important. For example, let $A=\{a,b\}$, and $R=\{(a,b)\}$. Then $R^{\leftrightarrow +}=A^2\ne \{(a,b),(b,a)\}=R^{+\leftrightarrow }$.