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

I know this may be a little regressive of me, but I found it easier to think of this problems in terms of "onto" and "one-to-one". Since I’m looking for a map that "has a section but not a retraction", that effectively means the map is "one-to-one but not onto". My insticts about functions tell me that this occurs when my "output space" is bigger than my "input space".

Consider the sets \(A = \set{a}\) and \(B = \set{b,c}\text{,}\) and define \(A \xrightarrow{f} B\) by the following internal diagram:

To demonstrate that this map has the required properties, let’s start by identifying the retraction \(B \xrightarrow{r} A\text{:}\)

Proving this is a retraction requires that we show \(r \circ f = 1_A\text{.}\) Fortunately this proof is trivial since there’s only one element in \(A\) for us to test. Since \(a\) is the only possible input, the fact that \((r \circ f)(a) = r(f(a)) = r(b) = a\) is sufficient to satisfy the condition \(r \circ f = 1_A\text{.}\) Thus, \(r\) is a retraction of \(f\text{.}\)

Note that this map \(r\) does not function as a section because \((f \circ r) \neq 1_B\text{.}\) This can be easily observed by applying the composition \(f \circ r\) to point \(c\text{:}\) \((f \circ r)(c) = f(r(c)) = f(a) = b \neq c\text{.}\) In order for a map to be a section of \(f\text{,}\) it needs to send point \(c\) to something other than \(b\text{,}\) but there isn’t anywhere else for it to go!

Since we lose an element when mapping from \(B \longrightarrow A\text{,}\) there’s no way to reconstruct it afterwards. It follows that \(f\) cannot possibly have a section \(s\) satisfying \(f \circ s = 1_B\text{.}\) This completes the proof that \(f\) satistfies the desired properties.

Recall that a map \(e\) is "idempotent" if \(e \circ e = e\text{.}\) Thus, we’ll take the maps defined in (a) and (b) and see how they might be simplified after being applied twice.

Let’s start with (a): \(p \circ q\text{.}\) Composing this map with itself gives us \((p \circ q) \circ (p \circ q)\text{,}\) which can be simplified using the associative property:

Having demonstrated that \((p \circ q) \circ (p \circ q) = (p \circ q)\text{,}\) we can safely conlude that the map in part (a) is idempotent.

We can apply the same strategy in (b) with the expression \(q \circ p\text{:}\)

Since \((q \circ p) \circ (q \circ p) = q \circ p\text{,}\) we can conclude that the map in (b) is idempotent as well.

My gut instict tells me \(q' = q \circ p \circ q\) because that’s the simpliest map I can construct that will have the requisite domain and codomain. Let’s check to see if it has the desired properties.

First, we’ll look at (a) by seeing if \(p \circ q' \circ p = p\text{.}\) Using only the associative property, we can simplify the left hand side as follows:

That confirms property (a). We can use a similar method to demonstrate property (b): \(q' \circ p \circ q' = q'\text{.}\)

Thus, our choice of \(q'\) has both of the required properties.

Upon reading this problem, it sounded very similar to one of the situations in the "zoo" from Session 4. Specifically, I was thinking of the map in Exercise 3 Item (c) where \(\mathbb{R} \xrightarrow{f} \mathbb{R}_{\geq 0}\) is given by \(f(x) = x^2\text{.}\) On closer inspection, my notes from that section indicate that this \(f\) had a section but no retraction -- which is the reverse of what I’m looking for here. I played around with item (a) from the zoo for a bit, but I wasn’t quite happy with how the domains and codomains weren’t aligning. This got me thinking about a clue at the end of Session 9. Specifically, the authors mention "Georg Cantor" by name.

With the realization that I could use infinite sets of varying sizes, I decided that I could combine this notion with the ideas behind the set sizes in Problem 1 by making a map from a "countably infinite set" to an "uncountably infinite set". In this situation, I could theoretically use Cantor’s diagonalization argument to prove the non-existance of my section.

I decided to use a "binary representation" map \(\mathbb{Z}^+ \xrightarrow{f} (0,1)\) that takes each positive integer and turns it into a binary representation of a real number between 0 and 1 by prepending "0." to the reversed binary representation of the integer. Like so:

We can construct a map \((0,1) \xrightarrow{g} \mathbb{Z}^+\) that iterates along the digits of the input and sums up the product of that digit with the respective powers of 2. For example, \(g(0.01001)\) could be evaluated as follows:

Assuming we started with some positive integer and applied \(f\) to it, it would be in the table above and this map \(g\) will return the number we started with. Thus we have a well defined retraction becaues \(g \circ f = 1_{\mathbb{Z}^+}\text{.}\) However, Cantor’s diagonal argument suggest that there still exists at least one real number in the interval (0,1) for which there is no inverse. Consider the real number constructed by taking a single "bit" from each line of the table following the diagonal and flipping it while adding trailing zeroes to the right as needed:

By concatenating all these flipped bits together we can constuct a number \(y \in (0,1)\) given by the binary expansion "0.0011..." as defined above. This number doesn’t have a corresponding \(x\) value in the table for \(f\) because it differs from every output by at least one bit. Since \(g(y)\) is undefined, we have \(f \circ g \neq 1_{(0,1)}\text{.}\) The uniqueness of the inverses we proved in Article 2 implies that the section couldn’t be anything other than the retraction \(g\text{,}\) so we must conlude that \(f\) does not have section.