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

So \(A \mathrel{\vcenter{\huge \triangleleft} \!\!\!\! \vcenter{\tiny \rightarrow}} B\) means that there exists some map \(A \xrightarrow{f} B\text{.}\) In the category of sets, we know that the number of possible maps from \(A \longrightarrow B\) is related to the size of the sets by a formula we arrived at in Session 2: \({|B|}^{|A|}\text{.}\) The only time when this expression for number of maps evaluates to 0 is when \(|B| = 0\) and \(|A| > 0\text{.}\)

Another way of looking at this might to consider the contrapositive of this statement. If we know that there does not exist a map from \(A\) to \(B\text{,}\) that means there must be some origin point in \(A\) for the map to act on but no destination point in \(B\) to send it to. Not having a place to send the point to directly implies \(B=\emptyset\text{.}\) If we also had \(A =\emptyset\) then we’d have a "null map", so the non-existance of a map also implies \(A\) must be non-empty.

Let’s start with the reflexive property (R): \(A \leq_R A\text{.}\) This notation indicates that there exist maps \(\set{s,r}\) such that \(A \xrightarrow{s} A \xrightarrow{r} A\) with \(rs = 1_A\text{.}\) Clearly the map \(1_A\) already mets both these conditions since \(1_A \circ 1_A = 1_A\text{.}\)

To prove the transitive property (T), we can construct a retraction for the composition of the functions using a composition of their retractions. If \(A \leq_R B\text{,}\) then there exist maps \(\set{s_1,r_1}\) such that \(A \xrightarrow{s_1} B \xrightarrow{r_1} A\) with \(r_1 \circ s_1 = 1_A\text{.}\) Likewise, \(B \leq_R C\text{,}\) then there exist maps \(\set{s_2,r_2}\) such that \(B \xrightarrow{s_2} C \xrightarrow{r_2} B\) with \(r_2 \circ s_2 = 1_B\text{.}\)

Given these \(\set{s_1,r_1,s_2,r_2}\text{,}\) we can define \(A \xrightarrow{s_3} C = s_2 \circ s_1\) and define \(C \xrightarrow{r_3} A = r_1 \circ r_2\text{.}\) Note that \(r_3 \circ s_3\) can be evaluated as follows using the associative property:

This completes the proof that \(A \leq_R C\text{.}\)

So we’re given that both \(A \mathrel{\substack{s \\[-0.6ex] \textstyle\longrightarrow \\[-0.6ex] \textstyle\longleftarrow \\[-0.6ex] r}} B\) and \(A' \mathrel{\substack{ s' \\[-0.6ex] \textstyle\longrightarrow \\[-0.6ex] \textstyle\longleftarrow \\[-0.6ex] r'}} B\) "split the same idempotent" \(B \xrightarrow{e} B\text{.}\)

The definition of "splitting an idempotent" tells us that \(sr = e = s'r'\) with \(rs = 1_A\) and \(r's' = 1_{A'}\text{.}\) Given these maps, we’re trying to establish a composition that goes from \(A\) to \(A'\) using \(B\) as a step in between. To get from \(A\) to \(B\) we can use map \(s\text{,}\) and then to get from \(B\) to \(A'\) we can use map \(s'\text{.}\)

Let us define \(A \xrightarrow{f} A'\) by \(r' \circ s\text{.}\) This map should be a well-defined isomorphism with the inverse map given by \(f^{-1} = r \circ s'\text{.}\) To prove this, we must show that \(f^{-1} \circ f = 1_A\) and \(f \circ f^{-1} = 1_{A'}\text{.}\)

By the associative property, the first expression can be simplified as follows:

Likewise, the second expression can be similarly simplified:

These two conditions are sufficient to demonstrate that \(f\) is an isomorphism.