The Ubiquity of Self-Predicative Universality of Adjoint Functors. Note Quote.

neuron_istock_ktsimage2.jpg.1280x720_q85_box-54,0,822,432_upscale

One of the most important and beautiful notions in category theory is the notion of a pair of adjoint functors. The developers of category theory, Saunders MacLane and Samuel Eilenberg, famously said that categories were defined in order to define functors, and functors were defined in order to define natural transformations. Adjoints were defined more than a decade later by Daniel Kan but the realization of their ubiquity (“Adjoint functors arise everywhere” (MacLane) and their foundational importance has steadily increased over time (Lawvere). Now it would perhaps not be too much of an exaggeration to see categories, functors, and natural transformations as the prelude to defining adjoint functors. The notion of adjoint functors includes all the instances of self-predicative universal mapping properties discussed above. As Steven Awodey (179) put it:

The notion of adjoint functor applies everything that we have learned up to now to unify and subsume all the different universal mapping properties that we have encountered, from free groups to limits to exponentials. But more importantly, it also captures an important mathematical phenomenon that is invisible without the lens of category theory. Indeed, I will make the admittedly provocative claim that adjointness is a concept of fundamental logical and mathematical importance that is not captured elsewhere in mathematics.

“The isolation and explication of the notion of adjointness is perhaps the most profound contribution that category theory has made to the history of general mathematical ideas.” (Goldblatt)

How do the ubiquitous and important adjoint functors relate to theme of self- predicative universals? MacLane and Birkhoff succinctly state the idea of the self-predicative universals of category theory and note that adjunctions can be analyzed in terms of those universals. The construction of a new algebraic object will often solve a specific problem in a universal way, in the sense that every other solution of the given problem is obtained from this one by a unique homomorphism. The basic idea of an adjoint functor arises from the analysis of such universals. (MacLane and Birkhoff)

We will use a specific novel treatment of adjunctions (Ellerman) that shows they arise by gluing together in a certain way two universal constructions or self-predicative universals (“semi-adjunctions”). But for illustration, we will stay within the methodological restriction of using examples from partial orders (where adjunctions are called “Galois connections”).

We have been working within the inclusion partial order on the set of subsets ζ(U) of a universe set U. Consider the set of all ordered pairs of subsets <a,b> from the Cartesian product ζ(U) x ζ(U) where the partial order (using the same symbol) is defined by pairwise inclusion. That is, given the two ordered pairs <a’, b’> and <a,b>, we define

<a’,b’> ⊆ <a,b> if a ⊆’  a and b ⊆’  b.

Order-preserving maps can be defined each way between these two partial orders. From ζ(U) to ζ(U) x ζ(U), there is the diagonal map Δ(x) = <x,x>, and from ζ(U) x ζ(U) to ζ(U), there is the meet map ∩(<a,b>)  = a ∩ b. Consider now the following “adjointness relation” between the two partial orders:

Δ(c) ⊆ <a,b> iff c ⊆ ∩ (<a,b>) Adjointness Equivalence

for sets a, b, and c in ζ(U). It has a certain symmetry that can be exploited. If we fix <a,b>, then we have the previous universality condition for the meet of a and b: for any c in ζ(U), c ⊆ a ∩ b iff Δ(c) ⊆ <a,b> Universality Condition for Meet of Sets a and b.

The defining property on elements c of ζ(U) is that Δ(c) ⊆ <a,b>. But using the symmetry, we could fix c and have another universality condition using the reverse inclusion in ζ(U) x ζ(U) as the participation relation: for any <a,b> in ζ(U) x ζ(U), <a,b> ⊇ Δ(c) iff c ⊆ a ∩  b. Universality Condition for Δ(c). Here the defining property on elements <a,b> of ζ(U) x ζ(U) is that “the meet of a and b is a superset of the given set c.” The self-predicative universal for that property is the image of c under the diagonal map Δ(c) = <c,c>, just as the self-predicative universal for the other property defined given <a,b> was the image of <a,b> under the meet map ∩(<a,b>) = a ∩ b.

Thus in this adjoint situation between the two categories ζ(U) and ζ(U) x ζ(U), we have a pair of maps (“adjoint functors”) going each way between the categories such that each element in a category defines a certain property in the other category and the map carries the element to the self-predicative universal for that property.

Δ: ζ(U) → ζ(U) x ζ(U) and ∩: ζ(U) x ζ(U) → ζ(U) Example of Adjoint Functors Between Partial Orders

The notion of a pair of adjoint functors is ubiquitous; it is one of the main tools that highlights self-predicative universals throughout modern mathematics.

Advertisement

Functors. Part 5.

We have called L ∶ P ⇄ Q ∶ R an adjoint pair of functions, but of course they more than just functions. If L ⊣ R is an adjunction, then property (2) of Galois connections says that ∀ p1, p2 ∈ P and q1, q2 ∈ Q we have

p1 ≤ P p2 ⇒ L(p1) ≤ Q L(p2) and q1 ≤ Q q2 ⇒ R(q1) ≤ P R(q2)

That is, the functions L ∶ P → Q and R ∶ Q → P are actually homomorphisms of posets.

Definition of Functor: Let C and D be categories. A functor F ∶ C → D consists a family of functions:

• A function on objects F ∶ Obj(C) → Obj(D),

• For each pair of objects c1, c2 ∈ C a function on hom sets:

F ∶ HomC(c1,c2) → HomD(F(c1),F(c2)). These functions must preserve the category structure:

(i) Identity: For all objects c ∈ C we have F (idc) = idF(c).

(ii) Composition: For all arrows α, β ∈ C such that β ○ α is defined, we have

F (β ○ α) = F (β) ○ F (α)

Functors compose in an associative way, and for each category C there is a distinguished identity functor idC ∶ C → C. In other words, the collection of all categories with functors between them forms a (very big) category, which we denote by Cat.

This definition is not surprising. It basically says that a functor F ∶ C → D sends commutative diagrams in C to commutative diagrams in D. That is, for each diagram D ∶ I → C in C we have a diagram FI(D) ∶ I → D in D (defined by FI(D) ∶= F ○ D), which is commutative if and only if D is.

Now let’s try to guess the definition of an “adjunction of categories”. Let C and D be categories and let L ∶ C ⇄ D ∶ R be any two functors. When C is a poset, recall that ∀ x, y ∈ C we have ∣HomC (x, y)∣ ∈ {0, 1} and we use the notations

x ≤ y ⇐⇒ ∣HomC(x,y)∣ = 1

x ≤/ y ⇐⇒ ∣HomC(x,y)∣ = 0

Thus if C and D are posets, we can rephrase the definition of a poset adjunction L ∶ C ⇄ D ∶ R by stating that ∀ objects c ∈ C and d ∈ D there exists a bijection of hom sets:

HomC (c, R(d)) ←→ HomD (L(d), c)

In this form the definition now applies to any pair of functors between categories.

However, if we want to preserve the important theorems (uniqueness of adjoints and RAPL) then we need to impose some “naturality” condition on the family of bijections between hom sets. This condition is automatic for posets, so we will have to look elsewhere for motivation.

Adjoint Functors: 

Let C and D be categories. We say that a pair of functors L ∶ C ⇄ D ∶ R is an adjunction if for all objects c ∈ C and d ∈ D there exists a bijection of hom sets

HomC (c, R(d)) ←→ HomD (L(d), c)

Furthermore, we require that these bijections fit together in the following “natural” way. For each arrow γ ∶ c2 → c1 in C and each arrow δ ∶ d1 → d2 in D we require that the following cube of functions commutes:

img_20170205_125111

Natural Transformation: 

Let C and D be categories and consider two parallel functors F1,F2 ∶ C → D. A natural transformation Φ ∶ F ⇒ G consists of a family of arrows Φc ∶F(c) → R(c), one for each object c ∈ C, such that for each arrow γ ∶ c1 → c2 in C the following square commutes:

img_20170205_125815

The figure below the square is called a “2-cell diagram”. It hints at the close relationship between category theory and topology.

Let DC denote the collection of all functors from C to D and natural transformations between them. One can check that this forms a category (called a functor category). Given F1, F2 ∈ DC we say that F1 and F2 are naturally isomorphic if they are isomorphic in DC, i.e., if there exists a pair of natural transformations Φ ∶ F1 ⇒ F2 and Ψ ∶ F2 ⇒ F1 such that Ψ ○ Φ = idF1 and Ψ ○ Φ = idF2 are the identity natural transformations. In this case we will write F1 ≅ F2 and we will say that Φ and Φ−1 ∶= Ψ are natural isomorphisms.

To develop some intuition for this definition, let I be a small category and let C be any category. We have previously referred to functors D ∶ I → C as “diagrams of shape I in C“. Now we can think of CI as a category of diagrams. Given two such diagrams D1, D2 ∈ CI , we visualize a natural transformation Φ ∶ D1 ⇒ D2 as a “cylinder”:

img_20170205_131311

The diagrams D1 and D2 need not be commutative, but if they are then the whole cylinder is commutative.

Limit/Colimit: 

Consider a diagram D ∶ I → C. The limit of D, if it exists, consists of an object limID ∈ C and a canonical natural transformation Λ ∶ (limID)I ⇒ D such that for each object c ∈ C and natural transformation Φ ∶ cI ⇒ D there exists a unique natural transformation υI ∶ cI ⇒ (limID)I making the following diagram in CI commute:

img_20170205_133433

Hom Functors:

Let C be a category. For each object c ∈ C the mapping d ↦ HomC(c, d) defines a functor from C to the category of sets Set. We denote it by

Hc ∶= HomC(c,−) ∶ C → Set

To define the action of Hc on arrows, consider any δ ∶ d1 → d2 in C. Then we must have a function Hc(δ) ∶ Hc(d1) → Hc(d2), i.e., a function Hc(δ) ∶ HomC(c,d1) → HomC(c,d2). There is only one way to define this:

H(δ) (φ) ∶= δ ○ φ

Similarly, for each arrow δ ∶ c1 → c2 we can define a function Hc(δ) ∶ HomC(d2,c) → HomC(d1,c) by H(δ) (φ) ∶= φ ○ δ. This again defines a functor into sets, but this time it is from the opposite category Cop (which is defined by reversing all arrows in C):

Hc ∶= HomC(−,c) ∶ Cop → Set

Finally, we can put these two functors together to obtain the hom bifunctor

HomC(−,−)∶ Cop ×C →Set 

which sends each pair of arrows (γ ∶ c2 → c1, δ ∶ d1 → d2) to the function

HomC(γ,δ) ∶ HomC(c1,d1) → HomC(c2,d2)

defined by φ ↦ δ ○ φ ○ γ. The product category Cop × C is defined in the most obvious way.

Adjoint Functors: 

Let C, D be categories and consider a pair of functors L ∶ C ⇄ D ∶ R. By composing these with the hom bifunctors HomC (−, −) and HomD (−, −) we obtain two parallel bifunctors:

HomC(−,R(−))∶ Cop × D → Set and HomD(L(−),−)∶ Cop × D → Set 

We say that L ∶ C ⇄ D ∶ R is an adjunction if the two bifunctors are naturally isomorphic:

HomC (−, R(−))HomD (L(−), −)……..

 

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 Qop with the same underlying set Q, such that for all q1 , q2 ∈ Q we have

q1Qop q2 ⇐⇒ q2Q q1

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

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: Qop = ∧Q and Qop = ∨Q.

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

img_20170204_163208

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(0P ) = 0Q and R(1Q) = 1P are special cases of the RAPL Theorem.

Just as with Galois connections, adjunctions between the Boolean lattices 2U and 2V are in bijection with relations ∼ ⊆ U × V, but this time we will view the relation as a function f ∼ ∶ U → 2V 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 → 2V. Then subsets S ∈ 2U and T ∈ 2V we define

L(S) ∶= ∪s∈S f(s) ∈ 2V,

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

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

S ⊆ Rf (T) ⇐⇒ ∀ s∈S, s ∈ R(T)

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

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

⇐⇒ L(S) ⊆ T

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

f(S) = {f(s) ∶ s ∈ S}, f−1(T)={u∈U ∶ f(s) ∈ T}

The resulting adjunction f ∶ 2U ⇄ 2V ∶ f−1 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−1 ∶ 2V → 2U to a function f−1 ∶ V → 2U by defining f−1(v) ∶= f−1({v}) for each v ∈ V. Then since f−1 = Lf−1 we obtain another adjunction

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

R f−1(S) = {v∈V ∶ f−1(v) ⊆ S}

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

adjoints f ⊣ f−1 ⊣ f! where f preserves unions, f! preserves intersections, and f−1 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 ∈ 2U we have

f∗ (S) = {v∈V ∶ ∃ u ∈ f−1 (v), u ∈ S}, f(S)={v ∈ V ∶ ∀ u ∈ f−1(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 2G.

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

φ ∶L(G) ⇄ L(H)∶ φ−1.

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

φ−1φ(A)=A ∨ ker φ and φφ−1(B) = B ∧ im φ

Thus the φ−1φ-fixed subgroups of G are precisely those that contain the kernel and the φφ−1-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:

img_20170204_173156

…..

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 = 2U is a Boolean lattice, and if the closure cl ∶ 2U → 2U 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:

img_20170204_065156

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.

img_20170204_071135

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 1P ≤ P ≤ 1p∗∗ and then from the universal property of the top element we have 1P** = 1P. 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 0P = 1Q. 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 ∈ 2U and T ∈ 2V we define,

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

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

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

To see this, note that ∀ subsets S ∈ 2U and T ∈ 2V 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 2U and 2V 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:

img_20170204_075300

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[x1,…,xn] in n commuting variables. For each polynomial f(x) ∶= f(x1,…,xn) ∈ K[x] and for each n-tuple of field elements α ∶= (α1,…,αn) ∈ Kn, we denote the evaluation by f(α) ∶= f(α1,…,α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).