Conceptual Mathematics - A First Introduction to Categories

Part 1 - The Category of Sets

Session 1 - Galileo and Multiplication of Objects

Galileo and the Motion of a Bird

We begin by understanding the concept of a mathematical mapping - these are functions from a domain to a codomain. We start by seeing some examples of mappings in the concept of physical motion, and describe the motion of a bird in 3 dimensions via various mappings. First we see a mapping from time to a point in space - $TIME SPACE $. Intuitively, this map states that at \(t_n\) the bird is at \((x_n, y_n, z_n)\). Next, we look at other mappings who’s domain is 3-dimensional space. We look at two such mappings - a mapping of space onto a 2-dimensional plane (\(\text{shadow}(x, y, z) = (x, y)\) which is the map \(SPACE \to PLANE\)), and a mapping from 3-dimensional space to elevation (\(\text{level}(x, y, z) = z\), which is \(SPACE \to LEVEL\)).

The significance of the latter two of these two maps is that they can be combined with the mapping from \(TIME \to SPACE\). We can compose the map from \(TIME \to SPACE\) with \(SPACE \to PLANE\), and we have a map from \(TIME \to PLANE\). Likewise we can compose a map from \(TIME \to SPACE\) with \(SPACE \to LEVEL\), and we are left with a map from \(TIME \to LEVEL\). Thus we can describe the motion of a bird y the simpler mappings \(TIME \to PLANE\) and \(TIME \to LEVEL\).

We finish the discussion of the motion of a bird by considering the equation \(\text{SPACE} = \text{PLANE} \times \text{LINE}\), and are to consider if we feel this now makes sense. To deepen our understanding of this equation, we consider what multiplication of objects (in general) could mean.

Multiplication of Objects

Multiplication often appears in the guise of independent choices, and we consider such an example - choosing what to eat for a two course meal. We have independent choices for the first course and the second course. Interestingly, Lawvere and Schanuel show that there are maps from the set of all meals, to first courses and second course:

Meals

Soup, Steak

Pasta, Steak

Salad, Steak

\(\rightarrow\)

Steak

Soup, Veal

Pasta, Veal

Salad, Veal

\(\rightarrow\)

Veal

Soup, Chicken

Pasta, Chicken

Salad, Chicken

\(\rightarrow\)

Chicken

Soup, Fish

Pasta, Fish

Salad, Fish

\(\rightarrow\)

Fish

\(\downarrow\)

\(\downarrow\)

\(\downarrow\)

Soup

Pasta

Salad

We have possible 2nd courses on the right, and possible first courses on the bottom. Thus we have mapping from \(MEALS \to 2^{nd} courses\) and \(MEALS \to 1^{st} courses\), and we notice the similarity to the mappings in the motion of a bird (\(SPACE \to PLANE\) and \(SPACE \to LINE\)). It the becomes clear that \(\text{MEALS} = \text{1st courses} \times \text{2nd courses}\), so it would follow that \(\text{SPACE} = \text{PLANE} \times \text{LINE}\).

Exercises

Find other examples of combining two objects to get a third - which of them seem to fit our pattern?

Given a set of drinks that can purchased at a cafe and a set of books that I like to read at cafes, we have two mappings: \(CAFE \to BOOKS\) and \(CAFE \to DRINKS\). We can then multiply these to determine all the ways I might relax at a cafe: \(\text{FREE TIME} = \text{DRINK} \times \text{BOOK}\). This fits the pattern we’ve seen above as the choice of what I read and what I drink is a (mostly) independent choice.

Another pairing of independent choices could describe my journey to work. A journey to work has two maps: \(JOURNEY \to WEATHER\) and \(JOURNEY \to TRANSPORT\). Thus we can see that all the possibilities of how I get to work can be expressed as \(\text{JOURNEY} = \text{WEATHER} \times \text{TRANSPORT}\)

In Galileo’s work considering a small area of space, what does it mean for two points to be at the same level. How would you experimentally test for this?

The simplest way would be to take line from the first point to the second point - if this line is parallel to the plane given by \(\text{PLANE}\) then the points are at equal height.

Article 1 - Sets, Maps, Composition

Before even defining what a category is, we start with a motivating example - the category of finite sets and maps. In this category, objects will be finite sets, and maps consist of three parts: the domain, the codomain and a rule associating each element in the domain with an element in the codomain. We see various notations for sets, including curly braces, internal diagrams with and without set element labels and finally external diagrams where the elements themselves are not important.

As a first example of a map in this category, we look at a map between people and choices of breakfast. The map associates for each person a single item of breakfast that is their favourite. Importantly, we note that this map considers all elements in the domain and associates them with a single element in the codomain. Elements in the codomain do not necessarily have any arrows arriving at them. As a small digression, we note that the domain and codomain can be the same set. This map is known as an endomap, presumably as the prefix endo is greek for “within” (“from endon within”). There is a special endomap available for all sets, and that is the identity mapping. This mapping associates each element with itself. Technically, we should refer to this as the identity map on A.

Now that we are familiar with maps between sets, we move on to consider the composition of maps between sets. This is mostly a case of “following the arrows” from the domain of the first map to its codomain, and then to the codomain of the second map. Crucially, this suggests that the codomain of the first map must be the same as the domain of the second map.

We are now ready to understand all the elements of a category:

A category has:

Objects
\(A\), \(B\), \(C\), …
Maps
\(A \overset{f}{\rightarrow} B\)
Identity maps (for each object):
\(A \overset{1_A}{\rightarrow} A\)
Composition of maps (for all maps):
Given \(A \overset{f}{\rightarrow} B \overset{g}{\rightarrow} C\) we have \(A \overset{f \circ g}{\rightarrow} C\)
Subject to the laws
  1. The identity laws: \(1_A\) should be a left and right identity for composition from \(A\).
  2. Composition of maps is associative.

Exercise 1

Check to be sure you understand how we got diagrams (ii) and (ii) from (i), then fill in (iv) and (v) yourself. Check the results are the same.

Singleton Sets

With the basic notion of a category out of the way, we return to looking at sets and mappings. We turn our attention to singleton sets - sets one of element. We usually refer to this set as 1.

A point of a set \(X\) is a map \(1 \to X\).

Note that a point is a map, not an element! This means that points can be composed over many maps.

Exercise 2

In these examples, \(A = \{ \text{John}, \text{Mary}, \text{Sam} \}\) and \(B = \{ \text{eggs}, \text{coffee} \}\).

How many maps \(f\) are there with a domain \(A\) and codomain \(B\)?

For each of the three objects in the domain there are two possible choices in the codomain. As a map has to consider all objects in the domain there are \(2 \cdot 2 \cdot 2 = 2^3 = 8\) maps.

How many maps for \(A \overset{f}{\rightarrow} A\)?

Now there are three choices for the codomain and three objects in the domain, so we have \(3 \cdot 3 \cdot 3 = 3 ^ 3 = 27\) maps.

How many maps for \(B \overset{f}{\rightarrow} A\)?

These maps have two elements in the domain and three choices in the codomain, so we have \(3 \cdot 3 = 3 ^ 2 = 9\) maps.

How many maps for \(B \overset{f}{\rightarrow} B\)?

\(B\) has only two elements, so for each element it can map to one of two elements. There for there are \(2 \cdot 2 = 2 ^ 2 = 4\) maps.

How many maps \(A \overset{f}{\rightarrow} A\) satisfy \(f \circ f = f\)?

Initially, one would assume that only the identity map has such a property - but this is far from the truth. In fact, there are many maps with this property - the family of constant maps to a single element for example, also have this property. We can systematically find all maps with this property. First we choose an element from the domain and map it to any element. If we map to ourselves, then we can continue the process with another element from the domain. This can again map to any element. However, whenever we map an element to a different element, then nothing can map to this domain element. Thus there are \(3 + 2 + 1 = 6\) possible mappings with this property.

How many maps \(B \overset{g}{\rightarrow} B\) satisfy \(g \circ g = g\)?A

The identity map, and the two possible constant maps, giving a total of \(3\) maps.

Can you find a pair of maps \(A \overset{f}{\rightarrow} B \overset{g}{\rightarrow} A\) for which \(g \circ f = 1_A\)? If so, how many such pairs?

There are no such mappings as \(A\) and \(B\) have differing amounts of elements. Specifically, the mapping \(g\) will have to associate two elements of \(A\) to a single element of \(B\), so there is no way to construct \(1_A\).

Can you find a pair of maps \(B \overset{h}{\rightarrow} A \overset{k}{\rightarrow} B\) for which \(k \circ h = 1_B\)? If so, how many such pairs?

Such mappings do exist, providing \(h\) maps to distinct elements of \(A\). There are 6 possibilities for \(h\), so there are at least 6 possible pairs. For \(k\) however, we are free to map the remaining element of \(A\) to any element in \(B\) - the effect of such a mapping is irrelevant to the composition. As the last element of \(A\) can map to one of two elements in \(B\) there are 12 possible “return” mappings, leading to 12 possible pairs of mappings with the desired property.

Session 2 - Sets, Maps and Composition

We begin by recapping the concept of a mapping from the previous chapters, and start to consider what happens when two different rules give the same map. We consider \(f(x) = (x + 1)^2\) and \(g(x) = x^2 + 2x + 1\) (the expansion of the rule of \(f\)), noting that these mappings result in the same internal diagrams. As these mappings are the same, we can say that \(f = g\), which expresses the equation \((x + 1)^2 = x^2 + 2x + 1\) and not that the functions have identical rules.

The idea is that a function is not the rule itself, but what the rule accomplishes.

Generalizing from the category of sets, we add the requirement that mappings between objects in a category may be equal if:

  1. They have the same domain
  2. They have the same codomain

These are not sufficient conditions for equality however, and we clarify the notion of equality by considering all possible points of a set. We note that:

If for each point \(1 \overset{a}{\rightarrow} A\), \(f \circ a = g \circ a\), then \(f = g\).

This clearly captures the notion that as long as every element in the domain maps to the same element in the codomain for both \(f\) and \(g\), then we can consider the mappings equal.

We emphasize that the composition of mappings is not just the composite of two (or more maps), but may be an entirely different rule, as extra detail can be discarded if nothing in the composite domain reaches elements involved in later maps. We also see how a complex mapping can be viewed as the composition of many smaller mappings, as in the example of mapping from a temperature in Fahrenheit to Celsius.

We finish this section by reviewing some problems of counting the amount of maps between sets, and encounter our first maps to and from empty sets. We see that mapping from the empty set has precisely one map, but mapping to the empty set has zero possible maps.

Session 3 - Composing Maps and Counting Maps

To begin this section, we review what it means to compose multiple maps together, and convince ourselves that composition is an associative operation - as long as you compose in the same order, the result is always the same. Comfortable with this knowledge, we review some of the exercises in article 1. Answers to the first four exercises match my solutions above, and we start to look at why this is the case. We introduce some notation for the set of all maps from \(A \to B\), we use \(B^A\). We note that \(\left|B^A\right| = \left|B\right|^\left|A\right|\), as we saw earlier.

Now that we’ve seen how to count all possible maps, we look at counting maps with specific properties. The session confirms that the identity maps certainly have this property, along with the constant maps, but don’t have much more discussion beyond that.

Exercises

\(A\), \(B\) and \(C\) are three different sets (or even three different objects in a category); \(f\), \(g\), \(h\) and \(k\) are maps with domains and codomains: \(A \overset{f}{\rightarrow} B\), \(B \overset{g}{\rightarrow} A\), \(A \overset{h}{\rightarrow} C\) and \(C \overset{k}{\rightarrow} B\). Which compositions are valid (of those in the book), and what are their domains and codomains?
  1. This composition is valid, and has domain \(A\) and codomain \(B\).
  2. This composition is not valid as \(f \circ g\) has codomain \(B\), but \(k\) has domain \(C\).
  3. This composition is valid, and has domain \(A\) and codomain \(A\).

Part 2 - The Algebra of Composition

Article 2 - Isomorphisms

Isomorphisms

Our motivation for this article is to answer the question: what is it that makes sets “resemble” one another. If we don’t have the ability to count a set, one way to notice that two sets are the same shape is to have a map from one set to the other, such that we can invert this map. In this way, there is a map to and from both sets. This means our two maps will be related by two properties:

  1. \(g \circ f = 1_A\)
  2. \(f \circ g = 1_B\)

(Here \(A \overset{f}{\rightarrow} B\) and \(B \overset{g}{\rightarrow} A\)).

This leads us to the notion of an isomorphism:

Isomorphism
A map \(A \overset{f}{\rightarrow} B\) is called an isomorphism or invertible map if there is a map \(B \overset{g}{\rightarrow} A\) for which \(g \circ f = 1_A\) and \(f \circ g = 1_B\).
A map \(g\) related to \(f\) by satisfying these equations is called an inverse for \(f\).
Two objects \(A\) and \(B\) are said to be isomorphic if there is at least one isomorphism \(A \overset{f}{\rightarrow} B\).

Isomorphisms are subject to the following properties, which are direct consequences of the associativity and identity laws of categories:

Reflexivity
\(A\) is isomorphic to \(A\). Symmetric
If \(A\) is isomorphic to \(B\) then \(B\) is isomorphic to \(A\). Transitive
If \(A\) is isomorphic to \(B\) and \(B\) is isomorphic to \(C\), then \(A\) is isomorphic to \(C\).

Exercise 1

Show that \(A \overset{1_A}{\rightarrow} A\) is an isomorphism.
As \(1_A \circ f = f\), then when \(f = 1_A\) we have \(1_A \circ 1_A = 1_A\). Hence the inverse of \(1_A\) is itself \(1_A\), and so as \(1_A\) has an inverse it is an isomorphism.
Show that if \(A \overset{f}{\rightarrow} B\) is an isomorphism, and \(B \overset{g}{\rightarrow} A\) is an inverse for \(F\), then \(g\) is also an isomorphism.
We have \(g \circ f = 1_A\) and \(f \circ g = 1_B\), so the inverse of \(g\) is \(f\). Therefore \(g\) is an isomorphism.
Show that if \(A \overset{f}{\rightarrow} B\) and \(B \overset{k}{\rightarrow} C\) are isomorphisms, then \(A \overset{k \circ f}{\rightarrow} C\) is also an isomorphism.
From \(f\) and \(k\) we have inverses \(g\) and \(h\), respectively. Thus \(g \circ h \circ (k \circ f) = 1_A\) and \((k \circ f) \circ g \circ h = 1_B\). Thus \(k \circ f\) has an inverse that satisfies the properties of an isomorphism, so \(k \circ f\) is an isomorphism.

With the theory of isomorphisms in our grasp, we look again for motivating examples to see why isomorphisms are so important. We briefly discuss the isomorphism between the Plane \(P\) and \(\mathbb{R}^2\) - the set of ordered pairs of real numbers. This isomorphism assigns to each point \(p\) in \(P\) a pair of coordinates in \(\mathbb{R}^2\), or takes these coordinates to a point in \(P\). This isomorphism is significant, as it lets us rephrase geometry problems in terms of algebraic problems, which can often be simpler to solve (though sometimes it’s easier to work in the opposite direction).

Exercise 2

Suppose \(B \overset{g}{\rightarrow} A\) and \(B \overset{k}{\rightarrow} A\) are both inverses for \(A \overset{f}{\rightarrow} B\). Show that \(g = k\).
We note that \(g = g \circ 1_B = g \circ (f \circ k) = (g \circ f) \circ k = 1_A \circ k = k\). Therefore \(g = k\). This proof is explained in more detail on the Proof Wiki entry for the theory Inverse Morphism is Unique.

The article is now set up to talk about “division” of objects, but before doing so we make it clear that composition is not a commutative operation. We note that the parallels between composition and multiplication of numbers starts to break down here, and also note that while a number has a multiplicative inverse, for mappings our inverses have to satisfy two equations.

If \(A \overset{f}{\rightarrow} B\) has an inverse, then the (unique) inverse for \(f\) is denoted by the symbol \(f^{-1}\). Remember that there are two important properties:

  1. To show that a map \(B \overset{g}{\rightarrow} A\) satisfies \(g = f^{-1}\), you must show that \(g \circ f = 1_A\) and \(g \circ g = 1_B\).
  2. If \(f\) does not have an inverse, then the symbol \(f^{-1}\) is meaningless.

Exercise 3 & 4

If \(f\) has an inverse, then \(f\) satisfies two of the following three possible cancellation laws. Prove those \(f\) satisfies:
  1. If \(f \circ h = f \circ k\), then \(h = k\).

    From the hypothesis, we know \(f^{-1} \circ (f \circ h) = f^{-1} \circ (f \circ k)\).

    Therefore, after associativity, \(1_A \circ h = 1_A \circ k\), and therefore \(h = k\). So this law is true.

  2. If \(h \circ f = k \circ f\), then \(h = k\).

    From the hypothesis, we know \((h \circ f) \circ f^{-1} = (k \circ f) \circ f^{-1}\).

    Therefore, after associativity, \(h \circ 1_B = k \circ 1_B\), and so \(h = k\). This law is also true.

  3. If \(h \circ f = f \circ k\), then \(h = k\).

    We find a counter-example that disproves this law. Take

    • \(A = \{x, y, z\}\),
    • \(f\) to be the constant map to \(x\)
    • \(h\) maps \(x\) to \(x\) and everything else \(z\)
    • \(k\) is the constant map to \(z\).

    Now \(h \circ f\) is the constant map to to \(x\), and \(f \circ k\) is also the constant map to \(x\). But \(h \ne k\), so this law is false in general.

For each of the 5 maps (page 44): decide whether it is invertible; and if it is invertible, find a ‘formula’ for the inverse map.
  1. This is invertible, with \(f^{-1}(x) = \frac{x - 7}{3}\).
  2. This is invertible, with \(g^{-1}(x) = +\sqrt{x}\).
  3. This map is not invertible (\((-2) ^ 2 = 4 = 2^2\), thus 4 does not have a unique inverse).
  4. This map is not invertible, for the same reason as 3.
  5. This map is invertible, with \(l^{-1}(x) = \frac{1}{x} - 1\)

General Division Problems: Determination and Choice

In this section, we will be looking at two closely related problems:

  1. Given \(A \overset{h}{\rightarrow} C\) and \(A \overset{f}{\rightarrow} B\), what are all \(g\) (if any) such that \(B \overset{g}{\rightarrow} C\) with \(h = g \circ f\)?

This problem will be known as the determination or extension problem. It is named such, as if there are any \(g\) that satisfy this property, then \(h\) is determined by \(f\) (\(g\) is a determination of \(h\) by \(f\)).

  1. Given \(A \overset{h}{\rightarrow} C\) and \(B \overset{g}{\rightarrow} C\), what are all \(f\) (if any) such that \(A \overset{f}{\rightarrow} B\) with \(h = g \circ f\)?

This problem will be known as the choice or lifting problem.

Firstly, we look at determination problems. We begin with a very simple set for \(B\) - a singleton set. If \(g\) exists here, then \(h\) must be a constant mapping. There is only one possible choice of the map \(f\), and any map \(g\) will choose a single element of \(C\). Therefore, we have:

\(h(x) = (g \circ f)(x) = g(f(x)) = g(b)\) for some \(b \in B\).

Such a map \(h\) is a constant.

Next, we look at specific class of choice problems. In this example, we have \(A = C\), and \(h = 1_A\). \(A\) is a 2-element set, and a map \(B \overset{g}{\rightarrow} A\) - where \(B\) is a 3-element superset of \(A\). We consider how many maps \(A \overset{f}{\rightarrow} B\) could exist, and deduce there are only two. We note that \(f\) must be a map with the property \(g(f(x)) = x\), and that \(f\) must choose an element \(z \in B\) such that \(g(z) = x\).

Exercise 5

Each map \(f\) must take \(0\) to \(x \in \{b, p, q\}\) and \(y \in \{r, s\}\). Thus there are \(2 ^ 3 = 8\) possible choices for \(f\).

Let \(f\) be defined as the map such that \(f(0) = b\) and \(f(1) = r\). Any map \(g\) that satisfies \(g \circ f = 1_{\{0, 1\}}\) has to map \(g(b) = 0\) and \(g(r) = 1\), but is free to map any of the 3 remaining elements to \(0\) or \(1\). Hence the are \(2^3 = 8\) possible choices for \(g\).

We next move on to look at some examples of choice and determination problems. A real life determination problem is given by Galileo and the distance fallen by an object. In this case, we see that the mapping from a falling object to the distance it falls is determined by the duration of the fall.

Retractions, Sections and Idempotents

The special cases we saw earlier where \(h\) is the identity map are known as retractions and sections:

Retraction
If \(A \overset{f}{\rightarrow} B\), then a retraction for \(f\) is a map \(B \overset{r}{\rightarrow} A\) such that \(r \circ f = 1_A\). Section
If \(A \overset{f}{\rightarrow} B\), then a section for \(f\) is a map \(B \overset{s}{\rightarrow} A\) such that \(f \circ s = 1_B\).

We now look at some properties of retractions and sections.

Proposition 1: If a map \(A \overset{f}{\rightarrow} B\) has a section, then for any \(T\) and for any map \(T \overset{y}{\rightarrow} B\) there exists a map \(T \overset{x}{\rightarrow} A\) for which \(f \circ x = y\).

We see that the presence of \(f\) having a section means there is a map \(B \overset{s}{\rightarrow} A\) such that \(f \circ s = 1_B\) (definition of a section). Thus we can certainly form a map \(T \overset{x}{\rightarrow} A\) by following the composite map \(s \circ y\). We then check that this composition satisfies the equation in the proposition:

\(f \circ x = f \circ (s \circ y) = (f \circ s) \circ y = 1_B \circ y = y\).

If the map \(A \overset{f}{\rightarrow} B\) has a retraction, then for any map \(A \overset{g}{\rightarrow} T\) there is a map \(B \overset{t}{\rightarrow} T\) for which \(t \circ f = g\).

If \(f\) has a retraction, there there exists a map \(B \overset{r}{\rightarrow} A\) such that \(r \circ f = 1_A\). Thus we can take the composite map \(t = g \circ r\). Checking the required equation, we have:

\(t \circ f = (g \circ r) \circ f = g \circ (r \circ f) = g \circ 1_A = g\).

Injective Maps/Monomorphisms

Proposition 2: If a map \(A \overset{f}{\rightarrow} B\) has a retraction, then for any set \(T\) and for any pair of maps \(T \overset{x_1}{\rightarrow} A\), \(T \overset{x_2}{\rightarrow} A\), we have the propostion: \(f \circ x_1 = f \circ x_2 \Rightarrow x_1 = x_2\).

To prove this, we begin at \(x_1\) and gradually expand the definition of \(x_1\) as \(x_1 = 1_A \circ x_1 = r \circ f \circ x_1\), where \(r\) is the retraction for \(f\). Now as \(f \circ x_1 = f \circ x_2\), we have \(x_1 = r \circ \f \circ x_2\), and as \(r \circ f = 1_A\) (definition of a retraction), we have \(x_1 = 1_A \circ x_2 = x_2\).

A map \(f\) satisfying the above proposition (\(f \circ x_1 = f \circ x_2 \Rightarrow x_1 = x_2\), for any \(x_1\) and \(x_2\)) is said to be injective for maps from \(T\). If \(f\) is injective for maps from \(T\) for every \(T\), we say that \(f\) is injective. \(f\) is also known as a monomorphism.

Epimorphisms

Suppose the map \(A \overset{f}{\rightarrow} B\) has a section. Then for any set \(T\) and any pair \(B \overset{t_1}{\rightarrow} T\), \(B \overset{t_2}{\rightarrow} T\) of maps, if \(t_1 \circ f = t_2 \circ f\), then \(t_1 = t_2\).

This proposition is dual to proposition 2 above, and can be proved in the same manner.

\(t_1 = t_1 \circ 1_B = t_1 \circ (f \circ s) = (t_1 \circ f) \circ s = (t_2 \circ f) \circ s = t_2 \circ (f \circ s) = t_2 \circ 1_B = t_2\).

Again, we use that fact that the identity map is the same as composing \(f\) with its \(section\), which lets us gradually show that \(t_1 = t_2\).

A map \(f\) with the cancellation property \(t_1 \circ f = t_2 \circ f \Rightarrow t_1 = t_2\) for every \(T\) is called an epimorphism.

If \(A \overset{f}{\rightarrow} B\) has a retraction and \(B \overset{g}{\rightarrow} C\) has a retraction, then \(A \overset{g \circ f}{\rightarrow} C\) has a retraction.

As \(f\) and \(g\) have retractions, we have \(B \overset{r_1}{\rightarrow} A\) and \(C \overset{r_2}{\rightarrow} B\). So as we can move from \(A\) to \(C\) via \(g \circ f\), we can move from \(C\) to \(A\) by following the retractions - \(r_1 \circ r_2\). We next show that this indeed a retraction for \(g \circ f\):

Let \(r = r_1 \circ r_2\). Then \(r \circ (g \circ f) = (r_1 \circ r_2) \circ (g \circ f) = r_1 \circ (r_2 \circ g) \circ f = r_1 \circ f = 1_A\), as required.

There is a dual theorem that we can state for maps with sections:

If \(A \overset{f}{\rightarrow} B\) has a section and \(B \overset{g}{\rightarrow} C\) has a section, then \(A \overset{g \circ f}{\rightarrow} C\) has a section.

As \(f\) and \(g\) have sections, we have \(B \overset{s_1}{\rightarrow} A\) and \(C \overset{s_2}{\rightarrow} B\), such that \(f \circ s_1 = 1_B\) and \(g \circ s_2 = 1_C\). Thus it would appear that the composite map \(g \circ f\) has a section, \(s = s_1 \circ s_2\), as we now verify.

Let \(s = s_1 \circ s_2\). Then \((g \circ f) \circ s = (g \circ f) \circ (s_1 \circ s_2) = g \circ (f \circ s_1) \circ s_2 = g \circ 1_B \circ s_2 = g \circ s_2 = 1_C\), as required.

Idempotent Maps

An endomap \(e\) with the property that \(e \circ e = e\) is idempotent.

If \(r\) is a retraction of \(f\), then \(e = f \circ r\) is idempotent.

\(e \circ e = (f \circ r) \circ (f \circ r) = f \circ (r \circ f) \circ r = f \circ r = e\). Thus \(e\) is idempotent.

Further more, if \(f\) is an isomorphism, then \(e\) is the identity map.

If \(f\) is an isomorphism, then \(r = f^{-1}\) (see exercise 2 for a proof that there is only one possible retraction). Therefore \(e = f \circ r = f \circ f^{-1} = 1\), as required.

Finally, we look at a theorem that ties retractions and sections together.

If \(f\) has both a retraction \(r\) and a section \(s\), then \(r = s\).

From the hypothesis, if we have \(A \overset{f}{\rightarrow} B\), then we have \(r \circ f = 1_A\) and \(f \circ s = 1_B\) (from the definition of retractions and sections).

Then, \(r = r \circ 1_B = r \circ (f \circ s) = (r \circ f) \circ s) = 1_A \circ s = s\).

Isomorphisms and Automorphisms

Now that we have seen how retractions and sections work, and the properties they possess, we are able to rephrase isomorphisms in terms of retractions and sections.

A map \(f\) is an isomorphism if there exists another map \(f^{-1}\) which is both a retraction and a section for \(f\).

If \(A \overset{f}{\rightarrow} B \overset{g}{\rightarrow} C\) are both isomorphisms, then \(g \circ f\) is an isomorphism too, and \((g \circ f)^{-1} = f^{-1} \circ g^{-1}\).

As \(f\) are \(g\) are isomorphisms, we have \(B \overset{f^{-1}}{\rightarrow} A\) and \(C \overset{g^{-1}}{\rightarrow} B\) that are both retractions for \(f\) and \(g\) respectively. These maps compose, as \(C \overset{f^{-1} \circ g^{-1}}{\rightarrow} A\), and

\((g \circ f) \circ (f^{-1} \circ g^{-1}) = g \circ (f \circ f^{-1}) \circ g^{-1} = g \circ 1_B \circ g^{-1} = 1_C\)

\((f^{-1} \circ g^{-1}) \circ (g \circ f) = f^{-1} \circ (g^{-1} \circ g) \circ f = f^{-1} \circ 1_B \circ f = 1_A\)

Thus \(f^{-1} \circ g^{-1}\) is both a section and a retraction for \(g \circ f\), so \(g \circ f\) is an isomorphism with inverse \(f^{-1} \circ g^{-1}\).

We now give an intuitive meaning to isomorphisms in the category of sets. If two objects are isomorphic (that is, there is an isomorphism between \(A\) and \(B\)), then these sets have the same amount of elements. Crucially, isomorphisms give us a way to discuss the idea of sets being “the same size” without depending on counting, which is important when we move to infinite sets. This idea extends to other categories, but as the object becomes richer the isomorphism begins to encode the idea of “same shape” or “same structure”.

Exercise 11

One isomorphism between \(A\) and \(B\) would be given as \(f(\text{Fatima}) = \text{coffee}\), \(f(\text{Omer}) = \text{tea}\) and \(f(\text{Alysia}) = \text{cocoa}\).

There is no isomorphism between \(A\) and \(C\) however, as maps from \(C\) cannot map to each element of \(A\). Thus an inverse of \(f\) cannot exist, and therefore there are no possible isomorphisms between \(A\) and \(C\).

As in Article I, we now begin to look at counting isomorphisms. We also look at counting a specific type of isomorphism - isomorphisms of the form \(A \overset{f}{\rightarrow} A\).

An isomorphism \(A \overset{f}{\rightarrow} A\) is called an automorphism.

Exercise 12

There are three possible choices to map from Fatima. There are then two remaining choices to map Omer to, and finally one choice to map Alysia to. Therefore we have \(3 \times 2 \times 1 = 6\) possible isomorphisms.

By the same reasoning, there are also 6 possible automorphisms.

There are less than 27 isomorphisms, as there are only 27 possible maps between these objects (\(3^3 = 27\)).

In general, if there are isomorphisms between objects \(A\) and \(B\), then there are the same amount of automorphisms of \(A\). The proof in the book shows that we can use the idea of “same size” via isomorphisms to answer this question. We take \(Aut(A)\) to be the set of automorphisms of \(A\) and \(Isom(A, B)\) to be the set of isomorphisms \(A \overset{f}{\rightarrow} B\) - if these sets are the same size then there exists an isomorphism between them.

To determine the isomorphism, we consider composite maps from \(A \overset{\alpha}{\rightarrow} A \overset{f}{\rightarrow} B\) and remember than all composites are in \(Isom(A, B)\), as the composite of isomorphisms is an isomorphism. We also consider the reverse case, using \(f^{-1}\) - the inverse of \(f\) - and observing that \(f^{-1} \circ f\) is contained in the set \(Aut(A)\). Finally, we show that these maps have the cancellation properties we desire of isomorphisms, and so \(Aut(A)\) is isomorphic to \(Isom(A, B)\).

Automorphisms in the category of sets are traditionally called permutations, so we now consider the category of permutations. Objects in this category are sets along with an automorphism of that set. where as maps are functions that preserves the given automorphisms.

Session 4 - Division of Maps: Isomorphisms

We begin this section by reviewing the analogy between the multiplication of numbers and the composition of maps. We note that multiplication has an identity (1), just as every object has an identity map. We ask the question: if composition is analogous to multiplication, what is analogous to division of numbers? The “division problem” is introduced - finding a solution to \(5 \times ? = 15\), for example.

Before looking for the category theory analogy to division, we look at reciprocals of numbers. A reciprocal number has the property that: \(? \times 2 = 1\). A map with this property of composition is an isomorphism - the map \(f\) has an inverse map \(g\) such that \(f \circ g = 1_B\) and \(g \circ f = 1_A\). We note that it is essential that an isomorphism satisfies both of these equations, and it is possible to have pairs of maps where only one is satisfied (but the maps will not be inverses).

The uniqueness of inverses theorem (proved correctly in Exercise 2) states that a map \(f\) has at most 1 inverse. A nice way to remember the proof is to suppose \(f\) has 2 inverses, \(g\) and \(h\), and to start “in the middle” with \(g \circ f \circ h\), and notice that this can be simplified to either \(g\) or \(h\).

We briefly discuss the notation of \(f^{-1}\), and note that this only maps sense if inverses actually exist - not every map has an inverse. Specifically, which maps have inverses depend on which category you are working in, but most of the upcoming work will only dependent on the category laws.

Isomorphisms are natural in our deductive process, as we see by looking at a variety of isomorphisms in the context of watching a film. We see how natural these isomorphisms feel, and that when we are making deductions we tend to freely compose isomorphisms as we need to.

To gain more appreciation for isomorphisms, we look for a few more examples. This time, rather than considering the category Set, we consider a category of algebras. Here, objects in the category are a set along with some operation - for example \((\mathbb{R}, +)\). Maps in this category are homomorphisms between these objects, e.g., \(f(a * b) = (fa) *' (fb)\). Some examples of isomorphisms in this category are:

  1. $(, +) (, +), where \(d\) is the “doubling” map. As doubling can be undone (via division by 2), this map is an isomorphism.
  2. $(, ) (, ), where \(c\) is the “cubing” map. Again, cubing can reversed by taking a cube root (which has a distinct answer, in \(\mathbb{R}\)), so \(c\) is an isomorphism.
  3. \((\mathbb{R}, +) \overset{exp}{\rightarrow} (\mathbb{R}_{>0}, \times)\), where exp is the map of exponentiation. exp is a homomorphism, as \(e^{a + b} = e^a \times e^b\).

These examples seem clear enough, but we still need to check that they are, in fact, isomorphisms.

Finish checking that \(d\) is an isomorphism in our category by showing that \(h \circ d\) and \(d \circ h\) are identity maps.

For \(h \circ d\), we have \(h(d(x)) = h(2x) = \frac{2x}{2} = x\), for all \(x \in \mathbb{R}\).

For \(d \circ h\), we have \(d(h(x)) = d(\frac{x}{2}) = 2\frac{x}{2} = x\).

So \(d\) is an isomorphism, with inverse \(h\).

We don’t have to limit ourselves to sets of numbers in this category, however. Another object in the category is \((\{ \text{odd}, \text{even} \}, +)\) - as \(\text{odd} + \text{even} = \text{odd}\), and so on. There is a similar object for \(\times\): \((\{ \text{negative}, \text{positive} \}, \times)\). As example (3) showed before, there is a similar isomorphism between these objects.

Find an isomorphism \((\{ \text{odd}, \text{even} \}, +) \overset{f}{\rightarrow} (\{ \text{negative}, \text{positive} \}, \times)\).

The map here takes \(\text{odd}\) to \(\text{negative}\) and \(\text{even}\) to \(\text{positive}\), such that:

\(f(\text{odd} + \text{odd}) = f(\text{odd}) \times f(\text{odd}) = \text{negative} \times \text{negative} = \text{positive} = f(\text{even})\).

A similar result is obtained for \(f(\text{even} + \text{even}) = \text{positive} = f(\text{even})\).

Which of the following (exercise 3, page 66) are not isomorphisms?
  1. This is not a map in our category. A counter example is \(f(1 + 2) = f(1) + f(2) = (1 + 1) + (2 + 1) = 2 + 3 = 5 \ne f(3) = 4\).
  2. This is not an isomorphism as \(\text{sq}\) is not injective (\(\text{sq}\) is not a monomorphism)
  3. This is not an isomorphism for the same reason as before (it is not injective from \(\mathbb{R}\)).
  4. This is a valid isomorphism.
  5. This is not a map in our category. A conuter example is \(f(-1 \ times -2) = f(-1) \times f(-2) = 2 \ne f(2) = -2\)
  6. This map isn’t valid for the given domain and codomain: \((-1)^3 = -1 \notin \mathbb{R}_{>0}\).

Session 5 - Divisions of Maps: Sessions and Retractions

Determination Problems

We begin by looking at the idea of determination from the context of scientific experiments. If one has a piston over some gas, then the temperature of the gas determines the volume of the gas, and thus the position of the piston. We then look at the general case for maps.

For determination, there is a map \(A \overset{h}{\rightarrow} C\) and \(A \overset{f}{\rightarrow} B\). For the determination problem, we seek all maps \(B \overset{g}{\rightarrow} C\) such that \(g \circ f = h\). The problem being asked here is: “is \(h\) determined by \(f\)?” We look at a few more determination problems and see that even though it may be possible to compose maps together, they don’t necessarily solve the determination problem.

Show that if there is a map \(g\) for which \(h = g \circ f\), then for any pair \(a_1\), \(a_2\) of points \(1 \rightarrow A\) of the domain \(A\) of \(f\), we have: \(f \circ a_1 = f \circ a_2 \Rightarrow h \circ a_1 = h \circ a_2\).

We have \(h \circ a_1 = (g \circ f) \circ a_1 = g \circ (f \circ a_1) = g \circ (f \circ a_2) = (g \circ f) \circ a_2 = h \circ a_2\).

Does the converse hold? That is, given the above as a hypothesis, does the map \(g\) have to exist such that \(h = g \circ f\)?

If \(f\) has the property that \(f \circ a_1 = f \circ a_2\) for all \(a_1\), \(a_2\), then \(f\) must be a constant map. Likewise with \(h\). Therefore a map \(g\) would exist, as all elements in \(A\) would map to a single element of \(C\) via \(g \circ f\), which is stipulated by the condition \(h \circ a_1 = h \circ a_2\).

A Special Case: Constant Maps

We look at a special case of the determination problem where \(B\) is a one element set. We notice that our problem has a solution when \(h\) sends all elements to a single element of \(C\), and \(g\) would be a choice of element in \(C\).

A map that can be factored through \(1\) is called a constant map.

Choice Problems

Another division problem occurs when looking for the other factor. That is, given \(A \overset{h}{\rightarrow} C\) and \(B \overset{g}{\rightarrow} C\), we seek \(A \overset{f}{\rightarrow} B\) such that \(g \circ f = h\). This is called the choice problem, because in order to find such a map we must choose for each element \(a \in A\) an element \(b \in B\) such that \(g(b) = h(a)\). We look at a concrete example of a choice problem through people, towns and supermarkets. We have a map from people to towns assignment each person their residence, and a map from supermarkets to towns indicating the location of the supermarket. The problem is then to find all maps between people and supermarkets, such that the location of the supermarket is in the same location as the person.

Show that if there is an \(f\) with \(g \circ f = h\), then \(h\) and \(g\) satisfy: For any \(a \in A\) there is at least one \(b \in B\) such that \(h(a) = g(b)\).

Let \(a\) be a point \(1 \rightarrow A\). Then \(h \circ a = g \circ (f \circ a)\). As \(f \circ a\) has domain \(B\), it follows that there is an element of \(B\) such that \(h(a) = g(b)\).

Two Special Cases of Division: Sections and Retractions

We turn our attention to a special case of choice problems, where the set \(A\) is the same as \(C\) and \(h\) is the identity map. In this case, the choice problem asks for each \(a \in A\) a \(b \in B\) such that \(g(b) = a\). This is “half” of an inverse, so to speak, as it only satisfies one of the conditions - namely \(g \circ f = 1_A\). This brings us to the definition of a section:

\(A \overset{f}{\rightarrow} B\) is a section of \(B \overset{g}{\rightarrow} A\) if \(g \circ f = 1_A\).

We see that the presence of a section lets us solve a whole class of choice problems, and note the analogy that “division by 2” is simply “multiplication by 1/2”.

Stacking or Sorting

In this section, we see a nice “trick” for understanding what a section means by stacking elements in a set. If we do this, we can easily see the correspondence between elements across the map. The crucial takeaway here is that we can easily spot if a function doesn’t have a section - if there are elements in the codomain with no stacked elements above in the domain, then a section cannot exist. This also lets us count the amount of sections a map can have - it’s the product of the size of each “stack”. If a stack is empty, then this continues the intuition that the map cannot have a section (as we multiply by zero).

We wrap up this discussion of stacking with an example of efficiently settling bills in a Chinese restaurant, though this doesn’t seem particularly related to sections.

Session 6 - Two General Aspects or Uses of Maps

For a general map \(X \overset{g}{\rightarrow} B\) we can say that \(g\) gives rise to a sorting of \(X\) into \(B\) ‘sorts’ - that is, \(g\) is a sorting of \(X\) by \(B\). This way of viewing a map describes the map as a \(B\)-valued property on \(X\). Another word to describe this notion of sorting is fibering - we say that \(X\) is divided into \(B\) fibers. Partitioning is a similar term, but only applicable to finite sets where the map has a section.

We also have the notion of naming elements of \(B\) by \(X\), or the geometric interpretation that we have a figure of \(X\) in \(B\). This emphasises the structure in the codomain, whereas sorting/fibering/partinioning emphasizes structure in the domain.

Finally, this session considers a “philosophical” view point. The objective category we are investigating contains within it subjective objects - a category of small objects. This subjective category can be used to name objects in the objective category, or the objective category can be used as properties of the small objects.

Session 7 - Isomorphisms and Coordinates

We begin this session by considering what a coordinate system is. We take begin by taking some real world concept - such as an infinite line - and deciding on a unit of distance, a direction of positivity, and an origin. This lets us build an isomorphism \(\mathbb{R} \overset{plot}{\rightarrow} L\), who’s inverse determines the coordinates of a point on the line. This notion generalises to \(\mathbb{R}^2\) and \(\mathbb{R}^3\) by taking products of real numbers.

We see another example of an isomorphism with a tournament bracketing system for tennis - we have an isomorphism between natural numbers and a set of players indicating both their rank, and in the inverse direction their seed position in the bracketing system.

Two Abuses of Isomorphism

  1. Assuming that some structure in the domain holds in the codomain.
  2. Assuming that from one familiar object \(A\) with objects \(X\) and \(Y\) coordinated by \(A\) that \(X\) and \(Y\) can be combined.

Session 8 - Pictures of a Map Making its Features Evident

This session is primarily a discussion on different ways of visualizing a map in order to easily count the amount of possible sections the map has. We again revisit the idea of stacking as a way of viewing maps, and gain more intuition that a section is a choice of representatives. We also see why a section has the name “section” - we can view the section as a “cross-section” of its codomain.

Session 9 - Retracts and Idempotents

We have seen that a reasonable notion of ‘same size’ is given by isomorphism - \(A\) is isomorphic to \(B\) means that there is at least one invertible map from \(A\) to \(B\), and for finite sets this tells us precisely that \(A\) and \(B\) have the same number of points.

We begin this session by considering a weaker relation - \(A\) is at most as big as \(B\).

Show that unless the set \(A\) has a point and \(B\) has none, then \(A \leq B\).

If \(A\) has no points, then there are 0 maps to \(B\). \(B\) has \(\geq 0\) elements, so this property holds. If \(A\) has at least one point, then by the assumption in the question \(B\) also has at least one point. Thus there is at least one map from \(A\) to \(B\), and so \(A \leq B\).

While this property works well for finite sets, it doesn’t scale well to other categories. Instead, we use retracts as a tool to measure “at most as big as”.

Show that \(A \leq A\).

\(A\) has an identity map which is idempotent. Thus this map has the property of being a retraction for itself, so \(A \leq A\).

Show that if \(A \leq B\) and \(B \leq C\) then \(A \leq C\).

We proved that if two maps \(f\) and \(g\) have retractions, then there composite also has a retraction. Thus there is a map \(A \rightarrow C\) with a retraction, so \(A \leq C\).

Next, we look at idempotent endomaps given by composing a map \(s\) with its retraction \(r\) in the opposite order: \(e = sr\). This is idempotent, as can be seen from \(ee = srsr = s(rs)r = sr = e\). This endomap is evidence in \(B\) of the maps \(s\) and \(r\). To see a concrete example of such an idempotent endomap, we consider people of USA (\(B\)) and congressional districts (\(A\)). We see that the fixed points of the endomap \(e\) in this case are people who are members of the House of Representatives. Specifically, this set of fixed points is isomorphic to the set of congressional districts.

We concentrate on this process, and draw the internal diagram for an endomap - observing that every point reaches its fixed point after (at most) one map. We then redraw this diagram as a sorting of this set by \(A\), the set of congressional districts.

The process we just observed has a specific name:

If \(B \overset{e}{\rightarrow} B\) is an idempotent map, a splitting of \(e\) consists of an object \(A\) together with two maps \(A \overset{s}{\rightarrow} B\) and \(B \overset{r}{\rightarrow} A\) with \(rs = 1_A\) and \(sr = e\).

Suppose that both \(A \overset{s}{\rightarrow} B\), \(B \overset{r}{\rightarrow} A\) and \(A' \overset{s'}{\rightarrow} B'\), \(B' \overset{r'}{\rightarrow} A'\) split the same idempotent \(B \overset{e}{\rightarrow} B\). Use these maps to construct an isomorphism \(A \overset{f}{\rightarrow} A'\).

We know that \(e = sr = s'r'\), and \(1_a = rs = r's'\). Thus we have

  • \(A \overset{f}{\rightarrow} A'\) given as \(f = r's\) and its inverse \(A' \overset{f^-{-1}}{\rightarrow} A\) given by \(f^{-1} = rs'\).
  • \(f^{-1}f = (rs')(r's) = r(s'r')s = res = rsrs = (rs)(rs) = 1_a1_a = 1_a\)
  • \(ff^{-1} = (r's)(rs') = r'(sr)s' = r'es' = r'(s'r')s' = (r's')(r's') = 1_{A'}1_{A'}\)

Thus \(A \overset{f}{\rightarrow} A'\) is an isomorphism.

As another motivating example of this process of idempotent maps and splitting, we look at the set of rational numbers. There is an idempotent map here that reduces each rational number to its canonical form - this process of reduction is the map \(e\).

Three Kinds of Retract Problems

We now briefly look at three different types of retract problems:

  1. Given \(B \overset{r}{\rightarrow} A\) we may seek sections. In this case, we can view \(r\) as a sorting of a \(B\), so a section in this case can be seen as choosing an “example” for each sort.
  2. The dual of this problem is given \(A \overset{s}{\rightarrow} B\) we seek retractions \(r\). In this case, we’re given “examples”, and we seek associations from real observations back to these examples.
  3. Finally, we considering the learning process of children. They begin with an idempotent map on animals - each animal can be mapped to some “known” animal. This idempotent can be split by the smaller object that contains sorts of animals.

Quiz

Question 1

For a map to have no section, we need to show that there is no map \(B \overset{s}{\rightarrow} A\) such that \(f \circ s = 1_B\). Following the idea of “stacking”, this would mean there are elements in \(B\) that have no corresponding elements of \(A\) in the stack. Therefore, if we take the set \(A = { a }\) and \(B = {0, 1}\), we can build the map \(f\), where:

  • \(f(a) = 0\)

The map \(f\) has a retraction \(r\), where \(r(0) = a\), as \(r(f(a)) = r(0) = a\). However, there is no section for \(s\). A section would have to satisfy the property \(f \circ s = 1_B\). However, there is only one map \(B \to A\), \(r\), so by the Theorem on Uniqueness of Inverses, we must have \(r = s\). \(r\) is not a section, as \(f(r(1)) = f(a) = 0\).

Therefore the given sets \(A\) and \(B\) with map \(f\) have a retraction \(r\), but no section.

Question 2

We have

\[\begin{array}{lcl} (p \circ q) \circ (p \circ q) &=& (p \circ q \circ p) \circ q \\ &=& p \circ q \end{array}\]

Therefore \(p \circ q\) is idempotent.

Also,

\[\begin{array}{lcl} (q \circ p) \circ (q \circ p) &=& q \circ (p \circ q \circ p) \\ &=& q \circ p \end{array}\]

So \(q \circ p\) is also idempotent.