Skip to main content

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

Ryan Ruff

Section 3.4 Session 4: Division of maps: Isomorphisms

While reading this section, I appreciated the fact that "just reverse the arrows" was the official description of isomorphisms on sets. It makes me feel like my answers to Article 2 are at least on the right track. I think my main goal for this week is to better understand what "respects the combining-rules" really means.

Example 3.4.1. Exercise 1.

Finish checking that \(d\) is an isomorphism...
Solution.
Let’s start with \(h \circ d\) first. The composition is applied from right to left, which means we double first then halve.
\begin{equation*} (h \circ d)(x) = h(d(x)) = 0.5(2x) = (0.5 \times 2) x = 1 \times x = x \end{equation*}
Next we check \(d \circ h\text{,}\) where we halve first and double after:
\begin{equation*} (d \circ h)(x) = d(h(x)) = 2(0.5x) = (2 \times 0.5) x = 1 \times x = x \end{equation*}
This proof seems kind of trivial since multiplication on \(\mathbb{R}\) is commutative.

Example 3.4.2. Exercise 2.

Find an isomorphism \((\set{odd,even},+) \overset{f}{\longrightarrow} (\set{positive,negative},\times)\text{...}\)
Solution.
Let’s start by organizing some data. Perhaps a table of each map will reveal some insight into the structure.
Table 3.4.3. Function table for \((\set{odd,even},+)\)
\(+\) even odd
even even odd
odd odd even
Table 3.4.4. Function table for \((\set{positive,negative},\times)\)
\(\times\) positive negative
positive positive negative
negative negative positive
These two tables mirror each other quite nicely, which suggests that ordering of options shown here is probably the correct choice of \(f\text{.}\) Let’s go ahead and define \(f\) as follows:
Figure 3.4.5. Internal diagram of our potential isomorphism \(f\)
In order for us to show that this \(f\) respects the combining rules, we need to verify that \(f(a + b) = f(a) \times f(b)\) for all \(\set{a,b} \in \mathbb{Z}\text{.}\)
Table 3.4.6. Combining rule validation table for \(f\)
For \(a\) even, \(b\) even:
\(f(a + b) = f(a) \times f(b)\)
\(f(even + even) = f(even) \times f(even)\)
\(f(even) = positive \times positive\)
\(positive = positive\)
Confirmed ✓		 For \(a\) odd, \(b\) even:
\(f(a + b) = f(a) \times f(b)\)
\(f(odd + even) = f(odd) \times f(even)\)
\(f(odd) = negative \times positive\)
\(negative = negative\)
Confirmed ✓
For \(a\) even, \(b\) odd:
\(f(a + b) = f(a) \times f(b)\)
\(f(even + odd) = f(even) \times f(odd)\)
\(f(odd) = positive \times negative\)
\(negative = negative\)
Confirmed ✓		 For \(a\) odd, \(b\) odd:
\(f(a + b) = f(a) \times f(b)\)
\(f(odd + odd) = f(odd) \times f(odd)\)
\(f(even) = negative \times negative\)
\(positive = positive\)
Confirmed ✓
Suppose instead we had used the map \(g\) given by the alternative assignment:
Figure 3.4.7. Internal diagram of alternative map choice \(g\)
When \(a\) and \(b\) are both even, \(g(a + b) = g(even + even) = g(even) = negative\) but \(g(a) \times g(b) = negative \times negative = positive\text{.}\) Thus, this map fails to preserve the combining rule \(g(a + b) = g(a) \times g(b)\text{.}\)

Example 3.4.8. Exercise 3.

...Unmask the imposters...
Solution.
Let’s start with (a): \((\mathbb{R},+) \overset{p}{\longrightarrow} (\mathbb{R},+)\) given by \(p(x) = x + 1\text{.}\)
While it seems like "subtract one" would be a reasonable inverse, this is not an isomorphism because it fails to respect the combining-rule \(p(a+b)=p(a)+p(b)\text{.}\) Consider the case where \(a = 1\) and \(b = 2\text{.}\) We have \(p(a)=2\) and \(p(b)=3\) so \(p(a)+p(b)=5\text{.}\) However, this is not the same as \(p(a+b)\text{,}\) which evaluates to \(p(1+2) = p(3) = 4\) instead.
The map in (b) and the map in (c) are both closely related because they share a common definition of \(sq(x) = x^2\text{,}\) but differ in the domain and codomain.
Again there’s an obvious inverse function of "square root", but the domains and codomains are what concern me. Notable about (b) is that it fails to map "onto" the entire codomain, because the \(sq\) map never produces any negative numbers as an output. The map in (c) resolves this by limiting the codomain to non-negative values, but it still fails to "one-to-one" because both 1 and -1 produce an output of 1.
The map in (d) and (e) likewise have similar definitions.
The map defined by the given expression \(m x = -x\) acts as its own inverse: \((m \circ m) (x) = m(m(x)) = m(-x) = -(-x) = x\text{.}\) Where (d) and (e) differ is in the "combining-rule". If we have \(\set{a,b} \in \mathbb{R}\text{,}\) then a little algebra can show that \(m(a+b) = -(a+b) = (-a)+(-b) = m(a)+m(b)\text{.}\) This means that both the identity rules and the combining-rules are satisfied for (d), making it the only genuine isomorphism in the list. The map in (e) fails to uphold the combining rule because \(m(a \times b) \neq m(a) \times m(b)\text{.}\) In the case where \(a = 1\) and \(b = -1\text{,}\) we have \(m(a \times b) = -(1 \times (-1)) = -(-1) = 1\) but \(m(a) \times m(b) = -1 \times 1 = -1\text{.}\)
Finally we have the map (f), which isn’t even a map with the specified domain and codomain because the cube of a negative number is still negative. Had the map been defined with the correct codomain, \((\mathbb{R},\times) \overset{c}{\longrightarrow} (\mathbb{R},\times)\text{,}\) then we’d potentially be able to define an inverse map by using the "cube root" function.
As I was proof reading this session, I noticed a couple small errors in the 3rd exercise. One of these was a misread problem, but the other was a little more subtle. In an effort to get the most out of this as a learning experience, I thought it might be valuable to talk about what I learned from my mistakes.

Example 3.4.9. Meta-Exercise.

As I was proof reading, I noticed an error in Exercise 3 Part (e). It was a simple case of me not reading the question as precisely as needed. I think I was so excited to show (d) was an isomorphism that I didn’t give (e) the amount of skepticism it deserved. I mistakely read the domain as \((\mathbb{R},+)\) instead of \((\mathbb{R},\times)\) which made finding a counter-example trivial relative to the actual problem.
As I was looking over my solution to fix this, I noticed something else kind of odd. My solution began with "Let’s go one at a time" but I had addressed some of the problems in pairs. There’s something that felt natural about approaching them this way, but it also seemed kind of ironic that I had failed to produce a isomorphism between my problems and solutions in a section that was all about matching things up.
All of this started to get my thinking about the solutions to these problems as a map \(\set{a,b,c,d,e,f} \overset{s}{\longrightarrow} \set{isomorphism,non-isomorphism}\text{.}\) Obviously this map is not invertable, but it made me wonder if the "Hints" to this section provided sufficient information about the functions to identify each one. Is there some set of descriptions that would establish a one-to-one relationship with these problems?
Solution.
The first hint tells us that only one of these maps is a "genuine isomorphism", which I concluded was (d). The last hint says that one is "not even a map", which I concluded is (f). The hint that "[s]ome... dont respect the combining rules" explains why I rejected (a) and (e). It also seems natural to ask "does it have a section?" and "does it have a retraction?".
Table 3.4.10. Table of selected map properties for Exercise 3
Item is a map? has a section? has a retraction? respects combining rules?
(a) Yes Yes Yes No
(b) Yes No No N/A
(c) Yes Yes No N/A
(d) Yes Yes Yes Yes
(e) Yes Yes Yes No
(f) No N/A N/A N/A
These four questions are almost enough to identify every problem except for distinguishing between (a) and (e). The best description of the difference is that (a) fails to preserve the combining-rules in every case while (e) might pass or fail the combining-rules depending on its input. This is a very subtle difference that I probably would have overlooked had I not made the mistake that I did.
PrevTopNext