Closure (mathematics)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

A set is closed under an operation if performance of that operation on members of the set always produces a member of that set. For example, the positive integers are closed under addition, but not under subtraction: is not a positive integer even though both 1 and 2 are positive integers. Another example is the set containing only zero, which is closed under addition, subtraction and multiplication (because , , and ).

Similarly, a set is said to be closed under a collection of operations if it is closed under each of the operations individually.

Basic properties[edit]

A set that is closed under an operation or collection of operations is said to satisfy a closure property. Often a closure property is introduced as an axiom, which is then usually called the axiom of closure. Modern set-theoretic definitions usually define operations as maps between sets, so adding closure to a structure as an axiom is superfluous; however in practice operations are often defined initially on a superset of the set in question and a closure proof is required to establish that the operation applied to pairs from that set only produces members of that set. For example, the set of even integers is closed under addition, but the set of odd integers is not.

When a set S is not closed under some operations, one can usually find the smallest set containing S that is closed. This smallest closed set is called the closure of S (with respect to these operations). For example, the closure under subtraction of the set of natural numbers, viewed as a subset of the real numbers, is the set of integers. An important example is that of topological closure. The notion of closure is generalized by Galois connection, and further by monads.

The set S must be a subset of a closed set in order for the closure operator to be defined. In the preceding example, it is important that the reals are closed under subtraction; in the domain of the natural numbers subtraction is not always defined.

The two uses of the word "closure" should not be confused. The former usage refers to the property of being closed, and the latter refers to the smallest closed set containing one that may not be closed. In short, the closure of a set satisfies a closure property.

Closed sets[edit]

A set is closed under an operation if the operation returns a member of the set when evaluated on members of the set. Sometimes the requirement that the operation be valued in a set is explicitly stated, in which case it is known as the axiom of closure. For example, one may define a group as a set with a binary product operator obeying several axioms, including an axiom that the product of any two elements of the group is again an element. However the modern definition of an operation makes this axiom superfluous; an n-ary operation on S is just a subset of Sn+1. By its very definition, an operator on a set cannot have values outside the set.

Nevertheless, the closure property of an operator on a set still has some utility. Closure on a set does not necessarily imply closure on all subsets. Thus a subgroup of a group is a subset on which the binary product and the unary operation of inversion satisfy the closure axiom.

An operation of a different sort is that of finding the limit points of a subset of a topological space (if the space is first-countable, it suffices to restrict consideration to the limits of sequences but in general one must consider at least limits of nets). A set that is closed under this operation is usually just referred to as a closed set in the context of topology. Without any further qualification, the phrase usually means closed in this sense. Closed intervals like [1,2] = {x : 1 ≤ x ≤ 2} are closed in this sense.

A partially ordered set is downward closed (and also called a lower set) if for every element of the set all smaller elements are also in it; this applies for example for the real intervals (−∞, p) and (−∞, p], and for an ordinal number p represented as interval [ 0, p); every downward closed set of ordinal numbers is itself an ordinal number.

Upward closed and upper set are defined similarly.

Examples[edit]

Closure operator[edit]

Given an operation on a set X, one can define the closure C(S) of a subset S of X to be the smallest subset closed under that operation that contains S as a subset, if any such subsets exist. Consequently, C(S) is the intersection of all closed sets containing S. For example, the closure of a subset of a group is the subgroup generated by that set.

The closure of sets with respect to some operation defines a closure operator on the subsets of X. The closed sets can be determined from the closure operator; a set is closed if it is equal to its own closure. Typical structural properties of all closure operations are: [1]

  • The closure is increasing or extensive: the closure of an object contains the object.
  • The closure is idempotent: the closure of the closure equals the closure.
  • The closure is monotone, that is, if X is contained in Y, then also C(X) is contained in C(Y).

An object that is its own closure is called closed. By idempotency, an object is closed if and only if it is the closure of some object.

These three properties define an abstract closure operator. Typically, an abstract closure acts on the class of all subsets of a set.

If X is contained in a set closed under the operation then every subset of X has a closure.

Binary relation closures[edit]

Consider first homogeneous relations RA × A. If a relation S satisfies aSbbSa, then it is a symmetric relation. An arbitrary homogeneous relation R may not be symmetric but it is always contained in some symmetric relation: RS. The operation of finding the smallest such S corresponds to a closure operator called symmetric closure.

A transitive relation T satisfies aTbbTcaTc. An arbitrary homogeneous relation R may not be transitive but it is always contained in some transitive relation: RT. The operation of finding the smallest such T corresponds to a closure operator called transitive closure.

Among heterogeneous relations there are properties of difunctionality and contact which lead to difunctional closure and contact closure.[2] The presence of these closure operators in binary relations leads to topology since open-set axioms may be replaced by Kuratowski closure axioms. Thus each property P, symmetry, transitivity, difunctionality, or contact corresponds to a relational topology.[3]

In the theory of rewriting systems, one often uses more wordy notions such as the reflexive transitive closure R*—the smallest preorder containing R, or the reflexive transitive symmetric closure R—the smallest equivalence relation containing R, and therefore also known as the equivalence closure. When considering a particular term algebra, an equivalence relation that is compatible with all operations of the algebra [note 1] is called a congruence relation. The congruence closure of R is defined as the smallest congruence relation containing R.

For arbitrary P and R, the P closure of R need not exist. In the above examples, these exist because reflexivity, transitivity and symmetry are closed under arbitrary intersections. In such cases, the P closure can be directly defined as the intersection of all sets with property P containing R.[4]

Some important particular closures can be constructively obtained as follows:

  • clref(R) = R ∪ { ⟨x,x⟩ : xS } is the reflexive closure of R,
  • clsym(R) = R ∪ { ⟨y,x⟩ : ⟨x,y⟩ ∈ R } is its symmetric closure,
  • cltrn(R) = R ∪ { ⟨x1,xn⟩ : n >1 ∧ ⟨x1,x2⟩, ..., ⟨xn-1,xn⟩ ∈ R } is its transitive closure,
  • clemb,Σ(R) = R ∪ { ⟨f(x1,…,xi-1,xi,xi+1,…,xn), f(x1,…,xi-1,y,xi+1,…,xn)⟩ : ⟨xi,y⟩ ∈ Rf ∈ Σ n-ary ∧ 1 ≤ inx1,...,xnS } is its embedding closure with respect to a given set Σ of operations on S, each with a fixed arity.

The relation R is said to have closure under some clxxx, if R = clxxx(R); for example R is called symmetric if R = clsym(R).

Any of these four closures preserves symmetry, i.e., if R is symmetric, so is any clxxx(R). [note 2] Similarly, all four preserve reflexivity. Moreover, cltrn preserves closure under clemb,Σ for arbitrary Σ. As a consequence, the equivalence closure of an arbitrary binary relation R can be obtained as cltrn(clsym(clref(R))), and the congruence closure with respect to some Σ can be obtained as cltrn(clemb,Σ(clsym(clref(R)))). In the latter case, the nesting order does matter; e.g. if S is the set of terms over Σ = { a, b, c, f } and R = { ⟨a,b⟩, ⟨f(b),c⟩ }, then the pair ⟨f(a),c⟩ is contained in the congruence closure cltrn(clemb,Σ(clsym(clref(R)))) of R, but not in the relation clemb,Σ(cltrn(clsym(clref(R)))).

See also[edit]

Notes[edit]

  1. ^ that is, such that e.g. xRy implies f(x,x2) R f(y,x2) and f(x1,x) R f(x1,y) for any binary operation f and arbitrary x1,x2S
  2. ^ formally: if R = clsym(R), then clxxx(R) = clsym(clxxx(R))

References[edit]

  1. ^ Birkhoff, Garrett (1967). Lattice Theory. Colloquium Publications. 25. Am. Math. Soc. p. 111.
  2. ^ Gunther Schmidt (2011) Relational Mathematics, pages 169 and 227, Encyclopedia of Mathematics and its Applications, vol. 132, Cambridge University Press ISBN 978-0-521-76268-7
  3. ^ Gunter Schmidt and M. Winter (2018) Relational Topology, Lecture Notes in Mathematics vol. 2208, Springer Verlag, ISBN 978-3-319-74451-3
  4. ^ Baader, Franz; Nipkow, Tobias (1998). Term Rewriting and All That. Cambridge University Press. pp. 8–9.