Closure Operators and the Consequence Operator

Introduction

A closure operator on a poset is a map that enlarges each element, respects the order and is unchanged when applied twice: the prototype is the topological closure of a set, or the span of a set of vectors. Its dual notion is the interior operator, which shrinks each element; the prototype is the interior of a topological space, or the largest subset of a given set on which a data set is constant. This article develops the theory of these two operators on a general poset and lattice. It shows that the closed elements of a closure operator form a closure system, that every closure system comes from a closure operator, and that the closed elements form a complete lattice when the ambient poset is complete; it isolates the finitary closure operators, whose closed sets are determined by finite data, and it identifies the consequence operator of logic as a finitary closure operator on a set of formulas, with the closed sets as the theories and the closed sets forming the Lindenbaum–Tarski lattice.

The article presupposes Order Theory and Lattices for posets, lattices, complete lattices, the least element, directed subsets and the closure operator (its definition is repeated for convenience), and Sets, Functions and Relations for sets, functions and families. The instance in which the closed elements are the relations preserved by an operator gives the connection to The Converse Relation as an Operator, where the symmetrisation of a relation is a closure operator. The poset example of a down-set generated by a set, and the monoid example of a submonoid generated by a set, are the two algebraic instances used. The systematic theory of groups is Groups, in this Part, and the Cauchy-type closures of group theory are not used.

Three boundaries are observed. No topology is used: the topological closure, the Kuratowski axioms and the separation axioms are the subject of Part II, and this article works with the order theory alone; the closure operator is defined by the three properties above and not by a topology. The Galois connection, also called an adjunction between posets, is recalled from Order Theory and Lattices and used here for the passage from a closure operator to its family of closed sets; its reading through an involution, and the Galois connection that the involution reverses, belong to The Involution on the Closure Operators, in the * Operator Theory group of this category, and are not used. The adjoint reading of the converse relation is The Converse as an Adjoint, in the same group. Nothing linear and no form is used.

Closure and Interior Operators

Definitions and First Properties

Let $P$ be a poset.

Definition. A map $c : P \to P$ is a closure operator if, for all $x, y \in P$,

$$ x \leq c(x), \qquad x \leq y \ \Longrightarrow \ c(x) \leq c(y), \qquad c(c(x)) = c(x). $$

The three properties are called extensiveness, monotonicity and idempotence. An element $x$ is closed if $c(x) = x$, and the set of closed elements is written $P_c$.

A map $i : P \to P$ is an interior operator if it satisfies the same three properties with the order reversed:

$$ i(x) \leq x, \qquad x \leq y \ \Longrightarrow \ i(x) \leq i(y), \qquad i(i(x)) = i(x). $$

The elements with $i(x) = x$ are the open elements. The two notions are exchanged by passing to the opposite order: $i$ is an interior operator on $P$ exactly when $i$ is a closure operator on $P^{\mathrm{op}}$. The article states everything for closure operators and leaves the dual to the duality principle of Order Theory and Lattices.

Proposition. Let $c$ be monotone and idempotent. Then $c$ is a closure operator if and only if $c(x)$ is the least closed element above $x$, for every $x \in P$. In that case the least closed element above $x$ exists and equals $c(x)$.

Proof. Suppose $c$ is a closure operator and let $x \in P$. Then $c(x)$ is closed, by idempotence, and $x \leq c(x)$ by extensiveness. If $z$ is closed and $x \leq z$ then monotonicity gives $c(x) \leq c(z) = z$, so $c(x)$ is the least closed element above $x$. Conversely, suppose that $c(x)$ is the least closed element above $x$ for every $x$; taking $x$ closed shows $c(x) = x$ for closed $x$, so $c$ is idempotent, and taking $x$ arbitrary shows $x \leq c(x)$, so $c$ is extensive; if $x \leq y$ then $c(y)$ is closed and $x \leq y \leq c(y)$, so $c(x) \leq c(y)$ by the defining property of $c(x)$, and $c$ is monotone.

The proposition is the reason $c(x)$ is called the closure of $x$: it is the least closed element above $x$, and the closed elements are exactly the fixed points of $c$.

Proposition. The composite of two closure operators is extensive and monotone, but need not be idempotent, so it need not be a closure operator.

Proof. Let $c_1, c_2$ be closure operators and put $c = c_2 \circ c_1$. Then $x \leq c_1(x) \leq c_2(c_1(x)) = c(x)$, so $c$ is extensive, and it is monotone as a composite of monotone maps. For the failure of idempotence, take the four-element Boolean lattice $\mathcal{P}(\{0,1\})$, let $c_1$ be the closure operator with closed sets $\{\emptyset, \{0,1\}\}$, so that $c_1(X) = X$ for $X = \emptyset$ and $c_1(X) = {0,1}$ otherwise, and let $c_2$ be the closure operator with closed sets $\{\{0\}, \{0,1\}\}$. Then

$$ c(\emptyset) = c_2(c_1(\emptyset)) = c_2(\emptyset) = \{0\}, \qquad c(c(\emptyset)) = c_2(c_1(\{0\})) = c_2(\{0,1\}) = \{0,1\}, $$

and $\{0\} \neq \{0,1\}$, so $c$ is not idempotent.

Closed Elements

The closed elements are the point of the theory, and their order determines the operator, by the proposition above. Two elementary facts are used constantly.

Proposition. If $c$ is a closure operator and $P$ has a least element $\bot$, then $c(\bot)$ is the least closed element and is the least element of $P_c$. If $P$ has a greatest element $\top$ then $\top$ is closed.

Proof. $c(\bot)$ is closed and, by the least-element property of $\bot$, there is no $x$ with $x < \bot$; the least closed element above $\bot$ is $c(\bot)$, and every closed element is above $\bot$, so $c(\bot)$ is least in $P_c$. If $x \leq \top$ for all $x$ then $c(\top) \leq \top$ by definition of $\top$, and $\top \leq c(\top)$ by extensiveness, so $c(\top) = \top$.

Proposition. Let $c$ be a closure operator on a lattice $P$ and let $x, y \in P$ be closed. Then $x \wedge y$ is closed. If $z$ is closed and $x \vee y \leq z$ then $c(x \vee y) \leq z$.

Proof. $x \wedge y \leq x$, so $c(x \wedge y) \leq c(x) = x$; likewise $c(x \wedge y) \leq y$; so $c(x \wedge y) \leq x \wedge y$, and the reverse inequality is extensiveness. For the second, $x \vee y \leq z$ with $z$ closed gives $c(x \vee y) \leq c(z) = z$.

So the closed elements are closed under meets, and the least closed element above a join is obtained by applying $c$ afterwards. This is the source of the lattice structure on $P_c$ in the next section.

Closure Systems and the Lattice of Closed Elements

Closure Systems

Definition. Let $P$ be a complete lattice. A subset $F \subseteq P$ is a closure system if it is closed under arbitrary meets:

$$ Y \subseteq F \ \Longrightarrow \ \bigwedge Y \in F, $$

with the meet of the empty family, namely $\top$, included. The members of $F$ are the closed elements of the system.

Theorem. Let $P$ be a complete lattice. The map

$$ c \;\longmapsto\; P_c = \{x \in P : c(x) = x\} $$

from closure operators on $P$ to closure systems in $P$ is a bijection, with inverse

$$ F \;\longmapsto\; c_F, \qquad c_F(x) = \bigwedge \{y \in F : y \geq x\}. $$

Proof. If $c$ is a closure operator then $P_c$ is closed under meets: for a family $(x_i)$ of closed elements and $x = \bigwedge_i x_i$, monotonicity gives $c(x) \leq c(x_i) = x_i$ for each $i$, so $c(x) \leq x$, and extensiveness gives $x \leq c(x)$; so $x$ is closed, and the meet of the empty family is $\top$, which is closed. Conversely, for a closure system $F$ the meet $c_F(x)$ is taken over a non-empty family, since $\top \in F$ and $\top \geq x$, so it exists; $c_F$ is extensive because $x$ is a lower bound of the family and the family is non-empty so that the meet is $\geq x$; it is monotone because the family for a larger $x$ is a subfamily of the family for a smaller one, so its meet is larger; and it is idempotent because $c_F(x)$ is the least member of $F$ above $x$, hence a member of $F$, hence $c_F(c_F(x)) = c_F(x)$. Finally the two constructions are inverse: for a closure operator $c$, the least closed element above $x$ is $c(x)$, so $c_{P_c} = c$, and for a closure system $F$, every member of $F$ above $x$ is closed for $c_F$ and $c_F(x)$ lies in $F$, so the closed elements of $c_F$ are exactly $F$.

The Galois Connection to the Closed Sets

The passage from a closure operator to its family of closed sets is a Galois connection, in the sense of Order Theory and Lattices, and this is the exact sense in which the operator and the system determine each other.

Proposition. Let $c$ be a closure operator on a poset $P$ and let $j : P_c \hookrightarrow P$ be the inclusion of the closed elements. Then $c$ and $j$ are adjoint,

$$ c \dashv j, \qquad \text{that is,} \qquad c(x) \leq y \iff x \leq j(y) \quad (x \in P,\ y \in P_c). $$

Proof. If $c(x) \leq y$ with $y$ closed, then $x \leq c(x) \leq y = j(y)$ by extensiveness. If $x \leq j(y) = y$, then $c(x) \leq c(y) = y$ by monotonicity and the closedness of $y$. So the two statements are equivalent, and both maps are monotone.

Corollary. A closure operator is the same datum as a Galois connection $c \dashv j$ in which the right adjoint $j$ is the inclusion of a subposet and $c$ is a self-map of $P$. The closed elements are exactly the fixed points of $c$, and the left adjoint of any Galois connection of this shape is a closure operator.

Proof. Given $c \dashv j$ with $j$ an inclusion, put $y = c(x)$ in the adjunction identity to get $x \leq j(c(x)) = c(x)$, and use the idempotence of a left adjoint; the converse is the proposition. The identification of the closed elements with the fixed points is the definition.

This is the Galois connection that the scope of the article names: it connects the operator to the family of its closed sets, and through it the two constructions of the previous theorem are inverse. The Galois connection built from a relation, and the closure operators it induces, are treated in Order Theory and Lattices and are not repeated; the reading of a Galois connection through an involution is deferred, as stated in the Introduction.

Remark. The compactness of the closure is the finitary property treated in the next section: the closed sets are determined by finite data, and a closure system with this property is closed under unions of directed families. The word is used in its algebraic sense; the topological compactness of Part II is a different notion and is not meant.

The Complete Lattice of Closed Elements

Theorem. Let $c$ be a closure operator on a complete lattice $P$. Then $P_c$ is a complete lattice in the order inherited from $P$, in which

$$ {\bigwedge}^{P_c}_{i} x_i = {\bigwedge}^{P}_{i} x_i, \qquad {\bigvee}^{P_c}_{i} x_i = c\Big({\bigvee}^{P}_{i} x_i\Big). $$

Proof. The meet of a family of closed elements is closed, by the previous theorem, so it is the greatest lower bound in $P_c$ and is computed as in $P$. The element $c(\bigvee_i x_i)$ is closed and lies above every $x_i$, since $\bigvee_i x_i$ does; and if $z$ is closed with $x_i \leq z$ for all $i$ then $\bigvee_i x_i \leq z$, so $c(\bigvee_i x_i) \leq c(z) = z$. Hence $c(\bigvee_i x_i)$ is the least upper bound in $P_c$. So $P_c$ has all meets and joins, and it is complete.

Corollary. Every complete lattice is isomorphic to the lattice of closed elements of a closure operator on itself, namely the identity; and for a closure system $F$ on a complete lattice $P$, the lattice $F$ has meets computed in $P$ and joins computed as $c_F$ of the join in $P$. The passage from $P$ to $P_c$ is therefore a quotient in the order-theoretic sense: it is monotone, surjective onto $P_c$ and idempotent, and it is left adjoint to the inclusion $P_c \hookrightarrow P$ — an adjunction that is named but not used here, its theory being deferred.

Example. On a poset $Q$ let $P = \mathcal{P}(Q)$ be the power-set lattice and let

$$ {\downarrow}(X) = \{q \in Q : q \leq x \text{ for some } x \in X\} $$

be the down-set generated by $X$. Then ${\downarrow}$ is a closure operator on $\mathcal{P}(Q)$: it is extensive because $x \in X$ has $x \leq x$; it is monotone because a larger $X$ gives more elements below; and it is idempotent because if $q \leq x$ for some $x \in {\downarrow}(X)$ then $q \leq x \leq x'$ for some $x' \in X$, so $q \in {\downarrow}(X)$. The closed sets are the down-sets, the subsets $D$ with $q \leq d \in D \Rightarrow q \in D$, and they form a complete lattice under inclusion.

Example. Let $M$ be a monoid and let $P = \mathcal{P}(M)$. The submonoid generated by $X$ is

$$ \langle X \rangle = \{m_1 m_2 \cdots m_k : k \geq 0, \ m_j \in X\}, $$

with the empty product equal to the identity. The map $X \mapsto \langle X \rangle$ is a closure operator whose closed sets are the submonoids of $M$; the closed sets form a complete lattice in which the meet is the intersection and the join is the generated submonoid of the union, by the corollary. The monoid of endomorphisms of a structure, in Endomorphisms of a Relational Structure, is such an $M$, and the generated submonoids are the submonoids of operators.

The Consequence Operator

Tarski's Axioms

The logical notion of consequence is the instance of the theory in which the ambient lattice is the
power set of a set of formulas. Let $\Sigma$ be a set, its elements called formulas, and let $C: \mathcal{P}(\Sigma) \to \mathcal{P}(\Sigma)$.

Definition. The map $C$ is a consequence operator if it satisfies, for all $X, Y \subseteq \Sigma$,

$$ X \subseteq C(X), \qquad X \subseteq Y \ \Longrightarrow \ C(X) \subseteq C(Y), \qquad C(C(X)) = C(X). $$

These are extensiveness, monotonicity and idempotence, so a consequence operator is exactly a closure operator on the complete lattice $\mathcal{P}(\Sigma)$. A set $X$ is closed if $C(X) = X$; the closed sets are called the theories, and the Lindenbaum–Tarski lattice of the consequence operator is the complete lattice of theories.

Theorem. The theories of a consequence operator form a closure system: they are closed under arbitrary intersections. Conversely every closure system $T \subseteq \mathcal{P}(\Sigma)$ is the set of theories of a unique consequence operator, namely $C(X) = \bigcap {Y \in T : X \subseteq Y}$. The consequence operator is recovered from its theories by this formula, and the lattice of theories has meets given by intersection and joins given by $C$ of the union.

Proof. This is the theorem of the previous section specialised to the power-set lattice, whose join is the union and whose least upper bound of a family of theories is the closure of the union.

The systematic account of proof, of the deduction theorem and of the relation of consequence to validity is the subject of Logic and Proof, in Part 0, and the algebraic treatment of the same consequence operator as an operator on the free structure of formulas belongs to the algebraic articles of Part V. This article uses the consequence operator as one instance of the order theory, and draws no logical conclusion from it beyond the lattice structure of the theories.

Finitary Operators

Consequence in logic is determined by finite sets of hypotheses, and that property has an exact order-theoretic form.

Definition. A closure operator $c$ on $\mathcal{P}(\Sigma)$ is finitary, or algebraic, if for every $X \subseteq \Sigma$,

$$ c(X) = \bigcup \{\, c(F) : F \subseteq X, \ F \text{ finite} \,\}. $$

Theorem. A closure operator $c$ on $\mathcal{P}(\Sigma)$ is finitary if and only if its family of closed sets is closed under unions of directed families.

Proof. Suppose $c$ is finitary and let $\mathcal{D}$ be a directed family of closed sets, with $X = \bigcup \mathcal{D}$. Every finite $F \subseteq X$ is contained in some member of $\mathcal{D}$, because $F$ is finite, each of its elements lies in a member of $\mathcal{D}$, and a finite union of members of a directed family lies in the family. So $c(F) \subseteq D \subseteq X$ for some $D \in \mathcal{D}$, and $c(X) = \bigcup_F c(F) \subseteq X$, whence $X$ is closed. Conversely, suppose the closed sets are closed under directed unions, and let $X \subseteq \Sigma$. The family ${c(F) : F \subseteq X \text{ finite}}$ is directed by inclusion, because $c(F_1 \cup F_2)$ is closed and contains both $c(F_1)$ and $c(F_2)$, so its union $Y$ is closed; and $X \subseteq Y$, so $c(X) \subseteq Y$; and $c(F) \subseteq c(X)$ for finite $F \subseteq X$ gives $Y \subseteq c(X)$. So $c(X) = Y$ and $c$ is finitary.

The finitary closure operators are the ones that come from a set of inference rules each with finitely many premisses, and this is the form in which the consequence operator is used in Logic and Proof: the rules give a finitary closure operator whose theories are the sets closed under the rules. The example of the submonoid generated by a set is finitary, because a word in the generators has finitely many letters and each letter lies in a finite subset of the generating set; the down-set generated by a set is finitary for the same reason.

Example (a closure operator that is not finitary). Let $\Sigma$ be an infinite set and let the closed sets be the finite subsets of $\Sigma$ together with $\Sigma$ itself. This family is a closure system: the intersection of two finite sets is finite, and the intersection of a finite set with $\Sigma$ is finite. The closure operator it defines is

$$ c(X) = X \ \text{ for finite } X, \qquad c(X) = \Sigma \ \text{ for infinite } X . $$

It is not finitary. The finite subsets of the set of even elements form a directed family whose union is the infinite set $E$ of even elements, and $c(E) = \Sigma$, while $\bigcup {c(F) : F \subseteq E \text{ finite}} = \bigcup {F : F \subseteq E \text{ finite}} = E$, a proper subset of $\Sigma$. Equivalently, the family of closed sets is not closed under directed unions, which the theorem identifies as the obstruction.

Proposition. A finitary closure operator on $\mathcal{P}(\Sigma)$ is determined by its values on finite sets.

Proof. This is the content of the definition: $c(X)$ is the union of the sets $c(F)$ for finite $F \subseteq X$.

Summary

A closure operator on a poset enlarges, preserves and is unchanged by repetition; its fixed points are the closed elements, and $c(x)$ is the least closed element above $x$. An interior operator is the same notion for the opposite order. On a complete lattice the closure operators are in bijection with the closure systems, the subsets closed under arbitrary meets, and the closed elements of a closure operator form a complete lattice in which meets are computed in the ambient lattice and joins are computed by applying the operator to the join.

The consequence operator of a logic is a closure operator on the power set of the formulas; its closed sets are the theories, they form the Lindenbaum–Tarski lattice, and the finitary consequence operators — those determined by their values on finite sets — are exactly the ones whose theories are closed under directed unions. The down-set generated by a set, the submonoid generated by a set and the symmetrisation of a relation are the three algebraic instances used in the article, and each is a closure operator whose closed sets are the down-sets, the submonoids and the symmetric relations respectively.

Summary of Notation

Symbol	Meaning
$c : P \to P$	Closure operator: extensive, monotone, idempotent
$i : P \to P$	Interior operator: intensive, monotone, idempotent
$P_c$, Fix$(c)$	Closed elements of $c$, the fixed points
closure system $F$	Subset closed under arbitrary meets
$c_F(x) = \bigwedge \{y \in F : y \geq x\}$	Closure operator of a closure system
${\downarrow}(X)$	Down-set generated by $X$, a closure operator on $\mathcal{P}(Q)$
$\langle X \rangle$	Submonoid generated by $X$
$C : \mathcal{P}(\Sigma) \to \mathcal{P}(\Sigma)$	Consequence operator
theory	Closed set of a consequence operator
finitary / algebraic	$c(X) = \bigcup \{c(F) : F \subseteq X \text{ finite}\}$