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

Advertisement