| Version 28 |
Version 27 |
| Let $A$ be a set and $R$ be an $n$-ary relation on $A$, $n\ge 1$. A subset $B$ of $A$ is said to be \emph{closed under $R$}, or \emph{$R$-closed}, if, whenever $b_1,\ldots,b_{n-1}\in B$, and $(b_1,\ldots,b_{n-1},b_n)\in R$, then $b_n\in B$. |
Let $A$ be a set and $R$ be an $n$-ary relation on $A$, $n\ge 1$. A subset $B$ of $A$ is said to be \emph{closed under $R$}, or \emph{$R$-closed}, if, whenever $b_1,\ldots,b_{n-1}\in B$, and $(b_1,\ldots,b_{n-1},b_n)\in R$, then $b_n\in B$. |
|
|
| Note that if $R$ is unary, then $B$ is $R$-closed iff $R\subseteq B$. |
Note that if $R$ is unary, then $B$ is $R$-closed iff $R\subseteq B$. |
|
|
| More generally, let $A$ be a set and $\mathcal{R}$ a set of (finitary) relations on $A$. A subset $B$ is said to be \emph{$\mathcal{R}$-closed} if $B$ is $R$-closed for each $R\in\mathcal{R}$. |
More generally, let $A$ be a set and $\mathcal{R}$ a set of (finitary) relations on $A$. A subset $B$ is said to be \emph{$\mathcal{R}$-closed} if $B$ is $R$-closed for each $R\in\mathcal{R}$. |
|
|
| Given $B\subseteq A$ with a set of relations $\mathcal{R}$ on $A$, we say that $C\subseteq A$ is an \emph{$\mathcal{R}$-closure} of $B$ if |
Given $B\subseteq A$ with a set of relations $\mathcal{R}$ on $A$, we say that $C\subseteq A$ is an \emph{$\mathcal{R}$-closure} of $B$ if |
| \begin{enumerate} |
\begin{enumerate} |
| \item $B\subseteq C$, |
\item $B\subseteq C$, |
| \item $C$ is $\mathcal{R}$-closed, and |
\item $C$ is $\mathcal{R}$-closed, and |
| \item if $D\subseteq A$ satisfies both 1 and 2, then $C\subseteq D$. |
\item if $D\subseteq A$ satisfies both 1 and 2, then $C\subseteq D$. |
| \end{enumerate} |
\end{enumerate} |
|
|
| Note that $C$ is necessarily unique, if it exists. Alternatively, let $S_{\mathcal{R}}(B)$ be the set of subsets of $A$ satisfying conditions 1 and 2, partially ordered by $\subseteq$. Then $C$ is the least element in $S_{\mathcal{R}}(B)$. Let us denote this set by $\operatorname{Cl}_{\mathcal{R}}(B)$, and call it the $\mathcal{R}$-closure of $B$. If $\mathcal{R}=\lbrace R\rbrace$, then we omit the parentheses and simply write $\operatorname{Cl}_{R}(B)$ for the $R$-closure of $B$. If $R$ is unary, then the $R$-closure of a subset $B$ of $A$ is $B\cup R$. |
Note that $C$ is necessarily unique, if it exists. Alternatively, let $S_{\mathcal{R}}(B)$ be the set of subsets of $A$ satisfying conditions 1 and 2, partially ordered by $\subseteq$. Then $C$ is the least element in $S_{\mathcal{R}}(B)$. Let us denote this set by $\operatorname{Cl}_{\mathcal{R}}(B)$, and call it the $\mathcal{R}$-closure of $B$. If $\mathcal{R}=\lbrace R\rbrace$, then we omit the parentheses and simply write $\operatorname{Cl}_{R}(B)$ for the $R$-closure of $B$. If $R$ is unary, then the $R$-closure of a subset $B$ of $A$ is $B\cup R$. |
|
|
| Here are some examples. |
Here are some examples. |
| \begin{enumerate} |
\begin{enumerate} |
| \item Let $A=\mathbb{Z}$, $B=\lbrace 5\rbrace$, and $R$ be the relation that $mRn$ whenever $m$ divides $n$. Clearly $B$ is not closed under $R$ (for example, $(5,10)\in R$ but $10\notin B$). Then $\operatorname{Cl}_{R}(B) = 5\mathbb{Z}$. If $R$ is instead the relation $\le$, then $\operatorname{Cl}_{\le}(B)=\lbrace n\in A\mid n\ge 5\rbrace$. |
\item Let $A=\mathbb{Z}$, $B=\lbrace 5\rbrace$, and $R$ be the relation that $mRn$ whenever $m$ divides $n$. Clearly $B$ is not closed under $R$ (for example, $(5,10)\in R$ but $10\notin B$). Then $\operatorname{Cl}_{R}(B) = 5\mathbb{Z}$. If $R$ is instead the relation $\le$, then $\operatorname{Cl}_{\le}(B)=\lbrace n\in A\mid n\ge 5\rbrace$. |
| \item |
\item |
| This is an example where $R$ is in fact a function (operation). Suppose $A=\mathbb{Z}$ and $R$ is the binary operation subtraction $-$. Suppose $B=\lbrace 3,5\rbrace$. Then $\operatorname{Cl}_{-}(B)=A$. To see this, set $C=\operatorname{Cl}_{-}(B)$. Note that $2=5-3\in C$ so $1=3-2$ as well as $-1=2-3\in C$. This means that if $n\in C$, both $n-1$ and $n+1\in C$. By induction, $C=\mathbb{Z}$. In general, if $B=\lbrace p,q\rbrace$, where $p,q$ are coprime, then $\operatorname{Cl}_{-} (B) =\mathbb{Z}$. This is essentially the result of the Chinese Remainder Theorem. |
This is an example where $R$ is in fact a function (operation). Suppose $A=\mathbb{Z}$ and $R$ is the binary operation subtraction $-$. Suppose $B=\lbrace 3,5\rbrace$. Then $\operatorname{Cl}_{-}(B)=A$. To see this, set $C=\operatorname{Cl}_{-}(B)$. Note that $2=5-3\in C$ so $1=3-2$ as well as $-1=2-3\in C$. This means that if $n\in C$, both $n-1$ and $n+1\in C$. By induction, $C=\mathbb{Z}$. In general, if $B=\lbrace p,q\rbrace$, where $p,q$ are coprime, then $\operatorname{Cl}_{-} (B) =\mathbb{Z}$. This is essentially the result of the Chinese Remainder Theorem. |
| \item |
%\item
|
|
In both 1 and 2 above, $\operatorname{Cl}_{R}(B)$ exists. Here is a counterexample. Let $X$ be a set containing at least three elements $a,b,c$. Let $\mathcal{R}=\lbrace R \subseteq X\mid \mbox{ either } a\in R \mbox{ or } b\in R\rbrace$. Let $B=\lbrace c \rbrace$. Suppose $C$ is the $\mathcal{R}$-closure of $B$, then either $c\in C$, and either $a\in C$ or $b\in C$. Let $D=\lbrace a,c\rbrace$ and $E=\lbrace b,c\rbrace$. Then, $D,E\in \mathcal{R}$, and $B\subseteq D$ and $B \subseteq E$. Since $C$ is minimal, $C\subseteq D$ and $C\subseteq E$, which forces $C=B\notin \mathcal{C}$, a contradiction!
|
%In both 1 and 2 above, $\operatorname{Cl}_{R}(B)$ exists. Here is a counterexample. Let $X$ be a set containing at least three elements $a,b,c$. Let $R$ be a unary relation on $2^X$ defined by $Y\in R$ iff either $a$ or $b$ is in $Y$. Let $B=\lbrace \lbrace c\rbrace \rbrace$. Suppose $C$ is an $R$-closure of $B$, then $\lbrace c\rbrace$ is an element of $C$. But $C$, being $R$-closed, is a subset of $R$. In other words, every element of $C$ contains either $a$ or $b$. However, $\lbrace c\rbrace$ contains neither $a$ nor $b$, a contradiction!
|
| \item |
\item |
| Here, we meet examples where $S_R(B)=\varnothing$. If we replace the $R$ in 3 by $Y\in R$ iff $c\notin Y$, then clearly $S_R(Z)=\varnothing$. Likewise, if $B=\lbrace (a,b)\rbrace \subseteq A\times A$, where $a\ne b$, and $\mathcal{P}$ is the family of all irreflexive relations on $A$ (so $\mathcal{P}$ is a collection of unary relations on $A\times A$), then no superset of $B$ is $\mathcal{P}$-closed. |
Here, we meet examples where $S_R(B)=\varnothing$. If we replace the $R$ in 3 by $Y\in R$ iff $c\notin Y$, then clearly $S_R(Z)=\varnothing$. Likewise, if $B=\lbrace (a,b)\rbrace \subseteq A\times A$, where $a\ne b$, and $\mathcal{P}$ is the family of all irreflexive relations on $A$ (so $\mathcal{P}$ is a collection of unary relations on $A\times A$), then no superset of $B$ is $\mathcal{P}$-closed. |
| \item |
\item |
| Here is an example where $S_R(B)$ is infinite, and has no minimal elements (hence $\operatorname{Cl}_{\mathcal{R}}(B)$ again does not exist). Let $A=\mathbb{Z}$ and $B=\lbrace 0\rbrace$. Let $\mathcal{P}$ be the property of a subset of $A$ such that $P\in \mathcal{P}$ iff $P$ is infinite and every element of $P$ is at least $0$. Like the set of irreflexive relations previously, $\mathcal{P}$ is a collection of unary relations on $A$. Now, the collection $\mathcal{Q}$ consisting of $P_n\subseteq A$ where $P_n:=\lbrace m\mid n<m\rbrace$ for each $n\ge 0$ is a subset of $\mathcal{P}$. Since $\mathcal{Q}$ is infinite, so is $\mathcal{P}$. Furthermore, if $P\in \mathcal{P}$ and $m\in P$, then $P-\lbrace m\rbrace$ is again in $\mathcal{P}$, showing that $S_R(B)$ has no minimal element. |
Here is an example where $S_R(B)$ is infinite, and has no minimal elements (hence $\operatorname{Cl}_{\mathcal{R}}(B)$ again does not exist). Let $A=\mathbb{Z}$ and $B=\lbrace 0\rbrace$. Let $\mathcal{P}$ be the property of a subset of $A$ such that $P\in \mathcal{P}$ iff $P$ is infinite and every element of $P$ is at least $0$. Like the set of irreflexive relations previously, $\mathcal{P}$ is a collection of unary relations on $A$. Now, the collection $\mathcal{Q}$ consisting of $P_n\subseteq A$ where $P_n:=\lbrace m\mid n<m\rbrace$ for each $n\ge 0$ is a subset of $\mathcal{P}$. Since $\mathcal{Q}$ is infinite, so is $\mathcal{P}$. Furthermore, if $P\in \mathcal{P}$ and $m\in P$, then $P-\lbrace m\rbrace$ is again in $\mathcal{P}$, showing that $S_R(B)$ has no minimal element. |
| \end{enumerate} |
\end{enumerate} |
|
|
| Given $B\subseteq A$ and $\mathcal{R}$, when do we know if the $\mathcal{R}$-closure of $B$ in $A$ exists? Call a class $\mathcal{R}$ of relations on $A$ \emph{has closures} if for each $B\subseteq A$, there is an $R\in \mathcal{R}$ such that $\operatorname{Cl}_{R}(B)$ exists. Then we have |
Given $B\subseteq A$ and $\mathcal{R}$, when do we know if the $\mathcal{R}$-closure of $B$ in $A$ exists? Call a class $\mathcal{R}$ of relations on $A$ \emph{has closures} if for each $B\subseteq A$, there is an $R\in \mathcal{R}$ such that $\operatorname{Cl}_{R}(B)$ exists. Then we have |
|
|
|
\begin{prop} A relation $R$ on $A$ always has closures. \end{prop}
|
\begin{prop} A relation $R$ on $A$ has closures if its arity is at least $2$. \end{prop}
|
| \begin{proof} |
\begin{proof} |
| If $R$ is unary, and $B$ is any subset of $A$, then its $R$-closure is just $R\cup B$. |
Let $B\subseteq A$, and $\mathfrak{A}:=\lbrace X\subseteq A\mid B\subseteq X\mbox{ and }X\mbox{ is }R\mbox{-closed}\rbrace$. $\mathfrak{A}\ne\varnothing$ since $A\in \mathfrak{A}$. Let $C=\bigcap \mathfrak{A}$. Clearly $B\subseteq C$. To prove that $C$ is $R$-closed, let $c_1,\ldots,c_{n-1}\in C$ and $(c_1,\ldots,c_n,c_n)\in R$. Since each of $c_1,\ldots,c_{n-1}\in X$ for each $X\in \mathfrak{A}$, and $X$ is $R$-closed, $c_n\in X$ and therefore $c_n\in C$ as well. So $C$ is $R$-closed and $C\in\mathfrak{A}$. |
|
|
| Now, suppose $R$ has arity at least $2$. Let $B\subseteq A$, and $\mathfrak{A}:=\lbrace X\subseteq A\mid B\subseteq X\mbox{ and }X\mbox{ is }R\mbox{-closed}\rbrace$. $\mathfrak{A}\ne\varnothing$ since $A\in \mathfrak{A}$. Let $C=\bigcap \mathfrak{A}$. Clearly $B\subseteq C$. To prove that $C$ is $R$-closed, let $c_1,\ldots,c_{n-1}\in C$ and $(c_1,\ldots,c_n,c_n)\in R$. Since each of $c_1,\ldots,c_{n-1}\in X$ for each $X\in \mathfrak{A}$, and $X$ is $R$-closed, $c_n\in X$ and therefore $c_n\in C$ as well. So $C$ is $R$-closed and $C\in\mathfrak{A}$. |
|
| \end{proof} |
\end{proof} |
|
|
| When every $R\in \mathcal{R}$ is unary, we have the following: |
When every $R\in \mathcal{R}$ is unary, we have the following: |
|
|
| \begin{prop} $\mathcal{R}$ has closures iff $\mathcal{R}$ is closed under arbitrary intersections (including null intersections). \end{prop} |
\begin{prop} $\mathcal{R}$ has closures iff $\mathcal{R}$ is closed under arbitrary intersections (including null intersections). \end{prop} |
|
|
| \begin{proof} |
\begin{proof} |
| $(\Rightarrow)$ Suppose $\mathcal{R}$ has closures in $A$. Let $\mathcal{Q}$ be an arbitrary subset of $\mathcal{R}$ and let $B=\bigcap \lbrace P \mid P\in \mathcal{Q} \rbrace \subseteq A$. By assumption, $C= \operatorname{Cl}_{\mathcal{R}}(B)$ exists, so $C\in \mathcal{R}$. But then $C\subseteq P$ for all $P\in \mathcal{Q}$, which implies that $C\subseteq \bigcap \mathcal{Q}=B$. As a result, $\bigcap \mathcal{Q}\in \mathcal{R}$. |
$(\Rightarrow)$ Suppose $\mathcal{R}$ has closures in $A$. Let $\mathcal{Q}$ be an arbitrary subset of $\mathcal{R}$ and let $B=\bigcap \lbrace P \mid P\in \mathcal{Q} \rbrace \subseteq A$. By assumption, $C= \operatorname{Cl}_{\mathcal{R}}(B)$ exists, so $C\in \mathcal{R}$. But then $C\subseteq P$ for all $P\in \mathcal{Q}$, which implies that $C\subseteq \bigcap \mathcal{Q}=B$. As a result, $\bigcap \mathcal{Q}\in \mathcal{R}$. |
|
|
| $(\Leftarrow)$ Now suppose that $\mathcal{R}$ is closed under arbitrary intersections. In particular, $A=\bigcap \varnothing \in \mathcal{R}$. Let $B$ be any subset of $A$ and $\mathcal{Q}:=\lbrace R\in \mathcal{R}\mid B\mbox{ is }R\mbox{-closed}\rbrace$. So $B\subseteq R$ iff $R\in \mathcal{Q}$, and $\mathcal{Q}\ne \varnothing$ since $A\in \mathcal{Q}$. Let $C=\bigcap \mathcal{Q}$. Since $\mathcal{R}$ is closed under arbitrary $\bigcap$, $C\in \mathcal{R}$. So $B$ is $C$-closed, and $C$ is the smallest among $R\in \mathcal{R}$ such that $B$ is $R$-closed. Therefore, $C$ is the $C$-closure of $B$. |
$(\Leftarrow)$ Now suppose that $\mathcal{R}$ is closed under arbitrary intersections. In particular, $A=\bigcap \varnothing \in \mathcal{R}$. Let $B$ be any subset of $A$ and $\mathcal{Q}:=\lbrace R\in \mathcal{R}\mid B\mbox{ is }R\mbox{-closed}\rbrace$. So $B\subseteq R$ iff $R\in \mathcal{Q}$, and $\mathcal{Q}\ne \varnothing$ since $A\in \mathcal{Q}$. Let $C=\bigcap \mathcal{Q}$. Since $\mathcal{R}$ is closed under arbitrary $\bigcap$, $C\in \mathcal{R}$. So $B$ is $C$-closed, and $C$ is the smallest among $R\in \mathcal{R}$ such that $B$ is $R$-closed. Therefore, $C$ is the $C$-closure of $B$. |
| \end{proof} |
\end{proof} |
|
|
| \textbf{Remark}. In fact, $\mathcal{R}$ has closures iff it is a complete lattice by virtue of \PMlinkname{this property}{CriteriaForAPosetToBeACompleteLattice}. Also, it is not hard to see $\operatorname{Cl}_{\mathcal{R}}$ has the following properties: |
\textbf{Remark}. In fact, $\mathcal{R}$ has closures iff it is a complete lattice by virtue of \PMlinkname{this property}{CriteriaForAPosetToBeACompleteLattice}. Also, it is not hard to see $\operatorname{Cl}_{\mathcal{R}}$ has the following properties: |
| \begin{enumerate} |
\begin{enumerate} |
| \item $B\subseteq \operatorname{Cl}_{\mathcal{R}}(B)$, |
\item $B\subseteq \operatorname{Cl}_{\mathcal{R}}(B)$, |
| \item $\operatorname{Cl}_{\mathcal{R}}(\operatorname{Cl}_{\mathcal{R}}(B))= \operatorname{Cl}_{\mathcal{R}}(B)$, and |
\item $\operatorname{Cl}_{\mathcal{R}}(\operatorname{Cl}_{\mathcal{R}}(B))= \operatorname{Cl}_{\mathcal{R}}(B)$, and |
| \item if $B\subseteq C$, then $\operatorname{Cl}_{\mathcal{R}}(B)\subseteq \operatorname{Cl}_{\mathcal{R}}(C)$. |
\item if $B\subseteq C$, then $\operatorname{Cl}_{\mathcal{R}}(B)\subseteq \operatorname{Cl}_{\mathcal{R}}(C)$. |
| \end{enumerate} |
\end{enumerate} |
|
|
| Next, assume that $\mathcal{S}$ has closures. Then |
Next, assume that $\mathcal{S}$ has closures. Then |
| \begin{enumerate} |
\begin{enumerate} |
| \item $\mathcal{R}\cap \mathcal{S}$ has closures, |
\item $\mathcal{R}\cap \mathcal{S}$ has closures, |
| \item if $\mathcal{R}\subseteq \mathcal{S}$, then $\operatorname{Cl}_{\mathcal{S}}(B) \subseteq \operatorname{Cl}_{\mathcal{R}}(B)$, |
\item if $\mathcal{R}\subseteq \mathcal{S}$, then $\operatorname{Cl}_{\mathcal{S}}(B) \subseteq \operatorname{Cl}_{\mathcal{R}}(B)$, |
| \item $\operatorname{Cl}_{\mathcal{S}}(\operatorname{Cl}_{\mathcal{R}}(B)) \subseteq \operatorname{Cl}_{\mathcal{R}\cap\mathcal{S}}(B)$, and |
\item $\operatorname{Cl}_{\mathcal{S}}(\operatorname{Cl}_{\mathcal{R}}(B)) \subseteq \operatorname{Cl}_{\mathcal{R}\cap\mathcal{S}}(B)$, and |
| \item $\operatorname{Cl}_{\mathcal{S}}(\operatorname{Cl}_{\mathcal{R}}(B))= \operatorname{Cl}_{\mathcal{R}\cap\mathcal{S}}(B)$ if $\mathcal{R}\subseteq \mathcal{S}$ or $\mathcal{S}\subseteq \mathcal{R}$. |
\item $\operatorname{Cl}_{\mathcal{S}}(\operatorname{Cl}_{\mathcal{R}}(B))= \operatorname{Cl}_{\mathcal{R}\cap\mathcal{S}}(B)$ if $\mathcal{R}\subseteq \mathcal{S}$ or $\mathcal{S}\subseteq \mathcal{R}$. |
| \end{enumerate} |
\end{enumerate} |
| For an example where $\operatorname{Cl}_{\mathcal{S}}(\operatorname{Cl}_{\mathcal{R}}(B)) \ne \operatorname{Cl}_{\mathcal{R}\cap\mathcal{S}}(B)$, see the remark at the end of \PMlinkname{this entry}{ClosureOfARelationWithRespectToAProperty}. |
For an example where $\operatorname{Cl}_{\mathcal{S}}(\operatorname{Cl}_{\mathcal{R}}(B)) \ne \operatorname{Cl}_{\mathcal{R}\cap\mathcal{S}}(B)$, see the remark at the end of \PMlinkname{this entry}{ClosureOfARelationWithRespectToAProperty}. |
