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}$.

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 anti-symmetric 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 (http://planetmath.org/CriteriaForAPosetToBeACompleteLattice), 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}$$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$

• $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}$.

Title closure of a relation with respect to a property ClosureOfARelationWithRespectToAProperty 2013-03-22 17:36:26 2013-03-22 17:36:26 CWoo (3771) CWoo (3771) 15 CWoo (3771) Definition msc 08A02 Property2 reflexive closure symmetric closure transitive closure reflexive transitive closure