Marching From Galois Connections to Adjunctions. Part 4.

To make the transition from Galois connections to adjoint functors we make a slight change of notation. The change is only cosmetic but it is very important for our intuition.

Definition of Poset Adjunction. Let (P, ≤P) and (Q, ≤Q) be posets. A pair of functions L ∶ P ⇄ Q ∶ R is called an adjunction if ∀ p ∈ P and q ∈ Q we have

p ≤_P R(q) ⇐⇒ L(p) ≤_Q q

In this case we write L ⊣ R and call this an adjoint pair of functions. The function L is the left adjoint and R is the right adjoint.

The only difference between Galois connections and poset adjunctions is that we have reversed the partial order on Q. To be precise, we define the opposite poset Q^op with the same underlying set Q, such that for all q₁ , q₂ ∈ Q we have

q₁ ≤ _Q^op q₂ ⇐⇒ q₂ ≤_Q q₁

Then an adjunction P ⇄ Q is just the same thing as a Galois connection P ⇄ Q^op.

However, this difference is important because it breaks the symmetry. It also prepares us for the notation of an adjunction between categories, where it is more common to use an “asymmetric pair of covariant functors” as opposed to a “symmetric pair of contravariant functors”.

Uniqueness of Adjoints for Posets: Let P and Q be posets and let L ∶ P ⇄ Q ∶ R be an adjunction. Then each of the adjoint functions L ⊣ R uniquely determines the other.

Proof: To prove that R determines L, suppose that L′ ∶ P ⇄ Q ∶ R is another adjunction. Then by definition of adjunction we have for all q ∈ Q that

L(p) ≤_Q q ⇐⇒ p ≤_P R(q) ⇐⇒ L′(p) ≤_Q q

In particular, setting q = L(p) gives

L(p) ≤_Q L(p) ⇒ L′(p) ≤_Q L′(p)

and setting q = L′(p) gives

L′(p) ≤_Q L(p) ⇒ L(p) ≤_Q L′(p)

Then by the antisymmetry of ≤_Q we have L(p) = L′(p). Since this holds for all p ∈ P we conclude that L = L′, as desired.

RAPL Theorem for Posets. Let L ∶ P ⇄ Q ∶ R be an adjunction of posets. Then for all subsets S ⊆ P and T ⊆ Q we have

L (∨_P S) = ∨_Q L(S) and R (∧_Q T) = ∧_P R(T).

In words, this could be said as “left adjoints preserve join” and “right adjoints preserve meet”.

Proof: We just have to observe that sending Q to its opposite Qop switches the definitions of join and meet: ∨_Q^op = ∧_Q and ∧_Q^op = ∨_Q.

It seems worthwhile to emphasize the new terminology with a picture. Suppose that the posets P and Q have top and bottom elements: 1_P , 0_P ∈ P and 1_Q, 0_Q ∈ Q. Then a poset adjunction L ∶ P ⇄ Q ∶ R looks like this:

In this case RL ∶ P → P is a closure operator as before, but now LR ∶ Q → Q is called an interior operator. From the case of Galois connections we also know that LRL = L and RLR = R. Since bottom elements are colmits and top elements are limits, the identities L(0_P ) = 0_Q and R(1_Q) = 1_P are special cases of the RAPL Theorem.

Just as with Galois connections, adjunctions between the Boolean lattices 2^U and 2^V are in bijection with relations ∼ ⊆ U × V, but this time we will view the relation ∼ as a function f ∼ ∶ U → 2^V that sends each to the set f ∼ (u)∶= {v∈V ∶ u∼v}. We can also think off ∼ as a “multi-valued function” from U to V.

Adjunctions of Boolean Lattices: Let U,V be sets and consider an arbitrary function f ∶ U → 2^V. Then ∀ subsets S ∈ 2^U and T ∈ 2^V we define

L_f (S) ∶= ∪_s∈S f(s) ∈ 2^V,

R_f (T) ∶= {u∈U ∶ f(u) ⊆ T} ∈ 2^U

The pair of functions L_f ∶ 2^U ⇄ 2^V ∶ R_f is an adjunction of Boolean lattices. To see this, note ∀ S ∈ 2^U and T ∈ 2^V

S ⊆ R_f (T) ⇐⇒ ∀ s∈S, s ∈ R_f (T)

⇐⇒ ∀ s∈S, f(s) ⊆ T

⇐⇒ ∪_s∈S f(s) ⊆ T

⇐⇒ L_f (S) ⊆ T

Functions : Let f ∶ U → V be any function. We can extend this to a function f ∶ U → 2^V by defining f(u) ∶= {f(u)} ∀ u ∈ U. In this case we denote the corresponding left and right adjoint functions by f_∗ ∶= L_f ∶ 2^U → 2^V and f₋₁ ∶= R_f ∶ 2^V → 2^U, so that ∀ S ∈ 2^U and T ∈ 2^V we have

f_∗(S) = {f(s) ∶ s ∈ S}, f⁻¹(T)={u∈U ∶ f(s) ∈ T}

The resulting adjunction f_∗ ∶ 2^U ⇄ 2^V ∶ f⁻¹ is called the image and preimage of the function. It follows from RAPL that image preserves unions and preimage preserves intersections.

But now something surprising happens. We can restrict the preimage f⁻¹ ∶ 2^V → 2^U to a function f⁻¹ ∶ V → 2^U by defining f⁻¹(v) ∶= f⁻¹({v}) for each v ∈ V. Then since f⁻¹ = Lf⁻¹ we obtain another adjunction

f⁻¹ ∶ 2^V ⇄ 2^U ∶ Rf⁻¹,
where this time f⁻¹ is the left adjoint. The new right adjoint is defined for each S ∈ 2^U by

R f⁻¹(S) = {v∈V ∶ f⁻¹(v) ⊆ S}

There seems to be no standard notation for this function, but people call it f_! ∶= Rf⁻¹ (the “!” is pronounced “shriek”). In summary, each function f ∶ U → V determines a triple of

adjoints f_∗ ⊣ f⁻¹ ⊣ f_! where f_∗ preserves unions, f_! preserves intersections, and f⁻¹ preserves both unions and intersections. Logicians will tell you that the functions f_∗ and f_! are closely related to the existential (∃) and universal (∀) quantifiers, in the sense that for all S ∈ 2^U we have

f_∗ (S) = {v∈V ∶ ∃ u ∈ f⁻¹ (v), u ∈ S}, f_! (S)={v ∈ V ∶ ∀ u ∈ f⁻¹(v), u ∈ S}

Group Homomorphisms: Given a group G we let (L (G), ⊆) denote its poset of subgroups. Since the intersection of subgroups is again a subgroup, we have ∧ = ∩. Then since L (G) has arbitrary meets it also has arbitrary joins. In particular, the join of two subgroups A, B ∈ L (G) is given by

A ∨ B = ⋂ {C ∈ L(G) ∶ A ⊆ C and B ⊆ C},

which is the smallest subgroup containing the union A ∪ B. Thus L (G) is a lattice, but since A ∨ B ≠ A ∪ B (in general) it is not a sublattice of 2^G.

Now let φ ∶ G → H be an arbitrary group homomorphism. One can check that the image and preimage φ_∗ ∶ 2^G ⇄ 2^H ∶ φ⁻¹ send subgroups to subgroups, hence they restrict to an adjunction between subgroup lattices:

φ_∗ ∶L(G) ⇄ L(H)∶ φ⁻¹.

The function φ_! ∶ 2^G → 2^H does not send subgroups to subgroups, and in general the function φ⁻¹ ∶ L(H) → L(G) does not have a right adjoint. For all subgroups A ∈ L (G) and B ∈ L (H) one can check that

φ⁻¹φ_∗(A)=A ∨ ker φ and φ_∗φ⁻¹(B) = B ∧ im φ

Thus the φ⁻¹φ_∗-fixed subgroups of G are precisely those that contain the kernel and the φ_∗φ⁻¹-fixed subgroups of H are precisely those contained in the image. Finally, the Fundamental Theorem gives us an order-preserving bijection as in the following picture:

…..

Advertisement

Teleology versus Purpose. Drunken Risibility.

Does the universe has any purpose whatsoever? Scientific and materialist ontologies have always prided themselves (in the modern sense of time) on the efficiency of causation rather than on the finality of causation. As was written many many posts ago, the quantum entanglement is smart enough to dupe us into accepting quasi-causation, or from the future, it is possible to determine the past, or more strictly, future determines the past. These physical determinations are always being apprehended under the garb of speculations, and if wants to get even with efficient and final causation, the very jargon teleology needs to be crafted accordingly. One way is to distinguish between the teleology and purpose with some conscious goal in mind. other is to look seriously at Peircean semiotic realism, where both efficient and final causation are within the legal ambit of being accepted.

… the non-recognition of final causation … has been and still is productive of more philosophical error and nonsense than any or every other source of error or nonsense . If there is any goddess of nonsense , this must be her haunt. — CSP

Galois Connections. Part 3.

Let (P,≤P) and (Q,≤Q) be posets, and consider two set functions ∗ ∶ P ⇄ Q ∶ ∗. We will denote these by p ↦ p ∗ and q ↦ q ∗ for all p ∈ P and q ∈ Q. This pair of functions is called a Galois connection if, for all p ∈ P and q ∈ Q, we have

p ≤ P q ∗ ⇐⇒ q ≤ Q p  ∗

Let ∗ ∶ P ⇄ Q ∶ ∗ be a Galois connection. For all elements x of P or Q we will use the notations x ∗ ∗ ∶= (x ∗)∗ and x ∗ ∗ ∗ ∶= (x ∗ ∗)∗.

(1) For all p ∈ P and q ∈ Q we have

p ≤ P p ∗ ∗ and q ≤ Q q ∗ ∗.

(2) For all elements p1, p2 ∈ P and q1, q2 ∈ Q we have

p1 ≤ P p2 ⇒ p ∗ 2 ≤ Q p ∗ 1 and q1 ≤ Q q2 ⇒ q2 ∗ ≤ P q1 ∗.

(3) For all elements p ∈ P and q ∈ Q we have

p ∗ ∗ ∗ = p ∗ and q ∗ ∗ ∗ = q ∗

Proof:

Since the definition of a Galois connection is symmetric in P and Q, we will simplify the proof by using the notation

x ≤ y ∗ ⇐⇒ y ≤ x ∗

for all elements x,y such that the inequalities make sense. To prove (1) note that for any element x we have x ∗ ≤ x ∗ by the reflexivity of partial order. Then from the definition of Galois connection we obtain,

(x ∗) ≤ (x) ∗ ⇒ (x) ≤ (x ∗) ∗ ⇒ x ≤ x ∗ ∗

To prove (2) consider elements x, y such that x ≤ y. From (1) and the transitivity of partial x ≤ y ≤ y ∗ ∗ ⇒ x ≤ y ∗ ∗. Then from the definition of Galois connection we obtain

(x) ≤ (y ∗) ∗ ⇒ (y ∗) ≤ (x) ∗ ⇒ y ∗ ≤ x ∗.

To prove (3) consider any element x. On the one hand, part (1) tells us that

(x ∗) ≤ (x ∗) ∗ ∗ ⇒ x ∗ ≤ x ∗ ∗ ∗.

On the other hand, part (1) tells us that x ≤ x ∗ ∗ and then part (2) says that

(x) ≤ (x ∗ ∗) ⇒ (x ∗ ∗) ∗ ≤ (x) ∗ ⇒ x ∗ ∗ ∗ ≤ x ∗

Finally, the antisymmetry of partial order says that x∗∗∗ = x∗, which we interpret as isomorphism of objects in the poset category. The following definition captures the essence of these three basic properties.

Definition of Closure in a Poset. Given a poset (P,≤), we say that a function cl ∶ P → P is a closure operator if it satisfies the following three properties:

(i) Extensive: ∀p ∈ P, p ≤ cl(p)

(ii) Monotone: ∀ p,q ∈ P, p ≤ q ⇒ cl(p) ≤ cl(q)

(iii) Idempotent: ∀ p ∈ P, cl(cl(p)) = p.

[Remark: If P = 2^U is a Boolean lattice, and if the closure cl ∶ 2^U → 2^U also preserves finite unions, then we call it a Kuratowski closure. Kuratowski proved that such a closure is equivalent to a topology on the set U.]

If ∗ ∶ P → Q ∶ ∗ is a Galois connection, then the basic properties above immediately imply that the compositions ∗ ∗ ∶ P → P and ∗ ∗ ∶ Q → Q are closure operators.

Proof: Property (ii) follows from applying property (2) twice and property (iii) follows from applying ∗ to property (3).

Fundamental Theorem of Galois Connections: Any Galois connection ∗ ∶ P ⇄ Q ∶ ∗ determines two closure operators ∗ ∗ ∶ P → P and ∗ ∗ ∶ Q → Q. We will say that the element p ∈  P (resp. q ∈  Q) is ∗ ∗-closed if p∗ ∗ = p (resp. q∗ ∗ = q). Then the Galois connection restricts to an order-reversing bijection between the subposets of ∗ ∗-closed elements.

Proof: Let Q ∗ ⊆ P and P ∗ ⊆ Q denote the images of the functions ∗ ∶ Q → P and ∗ ∶ P  → Q, respectively. The restriction of the connection to these subsets defines an order-reversing bijection:

Indeed, consider any p ∈ Q ∗, so that p = q ∗ for some q ∈ Q. Then by properties (1) and (3) of Galois connections we have

(p) ∗ ∗ = (q ∗) ∗ ∗ ⇒ p ∗ ∗ = q ∗ ∗ ∗ ⇒ p ∗ ∗ = q ∗ ⇒ p ∗ ∗ = p

Similarly, for all q ∈ P ∗ we have q ∗ ∗ = q. The bijections reverse order because of property (2).

Finally, note that Q ∗ and P ∗ are exactly the subsets of ∗ ∗-closed elements in P and Q, respectively. Indeed, we have seen above that every element of Q ∗ is ∗ ∗-closed. Conversely, if p ∈ P is ∗ ∗-closed then we have

p = p ∗ ∗ ⇒ p = (p ∗) ∗,

and it follows that p ∈ Q ∗. Similarly, every element of P ∗ is ∗ ∗-closed.

Thus, a Galois connection is something like a “loose bijection”. It’s not necessarily a bijection but it becomes one after we “tighten it up”. Sort of like tightening your shoelaces.

The shaded subposets here consist of the ∗ ∗-closed elements. They are supposed to look (anti-) isomorphic. The unshaded parts of the posets get “tightened up” into the shaded subposets. Note that the top elements are ∗ ∗-closed. Indeed, property (2) tells us that 1_P ≤ P ≤ 1_p^∗∗ and then from the universal property of the top element we have 1_P^** = 1_P. Since the left hand side is always true, so is the right hand side. But then from the universal property of the top element in Q we conclude that 0^∗_P = 1_Q. As a consequence of this, the arbitrary meet of ∗ ∗-closed elements (if it exists) is still ∗ ∗-closed. We will see, however, that the join of ∗ ∗-closed elements is not necessarily ∗ ∗-closed. And hence not all Galois connections induce topologies.

Galois connections between Boolean lattices have a particularly nice form, which is closely related to the universal quantifier “∀“. Galois Connections of Boolean Lattices. Let U,V be sets and let ∼ ⊆ U × V be any subset (called a relation) between U and V . As usual, we will write “u ∼ v” in place of the statement “(u,v) ∈ ∼“, and we read this as “u is related to v“. Then for all S ∈ 2^U and T ∈ 2^V we define,

S^∼ ∶= {v ∈ V ∶ ∀ s ∈ S, s ∼ v} ∈ 2^V,

T^∼ ∶= {u ∈ U ∶ ∀ t ∈ T , u ∼ t} ∈ 2^U

The pair of functions S ↦ S^∼ and T ↦ T^∼ is a Galois connection, ∼ ∶ 2^U ⇄ 2^V ∶ ∼.

To see this, note that ∀ subsets S ∈ 2^U and T ∈ 2^V we have

S ⊆ T^∼ ⇐⇒ ∀ s ∈ S, s ∈ T^∼

⇐⇒ ∀ s ∈ S,∀ t ∈ T, s ∼ t

⇐⇒ ∀ t ∈ T, ∀ s ∈ S, s ∼ t

⇐⇒ ∀ t ∈ T, t ∈ S^∼

⇐⇒ T ⊆ S^∼.

Moreover, one can prove that any Galois connection between 2^U and 2^V arises in this way from a unique relation.

Orthogonal Complement: Let V be a vector space over field K and let V ∗ be the dual space, consisting of linear functions α ∶ V → K. We define the relation ⊥ ⊆ V ∗ × V by

α ⊥ v ⇐⇒ α(v) = 0.

The resulting ⊥⊥-closed subsets are precisely the linear subspaces on both sides. Thus the Fundamental Theorem of Galois Connections gives us an order-reversing bijection between the subspaces of V ∗ and the subspaces of V.

Convex Complement: Let V be a Euclidean space, i.e., a real vector space with an inner product ⟨-,-⟩ ∶ V ×V → ℜ. We define the relation ∼ ⊆ V ×V by

u ∼ v ⇐⇒ ⟨u,v⟩ ≤ 0.

∀ S ⊆ V the operation S ↦ S ∼ ∼ gives the cone genrated by S, thus the ∼ ∼-closed sets are precisely the cones. Here is a picture:

Original Galois Connection: Let L be a field and let G be a finite group of automorphisms of L, i.e., each g ∈ G is a function g ∶ L → L preserving addition and multiplication. We define a relation ∼ ⊆ G × L by

g ∼ l ⇐⇒ g(l) = l.

Define K ∶= L ∼ to be the “subfield fixed by G“. The original Fundamental Theorem of Galois Theory says that the ∼ ∼-closed subsets of G are precisely the subgroups and the ∼ ∼-closed subsets of L are precisely the subfields containing K.

Hilbert’s Nullstellensatz: Let K be a field and consider the ring of polynomials K[x] ∶= K[x₁,…,x_n] in n commuting variables. For each polynomial f(x) ∶= f(x₁,…,x_n) ∈ K[x] and for each n-tuple of field elements α ∶= (α₁,…,α_n) ∈ Kn, we denote the evaluation by f(α) ∶= f(α₁,…,α_n) ∈ K. Now we define a relation ∼ ⊆ K[x] × Kn by

f(x) ∼ α ⇐⇒ f(α) = 0

By definition, the closure operator ∼ ∼ on subsets of Kn is called the Zariski closure. It is not difficult to prove that it satisfies the additional property of a Kuratowski closure (i.e., finite unions of closed sets are closed) and hence it defines a topology on Kn, called the Zariski topology. Hilbert’s Nullstellensatz says that if K is algebraically closed, then the ∼ ∼-closed subsets of K[x] are precisely the radical ideals (i.e., ideals closed under taking arbitrary roots).