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

Let’s start by recapping the definition. The maps \(Q,q_1,q_2\) are a product if and only if for each object \(X\) and any pair of maps \(X \xrightarrow{f_1} B_1\) and \(X \xrightarrow{f_2} B_2\) there is exactly one map \(X \xrightarrow{f} Q\) satisfying both \(f_1 = q_1 f\) and \(f_2 = q_2 f\text{.}\)

If that statement is true for every object \(X\text{,}\) it must also be true for the object \(P\text{.}\) We know we have a pair of maps \(P \xrightarrow{p_1} B_1\) and \(P \xrightarrow{p_2} B_2\text{,}\) so there must be a unique map \(P \xrightarrow{f} Q\) with \(p_1 = q_1 f\) and \(p_2 = q_2 f\text{.}\)

Likewise, the maps \(P,p_1,p_2\) form a product. For any object \(X\) with arbitrary maps \(X \xrightarrow{f_1} B_1\) and \(X \xrightarrow{f_2} B_2\text{,}\) we must have exactly one map \(X \xrightarrow{g} P\text{.}\) If this is true for all objects, it must also be true for \(Q,q_1,q_2\text{.}\) It follows that there is a unique map \(Q \xrightarrow{g} P\) with \(q_1 = p_1 g\) and \(q_2 = p_2 g\text{.}\)

Having established that the maps \(P \xrightarrow{f} Q\) and \(Q \xrightarrow{g} P\) exist and are both unique, we must also prove they are isomorphisms. To do so we’ll need to establish \(g \circ f = 1_P\) and \(f \circ g = 1_Q\text{.}\)

If the maps \(f,g\) are unique, then the compositions of maps \(Q \xrightarrow{f \circ g} Q\) and \(P \xrightarrow{g \circ f} P\) must also be unique. Since we’re guaranteed to have an identity map for any given domain, it follows from uniqueness that \(f \circ g = 1_Q\) and \(g \circ f = 1_P\text{.}\) Thus, we’ve established that \(f,g\) are inverses of each other and consequently isomorphisms.

Let’s begin by summarizing what we know.

We know this category has a terminal object. Let’s call it \(\mathbf{1}\text{.}\) For any object \(X\) in our category \(\mathcal{C}\text{,}\) there is exactly one \(\mathcal{C}\)-map \(X \rightarrow \mathbf{1}\text{.}\) Since this must also hold true for \(\mathbf{1}\text{,}\) we can safely assume the existence of a unique map \(\mathbf{1} \xrightarrow{1_1} \mathbf{1}\text{.}\)

We also know we have a product \(B_1 \times B_2\) and projection maps \(p_1,p_2\text{.}\) For any object \(X\) in \(\mathcal{C}\text{,}\) and any pair of maps \(X \xrightarrow{f_1} B_1\) and \(X \xrightarrow{f_2} B_2\text{,}\) there exists exactly one map \(X \xrightarrow{f} B_1 \times B_2\) with the property that \(f_1 = p_1 f\) and \(f_2 = p_2 f\text{.}\)

Let’s combine these definitions by choosing \(X = \mathbf{1}\text{.}\) It follows that for any pair of points \(\mathbf{1} \xrightarrow{b_1} B_1\) and \(\mathbf{1} \xrightarrow{b_2} B_2\text{,}\) there is exactly one map \(\mathbf{1} \xrightarrow{g} B_1 \times B_2\) with \(b_1 = p_1 g\) and \(b_2 = p_2 g\text{.}\)

Given that \(\mathbf{1}\) is a terminal object, we can pair each of the maps \(b_1,b_2,g\) with it’s respective dual: \(B_1 \xrightarrow{\bar{b_1}} \mathbf{1}\text{,}\) \(B_2 \xrightarrow{\bar{b_2}} \mathbf{1}\text{,}\) and \(B_1 \times B_2 \xrightarrow{\bar{g}} \mathbf{1}\text{.}\)

Essentially, either \(f,\bar{g}\) are the unique inverses such that \(\mathbf{1} \rightarrow X \xrightarrow{f} B_1 \times B_2 \xrightarrow{\bar{g}} \mathbf{1}\) or we get two competing definitions of these three unqiue compositions:

Our category \(\mathcal{S}^A\) has as objects a set \(X\) together with any action \(A \times X \xrightarrow{\xi} X\) of \(A\text{.}\) Our maps from \(X,\xi\) to \(Y,\eta\) are \(\mathcal{S}\)-maps \(X \xrightarrow{f} Y\) which "respect actions of \(A\)" such that \(f(\xi(a,x)) =\eta(a,f(x))\) for all \(a \in A,x \in X\text{.}\)

So lets attempt to define composition. We’ll need a pair of \(\mathcal{S}^A\)-maps. Let’s call them \(\langle X,\xi \rangle \xrightarrow{f} \langle Y,\eta \rangle\) and \(\langle Y,\eta \rangle \xrightarrow{g} \langle Z,\zeta \rangle\text{.}\) The action respecting nature of these maps means that for all \(a \in A,x \in X\) we have \(f(\xi(a,x)) =\eta(a,f(x))\) preserved by the first map and \(g(\eta(a,x)) =\zeta(a,g(x))\) preserved by the second map.

Let’s define the composition \(\langle X,\xi \rangle \xrightarrow{g \circ f} \langle Z,\zeta \rangle\) as the composition of respective \(\mathcal{S}\)-maps \(X \xrightarrow{g \circ f} Z\text{.}\) We’ll need to show that it respect actions in our category, namely that \((g \circ f)(\xi(a,x)) = \zeta(a,(g \circ f)(x))\) for all \(a,x\text{.}\)

Let’s start with \((g \circ f)(\xi(a,x))\text{.}\) We can regroup the terms to form \(g(f(\xi(a,x)))\text{.}\) Since \(f(\xi(a,x)) = \eta(a,f(x))\text{,}\) we can substitute to get \(g(\eta(a,f(x)))\text{.}\) Since we also know \(g(\eta(a,x)) =\zeta(a,g(x))\text{,}\) that means that \(g(\eta(a,f(x))) = \zeta(a,g(f(x))) = \zeta(a,(g \circ f)(x))\text{.}\) This establishes that \(g \circ f\) is a valid \(\mathcal{S}^A\)-map.

As a category, each domain must have an identity map. Each set/action pair \(X,\xi\) must have some map \(\langle X,\xi \rangle \xrightarrow{1_{X,\xi}} \langle X,\xi \rangle\) such that \(1_{X,\xi}(\xi(a,x)) =\xi(a,1_{X, \xi}(x))\) for all \(a,x\text{.}\) I think we get this from the "product" of identity maps \(1_{X,\xi} = 1_A \times 1_X = 1_{A \times X}\text{.}\) This lets us rewrite the identity above as \((1_A \times 1_X)(\xi(a,x)) = \xi(1_A(a),1_X(x))= \xi(a,x)\text{.}\)

For any \(\mathcal{S}^A\)-map \(\langle X,\xi \rangle \xrightarrow{f} \langle Y,\eta \rangle\text{,}\) we know \(f(\xi(a,x)) =\eta(a,f(x))\) for all \(a,x\text{.}\) This should continue to hold true if we choose \(f = 1_X, Y = X, \xi = 1_{A \times X} \text{.}\) Thus, for all \(a,x\) we can assert \(1_X(1_{A \times X} (a,x))=1_{A \times X} (a,1_X(x)) = 1_{A \times X} (a,x) = (a,x)\text{.}\)

What about our associative property? I think we kind of inherit this from the properties of \(\mathcal{S}\text{.}\) Since our \(\mathcal{S}^A\)-maps come from \(\mathcal{S}\)-maps, they must uphold \((h \circ g) \circ f = h \circ (g \circ f)\) independently of the additional retrictions placed on them as members of \(\mathcal{S}^A\text{.}\) We’ve already established that actions are respected by composition, so both sides necessisarily produce \(\mathcal{S}^A\)-maps.

Okay, I was under the impression that "equations" implied the presence of "an equals sign". I’m not even sure how to interpret this:

The preceeding text discusses a "preferred binary operation" \(A \times A \xrightarrow{\alpha} A\) and a "point" \(\mathbf{1} \xrightarrow{a_0} A\text{.}\) The action \(\alpha\) corresponds to map composition and \(a_0\) acts as the identity map \(1_X\text{.}\) It would be described by \(\xi\) through the equations: \(\forall a,b,x: \xi(\alpha(a,b),x) = \xi(a,\xi(b,x)) \) and \(\forall x: \xi(a_0,x) = x\text{.}\)

This sounds a lot like how in Session 15 I was using an invertable "zig zag" map \(\mathbb{N} \mathrel{\substack{\longrightarrow \\ \longleftarrow}} \mathbb{N} \times \mathbb{N}\) to iterate through all the possible steps of all the possible generators. In fact, I’d say these so called "equations" here look very similar to the equation for our generator \(d \in X^{\circlearrowright \alpha}\) which corresponded to an equation \(\alpha^2 d = d\) in our presentation.

When I was trying to verify my work in Python, I decided on using a tuple to represent the relations. The equation \(\alpha^2 d = d\) became represented by a generator and iteration pair (('d',2),('d',0)). Maybe that’s what I’m looking at here. Some action \(A\) is applied twice to \(X\) and the result is isomorphic to the sitation where the action isn’t applied at all.

Maybe it might be helpful for me to think of those double arrows as projection maps from Exercise 13. I could potentially think of \(\mathbf{1} \longrightarrow X \mathrel{\substack{\longrightarrow \\ \longrightarrow}} X \longrightarrow \mathbf{1}\) as a short hand for \(\mathbf{1} \longrightarrow X \mathrel{\substack{\longrightarrow \\ \longrightarrow}} B_1 \times B_2 \mathrel{\substack{\longrightarrow \\ \longrightarrow}} X \longrightarrow \mathbf{1}\) Any spliting of \(X\) into \(B_1 \times B_2\) would define three unique maps as follows.

The big difference between then and now is that here I’m splitting my space \(X\) into \(A \times X\) instead of \(B_1 \times B_2\text{.}\) The closest thing I have to "equality" is "isomorphism" and I get one of those for free between any terminal objects. Maybe it might help me to think of the statement in the exercise as defining two isomorphisms:

Since there must be an isomorphism between any pair of terminal objects, there must necessarily be an isomorphism \(X \mathrel{\substack{\longrightarrow \\ \longleftarrow}} A \times A \times X\text{.}\) In fact, the very existence of an object \(A \times A \times X \mathrel{\substack{\longrightarrow \\ \longrightarrow}} X\) implies an equation if I try to enforce the associative law on those maps. I can think of \(A \times A \times X\) as being a map \(A \times A \rightarrow A\) followed by a map \(A \times X \rightarrow X\) or being two evaluations of \(A \times X \rightarrow X\text{.}\) That essentially gives us an "equation" \((A \times A) \times X = A \times (A \times X)\text{.}\)

The other way of expressing this equation is by way of the "preferred" maps \(\xi,\alpha\text{.}\) Given \(A \times X \xrightarrow{\xi} X\) and \(A \times A \xrightarrow{\alpha} A\text{,}\) we can express the associative law above as \(\xi \alpha = \xi^2\text{.}\) At least that gives us something to work with.

As long as we have this preferred element \(\mathbf{1} \xrightarrow{a_0} A\) which "acts as" \(1_X\text{,}\) it has a corresponding map \(\bar{a_0}\) defined by the unique map \(X \longrightarrow \mathbf{1} \xrightarrow{a_0} A\text{.}\) Our preferred action \(\alpha\) then gives rise to an endomap on \(X\text{:}\) \(X \xrightarrow{\langle a_0,1_X \rangle} A \times X \xrightarrow{\alpha} X\text{.}\) This seems like a perfect candidate to define as the object \(X \mathrel{\substack{\longrightarrow \\ \longrightarrow}} X\text{.}\) Better still, \(\langle a_0,1_X \rangle\) defines an easily constructable map to \(A \times A \times X\) when applied twice!

Assuming that \(X \mathrel{\substack{\longrightarrow \\ \longrightarrow}} X\) is a uniquely defined pair of maps, perhaps the pairing of this with \(A \times A \times X \mathrel{\substack{\longrightarrow \\ \longrightarrow}} X\) denotes that these maps are not "the same map", just that there exists an isomorphism between them. Since associative property must apply to the latter, the compositions \(\xi \alpha\) and \(\xi^2\) must ultimately be the same.

A suppose we have a "point" \(\mathbf{1} \xrightarrow{(a,b,x)} A \times A \times X\text{,}\) expressed by the triple \((a,b,x)\text{.}\) With the first composition, we can apply \(A \times A \xrightarrow{\alpha} A\) to get \(\alpha(a,b,x) = (\alpha(a,b),x)\text{,}\) followed by \(A \times X \xrightarrow{\xi} X\) to get \(\xi(\alpha(a,b),x)\) or we can apply \(\xi\) twice to get \(\xi^2(a,b,c) = \xi(a,\xi(b,x))\text{.}\) Knowing \(\xi(\alpha(a,b),x) = \xi(a,\xi(b,x))\) is true for any choice of actions, it must be true for our preferred action \(a_0\text{.}\) Substituting \(a = b = a_0\) gives us \(\xi(a_0,\xi(a_0,x)) = \xi(a_0,x) = x\text{,}\) which establishes that it acts as an identity map.

I feel like there’s a parallel between these maps and role played by the functions (car L) and (cdr L) in LISP. Given a list L of '(a b x), car returns the first element a and cdr returns a list of the rest: '(b,c). The operations played by \(\xi\) and \(\alpha\) let us isolate arbitrary elements in a space \(A^n \times X\text{,}\) just like how LISP would use (car (cdr L)) to access the second element b.