Closure operator
Encyclopedia
In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, a closure operator on a set S is a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

 cl: P(S) → P(S) from the power set of S to itself which satisfies the following conditions for all sets X,YS.
X ⊆ cl(X) (cl is extensive)
XY implies cl(X) ⊆ cl(Y)   (cl is increasing)
cl(cl(X)) = cl(X) (cl is idempotent)


Closure operators are determined by their closed sets, i.e., by the sets of the form cl(X), since the closure cl(X) of a set X is the smallest closed set containing X. Such families of "closed sets" are sometimes called "Moore families", in honor of E. H. Moore
E. H. Moore
Eliakim Hastings Moore was an American mathematician.-Life:Moore, the son of a Methodist minister and grandson of US Congressman Eliakim H. Moore, discovered mathematics through a summer job at the Cincinnati Observatory while in high school. He learned mathematics at Yale University, where he was...

 who studied closure operators in 1911. Closure operators are also called "hull operators", which prevents confusion with the "closure operators" studied in topology. A set together with a closure operator on it is sometimes called a closure system.

Closure operators have many applications:

In topology, the closure operators are topological closure operator
Kuratowski closure axioms
In topology and related branches of mathematics, the Kuratowski closure axioms are a set of axioms which can be used to define a topological structure on a set. They are equivalent to the more commonly used open set definition...

s, which must satisfy


for all integers n ≥ 0 (Note that for this gives ).

In algebra
Algebra
Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...

 and logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...

, many closure operators are finitary closure operators, i.e. they satisfy
cl(X) = { cl(Y) | YX and Y finite }.


In universal logic
Universal logic
Universal logic is the field of logic that is concerned with giving an account of what features are common to all logical structures. Universal logic aims to be to logic what universal algebra is to algebra; currently there is no universally accepted notion of logic...

, closure operators are also known as consequence operators.

In the theory of partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...

s, which are important in theoretical computer science
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....

, closure operators have an alternative definition.

Closure operators in topology

The topological closure of a subset X of a topological space
Topological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...

 consists of all points y of the space, such that every neighbourhood
Neighbourhood (mathematics)
In topology and related areas of mathematics, a neighbourhood is one of the basic concepts in a topological space. Intuitively speaking, a neighbourhood of a point is a set containing the point where you can move that point some amount without leaving the set.This concept is closely related to the...

 of y contains a point of X. The function that associates to every subset X its closure is a topological closure operator. Conversely, every topological closure operator on a set gives rise to a topological space whose closed sets are exactly the closed sets with respect to the closure operator.

For topological closure operators the second closure axiom (being increasing) is redundant.

Closure operators in algebra

Finitary closure operators play a relatively prominent role in universal algebra
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....

, and in this context they are traditionally called algebraic closure operators. Every subset of an algebra
Structure (mathematical logic)
In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it....

 generates a subalgebra
Substructure
In mathematical logic, an substructure or subalgebra is a structure whose domain is a subset of that of a bigger structure, and whose functions and relations are the traces of the functions and relations of the bigger structure...

: the smallest subalgebra containing the set. This gives rise to a finitary closure operator.

Perhaps the best known example for this is the function that associates to every subset of a given vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

 its linear span
Linear span
In the mathematical subfield of linear algebra, the linear span of a set of vectors in a vector space is the intersection of all subspaces containing that set...

. Similarly, the function that associates to every subset of a given group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...

 the subgroup
Subgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...

 generated by it, and similarly for field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...

s and all other types of algebraic structure
Algebraic structure
In abstract algebra, an algebraic structure consists of one or more sets, called underlying sets or carriers or sorts, closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...

s.

The linear span in a vector space and the similar algebraic closure in a field both satisfy the exchange property: If x is in the closure of the union of A and {y} but not in the closure of A, then y is in the closure of the union of A and {x}. A finitary closure operator with this property is called a matroid
Matroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....

. The dimension
Dimension (vector space)
In mathematics, the dimension of a vector space V is the cardinality of a basis of V. It is sometimes called Hamel dimension or algebraic dimension to distinguish it from other types of dimension...

 of a vector space, or the transcendence degree
Transcendence degree
In abstract algebra, the transcendence degree of a field extension L /K is a certain rather coarse measure of the "size" of the extension...

 of a field (over its prime field) is exactly the rank of the corresponding matroid.

The function that maps every subset of a given field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...

 to its algebraic closure
Algebraic closure
In mathematics, particularly abstract algebra, an algebraic closure of a field K is an algebraic extension of K that is algebraically closed. It is one of many closures in mathematics....

 is also a finitary closure operator, and in general it is different from the operator mentioned before. Finitary closure operators that generalize these two operators are studied in model theory
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....

 as dcl (for definable closure) and acl (for algebraic closure).

The convex hull
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....

 in n-dimensional Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...

 is another example of a finitary closure operator. It satisfies the anti-exchange property: If x is not contained in the union of A and {y}, but in its closure, then y is not contained in the closure of the union of A and {x}. Finitary closure operators with this property give rise to antimatroid
Antimatroid
In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included...

s.

Closure operators in logic

Suppose you have some logical formalism
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...

 that contains certain rules allowing you to derive new formulas from given ones. Consider the set F of all possible formulas, and let P be the power set of F, ordered by ⊆. For a set X of formulas, let cl(X) be the set of all formulas that can be derived from X. Then cl is a closure operator on P. More precisely, we can obtain cl as follows. Call "continuous" an operator J such that, for every directed class T,
J(lim T)= lim J(T).


This continuity condition is on the basis of a fixed point theorem for J. Consider the one-step operator J of a monotone logic. This is the operator associating any set X of formulas with the set J(X) of formulas which are either logical axioms or are obtained by an inference rule from formulas in X or are in X. Then such an operator is continuous and we can define cl(X) as the least fixed point for J greater or equal to X. In accordance with such a point of view, Tarski, Brown, Suszko and other authors proposed a general approach to logic based on closure operator theory. Also, such an idea is proposed in programming logic (see Lloyd 1987) and in fuzzy logic (see Gerla 2000).

Consequence operators

Around 1930, Alfred Tarski
Alfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...

 developed an abstract theory of logical deductions which models some properties of logical calculi. Mathematically, what he described is just a finitary closure operator on a set (the set of sentences). In universal logic
Universal logic
Universal logic is the field of logic that is concerned with giving an account of what features are common to all logical structures. Universal logic aims to be to logic what universal algebra is to algebra; currently there is no universally accepted notion of logic...

, finitary closure operators are still studied under the name consequence operator, which was coined by Tarski. The set S represents a set of sentences, a subset T of S a theory, and cl(T) is the set of all sentences that follow from the theory. Nowadays the term can refer to closure operators which need not be finitary; finitary closure operators are then sometimes called finite consequence operators.

At this level of abstraction, S need not be a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...

. Since one can just as well apply this formalism to informal sentences in natural language, Tarski opened the field for mathematical reasoning about relatively intangible objects such as scientific theorems or even religious beliefs.

Closed sets

The closed sets with respect to a closure operator on S form a subset C of the power set P(S). Any intersection of sets in C is again in C. In other words, C is a complete meet-subsemilattice of P(S). Conversely, if CP(S) is closed under arbitrary intersections, then the function that associates to every subset X of S the smallest set YC such that XY is a closure operator.

A closure operator on a set is topological if and only if the set of closed sets is closed under finite unions, i.e., C is a meet-complete sublattice of P(S). Even for non-topological closure operators, C can be seen as having the structure of a lattice. (The join of two sets X,YP(S) being cl(X Y).) But then C is not a sublattice of the lattice P(S).

Given a finitary closure operator on a set, the closures of finite sets are exactly the compact element
Compact element
In the mathematical area of order theory, the compact or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not already contain members above the compact element....

s of the set C of closed sets. It follows that C is an algebraic poset.
Since C is also a lattice, it is often referred to as an algebraic lattice in this context. Conversely, if C is an algebraic poset, then the closure operator is finitary.

Closure operators on partially ordered sets

A partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...

 (poset) is a set together with a partial order ≤, i.e. a binary relation which is reflexive , transitive ( implies ) and antisymmetric ( implies a = b). Every power set P(S) together with inclusion ⊆ is a partially ordered set.

A function cl: PP from a partial order P to itself is called a closure operator if it satisfies the following axioms for all elements x, y in P.
x ≤ cl(x) (cl is extensive)
xy implies cl(x) ≤ cl(y)   (cl is increasing)
cl(cl(x)) = cl(x) (cl is idempotent)


More succinct alternatives are available: the definition above is equivalent to the single axiom
x ≤ cl(y) if and only if cl(x) ≤ cl(y)


for all x, y in P.

Using the pointwise order on functions between posets, one may alternatively write the extensiveness property as idP ≤ cl, where id is the identity function
Identity function
In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument...

. A self-map k that that is increasing and idempotent, but satisfies the dual
Duality (order theory)
In the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop if and only if y ≤ x holds in P...

 of the extensiveness property, i.e. k ≤ idP is called a kernel operator, interior operator, or dual closure. As examples, if A is a subset of a set B, then the self-map on the powerset of B given by μA(X) = AX is a closure operator, whereas λA(X) = AX is a kernel operator. The ceiling function from the real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

s to the real numbers, which assigns to every real x the smallest integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

 not smaller than x, is another example of a closure operator.

A fixpoint of the function cl, i.e. an element c of P that satisfies cl(c) = c, is called a closed element. A closure operator on a partially ordered set is determined by its closed elements. If c is a closed element, then xc and cl(x) ≤ c are equivalent conditions.

Every Galois connection
Galois connection
In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets . The same notion can also be defined on preordered sets or classes; this article presents the common case of posets. Galois connections generalize the correspondence...

 (or residuated mapping
Residuated mapping
In mathematics, the concept of a residuated mapping arises in the theory of partially ordered sets. It refines the concept of a monotone function....

) gives rise to a closure operator (as is explained in that article). In fact, every closure operator arises in this way from a suitable Galois connection. The Galois connection is not uniquely determined by the closure operator. One Galois connection that gives rise to the closure operator cl can be described as follows: if A is the set of closed elements with respect to cl, then cl: PA is the lower adjoint of a Galois connection between P and A, with the upper adjoint being the embedding of A into P. Furthermore, every lower adjoint of an embedding of some subset into P is a closure operator. "Closure operators are lower adjoints of embeddings." Note however that not every embedding has a lower adjoint.

Any partially ordered set P can be viewed as a category
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...

, with a single morphism from x to y if and only if xy. The closure operators on the partially ordered set P are then nothing but the monad
Monad (category theory)
In category theory, a branch of mathematics, a monad, Kleisli triple, or triple is an functor, together with two natural transformations...

s on the category P. Equivalently, a closure operator can be viewed as an endofunctor on the category of partially ordered sets that has the additional idempotent and extensive properties.

If P is a complete lattice
Complete lattice
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...

, then a subset A of P is the set of closed elements for some closure operator on P if and only if A is a Moore family on P, i.e. the largest element of P is in A, and the infimum
Infimum
In mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...

 (meet) of any non-empty subset of A is again in A. Any such set A is itself a complete lattice with the order inherited from P (but the supremum
Supremum
In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...

 (join) operation might differ from that of P). When P is the powerset Boolean algebra of a set X, then a Moore family on P is called a closure system on X.

The closure operators on P form themselves a complete lattice; the order on closure operators is defined by cl1 ≤ cl2 iff
IFF
IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...

 cl1(x) ≤ cl2(x) for all x in P.

History

The concept of a closure is due to E. H. Moore
E. H. Moore
Eliakim Hastings Moore was an American mathematician.-Life:Moore, the son of a Methodist minister and grandson of US Congressman Eliakim H. Moore, discovered mathematics through a summer job at the Cincinnati Observatory while in high school. He learned mathematics at Yale University, where he was...

, appearing in his 1910 Introduction to a form of general analysis, whereas that of a closure subset originated in the work of Frigyes Riesz
Frigyes Riesz
Frigyes Riesz was a mathematician who was born in Győr, Hungary and died in Budapest, Hungary. He was rector and professor at University of Szeged...

 in connection with topological spaces.

See also

  • Čech closure operator
  • Galois connection
    Galois connection
    In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets . The same notion can also be defined on preordered sets or classes; this article presents the common case of posets. Galois connections generalize the correspondence...

  • Interior algebra
    Interior algebra
    In abstract algebra, an interior algebra is a certain type of algebraic structure that encodes the idea of the topological interior of a set. Interior algebras are to topology and the modal logic S4 what Boolean algebras are to set theory and ordinary propositional logic...

  • Kuratowski closure axioms
    Kuratowski closure axioms
    In topology and related branches of mathematics, the Kuratowski closure axioms are a set of axioms which can be used to define a topological structure on a set. They are equivalent to the more commonly used open set definition...

  • Closure (topology)
    Closure (topology)
    In mathematics, the closure of a subset S in a topological space consists of all points in S plus the limit points of S. Intuitively, these are all the points that are "near" S. A point which is in the closure of S is a point of closure of S...

     and Interior (topology)
    Interior (topology)
    In mathematics, specifically in topology, the interior of a set S of points of a topological space consists of all points of S that do not belong to the boundary of S. A point that is in the interior of S is an interior point of S....


External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK