Consequence Operator - Closure Operators On Partially Ordered Sets

Closure Operators On Partially Ordered Sets

A partially ordered set (poset) is a set together with a partial order ≤, i.e. a binary relation which is reflexive (a ≤ a), transitive (a ≤ b ≤ c implies a ≤ c) and antisymmetric (a ≤ b ≤ a implies a = b). Every power set 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.

x ≤ cl(x)	(cl is extensive)
x ≤ y 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 id_P ≤ cl, where id is the identity function. A self-map k that 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 from the real numbers to the real numbers, which assigns to every real x the smallest integer 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. 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, 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 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 (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 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₁ ≤ cl₂ iff cl₁(x) ≤ cl₂(x) for all x in P.