RAPL (Right Adjoint Preserve Limits) Theorem. Part 8b/End Part.

Fix a small category I and a diagram D ∶ I → C of shape I. Then the limit of D, if it exists, consists of an object l ∈ C and a natural isomorphism

Cone ∶ HomC(−,l) ≅ HomCI((−)I,D) ∶ Uni

in the category SetCop.

This is intuitively plausible if we recall the definition of limits. Recall that a cone under D consists of an object l ∈ C and a natural transformation Λ ∶ lI ⇒ D. We say that the cone (l,Λ) is the the limit of D if, for any other cone Φ ∶ cI ⇒ D, there exists a unique arrow υ ∶ c → l making the following diagram in CI commute:

img_20170214_201951_hdr

The map sending the cone Φ ∶ cI ⇒ D to the unique arrow υ ∶ c → l is the desired function HomCI (cI,D) → HomC(c,l). Furthermore, it’s clear that this function is a bijection since we can pull back any arrow α ∶ c → l to the cone Λ ○ αI ∶ cI ⇒ D. The main difficulty is to show that the data of naturality for these bijections is equivalent to the data of the canonical cone Λ ∶ lI ⇒ D.

Proof: First assume that the limit of D exists and is given by the cone (limID,Λ). In this case we want to define a family of bijections

Unic ∶HomcI(cI,D) →~ Hom (c,limID)

that is natural in c ∈ Cop. (Then the inverse Cone ∶= Uni−1 is automatically natural. So consider any element Φ ∈ HomCI(cI,D), i.e., any cone Φ ∶ cI ⇒ D. By the definition of limits we know that there exists a unique arrow υ ∶ c → limID making the following diagram commute:

img_20170214_203133_hdr

Therefore the assignment Unic(Φ) ∶= υ defines an injective function (recall that the functor (−)I is faithful, so that υ1I = υ2I implies υ1 = υ2). To see that Unic is surjective, consider any arrow α ∶ c → limID in C. We want to define a cone Φα ∶ cI ⇒ D with the property that Unicα) = α. By definition of Unic this means that we must have Φα ∶= Λ ○ αI — in other words, we must have α)i ∶= Λi ○ α indices i ∈ I. And note that this does define a natural transformation Φα ∶ cI ⇒ D since for all arrows δ ∶ i ∈ j in I we have

D(δ) ○ (Φα)i =D(δ) ○ (Λi ○ α)

= (D(δ) ○ Λi) ○ α

= Λj ○ α (Naturality of Λ)

= (Φα)j

We conclude that Unic is a bijection. To see that Unic is natural in c ∈ Cop, consider any arrow γ ∶ c1 → c2 in C (i.e., any arrow γ ∶ c2 → c1 in C). We want to show that the following diagram commutes:

img_20170214_204617

And to see this, consider any cone Φ ∶ cI1 ⇒ D. By composing with the natural transformation γI ∶ cI2 ⇒ cI1 we obtain the following commutative diagram in CI:

img_20170214_205052_hdr

Since the diagonal embedding (−)I ∶ C → CI is a functor, the bottom arrow is given by

(Unic1 (Φ))I ○ γI = (Unic1 (Φ) ○ γ)I

But by the definition of the function Unic2 this arrow also equals (Unic2(Φ ○ γI))I

Then since (−)I is a faithful functor we conclude that

Unic2 (Φ ○ γI) = Unic1 (Φ) ○ γ

and hence the desired square commutes. Conversely, consider an object l ∈ C and suppose that we have a bijection

Conec ∶HomC(c,l) ←→ HomCI(cI,D) ∶ Unic

that is natural in c ∈ Cop. In other words, suppose that for each arrow γ ∶ c1 → c2 in Cop (i.e., for each arrow γ ∶ c2 → c1 in C) we have a commutative square:

img_20170214_210335_hdr

We want to show that this determines a unique cone Λ ∶ lI ⇒ D such that (l, Λ) is the limit of D. The only possible choice is to define Λ ∶= Conel(idl). Now given any cone Φ ∶ cI ⇒ D we want to show that there exists a unique arrow υ ∶ c → l with the property Λ ○ υI = Φ.

So suppose that there exists some arrow υ ∶ c → l with the property Λ ○ υI = Φ. By substituting γ ∶= υ into the above diagram we obtain a commutative square:

img_20170214_210951_hdr

Then following the arrow idl ∈ HomC(l, l) around the square in two different ways gives

idl ○ υ = Unic(Conel(idl) ○ υI)

υ = Unic(Λ ○ υI)

υ = Unic(Φ)

Thus there exists at most one such arrow υ. To show that there exists at least one such arrow, we must check that the arrow Unic(Φ) actually does satisfy Λ ○ (Unic(Φ))I = Φ. Indeed, by substituting υ ∶= Unic(Φ) into the above diagram we obtain a commutative square:

img_20170214_211902_hdr

Then following the arrow idl ∈ HomC(l,l) around the

Conel(idl) ○ (Unic(Φ))I) = Conec(idl ○ Unic(Φ)) Λ ○ (Unic(Φ))I

= Conec(Unic(Φ))

Λ ○ (Unic(Φ))I = Φ

square in two ways gives as desired.

[Remark: We have proved that the limit of a diagram D ∶ I → C, if it exists, consists of an object limID ∈ C and a natural isomorphism

HomC(−, limID) ≅ HomCI((−)I,D) of functors Cop → Set. It turns out that if all limits of shape I exist in C then there is a unique way to extend this to a natural isomorphism

HomC(−,limI−) ≅ HomCI((−)I,−)

of functors Cop × CI → Set, and hence that we have an adjunction (−)I ∶ C ⇄ CI ∶ limI. However, we don’t need this result right now so we won’t prove it. Dually, the colimit of D, if it exists, consists of an object colimID ∈ C and a natural isomorphism HomC(colimID, −) ≅ HomCI(D, (−)I) of functors C → Set. If all colimits of shape I exist in C then this extends uniquely to an adjunction colimI ∶ CI ⇄ C ∶ (−)I. This explains the title of the previous lemma.]

Theorem (RAPL):

Let L ∶ C ⇄ D ∶ R be an adjunction and consider a diagram D ∶ I → D of shape I in D. If the diagram D ∶ I → D has a limit cone Λ ∶ lI ⇒ D then the composite diagram RI(D) ∶ I → C also has a limit cone, which is given by RI(Λ) ∶ R(l)I ⇒ RI(D).

Proof:

In this proof we will write limID ∶= l ∈ D, and we will just assume that the limit object limI RI(D) ∈ C exists. Now we want to show that the following objects are isomorphic in C : R(limID) ≅ limI RI (D). (We will ignore the data of the limit cone.)

So assume that L ∶ C ⇄ D ∶ R is an adjunction. Then we have the following sequence of bijections, each of which is natural in c ∈ Cop:

Homc(c, R(limID)) →~ Homc(L(c), limID) (L ⊣ R)

~ HomDI(L(c),D) (Diagonal ⊣ Limit)

~ HomDI (LI (cI),D)

~ HomCI(c,RI(D))

~ Homc(c,limIRI(D)) (Diagonal ⊣ Limit)

By composing these we obtain a family of bijections

Homc(c,R(limID)) →~ Homc(c,limI RI(D))

that is natural in c ∈ Cop. In other words, we obtain an isomorphism of hom functors HR(limI(D)) ≅ HlimI RI(D) in the category SetCop. Then since the Yoneda embedding H(−) : C → SetCop is essentially injective (from the Embedding Lemma), we obtain an isomorphism of objects R(limID) ≅ limI RI(D) in the category C.

 

RAPL (Right Adjoint Preserve Limits) Theorem. Part 8a.

To prove the RAPL theorem we must first translate the definition of limit/colimit into a language that is compatible with the definition of adjoint functors.

Recall that a diagram is a functor D ∶ I → C from a small category I. If C is locally small then we have a locally small category CI consisting of diagrams and natural transformations between them. For each object c ∈ C we also have the constant diagram cI ∶ I → C that sends each object i ∈ Obj(I) to cI(i) ∶= c and each arrow δ ∈ Arr(I) to cI(δ) ∶= idc.

It is a general phenomenon that many categorical properties of CI are inherited from C. The next lemma collects a few of these properties that we will need later.

Diagram Lemma. Fix a small category I and locally small categories C, D. Then:

(i) For any category C, the mapping c ↦ cI defines a fully faithful functor (−)I ∶ C → CI which we call the diagonal embedding.

(ii)  For any functor F ∶ C → D the mapping FI(D)∶= F ○ D defines a functor FI ∶ CI → DI with the property that F (−)I = FI((−)I).

(iii)  Any adjunction L ∶ C ⇄ D ∶ R induces an adjunction LI ∶ CI ⇄ DI ∶ RI That is, we have a natural isomorphism of bifunctors

HomCI (−, RI(−)) ≅ HomDI (LI(−), −)

from (CI)op × DI to Set.

(iv) In particular, naturality in DI tells us that for all objects l ∈ C and all natural transformations Λ ∶ lI ⇒ D we have a commutative square:

img_20170209_191651_hdr

Proof:

(i): For any arrow α ∶ c1 → c2 in C we want to define a natural transformation of diagrams αI ∶ cI1 ⇒ cI2, and there is only one way to do this. Since (cI1)i = c1 and (cI2)i = c2 ∀ i ∈ I, the arrow I)i ∶= (cI1)i → (cI2)i must be defined by I)i ∶= α. Then for any arrow δ ∶ i → j in I we have cI1(δ) = idc1 and cI2(δ) = idc2, so that

I)i ○ (cI1) (δ) = (α ○ idc1) = (idc2 ○ α) = (cI2)i (δ) ○ (αI)i

and hence we obtain a natural transformation αI ∶ cI1 ⇒ cI2. The assignment α ↦ αI is functorial since for all arrows α, β such that α ○ β exists and ∀ i ∈ I we have (α ○ β)Ii = α ○ β = (αI)i ○ (βI)i = (αI ○ βI)i,

and hence (α ○ β)I = αI ○ βI. Finally, note that we have a bijection of hom sets HomC (c1, c2) ↔ HomCI (cI1, cI2given by α ↔ αI, and hence the functor (−)I ∶ C → CI is fully faithful.

(ii): Let F ∶ C → D be any functor. Then for any diagram D ∶ I → C we obtain a diagram FI(D) ∶ I → D by composition: FI(D) ∶= F ○ D. This assignment is functorial in D ∈ CI. To see this, consider any natural transformation Φ ∶ D1 ⇒ D2 in the category CI. Then for any arrow δ ∶ i → j in I we can apply F to the naturality square for Φ to obtain another commutative square:

img_20170209_195519

If we define FI(Φ)i ∶= F(Φi) ∀ i ∈ I then this second commutative square says that FI(Φ) ∶ FI(D1) ⇒ FI(D2) is a natural transformation in DI. If Φ and Ψ are two arrows (natural transformations) in CI such that Φ ○ Ψ is defined, then ∀ i ∈ I we have FI(Φ ○ Ψ)i = F((Φ ○ Ψ)i) = F(Φi ○ Ψi) = F(Φi) ○ F(Ψi) = FI(Φ)i ○ FI(Ψ)i = (FI(Φ) ○ FI(Ψ))i and hence FI(Φ ○ Ψ) = FI(Φ) ○ FI(Ψ). Thus we have defined a functor FI ∶ CI → DI. Finally, note that ∀ i ∈ I, c ∈ C, and α ∈ Arr(C) we have

FI(cI)i = F((cI)i) = F(c) = ((F(c))I)i FII)i = F((αI)i) = F(α) = ((F(α))I)i

and hence we have an equality of functors FI((−)I) = F (−)I from C to DI

(iii): Let L ∶ C ⇄ D ∶ R be any adjunction. We will denote each bijection HomC(−,R(−)) ↔ HomC(L(−), −) by φ ↦ φ, so that φ= = φ. Now we want to define a natural family of bijections HomCI (−, RI (−)) ≅ HomDI (LI(−), −)

To do this, consider diagrams C ∈ CI, D ∈ DI, and a natural transformation Φ ∶ C ⇒ RI(D). Then for each index i ∈ I we have an arrow Φi ∶ C(i) → R(D(i)), which determines an arrow Φi ∶ L(C(i)) → D(i) by adjunction. The arrows Φi assemble into a natural transformation Φ ∶ LI(C) ⇒ D. To see this, consider any arrow δ ∶ i ∈ j in I. Then from the naturality of Φ and the adjunction L ⊣ R we have

D(δ) ○ Φi = (R(D(δ)) ○ Φi)                             naturality of L ⊣ R

= (Φj ○ C(δ))                                                        naturality of Φ

= Φj ○ L(C(δ))                                                     naturality of L ⊣ R

as desired. In a similar way one can check that for each natural transformation Ψ ∶ LI(C) ⇒ D, the arrows Ψi ∶ C(i) → R(D(i)) assemble into a natural transformation Ψ ∶ C ⇒ RI(D). Thus we have established the desired bijection of hom sets HomCI (C, RI (D)) ↔ HomDI (LI (C), D).

To prove that this bijection is natural in (C, D) ∈ (CI)op × DI, consider any pair of natural transformations Γ∶ C2 ⇒ C1 in CI and ∆ ∶ D1 ⇒ D2 in DI. We need to show that a certain cube of functions commutes. For a fixed diagram C ∈ CI the following square commutes:

img_20170209_201750

First, recall that the natural transformation RI(∆) ∶ RI(D1) ⇒ RI(D2) is defined pointwise by RI(∆)i ∶= R(∆i) ∶ R(D1(i)) → R(D2(i)). Now consider any Φ ∶ C ⇒ RI(D1). The naturality of the original adjunction tells us that (R(∆i) ○ Φi) = ∆i ○ Φi, and hence we have

((RI(∆) ○ Φ)i) = (RI(∆)i ○ Φi)

= (R(∆i) ○ Φi)

= ∆i ○ Φi

= (∆ ○ Φ)i

∀ i ∈ I. By definition this means that (RI(∆) ○ Φ) = ∆ ○ Φ, and hence the desired square commutes. It remains only to check that the cube is natural in (CI)op. This follows from a similar pointwise computation.

(iv): Now fix an element l ∈ C, a diagram D ∈ DI, and a natural transformation Λ ∶ lI ⇒ D. By substituting C = R(l)I, D1 = lI, D2 = D, and ∆ = Λ into the above commutative square and using part (ii), we obtain the commutative square from the statement of the lemma. In particular, following the identity arrow idIR(l) around the square in two ways gives

(RI(Λ) ○ idIR(l)) = Λ ○ (idIR(l))

Finally, one can check pointwise that (idIR(l)) = ((idR(l))I) and hence we obtain the identity

(RI(Λ) ○ idIR(l)) = ((idR(l))I)

Now we will reformulate the definition of limit/colimit in terms of adjoint functors. If all limits/colimits of shape I exist in some category C then it turns out (surprisingly) that we can think of limits/colimits as right/left adjoints to the diagonal embedding (−)I ∶ C → CI : colimI ⊣(−)I ⊣ limI

In the next section/part’s lemma we will prove something slightly more general. We will characterize a specific limit/colimit of shape I, without assuming that all limits/colimits of shape I exist.

From Vector Spaces to Categories. Part 6.

topological_vector_spaces

We began by thinking of categories as “posets with extra arrows”. This analogy gives excellent intuition for the general facts about adjoint functors. However, our intuition from posets is insufficient to actually prove anything about adjoint functors.

To complete the proofs we will switch to a new analogy between categories and vector spaces. Let V be a vector space over a field K and let V ∗ be the dual space consisting of K-linear functions V → K. Now consider any K-bilinear function ⟨−,−⟩ ∶ V × V → K. We say that the function ⟨−,−⟩ is non-degenerate in both coordinates if we have

⟨u1,v⟩ = ⟨u2,v⟩ ∀ v ∈ V ⇒ u1 = u2, ⟨u,v1⟩ = ⟨u,v2⟩ ∀ u ∈ V ⇒ v1 = v2

We say that two K-linear operators L ∶ V ⇄ V ∶ R define an adjunction with respect to ⟨−, −⟩ if, ∀ vectors u,v ∈ V, we have

⟨u, R(v)⟩ = ⟨L(u), v⟩

Uniqueness of Adjoint Operators. Let L ⊣ R be an adjoint pair of operators with respect to a non-degenerate bilinear function ⟨−, −⟩ ∶ V × V → K. Then each of L and R determines

the other uniquely.

Proof: To show that R determines L, suppose that L′ ⊣ R is another adjoint pair. Thus, ∀ vectors u,v ∈ V we have

⟨L(u), v⟩ = ⟨u, R(v)⟩ = ⟨L′(u), v⟩

Now consider any vector u ∈ V. The non-degeneracy of ⟨−, −⟩ tells us that

⟨L(u), v⟩ = ⟨L′(u), v⟩ ∀ v ∈ V ⇒ L(u) = L′(u)

and since this is true ∀ u ∈ V we conclude that L = L′

RAPL for Operators:

Suppose that the function ⟨−, −⟩ ∶ V × V → K is non-degenerate and continuous. Now let T ∶ V → V be any linear operator. If T has a left or a right adjoint, then T is continuous.

Proof:

Suppose that T ∶ V → V has a left adjoint L ⊣ T, and suppose that the sequence of vectors vi ∈ V has a limit limivi ∈ V. Furthermore, suppose that the limit limiT(vi) ∈ V exists. Then for each u ∈ V, the continuity of ⟨−, −⟩ in the second coordinate tells us that

⟨u, T (limivi)⟩ = ⟨L(u), limivi

= limi⟨L(u), vi

= limi⟨u,T(vi)⟩

= ⟨u, limiT (vi)⟩

Since this is true for all u ∈ V, non-degeneracy gives

T (limivi) = limiT (vi)

The theorem can be made rigorous if we work with topological vector spaces. If (V, ∥ − ∥) is a normed (real or complex) vector space, then an operator T ∶ V → V is bounded if and only if it is continuous. Furthermore, if (V,⟨−,−⟩) is a Hilbert space then an operator T ∶ V → V having an adjoint is necessarily bounded, hence continuous. Many theorems of category have direct analogues in functional analysis. After all, Grothendieck began as a functional analyst.

We can summarize these two results as follows. Let ⟨−,−⟩ ∶ V ×V → K be a K-bilinear function. Then for each vector v ∈ V we have two elements of the dual space Hv, Hv ∈ V defined by

Hv ∶= ⟨v,−⟩ ∶ V → K,

Hv ∶= ⟨−,v⟩ ∶ V → K

The mappings v ↦ Hv and v ↦ Hv thus define two K-linear functions from V to V : H(−) ∶V → V and H(−) ∶ V → V

Furthermore, if the function is ⟨−,−⟩ is non-degenerate and continuous then the functions H(−), H(−) ∶ V → V are both injective and continuous.

the hom bifunctor

HomC(−,−) ∶ Cop × C → Set behaves like a “non-degenerate and continuous bilinear function”……

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

…..