Closure operator
From Wikipedia, the free encyclopedia
In mathematics, given a partially ordered set (P, ≤), a closure operator on P is a function C : P → P with the following properties:
- x ≤ C(x) for all x, i.e. C is extensive
- if x ≤ y, then C(x) ≤ C(y), i.e. C is monotonically increasing
- C(C(x)) = C(x) for all x, i.e. C is an idempotent function.
Contents |
[edit] Examples
The name comes from the fact that forming the closure of subsets of a topological space has these properties if the set of all subsets is ordered by inclusion ⊆. (Note that the topological closure operator is not characterized by these properties however; see the Kuratowski closure axioms for a complete characterization.)
Another typical closure operator is the following: take a group G and for any subset X of G, let C(X) be the subgroup generated by X, i.e. the smallest subgroup of G containing X. Then C is a closure operator on the set of subsets of G, ordered by inclusion ⊆. Analogous examples can be given for the subspace generated by a given subset of a vector space, for the subfield generated by a given subset of a field, or indeed for the subalgebra generated by a given subset of any algebra in the sense of universal algebra.
The ceiling function from the real numbers to the real numbers, which assigns to every real x the smallest integer not smaller than x, is a closure operator as well.
[edit] Closed elements; properties
Given a closure operator C, a closed element of P is an element x that is a fixed point of C, or equivalently, that is in the image of C. If a is closed and x is arbitrary, then we have x ≤ a if and only if C(x) ≤ a. So C(x) is the smallest closed element that's greater than or equal to x. We see that C is uniquely determined by the set of closed elements.
Every Galois connection 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 C can be described as follows: if A is the set of closed elements with respect to C, then C : 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, 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 monads on the category P. Equivalently, a closure operator can be viewed as an endofunctor on the category of Posets 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 (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). The closure operators on P form themselves a complete lattice; the order on closure operators is defined by C1 ≤ C2 iff C1(x) ≤ C2(x) for all x in P.
[edit] 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 of F, ordered by ⊆. For a set X of formulas, let C(X) be the set of all formulas that can be derived from X. Then C is a closure operator on P. More precisely, we can obtain C 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 C(X) as the least fixed point for J greather 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).
[edit] Bibliography
- Brown D.J. and Suszko R. (1973). Abstract Logics, Dissertationes Mathematicae, 102, 9-42.
- Castellini G. (2003) Categorial closure operators, Birkauser.
- Gerla G. (2000) Fuzzy Logic: Mathematical Tools for Approximate Reasoning, Kluwer Ac. Publishers.
- Lloyd J.W. (1987) Foundations of Logic Programming, Springer-Verlag, Berlin.
- Tarski A. (1956). Logic, semantics and metamathematics, Clarendon Press, Oxford.
- Ward M. (1942). The closure operators of a lattice, Annals of Mathematics, 43, 191-196.
