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_{n-1}\in B$, and $(b_1,\mathrm{\dots },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 $ℛ$ 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 ℛ$.

Given $B\subseteq A$ with a set of relations $ℛ$ on $A$, we say that $C\subseteq A$ is an $\mathrm{R}$-closure of $B$ if

1. $B\subseteq C$,

2. $C$ is $ℛ$-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 $ℛ$-closure of $B$, and denote it by ${\mathrm{Cl}}_{ℛ}(B)$. If $ℛ=\{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=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 ${\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 ℛ$ is unary, then the $ℛ$-closure of $B$ in $A$ is $(\bigcup ℛ)\cup B$.

Proposition 1.

${\mathrm{Cl}}_{ℛ}(B)$ exists for every $B\mathrm{\subseteq }A$.

Proof.

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

• In the case when $𝒞=\mathrm{\varnothing }$, we have $\bigcap 𝒞=A\in S_{ℛ}(B)$.

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

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

  2. If $n>1$, pick elements $c_1,\mathrm{\dots },c_{n-1}\in C$ such that $(c_1,\mathrm{\dots },c_n)\in R$. As each $c_i\in D$ for $i=1,\mathrm{\dots },n-1$, and $D$ is $R$-closed, $c_n\in D$. Since $c_n\in D$ for every $D\in 𝒞$, $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 𝒞$. Therefore, $C\in S_{ℛ}(B)$.

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

Remark. It is not hard to see ${\mathrm{Cl}}_{ℛ}$ has the following properties:

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

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

3. if $B\subseteq C$, then ${\mathrm{Cl}}_{ℛ}(B)\subseteq {\mathrm{Cl}}_{ℛ}(C)$.

Next, assume that $𝒮$ is another set of finitary relations on $A$. Then

1. if $ℛ\subseteq 𝒮$, then ${\mathrm{Cl}}_{𝒮}(B)\subseteq {\mathrm{Cl}}_{ℛ}(B)$,

2. ${\mathrm{Cl}}_{𝒮}({\mathrm{Cl}}_{ℛ}(B))\subseteq {\mathrm{Cl}}_{ℛ\cap 𝒮}(B)$, and

3. ${\mathrm{Cl}}_{𝒮}({\mathrm{Cl}}_{ℛ}(B))={\mathrm{Cl}}_{ℛ\cap 𝒮}(B)$ if $ℛ\subseteq 𝒮$ or $𝒮\subseteq ℛ$.