Closed pairs of adjunctions between lattices

Galois connections generalize closure conditions like those provided by the adjoint pairs of image/inverse image functions. In the special case of lattices, it can be shown that these closed pairs have certain special properties.

Definition. let $F: A \to B$ and $G: B \to A$ be a monotone Galois connection. Then we say that $(A,B)$ is a closed pair if it satisfies one of the equivalent conditions $F(A) \subseteq B$ or $A \subseteq G(B)$.

The point of Galois connections is that these closed pairs can be described by any one of two equivalent conditions. In the case of elementary set theory, these conditions are provided by the image and inverse image functions between sets.

Definition. let $F: A \to B$ and $G: B \to A$ be a monotone Galois connection. Let $A \times B$ be the product ordering on $A$ and $B$ defined in the natural way by the category of preorders. Define the partial order on the set of all closed pairs $C(F,G)$ to be the one induced on it by $A \times B$.

The special case of lattices warrants further examination. If there is a Galois connection between two lattices $A$ and $B$ then the product ordering $A \times B$ is itself a lattice, and so $C(F,G)$ is a suborder of a lattice. As we shall see, it is actually the most desirable type of suborder of a lattice.

Theorem. let $F: A \to B$ and $G: B \to A$ be a monotone Galois connection of lattices. Then $C(F,G)$ is a sublattice of $A \times B$.

Proof. let $(a,b)$ and $(c,d)$ be closed pairs. Then $F(a) \subseteq b$ and $G(c) \subseteq d$. Consider $(a \vee c, b \vee d)$. Then since $F(a) \subseteq b \subseteq b \vee d$ and $F(c) \subseteq d \subseteq b \vee d$ so both $F(a)$ and $F(c)$ are less then $b \vee d$. Then since $F(a) \vee F(c)$ is the least upper bound of $F(a)$ and $F(c)$ we have $F(a) \vee F(c) \subseteq b \vee d$. Then since $F$ preserves suprema we have $F(a \vee c) = F(a) \vee F(c)$ so that $F(a \vee c) \subseteq b \vee d$ which implies that $(a \vee c, b \vee d)$ is a closed pair. This demonstrates join-closedness. Meet-closedness follows by the dualizing. $\square$

Every sublattice $S$ of a lattice $L$ is associated to a closure operator and an interior operator. The closure of $x \in L$ is the meet of all of its successors in $S$ and its interior is the join of all of its predecessors. In the case of a monotone Galois connection, the computation of closure and interior operators on closed pairs are rather easier.

Definition. let $(a,b)$ be a pair in the product lattice $A \times B$ of a monotone Galois connection $(F,G)$ between lattices. Then the closure of $(a,b)$ is $(a,b \vee F(a))$ and the interior of $(a,b)$ is $(a \wedge G(b),b)$.

The most important Galois connections are actually between lattices, so this gets closer to what monotone Galois connections are actually about. In the special case of the image/inverse image functor, this demonstrates that the closed pairs of a $F: A \to B$ are a sublattice of $\wp(A) \times \wp(B)$. This lattice $\wp(A) \times \wp(B)$ is a distributive lattice, so this means that closed pairs form a distributive lattice, in fact they are the distributive lattice of subobjects of a $F: A \to B$ in the topos $Sets^{\to}$.

Example. let $f : A \to B$ be a multi-valued function in $Rel$, then $f$ induces a single-valued function $f: A \to \wp(B)$ in the topos $Sets$. Then for closed pairs $(a,b)$ we define a lower adjoint of $a$ to be $\{b : \exists c \in a : b \in f(c)\}$ and we define the upper adjoint of $b$ to be $\{d : r(d) \subseteq b \}$. Then closed pairs $(a,b)$ form a lattice: the lattice of subalgebras of a multi-valued function $Sub(f)$.

This basic concept is how we can define specialized subalgebras for hyperstructures, by generalizing the concept of subalgebras from classical algebra. Let $f: X^2 \to X$ be a hypersemigroup. Then a hypersubsemigroup of $f$ will simply be a pair $(S^2,S)$ that forms a closed pair with respect to $f$ which is induced by a subset $S \subseteq X$, and so on. In either case, the fundamental objects of lattice theory like lattices of subobjects come from adjoints.

References:
Galois connection

Functorial theory of Galois connections

We define the following category $C$ as an index category for monotone Galois connections: $C$ has four non-identity morphisms with the properties that $FG$ and $GF$ are idempotent, $FGF = F$ and $GFG = G$. A structure with these composition laws forms a category so $C$ is a well-defined category. We will use this category to examine the theory of Galois connections.

Galois connections as presheaves
Using the category $C$ we can define every monotone Galois connection as a presheaf of preorders in the functor category $[C,Ord]$. These are presheaves by the forgetful functor $F: Ord \to Sets$ from the category of preorders to the topos $Sets$.

Definition. let $(F,G)$ be a monotone Galois connection of preorders $A$ and $B$. Then their presheaf of preorders is defined by the diagram $C$ using the composed component arrows $FG$ and $GF$ as closure and interior operators.

This nicely encapsulates the entire datum of a monotone Galois connection into a single structure presheaf. The dual condition that all presheaves of preorders over $C$ is a monotone Galois connection is of course not true. Instead for that to happen the mappings of the presheaf need to have certain special conditions hold.

Properties of the component morphisms
The four morphisms in the Galois connection diagram $F$,$G$, $FG$, and $GF$ all belong to different types of categories and they all have their own theories associated to them:

• $F$: a residuated mapping (it reflects principal down sets)
• $G$: a coresiduated mapping (it reflects principal up sets)
• $GF$: a closure operator (idempotent, extensive, and monotone)
• $FG$: an interior operator (idempotent, decreasing, and monotone)

Each of these form different types of categories, because they are all closed under composition. The category of partial orders and residuated maps can be used to study the compositional properties of monotone Galois connections.

Presheaf perspective on order theory
It is increasingly my contention that the basic objects of order theory should be presheaves of preorders, and that this presheaf theoretic perspective should be applied to the subject. Let $S$ be a set, then it is associated to a lattice of preorders. A particular elegant construction is that we can associate instead to any presheaf $F: X \to Sets$ a lattice of presheaves of preorders.

I argue that the perspective of studying presheaves of preorders, which are functors $F: C \to Ord$ gives us the best theoretic footing on which to do order-theory from. In the same way that algebraic geometry studies certain presheaves of rings, order theory should be remade for presheaf foundations. In this context, a preorder is a presheaf over the trivial category, a monotone map is a presheaf over $T_2$, an order isomorphism is a presheaf over $K_2$, a Galois connection is a presheaf over $C$, and so on.

Presheaves and their topoi $Sets^C$ should be their basic object of study in any case in either logic or geometry. Topos theory is of the greastest foundational importance, however, when we get around to studying preorders, which are among the most fundamental objects of study then they should be considered by presheaves of preorders. I think the presheaf theoretic perspective will be getting greater acceptance and acknowledgement as time goes on.

Besides algebraic geometry, logic, and order theory it is desirable that presheaves should be used to reinterpret our understanding of computer science. Computation on the machine should be modeled by certain presheaves of memory locations, as this will produce the best results. So the presheaf perspective has the widest degree of applicability in different fields.

References:
Galois connection

The adjoint relationship between order and topology

The categories $Ord$ and $Top$ are the two most basic categories characterized by the adjoint relationships. The two categories $Ord$ and $Top$ are in turn adjointly related to one another, so this continues the basic theme of exploring adjoint relationships in category theory.

Theorem. let $f: (A,\tau_1) \to (B,\tau_2)$ be continuous then $Ord(f) : Ord(A) \to Ord(B)$ is a monotone map of specialization preorders.

Proof. the definition of the specialization preorder yields: \[a_1 \subseteq a_2 \Leftrightarrow \forall O \in \tau_1 : a_1 \in O \Rightarrow a_2 \in O\] We want that this would imply $f(a_1) \subseteq f(a_2)$. This will be demonstrated by using proof by contradiction. Suppose that $f(a_1) \not\subseteq f(a_2)$ then there exists $S$ such that $f(a_1) \in S$ and $f(a_2) \not\in S$. Then $f(a_1) \in S$ implies that $a_1 \in f^{-1}(S)$ and $a_2 \in f^{-1}(S)$ is logically equivalent to the condition that $f(a_2) \in S$ but we know that $f(a_2) \not\in S$ so $a_2 \not\in f^{-1}(S)$.

The inverse image of any open set is open, so $f^{-1}(S)$ is an open set, and it contains $a_1$ but not $a_2$ so it cannot be the case that $a_1 \in f^{-1}(S) \Rightarrow a_2 \in f^{-1}(S)$ which contradicts that $a_1 \subseteq a_2$. So by contradiction it cannot be the case that $f(a_1) \not= f(a_2)$ so $f(a_1) \subseteq f(a_2)$ which implies that $Ord(f) : Ord(A) \to Ord(B)$ is monotone. $\square$

Theorem. let $f: (A, \subseteq_A) \to (B, \subseteq_B)$ be a monotone map, then $f$ reflects upper sets.

Proof. let $I$ be an upper set of $B$ then consider $f^{-1}(I)$ and suppose that $a \in f^{-1}(I)$ then $f(a) \in I$ and now consider a $b$ with $a \subseteq b$. By monotonicity we have that $f(a) \subseteq f(b)$ and since $I$ is an upper set this implies that $f(b) \in I$. This in turn means that $b \in f^{-1}(I)$ so that $f^{-1}(I)$ is an upper set. $\square$

These two theorems are enough to construct an adjoint pair of functors from $Top$ to $Ord$, and these two theorems prove that these relationships are functorial.

• The specialization preorder functor: $P: Top \to Ord$ maps topologies to preorders.
• The Alexandrov topology functor: $T: Ord \to Top$ maps preorders to topologies.

Then these two functors define an adjoint relationship between order and topology. In particular, the Alexandrov topology is the largest topology with a given specialisation preorder. So the relationship $(P,\tau)$ which states that $P$ is a subpreorder of the specialisation preorder of $\tau$ is characterized by the monotone Galois connection $P(\tau) \subseteq P \Leftrightarrow \tau \subseteq T(P)$. So the relationship between preorders and topologies is governed by this adjoint pair of functors.

References:
Specialization order

The adjoint definition of monotonicity

A recent interest of mine is the ubiquity of adjoint relationships in mathematics, and the analysis of which categories are founded on adjoint relationships. The category $Ord$ of preorders and monotone maps is one example. We start by generalizing functions from taking values in points to taking values in preorders.

• Preorder image: let $f: A \to B$ be a function and let $\subseteq_R$ be a preorder on $A$ then define a preorder on $B$ by the preorder closure of $\{(f(x),f(y)): x \subseteq_R y\}$.
• Preorder inverse image: let $f: A \to B$ be a function and let $\subseteq_S$ be a preorder on $B$ then define a preorder on $A$ by $\{(a_1, a_2) : f(a_1) \subseteq_S f(a_2) \}$.

Then the interesting thing is that for any function $f: A \to B$ the definition of a monotonicity of $f$ with respect to two preorders can be defined by a monotone Galois connection expressed in terms of preorders on $A$ and $B$. In particular, for preorders $P$ on $A$ and $Q$ on $B$. \[ f(P) \subseteq Q \Leftrightarrow P \subseteq f^{-1}(Q) \Leftrightarrow \text{f is monotone} \] Every function $f: A \to B$ induces a dual pair of monotone maps $F: Ord(A) \to Ord(B)$ and $F^{-1} : Ord(B) \to Ord(A)$ from the lattices of preorders on $A$ to the lattice of preorders on $B$ which together form adjoint functors. The key realisation here is that preorders can be defined by the adjoint relationship between images/inverse images.

The preorder inverse image construction is particularly useful, because it induces an input preorder from an function to a preordered set. Consider the example of a set-valued function $f: A \to \mathcal{P}(B)$ then the preorder inverse image produces the familiar induced preorder on $A$. Similarly, for a ranking function $f: A \to \mathbb{N}$ this produces a preorder on $A$ by the size of its output numbers, and so on. So preorder images/inverse images are an important constructions in order theory, which can be described by adjoints.

References:
Galois connection
Adjoint functor

Adjoint definition of continuity

As category theory is basically the most fundamental object of mathematics, I am always looking for the most categorically appropriate way to define things. I have a new idea of a way of defining continuous maps of topological spaces $f: (X,\tau_1) \to (Y,\tau_2)$ which I think is really nice. Start by generalizing functions from taking values in sets to them taking values in topological spaces.

• Topological image: let $f: X \to Y$ be a function and let $\tau_1$ be a topology of $f$ then the topological image of $\tau_1$ is $f(\tau_1) = \{ U \subseteq Y : f^{-1}(U) \in \tau_1 \}$
• Topological inverse image: let $f: X \to Y$ be a function and let $\tau_2$ be a topology on $Y$ then the topological inverse image is $f^{-1}(\tau_2) = \{ f^{-1}(U) : U \in \tau_2 \}$.

Then if you recall the definition of a monotone galois connection, it states that $F: A \to B$ and $G: B \to A$ are monotone galois connections provided that: \[ F(a) \subseteq b \Leftrightarrow a \subseteq F(b) \] Let $f: A \to B$ be a function then its topological image and inverse image functions are monotone maps on the lattices of topological spaces of $A$ and $B$ with the topological image $f : Top(A) \to Top(B)$ and inverse image $f^{-1} : Top(B) \to Top(A)$ forming an adjoint pair. Then the if and only if condition is also the definition of continuity: \[ f(\tau_1) \subseteq \tau_2 \Leftrightarrow \tau_1 \subseteq f^{-1}(\tau_2) \Leftrightarrow \text{f is continuous} \] The key point is that the topological image and inverse image describe the extremal solutions to the continuity problem, and so they form an adjoint pair. We can now describe which functions of topological spaces are continuous and which topological spaces make a function continuous, so for example if we only have a topology on the input set we can get a topological on the output set using the topological image.

We can generalize the topological image and inverse image to families of functions to get the weakest topology that makes the family of functions continuous. So for example, in smooth manifolds and observables we define the topology on the dual space of an $\mathbb{R}$-algebra $F$ as the weakest topology that makes all $\mathbb{R}$-homomorphisms $m: F \to \mathbb{R}$ continuous. So these kinds of definitions where we need to form a minimal or maximal topology to make some set of functions continuous appears all the time, now we can give this concept its appropriate role.

Everything as much as possible should be defined in terms of adjoints like these, because by doing so you not only give a definition of something but also the way to compute its extremal solutions. So adjoints are one of the most fundamental objects of category theory, and I think at a later date I might elucidate how their fundamental importance extends beyond topology to almost every branch of math. But that is a discussion for another time.

References:
Galois connection
Adjoint functor

Monotone maps and Galois connections

Let $(P, \subseteq)$ and $(Q,\subseteq)$ be partially ordered sets and $f: (P, \subseteq) \to (Q,\subseteq)$ a function between them. Recall that a function is a one-to-one map between the lattices $Part(P)^d$ and $\mathcal{P}(Q)$. These are the lattices of subobjects and quotients of the topoi of sets. In the special case of functions between partial orders the equivalence classes and images of the function produce suborders. We will consider these suborders in the case of monotone maps in general and Galois connections in particular.

Maximal and minimal representatives:
The function $f : (P,\subseteq) \to (Q, \subseteq)$ induces an equivalence relation $x =_f y \Leftrightarrow f(x) = f(y)$. If the equivalence classes of $=_f$ are upper bounded suborders, then there is a maximal representative input that produces any given output. Dually, if the equivalence classes of $=_f$ are lower bounded suborders, then minimal representatives exist. It is also possible that both or neither exist. The existence of maximal and minimal representatives can be represented symbolically:

• Maximal representatives: $(F(a) = b) \Rightarrow (a \subseteq G(b))$
• Minimal representatives: $(F(a) = b) \Rightarrow (G(b) \subseteq a)$

Maximization produces an increasing idempotent action and minimization produces a decreasing idempotent action. For a given map between posets for which either process is possible, maximization and minimization don't necessarily have to be monotone. In the case which they are such as in a Galois connection then they form closure and interior operators.

Image suborders:
The image of $f : (P, \subseteq) \to (Q,\subseteq)$ is a suborder of $(Q, \subseteq)$. We can therefore classify monotone maps between partial orders based upon the properties of their image suborders. We say that a suborder is a Moore suborder if it has a closure operation and a Comoore suborder if it has an interior operation. These are the two special cases of interest in Galois connections.

Suppose that $f : (P, \subseteq) \to (Q,\subseteq)$ is a monotone map and we have $(F(a) \subseteq b) \Rightarrow (a \subseteq G(b))$. Then by monotonicity we have that $F(a) \subseteq F(G(b))$. Which proves that the $F$ image of $G(b)$ is greater then any other which is less then $b$. This means there must be on the images of $f$. Dually, if we have the same condition in the other direction there must be a closure operator on the images of $f$.

Overview:
There are three types of map associated to Galois connections: lower adjoints, upper adjoints, and polarities. Upper and lower adjoints are monotone and polarities are antitone. We can use the results proved thus far to describe the images and equivalence classes of each type of map:

• Lower adjoints:
  • Upper bounded equivalence classes
  • An interior operator of images
• Upper adjoints:
  • Lower bounded equivalence classes
  • A closure operator of images
• Polarities:
  • Upper bounded equivalence classes
  • A closure operator of images

A Galois connection is from a lower adjoint by taking the maximal representative of the largest image less then a given output value. For an upper adjoint it is determined by taking the minimal representative of the smallest image greater then a output value. Finally, for a polarity it is determined by the maximal representative of the closure of an output value. In this way, when Galois connections exist they are uniquely determined by each map.

For example, in algebraic geometry we saw that the antitone map $V: \wp(R[x,y,z,...]) \to \wp(\mathbb{A}^n)$ from any polynomial system to its algebraic set has upper bounded equivalence classes and its image has a closure operator. Therefore, V is a polarity in an antitone Galois connection. There are stronger properties, like that the images form a cotopology (the Zariski cotopology) and in the case of an algebraically closed field the maximal representatives are radical ideals.

As a function is a one-to-one map between its equivalence classes and its image, in order to construct a one-to-one restriction mapping of a function it is only necessary to get representatives of each equivalence class. In both types of Galois connection this can be achieved by selecting minimal and maximal representatives of a map. In the case of algebraic geometry, by Hilbert's nullstellensatz there is a one to one mapping between radical ideals and algebraic sets of a polynomial ring over an algebraically closed field.

Suprema and infima:
The purpose of this post is to compile all the relevant aspects of the monotone maps of a Galois connection, rather then considering the connections themselves. There is one more property worth considering and that is the relationship between maps and suprema/infima:

• Lower adjoints preserve suprema
• Upper adjoints preserve infima

Order theory and category theory comparison:
Almost everything in category theory is a slight variant of something older in order theory. One reason to consider Galois connections then, is their relationship to category theoretic adjoints. In that case, the most important property is that lower adjoints preserve colimits and upper adjoints preserve limits. An example of relevance to algebraic-geometry is the tensor-hom adjunction. There we see that the tensor product is a lower adjoint and so it preserves colimts and the hom is an upper adjoint so it preserves limits. The limit/colimit preserving conditions for adjoint functors correspond to the suprema/infima preserving conditions of Galois connections.