In
mathematics, a closure operator on a
set ''S'' is a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
from the
power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
of ''S'' to itself that satisfies the following conditions for all sets
:
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 closure systems or "Moore families", in honor of
E. H. Moore who studied closure operators in his 1910 ''Introduction to a form of general analysis'', whereas the concept of the closure of a subset originated in the work of
Frigyes Riesz in connection with topological spaces. Though not formalized at the time, the idea of closure originated in the late 19th century with notable contributions by
Ernst Schröder,
Richard Dedekind
and
Georg Cantor.
Closure operators are also called "hull operators", which prevents confusion with the "closure operators" studied in
topology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
. A set together with a closure operator on it is sometimes called a closure space.
Examples
Clearly, the usual set closure from
topology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
is a closure operator. Other examples include the
linear span of a subset of a
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
, the
convex hull or
affine hull
In mathematics, the affine hull or affine span of a set ''S'' in Euclidean space R''n'' is the smallest affine set containing ''S'', or equivalently, the intersection of all affine sets containing ''S''. Here, an ''affine set'' may be defined ...
of a subset of a vector space or the
lower semicontinuous
In mathematical analysis, semicontinuity (or semi-continuity) is a property of extended real-valued functions that is weaker than continuity. An extended real-valued function f is upper (respectively, lower) semicontinuous at a point x_0 if, r ...
hull
of a function
, where
is e.g. a
normed space, defined implicitely
, where
is the
epigraph of a function
.
The
relative interior is not a closure operator: although it is idempotent, it is not increasing and if
is a cube in
and
is one of its faces, then
, but
and
, so it is not increasing.
Applications
Closure operators have many applications:
In topology, the closure operators are
''topological'' closure operators, which must satisfy
:
for all
(Note that for
this gives
).
In
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary ...
and
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premise ...
, many closure operators are finitary closure operators, i.e. they satisfy
:
In the theory of
partially ordered sets, which are important in
theoretical computer science
computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumscribe the ...
, closure operators have a more general definition that replaces
with
. (See .)
Closure operators in topology
The
topological closure
In topology, the closure of a subset of points in a topological space consists of all points in together with all limit points of . The closure of may equivalently be defined as the union of and its boundary, and also as the intersection ...
of a subset ''X'' of a
topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called po ...
consists of all points ''y'' of the space, such that every
neighbourhood
A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; American and British English spelling differences, see spelling differences) is a geographically localised community ...
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.
Closure operators in algebra
Finitary closure operators play a relatively prominent role in
universal algebra, and in this context they are traditionally called ''algebraic closure operators''. Every subset of an
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary ...
''generates'' a
subalgebra In mathematics, a subalgebra is a subset of an algebra, closed under all its operations, and carrying the induced operations.
"Algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operat ...
: 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
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
its
linear span. Similarly, the function that associates to every subset of a given
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
the
subgroup
In group theory, a branch of mathematics, 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 ...
generated by it, and similarly for
fields and all other types of
algebraic structures.
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 but not in the closure of ''A'', then ''y'' is in the closure of the union of ''A'' and . A finitary closure operator with this property is called a
matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
. The
dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coor ...
of a vector space, or the
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. Specifically, it is defined as the largest cardinality of an algebraically independent subset of ...
of a field (over its
prime field
In mathematics, the characteristic of a ring , often denoted , is defined to be the smallest number of times one must use the ring's multiplicative identity (1) in a sum to get the additive identity (0). If this sum never reaches the additive ide ...
) is exactly the rank of the corresponding matroid.
The function that maps every subset of a given
field to its
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.
Using Zorn's lemmaMcCarthy (1991) p.21Kaplansky ( ...
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 as dcl (for ''definable closure'') and acl (for ''algebraic closure'').
The
convex hull in ''n''-dimensional
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean ...
is another example of a finitary closure operator. It satisfies the ''anti-exchange property:'' If ''x'' is in the closure of the union of and ''A'', but not in the union of and closure of ''A'', then ''y'' is not in the closure of the union of and ''A''. Finitary closure operators with this property give rise to
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. Antimatroi ...
s.
As another example of a closure operator used in algebra, if some algebra has universe ''A'' and ''X'' is a set of pairs of ''A'', then the operator assigning to ''X'' the smallest
congruence containing ''X'' is a finitary closure operator on ''A x A''.
Closure operators in logic
Suppose you have some
logical formalism 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
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
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
Director may refer to:
Literature
* ''Director'' (magazine), a British magazine
* ''The Director'' (novel), a 1971 novel by Henry Denker
* ''The Director'' (play), a 2000 play by Nancy Hasty
Music
* Director (band), an Irish rock band
* ''D ...
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 that 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 (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...
developed an abstract theory of logical deductions that models some properties of logical calculi. Mathematically, what he described is just a finitary closure operator on a set (the set of ''sentences''). In
abstract algebraic 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 that need not be finitary; finitary closure operators are then sometimes called finite consequence operators.
Closed and pseudo-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 ''C'' ⊆ ''P''(''S'') is closed under arbitrary intersections, then the function that associates to every subset ''X'' of ''S'' the smallest set ''Y'' ∈ ''C'' such that ''X'' ⊆ ''Y'' is a closure operator.
There is a simple and fast algorithm for generating all closed sets of a given 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'',''Y'' ⊆ ''P''(''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 {{Unreferenced, date=December 2008
In the mathematical area of order theory, the compact elements 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 ...
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.
Each closure operator on a finite set ''S'' is uniquely determined by its images of its ''pseudo-closed'' sets.
These are recursively defined: A set is pseudo-closed if it is not closed and contains the closure of each of its pseudo-closed proper subsets. Formally: ''P'' ⊆ ''S'' is pseudo-closed if and only if
* ''P'' ≠ cl(''P'') and
* if ''Q'' ⊂ ''P'' is pseudo-closed, then cl(''Q'') ⊆ ''P''.
Closure operators on partially ordered sets
A
partially ordered set (poset) is a set together with a ''partial order'' ≤, i.e. a
binary relation that is reflexive (), transitive ( implies ) and
antisymmetric ( implies ''a'' = ''b''). Every
power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
P(''S'') together with inclusion ⊆ is a partially ordered set.
A function cl: ''P'' → ''P'' 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''.
:
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 In mathematics, the qualifier pointwise is used to indicate that a certain property is defined by considering each value f(x) of some function f. An important class of pointwise concepts are the ''pointwise operations'', that is, operations defined ...
on functions between posets, one may alternatively write the extensiveness property as id
''P'' ≤ cl, where id is the
identity function
Graph of the identity function on the real numbers
In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...
. A self-map ''k'' that is increasing and idempotent, but satisfies the
dual of the extensiveness property, i.e. ''k'' ≤ id
''P'' 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'') = ''A'' ∪ ''X'' is a closure operator, whereas ''λ
A''(''X'') = ''A'' ∩ ''X'' is a kernel operator. The
ceiling function
In mathematics and computer science, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least int ...
from the
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s to the real numbers, which assigns to every real ''x'' the smallest
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
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 ''x'' ≤ ''c'' and cl(''x'') ≤ ''c'' are equivalent conditions.
Every
Galois connection (or
residuated mapping) 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.
[Blyth, p. 10] 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: ''P'' → ''A'' 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, plural categories, may refer to:
Philosophy and general uses
*Categorization, categories in cognitive science, information science and generally
* Category of being
* ''Categories'' (Aristotle)
* Category (Kant)
* Categories (Peirce) ...
, with a single morphism from ''x'' to ''y'' if and only if ''x'' ≤ ''y''. The closure operators on the partially ordered set ''P'' are then nothing but the
monad
Monad may refer to:
Philosophy
* Monad (philosophy), a term meaning "unit"
**Monism, the concept of "one essence" in the metaphysical and theological theory
** Monad (Gnosticism), the most primal aspect of God in Gnosticism
* ''Great Monad'', a ...
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, 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
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest lo ...
(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 (join) operation might differ from that of ''P''). When ''P'' is the
powerset Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
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 cl
1 ≤ cl
2 iff cl
1(''x'') ≤ cl
2(''x'') for all ''x'' in ''P''.
See also
*
*
*
*
*
*
*
Notes
References
*
Garrett Birkhoff
Garrett Birkhoff (January 19, 1911 – November 22, 1996) was an American mathematician. He is best known for his work in lattice theory.
The mathematician George Birkhoff (1884–1944) was his father.
Life
The son of the mathematician Ge ...
. 1967 (1940). ''Lattice Theory, 3rd ed''. American Mathematical Society.
* Burris, Stanley N., and H.P. Sankappanavar (1981
A Course in Universal Algebra Springer-Verlag. ''Free online edition''.
* Brown, D.J. and Suszko, R. (1973) "Abstract Logics,"
Dissertationes Mathematicae 102- 9-42.
* Castellini, G. (2003) ''Categorical closure operators''. Boston MA: Birkhaeuser.
* Edelman, Paul H. (1980) ''Meet-distributive lattices and the anti-exchange closure,''
Algebra Universalis 10: 290-299.
* Ganter, Bernhard and Obiedkov, Sergei (2016) ''Conceptual Exploration''. Springer, .
* Gerla, G. (2000) ''Fuzzy Logic: Mathematical Tools for Approximate Reasoning''.
Kluwer Academic Publishers
Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing.
Originally founded in 1842 in ...
.
* Lloyd, J.W. (1987) ''Foundations of Logic Programming''.
Springer-Verlag
Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing.
Originally founded in 1842 ...
.
*
Tarski, Alfred (1983) "Fundamental concepts of the methodology of deductive sciences" in ''Logic, Semantics, Metamathematics''. Hackett (1956 ed.,
Oxford University Press
Oxford University Press (OUP) is the university press of the University of Oxford. It is the largest university press in the world, and its printing history dates back to the 1480s. Having been officially granted the legal right to print books ...
).
*
Alfred Tarski
Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...
(1956) ''Logic, semantics and metamathematics''.
Oxford University Press
Oxford University Press (OUP) is the university press of the University of Oxford. It is the largest university press in the world, and its printing history dates back to the 1480s. Having been officially granted the legal right to print books ...
.
*
Ward, Morgan (1942) "The closure operators of a lattice,"
Annals of Mathematics
The ''Annals of Mathematics'' is a mathematical journal published every two months by Princeton University and the Institute for Advanced Study.
History
The journal was established as ''The Analyst'' in 1874 and with Joel E. Hendricks as the ...
43: 191-96.
* G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, D. S. Scott: ''Continuous Lattices and Domains'', Cambridge University Press, 2003
*
* M. Erné, J. Koslowski, A. Melton, G. E. Strecker, ''A primer on Galois connections'', in: Proceedings of the 1991 Summer Conference on General Topology and Applications in Honor of Mary Ellen Rudin and Her Work, Annals of the New York Academy of Sciences, Vol. 704, 1993, pp. 103–125. Available online in various file formats
PS.GZPS
External links
*
Stanford Encyclopedia of Philosophy:
Algebraic Propositional Logic—by Ramon Jansana.
{{DEFAULTSORT:Closure Operator
*
Universal algebra
Order theory
pl:Operator konsekwencji