L&S Cat Theory: Attempted solutions to "Conceptual Mathematics" by Lawvere and Schanuel

Let’s start with our definition:

Given this, we want to show \(e_1 = i s\) and \(e_0 = i t\) satisfy \(e_k e_j = e_j\) for \(k, j = 0, 1\text{.}\) Since there’s only four cases, it shouldn’t be too much effort to list them all out:

Conceptually, these properties would seem to imply that every point in \(P\) serves as both source and target for some arrow in \(X\text{.}\)

First, let’s formulate our definition with a diagram:

Where this gets interesting is when we look at all possible paths we can follow between \(Y\) and \(P\) in addition to the ones between \(X\) and \(Q\text{.}\) To follow the pattern of the previous categories, we’d need to enforce all 3 of the following:

The order of that last one seems a little bit tricky since our retraction \(i\) is heading in the opposite direction. At the same time, this map \(i\) is presicely what allows us to "solve" for \(f_D\) in terms of \(f_A\text{.}\) In Exercise 15, we saw that this \(i\) only works if there’s an arrow forming a "self-loop" at each point. All our map \(f_D\) needs to do is match up the self-looping arrows on each point in \(P\) with the corresponding self-looping arrows on \(Q\text{.}\)

Let’s suppose we use the common section \(i\) on a point \(p \in P\) to produce some arrow \(x = i p \in X\text{.}\) It follows that this arrow \(x\) needs to form a self-loop such that \(s x = t x = p\text{,}\) since \(s i = 1_P\) and \(t i = 1_P\) imply \(s \circ x = s \circ i \circ p = 1_P \circ p = p\) and \(t \circ x = t \circ i \circ p = 1_P \circ p = p\) respectively. We can then pair that point with a corresponding self-looping arrow \(f_A(x) = y \in Y\) with \(s'(y) = t'(y) = q\text{.}\) We know such a loop needs to exist because \(f_D s x = s' f_A x = s' y\) and \(f_D t x = t' f_A x = t' y\) would need to satisfy \(f_D s x = f_D t x\text{.}\) Finally, we can put this all together to define \(f_D p = s' f_A i p = t' f_A i p = q\) over all possible points in \(P\text{.}\)

I feel like there’s probably an easier way to demonstrate this using contradiction.

Suppose for a minute that there did exist some point \(p\) which satistfies \(f_D(p) \neq (s' \circ f_A \circ i)(p)\text{.}\) You could use the structure preserving criteria of \(f_A i = i' f_D\) to establish that \(f_D(p) \neq (s' \circ i' \circ f_D)(p)\text{.}\) Since we also know \(s' i' = 1_Q\text{,}\) that previous equation simplifies down to \(f_D(p) \neq (1_Q \circ f_D)(p)\text{,}\) which directly contradicts the identity property of \(1_Q\text{.}\) Our assumption must therefore be false and \(f_D = s' \circ f_A \circ i\text{.}\) QED.

Let’s lay out the structure we’re examining:

If we’re going to build a map between two such structures, we’ll need to include a pair of maps like so:

At a glance, the structure of this combined diagram resembles a composition of two \(\mathcal{S}^{\circlearrowright}\)-morphisms with another yet-to-be named structure that’s resembles our reflexive graph. I feel like it deserves some cool symbol like \(\mathcal{S}^{\downarrow^{\bullet}_{\bullet} \uparrow}\text{.}\)

Let’s start with the more familiar structures. I’d want this map to preserve the behavior of the endomaps \(\phi_n\) and \(\mu_n\) on each set. I’d want the maps \(f_M, f_D\) to behave like \(\mathcal{S}^{\circlearrowright}\)-morphisms here. Specifically, \(\boxed{M_0^{\circlearrowright \phi_0}} \xrightarrow{f_M} \boxed{M_1^{\circlearrowright \phi_1}}\) means that I’d want \(f_M \circ \phi_0 = \phi_1 f_M\) and \(\boxed{F_0^{\circlearrowright \mu_0}} \xrightarrow{f_F} \boxed{M_1^{\circlearrowright \mu_1}}\) means that I’d want \(f_F \circ \mu_0 = \mu_1 f_F\text{.}\)

Having a set of four equations to go with four pairs of maps seems consistent we what we saw for the other maps.

To prove \(a\) is injective, we’ll need the provided definition:

We’re given that \(a\) has a retraction \(p\) such that \(p a=1_X\text{.}\) To prove \(a\) is injective, we need to demonstrate that for any \(\mathbf{1} \xrightarrow{x_0} T\) and \(\mathbf{1} \xrightarrow{x_1} T\) it follows that \(a x_0 = a x_1 \implies x_0 = x_1\text{.}\)

Let’s approach this through contradiction. Suppose we had some \(x_0 \neq x_1\) that satisfy \(a x_0 = a x_1\text{.}\) Compose \(p\) on the left of both sides:

This contradicts our assumption that \(x_0 \neq x_1\text{,}\) which means that no such \(x_0, x_1\) exist. It follows that \(a x_0 = a x_1 \implies x_0 = x_1\) and \(a\) is injective.

Our maps here are defined by the following diagram:

To show \(a\) in \(\mathcal{S}^{\circlearrowright}\text{,}\) we’ll need to demonstrate that \(a \alpha = \beta a\) over the entire domain \(\{0,x\}\text{.}\) We’re given both \(a 0 = 0\) and \(a x = y\text{,}\) so these are fairly trivial:

Since those are the only points we have, we can safely conclude that \(a \alpha = \beta a\text{.}\)

Since \(a\) is only defined for two points, any \(\mathbf{1} \xrightarrow{x_0} T\) and \(\mathbf{1} \xrightarrow{x_1} T\) such that \(x_0 \neq x_1\) would directly imply that these two points are in fact the complete set \(X = \{0, x\}\text{.}\) Since \(a 0 = 0 \neq a x = y\text{,}\) it follows that \(\{a x_0, a x_1\} = \{0, y\}\) so clearly \(a x_0 \neq a x_1\text{.}\)

Essentially, the retractions \(p\) must contain the reversed arrows of \(a\text{,}\) but that leaves two possible places for it to send the third point which didn’t already have an origin defined:

For any retraction \(p_n\text{,}\) we’d be forced to have \(p_n 0 = 0\) and \(p_n y = x\) in order to have \(p_n a = 1_X\text{.}\) As a map \(Y \xrightarrow{p_n} X\text{,}\) \(p_n\) needs to do something with the point \(\bar{y} \in Y\) and there are only two choices. Let’s call them \(\{p_0, p_1\}\) such that \(p_0 \bar{y} = 0\) and \(p_1 \bar{y} = x\text{.}\)

As in the previous exercise, our only possible retractions are \(p_0\) and \(p_1\text{,}\) depending on where they send \(\bar{y}\text{.}\) For \(\boxed{Y^{\circlearrowright \beta}} \xrightarrow{p_n} \boxed{X^{\circlearrowright \alpha}}\) to be a valid \(\mathcal{S}^{\circlearrowright}\)-map, it needs to have the property \(p_n \circ \beta = \alpha \circ p_n\text{.}\) We’ll test each of our two possiblities for \(p_n\) in turn.

For \(p_0\text{,}\) we’d have \(p_0 \beta \bar{y} = p_0 y = x\) and \(\alpha p_0 \bar{y} = \alpha 0 = 0\text{.}\) Since \(p_0 \beta \bar{y} \neq \alpha p_0 \bar{y}\text{,}\) \(p_0\) is not a valid \(\mathcal{S}^{\circlearrowright}\)-map.

For \(p_1\text{,}\) we’d have \(p_1 \beta \bar{y} = p_1 y = x\) and \(\alpha p_1 \bar{y} = \alpha x = 0\text{.}\) Since \(p_1 \beta \bar{y} \neq \alpha p_1 \bar{y}\text{,}\) \(p_1\) is not a valid \(\mathcal{S}^{\circlearrowright}\)-map.

Having exhausted both possible retractions of \(a\text{,}\) we’re forced to conlude that no retraction exists in \(\mathcal{S}^{\circlearrowright}\text{.}\)

I’m going to start by sketching out the eight possible maps \(p: Y \longrightarrow X\text{:}\)

In order for \(p\) to be an \(\mathcal{S}^{\circlearrowright}\)-map, it needs to satisfy \(p \circ \beta = \alpha \circ p\text{.}\) Let’s go through those maps again, but this time produce tables of those values for each of \(\{0,y,\bar{y}\}\)

It appears that there are precisely two possible \(\mathcal{S}^{\circlearrowright}\)-maps. The one that sends everything to 0 and the one that sends everything to 0 but \(\bar{y}\) which it instead sends to \(x\text{.}\) These two maps make sense when considering the behavior of the endomap \(\alpha\) which always returns 0.

Let’s diagram the insertion \(J\) for our present maps:

Suppose \(p\) is a retraction for \(a\) in \(\mathcal{S}^{\downarrow_{\small\!\!\bullet}^{\small\!\!\bullet}}\) such that \(p \circ a = 1_X\text{.}\) We saw in Exercise 21 that there are precisely two possible maps \(p\) could be. We know \(p y = x\) and \(p 0 = 0\text{.}\) The only question was if \(p \bar{y} = x\) or \(p \bar{y} = 0\text{.}\)

However, for \(p\) to be a member of this category, it needs to satisfy the equation \(p \circ \beta = \alpha \circ p\) on the following commutative square:

In Exercise 23, our exhaustive search of maps \(Y \longrightarrow X\) revealed only two maps for which \(p \circ \beta = \alpha \circ p\text{.}\) However, neither of those maps match up with the only two possible retractions for \(p\text{.}\) We’re forced to conclude that can’t exist a map meeting these conditions.