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

By the definition of \(S_1, S_2\) as initial objects, for every object \(X\) of \(\mathcal{C}\) there is exactly one \(\mathcal{C}\)-map \(S_1 \rightarrow X\) and one \(\mathcal{C}\)-map \(S_2 \rightarrow X\text{.}\)

Since \(S_1, S_2\) are both "initial objects" in \(\mathcal{C}\text{,}\) they must also be "objects" in \(\mathcal{C}\text{.}\) By setting \(X = S_1\) or \(X = S_2\text{,}\) it follows that there needs to be exactly one map \(S_1 \rightarrow S_2\) and exactly one map \(S_2 \rightarrow S_1\text{.}\)

Now consider an arbitrary initial object \(S\) in \(\mathcal{C}\text{.}\) By the definition of initial objects, any \(X\) in \(\mathcal{C}\) must have exactly one \(\mathcal{C}\)-map \(S \rightarrow X\text{.}\) Since \(S\) is itself an object in \(\mathcal{C}\text{,}\) it follows that there is precisely one map \(S \rightarrow S\text{.}\) Since there must by an identity map for any domain in the category, it follows that this unique map \(S \rightarrow S\) must necessarily be the identity map \(1_S\text{.}\)

By the same reasoning, any map \(S_1 \rightarrow S_1\) must be the unique map \(1_{S_1}\) and any map \(S_2 \rightarrow S_2\) must be the unique map \(1_{S_2}\text{.}\) Since the composition \(S_1 \rightarrow S_2 \rightarrow S_1\) is a map \(S_1 \rightarrow S_1\text{,}\) it follows that \(S_1 \rightarrow S_2 \rightarrow S_1 = 1_{S_1}\text{.}\) Similarly, the composition formed by \(S_2 \rightarrow S_1 \rightarrow S_2\) is a map \(S_2 \rightarrow S_2\text{.}\) It follows that \(S_2 \rightarrow S_1 \rightarrow S_2 = 1_{S_2}\text{.}\)

Having established that both \(S_1 \rightarrow S_2 \rightarrow S_1 = 1_{S_1}\) and \(S_2 \rightarrow S_1 \rightarrow S_2 = 1_{S_2}\text{,}\) the maps \(S_1 \rightarrow S_2\) and \(S_2 \rightarrow S_1\) are inverses of each other. Consequently, these two maps define an isomorphism between \(S_1\) and \(S_2\text{.}\)

In each of \(\mathcal{S}\text{,}\) \(\mathcal{S}^{\downarrow_\bullet^\bullet \downarrow}\text{,}\) and \(\mathcal{S}^{\circlearrowright}\text{...}\)

We’re given that \(\mathbf{0}\) is an initial object and \(X \xrightarrow{f} \mathbf{0}\) is a map. We’re attempting to show that (a) for every \(X \xrightarrow{g} \mathbf{0}\) we have \(g=f\) and that (b) \(X\) itself is initial.

By defining \(\mathbf{0}\) as an intial object, we know that for any object \(X\) in the category there is exactly one map \(\mathbf{0} \xrightarrow{\phi_X} X\text{.}\) Since \(\mathbf{0}\) is itself an object of the category, there is exactly one map \(\mathbf{0} \xrightarrow{\phi_\mathbf{0}} \mathbf{0}\text{.}\) Furthermore, every domain needs an identity map, so the only possible map \(\phi_\mathbf{0}: \mathbf{0} \rightarrow \mathbf{0}\) we could possibly have is the identity map \(\phi_\mathbf{0} = 1_\mathbf{0}\text{.}\)

Consider the compositions \(f \circ \phi_X\) and \(g \circ \phi_X\text{.}\) In the first case, we have \(\mathbf{0} \xrightarrow{\phi_X} X \xrightarrow{f} \mathbf{0}\) defining a map \(\mathbf{0} \rightarrow \mathbf{0}\text{.}\) Since there is precisely one such map, it must be the unique identity map \(1_\mathbf{0}\text{.}\) Likewise, \(\mathbf{0} \xrightarrow{\phi_X} X \xrightarrow{g} \mathbf{0}\) must also be the same map \(1_\mathbf{0}\text{.}\) It follows that \(f \circ \phi_X = g \circ \phi_X = 1_\mathbf{0}\text{.}\)

If we assume \(f \neq g\text{,}\) then there needs to exist some "point" \(\mathbf{1} \xrightarrow{x} X\) with \(f x \neq g x\text{.}\) However, the property of \(\mathbf{0}\) being an initial object in the category says that we must have exactly one map \(\mathbf{0} \rightarrow \mathbf{1}\text{.}\) It follows from uniqueness of \(\mathbf{0} \rightarrow \mathbf{1}\) that we have a unique composition \(\mathbf{0} \rightarrow \mathbf{1} \xrightarrow{x} X\text{.}\)

In the category \(\mathcal{S}\text{,}\) the "points" of \(X\) are maps which correspond to each element of \(X\) and "point to" themselves. That means that each of the compositions \(\mathbf{0} \rightarrow \mathbf{1} \xrightarrow{x} X \xrightarrow{f} \mathbf{0}\) and \(\mathbf{0} \rightarrow \mathbf{1} \xrightarrow{x} X \xrightarrow{g} \mathbf{0}\) are effectively a map from \(\mathbf{0} \rightarrow \mathbf{0}\text{.}\) Since there can only be exactly one such map \(\mathbf{0} \rightarrow \mathbf{0}\) (the identity map \(\mathbf{1}_\mathbf{0}\) on that single element ), these compositions must be the same map. By precomposing with our maps \(f, g\) we see that \(X \xrightarrow{f} \mathbf{0} \rightarrow \mathbf{1} \xrightarrow{x} X\) and \(X \xrightarrow{g} \mathbf{0} \rightarrow \mathbf{1} \xrightarrow{x} X\) are both effectively the identity map \(1_X\text{.}\) This contradicts our choice of \(f \neq g\text{.}\) The uniqueness of a map \(\mathbf{0} \rightarrow \mathbf{1} \xrightarrow{x} X \xrightarrow{f} \mathbf{0}\) ensures the uniqueness of the composition \(\mathbf{0} \rightarrow \mathbf{1} \xrightarrow{x} X \xrightarrow{1_X} X \xrightarrow{f} \mathbf{0}\text{,}\) making \(X\) an initial object with the sole map \(X \rightarrow X\) being the identity \(1_X\text{.}\)

In the category \(\mathcal{S}^{\circlearrowright}\text{,}\) our "points" are the elements \(X^{\circlearrowright \alpha}\) fixed under the operation \(\alpha\text{.}\) Here a point is a map \(\mathbf{1} \xrightarrow{x} X^{\circlearrowright \alpha}\) such that \(\alpha x = x\text{.}\) In this situation, we also know \(f_D \alpha = \alpha' f_A\) so the following compositions should all result in "the same map":

In the category \(\mathcal{S}^{\downarrow_\bullet^\bullet \downarrow}\text{,}\) we need to preserve source and target relations. Namely, for any point \(\mathbf{1} \xrightarrow{x} X\) we need \(f_D s x = s' f_A x\) amd \(f_D t x = t' f_A x\text{.}\) However, there’s precisely one map from \(0 \rightarrow 1\text{,}\) so \(s'\) and \(t'\) both need to evaluate to the same object. We essentially have an equivalence between the following compositions:

I’m a little uncertain about the rigor of these solutions. Hopefully the follow-up questions will give me more to go on.

In this category, an object is a map \(\mathbf{1} \xrightarrow{x_0} X\) in \(\mathcal{S}\) and a map from \(\mathbf{1} \xrightarrow{x_0} X\) to \(\mathbf{1} \xrightarrow{y_0} Y\) is a map \(X \xrightarrow{f} Y\) in \(\mathcal{S}\) for which \(f x_0 = y_0\text{.}\) We’re given the following external diagram:

We’re asked to show that "any terminal object is also initial" and that "part (b) of the previous exercise is false".

Let’s start by assuming we have some "terminal object" in this category. We’ll call this object \(\mathbf{1}\text{.}\) As a terminal object of \(\mathcal{C}\text{,}\) there is exactly one \(\mathcal{C}\)-map \(X \rightarrow \mathbf{1}\) for any object \(X\) of \(\mathcal{C}\text{.}\)

Our choice of \(\mathcal{C}\) defined an object as a map \(\mathbf{1} \xrightarrow{x_0} X\text{.}\) Our definition of a terminal object implies that there is a unique map I’ll call \(\bar{x_0}\) with the property that satisfies \(\mathbf{1} \xrightarrow{x_0} X \xrightarrow{\bar{x_0}} \mathbf{1} = \mathbf{1}_\mathbf{1}\text{.}\)

Now, what happens if we were to also have an initial object \(\mathbf{0}\) in \(\mathcal{C}\text{?}\) That would imply for that every object \(X\) of \(\mathcal{C}\) we have exactly one \(\mathcal{C}\)-map \(\mathbf{0} \rightarrow X\text{.}\) Since our objects of \(\mathcal{C}\) are limited to maps \(\mathbf{1} \rightarrow X\text{,}\) our object \(\mathbf{0}\) would also need to exist as some map \(\mathbf{1} \xrightarrow{x_0} X\text{.}\) Given how we’ve defined our terminal object, there should be exactly one map \(X \xrightarrow{\bar{x_0}} \mathbf{1}\text{.}\) If we compose this unique map \(\bar{x_0}\) with the unique map \(\mathbf{0} \rightarrow \mathbf{1}\text{,}\) we get a unique map \(0 \rightarrow X \xrightarrow{\bar{x_0}} \mathbf{1}\text{.}\) It follows that any initial object is necessarily a terminal object.

That’s close to what we’ve been asked to prove, but not quite. We were asked to prove every terminal object is initial, and instead proved the converse. I think we might actually need to compose with \(x_0\) once more to show \(0 \rightarrow X \xrightarrow{\bar{x_0}} \mathbf{1} \xrightarrow{x_0} X\) is the same as our unique map \(\mathbf{0} \rightarrow X\text{.}\) Having both a unique map \(\mathbf{0} \rightarrow X\) and a unique map \(X \rightarrow \mathbf{1}\) should be sufficient to show the uniqueness of the map \(\mathbf{0} \rightarrow X \rightarrow \mathbf{1}\text{.}\)

So why does part (b) fail in this case? If \(X\) were itself an initial object, then there would be exactly one map \(X \rightarrow X\text{.}\) Since we need to have an identity map \(1_X\) from \(X \rightarrow X\text{,}\) the unique map \(0 \rightarrow X\) would need to the same as the composition \(0 \rightarrow X \xrightarrow{1_X} X\text{.}\) This is a problem because two maps can only be the same map if the domains and codomains match. The existence of a unique map \(\mathbf{1} \xrightarrow{y_0} Y\text{,}\) separate from our map \(\mathbf{1} \xrightarrow{x_0} X\text{,}\) means that the composition formed by \(0 \rightarrow X \xrightarrow{f} Y\) would be a different map from \(0 \rightarrow X\text{.}\) The lack of uniqueness would disqualify \(X\) as an initial object.

This time we define a category \(\mathbf{2}/\mathcal{S}\) of bipointed objects, with the objects being \(\mathcal{S}\)-maps \(\mathbf{2} \xrightarrow{\bar{x}} X\) and maps being the \(\mathcal{S}\)-maps satistfying \(f \bar{x} = \bar{y}\text{.}\) We’re also given the following diagram:

First, we want to show that the initial object \(\mathbf{0}\) in \(\mathbf{2}/\mathcal{S}\) is actually the identity map \(1_\mathbf{2}\text{.}\) In other words, we need to prove that for any object \(X\) in \(\mathbf{2}/\mathcal{S}\) there is exactly one map from \(1_\mathbf{2} \rightarrow X\text{.}\)

If every object in \(\mathbf{2}/\mathcal{S}\) is some map \(\mathbf{2} \xrightarrow{\bar{x}} X\text{,}\) then consider the composition \(\mathbf{2} \xrightarrow{f \bar{x}} Y\text{.}\) Our category has defined our maps \(f\) as those maps in \(\mathcal{S}\) satisfying the relation \(f \bar{x} = \bar{y}\text{.}\) By assigning \(f = 1_X\) and \(Y = X\text{,}\) it follows that \(1_X \bar{x} = \bar{x}\) which is only true if it holds for every element in the domain \(\mathbf{2}\text{.}\) If that we call the objects of \(\mathbf{2} = \{0,1\}\) then both \(1_X \bar{x} 0 = \bar{x} 0\) and \(1_X \bar{x} 1 = \bar{x} 1\) need to hold true for every \(X\) in \(\mathcal{C}\text{.}\) If \(\mathbf{2}\) is an object in \(\mathcal{C}\text{,}\) that structure preservation must also apply to the map \(f = 1_\mathbf{2}\text{.}\) The relations \(1_\mathbf{2} 0 = 0\) and \(1_\mathbf{2} 1 = 1\) ensure this is a valid map in \(\mathbf{2}/\mathcal{S}\text{.}\)

Maybe what I need to be doing here is establishing an isomorphism between the elements \(0\) and \(1\) with the "null map" and "identity map on objects of \(\mathcal{C}\)". We know there is precisely one \(\mathcal{C}\)-map \(\{\} \xrightarrow{\emptyset} \{\}\) and precisely one from \(X \xrightarrow{1_X} X\text{.}\) If we have a two element-set \(\mathbf{2} = \{0,1\}\text{,}\) then assigning \(0 = \{\} \xrightarrow{\emptyset} \{\}\) and \(1 = X \xrightarrow{1_X} X\) creates an unique isomorphism \(\mathbf{2} \xrightarrow{s} \{\emptyset,1_X\} \xrightarrow{r} \mathbf{2}\) such that \(r \circ s = 1_\mathbf{2}\) and \(s \circ r = 1_{\{\emptyset,1_X\}}\text{.}\)

In the category \(\mathcal{S}\text{,}\) a map \(X \xrightarrow{f} Y\) exists between any sets \(X\) and \(Y\) except in the case where \(Y = \emptyset\) and \(X \neq \emptyset\text{.}\) If we choose \(X = \mathbf{2}\) and \(Y = \emptyset\text{,}\) then we know from the non-existence of a map \(X \xrightarrow{f} Y\) in \(\mathcal{S}\) that we couln’t possibly have one in \(2/\mathcal{S}\text{.}\) In other words, we have a unique map \(\emptyset \rightarrow \emptyset\text{,}\) a unique map \(\emptyset \rightarrow \mathbf{1}\text{,}\) a unique map \(\mathbf{1} \rightarrow \mathbf{1}\text{,}\) and exactly zero maps \(\mathbf{1} \rightarrow \emptyset\text{.}\)

If \(Y\) is a subset of \(X\text{,}\) a map is guaranteed to exist. If we know no map exists, there needs to exist at least one element in \(y_0 = f x_0 \in Y\) that is not in \(X\text{.}\) The set of those two elements \(y_0\) and \(x_0\) need to be isomorphic to the set \(\mathbf{2}\text{.}\)

I think this is relevant because it provides us a way to define an "antipodal" map in \(\mathcal{C}\text{.}\) There is a unique map \(\mathbf{2} \xrightarrow{\alpha} \mathbf{2}\) defined by \(\alpha 0 = 1\) and \(\alpha 1 = 0\text{.}\) Composing \(\alpha \circ s\) swaps the roles of \(\emptyset\) and \(1_X\text{.}\) This mirrors the relationship between \(\forall\) and \(\exists\) statements under logical negation.

Perhaps this provides an answer the second half of the exercise. Knowing that \(\mathbf{0} = 1_\mathbf{2}\text{,}\) the existence of the antipodal map \(\mathbf{2} \xrightarrow{\alpha} \mathbf{2}\) provides a second map to the initial object by way of the composition \(\alpha \circ \alpha = 1_\mathbf{2}\text{.}\)

I keep thinking back to the minimal categories I was playing with in Python last week. In the course of my experimentation, one of the things I tried was defining my objects of my BinaryCategory to be [[0],[1,2]] instead of [[0],[0,1]]. Doing so changes the representation of my "point" maps from

{'domain': [0], 'codomain': [0], 'map': {0: 0}}, {'domain': [0], 'codomain': [0, 1], 'map': {0: 0}}, {'domain': [0], 'codomain': [0, 1], 'map': {0: 1}}]

to

{'domain': [0], 'codomain': [0], 'map': {0: 0}}, {'domain': [0], 'codomain': [1, 2], 'map': {0: 1}}, {'domain': [0], 'codomain': [1, 2], 'map': {0: 2}}]

making it lot clearer what my 3 points "point" to. If I add a "null map" to my category, a map \(\emptyset \xrightarrow{0} \emptyset\) with {'domain': [], 'codomain': [], 'map': {}}, and a unique map \(\emptyset \rightarrow \mathbf{1}\text{,}\) then I can think of my 3 points as being isomorphic to the maps

[{'domain': [], 'codomain': [0], 'map': {}}, {'domain': [], 'codomain': [1], 'map': {}}, {'domain': [], 'codomain': [2], 'map': {}}]

by precomposing my "points" \(\mathbf{1} \rightarrow X\) with that unique map \(\emptyset \rightarrow \mathbf{1}\text{.}\)

I’m not sure where I’m going with this anymore, so lets keep moving forward.

Let start by assuming we have some object \(X\) which is NOT an initial object in \(\mathcal{S}\text{.}\) That means there is either no map \(X \rightarrow X\) or more than one map \(X \rightarrow X\text{.}\) We know that we’re assured to at least have an identity map \(1_X\text{,}\) so we can rule out the first case and focus on the second. Let’s call these maps \(X \xrightarrow{e_i} X\text{,}\) and we know we must at least two such maps \(e_0 \neq e_1\text{.}\)

A terminal object \(S\) in \(\mathcal{S}\) would have the property that for any \(X\) in \(\mathcal{S}\) there is exactly one map \(X \rightarrow S\text{.}\) Clearly \(X \xrightarrow{1_X} X \rightarrow S = X \rightarrow S\text{,}\) so we can assume \(e_0 = 1_X\) is a terminal object. If we also have a second map \(e_1\) such that \(X \xrightarrow{e_1} X \rightarrow S = X \rightarrow S\text{,}\) then we can apply \(e_1\) on the left again:

I think I’m starting to see where we’re going with this. By asserting that \(e_0\) and \(e_1\) are different maps, and knowing that \(e_0\) is the identity map, we know these maps must satisfy \(e_0 e_0 = e_0\text{,}\) \(e_1 e_0 = e_1\text{,}\) \(e_0 e_1 = e_1\text{.}\) But there’s one more combination, and the composition above suggests that \(e_1 e_1 = e_1\text{.}\) Since we proved ealier that all terminal objects are isomorphic, having two distinct maps like this allows us to create an isomorphism between the terminal object \(S\) and each of the maps \(e_0, e_1\) respectively.

We’ve already shown "\(X\) is not initial" implies the existence of two distinct endomaps \(e_0,e_1: X \rightarrow X\) with with isomorphisms between them and the terminal object \(S\text{.}\) Having these isomorphisms \(e_0 \mathrel{\substack{s_0 \\ \longrightarrow \\ \longleftarrow \\ r_0}} S\) and \(e_1 \mathrel{\substack{s_1 \\ \longrightarrow \\ \longleftarrow \\ r_1}} S\) allows us compositions \(e_0 \xrightarrow{r_1 s_0} e_1\) and \(e_1 \xrightarrow{r_0 s_1} e_0\text{.}\) I think we can make the claim that there exists at least "one point" in \(X\) defined by this unique map \(e_1 \rightarrow e_0\text{,}\) which I think is techinically just the map \(e_1\) itself.

We can say \(e_1\) is terminal because \(e_1 e_1 = e_1\text{.}\) We can say \(e_0\) in \(X\) by the identity property of \(\mathcal{C}\text{.}\)

So why would this fail in the categories \(\mathcal{S}^{\circlearrowright}\) or \(\mathcal{S}^{\downarrow_\bullet^\bullet \downarrow}\text{?}\) It probably has something to do with the structure preservation in those categories.

Consider the endomap on the one point set \(\mathbf{1}^{\circlearrowright}\text{.}\) This set technically has two distinct "objects": the point \(\mathbf{1}\) and the map \(\mathbf{1} \rightarrow \mathbf{1}\text{.}\) A "point" in \(X^{\alpha}\) needs to satisfy \(\alpha x = x\text{,}\) which is not true of our map \(e_1\) for all objects by virtue of it being necessarily distinct from the identity map.

For maps in \(\mathcal{S}^{\downarrow_\bullet^\bullet \downarrow}\text{,}\) they need to preserve source and target relations. Namely, preserve \(f_D s = s' f_A\) and \(f_D t = t' f_A\text{.}\) Our terminal objects here are "loops". Maybe can embed our object \(e_1\) by defining \(s = 1_X\) and \(t = e_1\text{.}\) Since we’ve defined \(e_1\) such that \(e_1 e_1 = e_1\text{,}\) this would essentially give us \(e_1 s = e_1 1_X = e_1\) and \(e_1 t = e_1 e_1 = e_1\text{.}\)

I’m picturing the case in \(\mathcal{S}^{\downarrow_\bullet^\bullet \downarrow}\) as needing to preserve the source and target of the endomap on one point. In order to preserve source and target of \(\mathbf{1}^{\circlearrowright}\text{,}\) both the source and target must be the unique point \(\mathbf{1}\text{.}\) However, this space technically has two unique objects. As we "loop" through the point, we alternate between "dot" and "arrow". Since there’s no retraction in \(\mathcal{S}\) from the two point set \(\{\text{dot},\text{arrow}\}\) to the one point set \(\{\text{loop}\}\text{,}\) there couldn’t possibly be an isomorphism with the unique terminal object \(S\text{.}\)