From Cakes, custard and category theory by Eugenia Cheng:

Category theory emphasises the context in which we’re thinking about things, rather than just the things themselves.

Category theory seeks to highlight the context you’re thinking about at that moment, to emphasise its importance and raise our awareness of it. The way it does it [..] is by emphasising relationships between things rather than just their intrinsic characteristics.

Pure theory of functions.
- Not derived from set theory.
Part of pure mathematics.
- ie, not specific to some domain. Can be applied in a diverse set of fields. (eg: automata theory, type theory, etc)
Originated from the field of algebraic topology.

Something basic

Objects in categories
Morphisms: Maps between objects in the same category
Functor: Map between two categories
Natural transformation (=>): Map between two functors

General

Parallel morphism
- Two morphisms whose domains and codomains are same as that of each other.
- Eg: F: X -> Y and G: X -> Y
- https://ncatlab.org/nlab/show/parallel+morphisms

Limit of a functor

Given functor F: X -> Y
Limit of F is limF
limF is an object in Y such that:
- ∀x ∈ X, limF has a morphism to F x ??
This means the whole diagram can be thought of a single object via the morphisms

Morphism

Just functions?? Or are functions just a kind of morphisms??

1ₐ: identity on an object a in a category
composition: 'process of combining arrows'
- f∘g means g(f(x))

Monomorphisms

aka monic.

An arrow f:B→C is monic if for any two arrows g:A→B and h:A→B in the category, f∘h = g∘h then g = h.

I guess we can say

∀(g h:A→B), (f∘g = f∘h) -> (g = h)

Epimorphisms

aka epic.

Sounds like a 'reversed' form of monomorphism..

An arrow f:A→B is epic if for any two arrows g:B→C and h:B→C of the category, g∘f = h∘f means g = h.

Partial ordering

Reflexive
Asymmetric
Transitive

≤ₚ

Monotone function

Order preserving function. (Sort of like covariance in type theory??)

Monoid

(M,⋅,e) A set M equipped with:

a relation/operation ⋅ : (M, M) → M such that
- (x⋅y)⋅z = x⋅(y⋅z), ∀x ∈ M, y ∈ M, z ∈ M
- (ie, ⋅ is a relation from pairs of elements in M to elements in M)
an element e ∈ M such that
- e⋅x = x⋅e = x, ∀x ∈ M

TL;DR: has associative operation with identity element

Monoid homomorphism

A function f from a monoid to another.
Homomorphism => properties preserved.

f : M -> M'

where M and M' are monoids.

(M, ⋅, e) and (M', ⋅', e')

Properties:

f(e) = e'
f(x⋅y) = f(x)⋅'f(y)

Natural transformation

'Map between functors'
Possible when two functors have the same domain and codomain.

   α
F ==> G

This means that α is a natural transformation of F to G.

Natural isomorphism

A specialized form of natural transformation
It is natural equivalence in 1-category

Terminal object (1)

An object 1 of a category C is a terminal object if from any object q∈C, there exists a unique morphism from q to 1.

Terminal object may not exist and may not be unique.
But it is 'unique upto canonical isomorphism'. ¹
- So we can the terminal object of category C.

Adjunction

A relationship between two functors.

F: C ⇆ D : U

'Sort of' means that the categories C and D are 'kinda related'.

Then the functors F and U are said to be adjoint functors.

Monad

'a monoid in the category of endofunctors'. ʷ

Free monad: Monad with no additional constraints

Monads aka triples: (T, η, μ)

A functor T and two natural transformations: η and μ
T: C -> C
- A functor over the category C
η: A -> T A
- 'inclusion of value into computation'
- aka unit function
μ: T² A -> T A
- Flattening computation of computation to just a computation
- aka join function

        η               μ
T A ----->---- T² A ----->---- T A
   |             |              |
   |             |              |
id v             v μ            v id
   |             |              |
   |             |              |
   +----->----- T A -----<------+

Essentially, monad is a functor that comes with some additional rules (that supports some additional structure ⁸):

this functor is endomorphic (ie, from a category to the same category)
it comes with the two natural transformations: η and μ

The flattening function μ is called join in Haskell.

-- Like μ
join :: Monad m => m (m a) -> m a

-- Like η
return :: Monad m => a -> M a

Internal vs external binary operation

Internal binary operation => the 2 domains and codomain are the same sets
- ie, A -> A -> A
- https://mathyma.com/mathsNotes/index.php?trg=S1C2_Struct_IntBinOp&lng=en
External binary operation => (only?) one domain is not same as codomain
- ie, B -> A -> A ??
- https://www.cs.cas.cz/portal/AlgoMath/AlgebraicStructures/AlgebraicOperations/BinaryOperation.htm
- https://mathyma.com/mathsNotes/index.php?lng=en&trg=S1C2_Struct_ExtBinOp&treestate=00000000000000100000001000
- Eg: Scalar multiplication in linear algebra
  - a -> Vec a -> Vec a

Horizontal vs vertical composition

Vertical composition.

Consider the 2-category Cat.

Whiskering

Another name for horizontal composition in a 2-category ??

n-category

Category of categories at n levels.

0-category
∞-category: infinite levels

2-category

Category of categories.

Example is Cat
- objects: categories
- morphisms: functors
- functors: natural transformations

k-morphism

0 morphism: object
1 morphism: morphism
2 morphism
- In Cat (category of categories or 2-category), 2-morphisms are natural transformations between functors

A table

Category	Objects	Arrows
Set	Sets	Total functions
Pfn	Sets	Partial functions
Poset	Posets	monotone functions
Mon	Monoids	monoid homomorphism
Vect	Vector spaces	Linear transforms
Top	Toplogical spaces	Continuous functions
Grp	Groups	Group homomorphisms

Diagram

Diagrams in categories. Propreties of the category satisfied => the diagram commutes.

           f'
  X →-→-→-→-→-→-→-→-→-→- Z
  ↓                      ↓
g'↓                      ↓ g
  ↓                      ↓
  W →-→-→-→-→-→-→-→-→-→- Y
           f

If this diagram commutes, it means that f∘g' = g∘f'.

Many computer science people prefer to say f;g instead of g∘f (ie, by sort of reversing the order of functions).

Another example:

               succ-int
      int →-→-→-→-→-→-→-→-→- int
       ↓                      ↓
       ↓                      ↓
toreal ↓                      ↓ toreal
       ↓                      ↓
       ↓                      ↓
     real →-→-→-→-→-→-→-→-→- real
               succ-real

This says that toreal(succ-int(int)) ≡ succ-real(toreal(int)).

When a functional language is described as a category, commutative diagrams can be used to assert the validity of program transformations in which the order of operations is permuted.

Product

Products within a category. ie, with objects of the same category.

            C
  +-←-←-←-←-+-→-→-→-→-+
  ↓         ⇣         ↓
  ↓         ⇣         ↓
f ↓         ⇣ ⟨f,g⟩   ↓ g
  ↓         ⇣         ↓
  ↓         ⇣         ↓
  A-←-←-←-A x B-→-→-→-B
      π₁          π₂

(dashed arrows are assertions. Properties that should hold when the rest of the connections in the commutative diagram holds).

ie,

π₁ ∘ ⟨f,g⟩ = f
π₂ ∘ ⟨f,g⟩ = g

f:C → A
g:C → B

then

⟨f,g⟩:C → (AxB)

Coproduct

Written as one of these

A + B
A ⨿ B
A ⊔ B (well, this is notation for disjoint set)

Coproduct of two objects A and B is (A+B) along with two arrows ι₁ and ι₂.

ι₁: A → (A + B)
ι₂: B → (A + B)

f:A → C
g:B → C

then

[f,g]:(A+B) → C

      ι₁         ι₂
  A-→-→-→ A + B ←-←-← B
  ↓         ⇣         ↓
  ↓         ⇣         ↓
f ↓         ⇣ [f,g]   ↓ g
  ↓         ⇣         ↓
  ↓         ⇣         ↓
  +-→-→-→-→ C ←-←-←-←-+

Disjoint-union ʷ

Set theory instance of coproduct is disjoint-union.

It's like a union, where it's still possible to know which element came from which set.

(Kind of reminds one of a wedding with a prenuptial agreement.)

Eg:

A = {1,2,3}
B = {2,3,4}

A + B = {(1,A), (2,A), (3,A), (2,B), (3,B), (4,B)}

Functor

Forgetful functor:

Often denoted with U
'forgets' some structure

Example:

U: Monoid -> Set

which sends:

each monoid (M,⋅,e) to M
each monoid homomorphism (M,⋅,e) → (M',⋅,e) to M → M'

String diagrams

Hom-set

aka:
- internal hom-object
- internal hom
hom(X,Y): The set of all morphisms from object X to object Y (where X and Y are objects in the same category)
- ie, Set of morphisms from object X to object Y in a category C.
- For every f ∈ hom(X,Y), f:X → Y
hom(X,Y) may also be written as [X, Y]

Closed Cartesian Category (CCC)

Corresponds to simply typed lambda calculus.

T-algebra ʷ

Given a monad (T, η, μ) on a category C, T-algebra consists of objects of C acted upon by T.

A T-algebra (x,h) where:

x ∈ C
h is an arrow T x -> x (structure map of the T-algebra)

(Remember, T is an endofunctor of type C -> C where C is the category.)

T-algebras form a category known as Eilenberg-Moore category (Cᵀ).

Adjunction

A relationship between two functors.
In which case the two functors are known as adjoint functors (left adjoint and right adjoint).
Left and right adjoints are duals of each other

For example, for two categories C and D,

L: C -> D
R: D -> C

Extension

Kan extension
- Often written as 'Lan' to mean 'left Kan extension'
- https://math.stackexchange.com/questions/3827083/why-lan-for-kan-extension
Likewise for Kan lifts
- Lift: left kan lift
- Rift: right kan lift

New terms

Kan extension theorem
Double categories
dagger category
Kleisli category
Co-cartesian category
Adjunction
catamorphism
anamorphism
Large and small categories
- Meant to get around Russell's paradox
Ω-algebras, F-algebras

Some 'standard' categories

Cat: category of categories
- Objects: Categories
- Arrows/morphisms: Functors
Mon: category of monoids
CRing: category of commutative rings

References

Basic category theory for computer scientists - Benjamin C. Pierce
Categories, types and structures: An introduction to category theory for the working computer scientist - Andrea Asperti, Giuseppe Longo

Category theory vs Homotopy theory

	Homotopy theory	Category theory
Type	Spaces	Higher dimensional groupoids

Reboot

Morphisms: 'Functions' from one object of a category to another object (may be same) of the same category.
Functor: 'Function' from a category to another category.
- ie, functors are morphisms between categories.

Category theory in context

'It is traditional to name a category after its objects'

Category	Object	Morphism
Set	Sets	Functions
Top	Topological spaces	Continuous functions
Group	Set	Group homomorphism
Poset	Set	Order preserving maps

Morphisms aren't always functions.
- Why ???
- Eg: A category Mat_R where
  - Objects: non-zero ℕ
  - Morphisms: Between n and m is an nxm matrix
'Small and 'large' sets
- Sets and classes
- Via an extended form of ZF set theory axioms
- Way to get around Russell's paradox ??
Small category
- A category that has 'only a set's worth of arrows'
Locally small category
- Appears small when we are considering only pairs of objects in the category.
- Between any pairs of objects, there's only a set's worth of morphisms.
isomorphism: a morphism f: X → Y is an isomorphism if there exists a morphism g: Y → X such that:
- g∘f = 1_x
- f∘g = 1_y
Two objects X and Y are isomorphic is there exists an isomorphism between them.
- X ≅ Y
endomorphism: a morphism between the same object
automorphism: an endomorphism that is also isomorphic.
groupoid: category where all morphisms are isomorphisms.
- a group is a groupoid with exactly one object.

A functor F: C → D consists of:

For each object c ∈ D, there is a F c ∈ D
For each morphism (f: c → c') ∈ C, there is a morphism (F f: F c → F c') ∈ D

Awodhey

DBT: May think of categories as generalized groups. How??

Rel is a category

Object: sets
Arrows: relations
Identity: aRa = {(a,a) | a ∈ A}
Composition:
- R: A -> B
- S: B -> C
- S∘R: A -> C = {∃b∈B, aRb ∧ bSc | a∈A, c∈C}
Associativity of composition
- H∘(G∘F) = (H∘G)∘F

Continuing..

It's the arrows that really matter!

Functor

F:C->D gives a 'picture' of C in D

Some categories

Product category
Dual or opposite category of another category
- Objects = same, but arrow direction reversed
Arrow category
Co-slice category

Slice category (𝐂/C)

Slice category 𝐂/C of a category 𝐂 over an object C

Objects = arrows of 𝐂 whose codomain is in C.
(f:X -> C) (f': X' -> C) ∈ Arrow(𝐂), (g: X -> X') ∈ Arrow(𝐂/C),

C = base object

f : X  -> C
f': X' -> C
a : X  -> X'

f'∘a = f

Free monoid

Universal mapping property (UMP)

A monoid M(A) is generated from a set A.

Wikipedia: A monoid is free if it is isomorphic to the free monoid on some set.

DBT: I guess that's because there is only one such monoid? Due to UMP?

Notations:

|N| is the set underlying the monoid N.
A*: Free monoid on a set A

Given:

a function from a set A to a monoid M(A): i: A -> |M(A)|
- DBT: is A the generating set
a monoid N
a function f: A -> |N|

then there is a unique monoid homomorphism f̅: M(A) -> N such that:

|f̅|∘i : A -> |N|

DBT: 'monoid is a category with only one object'. How?

PS1

Background

Hom-set of a category: set of morphisms between two given objects of the category:

Hom(X, Y)

A functor does this:

F: C -> D
F: Hom_C(X, Y) -> Hom_D(F(X), F(Y)), where X,Y∈C

Faithful functor (injective):

Functor that is injective on hom-sets (ie, 1-to-1)
No morphism2 is mapped onto from multiple morphism1-s.

Full functor (surjective):

Functor that is surjective on hom-sets (ie, onto)

Fully faithful functor = bijective

1

Example of a category and functor from CS or math:

Categories:

STLC (Church or Curry)
- Arrows = functions
  - Identity = identity function
  - When you take the arrow, function is applied
- Objects = terms
UTLC
Functor with domain as STLC = type erasure to get UTLC from STLC
Functor with codomain as STLC = from category of sml to STLC

—

Is ℕ and ℤ isomorphic ???? No, I guess. But why?

3

Every monoid is like an untyped program.

skip = identity
sequence = operation

Resources

https://www.logicmatters.net/categories/
Categories with racket
Categories and λ-calculus: https://www.lix.polytechnique.fr/Labo/Samuel.Mimram/teaching/cat/

Glossary

Groupoid = category where every morphism is an isomorphism
Forgetful functor: functor that drops some properties of the domain category
Sub-category: Restrict to some objects and morphism of parent category while still remaining a category
Order theory terms
- Pre-order: refl, trans
- Poset or Partial order: refl, anti-symm, trans
- Total order: Partial order where every element is related
Scott domain ???
Concrete category: One that can be defined in terms of sets and functions over sets.
Cayley representation of a group/category
Dual of a category C: Same objects as C, but direction of arrows is reversed
Atomic boolean algebra: ???
- Atom of boolean algebra or poset: https://ncatlab.org/nlab/show/atomic+Boolean+algebra
Complete boolean algebra: ???
Universal algebra: Study of algebras themselves. Not just instances of algebras.
Pointed set: Set together with an element that set called the base point.
- aka based set, rooted set
Base map: Map functions that map between pointed sets
Small category: Collection of objects is a set, collection of arrows is a set
- Not the same as concrete categories
Cat: category of small categories
- This is a large category
Locally small category
- if Hom(X, Y) = {f ∈ ℂ | f: X → Y} is a set
- ie, if the collection of all morphisms between any pair of objects is a set
- Many large categories are locally small. Eg: Cat
A rule of thumb??
- X => left, co-X => right ✗
- Eg: in relations, domain is in left. Co-domain is in right
- Slice category. base object is in right. Co-slice cat => base object in left

Baez, J. and Stay, M., 2011. Physics, topology, logic and computation: a Rosetta Stone (pp. 95-172). Springer Berlin Heidelberg.

↩︎

Something basic

General

Limit of a functor

Category

Example: Set

Example: Categorical logic

More examples

Morphism

Monomorphisms

Epimorphisms

Partial ordering

Monotone function

Monoid

Monoid homomorphism

Natural transformation

Natural isomorphism

Terminal object (1)

Adjunction

Monad

Internal vs external binary operation

Horizontal vs vertical composition

Whiskering

n-category

2-category

k-morphism

A table

Diagram

Product

Coproduct

Disjoint-union ʷ

Functor

String diagrams

Hom-set

Closed Cartesian Category (CCC)

T-algebra ʷ

Adjunction

Extension

New terms

Some 'standard' categories

References

Category theory vs Homotopy theory

Reboot

Category theory in context

Awodhey

Rel is a category

Continuing..

Slice category (𝐂/C)

Free monoid

Universal mapping property (UMP)

PS1

Background

1

3

Resources

Glossary