closure of a subset under relations


Let A be a set and R be an n-ary relation on A, n1. A subset B of A is said to be closed underPlanetmathPlanetmath R, or R-closed, if, whenever b1,,bn-1B, and (b1,,bn-1,bn)R, then bnB.

Note that if R is unary, then B is R-closed iff RB.

More generally, let A be a set and a set of (finitary) relations on A. A subset B is said to be R-closed if B is R-closed for each R.

Given BA with a set of relationsMathworldPlanetmath on A, we say that CA is an R-closureMathworldPlanetmath of B if

  1. 1.

    BC,

  2. 2.

    C is -closed, and

  3. 3.

    if DA satisfies both 1 and 2, then CD.

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

Here are some examples.

  1. 1.

    Let A=, B={5}, and R be the relation that mRn whenever m divides n. Clearly B is not closed under R (for example, (5,10)R but 10B). Then ClR(B)=5. If R is instead the relation , then Cl(B)={nAn5}.

  2. 2.

    This is an example where R is in fact a function (operation). Suppose A= and R is the binary operationMathworldPlanetmath subtraction -. Suppose B={3,5}. Then Cl-(B)=A. To see this, set C=Cl-(B). Note that 2=5-3C so 1=3-2 as well as -1=2-3C. This means that if nC, both n-1 and n+1C. By inductionMathworldPlanetmath, C=. In general, if B={p,q}, where p,q are coprimeMathworldPlanetmathPlanetmath, then Cl-(B)=. This is essentially the result of the Chinese Remainder TheoremMathworldPlanetmathPlanetmathPlanetmath.

  3. 3.

    If R is unary, then the R-closure of BA is just BR. When every R is unary, then the -closure of B in A is ()B.

Proposition 1.

Cl(B) exists for every BA.

Proof.

Let S(B) be the set of subsets of A satisfying the defining conditions 1 and 2 of -closures above, partially ordered by . If 𝒞S(B), then 𝒞S(B). To see this, we break the statement down into cases:

  • In the case when 𝒞=, we have 𝒞=AS(B).

  • When C:=𝒞, pick any n-ary relation R.

    1. (a)

      If n=1, then, since aach D𝒞 is R-closed, RD. Therefore, R𝒞={DD𝒞}=C. So C is R-closed.

    2. (b)

      If n>1, pick elements c1,,cn-1C such that (c1,,cn)R. As each ciD for i=1,,n-1, and D is R-closed, cnD. Since cnD for every D𝒞, cnC as well. This shows that C is R-closed.

    In both cases, BC since BD for every D𝒞. Therefore, CS(B).

Hence, S(B) is a complete latticeMathworldPlanetmath 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 Cl(B) of B. ∎

Remark. It is not hard to see Cl has the following properties:

  1. 1.

    BCl(B),

  2. 2.

    Cl(Cl(B))=Cl(B), and

  3. 3.

    if BC, then Cl(B)Cl(C).

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

  1. 1.

    if 𝒮, then Cl𝒮(B)Cl(B),

  2. 2.

    Cl𝒮(Cl(B))Cl𝒮(B), and

  3. 3.

    Cl𝒮(Cl(B))=Cl𝒮(B) if 𝒮 or 𝒮.

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