This is technically my second time through this content and I think I made some errors in my original solutions to exercises 2-5. Rather than ignore my mistakes, I’ve made the decision to recreate them here and explain why I think I was wrong afterward. I hope this method will give more insight into my thought process. To prevent accidental spoilers, this will be treated as a "Hidden Exercise 10".
Example2.1.1.Exercise 1:.
"...understand how we got diagrams..."
Solution.
Okay let’s start by recreating diagram (i).
Figure2.1.2.The original associative law diagram (i) from L&S Article 1.
For diagram (iv), we drop set C and connect B directly to D.
Figure2.1.3.Completed associative law diagram (iv) from L&S Article 1.
To get from here to diagram (v), we drop set B and connect A directly to D.
Figure2.1.4.Completed associative law diagram (v) from L&S Article 1.
As expected, this diagram is an exact match of diagram (iii).
Example2.1.5.Exercise 2.
How many different maps \(f\) are there with domain \(A\) and codomain \(B\text{?...}\)
Solution.
So I approached this like I would an algebraic function like \(f(x)=\frac{x^2-1}{x+2}\text{,}\) but instead of feeding in a number I’m feeding in John (\(J\)), Mary (\(M\)) or Sam (\(S\)) and getting out a breakfast order at a diner that only serves eggs (\(e\)) or coffee (\(c\)) and has a 1 item limit per order.
I know that the number of outcomes is going to be the same for each person, so it made sense to focus on one person at a time. I imagined John’s breakfast order, \(f(J)\text{,}\) as having 3 possible outcomes.
John orders eggs: \(f(J)=e\)
John orders coffee: \(f(J)=c\)
John fails to place an order at all: \(f(J)\) is undefined
Likewise, Mary and Sam have the same 3 possible outcomes: {eggs,coffee,undefined}. Since these events are independent of each other, the total number of possible outcomes is \(3 \cdot 3 \cdot 3 = 27\) maps in total.
Example2.1.6.Exercise 3.
Same, but for maps \(A \overset{f}{\longrightarrow} B\)
Solution.
I thought of this function like the "favorite person" map example from the reading. Using John as an example, I imagined 4 possible character roles in a hypothetical Hollywood love triangle:
John is in love with Mary. \(f(J)=M\)
John is in love with Sam. \(f(J)=S\)
John is a narcissist, in love with himself: \(f(J)=J\)
John is a psychopath, incapable of love: \(f(J)\) is undefined
Given an analogous set of 4 outcomes for Mary and Sam, the total number of possible plot outcomes is \(4 \cdot 4 \cdot 4 = 64\text{.}\)
Example2.1.7.Exercise 4.
Same, but for maps \(B \overset{f}{\longrightarrow} A\)
Solution.
I imagined this one as a "mystery breakfast order". I’m the a waiter in a diner delivering one order of eggs and one order of coffee to a table where John, Mary, and Sam are seated. The map \(f\) tells me who ordered a given dish. Like before, I’ll consider one example at a time. There are 4 possible outcomes for the source of the eggs:
John ordered the eggs: \(f(e)=J\)
Mary ordered the eggs: \(f(e)=M\)
Sam ordered the eggs: \(f(e)=S\)
Nobody ordered eggs: \(f(e)\) is undefined
Since there must likewise be 4 sources for the coffee, the total number of possible outcomes is \(4 \cdot 4 = 16\text{.}\)
Example2.1.8.Exercise 5.
Same, but for maps \(B \overset{f}{\longrightarrow} B\)
Solution.
At this point I had observed a pattern and attempted to generalize. Following my reasoning from exercises 2-4, I notice all my answers fit a pattern:
\begin{equation*}
(\text{number of maps}) = (1+(\text{size of codomain}))^\text{size of domain}
\end{equation*}
In exercise 5, the size of the domain and codmain would each be 2. Evaluating the expression above gives us \((1+2)^2=9\) possible maps.
Example2.1.9.Exercise 6.
How many maps \(A \overset{f}{\longrightarrow} A\) satisfy \(f \circ f = f\text{?}\)
Solution.
This is where I started to notice some problems with my previous reasoning. In order for me to talk about the properties of \(f \circ f\text{,}\) it didn’t make sense for \(f\) to be "undefined" for an element in my domain. If I didn’t get something "out", I wouldn’t be able to feed it back in. So instead of considering all \(4^3=64\) possible "love triangles" I identified earlier, I could narrow my search down to a more limited set of \(3^3=27\) maps by excluding the "psychopaths" from my romance movies because they make it impossible to produce a sequel (more on that idea later).
This narrowed my search, but 27 is still too many for me too sort out by hand so I started looking for ways to break it down further. I knew I could satisfy the \(f \circ f = f\) constraint with the identity map because clearly \(1_A \circ 1_A = 1_A\text{.}\) I also know I could satisfy \(f \circ f = f\) with a "constant function" such as the following:
Furthermore, there would need to be a total of 3 such "constant functions" because you’d need one for each of the 3 possible destinations. At that point it seemed clear I was still missing some. If I could construct a function \(f\) with 1 arrow to each point and also a function \(f\) with 3 arrows to a single point, it seemed reasonable to assume there’d be a class of maps with 2 arrows leading to a single point.
Let’s consider the case where that point with two arrows leading in to be "John". One of the arrows leading to John has to be from himself for \(f \circ f (J) = f(J)\) to be true, but the other arrow could originate at either Mary or Sam. Given these two possible maps exist for each person, we’d have \(3 \cdot 2 = 6\) maps of this type.
Putting everything together, some patterns seem to emerge when I listed these out in a table using binomials.
Table2.1.10.
number of fixed points
number of maps
as binomial
1
3
\(\binom{3}{1}\)
2
6
\(\binom{3}{2}\)
3
1
\(\binom{3}{3}\)
Adding up all of these up gives us total of \(3+6+1=10\) possible maps.
Example2.1.11.Exercise 7.
How many maps \(B \overset{g}{\longrightarrow} B\) satisfy \(g \circ g = g\text{?}\)
Solution.
This was made even easier by the pattern I noticed in the previous example. Given that there are only two elements in the domain, there are \(\binom{2}{1}=2\) maps with 1 fixed point and \(\binom{2}{2}=1\) map with 2 fixed points (namely, \(1_A\)) for total of \(2+1=3\text{.}\)
Example2.1.12.Exercise 8.
...\(A \overset{f}{\longrightarrow} B \overset{g}{\longrightarrow} A\) for which \(g \circ f = 1_A\text{?...}\)
Solution.
None? B has fewer choices in it than A, so when f maps from A to B it must destroy at least one of them. The map g would not be able to produce 3 outputs from only 2 inputs, so there’s no possible way for the composition to cover all elements of A.
Example2.1.13.Exercise 9.
...\(B \overset{h}{\longrightarrow} A \overset{k}{\longrightarrow} B\) for which \(k \circ h = 1_B\text{?...}\)
Solution.
I started here by considering a blank diagram that would fit the composition, and start filling it in one point at a time.
Figure2.1.14.Empty diagram for \(B \overset{h}{\longrightarrow} A \overset{k}{\longrightarrow} B\)
Since I know each point has to end up back where it started, the only real "choice" is which of the 3 middle points the path goes through.
Figure2.1.15.Diagram of potential paths for first point in \(B \overset{h}{\longrightarrow} A \overset{k}{\longrightarrow} B\)
Once I fix the first path, the next point only has two possible intermediary points that it can go through.
Figure2.1.16.Diagram of potential paths for second point in \(B \overset{h}{\longrightarrow} A \overset{k}{\longrightarrow} B\)
Given that there were 3 choices for the first path and 2 choices for the second, there’s a total of \(3 \cdot 2 = 6\) paths altogether.
This also makes sense as the binomial \(\binom{3}{2}\text{,}\) because we have 3 possible intermediary points and we need to choose 2 of them.
Example2.1.17.Exercise 10.
[hidden]
Solution.
What first clued me in that my answers to exercises 2-5 might be wrong was the hint about "BOOKKEEPING rules" at the very end of the section. Looking back, it’s seem like my programming background may have clouded my understanding of "map".
I was thinking about a "map" like I would a "function" in a program. In this analogy I had interpreted "domain" as my "input type" and "codomain" as "output type". The flaw in this reasoning is that I was allowing "functions" to "error", which is not true under the definitions of "map" and "domain" that were presented. If the map \(f(J)\) produced something "undefined", it would be inaccurate to include \(J\) in the domain of \(f\) to begin with.
This means that the generalized formula I came up with earlier is "off by 1", and the corrected formula should be as follows:
\begin{equation*}
(\text{number of maps}) = (\text{size of codomain})^\text{size of domain}
\end{equation*}
Under these revised definitions, the answers to excercises 2-5 should be as follows:
Table2.1.18.
Excercise
Size of domain
Size of codomain
Expression
Result
2
3
2
2^3
8
3
3
3
3^3
27
4
2
3
3^2
9
5
2
2
2^2
4
I can see why these definitions simplify the process of talking about "bookkeeping" for the number maps. It’s much easier to count the maps if we limit ourselves to the ones that are well-formed to start with. I’m left wondering if there’s a situation where having an "undefined" output token like I used might be a useful construct, but the costs seem to far outweigh the benefits.
I can also see some programming parallels here between the "switch" statement in C-like languages and the "match" statement in Rust. The Rust compiler goes an extra step to verify that every possible outcome has been handled before even attempting to complile the code you give it. This provides an extra level of assurance that these functions will behave as expected.
