You are here
Homeclosure of a relation with respect to a property
Primary tabs
closure of a relation with respect to a property
Introduction
Fix a set $A$. A property $\mathcal{P}$ 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}$, $\mathcal{P}\subseteq P(A^{n})$, the powerset of $A^{n}$. An $n$ary relation is said to have property $\mathcal{P}$ if $R\in\mathcal{P}$.
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 $\mathcal{P}$, or the $\mathcal{P}$closure of $R$ for short, we mean the smallest relation $S\in\mathcal{P}$ such that $R\subseteq S$. In other words, if $T\in\mathcal{P}$ and $R\subseteq T$, then $S\subseteq T$. We write $\operatorname{Cl}_{{\mathcal{P}}}(R)$ for the $\mathcal{P}$closure of $R$.
Given an $n$ary relation $R$ on $A$, and a property $\mathcal{P}$ on $n$ary relations on $A$, does $\operatorname{Cl}_{{\mathcal{P}}}(R)$ always exist? The answer is no. For example, let $\mathcal{P}$ be the antisymmetric property of binary relations on $A$, and $R=A^{2}$. For another example, take $\mathcal{P}$ to be the irreflexive property, and $R=\Delta$, the diagonal relation on $A$.
However, if $A^{n}\in\mathcal{P}$ and $\mathcal{P}$ is closed under arbitrary intersections, then $\mathcal{P}$ is a complete lattice according to this fact, and, as a result, $\operatorname{Cl}_{{\mathcal{P}}}(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 $\mathcal{X}$ the reflexive property, $\mathcal{S}$ the symmetric property, and $\mathcal{T}$ be the transitive property on the binary relations on $A$.
Proposition 1.
Arbitrary intersections are closed in $\mathcal{X}$, $\mathcal{S}$, and $\mathcal{T}$. Furthermore, if $R$ is any binary relation on $A$, then

$R^{=}:=\operatorname{Cl}_{{\mathcal{X}}}(R)=R\cup\Delta$, where $\Delta$ is the diagonal relation on $A$,

$R^{{\leftrightarrow}}:=\operatorname{Cl}_{{\mathcal{S}}}(R)=R\cup R^{{1}}$, where $R^{{1}}$ is the converse of $R$, and

$R^{+}:=\operatorname{Cl}_{{\mathcal{T}}}(R)$ is given by
$\bigcup_{{n\in\mathbb{N}}}R^{n}=R\cup(R\circ R)\cup\cdots\cup\underbrace{(R% \circ\cdots\circ R)}_{{\displaystyle{n}\mbox{fold power}}}\cup\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 $\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}\neq\{(a,b),(b,a)\}=R^{{+\leftrightarrow}}$.
Mathematics Subject Classification
08A02 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections