|
|
|
Viewing Version
19
of
'closure of a subset under relations'
|
[ view 'closure of a subset under relations'
|
back to history
]
| Title of object: |
closure of a subset under relations |
| Canonical Name: |
ClosureOfASetViaRelations |
| Type: |
Definition |
| Created on: |
2006-10-29 20:18:40 |
| Modified on: |
2007-10-29 19:38:52 |
| Classification: |
msc:08A02 |
| Defines: |
closed under, has closures, closure property |
Preamble:
\usepackage{amssymb,amscd}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
\usepackage{xypic}
\usepackage{pst-plot}
\usepackage{psfrag}
% define commands here
\newtheorem{prop}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{ex}{Example}
\newcommand{\real}{\mathbb{R}}
\newcommand{\pdiff}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\mpdiff}[3]{\frac{\partial^#1 #2}{\partial #3^#1}} |
Content:
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,b_n)\in R$, then $b_n\in B$.
Note that if $R$ is unary, then $B$ is $R$-closed iff $B\subseteq 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
\begin{enumerate}
\item $B\subseteq C$,
\item $C$ is $\mathcal{R}$-closed, and
\item if $D\subseteq A$ satisfies both 1 and 2, then $C\subseteq D$.
\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$.
Here are some examples.
\begin{enumerate}
\item Let $A=\mathbb{Z}$, $B=\lbrace 5\rbrace$, and $R$ be the relation that $mRn$ whenever $m$ is divisible by $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
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
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 $Z=\lbrace c\rbrace$. Then $A=\lbrace a,c\rbrace$ and $B=\lbrace b,c\rbrace$ are both $R$-closed containing $Z$. If $C$ is the $R$-closure of $Z$, then $C\subseteq A$ and $C\subseteq B$, which means $C\subseteq A\cap B=Z$, which is not $R$-closed, a contradiction. Incidentally, $A$ and $B$ are minimal elements in the poset $S_R(Z)$.
\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.
\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.
\end{enumerate}
Given $A,B$ 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$ has closures if its arity is at least $2$. \end{prop}
\begin{proof}
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}
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{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}$.
$(\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} |
|
|
|
|
|
