PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
closure of a subset under relations (Definition)

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

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.

  1. 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$.
  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=\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.
  3. 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)$.
  4. 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.
  5. 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.

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$ 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

Proposition 1   A relation $ R$ on $ A$ has closures if its arity is at least $ 2$.
Proof. Let $ B\subseteq A$, and $ \mathfrak{A}:=\lbrace X\subseteq A\mid B\subseteq X$ and $ X$ is $ R$-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}$. $ \qedsymbol$

When every $ R\in \mathcal{R}$ is unary, we have the following:

Proposition 2   $ \mathcal{R}$ has closures iff $ \mathcal{R}$ is closed under arbitrary intersections (including null intersections).
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$ is $ R$-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$. $ \qedsymbol$

Remark. In fact, $ \mathcal{R}$ has closures iff it is a complete lattice by virtue of this property. Also, it is not hard to see that $ \mathcal{R}$ has closures iff $ \operatorname{Cl}_{\mathcal{R}}$ is a closure operator, in the broad sense, on $ P(A)$, the powerset of $ A$. That is, for any $ B,C\in P(A)$,

  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)$.
  4. $ \operatorname{Cl}_{\mathcal{R}}(B\cup C)=\operatorname{Cl}_{\mathcal{R}}(B)\cup \operatorname{Cl}_{\mathcal{R}}(C)$
The first three follow easily from the definition. For 4, $ \supseteq$ follows from 3, and $ \subseteq$ follows from 1 and the fact that $ \mathcal{R}$ is a lattice (so that $ \cup$ is closed in $ \mathcal{R}$).

Next, assume that $ \mathcal{S}$ has closures. Then

  1. $ \mathcal{R}\cap \mathcal{S}$ has closures,
  2. if $ \mathcal{R}\subseteq \mathcal{S}$, then $ \operatorname{Cl}_{\mathcal{S}}(B) \subseteq \operatorname{Cl}_{\mathcal{R}}(B)$,
  3. $ \operatorname{Cl}_{\mathcal{S}}(\operatorname{Cl}_{\mathcal{R}}(B)) \subseteq \operatorname{Cl}_{\mathcal{R}\cap\mathcal{S}}(B)$, and
  4. $ \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}$.
For an example where $ \operatorname{Cl}_{\mathcal{S}}(\operatorname{Cl}_{\mathcal{R}}(B)) \ne \operatorname{Cl}_{\mathcal{R}\cap\mathcal{S}}(B)$, see the remark at the end of this entry.



"closure of a subset under relations" is owned by CWoo. [ full author list (2) ]
(view preamble)

View style:

Also defines:  closed under, has closures, closure property

Attachments:
closure of a relation with respect to a property (Definition) by CWoo
Log in to rate this entry.
(view current ratings)

Cross-references: closed, lattice, powerset, closure operator, complete lattice, implies, null, arity, class, property, infinite, superset, collection, irreflexive, meet, poset, minimal elements, contradiction, unary relation, counterexample, Chinese remainder theorem, coprime, induction, subtraction, binary operation, operation, function, divisible, least element, iff, unary, subset, relation
There are 28 references to this entry.

This is version 21 of closure of a subset under relations, born on 2006-10-29, modified 2007-10-30.
Object id is 8492, canonical name is ClosureOfASetViaRelations.
Accessed 1660 times total.

Classification:
AMS MSC: 08A02 (General algebraic systems :: Algebraic structures :: Relational systems, laws of composition)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)