closure of a subset under relations
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 closed under^{} $R$, or $R$closed, if, whenever ${b}_{1},\mathrm{\dots},{b}_{n1}\in B$, and $({b}_{1},\mathrm{\dots},{b}_{n1},{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 $\mathrm{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 $\mathrm{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 ${\mathrm{Cl}}_{\mathcal{R}}(B)$. If $\mathcal{R}=\{R\}$, then we call it the $R$closure of $B$, and denote it by ${\mathrm{Cl}}_{R}(B)$ correspondingly.
Here are some examples.

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 ${\mathrm{Cl}}_{R}(B)=5\mathbb{Z}$. If $R$ is instead the relation $\le $, then ${\mathrm{Cl}}_{\le}(B)=\{n\in A\mid n\ge 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 ${\mathrm{Cl}}_{}(B)=A$. To see this, set $C={\mathrm{Cl}}_{}(B)$. Note that $2=53\in C$ so $1=32$ as well as $1=23\in C$. This means that if $n\in C$, both $n1$ and $n+1\in C$. By induction^{}, $C=\mathbb{Z}$. In general, if $B=\{p,q\}$, where $p,q$ are coprime^{}, then ${\mathrm{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.
${\mathrm{Cl}}_{\mathcal{R}}(B)$ exists for every $B\mathrm{\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}=\mathrm{\varnothing}$, we have $\bigcap \mathcal{C}=A\in {S}_{\mathcal{R}}(B)$.

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

(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.

(b)
If $n>1$, pick elements ${c}_{1},\mathrm{\dots},{c}_{n1}\in C$ such that $({c}_{1},\mathrm{\dots},{c}_{n})\in R$. As each ${c}_{i}\in D$ for $i=1,\mathrm{\dots},n1$, 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)$.

(a)
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 ${\mathrm{Cl}}_{\mathcal{R}}(B)$ of $B$. ∎
Remark. It is not hard to see ${\mathrm{Cl}}_{\mathcal{R}}$ has the following properties:

1.
$B\subseteq {\mathrm{Cl}}_{\mathcal{R}}(B)$,

2.
${\mathrm{Cl}}_{\mathcal{R}}({\mathrm{Cl}}_{\mathcal{R}}(B))={\mathrm{Cl}}_{\mathcal{R}}(B)$, and

3.
if $B\subseteq C$, then ${\mathrm{Cl}}_{\mathcal{R}}(B)\subseteq {\mathrm{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 ${\mathrm{Cl}}_{\mathcal{S}}(B)\subseteq {\mathrm{Cl}}_{\mathcal{R}}(B)$,

2.
${\mathrm{Cl}}_{\mathcal{S}}({\mathrm{Cl}}_{\mathcal{R}}(B))\subseteq {\mathrm{Cl}}_{\mathcal{R}\cap \mathcal{S}}(B)$, and

3.
${\mathrm{Cl}}_{\mathcal{S}}({\mathrm{Cl}}_{\mathcal{R}}(B))={\mathrm{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  20130322 16:21:26 
Last modified on  20130322 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 