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:



(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:


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:


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.


Disapproval resolution to test Government in Rajya Sabha.Why or Why Not the Justification?

My reflections are based on the views expressed by the Economic Times yesterday, which a friend of mine was kind enough to share.


From the news, the blurb for which is as under:

The government is up against an unexpected hurdle in the Rajya Sabha on the bill for scrapping Rs 500 and Rs 1000 notes. While the ordinance promulgated for extinguishing the notes was replaced by the Specified Bank Notes Bill in the Lok Sabha on Tuesday, the Opposition is set to exploit a procedural opening to derail the government’s efforts in the Rajya Sabha…..But the twist in the tale came at the Rajya Sabha Business Advisory Committee meeting on Tuesday, where Congress MP T Subbarami Reddy sought time to move a resolution “seeking disapproval” of the ordinance itself. The BAC has accepted this after his party backed him along with other Opposition members. This is likely to be taken up together with government’s bill slated for Thursday….


Legally yes, this is a possibility. Practically no, for the costs incurred would be humungous. Passing bills or rather introducing them as money bills is a commonwealth practice, unlike how these are treated in the US, where revenue bills are equally influenced by representatives as well as the senate to a point of governmental shutdown due to non-passage of budgetary legislations. The whole of the commonwealth is lacking on this equality accorded to the upper house, whereas the only couple of checks to safeguard how the Raja Sabha isn’t relegated in legislative duties as far introducing a money bill is considered is firstly in the definition of money bill, which has 7 provisions, of which “only” any of those provisions would meet the criteria of a money bill; and secondly the speaker of the lower house needs to show extreme discretion in consultation with secretaries of both the houses before declaring the bill as money bill. The latter provision installs political neutrality in the speaker of the lower house, which incidentally fails in this scenario, but could also have passed if the secretaries were listened to. Although, the last part in the previous statement is a mere speculation to say the least. 

Apart from this parliamentary procedure, regaining legal tender for the old denominations is a costly affair, for exchange nodes would have evaporated by then barring the zonal offices of the RBI, which as it is would continue acting to accept these old denominations until 31st March. For such a legal tender to become valid for a month would turn banking system inside-out throwing restocking at branches out of gear. Though BAC has accepted this resolution, opposition numbers in the upper house are already heading towards a changing equation with the current opposition still maintaining an edge, but with the 5-states poll, BJP might head for a improvement in numbers rollover. Congress-backed resolution would undoubtedly face flak from the ruling dispensation in the upper house in the form of disruptions and once it is recess time, this resolution going through would find a harder patch to clear. All I could say is expect a tremendous amount of lobbying by the BJP to nullify oppositional gains, if any.  


General Philosophy Of Category Theory, i.e., We Should Only Care About Objects Up To Isomorphism. Part 7.

In this section we will prove that adjoint functors determine each other up to isomorphism. The key tool is the concept of an “embedding of categories”. In particular, the hom bifunctor Cop × C → Set induces two “Yoneda embeddings”

H(−) ∶ Cop → SetC and H(−) ∶ C → SetCop

These are analogous to the two embeddings of a vector space V into its dual space that are induced by a non-degenerate bilinear function ⟨−, −⟩ ∶ V × V → K.

Embedding of Categories: Recall that a functor F ∶ C → D consists of:

• An object function F ∶ Obj(C) → Obj(D),

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

F ∶ HomC(c1,c2) → HomD(F(c1),F(c2))

We say that F is a full functor when the hom set functions are surjective, and we say that F is a faithful functor when the hom set functions are injective. If the hom set functions are bijective then we say that F is a fully faithful functor, or an embedding of categories.

An embedding is in some sense the correct notion of an “injective functor”. If F ∶ C → D is an embedding, then the object function F ∶ Obj(C) → Obj(D) is not necessarily injective, but it is “injective up to isomorphism”. This agrees with the general philosophy of category theory, i.e., that we should only care about objects up to isomorphism.

Embedding Lemma: Let F ∶ C → D be an embedding of categories. Then F is essentially injective in the sense that for all objects c1, c2 ∈ C we have

c1 ≅ c2 in C ⇐⇒ F(c1) ≅ F(c2) in D

Furthermore, F is essentially monic6 in the sense that for all functors G1, G2 ∶ B → C we have G1 ≅ G2 in CB ⇐⇒ F ○ G1 ≅ F ○ G2 in DB

Proof: Let F ∶ C → D be full and faithful, i.e., bijective on hom sets.

To prove that F is essentially injective, suppose that α ∶ c1 ↔ c2 ∶ β is an isomorphism in C and apply F to obtain arrows F (α) ∶ F (c1) ⇄ F (c2) ∶ F (β) in D. Then by the functoriality of F we have

F (α) ○ F (β) = F (α ○ β) = F (idc2 ) = idF(c2), F (β) ○ F (α) = F (β ○ α) = F (idc1) = idF(c1)

which implies that F (α) ∶ F (c1) ↔ F (c2) ∶ F (β) is an isomorphism in D. Conversely, suppose that α′ ∶ F (c1) ↔ F (c2) ∶ β′ is an isomorphism in D. By the fullness of F there exist arrows α ∶ c1 ⇄ c2 ∶ β such that F(α)=α′ and F(β)=β′, and by the functoriality of F we have

F (α ○ β) = F (α) ○ F(β) = α′ ○ β′ =idF(c2) = F(idc2), F (β ○ α) = F (β) ○ F (α) = β′ ○ α′ = idF(c1) = F(idc1)

Then by the faithfulness of F we have α ○ β = idc2 and β ○ α = idc1, which implies that α ∶ c1 ↔ c2 ∶ β is an isomorphism in C.

To prove that F is essentially monic, let G, G ∶ B → C be any functors and suppose that

we have a natural isomorphism Φ ∶ G1~ G2. This means that for each object b ∈ B we

have an isomorphism Φb ∶ G1(b) → G2(b) in C and for each arrow β ∶ b1 → b2 in B we have a commutative square:


Recall from the previous argument that any functor sends isomorphisms to isomorphisms, thus by the functoriality of F we obtain another commutative square:


in which the horizontal arrows are isomorphisms in D. In other words, the assignment F (Φ)b ∶= F(Φb) defines a natural isomorphism F(Φ) ∶ F ○ G1 ⇒ F ○ G2

Conversely, suppose that we have a natural isomorphism Φ’ ∶ F ○ G1~ F ○ G2, meaning that for each object b ∈ B we have an isomorphism Φb ∶ F (G1(b)) → F (G2(b)) in C, and for each arrow β ∶ b1 → b2 in B we have a commutative square:


Since F is fully faithful, we know from the previous result that for each b ∈ B ∃ an isomorphism Φb ∶ G1(b) →~ G2(b) in C with the property Φb = F (Φ’b). Then by the functoriality of F and the commutativity of the above square we have,

F(Φb2 ○ G1(β)) = F(Φb2) ○ F(G1(β))

=Φ′b2 ○ F(G1(β))

= F (G2(β)) ○ Φ′b1

=F (G2(β)) ○ F′(Φb1)

= F (G2(β) ○ Φb1),

and by the faithfulness of F it follows that Φb2 ○ G1(β) = G2(β) = Φb1. We conclude that the following square commutes:


In other words, the arrows Φb assemble into a natural isomorphism Φ ∶ G1 ⇒~ G2.

Lemma (The Yoneda Embeddings): Let C be a category and recall that for each object c ∈ C we have two hom functors

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

The mappings c ↦ Hc and c ↦ Hc define two embeddings of categories:

H(−) ∶ Cop → SetC and H(−) ∶ C → SetCop

We will prove that H(−)  is an embedding. Then the fact that H(−) is an embedding follows by substituting Cop in place of C.


Step 1: H(−) is a Functor. For each arrow γ ∶ c1 → c2 in Cop (i.e., for each arrow γ ∶ c2 → c1 in C) we must define a natural transformation H(−)(γ) ∶ H(−)(c1) ⇒ H(−)(c2), i.e., a natural transformation Hγ ∶ Hc1 ⇒ Hc2. And this means that for each object d ∈ C we must define an arrow (Hγ)d ∶ Hc1(d) → Hc2(d), i.e., a function (Hγ)d ∶ HomC(c1,d) → HomC(c2,d). Note that the only possible choice is to send each arrow α ∶ c1 → d to the arrow α ○ γ ∶ c2 → d. In other words, ∀ d ∈ C we define,

(Hγ)d ∶= (−) ○ γ

To check that this is indeed a natural transformation Hγ ∶ Hc1 ⇒ Hc2

δ ∶ d1 → d2 in C and observe that the following diagram commutes:


Indeed, the commutativity of this square is just the associative axiom for composition. Thus we have defined the action of H(−) on arrows in Cop. To see that this defines a functor Cop → SetC, we need to show that for any composible arrows γ1, γ2 ∈ Arr(C) we have Hγ1 ○ γ2 = Hγ2 ○ Hγ1. So consider any arrows γ1 ∶ c2 → c1 and γ2 ∶ c3 → c2. Then ∀ objects d ∈ C and for all arrows δ ∶ c1 → d we have

[Hγ2 ○ Hγ1]d(δ) = [(Hγ2)d ○ (Hγ1)d] (δ)

= (Hγ2)d [(Hγ1)d(δ)]

= (Hγ2)d (δ ○ γ1)

= (δ ○ γ1) ○ γ2

= δ ○ (γ1 ○ γ2)

= (Hγ1 ○ γ2)d(δ)

Since this holds ∀ δ ∈ Hc1(d) we have [Hγ2 ○ Hγ1]d = (Hγ1 ○ γ2)d, and then since this holds ∀ d ∈ C we conclude that Hγ1 ○ γ2 = Hγ2 ○ Hγ1 as desired.

Step 2:

H(−) is Faithful. For each pair of objects c1,c2 ∈ C we want to show that the function H(−) ∶ HomCop (c1, c2) → HomSetC (Hc1 , Hc2)

defined in part (1) is injective. So consider any two arrows α, β ∶ c2 → c1 in C and suppose that we have Hα = Hβ as natural transformations. In this case we want to show that α = β.

Recall that ∀ objects d ∈ C and all arrows δ ∈ Hc1(d) we have defined (Hα)d(δ) = δ ○ α. Since Hα = Hβ, this means that

δ ○ α = (Hα)d(δ) = (Hβ)d(δ) = δ ○ β. Now we just take d = c1 and δ = idc1 to obtain

α = (idc1 ○ α) = (idc1 ○ β) = β

as desired.

Step 3:

H(−) is Full. For each pair of objects c1, c2 ∈ C we want to show that the function

H(−) ∶ HomCop (c1, c2) → HomSetC (Hc1 , Hc2 )
is surjective. So consider any natural transformation Φ ∶ Hc1 ⇒ Hc2. In this case we want to find an arrow φ ∶ c2 → c1 with the property Hφ = Φ. Where can we find such an arrow? By definition of “natural transformation” we have a function Φd ∶ Hc1(d) → Hc2(d) for each object d ∈ C, and for each arrow δ ∶ d1 → d2 we know that the following square commutes:


Note that the category C might have very few arrows. (Indeed, C might be a discrete category, i.e., with only the identity arrows.) This suggests that our only possible choice is to evaluate the function Φc1 ∶ Hc1 (c1) → Hc2 (c1) at the identity arrow to obtain an arrow φ ∶= Φc1 (idc1) ∈ Hc2 (c1). Now hopefully we have Hφ = Φ (otherwise the theorem is not true). To check this, consider any element d ∈ C and any arrow δ ∶ c1 → d. Substituting this δ into the above diagram gives a commutative square:


Then by following the arrow idc1 ∈ H c1 (c1) around the square in two different ways, and by using the definition (Hφ)d(δ) ∶= δ ○ φ from part (1), we obtain

Φd(δ ○ idc1) = δ ○ Φc1 (idc1) Φd(δ) = δ ○ φ

Φd(δ) = (Hφ)d(δ)

Since this holds for all arrows δ ∈ Hc1(d) we have Φd = (Hφ)d, and then since this holds for

all objects d ∈ C we conclude that Φ = Hφ as desired.

Let’s pause to apply the Embedding Lemma to the Yoneda embedding H(−) ∶ Cop → SetC. The fact that H(−) is “essentially injective” means that for all objects c1, c2 ∈ C we have c1 ≅ cin C ⇐⇒ Hc1 ≅ Hc2 in SetC.

[Note that c1 ≅ c2 in C if and only if c1 ≅ c2 in Cop.] This useful fact is the starting point for many areas of modern mathematics. It tells us that if we know all the information about arrows pointing to (or from) an object c ∈ C, then we know the object up to isomorphism. In some sense this is a justification for the philosophy of category theory. The Embedding Lemma also implies that the Yoneda embedding is “essentially monic,” i.e., “left-cancellable up to natural isomorphism”. We will use this fact to prove the uniqueness of adjoints.

Uniqueness of Adjoints: Let L ∶ C ⇄ D ∶ R be an adjunction of categories. Then each of L and R determines the other up to natural isomorphism.

Proof: We will prove that R determines L. The other direction is similar. So suppose that L′ ∶ C ⇄ D ∶ R is another adjunction. Then we have two bijections

HomD(L(c),d) ≅ HomC(c,R(d)) ≅ HomD(L′(c),d)

that are natural in (c, d) ∈ Cop × D, and by composing them we obtain a bijection

HomD(L(c),d) ≅ HomD(L′(c),d)

that is natural in (c,d) ∈ Cop × D

Naturality in d ∈ D means that for each c ∈ Cop we have a natural isomorphism of functors HomD(L(c),−) ≅ HomD(L′(c),−) in the category SetD.

Now let us compose the functor L ∶ Cop → Dop  with the Yoneda embedding H(−) ∶ Dop → SetD to obtain a functor (H(−) ○ L) ∶ Cop → SetD. Observe that if we apply the functor H(−) ○ L to an object c ∈ Cop then we obtain the functor

(H(−) ○ L)(c) = HomD(L(c),−) ∈ SetD

Thus, naturality in c ∈ Cop means exactly that we have a natural isomorphism of functors (H(−) ○ L) ≅ (H(−) ○ L′) in the category (SetD)Cop. Finally, since the “Yoneda embedding” H(−) is an embedding of categories, the Embedding Lemma tells us that we can cancel H(−) on the left to obtain a natural isomorphism:

(H(−) ○ L) ≅ (H(−) ○ L′) in (SetD)Cop ⇒ L ≅ L′ in (Dop)Cop

 In other words, we have L ≅ L′ in DC…..