Title: Daniel's Flashcards / Year 4 / Term 1 / Category Theory

html: Definition 1.1 (Category). A category C consists of:
- (a)
a collection ob ⁡ C of objects A , B , C , ….
- (b)
a collection mor ⁡ C of morphisms f , g , h , ….
- (c)
two operations dom ⁡, cod ⁡ from mor ⁡ C to ob ⁡ C: we write f : A → B for “f is a morphism and dom ⁡ f = A and cod ⁡ f = B”.
- (d)
an operation from ob ⁡ C to mor ⁡ C sending A to 1 A : A → A.
- (e)
a partial binary operation ( f , g ) ↦ f g on mor ⁡ C, such that f g is defined if and only if dom ⁡ f = cod ⁡ g, and in this case we have dom ⁡ f g = dom ⁡ g and cod ⁡ f g = cod ⁡ f.
These are subject to the axioms:
- (f)
f 1 A = f and 1 A g = g when the composites are defined.
- (g)
f ( g h ) = ( f g ) h whenever f g and g h are defined.
nothing: True

html: Definition 1.4 (Functor). Let C and D be categories. A functor F : C → D consists of mappings F : ob ⁡ C → ob ⁡ D and F + mor ⁡ C → mor ⁡ D such that:
- F ( dom ⁡ f ) = dom ⁡ F f
- F ( cod ⁡ f ) = cod ⁡ F f
- F ( 1 A ) = 1 F A
- F ( f g ) = ( F f ) ( F g ) whenever f g is defined.
We write Cat for the category of small categories and the functors between them.
nothing: True

html: Definition 1.6 (Natural transformation). Given categories C and D, and two functors C ⇉ G F D, a natural transformation α : F → G assigns to each A ∈ ob ⁡ C a morphism α A : F A → G A in D, such that for any A → f B in C, the square
commutes (we call this square the naturality square for α at f). Given α as above, and β : G → H, we define β α : F → H by ( β α ) A = β A α A. We write [ C , D ] for the category of functors C → D and natural transformations between them.
nothing: True

html: Lemma 1.8. Assuming that:
- α : F → G is a natural transformation between functors C ⇉ D
Then α is an isomorphism in [ C , D ] if and only if α A is an isomorphism in D for each A.
proof: Proof.
- ⇒ Obvious since composition in [ C , D ].
- ⇐ Suppose each α A has an inverse β A. Given A → f B in C, in the diagram
we have β B ( G f ) = β B ( G f ) α A β A = β B α B ( F f ) β A = ( F f ) β A. □
cloze1: True

html: Definition 1.9 (Equivalence of categories). Let C and D be categories. An equivalence between C and D consists of functors F : C → D and G : D → C together with natural isomorphisms α : 1 C → G F, β : F G → 1 D. We write C ≡ D if there exists an equivalence between C and D.
We say P is a categorical property if
( C has P and C ≡ D ) ⟹ D has P .
nothing: True

html: Definition 1.11 (Faithful / full / essentially surjective). Let F : C → D be a functor.
- (a)
We say F is faithful if, given f and g in mor ⁡ C, ( F f = F g, dom ⁡ f = dom ⁡ g, cod ⁡ f = cod ⁡ g ) ⟹ f = g.
- (b)
We say F is full if, for every g : F A → F B in D, there exists f : A → B in C with F f = g.
- (c)
We say F is essentially surjective if, for any B ∈ ob ⁡ D, there exists A ∈ ob ⁡ C with F A ≅ B.
Note that if F is full and faithful, it’s essentially injective: given F A → ≅ g F B in D, the unique A → f B with F f = g is an isomorphism.
We say D ⊆ C is a full subcategory if the inclusion D → C is a full functor.
nothing: True

html: Lemma 1.12. Assuming that:
- F : C → D
Then F is part of an equivalence C ≡ D if and only if F is full, faithful, essentially surjective.
proof: Proof.
- ⇒ Suppose give G, α and β as in Definition 1.9. Then β B : F G B → B witnesses the fact that F is essentially surjective. If A ⇉ g f B satisfy F g = F g, then G F f = G F g; but f = α B − 1 ( G F f ) α A, so f = g. Suppose given F A → g F B; then f = α B − 1 ( G g ) α A satisfies G F f = G f but G is faithful for the same reason as F, so F f = g.
- ⇐ For each B ∈ ob ⁡ D, chose G B ∈ ob ⁡ C and an isomorphism β B : F G B → B. Given B → g C, define G g : G B → G C to be the unique morphism such that F G g = β C − 1 g β B. Functoriality follows from uniqueness, and naturality of β. We define α A : A → G F A to be the unique morphism such that F α A = β F A − 1 : F A → F G F A. α A is an isomorphism, and naturality squares for α are mapped by F to naturality squares for β − 1, so they commute. □
cloze1: True

html: Definition 1.13 (Skeleton). By a skeleton of a category C, we mean a full subcategory containing just one object from each isomorphism class.
We say C is skeletal if it’s a skeleton of itself.
nothing: True

html: Definition 1.14 (Monomorphism / epimorphism). Let f : A → B be a morphism in a category C. We say f is a monomorphism (or monic) if, given C ⇉ h g A, f g = f h ⟹ g = h. We say f is an epimorphism (or epic) if it’s a monomorphism in C o p.
We write A ↣ f B to indicate that f is monic, and A ↠ f B to indicate that it’s epic.
We say C is balanced if every arrow which is monic and epic is an isomorphism.
nothing: True

html: Definition 2.1 (Locally small). We say a category C is locally small if, for any two objects A and B, the morphisms A → B in C are parameterised by a set C ( A , B ).
nothing: True

html: Lemma 2.2 (Yoneda). Assuming that:
- C is a locally small category
- A ∈ ob ⁡ C
- F : C → S e t a functor
Then
- (i) There is a bijection between natural transformations C ( A , ∙ ) → F and elements of F A.
- (ii) Moreover, this bijection is natural in A and F.
proof: Proof.
- (i) Given α : C ( A , ∙ ) → F, we define Φ ( α ) = α A ( 1 A ) ∈ F A.
Given x ∈ F A, we define Ψ ( x ) : C ( A , ∙ ) → F by Ψ ( x ) B ( f : A → B ) = F f ( x ) ∈ F B. This is natural in B since F is a functor: given g : B → C we have
( F g ) Ψ ( x ) B ( f ) = ( F g ) ( F f ) ( x ) = F ( g f ) ( x ) = Ψ ( x ) C ( g f ) .
For any x, Φ Ψ ( x ) = Ψ ( x ) A ( 1 A ) = F 1 A ( x ) = x.
For any α, Ψ Φ ( α ) B ( f ) = F f ( α A ( 1 A ) ) = α B ( C ( A , f ) ( 1 A ) = α B ( f ) for all f : A → B. So Ψ Φ ( α ) = α.
- (ii) Later. Seeing examples of usage of (i) is interesting first. □
nothing: True

html: Corollary 2.3. Assuming that:
- C a locally small category
Then A ↦ C ( A , ∙ ) is a full and faithful functor C o p → [ C , S e t ].
proof: Proof. Substitute C ( B , ∙ ) for F in Lemma 2.2(i): we have a bijection from C ( B , A ) to the collection of natural transformations C ( A , ∙ ) → C ( B , ∙ ).
For a given f, the natural transformation C ( f , ∙ ) sends g : B → C to g f, so this is functorial by associativity of composition C.
Similarly, we have a full and faithful functor C → [ C o p , S e t ] sending A to C ( ∙ , A ). We call this the Yoneda embedding: it allows us to regard any locally small category C as a full subcategory of a S e t-valued functor category. □
cloze1: True

html: Definition 2.4 (Representable). We say a functor F : C → S e t is representable if it’s isomorphic to a C ( A , ∙ ) for some A. By a representation of F, we mean a pair ( A , x ) where x ∈ F A is such that Φ ( x ) is an isomorphism. We call x a universal element of F.
nothing: True

html: Proof of Yoneda (ii).
Suppose for the moment that C is small, so that [ C , S e t ] is locally small. Given two functors C × [ C , S e t ] → S e t: the first sends an object ( A , F ) to F A, and a morphism ( A → f A ′ , F → α F ′ ) to the diagonal of
The second is the composite
C × [ C , S e t ] → Y × 1 [ C , S e t ] o p × [ C , S e t ] → [ C , S e t ] ( ∙ , ∙ ) S e t
where Y is a Yoneda embedding. Then Φ and Ψ define a natural isomorphism between these two.
In elementary terms, this says that if x ∈ F A, and x ′ ∈ F ′ A ′ is its image under the diagonal, then Ψ ( x ′ ) is the composite
C ( A ′ , ∙ ) → C ( f , ∙ ) C ( A , ∙ ) → Ψ ( x ) F → α F ′ .
This makes sense without the assumption that C is small, and it’s true since the composite maps
1 A ′ ↦ f ↦ ( F f ) ( x ) ↦ α A ′ ( F f ) ( x ) . □
cloze1: True

html: Definition 2.7 (Separating / generating family). Let G be a family of objects of a locally small category C.
- (a)
We say G is a separating family if the functors C ( G , ∙ ), G ∈ G are jointly faithful, i.e. given a parallel pair A ⇉ g f B, the equations f h = g h for all h : G → A with G ∈ G imply f = g.
- (b)
We say G is a detecting family if the G ( G , ∙ ) jointly reflect isomorphisms, i.e. given A → f B, if every G → g B with G ∈ G factors uniquely through f, then f is an isomorphism.
If G = { G }, we call G a separator or a detector.
nothing: True

html: Definition 2.10 (Projective). We say an object P in a locally small category Cis projective if C ( P , ∙ ) preserves epimorphisms, i.e. if given
there exists h : P → Q with g h = f. Dually, P is injective if it’s projective in C o p.
If P satisfies this condition for all g in some class E of epimorphisms, we call it E-projective.
nothing: True

html: Corollary 2.11. functors of the form C ( A , ∙ ) are pointwise projective in [ C , S e t ].
proof: Proof. Immediate from Yoneda; given
with β pointwise epic, Φ ( α ) ∈ R A is β A ( y ) for some y ∈ Q A, so β Ψ ( y ) = α. □

html: Proposition 2.12. Assuming that:
- C is small
- F : C → S e t
Then there exists a pointwise epimorphism P ↠ F where P is pointwise projective.
proof: Proof. Set P = ∐ ⁡ ( A , x ) C ( A , ∙ ) where the disjoint union is over all pairs ( A , x ) with A ∈ ob ⁡ C and x ∈ F A. A morphism P → Q is uniquely determined by a family of morphisms C ( A , ∙ ) → Q. . Hence P is pointwise projective, since all the C ( A , ∙ ) are. But we have α : P → F whose ( A , x )-th component is Ψ ( x ) : C ( A , ∙ ) → F and this is pointwise epic since any x ∈ F A appears as Ψ ( x ) ( 1 A ). □
cloze1: True

html: Definition 3.1 (Adjunction, D. Kan 1958). Let C and D be categories. An adjunction between C and D consists of functors F : C → D and G : D → C together with, for each A ∈ ob ⁡ C and B ∈ ob ⁡ D, a bijection between morphisms F A → B in D and morphisms A → G B in C, which is natural in A and B. (If C and D are locally small, this means that D ( F ∙ , ∙ ) and C ( ∙ , G ∙ ) are naturally isomorphic functors C o p × D → S e t.)
We say F is left adjoint to G, or G is right adjoint to F, and we write ( F ⊣ G ).
nothing: True

html: Theorem 3.3. Assuming that:
- G : D → C is a functor
- for A ∈ ob ⁡ C, let ( A ↓ G ) be the category whose objects are pairs ( B , f ) where B ∈ ob ⁡ D and f : A → G B, and whose morphisms ( B , f ) → ( B ′ , f ′ ) are morphisms g : B → B ′ making
commute.
Then specifying a left adjoint for G is equivalent to specifying an initial object of ( A ↓ G ) for each A.
proof: Proof. First suppose ( F ⊣ G ). For each A ∈ ob ⁡ C, let η A : A → G F A be the morphism corresponding to 1 F A : F A → F A. Then ( F A , η A ) is an initial object of ( A ↓ G ): given any f : A → G B, the diagram
commutes if and only if g corresponds to f under the adjunction, by naturality of the adjunction bijection.
So there’s a unique morphism ( F A , η A ) → ( B , f ) in ( A ↓ G ).
Conversely, suppose given in initial object ( F A , η A ) in ( A ↓ G ) for each A. We make F into a function C → D: given A → f B, F f is the unique morphism ( F A , η A ) → ( F B , η B f ) in ( A ↓ G ). Functoriality comes from uniqueness: given B → g C, ( F g ) ( F f ) and F ( g f ) are both morphisms ( F A , η A ) → ( F C , η C g f ) in ( A ↓ G ). The adjunction bijection sends A → f G B to the unique morphism ( F A , η A ) → ( B , f ) in ( A ↓ G ), with inverse sending F A → g B to ( G g ) η A : A → G B. This is natural in A since η is a natural transformation 1 C → G F and natural in B since G is functorial. □
cloze1: True

html: Corollary 3.4. Assuming that:
- F and F ′ are both left adjoint to G : D → C
Then there is a canonical natural isomorphism α : F → F ′.
proof: Proof. ( F A , η A ) and ( F ′ A , η A ′ ) are both initial in ( A ↓ G ), so there’s a unique isomorphism α A between them. α is natural: given A → f B, ( F ′ f ) α A and α B ( F f ) are both morphisms ( F A , η A ) → ( F ′ B , η B ′ f ) in ( A ↓ G ), so they’re equal. □
cloze1: True

html: Lemma 3.5. Assuming that:
- C ⇄ G F D ⇄ K H E
- ( F ⊣ G ) and ( H ⊣ K )
Then ( H F ⊣ G K ).
proof: Proof. Given A ∈ ob ⁡ C, C ∈ ob ⁡ E, we have bijections between morphisms H F A → C, morphisms F A → K C, and morphisms A → G K C which are both natural in A and C, D. □
cloze1: True

html: Corollary 3.6. Assuming that:
- the diagram
is a commutative square of categories and functors
- all the functors have left adjoints
Then the square of left adjoints commutes up to natural isomorphism.
proof: Proof. By Lemma 3.5, both ways round are left adjoint to H F = K G, so by Corollary 3.4 they’re isomorphic. □
cloze1: True

html: Theorem 3.7. Assuming that:
- F : C → D and G : D → C are functors
Then specifying an adjunction ( F ⊣ G ) is equivalent to specifying a natural transformation η : 1 C → G F and 𝜀 : F G → 1 D satisfying the two commutative diagrams:
proof: Proof. Suppose ( F ⊣ G ). We defined η in the proof of Theorem 3.3, and 𝜀 is defined dually. Since 𝜀 F A corresponds to 1 G F A, the composite 𝜀 F A ( F η A ) corresponds to 1 G F A η A = η A. But by definition 1 F A corresponds to η A. The other identity is dual.
Conversely, suppose given η and 𝜀 satisfying the triangular identities. Given F A → f B, we define Φ ( f ) = ( G f ) η A : A → G F A → G B. Dually, given A → g G B, we define Ψ ( g ) = 𝜀 B ( F g ). Then Ψ Φ ( f ) = Ψ ( ( G f ) η A ) = 𝜀 B ( F G f ) F η A = f ( 𝜀 F A ) ( F η A ) = f, and dually Φ Ψ ( g ) = g. Naturality of Φ and Ψ follows from naturality of η and 𝜀. □
cloze1: True

html: Proposition 3.8. Assuming that:
- F : C → D, G : D → C, α : 1 C → G F and β : F G → 1 D be an equivalence of categories as defined in Definition 1.9
Then there exist isomorphisms α ′ : 1 C → G F and β ′ : F G → 1 D satisfying the triangular identities. In particular, ( F ⊣ G ⊣ F ).
proof: Proof. We define α ′ = α and take β ′ to be the composite
F G → ( F G β ) − 1 F G F G → ( F α G ) − 1 F G → β 1 D .
Note that F G β = β F G, since
commutes by naturality of β, and β is monic. Similarly, G F α = α G F.
To verify the triangular identities, consider
which commutes by naturality of β − 1.
For the second triangular identity, we have
Hence by Theorem 3.7 we have ( F ⊣ G ). But ( β ′ ) − 1 and α − 1 also satisfy the triangular identities for and adjunction ( G ⊣ F ). □
cloze1: True

html: Lemma 3.9. Assuming that:
- ( F : C → D ⊣ G : D → C ) an adjunction with counit 𝜀
Then
- (i) G is faithful if and only if 𝜀 is pointwise epic
- (ii) G is full and faithful if and only if 𝜀 is an isomorphism
proof: Proof.
- (1) Given g : B → C in D, g 𝜀 B corresponds to G g under the adjunction. So 𝜀 B epic if and only if G acts injectively on morphisms with domain B and specified codomain. Hence 𝜀 B epic for all B if and only if G is faithful.
- (2) Similarly, G full and faithful if and only if for all B and C composition with 𝜀 B is a bijection D ( B , C ) → D ( F G B , C ). This happens if and only if 𝜀 b : F G B → B is an isomorphism for all B. □
cloze1: True

html: Definition 3.10 (Reflection). By a reflection, we mean an adjunction such that the right adjoint is full and faithful (equivalently: the counit is an isomorphism). We say D ⊆ C is a reflective subcategory if it’s full and the inclusion D → C has a left adjoint.
nothing: True

html: Definition 4.1 (Diagram). Let J be a category (almost always small, and often finite). By a diagram of shape J in a category C, we mean a functor D : J → C. The objects D ( j ), j ∈ ob ⁡ J are called vertices of D, and morphisms D ( α ), α ∈ mor ⁡ J are called edges of D.
nothing: True

html: Definition 4.2 (Cone, limit). Let D : J → C be a diagram. A cone over D consists of an object A (its apex) together with morphisms λ j : A → D ( j ) for each j ∈ ob ⁡ J (the legs of the cone) such that
commutes for each α : j → j ′ in J.
A morphism of cones ( A , ( λ j | j ∈ ob ⁡ J ) ) → ( B , ( μ j | j ∈ ob ⁡ J ) ) is a morphism f : A → B such that μ j f = λ j for all j. We have a category C o n e ( D ) of cones over D; a limit for D is a terminal object of C o n e ( D ).
Dually, a colimit for D is an initial cone under D.
nothing: True

html: Proposition 4.4. Assuming that:
- C a category
Then
- (i) If C has equalisers and all small products (including empty product), then C has all small limits.
- (ii) If C has equalisers and all finite products (including empty product), then C has all finite limits.
- (iii) If C has pullbacks and a terminal object, then C has all finite limits.
proof: Proof.
- (i) & (ii) Let D : J → C be a diagram. Form the products P = ∏ j ∈ ob ⁡ J D ( j ) Q = ∏ α ∈ mor ⁡ J D ( cod ⁡ α )
We have morphisms P ⇉ g f Q defined by π α f = π cod ⁡ α and π α g = D ( α ) π dom ⁡ α for all α. Let e → e P be an equaliser for ( f , g ). The morphisms λ j = π j e : E → P → D ( j ) form a cone over D, since for any α : j → j ′ we have
D ( α ) λ j = D ( α ) π j e = π α g e = π α f e = π j ′ e = λ j ′ .
It is a limit: given any cone ( A , ( μ j | j ∈ ob ⁡ J ) ) over D, the μ j form a cone over the discrete diagram with vertices D ( j ), so they induce a unique μ : A → P. Then f μ = g μ since the μ js form a cone over D, so μ factors uniquely as e ν, and ν is the unique factorisation of ( μ j | j ∈ ob ⁡ J ) through ( λ j | j ∈ ob ⁡ J ).
- (iii) If 1 is a terminal object of C, then we can construct A × B as the pullback of
Then we can construct ∏ ⁡ i = 1 n A i as A 1 × ( A 2 × ( ⋯ × A n ) ⋯ ) ).
To form an equaliser of A ⇉ g f B, consider the pullback of
Any cone
over this has h = k = π 1 ( 1 A , g ) k = π 1 ( 1 A , f ) h. So a limit cone has the universal property of an equaliser for ( f , g ). □
cloze1: True

html: Definition 4.5 (Limit preserving / reflecting / creating). Let F : C → D be a functor.
- (a)
We say F preserves limits of shape J if, given D : J → C and a limit cone ( L , ( λ j | j ∈ ob ⁡ J ) ) for it, ( F L , ( F λ j | j ∈ ob ⁡ J ) ) is a limit for F D : J → D.
- (b)
We say F reflects limits of shape J if given D : J → C, any cone over D which maps to a limit cone in D is a limit in C.
- (c)
We say F creates limits of shape J if, given D : J → C and a limit cone ( L , ( λ j | j ∈ ob ⁡ J ) ) over F D, there exists a cone over D whose image under F is ≅ ( L , ( λ j ) ), and any such cone is a limit in C.
nothing: True

html: Lemma 4.9. Assuming that:
- G : D → C has a left adjoint
Then G preserves all limits which exist in D.
proof: Proof 1. Suppose ( F ⊣ G ), and suppose C and D have limits of shape J. Then the diagram
commutes, and all the functors in it have right adjoints, so
commutes up to isomorphism by Corollary 3.6. □
cloze1: True

html: Lemma 4.10. Assuming that:
- J a diagram shape
- D has all limits of shape J
- G : D → C preserves all limits of shape J
Then for each A ∈ ob ⁡ C, ( A ↓ G ) has limits of shape J and the forgetful functor ( A ↓ G ) → U D creates them.
proof: Proof. Suppose given D : J → ( A ↓ G ); write D ( j ) = ( U D ( j ) , f j : A → G U D ( j ) ) and let ( L , ( λ j | j ∈ ob ⁡ J ) ) be a limit for U D. Since the edges of D are morphisms in ( A ↓ G ), the f j form a cone over G U D, so there’s a unique f : A → G L satisfying ( G λ j ) f = f j for all j.
So ( L , f ) is the unique lifting of L to an object of ( A ↓ G ) which makes the λ j into morphisms ( L , f ) → ( U D ( j ) , f j ) in ( A ↓ G ). The fact that these morphisms form a limit cone is straightforward. □
cloze1: True

html: Lemma 4.11. Assuming that:
- C a category
Then specifying an initial object of C is equivalent to specifying a limit for 1 C : C → C.
proof: Proof. First suppose I is initial. The unique morphisms I → A, A ∈ ob ⁡ C, form a cone over 1 C, and it’s a limit cone since if ( A , ( f B : A → B | B ∈ ob ⁡ C ) ) is any cone over 1 C, then f I is its unique factorisation through the one with apex I.
Conversely, suppose given a limit ( I , ( f A : I → A | A ∈ ob ⁡ C ) ) for 1 C. Then I is weakly initial (i.e. it admits morphisms to every object of C); and if g : I → A then g f I = f A. In particular, f A f I = f A for all A, so f I is a factorisation of the limit cone through itself, so f I = 1 I and I is initial. □
cloze1: True

html: Theorem 4.12 (General Adjoint Functor Theorem). Assuming that:
- D is complete and locally small
Then G : D → C has a left adjoint if and only if G preserves small limits and satisfies the solution-set condition: for every A ∈ ob ⁡ C, there’s a set { ( B i , f i ) | i ∈ I } of objects of ( A ↓ G ) which is collectively weakly initial.
proof: Proof.
- ⇒ G preserves limits by Lemma 4.9, and { ( F A , η A ) } is a singleton solution-set for each A.
- ⇐ By Lemma 4.10, the categories ( A ↓ G ) are complete, and they’re locally small since D is.
So we need to show: if A is complete and locally small, and has a weakly initial set { A i | i ∈ I }, then it has an initial object. First form P = ∏ ⁡ i ∈ I A i; then P is weakly initial. Now form the limit of the diagram with vertices P and P ′, with the morphisms P → P ′ being all endomorphisms of P.
Writing I → i P for this, I is still weakly initial. Suppose given I ⇉ g f B; let E → e I be their equaliser. There exists some h : P → E. Now i e h : P → P, but we also have 1 P : P → P, so i = 1 P i = i e h i. But i is monic, so we get e h i = 1 I, so e is split epic, and hence f = g. □
nothing: True

html: Definition 4.14 (Subobject). By a subobject of A ∈ ob ⁡ C, we mean a monomorphism A ′ ↣ A. We order subobjects by ( A ′ ↣ A ) ≤ ( A ″ ↣ A ) if there exists
We write Sub ⁡ C ( A ) for this preorder.
We say C is well-powered if every Sub ⁡ C ( A ) is equivalent to a small poset.
nothing: True

html: Lemma 4.15. Assuming that:
- a pullback diagram
where f is monic
Then k is monic.
proof: Proof. Suppose given D ⇉ m l P with k l = k m. Then f h l = g k l = g k m = f h m, but f is monic so h l = h m. So l and m are both factorisations of
through the pullback, and hence l = m. □
cloze1: True

html: Theorem 4.16 (Special Adjoint Functor Theorem). Assuming that:
- C and D are locally small
- D is complete and well-powered
- D has a coseparating set of objects
Then G : D → C has a left adjoint if and only if it preserves all small limits.
proof: Proof.
- ⇒ is Lemma 4.9.
- ⇐ Let A ∈ ob ⁡ C. As in Theorem 4.12, ( A ↓ G ) inherits completeness and locally smallness from D: it also inherits well-poweredness since subobjects of ( B , f ) in ( A ↓ G ) are those B ′ ↣ m B in D such that f factors through G B ′ ↣ G m G B. (Note that the forgetful functor ( A ↓ G ) → D preserves monomorphisms by Remark 4.8). And if { S i | i ∈ I } is a coseparating set for D, then { ( S i , f ) | i ∈ I , f ∈ C ( A , G S i ) } is a coseparating set for ( A ↓ G ).
So we need to show: if A is complete, locally small and well-powered and has a coseparating set { S i | i ∈ I }, then A has an initial object. First form P = ∏ ⁡ i ∈ I S i; now consider the limit of the diagram
whose edges are a representative set of subobjects of P.
If I is the apex of the limit cone, the legs I → P ′ of the limit cone are all monic by the argument of Lemma 4.15, and in particular I → P is monic, and it’s a least subobject of P.
If we had I ⇉ g f A, their equaliser E → I would be a subobject of P contained in I ↣ P, so E → I is an isomorphism, and hence f = g.
Given any A ∈ ob ⁡ A form the product Q = ∏ ⁡ ( i , f ) S i over all pairs ( i , f ) with f i A → S i and the morphism g : A → Q with π ( i , f ) g = f for all ( i , f ). Since the S i are coseparating, g is monic. We also have h : P → Q defined by π ( i , f ) h = π i for all ( i , f ).
Form the pullback
then l is monic by Lemma 4.15, so I ↣ P factors as I → B ↣ l P and hence we have I → B → k A. So I is initial. □
nothing: True

html: Definition 5.1 (Monad). A monad on a category C is a triple ( T , η , μ ) = 𝕋 where T : C → C, and η : 1 C → T and μ : T T → T satisfy the commutative diagrams
nothing: True

html: Definition 5.3 (Eilenberg-Moore algebra). Let 𝕋 = ( T , η , μ ) be a monad on C. By an Eilenberg-Moore algebra for 𝕋 we mean a pair ( A , α ) where A ∈ ob ⁡ C and α : T A → A satisfies
A homomorphism f : ( A , α ) → ( B , β ) is a morphism f : A → B satisfying
We write C 𝕋 for the category of 𝕋-algebras and homomorphisms.
nothing: True

html: Proposition 5.4. Assuming that:
- C a category
- 𝕋 a monad
Then the forgetful functor C 𝕋 → G 𝕋 C has a left adjoint F 𝕋, and the adjunction induces the monad 𝕋.
proof: Proof. We define F 𝕋 A = ( T A , μ A ) (an algebra by (2) and (3)) and F 𝕋 ( A → f B ) = T f (a homomorphism by naturality of μ). Clearly, F 𝕋 is functorial and G 𝕋 F 𝕋 = T.
We establish the adjunction using Theorem 3.7: its unit is η, and the counit 𝜀 ( A , α ) is just α (a homomorphism F 𝕋 A → ( A , α ), by (5), and natural by (6)).
The triangular identity
is just (1), and
is (4).
Finally, G 𝜀 F 𝕋 A = μ by definition of F 𝕋 A. So the adjunction induces ( T , η , μ ). □
cloze1: True

html: Definition 5.5 (Kleisli category). Let 𝕋 be a monad on C. The Kleisli category C 𝕋 is defined by ob ⁡ C 𝕋 = ob ⁡ C, morphsims A → f B in C 𝕋 are morphisms A → f T B in C. The identity A → A is A → η A T A, and the composite of A → f B → g C is A → f T B → T g T T C → μ C T C.
For the unit and associative laws, consider the diagrams
nothing: True

html: Proposition 5.6. Assuming that:
- C a category
- 𝕋 a monad
Then there is an adjunction C ⇄ G 𝕋 F 𝕋 C 𝕋 inducing the monad 𝕋.
proof: Proof. We define F 𝕋 A = A and F 𝕋 ( A → f B ) = A → f B → η B T B. F 𝕋 preserves identities by definintion, and preserves composition by
We define G 𝕋 A = T A, and G 𝕋 ( A → f B ) = T A → T f T T B → μ B T B. G 𝕋 preserves identities by (1), and preserves composites by
We verify the adjunction using Theorem 3.7: G 𝕋 F 𝕋 ( f ) = T f by (1) so G 𝕋 F 𝕋 = T and we take η as unit of the adjunction.
We define T A → 𝜀 A A to be T A → 1 T A T A. To verify the naturality square
the lower composite is T A → T f T T B → μ B T B and the upper one is T A → T f T T B → μ B T B → η T B T T B → μ B T B, which agree since (2) tells us that μ B η T B = 1 B.
The triangular identities become
and
Finally, G 𝕋 𝜀 F 𝕋 A = μ A, so ( F 𝕋 ⊣ G 𝕋 ) induces the monad 𝕋. □
cloze1: True

html: Theorem 5.7. The Kleisli adjunction ( C ⇄ C 𝕋 ) is an initial object of Adj ⁡ ( 𝕋 ), and the Eilenberg-Moore adjunction ( C ⇄ C 𝕋 is terminal.
proof: Proof. Suppose given ( C ⇄ G F D ) in Adj ⁡ ( 𝕋 ). We define K : D → C 𝕋 by K B = ( G B , G 𝜀 B ) (an algebra by one of the triangular identities for η and 𝜀, and naturality of 𝜀), K ( B → g B ′ ) = G g (a homomorphism by naturality of 𝜀). K is functorial since G is, G 𝕋 K = G is obvious, and K F A = ( G F A , G 𝜀 F A ) = ( T A , μ A ) = F 𝕋 A.
So K is a morphism of Adj ⁡ ( 𝕋 ).
Suppose K ′ : D → C 𝕋 is another such: then we must have K ′ B = ( G B , β B ) where β : G F G → G is a natural transformation since K ′ g = G g is a homomorphism K ′ B → K ′ B ′ for all g : B → B ′. Also, since K ′ F = F 𝕋, we have β F A = μ A = G 𝜀 F A for all A.
For any B, we have naturality squares
whose left edges are equal, and whose top edge is split epic, so we obtain G 𝜀 B = β B for all B. So K ′ = K.
We define H : C 𝕋 → D by H A = F A and H ( A → f B ) = F A → F f F G F B → 𝜀 F B F B. H preserves identities and satisfies H F 𝕋 = F, by the first triangular identity for η and 𝜀.
H preserves the composite A → f B → g C by
Also G H A = G F A = T A = G 𝕋 A and
G H ( A → f B ) = ( T A → T f T T B → μ B T B ) = G 𝕋 ( A → f B ) .
So H is a morphism of Adj ⁡ ( 𝕋 ). Note that H is full and faithful, since it sends A → f G F B to its traspose across ( F ⊣ G ).
If H ′ : C 𝕋 → D is any morphism of Adj ⁡ ( 𝕋 ), we must have H ′ A = F A = H A for all A, and since G H ′ = G 𝕋 and the adjunctions have the same unit, H ′ must send the transpose A → f B of A → f G F B to its transpose across ( F ⊣ G ). So H ′ = H. □

html: Proposition 5.8. Assuming that:
- 𝕋 a monad on C
Then
- (i) The forgetful functor G 𝕋 : C 𝕋 → C creates all limits which exist in C.
- (ii) If C has colimits of shape J, then G 𝕋 creates colimits of shape J if and only if T preserves them.
proof: Proof.
- (i) Suppose given D : J → C 𝕋; write D ( j ) = ( G D ( j ) , δ j ), and let ( L , ( λ j : L → G D ( j ) | j ∈ ob ⁡ J ) ) be a limit for G D. The composites T L → T λ j T G D ( j ) → δ j G D ( j ) form a cone over G B. So they induce a unique λ : T L → L. And λ is a 𝕋-algebra structure on L, since the identities λ η L = 1 L and λ ( T λ ) = λ μ L follow from uniqueness of factorisations through limits and it’s the unique lifting of the limit cone in C to a cone in C 𝕋. The fact that it’s a limit cone is straightforward.
- (ii) If G 𝕋 creates colimits then it preserves them, but so does F 𝕋 since it’s a left adjoint, so T preserves them too.
Conversely, given D : J → C 𝕋 and a colimit cone ( G D ( j ) → λ j L | j ∈ ob ⁡ J ) under G D, we need to know that ( T G D ( j ) → T λ j T L | j ∈ ob ⁡ J ) is a colimit cone to obtain T L → λ L (and that T T L is a colimit to verify that λ is a 𝕋-algebra structure). Otherwise, the argument is as before. □
cloze1: True

html: Lemma 5.9. Assuming that:
- C ⇄ G F D is an adjunction inducing the monad 𝕋 on C
- for every 𝕋 algebra ( A , α ), the pair F G F A ⇉ 𝜀 F A F α F A has a coequaliser in D
Then K : D → C 𝕋 has a left adjoint L.
proof: Proof. Write F A → λ ( A , α ) L ( A , α ) for the coequaliser. For any homomorphism f : ( A , α ) → ( B , β ) the two left hand squares in
commute, so we get a unique L f making the right hand square commute. As usual, uniqueness implies functoriality of L.
For any B ∈ ob ⁡ D, morphisms L ( A , α ) → B correspond to morphisms F A → f B satisfying f ( F α ) = f 𝜀 F A. If f ¯ : A → G B is the transpose of f across ( F ⊣ G ), then f ( F α ) transposes to f ¯ α : G F A → G B, whereas f 𝜀 F A transposes to G f. But we can write f = 𝜀 B ( F f ¯ ) by the proof of Theorem 3.7, so G f = ( G 𝜀 B ) ( G F f ¯ ). So f ( F α ) = f 𝜀 F A if and only if
commutes, which happens if and only if f ¯ : ( A , α ) → K B in C 𝕋.
Naturality of the bijection follows from that of f ↦ f ¯. □
cloze1: True

html: Definition 5.10 (Reflexive / split coequaliser diagram / G-split).
- (a)
We say a parallel pair A ⇉ g f B is reflexive if there exists r : B → A with f r = g r = 1 B. Note that F G F A ⇉ 𝜀 F A F α F A is reflexive, with common right inverse F A → F η A F G F A.
- (b)
By a split coequaliser diagram, we mean a diagram
satisfying h f = h g, h s = 1 C, g t = 1 B and f t = s h. If these hold, then h is a coequaliser of ( f , g ) since if B → k D satisfies k f = k g then k = k g t = k f t = k s h, so k factors through h, and the factorisation is unique since h is (split) epic. Note that any functor preserves split coequalisers.
- (c)
Given G : D → C, we say a pair A ⇉ g f B in D is G-split if there’s a split coequaliser diagram
in C. The pair ( F α , 𝜀 F A ) in Lemma 5.9 is G-split, since
is a split coequaliser diagram in C.
nothing: True

html: Theorem 5.11 (Precise Monadicity Theorem). A functor G : D → C is monadic if and only if G has a left adjoint and creates coequaliser of G-split pairs in D.
proof: Proof.
- (5.11, ⇒) Necessity of F ⊣ G is obvious. For the other condition, it’s enough to show that G 𝕋 : C 𝕋 → C creates coequalisers of G 𝕋-split pairs. This is a re-run of Proposition 5.8(ii): if ( A , α ) ⇉ g f ( B , β ) are such that
is a split coequaliser diagram, the coequaliser is preserved by T and by T T, so C acquires a unique algebra structure T C → γ C making h a homomorphism, and h is a coequaliser in C 𝕋.
- (5.11 ⇐ and 5.12) Either set of hypotheses implies that D has the coequalisers needed for Lemma 5.9, so K has a left adjoint L. So we need to show that the unit and counit of ( L ⊣ K ) are isomorphisms.
The unit ( A , α ) → K L ( A , α ) is the factorisation of G λ ( A , α ) : G F A → G L ( A , α ) through the (G 𝕋-split) coequaliser G F A → α A of G F G F A ⇉ G 𝜀 F A G F α G F A. But either set of hypothesis implies that G preserves the equaliser of ( F α , 𝜀 F A ), so this factorisation is an isomorphism.
The counit L K B → B is the factorisation of F G B → 𝜀 B B through the coequaliser of F G F G B ⇉ 𝜀 F G B F G 𝜀 B F G B. The hypotheses of Theorem 5.11 imply that 𝜀 B is a coequaliser of this pair, so the counit is an isomorphism. Those of Theorem 5.12 imply that the factorisation is mapped to an isomorphism by G, so it’s an isomorphism. □
nothing: True

html: Theorem 5.12 (Crude Monadicity Theorem). Assuming that:
- G : D → C preserves reflexive coequalisers
- G has a left adjoint
- G reflects isomorphisms
Then G is monadic.
proof: Proof.
- (5.11, ⇒) Necessity of F ⊣ G is obvious. For the other condition, it’s enough to show that G 𝕋 : C 𝕋 → C creates coequalisers of G 𝕋-split pairs. This is a re-run of Proposition 5.8(ii): if ( A , α ) ⇉ g f ( B , β ) are such that
is a split coequaliser diagram, the coequaliser is preserved by T and by T T, so C acquires a unique algebra structure T C → γ C making h a homomorphism, and h is a coequaliser in C 𝕋.
- (5.11 ⇐ and 5.12) Either set of hypotheses implies that D has the coequalisers needed for Lemma 5.9, so K has a left adjoint L. So we need to show that the unit and counit of ( L ⊣ K ) are isomorphisms.
The unit ( A , α ) → K L ( A , α ) is the factorisation of G λ ( A , α ) : G F A → G L ( A , α ) through the (G 𝕋-split) coequaliser G F A → α A of G F G F A ⇉ G 𝜀 F A G F α G F A. But either set of hypothesis implies that G preserves the equaliser of ( F α , 𝜀 F A ), so this factorisation is an isomorphism.
The counit L K B → B is the factorisation of F G B → 𝜀 B B through the coequaliser of F G F G B ⇉ 𝜀 F G B F G 𝜀 B F G B. The hypotheses of Theorem 5.11 imply that 𝜀 B is a coequaliser of this pair, so the counit is an isomorphism. Those of Theorem 5.12 imply that the factorisation is mapped to an isomorphism by G, so it’s an isomorphism. □
nothing: True

html: Definition 5.15 (Monadic tower). Let C ⇄ G F D be an adjunction where D has reflexive coequalisers. The monadic tower of ( F ⊣ G ) is the diagram
where 𝕋 is the monad induced by ( F ⊣ G ), and K and L are as in Theorem 5.7 and Lemma 5.9, and 𝕊 is the monad induced by ( L ⊣ K ) and so on.
We say ( F ⊣ G ) has monadic length n if we reach an equivalence after n steps.
nothing: True

html: Definition 6.1 (Filtered). We say a category C is filtered if every finite diagram D : J → C has a cone under it.
nothing: True

html: Definition 6.3 (Has filtered colimits). We say C has filtered colimits if every D : J → C, where J is small and filtered, has a colimit.
nothing: True

html: Lemma 6.4. Assuming that:
- C has finite colimits
- C has directed colimits
Then C has all small colimits.
proof: Proof. By Proposition 4.4(i), enough to show C has all small coproducts.
Given a set-indexeud family ( A j | j ∈ J ) of objects, the finite coproducts ∑ ⁡ j ∈ F A j, for F ⊆ J finite, form the vertices of a diagram of shape P f J = { F ⊆ J | F finite } whose edges are coprojections. P f J is directed, and a colimit for this diagram has the universal property of a coproduct ∑ ⁡ j ∈ J A j. □
cloze1: True

html: Theorem 6.5. Assuming that:
- J a small category
Then colimits of shape J commute with all finite limits in S e t if and only if J is filtered.
proof: Proof.
- ⇒ Let D : I → J be a diagram with I finite. We have a diagram E : I o p × J → S e t defined by E ( i , j ) = J ( D ( i ) , j ).
For each i, ( colim ⁡ J E ) ( i ) is a singleton since every D ( i ) → j is identified with 1 D ( i ) in the colimit, so lim ⁡ I colim ⁡ J E is a singleton.
But elements of lim ⁡ I E ( ∙ , j ) are cones under D with apex j, so if colim ⁡ J lim ⁡ I E is nonempty there must be such a cone for some j.
- ⇐ Suppose given D : I × J → S e t where I is finite and J is filtered. In general, the colimitof E : J → S e t is the quotient of ∐ ⁡ j ∈ ob ⁡ J E ( j ) by the smallest equivalence relation identifying x ∈ E ( j ) with D ( α ) ( x ) ∈ E ( j ′ ) for all α : j → j ′ in J. For filtered J, this identifies x ∈ E ( j ) with x ′ ∈ E ( j ′ ) if and only if there exists j → α j ″ ← α ′ j ′ with E ( α ) ( x ) = E ( α ′ ) ( x ′ ), and moreover if j = j ′ we may assume α = α ′.
Now, given an element x of lim ⁡ I colim ⁡ J D, we can write it as ( x i | i ∈ ob ⁡ I ) where x i ∈ colim ⁡ J D ( i , ∙ ) is an equivalence class of elements x i j ∈ D ( i , j ). If α : i → i ′ in I, then D ( α , j ) ( x i j ) and x i ′ j ′ represent the same element of colim ⁡ J D ( i ′ , ∙ ) so by repeated use of Lemma 6.2(ii) we can choose representatives in D ( i , j 0 ) for some fixed j 0, and by repeated use of Lemma 6.2(iii) we can assume that these representatives define an element of lim ⁡ I D ( ∙ , j 0 ). This defines an element of colim ⁡ J lim ⁡ I D mapping to the given element of lim ⁡ I colim ⁡ J D.
The proof of injectivity is similar: if two elements x , y of colim ⁡ J lim ⁡ I D have the same image in lim ⁡ I colim ⁡ J D we can choose representatives x j , y j in lim ⁡ I D ( ∙ , j ) and then find j → j ′ so that each of the components x i j and y i j map to the same element of D ( i , j ′ ) under j → j ′. So x = y in colim ⁡ J lim ⁡ I D. □
cloze1: True

html: Corollary 6.6. Assuming that:
- C a category of finitary algebras as in Example 5.14(a)
Then
- (i) The forgetful functor U : C → S e t creates filtered colimits.
- (ii) Filtered colimits commute with finite limits in C.
proof: Proof.
- (i) This is just like Example 5.14(a): Given a filtered diagram D : J → C and a colimit for U D with apex L, then L n is the colimit of U D n for all n, so each n-ary operation on the D ( j )’s induces an n-ary operation on L, and L also inherits all the equations defining C, so there’s a unique lifting of the colimit cone under U D to a colimit cone for D.
- (ii) Follows from (i) and Theorem 6.5, since U also creates finite limits (and reflects isomorphisms). □
cloze1: True

html: Proposition 6.8. Assuming that:
- C a small category
- C has finite limits
- F : C → S e t a functor
Then the following are equivalent:
- (i)
F preserves finite limits.
- (ii)
( 1 ↓ F ) is cofiltered.
- (iii)
F is expresible as a filtered colimit of representable functors.
proof: Proof.
- (i) ⇒ (ii) By Lemma 4.10, ( 1 ↓ F ) has finite limits so ( 1 ↓ F ) o p is filtered.
- (ii) ⇒ (iii) Consider the diagram ( 1 ↓ F ) o p → U C o p → Y [ C , S e t ] where U is the forgetful functor and Y is the Yoneda embedding. A cone under this diagram (with apex G, say) yields a family of morphisms C ( A , ∙ ) → λ ( A , x ) G for each x ∈ F A, subject to compatibility conditions which say that ( G f ) Φ ( λ ( A , x ) ) = Φ ( λ ( B , y ) ) for every f : ( A , x ) → ( B , y ) in ( 1 ↓ F ), i.e. such that x ↦ Φ ( λ ( A , x ) ) is a natural transformation F → G. So the cone ( C ( A , ∙ ) → Ψ ( x ) F | ( A , x ) ∈ ob ⁡ ( 1 ↓ F ) ) has the universal property of a colimit for the diagram.
- (iii) ⇒ (i) Functors of the form C ( A , ∙ ) preserve any limits which exist, so this follows from Theorem 6.5 plus the fact that colimits in [ C , S e t ] are computed pointwise. □
cloze1: True

html: Definition 6.9 (Lawvere theory). By a Lawvere theory, we mean a small category T together with a functor S e t f → T which is bijective on objects and preserves finite coproducts. A model of a Lawvere theory T in any category C with finite products is a functor M : T o p → C preserving finite products.
nothing: True

html: Lemma 6.10. Assuming that:
- T a Lawvere theory
Then the category of T-models in S e t is (equivalent to) a finitary algebra category in the sense of Example 5.14(a).
proof: Proof. Given a model M : T o p → S e t, we have M [ n ] ≅ M [ 1 ] n for all n. Also, any morphism M [ 1 ] n → M [ 1 ] p induced by a morphism [ p ] → [ n ] in T is determined by its composites with the projections M [ 1 ] p → M [ 1 ], so specifying M on morphisms is determined by its effect on morphisms with domain [ 1 ].
So, given a set A, specifying a model M with M [ 1 ] = A is equivalent to specifying operations α A : A n → A for each α : [ 1 ] → [ n ] in T, subject to ( v i ) A ( a 1 , … , a n ) = a i whenever v i : [ 1 ] → [ n ] is the i-th coprojection, and
commutes whenever
commutes. □
cloze1: True

html: Theorem 6.11. Assuming that:
- C a category
Then the following are equivalent:
- (i)
C is equivalent to a finitary algebraic category in the sense of Example 5.14(a). (Recall that these categories are those whose objects are sets with finitary operations satisfying some equations, and morphisms are homomorphisms between them.)
- (ii)
C is equivalent to the category of S e t-models of a Lawvere theory.
- (iii)
C ≃ S e t 𝕋 for a finitary monad 𝕋 on S e t.
proof: Proof.
- (ii) ⇒ (i) Let T be the full subcategory of C on the free algebras F [ n ], for n ∈ ℕ. Then T is a Lawvere theory, and for every object A of C, the functor C ( ∙ , A ) restricted to T preserves finite products, so it’s a model of T. This defines a functor T − M o d ( S e t ) ← Y S e t 𝕋; but T − M o d ( S e t ) ≃ S e t 𝕋 ′ for some finitary monad 𝕋 ′ on S e t, so we get a functor S e t 𝕋 → Y S e t 𝕋 ′ which is the identity on underlying sets.
In this situation, Y is induced by a morphism of monads 𝕋 ′ → 𝕋, i.e. a natural transformation 𝜃 : T ′ → T commuting with the units and multiplications. (Clearly, such a 𝜃 induces a functor S e t 𝕋 → S e t 𝕋 ′ sending ( A , α ) to ( A , α 𝜃 A )).
But we know 𝜃 [ n ] is bijective for all n, since elements of the free algebras on [ n ] are just morphisms [ 1 ] → [ n ] in T. But both functors are finitary, so 𝜃 A is bijective for all A, i.e. it’s an isomorphism of monads. □
cloze1: True

html: Definition 7.1 (Image, cover). We say a category C has images if, for every A → f B in C, there exists a least m : B ′ ↣ B in Sub ⁡ ( B ) through which f factors. We call m the image of f, and we say f is a cover if its image is 1 B.
We write ⇾ A ⇾ f B to indicate that f is a cover.
nothing: True

html: Lemma 7.2. Any strong epimorphism is a cover. The converse holds if C has equalisers and pullbacks.
proof: Proof. If f is strong epic, applying the definition to commutative squares of the form
shows that f is a cover.
For the converse, a cover A → f B is epic since it can’t factor through the equaliser of any B ⇉ h g C with g ≠ h. To verify the other condition, suppose given
then the pullback of m along h is monic by Lemma 4.15, and f factors through it, so it’s an isomorphism. So we get B → C by composing with the top edge of the pullback square. □

html: Definition 7.3 (Regular category). We say C is regular if it has finite limits and images, and image factorisations are stable under pullback, i.e. if the left hand square above is a pullback then so are both right hand squares. (This is equivalent to saying that covers are stable under pullback).
nothing: True

html: Proposition 7.5. Assuming that:
- C a regular
Then covers coincide with regular epimorphisms.
proof: Proof.
- ⇐ Regular epimorphism implies strong epimorphism by Exercise 21˙4.
- ⇒ Suppose ⇾ A ⇾ f B is a cover; let R ⇉ b a A be its kernel-pair, i.e. the pullback of
Suppose given g : A → C with g a = g b; form the image ⇾ A ⇾ e ↣ ( h , k ) B × C of A → ( f , g ) B × C. We’ll show h is an isomorphism, so that k h − 1 is a factorisation of g through f. h is a cover since h e = f is, so we need to prove h is monic.
Let D ⇉ m l I such that h l = h m; form the pullback
e × e factors as ⇾ ⇾ A × A ⇾ 1 × e A × I ⇾ e × 1 I × I, so e × e is a cover, and p is a cover.
Now f q = h e q = h l p = h m p = h e r = f r so ( q , r ) factors through ( a , b ). But ( h , k ) e a = ( f , g ) a = ( f , g ) b = ( h , k ) e b and ( h , k ) is monic, so e a = e b, so e q = e r, i.e. l p = m p. Also p is epic, so l = m. □
cloze1: True

html: Lemma 7.6. Composition of relations in C is associative if and only if C is regular.
proof: Proof.
- ⇒ Suppose given ⇽ A → f B ⇽ e C. Consider the relations
Composing the right hand pair first, we get
and thus we get
Composing the left hand pair first, we begin by forming the pullback
and we endup with the image of ( p , ! P ) : P → A × 1; so p must be a cover.
- ⇐ Suppose given relations A ↬ R B ↬ S C ↬ T D. If we form the pullbacks
then both T ∘ ( S ∘ R ) and ( T ∘ S ) ∘ R are the image of U → A × D. □
cloze1: True

html: Proposition 7.7. A ↬ R B is a left adjoint in R e l ( C ) if and only if it is of the form f ∙.
proof: Proof.
- ⇐ We show ( f ∙ ⊣ f ∙ ): the composite f ∙ f ∙ is just the kernel-pair R ↣ ( a , b ) A × A of f, and A ↣ ( 1 A , 1 A ) A × A factors through it. Also f ∙ f ∙ is the image of
so it contains ( 1 B , 1 B ).
- ⇒ Conversely, suppose R ↣ ( a , b ) A × B has a right adjoint R ′ ↣ ( b ′ , a ′ ) B × A. In forming R ′ ∘ R, we take the pullback
So the image of ( a p , a ′ p ′ ) contains A → ( 1 A , 1 A ) A × A, so a p factors as a cover followed by a split epimorphism, so a is a cover.
Now, in the pullback
q and q ′ are covers, but the image of ( b q , b ′ q ) is contained in ( 1 B , 1 B ) so b q = b ′ q ′. But a q = a ′ q ′, so R ′ = R ∘, a = a ′, b = b ′ and q = q ′. So a is monic, and hence an isomorphism, so R = ( b a − 1 ). □
cloze1: True

html: Proposition 7.8. Assuming that:
- C a regular category
- E is the class of equivalence relations in C
Then C eff = ( R e l ( C ) [ E ˇ ] ) l a is effective regular, and the embedding R e l ( C ) → R e l ( C ) [ E ˇ ] restricts to a full and faithful regular functor C → C eff which is universal among regular functors C → D where D is effective regular.
proof: Proof. We make the assignment A ↦ P A into a functor P : E → E and a functor P ∗ : E o p → E: given f : A → B, P f : P A → P B corresponds to the image of ∃ ⁡ A ↣ P A × A → 1 × f P A × B, and P ∗ f corresponds to the pullback of
Given C → g P A corresponding to R ↣ C × A, ( P f ) g corresponds to the image of R ↣ C × A → 1 × f C × B and similarly given S ↣ D × B, composing with P ∗ f corresponds to pulling back along D × A → 1 × f D × B.
Given a pullback square
in E,
commutes, since both ways correspond to the image of the left vertical composite in
where both squares are pullbacks.
Now, as in Example 5.14(d), we have that if E → e A ⇉ g f B is a coreflexive in E, then
is a split coequaliser coequaliser in E. Also, P ∗ is self-adjoint on the right, and it reflects isomorphisms by Exercise 7.17(v). The second assertion follows from Proposition 5.8(i). □
cloze1: True

html: Definition 7.9 (Topos). A topos is a regular category E for which the embedding E → R e l ( E ) sending f to f ∙ has a right adjoint. We write the effect of the right adjoint on objects by A ↦ P A, and the unit A → P A as { } A, and the counit P A ↬ A as ∃ ⁡ A ↣ P A × A.
nothing: True

html: Proposition 7.10. Assuming that:
- E a topos
Then there exists a monadic functor E o p → E. In particular, E o p has finite colimits and if E has limits of shape J then it also has colimits of shape J o p.
proof: Proof. We make the assignment A ↦ P A into a functor P : E → E and a functor P ∗ : E o p → E: given f : A → B, P f : P A → P B corresponds to the image of ∃ ⁡ A ↣ P A × A → 1 × f P A × B, and P ∗ f corresponds to the pullback of
Given C → g P A corresponding to R ↣ C × A, ( P f ) g corresponds to the image of R ↣ C × A → 1 × f C × B and similarly given S ↣ D × B, composing with P ∗ f corresponds to pulling back along D × A → 1 × f D × B.
Given a pullback square
in E,
commutes, since both ways correspond to the image of the left vertical composite in
where both squares are pullbacks.
Now, as in Example 5.14(d), we have that if E → e A ⇉ g f B is a coreflexive in E, then
is a split coequaliser coequaliser in E. Also, P ∗ is self-adjoint on the right, and it reflects isomorphisms by Exercise 7.17(v). The second assertion follows from Proposition 5.8(i). □
cloze1: True

html: Definition 7.11 (Support, totally supported, capital).
- (a)
By the support of an object A in a regular category, we mean the image of A → 1. We say A is well-supported if A → 1 is a cover.
- (b)
We say a regular category C is totally supported if every object is well-supported. We say C is almost totally supported if every object is either well-supported or a strict initial object, where we cann an object 0 strict if every A → 0 is an isomorphism. (Given finite limits, a strict object is initial since for any A there exists 0 → π − 1 0 × A → π 2 A, and the equaliser of any pair 0 ⇉ A is a).
- (c)
We say a regular category C is capital if its terminal object 1 is a detector, i.e. C ( 1 , ∙ ) reflects isomorphisms.
nothing: True

html: Lemma 7.12. Assuming that:
- C a locally small capital regular category
Then 1 is cover-projective.
proof: Proof. Since covers are stable under pullback, we need to show that every ⇾ A ⇾ 1 is split epic. If A ≅ 1, nothing to prove. If not, the projections A × A ⇉ A aren’t equal (since their coequaliser is ⇾ A ⇾ 1, by Proposition 7.5). So there exists 1 → A × A not factoring through their equaliser, so there exists 1 → A × A → A. □
cloze1: True

html: Lemma 7.13. Assuming that:
- C a small almost totally-supported regular category
Then there exists an isomorphism-reflecting regular functor I : C → C ′, where C ′ is also small and almost totally-supported, such that for every well-supported A ∈ ob ⁡ C there exists a morphism 1 → I A in C ′ not factoring through I ( m ) for any proper subobject m : A ′ ↣ A in C.
proof: Proof. Recall from Exercise 7.17: C regular implies C ∕ A regular for any A, and for any f : A → B in C pullback along f defines a regular functor f ∗ : C ∕ B → C ∕ A, which has a left adjoint Σ f : C ∕ A → C ∕ B sending g : C → A to f g. And f ∗ reflects isomorphisms if and only if f is a cover.
We’ll define C ′ as ( C ^ ) tv where C ^ is easier to describe.
To satisfy the desired conclusion for a single well-supported object A, enough to take ( ! ) A ∗ : C ≅ C ∕ 1 → C ∕ A, since ( ! A ) ∗ A = ( A × A → π 2 A ) acquires a point Δ : ( A → 1 A ) → ( A × A → A ) not factoring through ( A ′ × A → A ) for any proper A ↣ A.
More generally, for any finite list A 1 , … , A n of well-supported objects, we can take C ∕ ∏ ⁡ i = 1 n A i.
We define a base to be a finite list A → = ( A 1 , … , A n ) of distinct well-supported objecs of C. We preorder the set B of bases by A → ≤ B → if B → contains all the members of A →. We write ∏ ⁡ A → for the product ∏ ⁡ i = 1 n A i and if A → ≤ B → we write π B → , A → for the product projection ∏ ⁡ B → → ∏ A →. This makes A → ↦ ∏ ⁡ A → into a functor B o p → C.
Hence the assignment A → → C ∕ ∏ ⁡ A →, π B → , A → ↦ π B → , A → ∗ is ‘almost’ a functor B → C a t.
We now define C ^: its objects are pairs ( B → , f ) where B → is a base and f : A → ∏ ⁡ B → is an object of C ∕ ∏ ⁡ B →. Morphisms ( B → , f ) → ( B → ′ , f ′ ) are represented by pairs ( C → , g ) where C → is a base containing B → and B → ′ and g : π ∗ f → π ′ ∗ f ′ in C ∕ ∏ ⁡ C →, subject to the relation which identifies ( C → , g ) with ( C → ′ , g ′ ) if C → ≤ C → ′ and the pullback of g to C ∕ ∏ ⁡ C → is isomorphic to g ′.
Clearly, each C ∕ ∏ ⁡ B → sits inside C ^ as a non-full subcategory; so in particular C ≅ C ∕ ∏ ⁡ [ ] is a subcategory of C ^, C ^ is regular, and the inclusions C ∕ ∏ ⁡ B → → C ^ are isomorphism-reflecting regular functors.
Given a finite diagram in C ^, we can choose B → such that all edges of the diagram appear as morphisms in C ∕ ∏ ⁡ B →, and take the limit there, and this is a limit in C ^. Similarly for images.
Also, if a morphism f becomes an isomorphism in C ^, its inverse must live C ∕ ∏ ⁡ B → for some B →, hence f is an isomorphism C ∕ ∏ ⁡ B →.
We define C ′ = ( C ^ ) tv: the induced functor C → C ^ → C ′ is still isomorphism reflecting since C is almost totally-supported. □
cloze1: True

html: Lemma 7.14. Assuming that:
- C a small regular and almost totally-supported category
Then there exists an isomorphism reflecting regular functor C → C ^ where C is capital. Hence in particular, there is an isomorphism-reflecting regular functor C → S e t.
proof: Proof. Consider the sequence
C = C 0 → C 1 → C 2 → ⋯ ,
where each C n + 1 is obtained from C n by the construction of Lemma 7.13.
We define C ^ to be the pseudo-colimit of this sequence: objects are pairs ( n , A ) where A ∈ ob ⁡ C n, and morphisms ( n , A ) → ( m , B ) are represented by pairs ( p , f ) where p ≥ max ⁡ { m , n } and F : I A → I ′ B in C p, modulo the identification of ( p , f ) with ( p ′ , f ′ ) if p ≤ p ′ and f ′ = I f.
The proof that C is regular, and that the embeddings C n → C ^ are isomorphism-reflecting regular functors, is as in Lemma 7.13.
Given any non-invertible monomorphism A ′ ↣ A in C ^, it lives in C n for some n, so there exists 1 → A in C n + 1 not factoring through A ′ ↣ A.
But if A → f B isn’t monic in C ^, the legs R ⇉ b a A of its kernel-pair aren’t equal, so there exists 1 → r R not factoring through their equation, so 1 ⇉ b r a r A are distinct but have the same composite with f.
So C ^ ( 1 , ∙ ) reflects monomorphisms and hence reflects isomorphisms. □
cloze1: True

html: Theorem 7.15. Assuming that:
- C small and regular
Then there exists a set I and an isomorphism-reflecting regular functor C → S e t I.
proof: Proof. Let I be a representative set of subobjects of 1 in C, and for each U ∈ I consider the composite
C → ( ! U ) ∗ C ∕ U → ( C ∕ U ) tv → ( C ∕ U ) tv ^ → S e t ,
where the third factor is the functor of Lemma 7.14 and the fourth is represented by 1.
Given any non-invertible morphism A → f B in C, if U is the support of B then ( ! ) H ∗ f remains non-invertible in C ∕ U and its codomain is well-supported there, so it remains non-invertible in ( C ∕ U ) tv and hence in S e t.
So these functors collectively reflect isomorphisms. □
cloze1: True