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.

$B\subseteq C$ ,
2.

$C$ is $\mathcal{R}$ -closed, and
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.

Let $A=\mathbb{Z}$ , $B=\{5\}$ , and $R$ be the relation that $m R n$ 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.

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.

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.

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

$\operatorname{Cl}_{\mathcal{R}}(\operatorname{Cl}_{\mathcal{R}}(B))=% \operatorname{Cl}_{\mathcal{R}}(B)$ , and
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.

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

$\operatorname{Cl}_{\mathcal{S}}(\operatorname{Cl}_{\mathcal{R}}(B))\subseteq% \operatorname{Cl}_{\mathcal{R}\cap\mathcal{S}}(B)$ , and
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
Canonical name	ClosureOfASubsetUnderRelations
Date of creation	2013-03-22 16:21:26
Last modified on	2013-03-22 16:21:26
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	36
Author	CWoo (3771)
Entry type	Definition
Classification	msc 08A02
Defines	closed under
Defines	closure property