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

Given a \(\mathcal{S}^{\downarrow^{\bullet}_{\bullet} \downarrow}\)-map between two graphs, we want to show \(f_D \circ s = f_D \circ t\) can only be true when \(f_A\) maps every arrow in \(X\) to a loop in \(Y\text{.}\) Our external diagram is reproduced below:

Thinking back to Exercises 9, the looping behavior of our endomap \(\alpha\) was based on the property that \(\alpha^3 = \alpha\text{.}\) I’m going to suggest that we can define an n-loop by the existence of endomap such that \(\alpha^{n+1} = \alpha\) over some subspace with that many elements. Then each 1-loop would be a fixed point for the endomap and a 2-loop would be an antipodal endomap on two points.

So what would these loops look like here? An n-loop in \(Y\) would need to be some sequence of \(\{y_1, y_2, ..., y_n\}\) where \(s y_n = t y_{n-1}\text{.}\)

I think the key to is that the equation \(f_D \circ s = f_D \circ t\) is essentially identifying a fixed point where both the source and target of an arrow from \(X\) wind up at the same point in \(Q\) after the transformation. Our category enforces that \(f_D \circ s = s' \circ f_A\) and \(f_D \circ t = t' \circ f_A\text{,}\) so it follows that this equation is equivalent to the expression \(s' \circ f_A = t' \circ f_A\text{.}\) In other words, any \(x \in X\) for which \((f_D \circ s)(x) = (f_D \circ t)(x)\) would directly correspond with a loop \(y = f_A x \in Y\) such that \(s' y = t' y\text{.}\)

Clearly, any self-loop in \(X\) must get matched up with a self-loop in \(Y\text{.}\) If for any \(\mathbf{1} \xrightarrow{x} X\) we have \(s x = t x\text{,}\) it follows naturally that both \((f_D \circ s)(x) = (f_D \circ t)(x)\) and \((s' \circ f_A)(x) = (t' \circ f_A)(x)\text{.}\)

Suppose we have some arrow in \(X\) satisfying \((f_D \circ s)(x) = (f_D \circ t)(x)\) but for which \(s(x) \neq t(x)\text{.}\) This needs to map to an arrow \(y = f_A(x)\) which would need to satisfy the condition that \((s' \circ f_A)(x) = (t' \circ f_A)(x)\text{.}\) It follows that \(s' y = t' y\) which forms another self-loop. So whether or not we start with a self-loop in \(X\text{,}\) we must wind up with one in \(Y\text{.}\)

This result seems almost too simple. I was expecting to need to work with loops of varying lengths, but it turns out the 1-loops were the only ones I needed. I may need to come back to this later.

I’m thinking that the map \(\mathbb{Z}^{\circlearrowright 5 \times ()}\) is the same as the one we used in Exercise 7. Previously we showed that "multiplying by 5" was not an invertable operation on the integers because the reverse operation of "dividing by 5" is not defined on the same domain. Now it looks like we’re planning to sidestep that issue by inserting our map in \(\mathbb{Q}\) instead.

Let’s consider a trivial insertion of \(\mathbb{Z} \xrightarrow{f} \mathbb{Q}\) where we simply define \(f(x) = x\text{.}\) I guess more specifically, we assign each integer \(\mathbf{1} \xrightarrow{z} \mathbb{Z}\) to the rational number \(\frac{z}{1} \in \mathbb{Q}\text{.}\) In order for this to be a valid \(\mathcal{S}^{\circlearrowright}\)-map, then we’d need \(\boxed{\mathbb{Z}^{\circlearrowright 5 \times ()}} \xrightarrow{f} \boxed{\mathbb{Q}^{\circlearrowright 5 \times ()}}\) to satisfy the equation \(f \circ (5 \times ()) = (5 \times ()) \circ f\text{.}\) This follows directly from commutative property of multiplication: \(x \times 5 = 5 \times x\text{.}\)

Since we’ve already established that we’re working with an endomap on \(\mathbb{Q}\text{,}\) to show that \(\mathbb{Q}^{\circlearrowright 5 \times ()}\) is an "automorphism" we just need to show it has an inverse. The inverse function would be given by the map \(\frac{1}{5} \times ()\text{.}\) For any \(q \in \mathbb{Q}\text{,}\) we have \(\frac{1}{5} \times 5 \times q = q = 5 \times \frac{1}{5} \times q\text{.}\) It follows that since \(\mathbb{Q}^{\circlearrowright 5 \times ()}\) is both an endomap and invertable, it meets the definition of an automorphism.

All that’s left is to prove our map \(f\) is injective. For any pair \(\mathbf{1} \xrightarrow{z_1} \mathbb{Z}\) and \(\mathbf{1} \xrightarrow{z_2} \mathbb{Z}\) such that \(f z_1 = f z_2\text{,}\) our choice of \(f\) implies this statement is equivalent to \(\frac{z_1}{1} = z_1 = z_2 = \frac{z_2}{1}\text{.}\)

Another way to think of this would be that \(f\) is injective when it has a retraction. In this case, the map \(\mathbb{Q} \xrightarrow{r} \mathbb{Z}\) given by \(r(x) = \lfloor x \rfloor\) meets this condition. For any \(z \in \mathbb{Z}\text{,}\) \(r f z = r \frac{z}{1} = \lfloor \frac{z}{1} \rfloor = z\) so \(r \circ f = 1_{\mathbb{Z}}\text{.}\)

Given the standard idempotent

and an automorphism \(Y^{\circlearrowright \beta}\text{,}\) we want to show any \(\mathcal{S}^{\circlearrowright}\)-map \(X^{\circlearrowright \alpha} \xrightarrow{f} Y^{\circlearrowright \beta}\) must be non-injective. Our "hint" is that the map must send both elements of \(X\) to the same fixed point in \(Y\text{.}\)

It follows from the definition of \(\mathcal{S}^{\circlearrowright}\)-map that \(f \circ \alpha = \beta \circ f\text{.}\) However, \(\beta\) is given as an automorphism which means it must have some inverse map \(Y \xrightarrow{\beta^{-1}} Y\) such that \(\beta \circ \beta^{-1} = \beta^{-1} \circ \beta = 1_Y\text{.}\) Apply this map \(\beta^{-1}\) to the left sides of our earlier expression to get \(\beta^{-1} \circ f \circ \alpha = f\text{.}\)

Since there’s literally only two elements in \(X\text{,}\) let’s call them \(\{x_0,x_1\}\) and denote the behavior of \(\alpha\) by \(\alpha x = x_0\) for \(x \in X\text{.}\) It follows from \(\beta^{-1} \circ f \circ \alpha = f\) that \(f x_0 = \beta^{-1} f \alpha x_0 = \beta^{-1} f x_0\) is a "fixed point" in \(Y\) since \(f x_0 = \beta^{-1} f x_0 \implies \beta f x_0 = f x_0\text{.}\) It also follows that \(f x_1 = \beta^{-1} f \alpha 1 = \beta^{-1} f x_0\) returns the same fixed point. Having shown that \(f x_0 = f x_1\) for some \(x_0 \neq x_1\text{,}\) we’ve demonstrated that \(f\) is non-injective.

Given that we have an injective map \(X^{\circlearrowright \alpha} \xrightarrow{f} Y^{\circlearrowright \beta}\text{,}\) it must also have some retraction \(Y \xrightarrow{r_f} X\) such that \(r_f \circ f = 1_X\text{.}\) We’re also given that \(\beta\) is an automorphism, which guarantees it has an inverse \(\beta^{-1}\text{.}\)

We want to prove that \(\alpha\) itself must be injective. It suffices to show there exists a retraction \(r_\alpha \circ \alpha = 1_X\text{.}\) I’m going to claim that the map \(r_\alpha = r_f \circ \beta^{-1} \circ f\) should have this desired property.

We can use this definition to expand the expression \(r_\alpha \circ \alpha\text{:}\)

As a \(\mathcal{S}^{\circlearrowright}\)-map, we know \(f \circ \alpha = \beta \circ f\text{:}\)

And there we have it!

There’s an awful lot to unpack here so lets start with a category. We know we have some sets of objects \(x \in X\) or \(y \in Y\) and maps \(X \xrightarrow{f} Y\) which obey the identity and associative properties over the domain and codomain.

Over the course of the article, we’ve seen that there’s a natural insertion of this map into the category \(\mathcal{S}^{\downarrow^{\bullet}_{\bullet} \downarrow}\text{.}\) For each pair of object \(x \in X\) and \(y \in Y\) such that \(f x = y\text{,}\) we can think of the map \(f\) as a collection of "arrows" with a source at \(x\) which we indicate \(s x = x\) and a target object at \(y\) which we indicate \(t x = y\text{.}\)

From what I gather, our \(\mathcal{A}\) supplements this insertion with an arbitrary number of additional properties \(A = \{a_1, a_2, ..., a_n\}\text{.}\) Each individual property \(a_n \in A\) gets a corresponding map \(\alpha_n\) that returns the value of the property with that name. For any property map \(\alpha\text{,}\) we can either access this property before we apply the map \(f\) or after. This provides natural defintion of preserving the structure of each property so that \(\alpha f = f \alpha\) as follows:

Our \(\mathcal{A}\)-figures must satisfy these conditions for every property. If that’s the case, then we can embed our \(\mathcal{S}^{\downarrow^{\bullet}_{\bullet} \downarrow}\)-map representation of \(f\) by treating our maps \(s\) and \(t\) as "just another property" in an \(\mathcal{A}\)-figure. Perhaps this might be diagrammed as follows:

The \(\mathcal{A}\)-structure would preserves the the source and targets of our map \(f\text{.}\) Essentially, each map \(f: X \longrightarrow Y\) can be expressed as an \(\mathcal{A}\)-structure with two components if we let \(\alpha_0\) be our "source" map and \(\alpha_1\) be our "target" map.

I’m not entirely sure, but I think the existence of such an embedding would reasonably demonstrate this notion of "giving rise to a map in the category".