# closure of a subset under relations

Let $A$ be a set and $R$ be an $n$-ary relation on $A$, $n\geq 1$. A subset $B$ of $A$ is said to be closed under $R$, or $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$.

More generally, let $A$ be a set and $\mathcal{R}$ a set of (finitary) relations on $A$. A subset $B$ is said to be $\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 $\mathcal{R}$-closure of $B$ if

1. 1.

$B\subseteq C$,

2. 2.

$C$ is $\mathcal{R}$-closed, and

3. 3.

if $D\subseteq A$ satisfies both 1 and 2, then $C\subseteq D$.

By condition 3, $C$, if exists, must be unique. Let us call it the $\mathcal{R}$-closure of $B$, and denote it by $\operatorname{Cl}_{\mathcal{R}}(B)$. If $\mathcal{R}=\{R\}$, then we call it the $R$-closure of $B$, and denote it by $\operatorname{Cl}_{R}(B)$ correspondingly.

Here are some examples.

1. 1.

Let $A=\mathbb{Z}$, $B=\{5\}$, 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 $\leq$, then $\operatorname{Cl}_{\leq}(B)=\{n\in A\mid n\geq 5\}$.

2. 2.

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=\{3,5\}$. 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=\{p,q\}$, where $p,q$ are coprime, then $\operatorname{Cl}_{-}(B)=\mathbb{Z}$. This is essentially the result of the Chinese Remainder Theorem.

3. 3.

If $R$ is unary, then the $R$-closure of $B\subseteq A$ is just $B\cup R$. When every $R\in\mathcal{R}$ is unary, then the $\mathcal{R}$-closure of $B$ in $A$ is $(\bigcup\mathcal{R})\cup B$.

###### Proposition 1.

$\operatorname{Cl}_{\mathcal{R}}(B)$ exists for every $B\subseteq A$.

###### Proof.

Let $S_{\mathcal{R}}(B)$ be the set of subsets of $A$ satisfying the defining conditions 1 and 2 of $\mathcal{R}$-closures above, partially ordered by $\subseteq$. If $\mathcal{C}\subseteq S_{\mathcal{R}}(B)$, then $\bigcap\mathcal{C}\in S_{\mathcal{R}}(B)$. To see this, we break the statement down into cases:

• In the case when $\mathcal{C}=\varnothing$, we have $\bigcap\mathcal{C}=A\in S_{\mathcal{R}}(B)$.

• When $C:=\bigcap\mathcal{C}\neq\varnothing$, pick any $n$-ary relation $R\in\mathcal{R}$.

1. (a)

If $n=1$, then, since aach $D\in\mathcal{C}$ is $R$-closed, $R\subseteq D$. Therefore, $R\subseteq\bigcap\mathcal{C}=\bigcap\{D\mid D\in\mathcal{C}\}=C$. So $C$ is $R$-closed.

2. (b)

If $n>1$, pick elements $c_{1},\ldots,c_{n-1}\in C$ such that $(c_{1},\ldots,c_{n})\in R$. As each $c_{i}\in D$ for $i=1,\ldots,n-1$, and $D$ is $R$-closed, $c_{n}\in D$. Since $c_{n}\in D$ for every $D\in\mathcal{C}$, $c_{n}\in C$ as well. This shows that $C$ is $R$-closed.

In both cases, $B\subseteq C$ since $B\subseteq D$ for every $D\in\mathcal{C}$. Therefore, $C\in S_{\mathcal{R}}(B)$.

Hence, $S_{\mathcal{R}}(B)$ is a complete lattice by virtue of this fact (http://planetmath.org/CriteriaForAPosetToBeACompleteLattice), which means that $S_{\mathcal{R}}(B)$ has a minimal element, which is none other than the $\mathcal{R}$-closure $\operatorname{Cl}_{\mathcal{R}}(B)$ of $B$. ∎

Remark. It is not hard to see $\operatorname{Cl}_{\mathcal{R}}$ has the following properties:

1. 1.

$B\subseteq\operatorname{Cl}_{\mathcal{R}}(B)$,

2. 2.

$\operatorname{Cl}_{\mathcal{R}}(\operatorname{Cl}_{\mathcal{R}}(B))=% \operatorname{Cl}_{\mathcal{R}}(B)$, and

3. 3.

if $B\subseteq C$, then $\operatorname{Cl}_{\mathcal{R}}(B)\subseteq\operatorname{Cl}_{\mathcal{R}}(C)$.

Next, assume that $\mathcal{S}$ is another set of finitary relations on $A$. Then

1. 1.

if $\mathcal{R}\subseteq\mathcal{S}$, then $\operatorname{Cl}_{\mathcal{S}}(B)\subseteq\operatorname{Cl}_{\mathcal{R}}(B)$,

2. 2.

$\operatorname{Cl}_{\mathcal{S}}(\operatorname{Cl}_{\mathcal{R}}(B))\subseteq% \operatorname{Cl}_{\mathcal{R}\cap\mathcal{S}}(B)$, and

3. 3.

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

Title closure of a subset under relations ClosureOfASubsetUnderRelations 2013-03-22 16:21:26 2013-03-22 16:21:26 CWoo (3771) CWoo (3771) 36 CWoo (3771) Definition msc 08A02 closed under closure property