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 C^I consisting of diagrams and natural transformations between them. For each object c ∈ C we also have the constant diagram c^I ∶ I → C that sends each object i ∈ Obj(I) to c^I(i) ∶= c and each arrow δ ∈ Arr(I) to c^I(δ) ∶= id_c.

It is a general phenomenon that many categorical properties of C^I 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 ↦ c^I defines a fully faithful functor (−)^I ∶ C → C^I which we call the diagonal embedding.

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

(iii)  Any adjunction L ∶ C ⇄ D ∶ R induces an adjunction L^I ∶ C^I ⇄ D^I ∶ R^I That is, we have a natural isomorphism of bifunctors

Hom_C^I (−, R^I(−)) ≅ Hom_D^I (L^I(−), −)

from (C^I)^op × D^I to Set.

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

Proof:

(i): For any arrow α ∶ c₁ → c₂ in C we want to define a natural transformation of diagrams α^I ∶ c^I₁ ⇒ c^I₂, and there is only one way to do this. Since (c^I₁)_i = c₁ and (c^I₂)_i = c₂ ∀ i ∈ I, the arrow (α^I)_i ∶= (c^I₁)_i → (c^I₂)_i must be defined by (α^I)_i ∶= α. Then for any arrow δ ∶ i → j in I we have c^I₁(δ) = id_c1 and c^I₂(δ) = id_c2, so that

(α^I)_i ○ (c^I₁) (δ) = (α ○ id_c1) = (id_c2 ○ α) = (c^I₂)_i (δ) ○ (α^I)_i

and hence we obtain a natural transformation α^I ∶ c^I₁ ⇒ c^I₂. The assignment α ↦ α^I is functorial since for all arrows α, β such that α ○ β exists and ∀ i ∈ I we have (α ○ β)^I_i = α ○ β = (α^I)_i ○ (β^I)_i = (α^I ○ β^I)_i,

and hence (α ○ β)^I = α^I ○ β^I. Finally, note that we have a bijection of hom sets Hom_C (c₁, c₂) ↔ Hom_C^I (c^I₁, c^I₂) given by α ↔ α^I, and hence the functor (−)^I ∶ C → C^I is fully faithful.

(ii): Let F ∶ C → D be any functor. Then for any diagram D ∶ I → C we obtain a diagram F^I(D) ∶ I → D by composition: F^I(D) ∶= F ○ D. This assignment is functorial in D ∈ C^I. To see this, consider any natural transformation Φ ∶ D₁ ⇒ D₂ in the category C^I. 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 F^I(Φ)_i ∶= F(Φ_i) ∀ i ∈ I then this second commutative square says that F^I(Φ) ∶ F^I(D₁) ⇒ F^I(D₂) is a natural transformation in D^I. If Φ and Ψ are two arrows (natural transformations) in C^I such that Φ ○ Ψ is defined, then ∀ i ∈ I we have F^I(Φ ○ Ψ)_i = F((Φ ○ Ψ)_i) = F(Φ_i ○ Ψ_i) = F(Φ_i) ○ F(Ψ_i) = F^I(Φ)_i ○ F^I(Ψ)_i = (F^I(Φ) ○ F^I(Ψ))_i and hence F^I(Φ ○ Ψ) = F^I(Φ) ○ F^I(Ψ). Thus we have defined a functor F^I ∶ C^I → D^I. Finally, note that ∀ i ∈ I, c ∈ C, and α ∈ Arr(C) we have

F^I(c^I)_i = F((c^I)_i) = F(c) = ((F(c))^I)_i F^I(α^I)_i = F((α^I)_i) = F(α) = ((F(α))^I)_i

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

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

To do this, consider diagrams C ∈ C^I, D ∈ D^I, and a natural transformation Φ ∶ C ⇒ R^I(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 Φ^– ∶ L^I(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 Ψ ∶ L^I(C) ⇒ D, the arrows Ψ_i ∶ C(i) → R(D(i)) assemble into a natural transformation Ψ ∶ C ⇒ R^I(D). Thus we have established the desired bijection of hom sets Hom_C^I (C, R^I (D)) ↔ Hom_D^I (L^I (C), D).

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

First, recall that the natural transformation R^I(∆) ∶ R^I(D₁) ⇒ R^I(D₂) is defined pointwise by R^I(∆)_i ∶= R(∆_i) ∶ R(D₁(i)) → R(D₂(i)). Now consider any Φ ∶ C ⇒ R^I(D₁). The naturality of the original adjunction tells us that (R(∆_i) ○ Φ_i)^– = ∆i ○ Φ_i^–, and hence we have

((R^I(∆) ○ Φ)_i)^– = (R^I(∆)_i ○ Φ_i)^–

= (R(∆_i) ○ Φ_i)^–

= ∆_i ○ Φ_i^–

= (∆ ○ Φ^–)_i

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

(iv): Now fix an element l ∈ C, a diagram D ∈ D^I, and a natural transformation Λ ∶ l^I ⇒ D. By substituting C = R(l)^I, D₁ = l^I, D₂ = 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 id^I_R(l) around the square in two ways gives

(R^I(Λ) ○ id^I_R(l))^– = Λ ○ (id^I_R(l))^–

Finally, one can check pointwise that (id^I_R(l))^– = ((id_R(l))^I)^– and hence we obtain the identity

(R^I(Λ) ○ id^I_R(l))^– = ((id_R(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 → C^I : colim_I ⊣(−)^I ⊣ lim_I

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.

Advertisement

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….

Take: 

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 C^op × C → Set induces two “Yoneda embeddings”

H⁽⁻⁾ ∶ C^op → Set^C and H₍₋₎ ∶ C → Set^Cop

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 c₁, c₂ ∈ C, a hom set function:

F ∶ Hom_C(c₁,c₂) → Hom_D(F(c₁),F(c₂))

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 c₁, c₂ ∈ C we have

c₁ ≅ c₂ in C ⇐⇒ F(c₁) ≅ F(c₂) in D

Furthermore, F is essentially monic6 in the sense that for all functors G₁, G₂ ∶ B → C we have G₁ ≅ G₂ in C^B ⇐⇒ F ○ G₁ ≅ F ○ G₂ in D^B

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

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

F (α) ○ F (β) = F (α ○ β) = F (id_c2 ) = id_F(c2), F (β) ○ F (α) = F (β ○ α) = F (id_c1) = id_F(c1)

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

F (α ○ β) = F (α) ○ F(β) = α′ ○ β′ =id_F(c2) = F(id_c2), F (β ○ α) = F (β) ○ F (α) = β′ ○ α′ = id_F(c1) = F(id_c1)

Then by the faithfulness of F we have α ○ β = id_c2 and β ○ α = id_c1, which implies that α ∶ c₁ ↔ c₂ ∶ β 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 Φ ∶ G₁ ⇒^~ G₂. This means that for each object b ∈ B we

have an isomorphism Φ_b ∶ G₁(b) → G₂(b) in C and for each arrow β ∶ b₁ → b₂ 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 ○ G₁ ⇒ F ○ G₂

Conversely, suppose that we have a natural isomorphism Φ’ ∶ F ○ G₁ ⇒^~ F ○ G₂, meaning that for each object b ∈ B we have an isomorphism Φ_b ∶ F (G₁(b)) → F (G₂(b)) in C, and for each arrow β ∶ b₁ → b₂ 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 ∶ G₁(b) →^~ G₂(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 ○ G₁(β)) = F(Φ_b2) ○ F(G₁(β))

=Φ′_b2 ○ F(G₁(β))

= F (G₂(β)) ○ Φ′_b1

=F (G₂(β)) ○ F′(Φ_b1)

= F (G₂(β) ○ Φ_b1),

and by the faithfulness of F it follows that Φ_b2 ○ G₁(β) = G₂(β) = Φ_b1. We conclude that the following square commutes:

In other words, the arrows Φ_b assemble into a natural isomorphism Φ ∶ G₁ ⇒~ G₂.

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

H^c =Hom_C(c,−) ∶ C → Set and H_c ∶ Hom_C(−,c) ∶ C^op → Set

The mappings c ↦ H^c and c ↦ H_c define two embeddings of categories:

H⁽⁻⁾ ∶ C^op → Set^C and H₍₋₎ ∶ C → Set^Cop

We will prove that H⁽⁻⁾  is an embedding. Then the fact that H₍₋₎ is an embedding follows by substituting C^op in place of C.

Proof:

Step 1: H⁽⁻⁾ is a Functor. For each arrow γ ∶ c₁ → c₂ in C^op (i.e., for each arrow γ ∶ c₂ → c₁ in C) we must define a natural transformation H⁽⁻⁾(γ) ∶ H⁽⁻⁾(c₁) ⇒ H(−)(c₂), i.e., a natural transformation H^γ ∶ H^c₁ ⇒ H^c₂. And this means that for each object d ∈ C we must define an arrow (H^γ)_d ∶ H^c₁(d) → H^c₂(d), i.e., a function (H^γ)_d ∶ Hom_C(c₁,d) → Hom_C(c₂,d). Note that the only possible choice is to send each arrow α ∶ c₁ → d to the arrow α ○ γ ∶ c₂ → d. In other words, ∀ d ∈ C we define,

(H^γ)_d ∶= (−) ○ γ

To check that this is indeed a natural transformation H^γ ∶ H^c₁ ⇒ H^c₂

δ ∶ d₁ → d₂ 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 C^op. To see that this defines a functor C^op → Set^C, we need to show that for any composible arrows γ₁, γ₂ ∈ Arr(C) we have H^{γ₁ ○ γ₂} = H^γ₂ ○ H^γ₁. So consider any arrows γ₁ ∶ c₂ → c₁ and γ₂ ∶ c₃ → c₂. Then ∀ objects d ∈ C and for all arrows δ ∶ c₁ → d we have

[H^γ₂ ○ H^γ₁]_d(δ) = [(H^γ₂)_d ○ (H^γ₁)_d] (δ)

= (H^γ₂)_d [(H^γ₁)_d(δ)]

= (H^γ₂)_d (δ ○ γ₁)

= (δ ○ γ₁) ○ γ₂

= δ ○ (γ₁ ○ γ₂)

= (H^γ₁ ○ γ₂)_d(δ)

Since this holds ∀ δ ∈ H^c₁(d) we have [H^γ₂ ○ H^γ₁]_d = (H^{γ₁ ○ γ₂})_d, and then since this holds ∀ d ∈ C we conclude that H^{γ₁ ○ γ₂} = H^γ₂ ○ H^γ₁ as desired.

Step 2:

H⁽⁻⁾ is Faithful. For each pair of objects c₁,c₂ ∈ C we want to show that the function H⁽⁻⁾ ∶ Hom_C^op (c₁, c₂) → Hom_Set^C (H^c₁ , H^c₂)

defined in part (1) is injective. So consider any two arrows α, β ∶ c₂ → c₁ 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 δ ∈ H^c₁(d) we have defined (H^α)_d(δ) = δ ○ α. Since H^α = H^β, this means that

δ ○ α = (H^α)_d(δ) = (H^β)_d(δ) = δ ○ β. Now we just take d = c₁ and δ = id_c1 to obtain

α = (id_c1 ○ α) = (id_c1 ○ β) = β

as desired.

Step 3:

H⁽⁻⁾ is Full. For each pair of objects c₁, c₂ ∈ C we want to show that the function

H⁽⁻⁾ ∶ Hom_C^op (c₁, c₂) → Hom_Set^C (H^c1 , H^c₂ )
is surjective. So consider any natural transformation Φ ∶ H^c1 ⇒ H^c₂. In this case we want to find an arrow φ ∶ c₂ → c₁ with the property H^φ = Φ. Where can we find such an arrow? By definition of “natural transformation” we have a function Φ_d ∶ H^c₁(d) → H^c₂(d) for each object d ∈ C, and for each arrow δ ∶ d₁ → d₂ 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 ∶ H^c₁ (c₁) → H^c₂ (c₁) at the identity arrow to obtain an arrow φ ∶= Φ_c1 (id_c1) ∈ H^c₂ (c₁). Now hopefully we have H^φ = Φ (otherwise the theorem is not true). To check this, consider any element d ∈ C and any arrow δ ∶ c₁ → d. Substituting this δ into the above diagram gives a commutative square:

Then by following the arrow id_c1 ∈ H c₁ (c₁) around the square in two different ways, and by using the definition (H^φ)_d(δ) ∶= δ ○ φ from part (1), we obtain

Φ_d(δ ○ id_c1) = δ ○ Φ_c1 (id_c1) Φ_d(δ) = δ ○ φ

Φ_d(δ) = (H^φ)_d(δ)

Since this holds for all arrows δ ∈ H^c₁(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⁽⁻⁾ ∶ C^op → Set^C. The fact that H⁽⁻⁾ is “essentially injective” means that for all objects c₁, c₂ ∈ C we have c₁ ≅ c₂ in C ⇐⇒ H^c₁ ≅ H^c₂ in Set^C.

[Note that c₁ ≅ c₂ in C if and only if c₁ ≅ c₂ in C^op.] 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

Hom_D(L(c),d) ≅ Hom_C(c,R(d)) ≅ Hom_D(L′(c),d)

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

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

that is natural in (c,d) ∈ C^op × D

Naturality in d ∈ D means that for each c ∈ C^op we have a natural isomorphism of functors Hom_D(L(c),−) ≅ Hom_D(L′(c),−) in the category Set^D.

Now let us compose the functor L ∶ C^op → D^op  with the Yoneda embedding H⁽⁻⁾ ∶ D^op → Set^D to obtain a functor (H⁽⁻⁾ ○ L) ∶ C^op → Set^D. Observe that if we apply the functor H⁽⁻⁾ ○ L to an object c ∈ C^op then we obtain the functor

(H⁽⁻⁾ ○ L)(c) = Hom^D(L(c),−) ∈ Set^D

Thus, naturality in c ∈ C^op means exactly that we have a natural isomorphism of functors (H⁽⁻⁾ ○ L) ≅ (H⁽⁻⁾ ○ L′) in the category (Set^D)C^op. 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 (Set^D)C^op ⇒ L ≅ L′ in (D^op)C^op

 In other words, we have L ≅ L′ in D^C…..