|
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 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, and, as a result, $\operatorname{Cl}_{\mathcal{P}}(R)$ exists for any $R\subseteq A^n$ .
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=\lbrace a,b\rbrace$ , and $R=\lbrace (a,b)\rbrace$ . Then $R^{\leftrightarrow +}=A^2\ne \lbrace (a,b),(b,a)\rbrace = R^{+ \leftrightarrow}$ .
|
