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:

img_20170208_203625

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

img_20170208_203609

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:

img_20170208_204652_hdr

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:

img_20170208_205811

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.

Proof:

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:

img_20170208_212435_hdr

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:

img_20170209_073201

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:

img_20170209_074057

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s