| Version 10 |
Version 9 |
| \PMlinkescapeword{proposition} |
\PMlinkescapeword{proposition} |
| \PMlinkescapeword{words} |
\PMlinkescapeword{words} |
| \PMlinkescapeword{closure} |
\PMlinkescapeword{closure} |
| \PMlinkescapeword{parent} |
\PMlinkescapeword{parent} |
|
|
| \subsubsection*{Introduction} |
\subsubsection*{Introduction} |
|
|
| Fix a set $A$. A \emph{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}$. |
Fix a set $A$. A \emph{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. |
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 \emph{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$. |
Let $R$ be an $n$-ary relation on $A$. By the \emph{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$. |
%If we treat $\mathcal{P}$ as a set of unary relation on $A^n$, and $R\subseteq A^n$, then the $\mathcal{P}$-closure of $R$ can be interpreted in the sense of the \PMlinkname{parent entry}{ClosureOfASetViaRelations}. |
|
|
|
%According to Proposition 2 of the \PMlinkname{parent entry}{ClosureOfASetViaRelations} (Proposition 2), for an arbitray $n$-ary relation $R$ on $A$, the closure of $R$ exists iff $\mathcal{P}$ is closed under arbitrary intersections, including empty intersections, which implies that $A^n$ itself has property $\mathcal{P}$. |
|
|
|
Therefore, given a property $\mathcal{P}$ on $n$-ary relations on a set $A$, to check whether an $n$-ary relation $R$ has $\mathcal{P}$-closure, the first thing to check is to see if $A^n$ itself has property $\mathcal{P}$. For example, let $\mathcal{P}$ be the anti-symmetric property of binary relations on $A$. Clearly, $A\times A$ is not anti-symmetric (does not have $\mathcal{P}$), so that $\mathcal{P}$ does not have closures. Similarly, the irreflexive property does not have closures, as $A\times A$ is not irreflexive. |
|
|
| \subsubsection*{Reflexive, Symmetric, and Transitive Closures} |
\subsubsection*{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$. |
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$. |
|
|
| \begin{prop} Arbitrary intersections are closed in $\mathcal{X}$, $\mathcal{S}$, and $\mathcal{T}$. Furthermore, if $R$ is any binary relation on $A$, then |
\begin{prop} Arbitrary intersections are closed in $\mathcal{X}$, $\mathcal{S}$, and $\mathcal{T}$. Furthermore, if $R$ is any binary relation on $A$, then |
| \begin{itemize} |
\begin{itemize} |
| \item $R^=:=\operatorname{Cl}_{\mathcal{X}}(R)=R\cup \Delta$, where $\Delta$ is the diagonal relation on $A$, |
\item $R^=:=\operatorname{Cl}_{\mathcal{X}}(R)=R\cup \Delta$, where $\Delta$ is the diagonal relation on $A$, |
| \item $R^{\leftrightarrow}:=\operatorname{Cl}_{\mathcal{S}}(R)=R\cup R^{-1}$, where $R^{-1}$ is the converse of $R$, and |
\item $R^{\leftrightarrow}:=\operatorname{Cl}_{\mathcal{S}}(R)=R\cup R^{-1}$, where $R^{-1}$ is the converse of $R$, and |
| \item $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 ,$$ |
\item $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. |
where $\circ$ is the relational composition operator. |
| \item $R^*:=R^{=+}=R^{+=}$. |
\item $R^*:=R^{=+}=R^{+=}$. |
| \end{itemize} |
\end{itemize} |
| \end{prop} |
\end{prop} |
| $R^=$, $R^{\leftrightarrow}$, $R^+$, and $R^*$ are called the \emph{reflexive closure}, the \emph{symmetric closure}, the \emph{transitive closure}, and the \emph{reflexive transitive closure} of $R$ respectively. The last item in the proposition permits us to call $R^*$ the \emph{transitive reflexive closure} of $R$ as well (there is no difference to the order of taking closures). This is true because $\Delta$ is transitive. |
$R^=$, $R^{\leftrightarrow}$, $R^+$, and $R^*$ are called the \emph{reflexive closure}, the \emph{symmetric closure}, the \emph{transitive closure}, and the \emph{reflexive transitive closure} of $R$ respectively. The last item in the proposition permits us to call $R^*$ the \emph{transitive reflexive closure} of $R$ as well (there is no difference to the order of taking closures). This is true because $\Delta$ is transitive. |
|
|
| \textbf{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}$. |
\textbf{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}$. |
