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

To begin, I labeled the set of points with no incoming points as my generators:

Next, I start labeling nodes by following each generator until I reach a point with more than one incoming arrow. This identifies two relations for the presentation.

So my presentation for this endomap is given by the set of generators \(\{a,b,c\}\) with the relations \(\alpha a = \alpha b\) and \(\alpha^2 a = \alpha^2 c\text{.}\)

The interesting thing I notice about this is that knowing that no generator appears twice in any relation. This property seems to imply that the resulting graph is "infinite". It’s also interesting that every point in this graph from \(\alpha^2\) on is the same distance from each of the three generators.

With so much to think about, where do I begin?

I think one of the big ideas that’s been floating in my head is that I can represent any finite endomap as a directed graph and I can construct an adjacency matrix that simulates the behavior of the map. If I take an "eigendecomposition" of the adjacency matrix, it seems like the "eigenvalues" tell me what kinds of "loops" I have.

If I calculate the eigenvalues for the \(X^{\circlearrowright \alpha}\) used in this session using np.linalg.eig, I get the following list of \(\lambda\)s: four copies of \(0\text{,}\) two copies of \(1\text{,}\) one instance of \(-1\) and a pair of complex conjugates \(-0.5 \pm 0.8660254i\text{.}\)

What strikes me as curious about this is that the numbers \(-0.5 \pm 0.8660254i\) are what I would describe as "third roots of unity". The number defined by \(\lambda = \frac{-1+i\sqrt{3}}{2} \approx -0.5 + 0.8660254i\) has a special property that \(\lambda^2 = \frac{-1-i\sqrt{3}}{2} \approx -0.5 - 0.8660254i\) and \(\lambda^3 = 1\text{.}\) Thus, my 3-cycle in the graph corresponds directly to set of 3 eigenvalues: \(\{\frac{-1+i\sqrt{3}}{2},\frac{-1-i\sqrt{3}}{2},1\}\text{.}\)

Likewise, \(-1\) is a "second root of unity" since \((-1)^2 = 1\text{.}\) If my cycle of 2 is corresponds with the set \(\{-1,1\}\text{,}\) the only unaccounted for eigenvalues left are the 4 copies of \(0\text{.}\) It seems natural that the four \(0\) values would correspond to the four generators.

It seems this is too big of a coincidence to be true by accident. It makes me wonder if there is some kind of connection here between the eigenvectors of the adjacency matrix and the relations in its presentation.

Suppose we have two different sequences \(u_1, u_2\) with the properties that \(u_1(n+1) = r(n,u_1(n))\text{,}\) \(u_2(n+1) = r(n,u_2(n))\text{,}\) and \(u_1(0) = u_2(0) = s_0\text{.}\) In order to have \(u_1 \neq u_2\) there would need to exist some \(n \in \mathbb{N}\) such that \(u_1(n) \neq u_2(n)\)

Consider what happens when we evaluate \(u_1(1)\) and \(u_2(1)\text{.}\) Applying our definitions gives us \(u_1(1) = r(0,u_1(0)) = r(0,s_0)\) and \(u_2(1) = r(0,u_2(0)) = r(0,s_0)\text{.}\) Since both expressions are equivalent to \(r(0,s_0)\text{,}\) it follows that \(u_1(1) = u_2(1)\text{.}\)

Having established that \(u_1(0) = u_2(0) \implies u_1(1) = u_2(1)\text{,}\) consider the case where \(u_1(n) = u_2(n)\text{.}\) It follows from our definitions that \(u_1(n+1) = r(n,u_1(n)) = r(n,u_2(n)) = u_1(n+1)\text{.}\) Since \(u_1(n) = u_2(n) \implies u_1(n+1) = u_2(n+1)\text{,}\) it follows from induction that \(u_1(n) = u_2(n)\) for all \(n \in \mathbb{N}\) and contradicts our assumption that they were two different maps.

I’m still not sure I have a satisfactory answer to this, but I’m starting think it’s more closely related to the way we defined "parity" on maps using the existence of a fixed point.

As I was exploring the graphs using the adjacency matrix representation, I found it helpful to use a zeroes_vec of the form \(v_0 = <0,0,...,0>\) and ones_vec of the form of the form \(v_1 = <1,1,...,1>\) to assist in ascertaining the properties of the endomap. What was interesting about these was how it allowed me to easily formulate questions about the behavior of all the points in the map at once.

One of the interesting things I noticed was that if \(A\) was my adjacency matrix, multiplying by \(v_0\) was "commutative" but my multiplying by \(v_1\) was not. More specifically, I found \(A v_0 = v_0\) and \(v_0^{\intercal} A = v_0^{\intercal}\text{,}\) which suggests that \(v_0\) is essentially a "fixed point" when applied on either side. In contrast, \(v_1\) only has this property when multiplied on the right. I found that \(A v_1 = v_1\text{,}\) because each point has exactly one arrow out, but \(v_1^{\intercal} A \neq v_1^{\intercal}\) because some points had more than one arrow leading in.

What’s interesting about this is that \(v_0\) is kind of acting like an idempotent here. Whether we multiple on the left or right, we still get \(v_0\) back again. In contrast, \(v_1\) is fixed on one side but not the other. This got me thinking about somehow using \(v_1\) as a proxy for the "universal quantifier" (\(\forall x \in X)\) and \(v_0\) as a proxy for the "existential quantifier" (\(\exists x \in X)\text{.}\)

Once I discovered which dimensions are different in \(v_1^{\intercal} A \neq v_1^{\intercal}\text{,}\) those were the points that I added to my set of generators. One of the tricky parts was that this doesn’t give a generator for the cycle of 2. In order to give that point a identifier, I’d need to evaluate the expression \(v_1^{\intercal} A^2\text{.}\) I’ll go out on a limb here and suggest that I’d need to examine higher powers of \(A\) to find generators for larger cycles if they didn’t already get identified by a "tail".

In essence, I’m thinking that since we can assign a map from points of \(X\) to \(\{0,1\}\) that classifies points into "fixed" or "not fixed" under the operator \(\alpha^n\) for every \(n \in \mathbb{N}\text{.}\) As long as I enumerate along the "zig zag" pattern, I can check this property for every element of \(X\) to every power of \(\alpha\text{.}\)

Part of being in a category means we need to have an identity map \(1_X\) on \(X\text{.}\) The structure preservation property of \(\mathcal{S}^{\circlearrowright}\) asserts that \(\alpha 1_X = 1_X \alpha\text{.}\) With that in mind, what if I define \(f = \alpha\text{?}\) It would follow that \(Y^{\circlearrowright \beta}\) would really be the "image" of \(X^{\circlearrowright \alpha}\text{.}\) If that map counts as a new map, there’s also the symmetry of the two cycle that could be used to produce another map where the roles of points in the two-cycle have been reversed.

Anything I seem to come up with to explain those missing two maps makes this feel like a "trick question" somehow. Perhaps the answers I’m looking for will be illuminated in a later chapter.