Representation and Symbols
- If we’re talking about a one-element set we often declare the single element to be an asterisk ∗ to remind ourselves that it has no meaning. The resulting one-element set is then written {∗}.
Chapter 1 and 2
- Rigorous logic being problematic is starting point for category theory as well.
- “Abstraction is the process of deciding on some details to ignore in order to ensure that our logic does work perfectly.” e.g. Think of the difference between map and territories in a way. Though maps seem very different, having different maps helps us understand territory better using connections. And same kind of relationships can be translated and reused.
- All about zooming in and out.
- Category Theory always needs context first. Similar to BR The Courage of Being Disliked where it says all problems are interpersonal problems. Unless there are more than one node a.k.a a relationship, there is no problem at all.
- “We will see that category theory is a framework that achieves a remarkable trade-off between good behavior and expressive possibilities. If a framework demands too much good behavior then expressivity is limited, as in a totalitarian state with very strict laws. On the other hand if there are too few demands, then there is great potential for expressivity, but also for chaos and anarchy. Category theory achieves a productive balance between those, in the way it specifies what type of relationship it is going to study.”
- Not limited to numbers. Not limited to equations. Not limited as long as “sameness” can be defined properly.
- Doesn’t look into a node. Only role it plays in context.
- Different contexts, same relationships even results to different understanding, different conclusions.
- If category theory is theory of mathematics, then higher dimensional category theory is theory of categories.
- Logic + Abstraction
- “I would say that philosophy uses logic, but applies it to real questions about life experiences. Art uses abstraction, but does not primarily build on its abstractions by logic. Math uses logic and abstraction together. It uses logic to build rigorous arguments, and uses abstraction to ensure that we are working in a world where logic can be made rigorous.”
- Abstraction in definition is very close to trying for generalization in AI. Trying to find good abstraction that just covers essentials between nodes without having everything.
- Stripping out the details to reveal a relationship sturcture is what category theory is all about.
- Moral abstractions require us to make sure we are using the same type of relationship between nodes, else the idea of sameness cannot be applied.
- The goal isn’t to find most abstract possible level. Goal is to find a good enough abstraction in order to solve a problem.
- Different context, different truths.
- By stripping the details, we can always take everything to the same level but that might not be what we need. Too much details is bad, so is too much abstraction. Rather than even be fixed at certain level, we can move between different levels and see a good picture about our problem at hand.
- Addition and multiplication:
- Both are binary operations.
- Both are Associative
- Both are Commutative
- Addition is reversible by subtraction while multiplication is not always reversible by division.
Process of moving between levels of abstraction :
- See an analogy between some different things (a.k.a defining the first level)
- Specify what we are regarding as causing the analogy (a.k.a. defining the direction from this first level)
- Regard that thing as a new, more abstract, concept in its own right(a.k.a. taking the direction and specifying this second level)
- Be comfortable with new abstract concepts without thinking that they are abstract (a.k.a. understanding this second level in its own right as if first level didn’t exist)
- See analogy between some of these new concepts (a.k.a. trying to find new direction from this level)
- Iterate (a.k.a loop )
Example
- Start with statement " If we add two numbers, the order we put them in doesn’t matter. " [ First level ]
- By converting them to numbers, “Given any numbers a and b, a+b = b+a” [ Defining the direction: From letters to numbers a,b ]
- Now this process of a and b to a+b or b+a is a concept called addition. [ Point 3 and 4 together ]
- Process that takes two numbers and produces a number a . b [ Taking a new direction of abstraction from addition ]
- Now from that we can take it in direction of multiplication [ a * b = c which is multiplication ]
In conclusion, the top level becomes abstract binary operation. This is starting point to so many branches of mathematics being applied starting from categorical principles.
Simple example of abstracting to binary operation:
More complex example
Chapter 3 Patterns
- Patterns are aesthetic and functional.
- e.g. Repetitive tiles
- base 10 numbers
- Category theory is all about patterns a.k.a the underlying structure
- When you analyse patterns deeply, we can go layres deep to find patterns within patterns as well.
- Difference of levels: mother-daughter relation between generations becomes a different relation when skipped a level: grandmother-granddaughter
- Visual patterns help derive analogy, abstraction of the structure of those patterns help reason and do more complex operations with those analogies.
- We should be able to see simple patterns visually and blow them to understand high level patterns that are complicated to visualize.
Example of using category theory pattern matching in real life conflict
Disagreement usually arises in two forms if we follow category theory ardently. Suppose A and B are two ideas, and X and Y are abstract levels of categories:
- Someone sees principle W at work which is behind A, so A and B are not analogous.
- They see another general principle Y that they think first person is invoking. And that makes some other C analogous. Then they object to that.
Chapter 4 Context
- In category theory, truth depends on context.
- Even things we generally assume as true will be questioned using a different context. So, we need to be very flexible with changing contexts.
Distance
- When we take distance and try to abstract it to a circle on a line grid, we have to say we move by a fixed distance on the grid. Then that abstraction of our understanding of distance on a grid with limitation of fixed distance from a center point gets us this shape.
- So, it tells us that we can create so many different types of distances based on the restrictions or rules. So, the context matters for truth.
Different context of numbers we use in daily lives
- 2 hours after 11 isn’t 13 in a 12-hour clock. It’s 1. It doesn’t need to be just about 12. We literally can have n-hour clocks.
- Rotating something by 90 degrees four times makes it back to original. a.k.a 1 + 1 + 1 + 1 = 0
- Mixing paint 1 + 1 = 1
Chapter 5 Relationships
- So context is defined by relationships or vice versa.
- If we relate fruits by color, we get a different context than when we relate fruits by taste.
- Distance is a type of relationship but depending on whether its streets, airspace, it can be totally different. So, context matters.
- Zero world: Multiple items can look as if they are same in certain context but when we take them somewhere else, they might start looking different.
Example : Family Relationship
Now, same abstraction can be used with ease to other contexts as well.
Example of mapping the relationship
Mapping relation for rotating a square.
Arithmetic Relationship
Similar to squares, we have the relationship but this table is not finite. So, we don’t even need to have full table to properly understand the pattern as a result of the relationship.
Quadrilaterals
By releasing certain conditions or applying certain conditions, we get to more general cases.
When we draw the same composition like a venn diagram, it looks like this:
But still we have problems:
- All rhombuses are kites, so the kite circle needs to contain the entire rhombus circle.
- A kite that is not a rhombus is also not a parallelogram or a trapezoid, so the kite circle needs to stick out into the random quadrilateral part without overlapping the parallelogram or trapezoid circles.
Lattices of factors
We see a similar type of relationship structure. Also by drawing such a structure, we can go into many more details like: what does each face of cube represent? What are edges telling us? Can we know the shape before drawing it based on prime factors it can have etc. etc.
Inferring patterns from structure
e.g. The square faces tell us things like the fact that multiplying by 2 and then 3 is the same as multiplying by 3 and then 2, i.e. that multiplication is commutative.
The dimension of the shape can give us how many prime factors it has. If its a 2D shape, it only has two prime factors. If its 3d, it has 3 prime factors.
Inferring other types of relationships from this one
We can clearly see that same structure arises in subset relationship.
And not just maths, anywhere :
Now, what goes higher in hierarchy can be different e.g. In lattice of factors, 6 goes higher than 7 because its not prime and has two prime factors. So, we need to understand what we are defining by levels. Our levels can have meaning, hierarchy or not. Most conflict happen because we don’t agree on level of abstractions.
Chapter 6 Formalism
- Mathematical notation is used for efficiency and abstraction. It becomes so complicated if we had to do all our maths using English language.
- Concise notation to make complex entities simpler which is abstraction at its core.
- e.g. 3 + 3 + 3 + 3 replaced by 3 x 4
- Exponential growth vs linear growth when we talk in that terms, maths and science people immediately know what is growing faster.
Metric Spaces
- Different types of distances are called “metrics”.
- Some criterion for distances are:
- Distance is a number
- Distance isn’t negative
- Distance from same point to same point should be zero. We say d(A, B) = 0 if and only if A = B.
- Symmetry d(A, B) = d(B, A)
- Detours [ Triangle Inequality ] If you stop off somewhere along the way it should not make your distance any less. At best it won’t change the distance, but it might well make the journey longer. d(A, X) + d(X, B) >= d(A, B)
- So, these criterion define distance. By releasing certain criterion, we might get different examples.
Basic Logic
Logic is based on logical implication. A > B A if B written as B < A
A only if B written as A => B
Modular Arithmetic (Very interesting example indeed )
How do we say “is a multiple of 6” using formal language
Start by using another random letter “k” to represent whole number, so multiple of 6 is 6k. However, we used an extra letter. 6k = m
So, instead of using that notation, mathematicians came up with this notation: 6 | m which means “6 divides m” or “6 goes into m” which is saying the same thing “multiple of 6” but other way around.
So, when we talk about modulo “a and b occupy the same position” we say “a-b| 6” for modulo arithmetic table. Then mathematicians said “congruent modulo 6” or “congruent mod 6” to say this thing for short. In notation form, a ≡ b (mod 6)
Now using the same notation, we write “integers modulo 6” as \(\mathbb{Z}_{6}\).
\(a \in \mathbb{Z}\) is shorthand for “a is an element of \(\mathbb{Z}\).
Example definition
- Let \(a, b \in \mathbb{Z}\) Then \(a \equiv b (mod 6)\) if and only if 6|b-a.
Why didn’t we write => instead of “if and only if” because we are trying to define the thing on the left using thing on the right. Not trying to create equivalence.
- Let \(n \in \mathbb{Z}_{+}\) and \(a,b \in \mathbb{Z}\). Then \(a \equiv b\) (mod n) iff \(n | b -a\).
Also try to think of informal proof before trying to prove it formally and that will make most things easier.
Chapter 7 Equivalence Relations
- Category theory if allowed to study with any kind of relationship can get really chaotic. So, mildest conditions for type of relationship is defined.
- Equality without a good condition is hard. So, reasons for equality need to be defined.
- Relations really can be abstract a RELN b.
- Reflexivity involves only one object at a time, Symmetry involves two, Transitivity involves three. But it doesn’t mean these three or two need to be distinct objects.
Reflexivity
- A relation is called reflexive if it sees everything related to itself. i.e. every object satisfies an abstract relation a RELN a. This is property of relation, not of object/node.
Asking questions about reflexivity of relations
Proving via counter example
Symmetry
- If its same both way around.
- If definition says a RELN b => b RELN a, then if we switch the roles of a and b we get, b RELN a => a RELN b. so, combining those we get: a RELN b <=> b RELN a.
- So, statements are logically equivalent. a RELN b and b RELN a.
Example where its symmetric
Example where its not symmetric
Transitivity
The case of less than relation which was neither symmetric nor reflexive is at least transitive.
Equivalence Relation
- If a relation RELN on a set S is reflexive, symmetric and transitive.
The relation itself depends on the kind of surface we are dealing with. If its a globe, how do we say what’s east. So, due to such reasons we need to restrict our context first.
- Equivalence relations are too well behaved that they are not interesting. So, we relax our conditions.
Chapter 8 Categories
- Based on the equivalence relation and relaxing of it, we are ready to define category. It contains three parts:
- Data
- Structure
- Properties
Data
- Objects can be anything
- world “S” of objects we are going to consider category \(\mathcr{C}\)
- Relationships can be “less than”, “equals” etc. We call them Morphisms or Arrows.
- We really aren’t asking whether they are equal in category. We are asking “in what ways are these objects related?”
- No limit to number of arrows that can go from one object to other.
- When we focus on set of objects we write collection of arrows as \(\mathcr{C}(a,b)\). Or we can write in terms of Homsets in Category Theory homc(a,b). Set of these morphisms is called homset.
Structure
- We don’t go with stricter conditions of equivalence like last time. We relax conditions.
- For any object a, there must at least be an arrow to itself called identity.
- Composition. For every relation that goes from a to b and b to c there will be a composed arrow that goes from a to c.
- They don’t have to be transitive or true/false. We just need to ensure that a morphism exists.
- Arrows have to be composable. Target of first one must match the source of second and so on.
Properties
- One for identity
- One for composing more than two arrows
- Also called axioms. These are the ones governing structure.
Identity Morphism
- Does not do anything. Starts at the object and returns the object.
- e.g. 0 is the identity for addition on real numbers.
- So, here : f ˆ 1a = f = 1b ˆ f
Composition Morphism
This is how we compose these arrows. This is associativity. h ˆ ( g ˆ f ) = (h ˆ g) ˆ f
Formal definition
A category C consists of:
- Data
- Objects: a collection obC of objects
- Arrows: for objects a, b ∈ obC, a collection C(a, b) of arrows a -> b
- Structure
- Identities: for any object a ∈ obC an identity arrow a -1a-> a
- Composition: for any arrows a -f-> b -g-> c, where a,b,c are nodes and f,g are relations. a composite arrow a -g◦f-> c
- Properties
- Unit laws: for any arrow a -f-> b, f ◦ 1a = f = 1b ◦ f
- Associativity: for any arrows a -f-> b -g-> c -h-> d, (h ◦ g) ◦ f = h ◦ (g ◦ f)
- Arrows are also called morphisms, and the composite g ◦ f is also written gf .
We loosened equivalence to this. And for equality, we will look at invertibility which is more subtle notion of sameness in categories so that they are more useful to build everything.
Sizes
- Category where objects and morphisms form a set is called small.
- Category where each individual collection C(a,b) is a set, then its called locally small. In this case, they might form a collection, not a set.
Geometry of associativity
This gets translated into a full pyramid like 3d image.
Drawing a category
- Usually don’t draw identity arrows. Assumed to exist there.
- Omit arrows whose existence can be deduced from composition.
- Physical positioning doesn’t affect structure.
Chapter 9 Basic Maths
- Trivial symmetry : A symmetry that might not be considered useful in real life. e.g. rotation by 0 degrees for a square is its identity arrow which is a trivial symmetry.
- For a category we draw from factors, we started by pointing arrows from prime factors toward the number. If we reverse the arrows, it still contains same information as the last category. Such a category where arrows are reversed, is called a Dual Category.
Category Theory in Number system
- Thinking of these numbers in terms of addition
- objects : natural numbers
- arrows : a -> b whenever a ≤ b
- Every other number is related to itself and every other but since these can be derived from plain relation we can write it as: 0 -> 1 -> 2 -> 3 …
- We need a less than or equal to or greater than or equal to to satisfy the identity constraint. Now, we just know what dual here looks like as well.
Summing up equivalence relations
Chapter 10 Ordered Sets
Tosets
- Totally ordered sets
- Category in which for all objects a,b there is exactly one arrow between them.
- Can’t have arrow both ways from a -> b and b -> a unless a = b in that case both arrows mean identity.
- e.g. Category of natural numbers with relation a ≤ b is a totally ordered set according to the definition.
Examples of when its not toset
Two objects on the right don’t have morphism betwen them. Same for two objects on the left on second one. Two arrows from one object to another on the third one. Multiple arrows even though one object on the fourth one.
Non-categorical definition of ordered set
An ordered set is a set S equipped with a binary relation ≤ satisfying
- reflexivity: a ≤ a for all a ∈ S
- antisymmetry: if a ≤ b and b ≤ a then a = b
- transitivity: if a ≤ b and b ≤ c then a ≤ c
- trichotomy: for all a, b ∈ S , a ≤ b or b ≤ a
Now coming to categorical definition from this one
Reflexivity is a special case of trichotomy: if we put a = b in the definition of trichotomy we get “a ≤ a or a ≤ a”, which is reflexivity. It’s useful to state it as a condition though, because when we relax the conditions later we will need to specify it. In the categorical definition we don’t need the other conditions because:
- Reflexivity comes from the category having identities.
- Transitivity comes from composition in the category.
- Antisymmetry and trichotomy both come from there being exactly one arrow between a and b: antisymmetry comes from there being at most one, and trichotomy from there being at least one.
Posets
- Partially ordered sets
- Relaxing the condition of tosets saying there can be at most one arrow between two objects, but possibly none.
- The condition we need to drop is trichotomy, as we now want to allow pairs of objects that are not related either way round.
Non categorical definition of posets
A partially ordered set or poset is a set S equipped with a relation ≤ satisfying:
- reflexivity: a ≤ a for all a ∈ S
- antisymmetry: if a ≤ b and b ≤ a then a = b
- transitivity: if a ≤ b and b ≤ c then a ≤ c.
Chapter 11 Small mathematical structures
- For a category to be defined, we can just draw its structure and call it an abstract category.
- A set is a category with no arrows between objects, just the identity arrow. Such a category is called Discrete category. Also we call identity arrows “trivial”, so discrete category can be thought of as one that has no non-trivial arrows.
Monoids
Suppose every time we compose that loop with itself we get a new arrow. In that case this category has only one object but infinitely many arrows. If we call the basic arrow f then:
- There is also f ◦ f which we might write as f2.
- Then there is f ◦ f ◦ f which we might write as f3.
- In fact there’s fn for every n ∈ N.
Note it makes sense to include 0 in N here, with f0 = 1, the identity. So, even if its a loop, its not identity by default. We have multiple relations from itself to itself.
Example would be when natural numbers are not written as separate blobs but instead written as infinite loop relations like +1, +2, +3 … etc. We instead now have a separate arrow for each natural number instead of objects. Composition was like multiplication, but really it was addition of natural numbers in the exponent: fn ◦ fm = fn+m.
By now, we have seen three ways of putting category structure on natural numbers:
- Using factors
- Using size
- Using addition
In the first two, numbers were objects. How arrows formed were different. Now, in third case, we assumed one object and mapped everything into the arrows instead. So, this is a different abstraction that is really powerful.
Definition
A category with only one object is called a monoid.
Consequences
Since there is just one object, all arrows are composable. Now, coming back to definition of binary operation, composition is generalization of binary operation. So, when there is just one object, composition is a binary operation on the arrows.
Non categorical definition
A monoid is a set M equipped with an identity 1 and a unital and associative binary operation ◦. The monoid is sometimes written fully as (M, ◦, 1).
- unital means that for all m ∈ M, 1 ◦ m = m = m ◦ 1
- associativity means that for all a, b, c ∈ M, (a ◦ b) ◦ c = a ◦ (b ◦ c)
Relation between these two
- Objects of monoid
- Single Dummy object and arrows
- Identity object
- Identity arrow
- Binary operation
- Composition
- Unitality
- Unitality
- Associativity
- Associativity
In such case where there is one object, we really don’t give importance to the object and make it all about the arrows and composability.
Conclusion
- Natural numbers are monoid under addition. Free monoid on one generator. One object, one loop and its repeated composition makes a new arrow.
- Now coming to mod(n) category, we impose extra rules because it loops on itself like f5 = f4 . f = 1 . f = f . So, these extra loops on mod(4) so this becomes a monoid but with constraint f4 = 1 which makes it integer mod(4). This can be generalized to Zn with fn = 1 since it loops on itself it won’t need two different kind of relationships to get all numbers. e.g. For natural numbers, we cant get to negative numbers by just addition. But, in this case, since it loops after a certain point, they become composable for integers as well. Such a beautiful concept.
Groups and Groupoids
- Integers are different from natural numbers in having negative numbers, which are inverses with respect to addition, also called “additive inverses”.
- Inverses undo the binary operation wrt that element, taking back to identity.
- An inverse for an element a of a monoid (M, ◦, 1) is an element b such that a ◦ b = 1 and b ◦ a = 1.
- In general definition of monoids, they don’t have inverses for every element. If a monoid does, then that’s a special case. In case of normal natural numbers under addition, only 0 has a additive inverse. Others don’t. But, in mod operation under integers Zn, there are inverses for each element.
- e.g. in mod(4) we have inverses like this:
- 0 – 0
- 1 – 3
- 2 – 2
- 3 – 1
- e.g. in mod(4) we have inverses like this:
- Now, coming back to monoidal representation: The arrow fk has inverse fn−k since fk ◦ fn−k = fn = 1.
Definition
Group is a monoid in which every element has an inverse.
Non categorical definition
A group consists of a set G equipped with a binary operation ◦ and an identity element 1 satisfying unit laws and associativity, and such that every element has an inverse with respect to ◦
Note that in a category coming from an equivalence relation the arrows are restricted — there can be at most one from any object a to an object b. By contrast in a category coming from a group the objects are restricted: there is just one, the “dummy” object. This is the main idea.
Tables arising from binary operation on a group are called Cayley tables. In such tables, each element appears once in each row and each column. Used to represent small categorical relationships.
Extras
- Groups are often introduced directly via symmetry. Two symmetries of a given shape can be combined to produce another symmetry of that shape, and that structure forms a group.
- Symmetry doesn’t have to be visual. e.g. in x2 + 2xy + y2 = 0, x and y can be interchanged and that’s symmetry in equations. Such group theory is called algebraic group theory.
- Algebraic topology starts from the idea that you can take a topological space and encapsulate some of its structure as a group.
- Algebraic geometry comes from studying geometry by encapsulating some of its structure as a group.
- Algebraic number theory studies numbers via group structures.
Defining a groupoid
- A groupoid is a category in which every arrow has an inverse. Not expecting it to be a monoid, but expecting it to have inverses.
- Thus, by implying and relaxing certain conditions, we get different types of category.
Points and Paths
- Now studying shapes and shape of space.
- Topology studies what makes the shape of one space really different from the shape of another.
- e.g. If you just moved a wall inwards slightly then the size of the space would change but in some sense not really the shape. Likewise if you shrank the entire building.
- Given space X, we can make category with:
- objects : points in X
- arrows : arrow a -> b is a path from a to b in that space
- Now comes the question: how do we say if two paths are different, and hwo do we get a composition on these paths.
- There comes the definition of homotopy to define what really counts as same path. It tries to see if the paths by continuous deformation can go from one to another without breaking or not. If it doesn’t break, then those paths would be counted as same, etc. etc.
- So, we just wanted to see that we can create category to study topology as well.
Chapter 12 Sets and Functions
- A first example of large category of mathematical structure.
- By zooming out, we study larger structures.
- Poset is a set of objects equipped with some ordering on it. So, the collection of all possible posets is also a category.
- From one smaller mathematical structure, we built a larger structure. Same can be done for monoids, groups, spaces etc. And the starting point for all these structures is an underlying set.
- So, sets are special in some way and then the maps between structures is then concept of a function.
Comparisons with set theory
- When mathematicians tried to make the idea of numbers very precise, they found they had to deal with sets first, and then build numbers out of particular sets. When mathematicians became really serious about developing mathematics completely rigorously, they started with sets. Set theory was developed as a foundation of mathematics.
- Set theory starts with the concept of membership as a basic concept, and builds up from the idea of elements being members of sets. By contrast, category theory builds up from the notion of relationships which is why our basic concepts in category theory are elements (objects) and relationships (arrows) between them, rather than membership. Comparing set theory with category theory for same definition of sets.
- Category theory takes sets and functions as the basic starting point, rather than sets and membership. But these ideas are converse of each other. From memberships, functions can be built and vice versa. Its like choosing what you consider as more fundamental and start there.
Function
- In categorical approach, function is a relationship between sets. Goes from one set to another.
- There are restrictions on what is a function. Classical definition of a function with domain and co-domain.
- Every element needs to map to at least some output.
- One input can’t produce two different outputs. However, we can have multiple inputs producing one output.
- Let A and B be any sets. A function A -f-> B assigns to every element a ∈ A an element f(a) ∈ B.
- In very formal set theory the definition happens by means of “ordered pairs”: we construct a new set from A and B consisting of pairs of elements, one from A and one from B, representing the input–output pairs that define f
- f: A -> B means from set A to set B
- f: a |-> b means from element a to element b
- Let f, g be functions A B. We say f = g as functions whenever ∀a ∈ A f(a) = g(a)
Structure : Identities and Composition
- Identity
- Given any set A there is an identity function A A which just sends every element of A to itself. We can call it 1A and define it by ∀a ∈ A 1A(a) = a.
- Composition
- We define the composite function g ◦ f by: (g ◦ f)(a) = g(f(a))
This is pretty plain definition of function identity and composition. Nothing too fancy here.
Making a category of sets and functions
- Need to check that identity really behaves like identity, both on the left and right, and composition is associative.
Identity
Even when we zoom in to individual elements of set, we see the identity structure.
Associativity
For A -f-> B -g-> C -h-> D, we need to show that : (h ◦ g) ◦ f = h ◦ (g ◦ f ) that is, ∀a ∈ A: ((h ◦ g) ◦ f)(a) = (h ◦ (g ◦ f ))(a)
If we apply functions to both, we finally come at h(g(f(a))) which proves that it follows associativity.
Category of sets and functions [ Formalised ]
This category is typically written as Set and is given by:
- objects: all sets
- morphisms: a morphism A B is a function A B
- identities: given a set A, the identity is the identity function 1A
- composition: composition of morphisms is composition of functions.
Now, this Set becomes a prototype to be able to use in larger mathematical structures. That way we can move from elements in traditional sets to treating structures as categorical Set.
Large world of mathematical structures
From the miniature world where we were looking at each element, we will zoom out and see larger category. The restrictions are the structures.
- Sets
- No structure
- Monoids
- Binary Operation, Identity
- Groups
- Binary Operation, Identity, Inverses
Homomorphism
- Any function between two algebraic structures – like monoids, groups, posets etc. – that preserves their operations and properties.
- The small object is a monoid and the relationship between monoids is also a monoid. Then that relation is called monoid homomorphism.
Monoids
- We need to define “function between monoids” as part of large category.
Understanding previous definitions of monoids as Set
A monoid has:
- data: a set of objects
- structure: an identity and a binary operation
- properties: unitality and associativity.
So it can be broadly summed up as a “set equipped with extra structure (satisfying some properties)”. Whenever we have “sets-with-structure” we can look for “sensible” functions between them, that is, functions that respect that structure.
-
Looking at previous example
- Monoid of natural numbers N under addition (N, +, 0) and monoid of integers Z under addition (Z, +, 0).
- Now, we are trying to map function between the monoids. f: N -> Z with f(n) = n, so every natual number is mapped to itself as an integer.
- Now, the binary operation must hold in this new function that we created. i.e. f(n+m) = n + m and f(n) + f(m) = n + m. Since we got, f(n+m) = f(n) + f(m) this holds the binary operation a.k.a preserves addition.
- Functions like f(n) = n + 1 however isn’t a sensible function because it leads to f(n+m) = n+ m+ 1 and f(n) + f(m) = n + 1 + m + 1 = n + m + 2. So, it doesn’t preserve addition.
- Also our structure needs to respect identity of monoid structure as well. In this case, f(0) = 0, which is identity in Z as well, so good. Preserves identity.
Monoid Morphism / Monoid Homomorphism
- A structure preserving morphism that leaves things the same.
- Let A and B be monoids, and write the identity as 1 and the binary operation as ◦ in each case. Then a monoid homomorphism from A to B is a function f : A -> B on the underlying sets, such that
- f respects ◦ ( Binary operation ) : for all x, y ∈ A we have f(x ◦ y) = f(x) ◦ f(y), and
- f respects the identity: f(1) = 1.
In general not every function on the underlying sets will respect the monoid structure, so this is a restriction to some special functions.
Then, we finally get our category Mnd whose objects are all the monoids and whose morphisms are all the monoid morphisms between them.
Groups
A group is a monoid with some extra structure, so a group homomorphism should at least be a monoid homomorphism, but it should also preserve the extra structure. So we might think that a group homomorphism f : A -> B should be a function on the underlying sets such that:
- the binary operation ◦ is respected: ∀x, y ∈ a, f(x ◦ y) = f(x) ◦ f(y),
- the identity 1 is respected: f(1) = 1, and
- inverses are respected: ∀x ∈ A, f(x−1) = (f(x))-1
The interesting thing in groups is that preserving the operation often forces identity and inverse preservation, due to the existence of inverses.
Posets
Relation ≤ is a poset. An order preserving function f: A -> B between posets satisfies : if x ≤ y in A, then f(x) ≤ f(y) in B.
Order Preserving poset
Poset N with ≤. Define f(n) = n+1 If m ≤ n, then f(m) = m+1 ≤ n+1 = f(n) which is preserving order.
Not order preserving poset
Poset N with ≤. Define f(n) = -n, e.g. m ≤ n ; then f(1) = -1 ≥ -2 = f(2) Which reversed the order It doesn’t always preserve order. So, not order preserving poset.
Category of posets
- Objects are posets
- Morphisms need to be order preserving functions preserving ≤ .
Example
Here, there are three different orderings:
- The way which the arrows are drawn in: where a -> b whenever a is a factor of b. Written as operation |.
- THe usual ordering according to size a ≤ b
- The physical levels on the drawing ( How many prime factors for each element depends on what level it is in ) Written as operation <>
So, we can define binary relationships here. Given a number a, N(a) be the number of terms in prime factorization. Then for each level of cube, we can write N(a) ≤ N(b).
| a | N(a) |
|---|---|
| 42 | 3 |
| 6, 14, 21 | 2 |
| 2, 3, 7 | 1 |
| 1 | 0 |
So, we have three orderings: (A, |), (A, ≤), (A, <>).
The factor operation is order preserving because (A, |) -> (A, ≤) But the hierarchy operation is not order preserving because 6 lies above 7 in hierarchy level. So, the hierarchy operation 7 <> 6 will imply 7 ≥ 6. So, the order isn’t preserved.
Top
Category of topological spaces Top where:
- objects: all the topological spaces
- morphisms: a morphism A B is a continuous function A B.
Homotopy is the notion of continuous deformation which is in some sense really the point of topology, but it requires more dimensions of thought than are available in the category of spaces and continuous maps. One way to deal with those higher dimensions is to go into higher-dimensional category theory, which we will briefly discuss at the end of the book. Another way is to try and work out how to detect traces of the higher dimensions in lower-dimensional algebra so that we can avoid creating new types of algebra to deal with it.
Normal Categories
- Sometimes we get a little bored of all these parentheses so we might omit them and just write Fx, Fy and Ff trusting that using uppercase and lowercase letters makes the point that F is applied to the lowercase letters.
- These morphisms between categories are so important that they have an actual name rather than just “morphisms of categories”: they are called functors.
- The property of preserving identities and composition is called functoriality.
Matrices
- One of my favorite examples is the category of matrices. In this category again it’s not the objects that are really interesting but the morphisms: the morphisms are matrices. That is, we regard matrices as a sort of map.
- In a bit of a leap of imagination we can regard an a × b matrix as a morphism a b, in which case a b × c matrix is a morphism b c and the condition of composability matches the condition of when we can multiply matrices. We get a category Mat with
- objects: the natural numbers
- arrows: an arrow a b is an a × b matrix
- composition: matrix multiplication.
- This might seem like a weird category until we consider that one of the points of matrices is actually to encode linear maps between vector spaces. In that way, matrices really do come from some kind of map, it’s just that the encoding has taken them quite far away from looking like a map. That typically makes it very handy for computation (especially if you’re telling a computer how to do it) but can be quite baffling for students if they’re just told about matrices for no particular reason — like so much of math.
Isomorphisms
- The harder conditions we put for sameness, it becomes more about the objects than the relationship and the patterns in it. So, we want to find some sense in which the object can be compared. And for that we need some notion of “sameness”.
- e.g. Equality sign is a sign of sameness for algebraic equations.
- Multiply sign is same as adding that number that many times.
Invertibility
- A invertible arrow between them.
- We can use that as one condition to say that they are same.
- e.g. On real numbers, we can say addition is invertible. But multiplication by 0 or square root, they are not invertible. Either they don’t know where to go back to, or go to a different place than where they came from.
Isomorphism
- Treated as same in category theory because they have same relationship with other objects in the category. i.e. Other object that has relation with two objects that are isomorphic, lets say a and b, can’t differentiate between a and b since it knows a and b only by the relationship it has with them. We don’t really look into the intrinsic property of the object.
- By assuming object “x” and drawing relationship like this, it becomes clear.
So, the relationship of x with both a and b is essentially the same i.e. isomorphic. We can do this by drawing arrows towards x as well and pre-compose to see the same results. Very easy to go step by step using just plain categorical principles.
Definition
- Definition of an inverse
- Let a -f-> b be an arrow in a category C. An inverse for f is an arrow b -g-> a such that g ◦ f = 1a and f ◦ g = 1b.
- From the properties of inverses, they are unique.
- Definition of isomorphism
- Let a -f-> b be an arrow in a category C. If f has an inverse we say that f is invertible and call it an isomorphism, and we say that a and b are isomorphic. We use the notation as in a ≅ b, or we write a -∼-> b.
Pre and post composition
- Post composing by g means g after f. So, we apply f first, then g but is written as g . f
- Pre composing by g means g before f. So, we apply g first and then to that result, apply f. So, its f . g
Isomorphism of sets
- For isomporphism, we need the functions to be invertible. For functions to be invertible, we need to have one-to-one mapping between two sets.
- This is however for finite sets. For infinite sets, we can turn things around because there is no size. As long as they are countably infinite, we can always create one-to-one mapping.
- Also, not every functions inside isomorphic sets are isomorphic. If a function maps elements from set A into one element of set B, then it’s a valid function but not invertible. Thus, not isomorphic. So, functions that are isomorphisms between sets are called bijections.
Non categorical definition of bijection
- A function A -f-> B is a bijection if for every element b ∈ B there is a unique element a ∈ A such that f(a) = b.
- This is definition from our sets which is regarding each element.
Isomorphisms of large structures
- Similar definition. Existence of an inverse that is structure preserving means the objects are isomorphic.
Monoids
- Assuming monoid morphism A -f-> B and its inverse B -g-> A, we need to ensure that it preserves monoid structure. a.k.a. binary operation and identity.
- Identity
- Need to show g(1) = 1. Applying f to the left gives 1 i.e. f . g = 1 because f and g are inverses. Also applying f to the right gives 1 for the same reason. So, there is just one identity.
- Binary Operation
- g(b1 . b2) = g(b1) . g(b2)
- By applying f to the left, we get b1 . b2 because f.g = 1.
- By applying f to the right, we get f(g(b1) . g(b2)) and since f should respect binary operation by being a monoid mapping, it also resolves to b1 . b2
- So, if f is a bijective homomorphism, then its an isomorphism of monoids and vice versa.
- Example of monoid isomorphism:
- Representation of number system as 1, 2, 3 .. and One, Two, Three … They have same structure, so shouldn’t be really counted as different.
- If monoids have same elements but different structures, then they aren’t isomorphic as monoids, but as sets. Sets have loose structure compared to monoids.
Groups
- Homomorphism of groups is just a homomorphism of underlying monoids. So, group isomorphism must be bijective homomorphism.
- By definition of groups, they need to have inverses for each elements.
- Rotation by 90 degrees or mod 4 clock both are groups since they have inverses for each elements, follow binary operation, and have identity.
- By looking at the fact that we can map these two to one another clockwise, counter clockwise etc., they are isomorphic. They both are “cyclic group of order 4”.
Posets
- Order preserving and bijection.
- Inverse is automatically order preserving in a poset.
Topological spaces
- In case of topological spaces, function that is continuous can have inverse function that is not continuous. So, bijection is not enough to ensure continuous map is an isomorphism in the category of spaces and continuous maps.
- So, its a wrong notion of sameness in this case.
- For topological spaces, there is “homeomorphism”. The reason why we call this is that our previous definition of isomorphism wasn’t sensitive enough to give us sameness for topological spaces.
Groupoids
- More expressive than equivalence relations as things can be related in more than one way.
- Each arrow needs to have its inverse in a groupoid.
- Groupoids and topological spaces are related in the sense that inverse in topological path is like going backwards along the same exact path.
Thinking categorically
- Become curious about a structure, in sets and functions.
- Express it categorically, forget about the elements.
- Take definition of other categories to see what it means.
Monics and Epics
Asymmetry of functions
- Since functions can’t be isomorphic when they don’t have one-one mapping between elements, we can say isomorphism is generalization of symmetry of relations.
Injective Functions
- Every output is hit at most once.
- One-one, same output means same inputs.
- A function f : A -> B is called injective if ∀x, y ∈ A, f(x) = f(y) => x = y.
- e.g. f : N -> N where f(x) = x + 1 has mapping for all elements on the left to unique elements on the right but doesn’t say anything about element on the right to have input on the left. In this case, 0 won’t have an input. So, its only about one to one relationship. Injective still since the mapping is one to one.
- To prove that a function is not injective we have to prove the negation of the definition of injective, that is: ∃ x, y ∈ A such that f(x) = f(y) but x ≠ y.
Surjective Functions
- If co-domain equals range
- Meaning that every output element has a mapping from one input element.
- A function f : A -> B is called surjective if ∀b ∈ B ∃ a ∈ A such that f (a) = b.
- e.g. f : N -> N where f(x) = x + 1 has mapping for all elements on the left to unique elements on the right but doesn’t say anything about element on the right to have input on the left. In this case, 0 won’t have a corresponding input. So, its not surjective.
Bijective Functions
- If its both injective and surjective.
- A function f : A B is called bijective if it is injective and surjective, that is: ∀b ∈ B ∃!a ∈ A such that f(a) = b. Here exclamation means “unqiue”.
Examples
- A = φ, B = Z
- For injective, the definition starts “for all x, y ∈ A”. We can now stop because A is empty, so whatever happens this condition is vacuously satisfied. Thus the function is injective.
- For surjective there is a part of the definition that says “∃ a ∈ A such that. . . ” and then we’re in trouble because there is no element in A. The only way we could survive this is if the condition is vacuously satisfied, that is: the condition starts with “∀b ∈ B” so if B is empty then the condition is vacuously satisfied.
- So, if it were A = φ, B = φ then that would have been bijective.
Monics: Categorical Injectivity
- All the definitions before have elements tied to them. So, that’s not categorical. Now, we need to express them as sets and functions only, not sets and elements.
- A morphism a -f-> b in a category C is called a monomorphism or monic if, given any fork diagram in C, f ◦ s = f ◦ t => s = t.
Now, this is since a categorical version of injectivity, it needs to be part of isomorphism as well.
Proposition: A function is injective iff it is monic in Set category.
Assume injective function f: a -> b . We assume to show its monic. Draw the fork diagram as above. Then, We want to show such that fs = ft, we need to prove s = t. By definition of injectivity above. fs = ft means: for all x belongs to a, f . s(x) = f . t(x) if f is injective , that impiles: for all x belongs to a, s(x) = t(x) thus s = t.
Proposition: A function f that is isomorphic is automatically a monic.
Let f: a -> b be an isomorphism with inverse g. Draw the fork diagram.
Then we need to show if fs = ft, then s = t Start with fs = ft => gfs = gft => s = t since gf = 1a. Thus, f is monic as required.
Split monic
Let f : a -> b be a morphism in a category. If there is a morphism g as shown here with gf = 1a then f is certainly monic and is called a split monic. Then g is called a splitting, left inverse or a retraction for f.
Epics: Categorical Surjectivity
- In sets, injectivity and surjectivity didn’t look like other way round. But they do look like duals here.
- Start by reversing the arrow diagram.
- A morphism f : a b in a category is called an epimorphism or epic if, given any diagram as above: sf = tf => s = t.
Proposition: A function f is surjective iff its epic in Set category
Putting it with definition of image f, it can be put as Image(f) = { y ∈ b | ∃ x ∈ a such that f(x) = y }
We know that : b = Image(f) union Nonimage(f)
So, a function is surjective iff Image(f) = b.
Using the second arrow diagram, given sf = tf, we need to show s = t. Consider y ∈ b. Now, f is surjective, so ∃ x ∈ a such that f(x) = y.
Thus, s(y) = sf(x) by substitution from line above = tf(x) by hypothesis = t(y) by substitution from definition again Thus s = t as required.
By using a contrapositive example, we can prove the reverse.
Proposition: If f is an isomorphism, then f is epic
Same proof like monic with these new arrow diagram
Split epic
- Let g: b a be a morphism in a category. If there is a morphism f as shown here with f g = 1b then g is certainly epic. Then g is called a split epic and f is called a splitting, a left inverse or a section for g.
Relationship with isomorphisms
- If f is a split monic and a split epic, then it has an inverse on both sides, thus isomorphic.
- A morphism can be monic and epic without necessarily being an isomorphism, if it doesn’t split. This can be understood when we get out of Sets. The examples and proofs we have done are comparison to Sets upto this moment.
- Monic/Epic is a property of morphism, whereas splitting is a piece of structure.
Monoids
For example, consider the monoid of natural numbers N under addition. We will try to define a monoid homomorphism f to some other monoid M.
- We know that 0 is the identity in N so it must go to the identity in M; we have no choice about that.
- We can send 1 anywhere we want.
- We know that 2 = 1+1 in N, and by the definition of monoid homomorphism we must have f(1 + 1) = f(1) + f(1) so we have no choice about where 2 goes: it has to go to f(1) + f(1).
- Something similar is now true for every other natural number. Every n is a sum of 1’s and so we have no choice over where it goes: it has to go to the n-fold sum of f(1)’s.
What we’ve done here is based on the fact that N is the free monoid built up from a single element.
Proposition Let f: N -> Z be monoid homomorphism given by inclusion f(n) = n. Then f is epic in Mnd (Monoid category).
If we have sf = tf, then that means s and t agree on the image of f. However, 1 ∈ Z is the image of f because f(1) = 1 and so we must have s(1) = t(1) which in turn forces s = t. Because monoid is built on top of a single thing. So, this shows that f is epic even when it isn’t surjective.
f is also injective since it maps element by element on this case and that’s enough to ensure that its monic in Mnd. Now, in fact f is monic and epic, yet its not an isomorphism.
Density
- Examples similar to monoids where morphisms are epic without being surjective.
- A set is called dense inside B if closure of A is B; closure of A is essentially the most economical way to enlarge A just enough to make it a closed set.
- This is related to how we can construct the real numbers from the rationals, by taking the closure under limits, which amounts to throwing in the irrational numbers.
- This sort of thing happens any time something has been constructed “freely” from some generators. If the morphisms in that category preserve the structure, then all you have to know is where the generators go, and then there’s no choice of where the rest of the structure can go. You might also have seen this with vector spaces and basis elements. There’s a concept of “limit” and “density” in category theory that mimics the situation of limits and density in analysis.
- One special case of injective functions is subset inclusions. For example we have seen the function N -> Z which just takes each natural number and sends it to the same number as an integer.
- There’s no categorical reason that a subset inclusion is any better than any other kind of monic, and so in more general situations monics are used to indicate subobjects.
Higher Dimensions
- Monic and epic are categorical versions of injective and surjective functions, and when we go into higher dimensions we want to generalize injective and surjective functions to the level of functors, that is, the morphisms in the category Cat. We can try looking for monics and epics in that category, but it won’t really give us “the right thing” because that is working at the wrong dimension.
- Cat is really trying to be a 2-category (as we mentioned before) with a more subtle type of relationship between morphisms.
Universal Properties
- The reason for trying to characterize things by universal properties is so that we find things that play analogous roles in different contexts.
- How uniquely we can pin things down is important consideration with universal properties.
- We may find several objects that all satisfy the property, but they will all be uniquely isomorphic so the category “can’t tell them apart”. Thinking categorically, we need to embrace that we can’t tell them apart, even though there are many.
Role vs Character
- In category theory, we care about the role they play. Not the character that it has. e.g. 0 is representing nothing. But we can also describe it by role it plays: a number that when you add to something does nothing. That’s a role that it plays. And that’s a number that can only play that role.
- Same goes for number 1 in multiplication.
- They are thus called additive identity and multiplicative identity respectively.
Extremities
- One sure shot way of understanding a problem by knowing its bounds.
- Also by taking something into a different context where its extreme also tells us about a context. So many interesting ways to learn new things, find new patterns.
- e.g. If I am 5'6’’ and I am the tallest in the room, it says that the room is full of short people.
- In category theory, we are looking for extremities based on arrows. Where the arrows start and where the arrows end are usually the extremes. Not physical location on the drawing etc.
Initial Object
- An object I in a category C is initial if for every object X ∈ C there is a unique morphism I -> X.
- Its like having an end that you can attach to one end of your tape measure, a reference point.
- Category of integers has no initial object, however category of natural numbers has 0 as initial object.
- In a category with more than one object and no non-trivial morphisms, there is no initial object since there just aren’t enough morphisms. We need at least an object with a morphism going everywhere else. Though we might not draw it out loud, through composition that needs to be the case.
- In this diagram, if composite g . f is not identity, then a can’t be initial because we have at least two different morphisms a -> a: composite g . f and identity 1a. And we can have infinite number of morphisms from a -> a since f and g don’t have to satisfy any other equation and every time we go around the loop we can have a different morphism.
- In the case that they are in fact inverses, then this category exactly has four morphisms: f, g, 1a, 1b. All composites will be equal to one of these because f and g have to composite both ways around into identity. In this case, we see that a -1a-> a and a -f-> b, a is initial with unique morphisms. Same goes for b.
- There we have two initial objects but categorically they’re not really different.
Uniqueness
Terminal Object
- Now the end of category where all arrows lead upto.
- If we reverse the arrows, where all all arrows start from.
- An object T in a category C is terminal if for every object X ∈ C there is a unique morphism X -> T.
Proposition
Let T be a terminal object in a category C and T’ any object. The following are equivalent:
- T’ is a terminal object in C.
- T’ is uniquely isomorphic to T.
- T’ is isomorphic to T.
Using similar logic as initial object, these can be verified too.
Failure Cases for terminal and initial objects
- When category has too few morphisms or too many morphisms.
Going on forever
-
The last case we talked about for natural numbers, we know that there is no terminal object but we can add an object called ω which every number points to assuming its the largest, then we have a terminal object. 0 -> 1 -> 2 -> ω. We can omit the arrows since we have been doing that for natural numbers all the time as they can be composed.
Branching
- There might be a beginning or an end but not a place where everything begins or ends.
Going round in circles
- No initial object, provided that the arrows were not inverses.
Parallel arrows
- Too many morphisms to be unique
Disconnectedness
- Too few arrows to be terminal or initial
- “Locally initial” if there are disconnected regions with but those disconnected region has an initial or terminal object.
Case where object is both terminal and initial
- If it has only one object and one identity morphism.
- If more than one object but they are all uniquely isomorphic. THen every object is terminal and initial.
Examples in different contexts
Sets and posets
- Empty one is initial and 1-element one is terminal in sets with structure: posets and topological spaces.
Monoids and Groups
- They can’t be empty by definition.
- Trivial monoid/group is one with a single example.
- Unique function to that one element to itself is definitely a homomorphism. So, trivial group is terminal in category Grp. And also initial in Grp.
- A null object in a category is one that is both terminal and initial.
Context
- We can compare universal objects in different categories, or we might observe something being universal in one category, but not another.
- For posets and topological spaces, we can follow dotted arrows and get to the empty set. For monoids and groups, the arrow takes us to 1-element set because they are bound by definition.
Duality
- By turning arrows around, we get a dual version of every construction, every theorem.
- Dual category For any category C the dual (or opposite) category Cop is given as follows.
- objects: ob Cop = ob C
- morphisms: given objects a, b, we have Cop (a, b) = C(b, a)
- identities are the same
- composition is reversed
- The dual version is often indicated by the prefix “co-”. So for example:
- we define products and then the dual concept is coproducts
- we define limits and then the dual concept is colimits
- we define equalizers and then the dual concept is coequalizers
- we define projections and then the dual concept is coprojections.
- The dual of dual category takes us back to original category.
- A morphism f is epic in C if and only if it is monic in Cop .
- If f is an isomorphism in Cop, then it is also an isomorphism in C. If something is exactly the same in both C and Cop, then its called self-dual.
- Let C be a category. A terminal object in C is precisely an initial object in Cop .
Products and Coproducts
Idea
- If we think about our 2 by 4 grid of objects above, what is the relationship between this grid and the numbers 2 and 4? We might say there are 2 rows and 4 columns, but that sort of presupposes an understanding of what rows and columns are. We might say its height is 2 and its width is 4, but that also presupposes concepts of height and width. Here is something we could say that’s (perhaps) more fundamental.
- Imagine projecting shadows of our objects onto a wall. If we project in one direction (and perfectly line everything up) then we will see only 2 things, and if we project in the other direction we’ll see 4.
Definition
Given objects a and b in a category, a product for them is: an object a × b equipped with morphisms p and q as shown below such that given any diagram of this form there is a unique morphism x -k-> a × b making the following diagram commute.
- For product, we need to draw the shape and make sure that we have a unique morphism.
- This third diagram is a universal shape that we use to prove so many other stuff as well.
- The morphism k in the third diagram is a type of comparison between the universal situation (the first diagram) and the non-universal one (the second diagram). Note that asking for the diagram to commute means that the triangle on each side commutes. Written out in algebra this means pk = f and qk = g
- Uniqueness: it might not be the only morphism x -> a x b, but it has to be the only morphism that makes both of those side triangles commute.
Terminology
- The morphisms p and q are called projections.
- The morphism k is called a factorization. We are factorizing f and g.
- There is a general type of diagram called a cone which consists of a vertex and the morphisms from that vertex to everything else. In this case the vertex is a × b and “everything else” is just the objects a and b.
- The product is the universal cone, universal among all cones of this shape.
- We say the universal property induces the factorization k.
Step by step
So, we start by understanding that there are two objects in a category. Then we define a product a x b. Then that product assumes two projections p and q to relate with objects a and b. By drawing these projections, we need to understand that we have created arrows. By definition of universal property, we are saying a x b is the best option that can project onto a and b. This is the understanding. Now, how do we prove its the best? We start by drawing another projection onto a and b: f and g. But why did we do that? To factorize these f and g using a factorization unique morphism k. Its like saying a x b is the least possible path to a and b and then any other path is basically a composition of some factor with that least possible path. That makes product the best path out there.
Products as terminal objects
- Products are in fact a special type of terminal object. It’s just that a product in C isn’t a terminal object in C, it’s a terminal object in some more complicated category based on C, which I like to call a “souped-up” category.
- We know that terminal objects are unique up to unique isomorphism, and products are a terminal object somewhere, so products must also be unique up to unique isomorphism.
- There can be many relationships on the cone but only one that makes the diagram commute.
- By definition of products, all morphisms can be factored with product being a component of it, that means all relationships from any object to terminal object will have a unique morphism to that product. So, that product becomes a terminal object since there will be unique morphism from every other object to product. We called it in a “souped up” category because if we define a and b as objects, they don’t have arrow upto product. That’s why product is not a terminal object in that category but in a “souped up” category.
Look at what we consider objects in this “souped-up” category to say that its a terminal object.
Products in set
- Cartesian product is the categorical product in a set.
- Need to remember that second lines are elemental mappings.
- Let A and B be sets. Then the cartesian product A × B is the set defined by A × B = { (a, b) | a ∈ A, b ∈ B }
- The elements (a, b) are called ordered pairs, and there are functions p and q as shown on the right called projections, sending an element (a, b) to a and b respectively.
Products in posets
If we now work through the definition of product in this context, we see that for the product of a and b we need:
- A diagram of the form shown here, which in this category just means that v is a multiple of both a and b.
- Given any such diagram with vertex x, we need a morphism x -> v. Here is a “translation” of what that means in this particular category. “Given x that is a multiple of both a and b, x is a multiple of v”
Then by these two ideas, we come to the definition of LCM. In a general poset we might generically call the ordering ≥ and in that case the definition of categorical product gives us this:
- an object v such that v ≥ a and v ≥ b, and
- for any object x such that x ≥ a and x ≥ b, we must have x ≥ v.
This is exactly the definition of least upper bound or supremum. The first point says that v is an upper bound for a and b, and the second point says that if x is any upper bound, it is greater than or equal to v.
Category of posets
Let (A, ≤) and (B, ≤) be posets. Then we can define an ordering ≤ on A × B by (a1, b1) ≤ (a2, b2) <=> a1 ≤ a2 and b1 ≤ b2 and this makes (A × B, ≤) into a categorical product (A, ≤) × (B, ≤) in Pst.
Monoids and groups
- We have to start with groups (A, .) and (B, . ) and instead of making an ordering on A x B, we need to make a binary operation based on binary operations in A and B. Here dot means binary operation.
- If we take group/monoid to be R under addition , categorical product R x R is to come up with definition of addition for these ordered pairs. e.g. (x1,y1) + (x2,y2)
- Now, when we add this component wise we get (x1+x2, y1+y2)
- On generalizing this, we get
- Let (A, ◦, 1) and (B, ◦, 1) be monoids. We define a binary operation on A × B by (a1, b1) ◦ (a2, b2) = (a1 ◦ a2 , b1 ◦ b2 ). This makes A×B into a monoid with unit (1, 1), and it is the categorical product of the original two monoids.
Coproducts
- A coproduct in a category C is a product in Cop.
- Now, the arrows are reversed in the universal cone diagram.
- A coproduct for a and b is an initial object in a category whose objects are cocones over a and b, that is, diagrams of the form shown on the right.
- Coproducts are unique up to unique isomorphism (making cocones commute), there is symmetry in the variables, and there are n-fold versions.
- Coproducts in set is just union.
- Note that technically we shouldn’t say “A U B is a coproduct” without saying what the coprojections are, but we often do when the coprojections can be understood to be the “obvious” inclusions.
- This is an important way of thinking about universal properties. In general it says there is a bijective correspondence between (co)cones and factorizations, so that we can equivalently encapsulate the information of any (co)cone as a single morphism to (or from) a universal one. It’s very handy because a cone generally involves many morphisms, and we can now encapsulate it as one morphism together with a “reference” cone.
Terminology
- p and q are called coprojections or insertions.
- Instead of a cone, this is now a cocone. In a cone we have projections pointing away from the vertex, and in a cocone we have coprojections pointing to the vertex. The coproduct is then the universal cocone.
- The coproduct is written a union b, a u b, or a + b.
Coprdoucts in other categories
- Inside a poset : In the poset of factors of n we saw that products are lowest common multiples. Coproducts are then highest common factors.
- In the category of posets, we can take a disjoint union of two posets A and B and it will still be a poset: everything in the A part will simply be incomparable to everything in the B part.
- For tosets, if we take the coproduct of two tosets A and B, the result is in general not a toset: the elements of A will be incomparable to the elements of B, and this is not allowed in a toset.
- For monoids, if we take the disjoint union of A and B as sets then the result is not in general a monoid — we have a binary operation on the A part and a binary operation on the B part but we do not have a way of doing a ◦ b with an element from each side. So, if we restrict to the category of commutative monoids, everything in a co product can be expressed as “element of A . element of B” where dot is binary operation.
- Very similar to writing it as ordered pairs (element of A, element of B) just that we have binary operation in between.
- In category of commutative monoids, coproduct and product are the same.
- Commutative groups are also called Abelian Groups.
- Coproducts of groups are called “Free products” in group theory
- Products of groups are called “Direct products” in group theory
Products examples in topological spaces
- The product of a square and a line is a cube, because if you move a square in a line you sweep out a cube in the air.
- The product of a circle with a circle is a torus (like the surface of a bagel), which I like to demonstrate by taking a slinky (essentially a circle) and wrapping it round on itself in a circle. You can even make a vertical cut in a bagel and then insert the bagel into the slinky-torus.
Analogies with numbers
- Based on our understanding with commutativity, associativity, products, we can keep asking questions while playing with numbers like these ones:
- Is there an identity?
- Are their inverses?
- Do we have something like unique factorization into primes? If so, what are the primes? This one is studied for groups and is particularly straightforward for Abelian groups, where there is a “fundamental theorem of Abelian groups” rather like the fundamental theorem of arithmetic (which says that every natural number can be uniquely expressed as a product of primes).
Pullbacks and pushouts
- Our starting data so far has not been very general: it has not included any morphisms. For terminal/initial objects the starting data was trivial, that is, it was empty. For products/coproducts it was a pair of objects. In this chapter we are going to do a first example where the starting data is a diagram including some morphisms.
- Pullbacks and pushouts are dual to each other.
Universal cone
- A cone is an object v (the “vertex”) together with morphisms to every object in the starting diagram, such that everything commutes.
- We can start with any diagram and build a cone from it.
- For it to be universal, it needs to be universal among all cones of that shape. That is what we are doing on the third diagram. Asserting uniqueness through unique factorization from x to v, x -> v. And being a factorization, everything must commute of course. We can see that gray arrows on third diagram are commutative arrows. These are relations that can be derived by commutative laws.
Pullbacks
- A product of two sets takes all the possible ways of making pairs, with one element from each set. But perhaps we want to make pairs that are coherent in some way, perhaps pairing up people who are the same height to be dancing partners, or pairing pants/trousers with shirts that are the same color: we do that using a pullback.
- Ordering with some restriction basically but how is this a universal one?
- Developing from the idea of universal cone, a limit over a diagram is a universal cone over it. A pullback in a category is a limit over a diagram of the given shape.
So, depending on how we draw the base objects and find a universal cone there, it gets named different things. Then cone here is vertex v together with morphisms a, b, and c making everything commute. We can draw it like a square after omitting the composition from v to c:
- Then the universal property states: Given any square with vertex x, there must be a unique factorization as shown on the right. The factorization must of course commute here as well.
- To indicate a pullback we often put a little corner sign at the top left, as shown here. It goes where the vertex of the universal cone is.
- We can say a category has pullbacks when it has pullbacks over all diagrams of relevant shape. The shape involving three objects with two objects pointing to the third object as shown at the start of this section.
Pullbacks in sets
- Its like a product but it also has to commute to third object C. So, its written as A XC B.
- A XC B = {(a, b) ∈ A × B | s(a) = t(b)}
- The square is a pullback, where p and q are the projections inherited from A × B.
- Note that when we write the vertex of the pullback as A ×C B it only tells us what the corner object C is, without reference to the morphisms s and t. In some situations those are very natural, but I think it’s good to be aware that the notation is missing something.
- Sometimes we talk about pulling back morphisms along each other. So we might say that p is the pullback of t along s, and that q is the pullback of s along t. Although the definition is symmetrical in s and t sometimes the situation isn’t. Sometimes one of the starting morphisms is more interesting and the other is in more of a supporting role.
- In this diagram, every arrow is a subset inclusion function and forms this shape.
Definition of category using pullbacks
- Set C1 of morphisms and C0 of objects, equipped with functions giving the source and target of each morphism.
A composable pair of morphisms looks like an ordered pair (f, g) but its not any old ordered pair. the two morphisms have to meet in the middle in order to be composable.
We are trying to define what a category is using pullbacks.
- We take the pullback shown on the right; it’s a pullback in Set so can be defined as follows:
- C1 XC0 C1 = { (f, g) ∈ C1 × C1 | t(f) = s(g) }
- Then composition is defined as C1 XC0 C1 -> C1
- The fact that composition is defined as pullback rather than the product is what makes it a partial binary operation rather than a binary operation since a binary operation on set is A X A -> A. j
Representing by elements of set.
Pushouts
- A pushout is a universal cocone for a diagram of the shape shown in the first diagram below. That is, it is a vertex v and morphisms as shown in the second diagram, such that given any diagram as in the third diagram, there is a unique factorization as shown in the fourth diagram.
- Represented by small corner marking the vertex of universal cocone.
- Dually to pullbacks, these pushouts are :
- Initial objects somewhere
- Unique upto unique isomorphism
- Canonically related to coproducts
Pushouts in sets
- As for when we did the pullback property, it may help to think about what it means for the outside to commute. If we start with an element y ∈ A ∩ B and chase it around, we see that commutativity means f(y) = g(y), that is the functions f and g have to agree on the intersection A ∩ B.
- This square is both a pullback and a pushout.
- The diagram on the right has a pushout given by A U B / ∼ where the relation ∼ is generated by: s(c) ∼ t(c) ∀c ∈ C
- The quotient map is a function A U B -> A U B / ~ which is unique factorization induced by universal property of coproduct.
- So, defining a function out of a quotient like this V / ~ -> X. The item on the left will consists of elements of V at root but some will be identified under relation ~.
Pushouts in topology
- Key way of glueing spaces together to make more complex spaces.
On one hand is a mobius strip. This shape famously has “only one side” as the front and back of the paper have been joined up. It also only has one edge, because the “right and left” edges of the strip of paper have been joined up. As it only has one edge, this means its edge (or boundary) is topologically a circle. Thus we can abstractly (though not physically) glue a disk onto that boundary.
Pushouts in other places
Groups
- We already saw that coproducts are much more complicated for monoids and groups than for sets and posets. This is because of the binary operation: it means that after making the disjoint union of the underlying sets, we must then generate new elements produced by the binary operation.
- To find pushouts of groups we have to start with the coproduct of groups, which we saw in the previous chapter is the “free product”, and then we have to do something analogous to quotienting out by an equivalence relation. In group theory this is provided by the theory of quotient groups. The idea is that one can “divide” a group by a special kind of subgroup, called a normal subgroup. We have actually seen an example of this although we didn’t put it that way: the integers modulo n can be constructed as a quotient group where you start with the integers and then quotient by the subgroup consisting of all the multiples of n.
Algebraic topology
- Algebraic topology is about making relationships between spaces and groups.
- A big problem is then actually calculating what the fundamental group is as a group, rather than just as an abstract definition. Pushouts help us do this because of a wonderful theorem called Van Kampen’s theorem.
- The pushout method works much better if instead of using groups we use groupoids.
More general universal properties
- Terminal and initial objects are cocones over empty diagrams: no objects and no morphisms.
- Products and coproducts are cocones over discrete diagrams: no morphisms.
- Pullbacks and pushouts are cocones over diagrams with just two morphisms pointing in opposite directions.
- There are other properties like equalizers and coequalizers. They are cocones over parallel pair of arrows.
- We also defined limits which are universal cones over a diagram and colimits which are universal cocones. They are superset of all these.
- Equalizers and pullbacks are interchangeable in the presence of products, that is, we can make equalizers out of pullbacks and products, and we can also make pullbacks out of equalizers and products. It is perhaps more intuitive to state the result about limits in terms of products and equalizers, as products deal with multiple objects and equalizers deal with multiple morphisms between the same objects, and that is really the two features that a diagram can have.
Functors
- Functor is a function on underlying data, preserving structure.
- Functor is function between two categories.
- In this case the definition of functor consists of a function on sets of objects, and a function on every homset. This is for small category.
- Let C and D be (small) categories. A functor F : C -> D is given by
- a function F : obC -> obD, and
- for all objects x, y ∈ C, a function F : C(x, y) -> D(Fx, Fy) satisfying the following conditions called functoriality:
- on identities: for all objects x ∈ C, F(1x) = 1Fx and
- on composites: for all morphisms x -f-> y -g->z ∈ C, F(g ◦ f) = Fg ◦ Ff.
- More generally, Let C and D be categories. A functor F : C -> D associates:
- to every object x ∈ C an object Fx ∈ D,
- to every morphism x -f-> y ∈ C a morphism Fy -Ff-> Fy ∈ D satisfying functoriality as above.
- Like we talked about, after functors are applied, it need to satisfy identity and composition again.
- In terms of definition of category with C1 and C0 where one is morphism and another set of objects, in that context, we can see functor as pair of functions that make the diagram commute.
Functors between small examples
- Considering posets as categories, functor is aautomatically a order preserving function as well. For a -> a’, we get a morphism Fa -> Fa’ and since a ≤ a’, Fa ≤ Fa'.
- In monoids and groups, the monoid homomorphism are the functors between those categories. The functorality maps out to preserving identity and binary operation in case of monoids which is same as conditions for monoid homomorphism.
Functors from small drawable categories
- There is nothing left to specify or check as we know that identities must go to identities, and there are no non-trivial composable morphisms anyway. Note that Fa and Fb could be the same set, and Ff could itself be the identity: identities must be mapped to identities, but non-identities are allowed to be mapped to identities.
- A functor A -> Mon just picks out a monoid homomorphism (and by implication, a pair of monoids for the source and target as well). In general a functor A -> C just picks out a morphism in C.
- In this drawing, the top-and-right composite is Ft ◦ Ff which equals F(t ◦ f) by functoriality of F; similarly the left-and-bottom composite equals F(g ◦ s). The commutativity of the original square tells us t ◦ f = g ◦ s, so we must also have F(t ◦ f) = F(g ◦ s). So the second square commutes.
- Let J be a finite category and C be any category. Then a diagram of shape J in C is a functor.
- Let F : C -> D be a functor, and f an isomorphism in C with inverse g. Then Ff is an isomorphism in D with inverse Fg.
- The fact that isomorphism is still an isomorphism after applying a functor is called preservation.
Free and Forgetful functors
- When we were looking at products of posets we took products of their underlying sets and then constructed a “natural” ordering on that set. Without saying so, we were invoking a functor Poset Set , which takes each poset and “forgets” that it’s a poset. Without saying so, we were invoking a functor Poset -> Set which takes each poset and forgets that its a poset.
- Functors that forget structure are called forgetful functors. They are often denoted U ( for underlying), so for poset A, we call its underlying UA.
- Other forgetful functors are Grp -> Mnd, Abelian -> Grp, Toset -> Poset, Anything with structure -> Set.
- The relationship they often have with a functor going the other way which does the “opposite” of forgetting structure: it creates structure freely and is called a free functor. By contrast, sometimes forgetful functors do not have a relationship with such a functor, and that is in itself interesting.
- Order preserving functions between posets then become functors between special categories. Then we get a functor Pst -> Cat
- We can express monoids as one object categories. If we decide in advance what the single object is going to be, then we get a functor Mnd -> Cat.
- Free functors are harder than forgetful functors.
- Without imposing any unnecessary constratints or using any extra information, we have to make Set -> Mnd or something like this.
- e.g. Start with any set A and produce monoid of words in the elements of A. This is called a free monoid on A.
- e.g. A -> {*} will turn every word to series of asterisks. So, this is like a free monoid functor.
Preserving and reflecting structure
- In the forwards direction we have the question of preservation: given a type of structure in C, if we apply F does it still have that structure in D?
- In the backwards direction we have the question of reflection: if we apply F to something in C and the result has a particular structure in D, can we conclude that it already had that structure in C?
- Last time we talked about the split epics vs epics. Now, functors don’t preserve epics as structure but always preserve split epics.
- Structures preserved by all functor are generally called absolute.
- e.g. Those with rules where “for all” exists, they are easier to preserve even when compressed. Those with rules where “there exists”, they are harder to preserve when it compresses the structure.
Example 1
- As the target category has only one object and only one morphism, we have no choice about where F can send everything: every object has to go to the single object and every morphism goes to the identity. Functoriality has to hold because the only morphism in the target category is the identity, so every equation of morphisms just reduces to an identity equalling itself.
- Now we just check that this functor sends a non-isomorphism to an isomorphism. The single non-trivial morphism in C is not an isomorphism as it has no inverse, but it is mapped to the identity in D which is an isomorphism. So we see that F does not reflect isomorphisms.
Example 2
- If we have two parallel arrows that are not equal instead of the diagram on the left in first example, then the diagram does not commute, as there are two paths with same endpoints whose composites are not the same.
- Now if we again take the functor to the category , the parallel arrows will both be mapped to the identity, so the non-commutative diagram is mapped to a commutative diagram. This is thus a functor that does not reflect commutative diagrams.
General ideas
In Set any one-element set is terminal, and the empty set is initial. We can compare this with various categories of sets-with-structure.
- In the category Pst of posets and order-preserving maps, any one-element poset is terminal and the empty poset is initial. So the forgetful functor Pst -> Set preserves terminal and initial objects.
- In the category Grp of groups and homomorphisms, the trivial group has one element (the identity) and is both terminal and initial. So the forgetful functor Grp -> Set preserves terminal objects but not initial objects, because if we apply it to the initial object in Grp we do not get the initial object in Set.
- In the category Top of topological spaces and continuous maps any one-point space is terminal and the empty space is initial. So the forgetful functor Top -> Set preserves terminal and initial objects.
Contravariant functors
- It reverses the direction of morphisms and switches the order of composition.
- F(g ◦ f) = Ff ◦ Fg.
- A contravariant functor is a functor Cop -> D.
Algebraic Topology
- The elements of the fundamental group are the homotopy classes of loops. This means, essentially, that we count loops as the same if they’re not really different, but you can continuously deform one into the other without breaking it or going over a hole in the space. We talked about this before in small categories as well.
Categories of categories Cat
-
Now, we want to show that there is an identity functor, composition of functors, and that axioms hold. So, its a bigger category.
-
By restricting the size of category we’re talking about, we avoid creating self-referential categorical loop.
-
First level is small categories which can be represented as sets (homsets). Then we make category Cat of small categories and all functors between them. We don’t include any of examples of “large categories of mathematical structures” like Set, Pst, Top etc,. for now. And it can’t of course contain Cat itself to avoid self-reference.
-
Then next level up is locally small categories. If morphisms between any two objects form a set, however the objects might form a large collection. So, in category Set, the objects are all possible sets. Set is locally small.
-
Then we make category CAT of locally small categories and all functors between them.
-
A poset is a category in which there is at most one morphism between any pair of objects. This means we have an “inclusion” functor Pst Cat which simply sends each poset to itself as a category.
-
If we define monoids as sets with a binary operation, then to construct an “inclusion” functor Mnd Cat we have to fabricate a single object from somewhere. We could decide that every monoid is going to become a one-object category with the same single object, say ∗. However, sending every monoid to itself expressed as a category is not quite as straightforward as for posets.
-
There are various forgetful functors from Cat to Set including functors that:
- send a small category to its set of objects,
- send a small category to its set of morphisms, or
- send a small category to its set of connected components.
-
The forgetful functors to Set are in a sense excessively forgetful. They don’t just forget structure, they also forget data. A more “sensible” forgetful functor would only forget the structure of a category, not the data, and that means that we wouldn’t land in Set but in the category of graphs.
-
Given a graph A, the free category on it has
- objects: the same objects as A, and
- morphisms: finite composable strings of morphisms in A.
- Note that finite composable strings include strings of length 0 (empty strings), which will be the identities. Composition is then given by concatenation, just like for words in the free monoid, but with the extra composability condition.
-
At the top we have a category of “data equipped with a particular kind of structure”, together with structure-preserving maps. In good situations the free and forgetful functors are in a special relationship called an adjunction, which can be expressed via universal properties in various ways that are beyond our scope here. The composite UF is then a functor from the category of underlying data to itself, and has many excellent properties. It is a prototype example of what is called a monad. Monads are then an abstract way to study “sets with structure”, and more generally the category of data at the bottom could be something other than Set, in which case monads give us a very general way to study algebraic structure. In fact, at an abstract level this is a definition of algebra: something that can be studied via monads.
Terminal and Initial Categories
- Given any category C there is a unique functor C -> 1 which is one object one morphism category,
- all objects of C must go to single object of 1
- all morphisms of C must go to identity morphism of 1
- Functorality holds because everything is identity.
- This is our terminal category.
- For intial category, we can try taking empty category 0, which has no objects and no morphisms. There is then a unique functor to any category C, just like a mapping was defined from empty set to each element. And functorality is vacuously satisfied. So, its the initial category.
Products and Coproducts of categories
- Composition is componentwise. We take the composite in C and composite in D individually, and then put them together in an ordered pair.
- So, is identity.
- (f2, g2) ◦ (f1, g1) = (f2 ◦ f1, g2 ◦ g1).
- 1(c,d) = (1c, 1d).
Observations
- Products of posets in the category Pst correspond to products of posets expressed as categories, in Cat.
- Products of monoids in the category Mnd correspond to products of monoids expressed as categories, in Cat.
- This can be said by saying that Pst -> Cat and Mnd -> Cat preserves products.
Isomorphism of categories
- By definition, an isomorphism in Cat must be a functor with an inverse functor, but the question is what that means: how we might characterize that directly, and what relationship it gives us between isomorphic categories.
Given pair of functors with F and G being inverses. In terms of their representation as sets and functions, they look like this. We know that the identity functor acts as the identity function on both objects and morphisms, and that composition of functors happens by composition of the functions at the level of objects and morphisms. So F1 and G1 must compose to the identity function both ways round, and similarly F0 and G0. This says we must have a bijection at the level of objects and a bijection at the level of morphisms, as well as the usual functoriality. This means that C and D have same structure, just different names on objects and morphisms. And interesting thing is it doesn’t have to be one isomorphism. There can be other isomorphisms as well. So, saying two categories are isomorphic is different from actually specifying an isomorphism between them. So, we need to know what’s the “right” notion of sameness for categories.
- In order to say that a functor F : C -> D is invertible it needs to have an inverse G, which means GF = 1C and FG = 1D. Now we unravel what this means: for two functors to be equal they have to have the same action on objects and on morphisms.
- So for the first equation, on objects we’re saying ∀c ∈ C, GFc = c. We get something similar for the second equation.
- BUt notions for sameness “wants” to be little weaker so that we don’t have tighter condition to say that they follow the same structure. Equality is too hard.
- So, better notion of sameness is like this:
- On morphisms: strictly invertible, so ∀ f ∈ C, GFf = f and similarly for the composite FG.
- On objects: only invertible up to isomorphism, so ∀c ∈ C, GFc ≅ c and similarly for the composite FG.
Full and Faithful functors
- We should not look at the set of morphisms overall, but we should look at individual homsets. This comes down to the difference between the two definitions of category we’ve seen:
- By homsets: for every pair of objects a, b a set of morphisms C(a, b).
- By total set of morphisms: a set C1 of morphisms equipped with source and target functions to the set C0 of objects.
- Let F : C -> D be a functor.
- F is called faithful if for all x, y ∈ C the function C(a, b) -> D(Fa, Fb) is injective. We also sometimes call this locally injective.
- F is called full if for all x, y ∈ C the function C(a, b) -> D(Fa, Fb) is surjective. We also sometimes call this locally surjective.
- If for all x, y the function C(a, b) -> D(Fa, Fb) is a bijection then we say F is full and faithful.
- Locally means that we are watching those up real close.
- In practice we often unravel the definitions as follows.
- Full: ∀ Fx -h-> Fy ∈ D, ∃ x -f-> y ∈ C such that Ff = h.
- Faithful: ∀ f,g: x -> y ∈ C, Ff = Fg ==> f = g.
- Full and faithful: ∀ Fx -h-> Fy ∈ D, ∃! x -f-> y ∈ C such that Ff = h
- Let F : C -> D be a full and faithful functor and a -f-> b be a morphism in C. Then f is an isomorphism iff Ff is an isomorphism.
- Earlier on we said that if we express posets as categories then the functors between them are precisely the order-preserving functions. Likewise if we express monoids as one-object categories then the functors between them are precisely the monoid homomorphisms. What is this saying about the “inclusion” functors Pst -K-> Cat and Mnd -Σ-> Cat? ==> Its saying that the functors K and Σ both are full and faithful.
- Full and faithful means “isomorphism at the level of morphisms” and “bijection up to isomorphism” for level of objects.
- A functor F : C -> D is essentially surjective (on objects) if ∀ d ∈ D, ∃ c ∈ C such that f(c) ≅ d.
- A functor F : C -> D is a pointwise equivalence if it is full and faithful, and essentially surjective on objects.
- Suppose F : C -> D is full and faithful. Then F is “essentially injective on objects” as in the above definition.
Natural Transformations
- Relationship between functors
- Start by assuming that only possible notion of relationship between functions is equality, while knowing that for functors its too strict.
- Given functors F, G: A -> B, a natural transformation α from F to G is depicted, or as α: F => G, and is given by:
- for all objects x ∈ A, a morphism Fx -αx-> Gx ∈ B, such that
- for all morphisms x -f-> y ∈ A the following square called the naturality square commutes.
- The morphism αx is called component of α at x.
- We think of natural transformation as 2-dimensional, like surface connecting paths made by functors.
Shape
- The way we have drawn shape of natural transformation, we say that F and G have to be parallel, which means they have same endpoints. The shape of α is then called “globular”.
- These square shapes are called “cubical”. In many situations, we define the cubical natural transformations using the definition of globular ones. e.g. In this cubical one below, we can say natural transformation α QF => GP. So, that way we study the cubical transformation as globular as well.
- The reason why we even have cubical is it’s more naturally arising in higher dimensional spaces, so sometimes more productive.
Functor Categories
- Assembling category can be done in so many different ways. We thus have had different definitions of category.
- Now, we can assemble category using natural transformations as morphisms between functors and functors themselves. This is similar to when we did define category using functors as morphisms.
- Given categories C, D, the functor category [C, D] has
- objects: functors C -> D
- morphisms: a morphism F -> G is a natural transformation.
- Identities and composition for natural transformation are componentwise.
- Given a functor F : C -> D the identity natural transformation 1F : F => F has all identity components.
- Consider functors and natural transformations as shown below. The composite natural transformation β ◦ α : F => H is defined by the following components: for each x ∈ C, (β ◦ α)x = βx ◦ αx
- That is Fx -(β . α)x -> Hx = Fx -αx-> Gx -βx-> Hx . This is also known as vertical composition.
- A general principle is that functor categories inherit more of their properties from the target category than from the source category.
- If D is discrete (only has identity morphisms) then the functor category [C, D] is discrete.
- This principle can be useful to study a category C via functors into a category that we know has a lot of excellent structure, such as Set.
- Given a category C, a functor Cop -> Set is called a presheaf on (or over) C. The category of presheaves over C is the functor category [Cop , Set].
Diagrams and cones over diagrams
- Functor categories give us a way to define cones over general diagrams, in order to define limits over general diagrams.
- A diagram of shape I in a category C is a functtor D: I -> C. We can imagine I to be a quintissential commuting square category, or a parallel pair of arrows, if we want to visualize. The functor then picks out a specific diagram of that shape in the category C.
- To pick out a vertex, we use little technical trick: constant functor. A functor that sends every object to the same place. Since its a functor, it not just sends every object to same object, say v, but every morphism as well to identity on v.
Constant functor
Let I and C be any categories, and v an object of C. We write Δv: I -> C for the constant functor at v, defined as follows:
- Given diagram D : I -> C, a cone over it with vertex v is a natural transformation Δv => D.
- Taking I to be 0 -f-> 1 as category
- Functor D: I -> C gives us this diagram in C : D(0) -D(f)-> D(1)
- A natural transformation α : Δv => D has a component Δv(i) - αi -> D(i) for each object i ∈ I.
- But αv(i) = v for all objects because of that assumption about I, we then have this:
- αv(i) = v -α0-> D(0)
- αv(i) = v -α1-> D(1)
- For naturality, we only have one non-trivial morphism f ∈ I to consider.
- Finally naturality corresponds to commutavitiy of every triangle necessary in a cone over diagram D, with each naturality square collapsing into a one triangle. This way of expressing general cones is the basis of general definition of “limit over a diagram of shape I”.
Natural Isomorphisms
- An isomorphism in a functor category is a natural transformation with an inverse.
- Natural transformation is an isomorphism iff all its components are isomorphisms.
- A natural transformation is an isomorphism in the category [C, D] if and only if for all x ∈ C the component α x : Fx -> Gx is an isomorphism in D.
- The inverse is components wise and vice versa.
- An invertible natural transformation is called a natural isomorphism. If there is a natural isomorphism F => G we often write F =∼=> G or F ≅ G and say F and G are naturally isomorphic.
- So, now we have two equivalent characterizations of natural isomorphisms:
- abstract/categorical: isomorphisms in a functor category
- concrete/pointwise: each component is an isomorphism
- One is a concrete set of conditions to check to ensure that some abstract principle holds, and the abstract principle is then the thing that enables us to do things. The key is to know how the two are related. This is often generally referred to as coherence conditions.
Equivalence of categories
- Using this “morphisms of functors” to make our nuanced version of sameness, called equivalence.
- With isomorphism, we invoked some equalities between objects because isomorphism involves a pair of functors such that FG = 1 and GF = 1.
- A functor F : C -> D is an equivalence if there is a functor G: D -> C and natural isomorphisms GF ≅ 1C and FG ≅ 1D . Then we say the categories C and D are equivalent, and that F and G are pseudo-inverses.
- F and G are like “inverses up to isomorphism”
- A functor is an equivalence if and only if it is a pointwise equivalence, that is, full and faithful and essentially surjective on objects.
- The general idea is that equivalent categories are “the same” in an appropriate sense. Categories are isomorphic if they have exactly the same object and arrow structure, so the only difference is that everything is renamed. Categories are equivalent if they have the same arrow structure but the objects can be “fattened up” a bit by having many isomorphic copies, or “thinned down” by identifying isomorphic objects (making them the same). In the process of fattening or thinning we just have to be careful to adjust the morphisms appropriately so that they effectively stay the same,
- A category is called indiscrete (or chaotic) if it is equivalent to the terminal category.
- Indiscrete is basically way to make the objects the same without actually identifying them. This is the right level of nuance in a category.
- Discrete and indiscrete categories have opposite universal properties. They are analogous (ideologically and formally) to discrete and indiscrete spaces in topology: in a discrete space all points are considered to be far apart, and in an indiscrete space all points are considered to be close together. The analogy is made formal by expressing the universal properties, by something called adjunctions.
Examples of equivalence in large categories
- We have always said monoid is one-object category. In one sense, its not the same because monoid has underlying data a set of elements whereas a one object category has an object and morphisms. So, this sense of “is” is via equivalence in structure.
- Defining G is “easy” as we just send a one-object category to the monoid of its morphisms. But defining F is “hard” because we have to decide which one-object version of the monoid to choose. However, it’s not excessively hard: we could just decide that the single object is always going to be ∗, say. In that case GF really is the identity on Mnd, but FG is only isomorphic to the iden- tity on ooCat. This is because if we start with a one-object category whose single object is not ∗, when we come back again via FG we will land on a category with the same monoid of morphisms, just a differently named single object. This is not really different, just isomorphic.
- Also, the pointwise way of looking at it is that G is surjective but F is only essentially surjective.
- Both are full and faithful because a functor between one-object categories is precisely a monoid homomorphism.
Horizontal Composition
- The idea is that although categories and functors do form a category, there is a better, richer, more nuanced 2-dimensional environment if we take cat- egories, functors and natural transformations between them. When we first defined categories, we had a prototype category given by sets and functions. Now we get a prototype 2-dimensional category given by categories, functors and natural transformations. We say “2-category” instead of “2-dimensional category” so that it’s less of a mouthful. There is one more structure that we need to consider in order to go fully 2-dimensional, and that is horizontal composition.
- Horizontal composition deals with categories, functors and natural transformations in this way. In this one, this would have components for all objects a ∈ A, HFa -> KGa.
- The components for α and β gives us morphisms like these:
- ∀a ∈ A Fa -αa-> Ga
- ∀b ∈ B Hb -βb-> Kb
- HFa -Hαa-> HGa -βGa-> KGa
- For first mrophism we applied functor H to compoent αa, but for second one we did the component of β at object Ga ∈ B.
- HFa -βFa-> KFa -Kαa-> KGa is another way of doing this as well.
- These two ways give us a naturality square.
- The left-hand square is the naturality square for α at the morphism f , with H applied to the whole square; recall that all functors preserve the commutativity of diagrams so after applying H the square still commutes. The right-hand square is the naturality square for β, at the morphism G f . They both commute, so the outside commutes.
Definition
Let α and β be natural transformations as shown. Then we define the horizontal composite to have components HFa -Hαa-> HGa -βGa-> KGa or equivalently HFa -βFa-> KFa -Kαa-> KGa
- The standard notation which is to use a star ∗ for horizontal composition and a circle ◦ for vertical composition.
- For vertical composition the boundary is a functor (1-dimensional) and for horizontal composition the boundary is a category (0-dimensional).
Interchange
When looking at HFa -Hαa-> HGa -βGa-> KGa. The first morphism Hαa is a component of α, with functor H applied. So, this is what it looks like on the top diagram. Same for second mrophism.
We can write them as whiskers which will look like this.
Now, we can see that using another equivalent statement from horizontal composition, we can get this:
From these, we combine to get 2x2 grid of natural transformations like this:
So, we can see that we can compose the pairs horizontally first and then compose the results vertically or vice versa.
This equality sums up to this:
The above equation is called interchange law. Natural transformations follow interchange law.
Other string of equalities tha appear in this:
Yoneda
- It is very abstract and formal but encapsulates some of the most deep fundamental truths about algebraic structures, while somehow at the same time being almost trivial to the point of being barely any more than type-checking.
- Almost simplistic to the point where people get divided in terms of whether category theory is the shit.
Revisiting sameness
In a typical two object, two morphisms each inverse of each other f and g between two objects a and b. We can write the conical relationship like this:
- When acting on morphisms out of x, we use post-composition with f .
- When acting on morphisms into x, we use pre-compositon with f.
Representable functors
An isomorphism in C produces an isomorphism in Set.
Now, we can see that it looks like a functor C -> Set Here x is fixed, but now a and b can be any objects, and f any morphism (not necessarily an isomorphism). We will call this functor Hx to remind us that x is fixed.
For it to be a functor, we need to validate its functorality.
Identity
We check the action of 1a ◦ _ on an element f ∈ C(x, a) as shown on the right: f is sent to f so 1a ◦ _ is indeed the identity function. f |-> 1a . f = f
Composition
We consider a pair of composable morphisms a -f-> b -g-> c in C and compare two things. Apply the functor Hx first and then compose the results in Set:
Instead if we compose in C first and then apply the functor Hx, then we get
The action of these two functions on s is the same, so associativity. So, functoriality comes down to associativity of composition in C.
Contravariant functors
Using the same analogy, we can make functor Cop -> Set. We now call this Hx since we are now looking at homsets of morphisms into x.
So, in summary, we get these:
The functors Cop -> Set are called presheaves on C. Functors of these two forms are called representable functors.
Yoneda Embedding
Assuming two categories [C, D] whose objects are functors C -> D We now want to send an object x in C to functor Hx: Cop -> Set. But Hx is itself an object of functor category [ Cop, Set ]. So, we go level above and use a H. where the “blob” is like empty spot for us to place the variable x or even f.
To define this functor we need to define Hf. Since we are trying to define natural transformation Hf : Hx => Hy, we must have these components.
Now to get where this a -s-> x should be mapped to. we’re starting with a morphism a -s-> x and x -f-> y, and we’re trying to produce a morphism a -> y, so there’s really only one thing we can do: compose s and f .
So, we have this definition of Hf at a. We need to also make sure that Hf satisfies naturality.
There is a naturality square buildup to prove it. So, the functor C -H.-> [ Cop, Set ] is called Yoneda embedding.
- Yoneda embedding is full and faithful.
Yoneda embedding being locally injective
So, if we fix x, y ∈ C , consider morphisms f, g: x -> y and check the implications on the right.
Now, Hf and Hg are natural transformations, so being equal means all their components are equal, as functions. Now, for respective components for each a ∈ C, we are supposing these are equal for all a ∈ C.
Now, by doing a = x, the component (Hf)x is a function acting on 1x. As well as same for (Hg)x.
By hypothesis, the components are equal as functions; so they have to produce same result for every element of C(x, c) and in particular on 1x. So, f = g as required which proves that its locally injective.
Yoneda embedding Being full
We will now show that H• is full. By definition this means: any natural transformation α : Hx -> Hy So first Hy must be of the form Hf for some x -f-> y, we need to produce a morphism f from the natural transformation α.
Now α has components for all a ∈ C i.e. αa: C(a, x) -> C(a, y). These αa are functions and we can use the same “Yoneda-y” principle. We know that identity 1x ∈ C(x,x). So, we can look at action of αx on 1x like this:
So , we produced a canonical morphism x -> y from α, so we can just try : f = αx(1x) and claim that α = Hf. For that, we need to show that their components are equal i.e. for all a ∈ C, αa = (Hf)a.
From this definition of (Hf)a, we now have αa(p) = f . p
Now, Using information about alpha in terms of how the naturality square looks like: for any morphism, a -p-> b , the square commutes.
Now, using b = x in this naturality square, we get this:
Now, seeing this in terms of sets and functions, we can go to element level and see what happens. If we start from identity and follow it, we get this.
Naturality tells us both ways around the square are equal , so αa(p) = f . p. Thus α = Hf. So, H. is full.
- The overall idea is that we can start with any category C and embed it in its presheaf category via the Yoneda embedding C -H•-> [Cop , Set].
- The fact that H• is an embedding means we can then sort of regard C as a subcategory of the presheaf category. Or at least, a copy of it appears as a subcategory of the presheaf category: we know that the embedding takes an object x ∈ C to the functor Hx , so if we take all the functors of this form and all the natural transformations between them, we get a copy (or model) of C as presheaves. Note that taking all the natural transformations between them is right because the embedding is full; if it weren’t full then taking all the natural transformations would give us extra morphisms that are not in C.
- So, these kind of presheaves are called Representable Functors.
- Every presheaf is canonically a colimit of representables.
- [Cop, Set] is the closure of C under colimits.
- Parts of presheaf category that are not in subcategory C are all colimits of things in C in canonical way.
Yoneda lemma
- It essentially captures the “Yoneda-y principle” we used above, which was that our natural transformations kept being entirely determined by looking at the identity.
- We were looking at natural transformations Hx => Hy but the principle really only depended on the source functor being of the form Hx. The target functor could have been any functor F: Cop -> Set.
Now, using the Yoneda-y principle, we set a = x and look at the action of αx on 1x which is αx(1x). Image of 1x is now not a morphism, becuase F(x) is a set, not necessarily a homset. But the idea is to define a natural transformation α where we have a free choice of where 1x can go, and moreover this completely determines the rest of components of α, by following a naturality square around. Thus, natural transformations Hx => F correspond precisely to elements of F(x). THis is yoneda lemma.
- Let C be a locally small category and F a functor Cop -> Set. Then there is an isomorphism F(x) ≅ [Cop , Set](Hx , F) natural in x and F.
- Whenever we say “natural in X”, it means that X lives in some category and if we use a different X and a morphism in between the two different X’s, we will get a square and it needs to commute.
- In this case x lives in the category C so that’s not too surprising; naturality in x is thus based on a morphism x -f-> y and a square like the first one (remembering that F is contravariant so flips the direction of f )
- Now F is a functor, but as an object it lives in the category [Cop , Set] so “naturality in F” is based on a natural transformation F =α==> G and square like the second one.
Higher Dimensions
- Sets were 0-dimensional structures. Sets and Functions together made a category. 1-dimensional structures. Then functors and natural transformations came together. Making them 2-dimensional structures.
- Extra dimension inside categories produced an extra dimension in the totality of categories.
- For succinctness, we call them 0-cells, 1-cells and 2-cells respectively.
- The 2-cells inside 2-category go on to produce morphisms between natural transformations.
- The higher dimensional structure with morphisms at every dimension “forever”, with no upper limit is called “infinity category”.
Defining 2-categories directly
- Defining using structure of categories, functors and natural transformations, and encapsulate it as data, structure and properties.
Data
- A collection of 0-cells.
- For any 0-cells a, b a collection A(a, b) of 1-cells from a to b, drawn as shown.
- For any parallel 1-cells f, g: a b a collection A(f, g) of 2-cells from f to g, drawn as shown.
Structure
Properties
- Unit laws: the identity 1-cells act as identities with respect to 1-cell composition, and identity 2-cells act as identities with respect to vertical composition of 2-cells.
- Associativity: composition of 1-cells, and both horizontal and vertical composition of 2-cells are associative.
- Interchange law, summed up in this diagram:
Now, we try to look at internal logic: one by homsets, and one by underlying graph.
Revisiting Homsets
- Instead of having sets of morphisms, we are going to have categories of morphisms. Then any part of the definition that was previously a function between sets of morphisms is now going to have to be a functor between categories of morphisms.
- Definition of category based on homsets
- Data
- collection of objects
- For any objects a, b a set C(a, b) of morphisms from a to b.
- Structure
- Identities: For any object a, identity function. a -1a-> a
- Composition: For any objects a, b, c, sending composable pairs to composites.
- Data
Properties
- The axioms for units and associativity can now be expressed entirely according to these functions on homsets, without reference to elements of homsets.
- The two triangles are the unit axioms saying that identity morphisms act as identities on both the left and the right; the square underneath is associativity.
- By referring to homsets and functions between them only, we have made definition categorical.
- If we move all our homsets from Set to category V, this is the notion of a category enriched in V. We can then define 2-categories as categories enriched in Cat.
Definition of 2-category by enrichment
- A locally small 2-category C is a category enriched in Cat.
- Data is collection of objects, and for any objects a,b a category C(a,b) of morphisms from a to b.
- Structure:
- Identities: For any object a , a functor 1 -> C(a,a) picking out an identity 1-cell a -1a-> a. 1 being the terminal category.
- Composition: For any objects a, b, c, a functor on objects ( 1-cells) and 2-cells. The second row is for 1-cells on objects, third row is for functor on morphisms. So, composition functor gives us both composition of 1-cells and horizontal composition of 2-cells.
- Properties
- The axioms for units and associativity are now the same commutative diagrams we drew for the categorical definition of a category, they just happen to live in Cat now rather than Set.
From underlying graphs to underlying 2-graphs
- This is the typical graph representation. As this is a diagram in Set, we could try putting the entire diagram inside Cat instead of Set. This is called internalization but it gives us something slightly different: we’ll get a category of morphisms and a category of objects as well.
- Now, we will extend graph by one dimension to include set of 2-cells like the second image.Now, to make 2-cells globular , we need a condition. The shape occurs because source and target 1-cells of α themselves have the same source and target. That is ss = st and ts = tt. This is the globularity condition. The diagram of sets and functions satisfying this condition are called 2-dimensional globular set or 2-globular set. This generalizes into n-dimensions.
- These are examples of 1-globular sets that live inside 2-globular set above. First and second are from taking left and taking right, the third one comes from composition end to end.
-
Lets discuss the properties of these sub-globular sets.
- In the 2-category of categories, functors and natural transformations, the first sub-globular set (collection) above has categories as its objects, and functors as its morphisms. We know this has the structure of a category: it’s the basic category Cat from before we even thought about natural transformations.
- The second sub-globular set (involving C2 and C1) has functors as objects and natural transformations as morphisms. This also forms a category. Previously we have defined functor categories [C, D] only after fixing the source and target categories, but we can throw all functors together into a large category of functors and natural transformations with any endpoints.
- The third sub-globular set is a little curious. It considers natural transformations with respect to their source and target categories rather than the functors.
-
By asserting that each of these three sub-globular sets is a category gives us, composition of 1-cells, vertical composition of 2-cells, and horizontal composition of 2-cells.
-
Thus, A small 2-category is a 2-globular set in which
- every sub 1-globular set has the structure of a category
- interchange holds
-
We saw that even for ordinary categories these two different characterizations (by homset, or by underlying graph) give us slightly different insights. For example, from the graph approach we saw how duality naturally arises from the symmetry between s and t. In a 2-globular set we have two pairs of source/target functions, each with analogous symmetry. We can flip either pair independently. Flipping the left-hand pair consists of flipping the direction of the 2-cells; flipping the right-hand pair consists of flipping the direction of the 1-cells; or we can flip both.
- Flipping the direction of the 1-cells is like what we do with ordinary categories, and this gets called “op” just like for categories.
- Flipping the direction of the 2-cells means we’re taking the duals of the hom-categories; this gets called “co”.
- Flipping both means we flip everything, and is inevitably called “co-op”.
-
Developing a “2-category theory”
- Taking everything we’ve done in one dimension and try to do it in two, replacing equalities with isomorphisms, and working out what axioms those isomorphisms should satisfy one dimension up.
- Another way is to express everything 2-categorically. In 2-categories, we express every underlying as category, unlike when we tried to express it as sets and functions for 1-caetgory. So, its all functors, categories, and natural transformations.
- Pointwise equivalence of categories defined in terms of functor being full, faithful, and essentially surjective on objects, is clue to the idea that full and faithful relate to thinking about morphisms inside categories rather than functors between them.
- Next equivalence we talked was about pseudo inverses: functors F and G going back and forth, natural isomorphisms GF ≅ 1 and FG ≅ 1. This definition doesn’t involve looking inside, so it is something we can now do in 2-category instead of Cat.
- More dimensions a cell has above it, the more subtle the notion of sameness can get. The number of dimensions that a cell has above is called codimension.
Monoidal Categories
- Monoidal categories are one of the most widespread examples of a slightly higher-dimensional structure. They are a “categorification” of the concept of monoids.
- A monoidal category is a 2-category with only one 0-cell. If we unravel this we can perform a dimension shift just like we did for monoids:
- The single 0-cell gives us no information so we can ignore it.
- We have non-trivial 1-cells and 2-cells; we regard these as objects and morphisms in the new structure.
- All 1-cells are now composable, so ◦ on 1-cells becomes a binary operation on our new objects, which we often write as ⊗.
- All 2-cells are now horizontally composable so ∗ on 2-cells becomes a binary operation, that is, ⊗ extends to morphisms in our new structure.
- Now, defining compositionwhen there is only one 0-cell, say ∗, then there is just one hom-category C(∗,∗) and single composition functor: C(∗,∗) x C(∗,∗) -> C(∗,∗)
- It looks like this since we can omit asterisks.
- We can think of binary operation in monoid as being like a form of multiplication, but it need not actually come from multiplication.
- One motivating example for abstract mathematicians is the tensor product of vector spaces; tensor products in general are subtle binary operations on abstract structures, which are not the same as products but can be studied a little like products. The framework of monoidal categories gives us a way to do that. As tensor products arise in a vast range of mathematical fields, monoidal categories are one of the most widespread examples of categorical structures.
Strictness vs Weakness
- We asked for some equalities at levels where something more nuanced was possible. This is the issue of “weakness” for higher-dimensional categories. If we ask for strict equalities even though a more nuanced type of sameness is available, we are doing things strictly.
- In the definition of 2-category the issue arises where we asked for diagrams to commute in Cat. Those diagrams gave us the unit and associativity laws, but were at the “wrong” level of weakness: the more nuanced notion of sameness for functors is natural isomorphism. So we did something unnecessarily strict.
- Associativity on objects would look like this: (a ⊗ b) ⊗ c = a ⊗ (b ⊗ c). This is an equality between objects in a category, so it’s the “wrong” level of sameness. The correct level is an isomorphism. And the best thing to do is not just to say that these things are isomorphic, but to specify an isomorphism showing it, like this: (a ⊗ b) ⊗ c -αabc-> a ⊗ (b ⊗ c).
- For the unit laws the same thought process leads us to realize that we don’t want the identity to act as a strict identity but as a weak one. As a result we tend not to write it as 1 any more, but perhaps I. The unit isomorphisms look like this: a ⊗ I -ra-> a and I ⊗ a -la-> a. The letters r and l stand for “right” and “left” as they’re dealing with a unit on the right or a unit on the left.
- The general idea now is that “everything that could commute does commute”. That is, whenever there are two ways to get from one place to another using the coherence isomorphisms, they should give the same answer so that we don’t get abstract anarchy.
- Naturality square. Structure isomorphism αabc compile into a natural transformation, as do ones for units.
- We still need some axioms for the structure isomorphisms. We want them to behave well enough that we can manipulate things somewhat as if they were strict equalities, even though they’re not. That means that if we move parentheses around using the isomorphisms, it shouldn’t matter in what steps we do it — one of the key things about equalities is that we can pile them up on each other, and keep substituting things for other things safe in the knowledge that the equalities will still hold. This is what we want here.
- We get this pentagon called the associativity pentagon; it is one of the axioms for a weak monoidal category. The other axiom involves the unit object I.
- We get this triangle, which is called the unit triangle, and is the other axiom for a weak monoidal category.
- Pentagon and triangle are axioms we need for a weak monoidal category, to ensure that we can manipulate structure isomorphisms as if they were equalities. In fact, as this is a one-object 2-category, those are the axioms we need for a weak 2-category, also called a bicategory. The structure isomorphisms are also called coherence constraints, and the question of how constraints in general interact is one of the big questions of higher-dimensional category theory. It is the question of coherence.
Coherence
- Which diagrams commute in a particular type of category, as a consequence of axioms.
- Interaction between different ways of presenting the structure
- Example we represent basic associativity (of multiplication or composition) like this:
- Local: for any a,b,c (ab)c = a(bc)
- Global: any finite string a1 a2 … an has unique well defined product.
- Examples 2 For monoidal categories
- Local: for any objects a,b,c,d the above pentagon and triangle commute.
- Global: All diagrams of structure isomorphisms commute.
- The point of the “global” description is that if all diagrams of structure isomorphisms commute, then we can move around them without worrying exactly which path we took, which is somewhat how we manipulate equalities.
- The fact that those two presentations of monoidal categories (or bicategories) are equivalent is a deep theorem of Mac Lane called a coherence theorem, specifically, coherence for monoidal categories.
- However, another point of view is to define monoidal categories by saying “all diagrams commute” and then prove a coherence theorem saying that it suffices to know that the pentagon and triangle commute.
- Or to find a small set of axioms that generates all the commuting diagrams.
- When we are checking that something is a monoidal category in the first place it is necessary to have a small set of axioms to check because we can’t physically check that all diagrams commute.
- But when we are working with (or in) a monoidal category we usually use the fact that all diagrams commute, as the diagram we’re looking at is typically not precisely a pentagon or triangle. The important thing is that we have both possibilities and we know they’re equivalent.
- As a case in point, when Mac Lane was first making the definition of monoidal category his list of axioms was longer; it was only later that Max Kelly proved that some were redundant. However, arguably Mac Lane had a point, because more axioms turn out to be needed to understand the next dimension up properly.
- Another way of interpreting coherence for monoidal categories is that weakness doesn’t matter that much, and we can more or less behave as if it’s a strict monoidal category without anything going too wrong. This is why, for example, we can take cartesian products of three sets and not worry too much whether we’re really taking ordered triples (a, b, c) or ((a, b), c) or (a, (b, c)).
- Theorem (Coherence for monoidal categories) Every weak monoidal category is monoidal equivalent to a strict one.
- This coherence theorem is a one-object version of the one for weak 2-categories, which are also called bicategories.
- Theorem (Coherence for bicategories) Every bicategory is biequivalent to a (strict) 2-category.
- Studying higher-dimensional structures in which the bottom dimensions are trivial (containing only one cell) can help us understand and deal with higher dimensions at many levels. A structure with trivial lower dimensions is called degenerate.
Degeneracy
- A degenerate category is one where the lowest dimension is trivial, that is, there is only one object. Once we’re in a 2-category there is one further level of degeneracy we could consider. We have seen that a 2-category with just one 0-cell “is” a monoidal category, but what about a 2-category with just one 0-cell and also one 1-cell? This is called “doubly degenerate”.
- If there is only one 0-cell and only one 1-cell our non-trivial data is now just a set of 2-cells. We now have two types of composition, horizontal and vertical, so we get two binary operations, one coming from vertical composition and the other from horizontal composition. We also know one thing about the interaction between those binary operations, coming from the interchange law. At this point something rather amazing happens, called the Eckmann–Hilton argument.
- For our doubly degenerate 2-category we consider the interchange law in the following special case, with only two of the 2-cells being non-trivial.
- Remember that as the structure is doubly degenerate all the 0-cells are the same, and all 1-cells are identities. We then have the following which I like to call the “Eckmann–Hilton Clock”.
- The “clock” depicts an argument showing this amazing result: horizontal and vertical composition must be the same binary operation, and moreover, it is commutative. The clock is not a formal proof, but it’s the beginning of one: the idea is that every time you move to the next “hour” on the clock face you are performing a coherence isomorphism.
- In summary, we start with a set with two monoid structures on it that are a priori different, but satisfy the interchange law. We then show this means that the second monoid structure isn’t really extra structure, but has the effect of forcing the first one to commute. So a doubly degenerate 2-category “is” a commutative monoid.
- This is a sign of something rather subtle going on in higher dimensions. Higher-dimensional categories are difficult to study for many reasons, and studying various degenerate versions can be a good way to get a handle on subtle coherence questions.
- As we go up dimensions, the gap between strict and weak versions gets wider and wider. We have seen that for 2-categories the strict and weak versions aren’t extremely different. However for 3-categories the gap is wider. Weak 3-categories are called tricategories, and coherence for tricategories is much harder.
- It is much easier to see this effect for doubly degenerate tricategories, that is, tricategories with only one 0-cell and only one 1-cell. This is like a categorified version of what we just did for doubly degenerate bicategories. The Eckmann–Hilton argument showed us that doubly degenerate bicategories produce commutative monoids. When we go up a dimension we have a sort of weak Eckmann–Hilton argument showing that doubly degenerate tricategories produce “weakly commutative monoidal categories”.
- This isomorphism γ is called a braiding, because it is quite a lot like braiding hair. This idea starts from the idea that commutativity can be shown using physical objects by moving them around each other physically.
- Studying degenerate higher-dimensional categories is like studying the footprints left in the snow by some mysterious higher-dimensional creatures, and helps us to understand how much more subtle they are than 2-categories.
n and infinity
- There have been many approaches to defining n-categories, and describing any of them here is far beyond our scope. However, I would like to describe some of the different ideologies behind the approaches. Here are the general features that a definition needs to have.
- Data: A way of producing more dimensions. Higher-dimensional morphisms are sometimes called “cells”.
- Structure: A way of dealing with all the different levels of composition and all the structure/constraint cells that need to exist (and these should all be equivalences at the right level for the codimension).
- Properties: A way of deciding what axioms the constraint cells should satisfy in order to produce a coherent enough structure. The general principle is that at each dimension there are constraint cells whose interaction is mediated by constraint cells at the dimension above; this continues to the top dimension where there is no dimension above, so we need some axioms in the form of equalities. Of course, if we are doing infinity-categories there never is a top dimension so we never have any axioms invoking equalities.
- Notation: One of the most fundamental problems that makes this all hard is the problem of expressing higher-dimensional cells in the first place. We can’t easily draw them any more as we’re stuck with our 2-dimensional pieces of paper. Even once we’ve succeeded in making a definition, doing any sort of calculations or proofs in higher dimensions remains a difficult problem.
Definining using (Iteration vs all at once)
- Some definitions iterate a process of adding a dimension, whereas others start with data giving all dimensions at once. We saw this difference in our two ways of defining 2-categories: one way was by enrichment, where we took the definition of category and added another dimension by using hom-categories instead of hom-sets. The other way involved starting with a 2-globular set as our data, straight off.
- However, for higher categories this idea comes with a complicated feature: as we go up in dimensions, enrichment needs to happen more and more weakly.
- We can work out how to do weak enrichment to produce bicategories at the first step, but iterating that will not produce something as weak as tricategories at the next stage (although it will be slightly weaker than a strict 3-category).
Enrichment vs Internalization
- This gives us the definition of a category internal to another category, and is slightly different from a category enriched in another category. For an internal category, the whole underlying graph is now a diagram inside another category, which means something has happened to the objects as well as the morphisms. This is different from enrichment, where the objects are still just a set.
- We can also compare categories enriched in Cat and categories internal to Cat. Categories enriched in Cat are 2-categories.
- The usual graph definition of category using sets and functions is now a diagram in Cat, that is diagram of categories and functors.
- This means that C1 and C0 themselves have underlying graphs. If we unravel that, we have the diagram in Set shown on the right.
- In this structure the 0-cells (C0)0 have two types of 1-cell between them:
- (C0)1: those coming from the original category of objects C0, and
- (C1)0: the objects of the category of morphisms C1.
- The end result is that 2-cells have this shape; remember that the horizontal and vertical 1-cells come from different parts of the abstract structure and can’t be composed: they’re different.
- Here f and g are the source and target of α in (C1)0 and p and q are the source and target of α in (C0)1 . We could have picked the horizontal and vertical conventions the other way round, but I like it this way as it shows the generalization from globular cells vividly: globular 2-cells can be regarded as square ones in which all the vertical 1-cells are identities (collapsing the sides to a point). This comes from the category C0 being discrete, that is, (C0)1 being trivial; the underlying data then collapses to a 2-globular set.
- This structure with square-shaped 2-cells is called a double category. It still has horizontal and vertical composition and interchange. The square-shaped cells complicate the situation but turn out to be quite efficacious for addressing some questions in algebraic topology. When this process is iterated we get n-dimensional cubes at each dimension, and indeed these types of n-categories are called cubical rather than globular.
Algebraic vs non algebraic
- There are in fact many other different underlying shapes that are possible, and they are usually described by using a different adjective on the word “set”. Thus so far we have had globular sets and cubical sets, but there are also simplicial sets (which have been well studied by topologists for some time) and then shapes called things like “opetopic”, “multitopic”, “dendroidal”, “multisimplicial”
- The shapes are not just arbitrary choices; they’re related to the way in which we then go on to express the structure on the underlying data.
- This is called algebraic because algebra is about operations combining multiple inputs into one output. In higher-dimensional algebra we often need to combine more than two inputs, so we might generalize to “k-ary operations” with k inputs. These generalized operations are often expressed by means of monads.
- We have not really talked about monads but they are special functors which are particularly good for generating algebraic structures “freely”, as we did for the free monoid construction. Once we have generated the structure freely we then say “‘right, now we want this structure actually to have a value in our underlying data”. So for a monoid we would start with an underlying set A, generate the free monoid on it (all the words) and then say: given any word abc, say, I want this actually to have a value in my original underlying set. For example in the natural numbers we would say “2 × 4 × 3 is a valid possible multiplication, now what does it actually equal?” Abstractly this amounts to giving a function free monoid on A -> A.
- What we do for n-categories is something like this: start with an underlying globular set A, generate the free n-category on it, and then evaluate all those operations by means of a morphism (of globular sets) free n-category on A -> A.
- We know that 2 × 4 × 3 definitely equals 24 in the natural numbers. However, there are situations in which answers are less definite. For example, suppose that instead of doing multiplication of natural numbers we are doing products of sets. We know that a product of three sets exists but there are many possible candidates for it. So instead of having one definite answer we have many possible answers, and they are all uniquely isomorphic.
- This idea is expressed by non-algebraic approaches to n-categories. To express structure non-algebraically we don’t actually specify what the results of operations are, we just verify that there is enough structure around making valid possible results exist.
- Non-algebraic approaches typically use shapes of structure more complicated than globular cells, in order to be able to build in enough scope for expressing what the candidates for composites are. Arguably, the approaches based on simplicial sets have made by far the most progress. Simplicial sets are based on “simplices”, which are higher-dimensional generalizations of triangles.
- The simplicial approaches are greatly helped by a huge body of existing work on simplicial sets from the fields of topology and homotopy theory.
Finite dimensions vs isomorphisms forever
- We have seen that a set “is” a category with no non-trivial morphisms, that is, all morphisms are identities. If we relax that condition slightly we get a category in which all the morphisms are isomorphisms. This is the definition of a groupoid.
- Whenever we cut off at n dimensions, we are essentially saying that every morphism at a dimension above n is the identity. Instead, we could say that every morphism above dimension n is an isomorphism, or rather, an equivalence at the appropriate level.
- We will get an infinity category in which every morphism above dimension n is an equivalence, for an appropriate infinite-codimensional notion of equivalence.
- These are sometimes called (∞, n)-categories. They arise naturally in topology because topological spaces effectively have no top dimension — there is always another level of homotopy that can be defined. But sometimes one wants to focus on a few dimensions at the bottom and sort of let the others take care of themselves, hence we look at n dimensions closely but without having to chop off and “seal up” the top dimensions.
- One of the advantages of this approach is that you can do everything maximally weakly right from the start, which might help with iteration. You don’t start with equalities that you then have to weaken to isomorphisms when you go up a dimension (and so on), because you had infinite dimensions all along.
- However, only a finite number of the dimensions are really non-trivial, so you don’t end up with the full complications of infinite dimensions. This approach has been particularly fruitful in non-algebraic definitions, as a certain amount of non-specified-ness is helpful for allowing all those equivalences to whiz around all the way up to infinity. The theory of (∞, 1)-categories is particularly well developed, so much so that they are sometimes called “infinity-categories”.
- You never have to worry about specifying axioms at the top dimension to seal up the ends, because there is no top dimension.
Summary of high dimensional category theory
- Higher-dimensional category theory is currently still developing as a field of research. It is difficult because of the infinite levels of nuance and subtlety that can arise, and because of the difficulties inherent to representing infinite dimensions in our very limited three-dimensional physical world.
- As I said, if you’re shining a light on something to see it better you can raise the light higher up to illuminate a broader area and see more context, but you might see less detail. If you shine the light very close it will be very bright but you will lose context. This is a trade-off we make whenever we get involved with abstraction and higher dimensions. We gain overview and context. We gain the chance to unify a wider variety of structures. We see more connections between different areas. But we also lose detail.
Thinking categorically
- Category theory is about understanding structural reasons behind things, not just constructing formal justifications.
Process of doing category theory
- We see an interesting structure somewhere.
- We express it categorically, that is, using only objects and morphisms in some relevant category.
- We look for that structure in other categories.
- We use it to prove things that will immediately be true in many different categories.
- We investigate how it transports between categories via functors.
- We explore how to generalize it, perhaps by relaxing some conditions.
- We investigate what universal properties it has.
- We ask whether it has generalizations to higher dimensions via categorification.
Practice of category theory
Reasoning
- We use diagrammatic reasoning to make use of geometric intuition as well as logical and algebraic intuition. Proofs are often essentially type-checking. We invoke the “obvious axioms” which might seem obscure but once you understand the principle it’s less obscure: the principle is that if we have two inherently structural ways of mediating between the same things, they should be the same in order to prevent structural incoherence.
Coherence
- We often have two approaches to the same structure, one that starts locally and expands to a global view, and one that starts globally and then pins down a local view that suffices. These two approaches are summarized in the following table.
Universal Properties
- We try and characterize things by properties rather than intrinsic characteristics, and best of all we characterize by universal property, where possible.
Structural Awareness
- We maintain an awareness of our interaction with structure and how we’re using it. For example if we are making use of associativity we make sure we’re aware of it rather than taking it for granted.
- For example, we remain aware of whether we’re saying things are “isomorphic”, or whether we’re exhibiting a specific isomorphism between them. Being specific is harder but gives us a more precise understanding.
Higher dimensions for nuance
- Morphisms are higher-dimensional than objects and give us more nuance. More generally, every higher dimension we involve gives us even more nuance, along with more complications.
Highlights
The way in which children grasp concepts of numbers probably does follow the history of how numbers developed, starting with the counting numbers 1, 2, 3, and so on, then zero, then negative numbers and fractions (maybe the other way round) and eventually irrational numbers.
1.1 Abstraction and analogies
We can try and use rigorous logic in less abstract settings, but we will probably always† run into problems of ambiguity: ambiguity of definitions, ambiguity of interpretations, ambiguity of behavior, and so on.
1.3 Context
It might seem that abstraction takes us further away from “real” situations. This is superficially true, but at the same time abstraction enables us to make connections between situations that are further apart from one another. This is one of the ways in which math helps us understand more things in a more powerful way, by making connections between different situations so that we can study them all at once instead of having to do the work over and over again.
1.4 Relationships
For example, the context of someone’s life situation, how they grew up, what is going on for them in their personal life, and so on, has a big effect on how they behave, and what their achievements represent. The same achievement is much more impressive to me when someone has struggled against many obstructions in life, because of race, gender, gender expression, sexual orientation, poverty, family circumstance, or any number of other struggles.
1.5 Sameness
We will see that category theory is a framework that achieves a remarkable trade-off between good behavior and expressive possibilities. If a framework demands too much good behavior then expressivity is limited, as in a totalitarian state with very strict laws. On the other hand if there are too few demands, then there is great potential for expressivity, but also for chaos and anarchy. Category theory achieves a productive balance between those, in the way it specifies what type of relationship it is going to study.
1.6 Characterizing things by the role they play
However, when we study ideas that are more complex than numbers, much more subtle notions of sameness are possible. To take a very far opposite extreme, if we are thinking about people then the notion of “equality” becomes rather complicated.
1.7 Zooming in and out
One of the advantages of characterizing things by the role they play in context is that you can then make comparisons across different contexts, by finding things that play analogous roles in other contexts.
1.8 Framework and techniques
Category theory is a theory of mathematics, but is itself a piece of mathematics, and so it can be used to study itself. This sounds self-referential, but what ends up happening is that although we are still in category theory we find ourselves in a slightly higher dimension of category theory. Dimensions in this case refer to levels of relationship.
ous philosophies. It is still entirely rigorous technical mathematics. It sets up a framework for implementing these philosophies and pursuing these goals rigorously. The framework consists of a formal definition of a category as an algebraic structure, and then techniques for studying these structures and for constructing and investigating particular features that might arise in them.
2.2 The twin disciplines of logic and abstraction
The framework of mathematics involves the twin disciplines of logic and abstraction. Math is not unique in its use of either of these things, but I regard it as being more or less defined by its use of these in combination.
2.3 Forgetting details
Abstraction is about digging deep into a situation to find out what is at its core making it tick. Another way to think of it is about stripping away irrelevant details, or rather, stripping away details that are irrelevant to what we’re thinking about now.
2.4 Pros and cons
I will now acknowledge some disadvantages of abstraction. One is that it does take some effort, but I do think this is about front-loading effort in order to reap rewards from it later. I think that it’s an investment, and the extra effort early means that we can understand more things more deeply with less effort later. Another disadvantage is that we lose details.
For example, it’s unavoidable to have a gut instinct when we meet a new person, but it’s wrong to hold onto that instead of actually responding to the person as we get to know them, especially when our gut instinct is skewed by implicit bias as it (by definition) always is.
2.5 Making analogies into actual things
Abstraction comes from seeing analogies between different situations. This is a particular form of detail-forgetting, based in finding connections between different situations, rather than just arbitrarily ignoring details.
2.6 Different abstractions of the same thing
through a field, and actually marking out where the path is.
really think that just retorting “That’s not the same” is ineffective, and that using some more careful logic is more productive. Here is a level of abstraction that does yield that analogy, and a different level that differentiates between those two conclusions:
2.7 Abstraction journey through levels of math
T 2.1 What are some senses in which addition and multiplication are “the same”? What are some senses in which they are “different”? Addition and multiplication are both binary operations: they take two inputs and produce one answer at the end. In the first instance they are binary operations on numbers, but as math progresses through different levels of abstraction we find ways of defining things like addition and multiplication on other types of mathematical object as well. As binary operations, they have some features in common, including that the order in which we put the numbers doesn’t matter (which is commutativity) and nor does how we parenthesize (which is associativity). However, addition and multiplication behave differently in various ways. For example, addition can always be “undone” by subtraction, but multiplication can only sometimes be “undone” by division: multiplication by 0 can’t be undone by division. This is sometimes thought of as “you can’t divide by 0” but we’ll come up with some better abstract accounts of this later.
We could describe this in words as “if we add two numbers together it doesn’t matter what order we put them”, but this is a bit long-winded. The concise abstract way of saying it is: given any numbers a and b, a + b = b + a.
The top level here, with the abstract binary operation, is the kind of thing we study in “abstract algebra” if we take some higher level math at university. Binary operations are studied in group theory,
. I think this is like swinging from a rope — if you hang the rope from a higher pivot then you can swing much further, provided you have a long rope. It’s also like shining a light from above — if you raise it higher then the light will become less bright but you will illuminate a wider area. The result is perhaps more of an overview and an idea of context, rather than a close-up of the details. However, you won’t lose the details forever as long as you retain the ability to move the light up and down. Furthermore, if you can find a way to make the light itself brighter, then you can see more detail and more context at the same time. I think this is an important aspect of becoming more intelligent, and that abstract mathematics can help us with that.
3.1 Mathematics as pattern spotting
Patterns are aesthetically pleasing, but they are also about efficiency. They are a way to use a small amount of information to generate a larger amount of information, or a small amount of brain power to understand a large amount of information.
The fact that multiples of 10 end in 0 is nothing to do with any inherent property of the number 10, but is because we have chosen to write numbers in base 10. If we wrote numbers in base 9 then it would be all the multiples of 9 that end in 0, and multiplying by 9 is what would be done by sticking a 0 on the end. Similarly the fact that multiples of 5 and 2 have such a tidy pattern in their last digit is nothing to do with any inherent property of 5 and 2, but because of their relationship with 10: they are factors.
3.3 Patterns as signs of structure
Patterns are really analogies between different situations, which is what category theory is going to be all about. At a visual level, we could talk about “stripes”, for example, and understand that we mean alternating lines in different colors. We might not know the specific details – how wide the lines are, what the colors are, what direction they’re pointing – but there is something analogous going on between all different situations involving stripes, and the abstract concept behind it is the concept of a “stripe”. Patterns for clothes are also analogies, this time between different items of clothing. A dress pattern is like an abstract version of the dress.
A general principle of pattern spotting is that visual patterns might be easy to spot in simple examples, but the abstract structure might be easier to reason with, use or even verify, in more complex situations. It would be harder to draw the table for multiples of a much larger number, and if the patterns in the table were less obvious then it would be harder to see them. In situations of higher dimensions it is then even harder
3.4 Abstract structure as a type of pattern
If category theory is the mathematics of mathematics, then categorical structure is about patterns in patterns.
3.5 Abstraction helps us see patterns
Finding the abstract structure in situations and expressing it in some way, often as a diagram to make it less abstract, can help us see the patterns and relationships between situations.
Someone then objects, for either of these two reasons:
- They see a more specific principle W at work
that is really the reason behind A, so they do not consider A and B to be analogous: X W A B 2 They see a more general principle Y that they think the first person is invoking. This makes some other thing C analogous, and they object to that.
4 Context
Thus truth is not absolute but is contextual, and so we should always be clear about the context we’re considering. This idea is central to category theory.
4.1 Distance
So a circle in this taxi world is just a collection of disconnected dots in a diamond shape. How does that make you feel? Do you feel uncomfortable, as if this somehow violates natural geometry? Or do you feel tickled that a circle can look so funny? Both reactions are valid. The main thing is to appreciate that even some of the most basic things we think we know are only true in a particular context, and things can look very different in another context. It is important to be a) clear what context we’re considering at any given moment (which we usually aren’t in basic math lessons), and b) open to shifting context and finding different things that can happen.
4.3 The zero world
The zero world might not seem very interesting — you can’t really do anything in it. Or rather, you can do anything in it and it’s all equally valid. It turns out that a world in which everything is equally valid is not very interesting, and is more or less the same as a world in which nothing is possible.
5 Relationships
Now we’re going to see that different contexts can be provided by looking at different types of relationship. For example, if we relate people by age we get a different context from if we relate them by wealth or power.
5.1 Family relationships
If we represent a relationship using arrows rather than physical positioning on the page, we can draw things any of these ways up (and others) without affecting the relationship we’re expressing: A B A B A B That is the point of the arrowhead
5.2 Symmetry
We are going to see that this way of depicting and compiling relationships is remarkably fruitful. It is general and flexible enough to be usable in a vast range of situations, and illuminating enough to have become a widespread technique in modern math and central to category theory. However we will see that we do need to impose some conditions to make sure we don’t have ambiguities.
In the case of the rectangle it’s a relationship between these two pictures. In the case of the square it’s a relationship between these two pictures: the square and itself.
5.4 Modular arithmetic
It now looks a lot like our depiction of rotations, and we can go ahead and put these in a table; it’s rather large (well, infinite) but has some patterns in it that help us tell what is going to happen later without us having to fill in the whole table.
5.5 Quadrilaterals
the n-hour clock) will be smaller. We only have a finite quantity of numbers on the n-hour clock — the numbers 1,…, n (or 0,…, n − 1). We regard n as being the same as 0, a bit like when we regarded 360◦ as being the same as 0◦ for rotations of a square.
So we have the following compilation of relationships, and this diagram of arrows that looks just like some other situations we’ve seen already:
Special cases are often found by imposing extra conditions on a situation, and generalizations are found by relaxing conditions. Thinking about the conditions making a quadrilateral a square, or a trapezoid,† or some other special case can help us see how to relax them gradually to make more general cases.
5.6 Lattices of factors
If we try to put all the types of quadrilateral into a Venn∗ diagram it’s hard.
Consider the number 30. If we think about all its factors, those are the numbers a related to it as shown.
This is the key to “why” this is a cube: 42 has three distinct prime factors.† In this depiction each one gives a dimension, so we have a 3-dimensional object. Notice that the parallel edges are all the same type of relationship — either ×2, ×3 or ×7.
This shape is 2-dimensional: it consists of three (2-dimensional) squares side by side. The two dimensions are given by ×2 and ×3 — they arise from the fact that 24 has only two distinct prime factors. The fact that 2 is a repeated factor (three times) appears visually in the fact that there are three squares in a row. This is because we can travel three times in the “×2” direction.
Now for the point of the abstraction: at this level of abstraction we can have a, b, c being any three things, not necessarily prime numbers, and not necessarily numbers at all because we are not trying to multiply them. For example they could be three types of privilege, such as rich, white, male. We get this diagram:
analogous to thinking we could make the cube of factors of 42 by putting the smallest numbers at the bottom level above 1. That didn’t work because 6 < 7 so 6 is lower in the hierarchy of sheer size, but 6 has more prime factors than 7 so is higher up in the hierarchy of number of factors. Later we will see that these are questions of
- totally ordered sets vs partially ordered sets, and
- order-preserving vs non-order-preserving maps.
6.2 Why we express things formally
Formal mathematical language and notation are partly to do with efficiency, and partly to do with abstraction (and those two concepts are themselves related).
us to package up multiple concepts into a single unit that our brains can treat as a new object, which is one of the crucial aspects of abstraction.
Criterion 1: distance is a number
6.3 Example: metric spaces
Writing those variables as x and y means that the numbers could be different but it still allows for the possibility of them being the same. Whereas if you write them both as x then you have declared in advance that they’re the same and ruled out the possibility of them being different.
if you stop off somewhere along the way it should not make your distance any less. At best it won’tchange the distance, but it might well make the journey longer.
In situations where it is impossible to write everything down one by one it can be extremely helpful to have a formal and/or abstract way of writing things, so that we can give a sort of recipe or make a machine for working every case out, without actually having to write out every case one by one.
this notation instead: 6 | m means “6 divides m”, or “6 goes into m”, which is the same as saying m is a multiple of 6, just the other way round.
(A lemma is a small result that we prove, smaller than a proposition, which is in turn smaller than a theorem.
6.5 Example: modular arithmetic
This sounds unrigorous but we can put in technical work early on to make that level rigorous. This is what category theory is often about, which is one of the reasons I love it so much: I feel like I’m spending much more time working at the level of ideas, which is my favorite level, rather than the level of technicalities.
Category theory is based on the idea of relationships. We build contexts in which to study things. We build them out of objects, and relationships between objects.
7.3 Reflexivity
A relation is called reflexive if it sees everything to be related to itself. That is, every object a satisfies a a.
This shows that this particular is not reflexive. If there’s one case that contradicts a “for all” statement it’s called a counterexample. There might well be more than one counterexample, but you only need one in order to show that a “for all” statement isn’t true.
7.4 Symmetry
A relation is called symmetric if it’s “the same both ways round”, that is, it doesn’t matter which way round you write it. That doesn’t mean it’s always true both ways round, it just means that its truth doesn’t change if you write it the other way. Here’s the formal definition.
7.5 Transitivity
Note that where reflexivity involves only one object at a time, symmetry involves two objects at a time, and transitivity involves three. And let me just re-emphasize that these are not necessarily three distinct objects.
7.6 Equivalence relations
Definition 7.11 If a relation on a set S is reflexive, symmetric and transitive then we call it an equivalence relation.
T 7.9 This time let S be the set of locations and be the relation “is east of”. Is this reflexive, symmetric, transitive?
Earlier on we saw a version of “more or less the same as” that is not transitive, when we looked at people born within a month of each other. Although we did it for people and ages, that is essentially the same as for numbers. We could make “more or less the same as” mean “within ε of each other”† for any value of ε > 0 and it still wouldn’t be transitive, no matter how small we made ε. (It would, however, be reflexive and symmetric.
. In math (and in life) if something doesn’t fit our rigid constraints we can either continue to exclude them, or relax our constraints to let them in. In both math and life I believe in recognizing when our constraints have been unreasonably rigid, excluding things and people just because of preconceptions, out-dated practices, or fear. I believe in inclusivity in math and in life.
We’re going to define a framework for thinking about relationships. In order to make sure we are thinking about slightly reasonable types of relationships, we will stipulate that they at least behave slightly well, so that we can do various things with them. These stipulations will be inspired by some of the things we’ve already seen, but will be less stringent than the stipulations on equivalence relations.
they also might not be anything like relationships, so we more generally call them arrows, or “morphisms”, inspired by examples where they transform or “morph” one thing into another. (However in this book we might still informally refer to them as relationships). We draw them like this: a b,
So we say that given any object a there must be at least an arrow like this, called an identity.
This is similar to transitivity, but different. The relations of the previous chapter were yes/no situations: things just were or weren’t related. Now we’re in “sense in which” situations, so this is more like saying: if there’s a sense in which a is related to b and a sense in which b is related to c then we can combine those to get a sense in which a is related to c.
8.3 Properties: stipulations on the structure
doesn’t do anything, and those elements are generally called identities. If I line up these conditions I hope the analogy is clear. 0 is the identity for + on (real) numbers: ∀a ∈ R a + 0 = a 1 is the identity for × on (real) numbers: ∀a ∈ R a × 1 = a
In this situation both ways produce the same relationship between A and D. This is associativity and we will now state it in the general situation.
8.4 The formal definition
This then gives us a concept of different sizes of category, defined as follows: • If the objects and the morphisms each form a set the category is called small. • If each individual collection C(a, b) is a set then the category is called locally small; in this case the objects might form a collection, not a set.
8.7 Drawing helpful diagrams
We usually don’t bother drawing identity arrows because they’re always there. Occasionally we draw them if we’re trying to emphasize something, for example if two arrows compose to the identity.
- We omit arrows whose existence we can deduce from composition.
Definition 8.2 A diagram in a category is a collection of objects and arrows from the category, possibly not all of them. A diagram is said to commute if any two composable strings with the same endpoints produce the same composite.
9.2 Equivalence relations
The identity arrow is the “trivial symmetry” which is technically “rotation by 0◦”. This is one of the reasons that mathematicians like considering that to be a symmetry although you might not usually do that in normal life. In normal life you’d say “this thing has no symmetry” rather than “this thing has one symmetry, the trivial symmetry”.
9.3 Factors
In Section 5.6 we drew some diagrams of factors which were in fact diagrams of categories. We start by picking a number, say 30 as we did in that section. Then we make a category with • objects: all the factors of 30 • arrows: an arrow a b whenever a is a factor of b. We could also do this the other way round and say there’s an arrow a b whenever a is a multiple of b, and the information in the diagram will be the same; it will just be depicted with the arrows pointing the other way. Turning the arrows around is called taking the dual in category theory,
9.4 Number systems
T 9.3 What would happen if we took our objects to be the whole of N instead?
The thing is to remember to omit arrows we don’t need as they can be deduced: identities (the “loops” above) and composites. This “tidies up” the diagram to look like this instead:
10.1 Totally ordered sets
An ordered set is a set equipped with an ordering. An ordering is a way of organizing all the objects in an order. A totally ordered set is one that is “totally organized”
Non-categorical definition of ordered set An ordered set is a set S equipped with a binary relation ≤ satisfying • reflexivity: a ≤ a for all a ∈ S • antisymmetry: if a ≤ b and b ≤ a then a = b • transitivity: if a ≤ b and b ≤ c then a ≤ c • trichotomy†: for all a, b ∈ S , a ≤ b or b ≤ a
10.2 Partially ordered sets
We just saw that a totally ordered set has “exactly one” arrow between any pair of objects, and thus there are two ways to fail: • a pair of objects with more than one arrow between them, or • a pair of objects with fewer than one arrow between them (i.e. none). We could now try relaxing this definition by maintaining the first condition but dropping the second, so we are thinking about categories in which there is at most one arrow between any two objects, but possibly none.
Definition 10.2 A partially ordered set is a category in which for any objects a, b there is at most one arrow between them.
The objects of a category can be points, sets, sets of sets, whole categories, entire mathematical worlds… And I do like the fact that many types of historically pre-existing mathematical structure can be encapsulated as a special type of category.
11.1 Small drawable examples
The objects and arrows have no meaning here; all we’re specifying is the structure of the category. This is different from situations where we take the objects to be “all the factors of 30” or “all the natural numbers” in which case those objects come with properties and behaviors already.
11.2 Monoids
However we sometimes call identity arrows “trivial”, so we can think of discrete categories as having no non-trivial arrows.
is the same structure we described with the f notation above, except that then all the arrows were written as f n rather than n. Composition was like multiplication, but really it was addition of natural numbers in the exponent: f n ◦ f m = f n+m.
In the data, the dummy object comes from nowhere and has no meaning. In any category with a single object it doesn’t matter what that object is; it mostly just serves to ensure that all arrows are composable. So we often ignore it.
11.3 Groups
If instead we imposed an equation on some of those composites then it would no longer be a “free” monoid (because we’ve imposed some constraints). For example we could declare that f 2 is a new arrow and f 3 is a new arrow but that f 4 = 1. Then by associativity we find various other relationships, as shown, and the only four arrows in this category are now 1, f, f 2, f 3.
inverses”.
If instead we think of the presentation using arrows f k, then this all comes to the same thing, just at the level of exponents instead. The arrow f k has inverse f n−k since f k ◦ f n−k = f n = 1.
restricted — there can be at most one from any object a to an object b. By contrast in a category coming from a group the objects are restricted: there is just one, the “dummy” object.
Groups are often introduced directly via symmetry. The idea is just like what we did with the symmetries of a square in Chapter 5, but now with any shape we choose: any two symmetries of a given shape can be combined to produce another symmetry of that shape, and that structure forms a group.
11.4 Points and paths
The first condition ensures that we have a monoid, and the second says it is a monoid with inverses. Now, we can relax this definition by dropping the second condition, and we’ll get back to monoids. But we could instead relax this definition by dropping the first condition, as follows. Definition 11.5 A groupoid is a category in which every arrow has an inverse.
This is the sort of thing that is studied in topology: what is it that makes the shape of one space really different from the shape of another? If you just moved a wall inwards slightly then the size of the space would change but in some sense not really the shape. Likewise if you shrank the entire building.
These ideas are all from the study of topological spaces. I think the technical definition of a topological space is too much of a digression for me to go into here (see Appendix D for a little more detail), but the idea is that there is a notion of “continuous deformation” where we think about whether or not we can continuously morph one thing into another without really changing it or breaking it at any stage. The three paths from a to b in the left-hand diagram above would formally count as “the same” in the sense that we could define each one as a function and then define something called a “homotopy”† that continuously deforms one function into the other. This also helps us deal with the technical question of associativity.
12 Sets and functions
Sets and functions A first example of a large category of mathematical structures. This is one of the fundamental motivating examples of category theory.
12.1 Functions
that the set is special in some way, by having an ordering, or by having a binary operation, or by having a notion of closeness. The starting point for the maps between structures is then the concept of a function, the basic notion of a map between sets. We then find a good notion of map between special structures by looking at maps that “preserve” the special properties in question. We’ll look at that, but first we need to think about functions.
can build the concept of set membership from the concept of a function. It’s really a matter of preference which concept you take to be more fundamental.
It’s also important to note that all the inputs have to produce something. If we ran out of bananas and just left the “b” slot empty then it would not count as a function any more.
If we generalize to p inputs and k outputs we see that each input has a choice of k outputs, so the total number of possible functions is: k ×···× k p times = kp.
Definition 12.1 Let A and B be any sets. A function A f B assigns to every element a ∈ A an element f(a) ∈ B. In very formal set theory the definition happens by means of “ordered pairs”: we construct a new set from A and B consisting of pairs of elements, one from A and one from B, representing the input–output pairs that define f
Definition 12.2 Let f, g be functions A B. We say f = g as functions whenever ∀a ∈ A f(a) = g(a)
12.2 Structure: identities and composition
Given any set A there is an identity function A A which just sends every element of A to itself. We can call it 1A and define it by ∀a ∈ A 1A(a) = a.
12.3 Properties: unit and associativity laws
For the unit laws we need to check that the identity function behaves like the identity on each side, that is, given a function A f B we need to check these two equations hold.
12.4 The category of sets and functions
We now have all we need to construct the very important category of sets and functions. This category is typically written as Set and is given by: • objects: all sets • morphisms: a morphism A B is a function A B • identities: given a set A, the identity is the identity function 1A • composition: composition of morphisms is composition of functions.
13.1 Monoids
Large worlds of mathematical structures
Adding them together before mapping gives this: f(n + m) = n + m Mapping them first before adding them gives this: f(n) + f(m) = n + m So it doesn’t matter which way we do it, and this is one of the key conditions for being a “sensible” function between monoids. The condition is expressed abstractly like this: f(n + m) = f(n) + f(m)
Anyway, we only have to find one place where this goes wrong in order to show that something has gone wrong, so let’s take n = 1 and m = 2. Then f(n + m) = f(3) = 2 but f(n) + f(m) = 1 + (−1) = 0. So this function does not respect addition.
However, if you get really into the spirit of category theory you’ll start understanding what counts as “obvious axioms”
13.2 Groups
So g ◦ f is a monoid morphism as required. Thus we have a category Mnd whose objects are all the monoids, and whose morphisms are all the monoid morphisms between them. We quite often name categories like this: naming them after their objects, in abbreviation, in boldface. This is when it is sort of “obvious” what morphisms we are using. When it’s not, then we might name the category after their morphisms; we’ll see some examples of that later.
Proving that the condition on identities was redundant depended on the existence of inverses, which is why it doesn’t happen for general monoids.
This formal definition includes the ambiguous cases as order-preserving, because the ordering includes equality as a possibility. If we didn’t want to allow it we’d have to do something “stricter” and perhaps use < instead. The trouble is that it’s not such a categorical notion. (Recall that when we tried to express < as arrows in a category we found we would not have any identities.) Another way we could eliminate the ambiguous cases would be to put in a condition saying that different elements of A are not allowed to land on the same place in B,
In fact this is a sensible, interesting and illuminating condition to think about for any functions, not just order-preserving ones. It’s called “injectivity”
When ordered by number of types of privilege, poor white men have two types and so are “higher” on the page than rich black women; poor white men are in the position of 6 and rich black women are in the position of 7 with only one type of privilege. However, when it comes to absolute privilege I am
sure that a sufficient amount of wealth can greatly mitigate for the very real disadvantages of being black and female, where no amount of maleness and whiteness can counteract being very poor, perhaps unemployed or homeless. Thus as with the factors of 42 we have an identity function that does not preserve order.
13.4 Topological spaces
In calculus one goes to great lengths to prove that continuous functions compose to make continuous functions. That is very important, and together with the (easier) fact that the identity function is continuous, it gives us a category of topological spaces, written Top, with • objects: all the topological spaces • morphisms: a morphism A B is a continuous function A B.
13.5 Categories
if these were made of playdough you could turn one into the other by continuously squidging it around, without ever breaking or piercing it or sticking separate parts together. This is a more subtle notion of sameness appropriate for topology, and is technically called homotopy equivalence.
categories. So should group homomorphisms and order-preserving functions. The totality of monoids should sit inside the totality of categories as something we might call a “sub-category”. We need a concept of “morphism between categories”, and we can arrive at the definition by our usual method of thinking about structure-preserving maps.
13.6 Matrices
One of my favorite examples is the category of matrices. In this category again it’s not the objects that are really interesting but the morphisms: the morphisms are matrices. That is, we regard matrices as a sort of map.
of composability matches the condition of when we can multiply matrices. We get a category Mat with • objects: the natural numbers • arrows: an arrow a b is an a × b matrix • composition: matrix multiplication.
We need a more subtle notion of sameness that doesn’t demand that objects are exactly the same but finds some pertinent sense in which they’re the same, and gives us a framework for using that sense as a pivot in similar ways to how we use equations to pivot between two different points of view.
The point of an equation is to use the sense in which two sides are the same to pivot between the senses in which they aren’t. Category theory says that the “sense in which they’re the same” can be more relaxed than equality as long as it still gives us a way to pivot between two sides.
Category theory gives us a framework in which we can say something more subtle. As we’ll later see, when we go into higher dimensions, each extra dimension gives us another layer of subtlety. Categories have one extra dimension over sets. That extra dimension is where we express relationships between objects, and we are now going to use that dimension to express this particularly strong form of relationship, that is, categorical sameness.
14.3 Isomorphism in a category
Note that for composition in a category we do have to be careful about the order, but the sides can be confusing so instead of talking about composing on the “left” or “right” of f I will say • post-composing by g if we compose g after f , giving this: • pre-composing by g if we compose g before f , giving:
Isomorphism is the “more nuanced version of sameness” of category theory. Let’s now see how category theory treats isomorphic objects as the same. The point of the framework of categories is to study objects in a category via their relationships with other objects, not via their intrinsic characteristics.
Isomorphic objects are treated as the same by the rest of the category because they have the same relationships with other objects in the category.
If we look at morphisms to x instead, we need to pre-compose with the isomorphisms rather than post-compose, to get the correspondence going. The diagrams would be like this.
To construct an isomorphism we need to give one function going in each direction and show that they compose to the identity both ways round.
define what it means for an infinite set to have the “same number” of elements as another. This gives us the notion of cardinality of an infinite set, and the idea that there are different orders of infinity: this is when infinite sets have no isomorphism between them, so have different “sizes” of infinity.
Non-categorical definition of bijection A function A f B is a bijection if for every element b ∈ B there is a unique element a ∈ A such that f(a) = b.
14.6 Isomorphisms of large structures
We have shown that if f is a bijective homomorphism then it is an isomorphism of monoids. For the converse we have to show that if f is an isomorphism of monoids then it is a bijective homomorphism. This is immediate as f is a homomorphism, and it has an inverse, so it is certainly an isomorphism at the level of sets and thus must be a bijection.
In summary, the names of the objects are not important at all, it’s the interaction between the objects which determines the structure.
This is related to the “deep meaning” of the situation which is that if we count rotations in quarter-turns instead of degrees then we really get the integers mod 4. Or, to look at it the other way round, if we put the integers mod 4 on a 4-hour clock they are really indicating the four possible rotations of a square.
Groups can be referred to by their deep structure rather than their superficial labels. For example, the group of rotations of a square or the integers mod 4 under addition or anything else with the same structure is the cyclic group of order 4.
a bijection, the point being that the inverse is automatically order-preserving.
Incidentally, isomorphism is sort of the “wrong” notion of sameness for topological space. When it’s defined directly in topology (rather than via categories) it gets the name homeomorphism (not to be confused with homomorphism†) but often the type of sameness we’re interested in is the kind we talked about earlier where you continuously deform things, and this is called homotopy equivalence.
Thus any time we invoke an equality between objects in a category we have done something not very categorical, or not really in the spirit of category theory.
Categorical uniqueness
15 Monics and epics
Another example of doing things categorically, that is, moving away from elements and expressing everything in terms of morphisms.
15.1 The asymmetry of functions
The external way is to decide on the places you want to visit, and then work out how to get to them. The internal way is to just plonk yourself in the middle of the city and start following your nose.
15.2 Injective and surjective functions
Injective functions
To prove that a function is not injective we have to prove the negation† of the definition of injective, that is: ∃ x, y ∈ A such that f(x) = f(y) but x y.
To show that something is not surjective we need to negate the definition, which gives us this: ∃ b ∈ B such that ∀a ∈ A f(a) b.
Lisa Selin Davis, “For 18 years, I thought she was stealing my identity. Until I found her.” The Guardian, April 3, 2017. https://www.theguardian.com/us-news/2017/apr/03/identity-theft-racial-justice
For injective, the definition starts “for all x, y ∈ A”. We can now stop because A is empty, so whatever happens this condition is vacuously satisfied. Thus the function is injective. For surjective there is a part of the definition that says “∃ a ∈ A such that. . . ” and then we’re in trouble because there is no element in A. The only way we could survive this is if the condition is vacuously satisfied, that is: the condition starts with “∀b ∈ B” so if B is empty then the condition is vacuously satisfied.
15.3 Monics: categorical injectivity
The definitions of injectivity and surjectivity had elements of sets all over them. To express them categorically we need to express them using only sets and functions, not sets and elements. So we need to avoid saying anything like “for any element in A” or “there exists an element in A”.
Checking that monics are a categorical version of injectivity amounts to checking that in the case of Set monics correspond to injective functions.
Proposition 15.6 Let f be a morphism in any category. If f is an isomorphism then f is monic.
15.4 Epics: categorical surjectivity
with the categorical version we can see a very precise sense in which they are the other way round from each other: they are duals, which means that in the categorical definitions all we need to do is turn all the morphisms to point the other way.
Definition 15.10 The image of a function f : a b is a subset of b defined as follows: Im f = f(x) | x ∈ a
Proposition 15.11 Let f be a morphism in any category. If f is an isomorphism then f is epic.
In Chapter 17 we are going to talk about the fact that we can get results “for free” by turning all the arrows around, which is called duality. This means we will be able to say “and dually” for epics here, but it’s not a bad idea to try writing it out directly anyway, by turning around all the arrows in the proof that isomorphisms are monic.
15.5 Relationship with isomorphisms
The Axiom of Choice says that it is possible, and this axiom is logically equivalent to saying that all epics split. There are different versions of set theory that include or don’t include the Axiom of Choice.
For example, consider the monoid of natural numbers N under addition. We will try to define a monoid homomorphism f to some other monoid M. • We know that 0 is the identity in N so it must go to the identity in M; we have no choice about that. • We can send 1 anywhere we want. • We know that 2 = 1+1 in N, and by the definition of monoid homomorphism we must have f(1 + 1) = f(1) + f(1) so we have no choice about where 2 goes: it has to go to f(1) + f(1). • Something similar is now true for every other natural number. Every n is a sum of 1’s and so we have no choice over where it goes: it has to go to the n-fold sum of f(1)’s. What we’ve done here is based on the fact that N is the free monoid built up from a single element.
Note that f is injective and this is enough to ensure it is monic in Mnd. So in fact f is monic and epic, but it is not an isomorphism.
There’s no categorical reason that a subset inclusion is any better than any other kind of monic, and so in more general situations monics are used to indicate subobjects.
16.1 Role vs character
We could describe 0 as a number representing nothing, which is describing it by an intrinsic characteristic. Or we could describe it as the unique number such that when you add it to any other number nothing happens. Not only does 0 play this role but, crucially, it is the only number that plays this role, so we can describe it by that role and all know we’re talking about the same number.
The number 1 is the unique number such that when we multiply it by any other number nothing happens. Formally we can say:† ∃! a ∈ R such that ∀ x ∈ R ax = x. Every part of this definition is important and we must get all the clauses in the right order. If we just look at the end part “ax = x” we might be tempted to say this is true when x = 0. Now, “ax = x” is indeed true when x = 0, but we’re not supposed to be looking for one value of x where this is true, we’re supposed to be looking for one value of a that makes this true for all x. The only number that works is 1, so 1 is the unique number with this property.
16.2 Extremities
We have to arbitrarily pick one and call it i, and then the other one is −i. However, as we can’t tell them apart until we’ve picked one, we also have no way to say which one we’ve picked. The whole thing should feel very disconcerting, maybe a bit quantum.
16.3 Formal definition
It is more rigorous to identify the extremity relative to the arrows in the category, rather than relying on the physical positioning on the page. We can say that 30, 42 and rich white men are each in a position where all arrows begin (with the direction for arrows that I’ve chosen here)
Definition 16.1 An object I in a category C is initial if for every object X ∈ C there is a unique morphism I X.
16.4 Uniqueness
More generally in any category with more than one object and no non-trivial morphisms there is no initial object because there just aren’t enough morphisms. To have an initial object we must at the very least have an object with a morphism going everywhere else.
Proposition 16.3 If I is uniquely isomorphic to an initial object I then it is also initial.
16.5 Terminal objects
Proposition 16.4 Any object isomorphic to an initial object in C is initial.
16.6 Ways to fail
Definition 16.5 An object T in a category C is terminal if for every object X ∈ C there is a unique morphism X T.
That is, some categories fail to have a terminal/initial object because they have too many morphisms, and some fail because they have too few.
This way of adding a terminal object that’s missing is quite in the spirit of higher mathematics: we find ourselves in a situation that is lacking something, and that lack is preventing us from doing something we want, so we construct a new world in which we’ve added that thing in. This is how we get from the natural numbers to the integers and then to the rationals, the reals, and the complex numbers.
16.7 Examples
This example has a pair of parallel arrows, meaning there are too many morphisms for a to be initial and too many for b to be terminal. This is another self-dual example.
For the formula, we saw that if we have n inputs and p outputs then the number of possible functions is pn. Now observe that pn = 1 if and only if p = 1 or n = 0. Let’s think about the outputs first. Intuitively the condition p = 1 means we have only one output, so only one option for where any inputs go, thus only one possible function. Thus any set with only one element is terminal: if a set B has only one element, then for any set A there is exactly one function A B.
Thus this initial object is actually strictly unique. In category theory we say something is “strictly” the case to contrast it with being the case “up to isomorphism”
Likewise for spaces, the intuition is that the unique function from any space to the one-element space is continuous because everything lands on the same point, thus everything ends up close together and nothing is broken apart.
to any other, that is, the trivial group is initial in Grp, as well as being terminal. This is quite an interesting situation so gets a name.
16.8 Context
In the diagram of quadrilaterals “square” was initial and “quadrilateral” was terminal. This was because everything was a type of quadrilateral, and squares turned out to be special cases of everything.
The question then is whether we can go round the dotted arrows and still get to the empty set. For posets and topological spaces we could, but for monoids and groups the dotted arrow took us to a 1-element set, not the empty set. We will talk about this more when we talk about functors preserving structure.
16.9 Further topics
Similarly category theory should not be about getting fixed in one category. Expressing things as categories is only the start. What’s more important is moving between different categories and thereby seeing the same structure from different points of view, which is why we will soon come to functors, which are morphisms between categories.
Freely generated algebraic structures are related to the use of functors to move between categories.
17.1 Turning arrows around
We can regard all arrows in a category as pointing the other way, and this gives us the dual category. One advantage is that we immediately get a dual version of every construction and every theorem.
If we think about our 2 by 4 grid of objects above, what is the relationship between this grid and the numbers 2 and 4? We might say there are 2 rows and 4 columns, but that sort of presupposes an understanding of what rows and columns are. We might say its height is 2 and its width is 4, but that also presupposes concepts of height and width. Here is something we could say that’s (perhaps) more fundamental.
Definition 18.1 Given objects a and b in a category, a product for them is:
Terminology This sort of situation is going to come up repeatedly so it’s useful to have some terminology. • The morphisms p and q are called projections. • The morphism k is called a factorization. We are factorizing f and g. • There is a general type of diagram called a cone which consists of a vertex and the morphisms from that vertex to everything else. In this case the vertex is a × b and “everything else” is just the objects a and b. • The product is the universal cone, universal among all cones of this shape. • We say the universal property induces the factorization k.
18.3 Products as terminal objects
We know that terminal objects are unique up to unique isomorphism, and products are a terminal object somewhere, so products must also be unique up to
18.4 Products in Set
unique isomorphism. However we have to be careful what that means: it’s only going to be unique in the somewhere category, not in C.
Proposition 18.2 The function k defined above is the unique morphism making the diagram defining the universal property commute. Proof Consider any morphism k making the diagram commute. By definition of p and q, we know k(a) = pk(a), qk(a) . • We know that the left-hand triangle commutes so pk(a) = f(a). • Similarly from the right-hand triangle we get qk(a) = g(a). • Thus k(a) = f(a), g(a) .
18.5 Uniqueness of products in Set
We previously saw that any object isomorphic to an initial object is also initial (and likewise for terminal objects). We have also seen that uniqueness of products is more subtle: the unique isomorphism between products is only unique such that the diagram involving the projections commutes.
18.6 Products inside posets
Finally I’ll stress that there may be many isomorphisms C ∼ A × B as sets (as we saw with the small example producing 6! isomorphisms), but only one isomorphism as products. This means that once C has been equipped with the structure of a product, there is only one isomorphism with C ∼ A × B respecting that structure, that is, commuting with the projections.
a category has enough structure that we can take products of any two objects in the category, then we say that the category has binary products.
18.7 The category of posets
If we now work through the definition of product in this context, we see that for the product of a and b we need:
- A diagram of the form shown here, which in this category
just means that v is a multiple of both a and b. a b v
- Given any such diagram with vertex x, we need a morphism x v. Here is
a “translation” of what that means in this particular category.
I hope you agree that there’s something more satisfying about the second diagram. That’s a rather subjective point though; a non-subjective point is that the second one is symmetrical in the x and y values, where the first one isn’t.
Proof First we show that the projections are order-preserving
There are some trivial cases in which a product of tosets will be a toset (if either of the original tosets is empty or has only one element) but in general it will not be a toset.
18.8 Monoids and groups
What do the projection maps do in this case? In this case the first projection ignores a person’s gender and the second projection ignores a person’s race.
We call this doing addition “pointwise” or “componentwise” as we do it on each component separately, just like when we did posets we defined the ordering on the product componentwise. When we do anything pointwise, typically axioms all follow as they hold in each component individually. That is the case here. In particular the identity is (0, 0), and the inverse of (x, y) is (−x, −y).
18.10 Dually: coproducts
18.9 Some key morphisms induced by products
Note that the factorization k now goes from the universal vertex v to the vertex x that is not universal, where for products it was the other way round. The key here is not to think of that direction exactly, but to think of the fact that we are “factorizing” the non-universal diagram: expressing it as a composite of the universal one and k.
18.11 Coproducts in Set
We can picture the disjoint union as just sticking the sets side by side,
18.12 Decategorification: relationship with arithmetic
Here’s a picture encapsulating the idea of the coprojections. Note that technically we shouldn’t say “A B is a coproduct” without saying what the coprojections are, but we often do when the coprojections can be understood to be the “obvious” inclusions.
I often say that numbers are an abstraction because we make them by forgetting a lot of details about objects in the real world. However another point of view is that they’re a “de-categorification”,† regarding isomorphic sets as strictly the same. For example there are infinitely many one-element sets, and they’re all isomorphic in the category Set.
18.13 Coproducts in other categories
Inside a poset In the poset of factors of n we saw that products are lowest common multiples. Coproducts are then highest common factors.
So if we restrict to the category of commutative monoids everything in a coproduct can indeed be expressed as “element of A ◦ element of B”. You might notice that this is oddly similar to the elements of the product A × B apart from in notation, as the elements of the product are element of A, element of B . This is the same information, just with a different symbol in between the elements.
18.14 Further topics
Topological spaces The product of topological spaces follows the same principles as above but is somewhat more technically difficult, and we haven’t actually done the technical definition of topological space in the first place. However the idea is the same: we take the cartesian product A × B of underlying sets, and then try and put a topology on it in a canonical way.
Do we have something like unique factorization into primes? If so what are the “primes”? The last one is quite well studied for groups and is particularly straightforward for Abelian groups, where there is a “fundamental theorem of Abelian groups” rather like the fundamental theorem of arithmetic (which says that every natural number can be uniquely expressed as a product of primes).
universal properties are all universal cones over some starting data.
partners, or pairing pants/trousers with shirts that are the same color: we do that using a pullback.
Definition 19.1 A limit over a diagram is a universal cone over it. A pullback in a category is a limit over a diagram of the shape shown on the right.
To indicate a pullback we often put a little corner sign at the top left, as shown here. It goes where the vertex of the universal cone is.
Proof Consider a commuting diagram of sets and functions as in the outside of this diagram. We need to show there is a unique factorization as shown.
The diagram on the right is officially my favorite square, for reasons we’re about to investigate. Here every arrow is the subset inclusion function.
We can now immediately deduce that pullbacks are unique up to unique isomorphism, where the isomorphism in question is unique making the whole diagram commute as in the diagram for a factorization.
We take the pullback shown on the right; it’s a pullback in Set so can be defined as follows: C1 ×C0 C1 = (f, g) ∈ C1 × C1 t(f) = s(g)
19.5 Dually: pushouts
Definition 19.4 A pushout is a universal cocone for a diagram of the shape shown in the first diagram below. That is, it is a vertex v and morphisms as shown in the second diagram, such that given any diagram as in the third diagram, there is a unique factorization as shown in the fourth diagram.
19.6 Pushouts in Set
We indicate a pushout using the notation shown: a small corner marking the vertex of the universal cocone.
One thing we can do with the pullback notation is stress that something that is not a priori ‡ the intersection is in fact isomorphic to the intersection.
We now see that, as a consequence, 1 and 2 also end up being identified with each other. So the resulting set has only two elements: 1=x=2, and y. This process is called quotienting out by an equivalence relation. Technically, however, the relation we’re starting with isn’t necessarily an equivalence relation, so actually we first have to use it to generate an equivalence relation, and then we quotient out by it.
This relation is definitely not reflexive, as nothing is related to itself; however, it’s easy to add that condition into a relation. We can also straightforwardly define it to be symmetric. Transitivity is more interesting: we have 1∼ x and x∼2 , but we don’t know in advance that 1∼2, so transitivity fails.
Proposition 19.5 The diagram on the right has a pushout given by A B ∼ where the relation ∼ is generated by: s(c) ∼ t(c) ∀c ∈ C
19.7 Pushouts in topology
Pushouts in spaces are a key way of glueing spaces together to make more complex spaces. The idea is that when we (physically) glue things together we choose an area on each thing where the glue will go, and then those areas get identified.
The above example of making a longer strip was not that interesting but here is a pushout that sticks two intervals together to make a circle.
Pushouts of groups
More general universal properties
20.1 Making up the definition
We now change direction a little and address the concept of morphisms between categories. It is the “sensible” definition, using the principle of preserving structure.
Definition 20.1 Let C and D be (small) categories. A functor F : C D is given by • a function F : obC obD, and • for all objects x, y ∈ C, a function F : C(x, y) D(Fx, Fy) satisfying the following conditions called functoriality: • on identities: for all objects x ∈ C, F(1x) = 1Fx and • on composites: for all morphisms x f y g z ∈ C, F(g ◦ f) = Fg ◦ Ff.
There are two entries for the bottom right corner because a priori we don’t know if they’re the same. One comes from going around the top-and-right edges of the square, and the other comes from going around the left-and-bottom. I would say the answer is that they are not in general the same.
20.2 Functors between small examples
Posets as categories
monoid homomorphisms precisely the functors between those categories? The answer is yes.
There is nothing left to specify or check as we know that identities must go to identities, and there are no non-trivial composable morphisms anyway. Note that Fa and Fb could be the same set, and Ff could itself be the identity: identities must be mapped to identities, but non-identities are allowed to be mapped to identities.
Allowing degenerate ones gives us important flexibility and generality in the formalism.
Another “quintessential” category we could look at is a quintessential isomorphism. In order to use such a category to pick out an isomorphism in another category, we need to know that if we apply a functor to an isomorphism it will still be an isomorphism in the target category.
20.4 Free and forgetful functors
For example when we were looking at products of posets we took products of their underlying sets and then constructed a “natural” ordering on that set. Without saying so, we were invoking a functor Poset Set , which takes each poset and “forgets” that it’s a poset.
However, one very powerful aspect of them is the relationship they often have with a functor going the other way which does the “opposite” of forgetting structure: it creates structure freely and is called a free functor. By contrast, sometimes forgetful functors do not have a relationship with such a functor, and that is in itself interesting.
For codes like this it’s important that the function on letters is an isomorphism otherwise it won’t be decodable, but for our free monoids it needn’t be an isomorphism; for example, if we used the function A {∗} then every word in the elements of A would just become a string of ∗’s, like when you type in a password but it stays hidden on the screen. We can check that all this makes F into a functor Set Mnd. It is called the free monoid functor.
20.5 Preserving and reflecting structure
This good interaction can happen both forwards and backwards, and this is the idea of “preserving” and “reflecting” structure.
As the target category has only one object and only one morphism, we have no choice about where F can send everything: every object has to go to the single object and every morphism goes to the identity. Functoriality has to hold because the only morphism in the target category is the identity, so every equation of morphisms just reduces to an identity equalling itself.
The point is that the inclusion N Z as a map of monoids is epic, but its image under U (that is, where it’s mapped to in Set) is not epic. Abstractly this is saying that U does not preserve epics.
In Set any one-element set is terminal, and the empty set is initial. We can compare this with various categories of sets-with-structure. • In the category Pst of posets and order-preserving maps, any one-element poset is terminal and the empty poset is initial. So the forgetful functor Pst Set preserves terminal and initial objects. • In the category Grp of groups and homomorphisms, the trivial group has one element (the identity) and is both terminal and initial. So the forgetful functor Grp Set preserves terminal objects but not initial objects, because if we apply it to the initial object in Grp we do not get the initial object in Set. • In the categoryTop of topological spaces and continuous maps any one-point space is terminal and the empty space is initial. So the forgetful functor Top Set preserves terminal and initial objects.
20.6 Further topics
The elements of the fundamental group are the homotopy classes of loops. This means, essentially, that we count loops as the same if they’re not really different, but you can continuously deform one into the other without breaking it or going over a hole in the space.
you do them in because one way round can be deformed into the other. So the group we get is the product Z × Z.
contravariant functor, and the idea is that it reverses the direction of morphisms. The standard action on morphisms and the contravariant action are shown on the right.
21.1 The category Cat
Categories of categories
The next level up is locally small categories. We said a category is called locally small if the morphisms between any two objects form a set; however the objects might form a (large) collection. For example, in the category Set the objects are all the possible sets, so these cannot form a set (to avoid Russell’s paradox). However, given any sets A and B there is a set of functions A B. So Set is locally small. We can then make a category CAT of locally small categories and all functors between them.
There are various forgetful functors from Cat to Set including functors that:
- send a small category to its set of objects,
- send a small category to its set of morphisms, or
- send a small category to its set of connected components.
Graphs and their morphisms then form a category Gph, and we have a sensible forgetful functor Cat Gph. What
21.2 Terminal and initial categories
At the top we have a category of “data equipped with a particular kind of structure”, together with structure-preserving maps. In good situations the free and forgetful functors are in a special relationship called an adjunction, which can be expressed via universal properties in various ways that are beyond our scope here. The composite UF is then a functor from the category of underlying data to itself, and has many excellent properties. It is a prototype example of what is called a monad. Monads are then an abstract way to study “sets with structure”, and more generally the category of data at the bottom could be something other than Set, in which case monads give us a very general way to study algebraic structure. In fact, at an abstract level this is a definition of algebra: something that can be studied via monads.
21.3 Products and coproducts of categories
of C must go to the single object of , and all morphisms must go to the identity. Functoriality holds because everything is the identity, so all the required equations become “1 = 1”.
But anyway here’s the formula: (f2, g2) ◦ (f1, g1) = (f2 ◦ f1, g2 ◦ g1). Identities are also “componentwise”, which means 1(c,d) = (1c, 1d).
Products of posets in the category Pst correspond to products of posets expressed as categories, in Cat. • Products of monoids in the category Mnd correspond to products of monoids expressed as categories, in Cat.
21.4 Isomorphisms of categories
that weren’t already composable. Whereas in the coproduct of two monoids all the elements can be combined using the binary product; essentially it’s like taking the coproduct of one-object categories and then forcing the two single objects to be the same, making everything composable.
For example the categories of factors shown on the right are isomorphic.
This shows that saying that two categories “are isomorphic” is different from actually specifying an isomorphism between them. In the first case we are just saying that it is possible to match the structures up, and in the second case we are specifying a particular way of matching them up. That difference, as a general idea, becomes more and more important in higher dimensions.
In the first case we have these three “single arrow” categories.
One thing that we can and should call into question is whether this is the “right” notion of sameness for categories. We have seen that isomorphism is the “right” notion of sameness for objects inside a category, and that we therefore try not to invoke equalities between objects inside a category, rather than isomorphisms. However, now we are thinking about sameness for categories themselves. It turns out that in the definition of an isomorphism of categories we have invoked equalities between objects inside those categories, showing that the definition is “too strict”
21.5 Full and faithful functors
If we are dealing with a functor that is not strictly a bijection on objects we need to be careful what “bijection on morphisms” means.
However it is not a bijection on morphisms as four morphisms are sent to the same place, so it is not injective on morphisms.
If for all x, y the function C(a, b) D(Fa, Fb) is a bijection then we say F is full and faithful.
Proposition 21.4 Let F : C D be a full and faithful functor and a f b be a morphism in C. Then f is an isomorphism iff Ff is an isomorphism.
Earlier on we said that if we express posets as categories then the functors between them are precisely the order-preserving functions. Likewise if we express monoids as one-object categories then the functors between them are precisely the monoid homomorphisms. What is this saying about the “inclusion” functors Pst K Cat and Mnd Σ Cat?
Proposition 21.7 Suppose F : C D is full and faithful. Then F is “essentially injective on objects” as in the above definition.
22.1 Definition by abstract feeling
We’re going to develop a definition of “sensible relationships between functors”, called natural transformations.
Note that where previously we were just talking about whether or not two functions were equal, we are now looking at a system of morphisms in B. So we are looking at “senses in which” F and G are related.
22.2 Aside on homotopies
We think of natural transformations as 2-dimensional, like a “surface” connecting the “paths” made by the functors in the diagram.
22.3 Shape
We say that F and G have to be parallel, which means they have the same endpoints. The shape of α is then called globular.
22.4 Functor categories
We have assembled categories into a category using functors as the morphisms, but we can now assemble functors themselves into a category, using natural transformations as the morphisms between functors.
22.5 Diagrams and cones over diagrams
Thus the naturality of β ◦ α follows from the naturality of α and β individually.
a diagram of shape I in a category C is a functor D: I C. You can imagine I to be a quintessential commuting square category, or a parallel pair of arrows, if you want to visualize something. The functor D then picks out a specific diagram of that shape in the category C.
22.6 Natural isomorphisms
In general, naturality corresponds to the commutativity of every triangle necessary in a cone over a diagram D, with each naturality square collapsing to one triangle. This way of expressing general cones is the basis of the general definition of “limit over a diagram of shape I”.
So each βx is an inverse for αx, giving componentwise inverses as claimed.
24.1 Why higher dimensions?
This is a way in which abstract principles nudge us into higher dimensions just by us using our imagination. A way in which something more like practice nudges us that way is if we think about totalities of structures. We have seen that sets are 0-dimensional structures, as they just consist of points; but sets and functions together make a category, which is 1-dimensional.
mension higher, and they arise from the existence of morphisms in categories. So the extra dimension inside categories produced an extra dimension in the totality of categories.
24.2 Defining 2-categories directly
For the definition of a 2-category we basically take the structure of categories, functors and natural transformations and encapsulate it as data, structure and properties.
24.3 Revisiting homsets
Associativity: composition of 1-cells, and both horizontal and vertical composition of 2-cells are associative.
Structure • Identities: for any object a, a function as shown,† picking out an identity morphism a 1a a.
referred to a set of morphisms we now have an object of V instead, and everywhere we have a function between homsets we now have a morphism in V.
24.4 From underlying graphs to underlying 2-graphs
Properties The axioms for units and associativity are now the same commutative diagrams we drew for the categorical definition of a category, they just happen to live in Cat now rather than Set.
called a (2-dimensional) globular set or 2-globular set† and generalizes into n dimensions. Our original graphs are 1-globular sets.
A (small) 2-category is a 2-globular set in which • every sub-1-globular set has the structure of a category, and • interchange holds.
We could develop “2-category theory”: take everything we’ve done in one dimension and try to do it in two, by replacing equalities with isomorphisms and working out what axioms those isomorphisms should satisfy one dimension up.
24.5 Monoidal categories
We see that the more dimensions that a cell has above it, the more subtle a notion of sameness we can get. The number of dimensions that a cell has above it is called its codimension.
Now if our 2-category has only one 0-cell, say ∗, then there is just one hom-category C(∗, ∗) and a single composition functor:
24.6 Strictness vs weakness
while it can come from categorical products (with some caveats about weakness which we’ll come to) it need not.
For the unit laws the same thought process leads us to realize that we don’t want the identity to act as a strict identity but as a weak one. As a result we tend not to write it as 1 any more, but perhaps I. The unit isomorphisms look like this: a ⊗ I ra a and I ⊗ a la a. The letters r and l stand for “right” and “left” as they’re dealing with a unit on the right or a unit on the left.
However, we do have structure isomorphisms mediating between the ends, so we can ask instead for this diagram to commute.
24.7 Coherence
We get this triangle, which is called the unit triangle, and is the other axiom for a weak monoidal category.
categories by saying “all diagrams commute” and then prove a coherence theorem saying that it suffices to know that the pentagon and triangle commute.
24.8 Degeneracy
A degenerate category is one where the lowest dimension is trivial, that is, there is only one object. Once we’re in a 2-category there is one further level of degeneracy we could consider. We have seen that a 2-category with just one 0-cell “is” a monoidal category, but what about a 2-category with just one 0-cell and also one 1-cell? This is called “doubly degenerate”
The “clock” depicts an argument showing this amazing result: horizontal and vertical composition must be the same binary operation, and moreover, it is commutative. The clock is not a formal proof, but it’s the beginning of one: the idea is that every time you move to the next “hour” on the clock face you are performing a coherence isomorphism.
This isomorphism γ is called a braiding, because it is quite a lot like braiding hair. This idea starts from the idea that commutativity can be shown using physical objects by moving them around each other physically.
24.9 n and infinity
Studying degenerate higher-dimensional categories is like studying the footprints left in the snow by some mysterious higher-dimensional creatures, and helps us to understand how much more subtle they are than 2-categories.
There have been many approaches to defining n-categories, and describing any of them here is far beyond our scope. However, I would like to describe some of the different ideologies behind the approaches. Here are the general features that a definition needs to have.
enrichment to produce bicategories at the first step, but iterating that will not produce something as weak as tricategories at the next stage (although it will be slightly weaker than a strict 3-category).
The underlying graph as shown on the right is now a diagram in Cat, that is, a diagram of categories and functors.
Algebraic vs non-algebraic
We know that 2 × 4 × 3 definitely equals 24 in the natural numbers. However, there are situations in which answers are less definite. For example, suppose that instead of doing multiplication of natural numbers we are doing products of sets. We know that a product of three sets exists but there are many possible candidates for it. So instead of having one definite answer we have many possible answers, and they are all uniquely isomorphic
Whenever we cut off at n dimensions, we are essentially saying that every morphism at a dimension above n is the identity. Instead, we could say that every morphism above dimension n is an isomorphism, or rather, an equivalence at the appropriate level.
24.10 The moral of the story
you never have to worry about specifying axioms at the top dimension to seal up the ends, because there is no top dimension.
The process of doing category theory
So much for the motivations behind category theory. Here is what a typical process of doing category theory might look like, in steps.
- We see an interesting structure somewhere.
- We express it categorically, that is, using only objects and morphisms in
some relevant category.
- We look for that structure in other categories.
- We use it to prove things that will immediately be true in many different
categories.
- We investigate how it transports between categories via functors.
- We explore how to generalize it, perhaps by relaxing some conditions.
- We investigate what universal properties it has.
- We ask whether it has generalizations to higher dimensions via categorification.
The practice of category theory
Reasoning We use diagrammatic reasoning to make use of geometric intuition as well as logical and algebraic intuition. Proofs are often essentially type-checking. We invoke the “obvious axioms” which might seem obscure but once you understand the principle it’s less obscure: the principle is that if we have two inherently structural ways of mediating between the same things, they should be the same in order to prevent structural incoherence.
Structural awareness We maintain an awareness of our interaction with structure and how we’re using it. For example if we are making use of associativity we make sure we’re aware of it rather than taking it for granted.