It looks like you're new here. If you want to get involved, click one of these buttons!

- All Categories 2.4K
- Chat 505
- Study Groups 21
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 2
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- Baez ACT 2019: Online Course 339
- Baez ACT 2019: Lectures 79
- Baez ACT 2019: Exercises 149
- Baez ACT 2019: Chat 50
- UCR ACT Seminar 4
- General 75
- Azimuth Code Project 111
- Statistical methods 4
- Drafts 10
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 148
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 718

Options

Last time I introduced natural transformations, and I think it's important to solve a bunch more puzzles to get a feel for what they're like. First I'll remind you of the basic definitions. I'll go through 'em quickly and informally:

**Definition.** A **category** \(\mathcal{C}\) consists of:

a collection of

**objects**anda set of

**morphisms**\(f : x \to y\) from any object \(x\) to any object \(y\),

such that:

a) each pair of morphisms \(f : x \to y\) and \(g: y \to z\) has a **composite** \(g \circ f : x \to z \) and

b) each object \(x\) has a morphism \(1_x : x \to x\) called its **identity**,

for which

i) the **associative law** holds: \(h \circ (g \circ f) = (h \circ g) \circ f\), and

ii) the **left and right unit laws** hold: \(1_y \circ f = f = f \circ 1_x \) for any morphism \(f: x \to y\).

A category looks like this:

**Definition.** Given categories \(\mathcal{C}\) and \(\mathcal{D}\), a **functor** \(F: \mathcal{C} \to \mathcal{D} \) maps

each object \(x\) of \(\mathcal{C}\) to an object \(F(x)\) of \(\mathcal{D}\),

each morphism \(f: x \to y\) in \(\mathcal{C}\) to a morphism \(F(f) : F(x) \to F(y) \) in \(\mathcal{D}\) ,

in such a way that:

a) it preserves composition: \(F(g \circ f) = F(g) \circ F(f) \), and

b) it preserves identities: \(F(1_x) = 1_{F(x)}\).

A functor looks sort of like this, leaving out some detail:

**Definition.** Given categories \(\mathcal{C},\mathcal{D}\) and functors \(F, G: \mathcal{C} \to \mathcal{D}\), a **natural transformation** \(\alpha : F \to G\) is a choice of morphism

$$ \alpha_x : F(x) \to G(x) $$ for each object \(x \in \mathcal{C}\), such that for each morphism \(f : x \to y\) in \(\mathcal{C}\) we have

$$ G(f) \alpha_x = \alpha_y F(f) ,$$
or in other words, this **naturality square** commutes:

A natural transformation looks sort of like this:

You should also review the free category on a graph if you don't remember that.

Okay, now for a bunch of puzzles! If you're good at this stuff, please let beginners do the easy ones.

**Puzzle 129.** Let \(\mathbf{1}\) be the free category on the graph with one node and no edges:

Let \(\mathbf{2}\) be the free category on the graph with two nodes and one edge from the first node to the second:

How many functors are there from \(\mathbf{1}\) to \(\mathbf{2}\), and how many natural transformations are there between all these functors? It may help to draw a graph with functors \(F : \mathbf{1} \to \mathbf{2} \) as nodes and natural transformations between these as edges.

**Puzzle 130.** Let \(\mathbf{3}\) be the free category on this graph:

How many functors are there from \(\mathbf{1}\) to \(\mathbf{3}\), and how many natural transformations are there between all these functors? Again, it may help to draw a graph showing all these functors and natural transformations.

**Puzzle 131.** How many functors are there from \(\mathbf{2}\) to \(\mathbf{3}\), and how many natural transformations are there between all these functors? Again, it may help to draw a graph.

**Puzzle 132.** For any category \(\mathcal{C}\), what's another name for a functor \(F: \mathbf{1} \to \mathcal{C}\)? There's a simple answer using concepts you've already learned in this course.

**Puzzle 133.** For any category \(\mathcal{C}\), what's another name for a functor \(F: \mathbf{2} \to \mathcal{C}\)? Again, there's a simple answer using concepts you've already learned here.

**Puzzle 134.** For any category \(\mathcal{C}\), what's another name for a natural transformation \(\alpha : F \Rightarrow G\) between functors \(F,G: \mathbf{1} \to \mathcal{C}\)? Yet again there's a simple answer using concepts you've learned here.

**Puzzle 135.** For any category \(\mathcal{C}\), classify all functors \(F : \mathcal{C} \to \mathbf{1} \).

**Puzzle 136.** For any natural number \(n\), we can define a category \(\mathbf{n}\) generalizing the categories \(\mathbf{1},\mathbf{2}\) and \(\mathbf{3}\) above: it's the free category on a graph with nodes \(v_1, \dots, v_n\) and edges \(f_i : v_i \to v_{i+1}\) where \(1 \le i < n\). How many functors are there from \(\mathbf{m}\) to \(\mathbf{n}\)?

**Puzzle 137.** How many natural transformations are there between all the functors from \(\mathbf{m}\) to \(\mathbf{n}\)?

I think Puzzle 137 is the hardest; here are two easy ones to help you recover:

**Puzzle 138.** For any category \(\mathcal{C}\), classify all functors \(F : \mathbf{0} \to \mathcal{C}\).

**Puzzle 139.** For any category \(\mathcal{C}\), classify all functors \(F : \mathcal{C} \to \mathbf{0} \).

## Comments

I was thinking... if functions can be described using a table of sets,

\[ \begin{array}{c|c} X & f \\ \hline x_1 & f(x_1) \\ x_2 & f(x_2) \\ x_3 & f(x_3) \\ \vdots & \vdots \end{array} \]

since functors map functions, would functors be described using a table of tables?

\[ \begin{array}{c||c} \mathcal{C} & F \\ \hline \hline \begin{array}{c|c} X & f \\ \hline x_1 & f(x_1) \\ x_2 & f(x_2) \\ x_3 & f(x_3) \\ \vdots & \vdots \end{array} & \begin{array}{c|c} F(X) & F(f) \\ \hline F(x_1) & F(f)(x_1) \\ F(x_2) & F(f)(x_2) \\ F(x_3) & F(f)(x_3)\\ \vdots & \vdots \end{array} \\ \begin{array}{c|c} Y & g \\ \hline y_1 & g(y_1) \\ y_2 & g(y_2) \\ y_3 & g(y_3) \\ \vdots & \vdots \end{array} & \begin{array}{c|c} F(Y) & F(g) \\ \hline F(y_1) & F(g)(y_1) \\ F(y_2) & F(g)(y_2) \\ F(y_3) & F(g)(y_3)\\ \vdots & \vdots \end{array} \\ \vdots & \vdots \end{array} \]

`I was thinking... if functions can be described using a table of sets, \\[ \begin{array}{c|c} X & f \\\\ \hline x_1 & f(x_1) \\\\ x_2 & f(x_2) \\\\ x_3 & f(x_3) \\\\ \vdots & \vdots \end{array} \\] since functors map functions, would functors be described using a table of tables? \\[ \begin{array}{c||c} \mathcal{C} & F \\\\ \hline \hline \begin{array}{c|c} X & f \\\\ \hline x_1 & f(x_1) \\\\ x_2 & f(x_2) \\\\ x_3 & f(x_3) \\\\ \vdots & \vdots \end{array} & \begin{array}{c|c} F(X) & F(f) \\\\ \hline F(x_1) & F(f)(x_1) \\\\ F(x_2) & F(f)(x_2) \\\\ F(x_3) & F(f)(x_3)\\\\ \vdots & \vdots \end{array} \\\\ \begin{array}{c|c} Y & g \\\\ \hline y_1 & g(y_1) \\\\ y_2 & g(y_2) \\\\ y_3 & g(y_3) \\\\ \vdots & \vdots \end{array} & \begin{array}{c|c} F(Y) & F(g) \\\\ \hline F(y_1) & F(g)(y_1) \\\\ F(y_2) & F(g)(y_2) \\\\ F(y_3) & F(g)(y_3)\\\\ \vdots & \vdots \end{array} \\\\ \vdots & \vdots \end{array} \\]`

Puzzle 136.The free categories \(\mathbf{m}, \mathbf{n}\) are total orders, so a functor \(F : \mathbf{m} \to \mathbf{n}\) can be identified with a monotone sequence of length \(m\) on the integer interval \([1, n]\). For instance, one possible functor from \(\mathbf{4}\) to \(\mathbf{3}\) is \(f = 1, 1, 3, 3\). We can denote this by \(1^2 2^0 3^2\), using exponents to show how many times a given value is repeated; this suggests we want to count the number of ways to divide \(\textbf{n}\) indistinguishable objects amongst \(\textbf{m}\) boxes, since there is always a unique monotone function associated with such an assignment.This puts us squarely in the realm of combinatorics, where we can use a technique known as "stars and bars". For the example functor above, if we lay out the output interval \([1, 3]\) as a line of dots \(\bullet \bullet \bullet\), we want to place three bars so as to divide the dots into four clusters (some of which may be empty): \(\bullet \bullet {\mid} {\mid} \bullet {\mid}\). By the stars-and-bars method, there are \(\binom{3 + (4 - 1)}{4 - 1} = \binom{6}{3} = 20\) functors from \(\mathbf{4}\) to \(\mathbf{3}\). In general, there are \(\binom{n + (m - 1)}{m - 1}\) functors from \(\mathbf{m}\) to \(\mathbf{n}\).

In the interest of full disclosure, I tried tackling this through integer partitions first, and then by writing an explicit recursive function for counting these monotone functions. But I kept seeing patterns that weren't well explained by my answer, so I ended up finding the stars and bars technique in a StackExchange answer and going "derp, I remember that now..."

Keith wrote:

Morphisms in a category don't have to be functions. (Think about posets!) An endofunctor from \(\mathbf{Set}\) to \(\mathbf{Set}\) can probably be represented the way you're suggesting, though.

`**Puzzle 136.** The free categories \\(\mathbf{m}, \mathbf{n}\\) are total orders, so a functor \\(F : \mathbf{m} \to \mathbf{n}\\) can be identified with a monotone sequence of length \\(m\\) on the integer interval \\([1, n]\\). For instance, one possible functor from \\(\mathbf{4}\\) to \\(\mathbf{3}\\) is \\(f = 1, 1, 3, 3\\). We can denote this by \\(1^2 2^0 3^2\\), using exponents to show how many times a given value is repeated; this suggests we want to count the number of ways to divide \\(\textbf{n}\\) indistinguishable objects amongst \\(\textbf{m}\\) boxes, since there is always a unique monotone function associated with such an assignment. This puts us squarely in the realm of combinatorics, where we can use a technique known as ["stars and bars"](https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)). For the example functor above, if we lay out the output interval \\([1, 3]\\) as a line of dots \\(\bullet \bullet \bullet\\), we want to place three bars so as to divide the dots into four clusters (some of which may be empty): \\(\bullet \bullet {\mid} {\mid} \bullet {\mid}\\). By the stars-and-bars method, there are \\(\binom{3 + (4 - 1)}{4 - 1} = \binom{6}{3} = 20\\) functors from \\(\mathbf{4}\\) to \\(\mathbf{3}\\). In general, there are \\(\binom{n + (m - 1)}{m - 1}\\) functors from \\(\mathbf{m}\\) to \\(\mathbf{n}\\). In the interest of full disclosure, I tried tackling this through [integer partitions](https://en.wikipedia.org/wiki/Partition_(number_theory)) first, and then by writing an explicit recursive function for counting these monotone functions. But I kept seeing patterns that weren't well explained by my answer, so I ended up finding the stars and bars technique in a [StackExchange answer](https://math.stackexchange.com/questions/1552233/counting-monotonically-increasing-functions) and going "derp, I remember that now..." --- Keith wrote: > since functors map functions Morphisms in a category don't have to be functions. (Think about posets!) An endofunctor from \\(\mathbf{Set}\\) to \\(\mathbf{Set}\\) can probably be represented the way you're suggesting, though.`

Morphisms between posets are called monotone

functions.You're right though that\(\mathbf{Set}\) morphisms need not be functions, they can be any relation of sets, functions are just a particularly well-behaved class of relations.

`>Morphisms in a category don't have to be functions. (Think about posets!) Morphisms between posets are called monotone *functions*. You're right though that\\(\mathbf{Set}\\) morphisms need not be functions, they can be any relation of sets, functions are just a particularly well-behaved class of relations.`

Functors of the form \(F: \mathbf{1} \to \mathcal{C}\) select a particular

objectin \(\mathcal{C}\)Functors of the form \(F: \mathbf{2} \to \mathcal{C}\) select a particular

morphismin \(\mathcal{C}\)`> **Puzzle 132.** For any category \\(\mathcal{C}\\), what's another name for a functor \\(F: \mathbf{1} \to \mathcal{C}\\)? There's a simple answer using concepts you've already learned in this course. Functors of the form \\(F: \mathbf{1} \to \mathcal{C}\\) select a particular *object* in \\(\mathcal{C}\\) > **Puzzle 133.** For any category \\(\mathcal{C}\\), what's another name for a functor \\(F: \mathbf{2} \to \mathcal{C}\\)? Again, there's a simple answer using concepts you've already learned here. Functors of the form \\(F: \mathbf{2} \to \mathcal{C}\\) select a particular *morphism* in \\(\mathcal{C}\\)`

Keith wrote:

Yes, but those are functors over posets, not morphisms

ina poset. You said "functors map functions", but monotone maps don't map functions, they map relationships \(x \le y\) to relationships \(f(x) \le f(y)\).You can talk about the category of

allposets with morphisms as monotone maps, \(\textbf{Pos}\), but that wasn't what I was suggesting as a counterexample. Take any specific poset and consider it as a category; then morphisms in this poset are not functions, so functors out of this poset do not map functions.Morphisms in \(\textbf{Set}\) are precisely functions. We need other categories, like \(\textbf{Rel}\), if we want to talk about more general relations between sets.

`Keith wrote: > Morphisms between posets are called monotone *functions*. Yes, but those are functors over posets, not morphisms _in_ a poset. You said "functors map functions", but monotone maps don't map functions, they map relationships \\(x \le y\\) to relationships \\(f(x) \le f(y)\\). You can talk about the category of _all_ posets with morphisms as monotone maps, \\(\textbf{Pos}\\), but that wasn't what I was suggesting as a counterexample. Take any specific poset and consider it as a category; then morphisms in this poset are not functions, so functors out of this poset do not map functions. > You're right though that \\(\mathbf{Set}\\) morphisms need not be functions Morphisms in \\(\textbf{Set}\\) are precisely functions. We need other categories, like \\(\textbf{Rel}\\), if we want to talk about more general relations between sets.`

A functor from \(\mathbf{1}\) to \(\mathbf{2}\) can map \(v_1\) in \(\mathbf{1}\) to either of \(v_1\) or \(v_2\) in \(\mathbf{2}\). There are no morphisms to be mapped other than the identity morphism in \(\mathbf{1}\), and mapping this to the identity morphism of its target trivially preserves identities and the composition of identities in \(\mathbf{1}\)). This is then a total of 2 functors, call them \(F\) and \(G\).

There is a natural transformation from \(F\) to \(G\) with a single morphism \(\alpha_{v_1} : F(v_1) \to G(v_1)\) ie \(v_1 \to v_2\). Since there is only the identity morphism in \(\mathbf{1}\) the naturality square is squished to be a naturality line, which commutes for reasons so simple I have difficulty explaining.

There is a natural transformation from \(G\) to \(F\) with a single morphism \(\alpha_{v_1} : G(v_1) \to F(v_1)\) ie \(v_2 \to v_1\). The naturality condition again trivially holds.

Finally there are two identity natural transformations, one for \(F\) and one for \(G\).

So the total is: two functors from \(\mathbf{1}\) to \(\mathbf{2}\) and four natural transformations between all these functors (if we include identities).

`> **Puzzle 129.** Let \\(\mathbf{1}\\) be the free category on the graph with one node and no edges: Let \\(\mathbf{2}\\) be the free category on the graph with two nodes and one edge from the first node to the second: How many functors are there from \\(\mathbf{1}\\) to \\(\mathbf{2}\\), and how many natural transformations are there between all these functors? A functor from \\(\mathbf{1}\\) to \\(\mathbf{2}\\) can map \\(v_1\\) in \\(\mathbf{1}\\) to either of \\(v_1\\) or \\(v_2\\) in \\(\mathbf{2}\\). There are no morphisms to be mapped other than the identity morphism in \\(\mathbf{1}\\), and mapping this to the identity morphism of its target trivially preserves identities and the composition of identities in \\(\mathbf{1}\\)). This is then a total of 2 functors, call them \\(F\\) and \\(G\\). There is a natural transformation from \\(F\\) to \\(G\\) with a single morphism \\(\alpha_{v_1} : F(v_1) \to G(v_1)\\) ie \\(v_1 \to v_2\\). Since there is only the identity morphism in \\(\mathbf{1}\\) the naturality square is squished to be a naturality line, which commutes for reasons so simple I have difficulty explaining. There is a natural transformation from \\(G\\) to \\(F\\) with a single morphism \\(\alpha_{v_1} : G(v_1) \to F(v_1)\\) ie \\(v_2 \to v_1\\). The naturality condition again trivially holds. Finally there are two identity natural transformations, one for \\(F\\) and one for \\(G\\). So the total is: two functors from \\(\mathbf{1}\\) to \\(\mathbf{2}\\) and four natural transformations between all these functors (if we include identities).`

Allan wrote:

I'm not sure \(v_2 \to v_1\) is an existing morphism in \(\textbf{2}\). ;)

`Allan wrote: > There is a natural transformation from \\(G\\) to \\(F\\) with a single morphism \\(\alpha_{v_1} : G(v_1) \to F(v_1)\\) ie \\(v_2 \to v_1\\). The naturality condition again trivially holds. I'm not sure \\(v_2 \to v_1\\) is an existing morphism in \\(\textbf{2}\\). ;)`

I'm having some trouble pushing Puzzle 137 through, so I'll post what I've done so far and hope others can take it further.

Puzzle 137.A natural transformation between functors \(F, G : \textbf{m} \to \textbf{n}\) is a selection of morphisms \(\alpha_x : F(x) \to G(x)\) in \(\textbf{n}\) satisfying the naturality condition. But since we're working with total orders, that means \(\alpha_x\) is just the unique relationship \(F(x) \le G(x)\), if it exists. In other words, a natural transformation between \(F\) and \(G\) is thepropertythat \(F \le G\) for all inputs.I suspect a natural setting for considering natural transformations would be the partial order of length \(m\) monotone sequences over \(\textbf{n}\), where \(F \le G\) iff \(F(x) \le G(x)\) for all \(x \in \textbf{n}\). (This is the functor category for our total order.) At the bottom is \(\bot = v_1, v_1, v_1, \cdots, v_1\), and at the top is \(\top = v_n, v_n, v_n, \cdots, v_n\). Observe that if we have \(F \le G\), since we are working with an interval of integers there is a well-defined notion of component-wise subtraction between these monotone sequences. To make the math cleaner, I'm going to translate so that \(v_1 = 0, v_2 = 1\), etc., but this is no more than a more intuitive relabeling.

Notably, \(G - F\) need not be monotone! Consider the toy case where \(F = 0, 0, 2\) and \(G = 0, 2, 2\): their subtraction is \(H = 0, 2, 0\). All that's strictly necessary is that \(F(x) + H(x) \le F(x+1) + H(x+1)\), or \(F(x) + H(x) \le (n - 1)\) when \(x = m\). (At this point, it's fair to observe that \(H\) might as well be the unique witness for the natural transformation between F and G, since \(x \le z\) precisely when there exists a \(y\) such that \(x + y = z\).)

`I'm having some trouble pushing Puzzle 137 through, so I'll post what I've done so far and hope others can take it further. --- **Puzzle 137.** A natural transformation between functors \\(F, G : \textbf{m} \to \textbf{n}\\) is a selection of morphisms \\(\alpha\_x : F(x) \to G(x)\\) in \\(\textbf{n}\\) satisfying the naturality condition. But since we're working with total orders, that means \\(\alpha\_x\\) is just the unique relationship \\(F(x) \le G(x)\\), if it exists. In other words, a natural transformation between \\(F\\) and \\(G\\) is the _property_ that \\(F \le G\\) for all inputs. I suspect a natural setting for considering natural transformations would be the partial order of length \\(m\\) monotone sequences over \\(\textbf{n}\\), where \\(F \le G\\) iff \\(F(x) \le G(x)\\) for all \\(x \in \textbf{n}\\). (This is the [functor category](https://en.wikipedia.org/wiki/Functor_category) for our total order.) At the bottom is \\(\bot = v\_1, v\_1, v\_1, \cdots, v\_1\\), and at the top is \\(\top = v\_n, v\_n, v\_n, \cdots, v\_n\\). Observe that if we have \\(F \le G\\), since we are working with an interval of integers there is a well-defined notion of component-wise subtraction between these monotone sequences. To make the math cleaner, I'm going to translate so that \\(v_1 = 0, v_2 = 1\\), etc., but this is no more than a more intuitive relabeling. Notably, \\(G - F\\) need not be monotone! Consider the toy case where \\(F = 0, 0, 2\\) and \\(G = 0, 2, 2\\): their subtraction is \\(H = 0, 2, 0\\). All that's strictly necessary is that \\(F(x) + H(x) \le F(x+1) + H(x+1)\\), or \\(F(x) + H(x) \le (n - 1)\\) when \\(x = m\\). (At this point, it's fair to observe that \\(H\\) might as well be the unique witness for the natural transformation between F and G, since \\(x \le z\\) precisely when there exists a \\(y\\) such that \\(x + y = z\\).)`

Jonathan wrote:

Monotone functions are \(\mathbf{Bool}\)-functors, not functors (\(\mathbf{Set}\)-functors). \(\mathcal{V}\)-functors are not necessarily functors, much the same way that \(\mathcal{V}\)-categories are not nessesarily categories.

`Jonathan wrote: >Yes, but those are functors over posets, not morphisms _in_ a poset. You said "functors map functions", but monotone maps don't map functions, they map relationships \\(x \le y\\) to relationships \\(f(x) \le f(y)\\). Monotone functions are \\(\mathbf{Bool}\\)-functors, not functors (\\(\mathbf{Set}\\)-functors). \\(\mathcal{V}\\)-functors are not necessarily functors, much the same way that \\(\mathcal{V}\\)-categories are not nessesarily categories.`

Keith, see nLab.

To any preorder \(P\) we can associate a category \(\mathcal{X}\): let \(\mathrm{Ob}(\mathcal{X}) = P\) and \(\mathrm{Hom}_\mathcal{X}(x, y) = \{(x, y) \mid x \le y\}\), with composition \((x, y) \circ (y, z) = (x, z)\). This has identities and composition is associative. Similarly, we can construct a preorder from any category with at most one morphism between two objects: take \(\mathrm{Ob}(\mathcal{X})\) as our base set, and \(\bigcup_{x, y \in \mathrm{Ob}(\mathcal{X})} \{(x, y) \mid f \in \mathrm{Hom}_\mathcal{X}(x, y)\}\) as our order \(\le\). These constructions are inverses.

`Keith, [see nLab](https://ncatlab.org/nlab/show/monotone+function). > As a preordered set is the same thing as a category in which any two parallel morphisms are equal, so a monotone function is simply a functor between such categories. To any preorder \\(P\\) we can associate a category \\(\mathcal{X}\\): let \\(\mathrm{Ob}(\mathcal{X}) = P\\) and \\(\mathrm{Hom}\_\mathcal{X}(x, y) = \\{(x, y) \mid x \le y\\}\\), with composition \\((x, y) \circ (y, z) = (x, z)\\). This has identities and composition is associative. Similarly, we can construct a preorder from any category with at most one morphism between two objects: take \\(\mathrm{Ob}(\mathcal{X})\\) as our base set, and \\(\bigcup\_{x, y \in \mathrm{Ob}(\mathcal{X})} \\{(x, y) \mid f \in \mathrm{Hom}\_\mathcal{X}(x, y)\\}\\) as our order \\(\le\\). These constructions are inverses.`

There are now three functors \(F\), \(G\), and \(H\), one for each of the objects in \(\mathbf{3}\) which can be mapped to from \(v_1\) in \(\mathbf{1}\).

Having only an identity morphism in \(\mathbf{1}\) again helps simplify checking the naturality condition for transformations. We have \(F \Rightarrow G\), \(G \Rightarrow H\) and \(F\Rightarrow H\) by composition. Likewise, \(H\Rightarrow G\), \(G \Rightarrow F\) and \(H\Rightarrow F\).

The totals are: three functors, and six natural transformations (not including identities this time, nine if we do). In my last answer I forgot to check/justify that further composition of natural transformations do not give rise to new ones that would need to be counted: I can see that since there is only one object \(v_1\) in \(\mathbf{1}\) to form the natural transformation on, any transformations arrived at by composition cannot be be new ones, but this doesn't sound like the nicest way of saying it.

`> **Puzzle 130.** Let \\(\mathbf{3}\\) be the free category on this graph: How many functors are there from \\(\mathbf{1}\\) to \\(\mathbf{3}\\), and how many natural transformations are there between all these functors? There are now three functors \\(F\\), \\(G\\), and \\(H\\), one for each of the objects in \\(\mathbf{3}\\) which can be mapped to from \\(v_1\\) in \\(\mathbf{1}\\). Having only an identity morphism in \\(\mathbf{1}\\) again helps simplify checking the naturality condition for transformations. We have \\(F \Rightarrow G\\), \\(G \Rightarrow H\\) and \\(F\Rightarrow H\\) by composition. Likewise, \\(H\Rightarrow G\\), \\(G \Rightarrow F\\) and \\(H\Rightarrow F\\). The totals are: three functors, and six natural transformations (not including identities this time, nine if we do). In my last answer I forgot to check/justify that further composition of natural transformations do not give rise to new ones that would need to be counted: I can see that since there is only one object \\(v_1\\) in \\(\mathbf{1}\\) to form the natural transformation on, any transformations arrived at by composition cannot be be new ones, but this doesn't sound like the nicest way of saying it.`

@Jonathan Castello

Well if you want to get pedantic, a poset is a (0,1)-category, whereas a category is a 1-category.

If you're wondering. a monoidal poset is a 1-tuply (0,1)-category (I don't think the nlab has a page for k-tuply (n,r)cats, yet...)

Edit: Also, my issue is with your loose use of language, not correctness, ie saying a monotone function "is" a functor.

`@Jonathan Castello Well if you want to get pedantic, a poset is a (0,1)-category, whereas a category is a 1-category. If you're wondering. a monoidal poset is a 1-tuply (0,1)-category (I don't think the nlab has a page for k-tuply (n,r)cats, yet...) Edit: Also, my issue is with your loose use of language, not correctness, ie saying a monotone function "is" a functor.`

No, really, it is! I intend to be quite precise with my language. I just showed how a preorder is a category in my previous post; it's a straight step from there to have monotone functions as functors. And the nLab also explains that a category where all parallel morphisms are equal is just a preorder.

If you're concerned that a preorder is also a \(\textbf{Bool}\)-category, there's no reason an object can't be represented in multiple ways. I am fairly certain these two representations can be reconciled by a

change of basebetween monoidal categories \(\textbf{Bool}\) and \(\textbf{Set}\), but we haven't met true monoidal categories yet -- just monoidal preorders. So we don't have the language to formalize it yet.I

stillmaintain that morphisms in categories are not always functions, and hence functors do not always map functions. There is no requirement on what the contents of a hom-set is -- just that the contents have a suitably-defined composition operator with suitably-compatible elements of other homsets. The construction I gave for posets gives an explicit example of such a category.`> Edit: Also, my issue is with your loose use of language, not correctness, ie saying a monotone function "is" a functor. No, really, it is! I intend to be quite precise with my language. I just showed how a preorder is a category in my previous post; it's a straight step from there to have monotone functions as functors. And the nLab also explains that a category where all parallel morphisms are equal is just a preorder. If you're concerned that a preorder is also a \\(\textbf{Bool}\\)-category, there's no reason an object can't be represented in multiple ways. I am fairly certain these two representations can be reconciled by a _change of base_ between monoidal categories \\(\textbf{Bool}\\) and \\(\textbf{Set}\\), but we haven't met true monoidal categories yet -- just monoidal preorders. So we don't have the language to formalize it yet. I _still_ maintain that morphisms in categories are not always functions, and hence functors do not always map functions. There is no requirement on what the contents of a hom-set is -- just that the contents have a suitably-defined composition operator with suitably-compatible elements of other homsets. The construction I gave for posets gives an explicit example of such a category.`

Jonathan said:

That's right...

I am wondering about this...

I found a math exchange discussion regarding the special case of monotone automorphisms in \(F : \mathbf{n} \to \mathbf{n}\) here

They claim the answer in that case is

$$ \binom{2 n - 1}{n} $$ If they are wrong, maybe we should make a fix?

`[Jonathan](https://forum.azimuthproject.org/profile/2316/Jonathan%20Castello) said: > The free categories \\(\mathbf{m}, \mathbf{n}\\) are total orders, so a functor \\(F : \mathbf{m} \to \mathbf{n}\\) can be identified with a monotone sequence of length \\(m\\) on the integer interval \\([1, n]\\) here is always a unique monotone function associated with such an assignment. That's right... > In general, there are \\(\binom{n + (m - 1)}{m - 1}\\) functors from \\(\mathbf{m}\\) to \\(\mathbf{n}\\). I am wondering about this... I found a math exchange discussion regarding the special case of monotone automorphisms in \\(F : \mathbf{n} \to \mathbf{n}\\) [here](https://math.stackexchange.com/a/1916542) They claim the answer in that case is \[ \binom{2 n - 1}{n} \] If they are wrong, maybe we should make a fix?`

Matthew said:

It is! If \(n = m\), then \(n + m - 1 = n + n - 1 = 2n - 1\), so the top checks out; and as it happens, the binomial coefficients have a nice symmetry:

\[\binom{n}{k} = \frac{n!}{k!(n-k)!} = \binom{n}{n - k}\]

So \(\binom{2n - 1}{n} = \binom{2n - 1}{n - 1}\), since \(2n - 1\) is odd. All is in agreement :)

`Matthew said: > They claim the answer in that case is > > \[ \binom{2 n - 1}{n} \] It is! If \\(n = m\\), then \\(n + m - 1 = n + n - 1 = 2n - 1\\), so the top checks out; and as it happens, the binomial coefficients have [a nice symmetry](https://en.wikipedia.org/wiki/Binomial_coefficient#Factorial_formula): \\[\binom{n}{k} = \frac{n!}{k!(n-k)!} = \binom{n}{n - k}\\] So \\(\binom{2n - 1}{n} = \binom{2n - 1}{n - 1}\\), since \\(2n - 1\\) is odd. All is in agreement :)`

Wow thanks for the fast answer on that!

And thanks again for all of your insight on these puzzles.

I have to run, but I was thinking about your ideas for

Puzzle 137:So essentially we just need to count the pairs of \(F \leq G\) for \(\mathbf{m} \to \mathbf{n}\).

Here's an algorithm in Haskell that counts them.

[

Edit: I have revised the above and I feel it is likely correct now]The idea is as we pick the first element in \(\mathbf{n}\) that \(F\) maps to, we are constrained for what the first element in \(\mathbf{n}\) that \(G\) map to and all subsequent choices.

Obviously a closed form solution strongly preferable as this algorithm appears to be exponential at first glance.

`Wow thanks for the fast answer on that! And thanks again for all of your insight on these puzzles. I have to run, but I was thinking about your ideas for **Puzzle 137**: > **Puzzle 137.** A natural transformation between functors \\(F, G : \textbf{m} \to \textbf{n}\\) is a selection of morphisms \\(\alpha\_x : F(x) \to G(x)\\) in \\(\textbf{n}\\) satisfying the naturality condition. But since we're working with total orders, that means \\(\alpha\_x\\) is just the unique relationship \\(F(x) \le G(x)\\), if it exists. In other words, a natural transformation between \\(F\\) and \\(G\\) is the _property_ that \\(F \le G\\) for all inputs. So essentially we just need to count the pairs of \\(F \leq G\\) for \\(\mathbf{m} \to \mathbf{n}\\). Here's an algorithm in Haskell that counts them. <pre> #! /usr/bin/env nix-shell #! nix-shell -p "haskell.packages.ghc822.ghc" -i "cabal exec -- runghc" module Main where countNat :: Int -> Int -> Integer countNat m n = countNat' m n n where countNat' 0 _ _ = 1 countNat' _ _ 0 = 0 countNat' _ 0 _ = 0 countNat' _ 1 _ = 1 countNat' m a b = sum [ countNat' (m - 1) (a - x) (b - y) | x <- [0..(a-1)], y <- [(max 0 (x + b - a))..(b-1)] ] main :: IO () main = (putStrLn . show) $ fmap (countNat 1) [1..5] </pre> [**Edit**: I have revised the above and I feel it is likely correct now] The idea is as we pick the first element in \\(\mathbf{n}\\) that \\(F\\) maps to, we are constrained for what the first element in \\(\mathbf{n}\\) that \\(G\\) map to and all subsequent choices. Obviously a closed form solution strongly preferable as this algorithm appears to be exponential at first glance.`

Jonathan Costello: whoops! Thanks for checking my answer.

`Jonathan Costello: whoops! Thanks for checking my answer.`

Puzzle 137As I was testing my code in #16, I used the special (easy) case:$$ \left\lvert \mathbf{Mor}(\mathbf{n}^\mathbf{1}) \right\rvert = \frac{n(n+1)}{2} $$ These are the triangular numbers.

Now that I have a clumsy algorithm I trust enough, I can use it to compute other series and search for a good closed form.

Looking at \(\mathbf{Mor}(\mathbf{n}^\mathbf{2})\), the program outputs

`1,6,20,50,105`

as \(n\) goes from 1 to 5.These appear to be the 4D pyramidal numbers.

$$ \left\lvert \mathbf{Mor}(\mathbf{n}^\mathbf{2}) \right\rvert = \frac{n^2(n^2-1)}{12} $$ Doing the same for \(\mathbf{Mor}(\mathbf{n}^\mathbf{3})\) yields OEIS A006542.

Reading the citations and cross references on the various OEIS entries suggests the following answer:

$$ \left\lvert \mathbf{Mor}(\mathbf{n}^\mathbf{m}) \right\rvert = \binom{m + n - 1}{n - 1}^2 - \binom{m+n}{n} \binom{m + n - 2}{n - 2} $$

`**Puzzle 137** As I was testing my code in [#16](https://forum.azimuthproject.org/discussion/comment/19388/#Comment_19388), I used the special (easy) case: \[ \left\lvert \mathbf{Mor}(\mathbf{n}^\mathbf{1}) \right\rvert = \frac{n(n+1)}{2} \] These are the [triangular numbers](https://oeis.org/A000217). Now that I have a clumsy algorithm I trust enough, I can use it to compute other series and search for a good closed form. Looking at \\(\mathbf{Mor}(\mathbf{n}^\mathbf{2})\\), the program outputs `1,6,20,50,105` as \\(n\\) goes from 1 to 5. These appear to be the [4D pyramidal numbers](https://oeis.org/A002415). \[ \left\lvert \mathbf{Mor}(\mathbf{n}^\mathbf{2}) \right\rvert = \frac{n^2(n^2-1)}{12} \] Doing the same for \\(\mathbf{Mor}(\mathbf{n}^\mathbf{3})\\) yields [OEIS A006542](https://oeis.org/A006542). Reading the citations and cross references on the various OEIS entries suggests the following answer: \[ \left\lvert \mathbf{Mor}(\mathbf{n}^\mathbf{m}) \right\rvert = \binom{m + n - 1}{n - 1}^2 - \binom{m+n}{n} \binom{m + n - 2}{n - 2} \]`

Since the category \(\mathbf{1} \) is just a one object category with a single identity morphism, \(F: \mathbf{1} \to \mathcal{C}\) must send this object to a single object in \(\mathcal{C}\). In other words, functors \(F: \mathbf{1} \to \mathcal{C}\) are objects of \(\mathcal{C}\).

Since the category \(\mathbf{2} \) is a two object category with a single non-identity morphism, \(F: \mathbf{2} \to \mathcal{C}\) must send this arrow, and it's source and target objects, to a single arrow with mapped source anf target obects in \(\mathcal{C}\). In other words, functors \(F: \mathbf{2} \to \mathcal{C}\) are morphisms of \(\mathcal{C}\).

Since both \(F\) and \(G\) map a single set to a chosen basepoints in \(\mathcal{C}\), so a natural transformation is a map that takes basepoints to basepoints, ie a based map, or point-preserving map.

Such functors map all objects into a single object and maps all morphisms into the identity morphism.

Well, \(\mathbf{0}\) is empty, so a map \(F : \mathbf{0} \to \mathcal{C}\) just "pops" \(\mathcal{C}\) out of nothing. This mind as well be called

creatio ex nihilo,since \(\mathcal{C}\) is created out of nothingness.Such a map is as if \(\mathcal{C}\) just vanishes from existence as if it never existed. If my Latin isn't bad, this would be

destructio in nihilio. Also, what \(\mathcal{C}\)?`>**Puzzle 132.** For any category \\(\mathcal{C}\\), what's another name for a functor \\(F: \mathbf{1} \to \mathcal{C}\\)? There's a simple answer using concepts you've already learned in this course. Since the category \\(\mathbf{1} \\) is just a one object category with a single identity morphism, \\(F: \mathbf{1} \to \mathcal{C}\\) must send this object to a single object in \\(\mathcal{C}\\). In other words, functors \\(F: \mathbf{1} \to \mathcal{C}\\) are objects of \\(\mathcal{C}\\). >**Puzzle 133.** For any category \\(\mathcal{C}\\), what's another name for a functor \\(F: \mathbf{2} \to \mathcal{C}\\)? Again, there's a simple answer using concepts you've already learned here. Since the category \\(\mathbf{2} \\) is a two object category with a single non-identity morphism, \\(F: \mathbf{2} \to \mathcal{C}\\) must send this arrow, and it's source and target objects, to a single arrow with mapped source anf target obects in \\(\mathcal{C}\\). In other words, functors \\(F: \mathbf{2} \to \mathcal{C}\\) are morphisms of \\(\mathcal{C}\\). >**Puzzle 134.** For any category \\(\mathcal{C}\\), what's another name for a natural transformation \\(\alpha : F \Rightarrow G\\) between functors \\(F,G: \mathbf{1} \to \mathcal{C}\\)? Yet again there's a simple answer using concepts you've learned here. Since both \\(F\\) and \\(G\\) map a single set to a chosen basepoints in \\(\mathcal{C}\\), so a natural transformation is a map that takes basepoints to basepoints, ie a based map, or point-preserving map. >**Puzzle 135.** For any category \\(\mathcal{C}\\), what are functors \\(F : \mathcal{C} \to \mathbf{1} \\) like? Such functors map all objects into a single object and maps all morphisms into the identity morphism. >**Puzzle 138.** For any category, what are functors \\(F : \mathbf{0} \to \mathcal{C}\\) like? Well, \\(\mathbf{0}\\) is empty, so a map \\(F : \mathbf{0} \to \mathcal{C}\\) just "pops" \\(\mathcal{C}\\) out of nothing. This mind as well be called *creatio ex nihilo,* since \\(\mathcal{C}\\) is created out of nothingness. >**Puzzle 139.** For any category, what are functors \\(F : \mathcal{C} \to \mathbf{0} \\) like? Such a map is as if \\(\mathcal{C}\\) just vanishes from existence as if it never existed. If my Latin isn't bad, this would be *destructio in nihilio*. Also, what \\(\mathcal{C}\\)?`

In comment 11 the candidates for natural transformation, \(\alpha\), are enumerated.

But, we need to prune some of them away.

In particular \(\alpha\) needs to have a morphism by which it may be realized in

3. Such a morphism is not present in the case of \(H\Rightarrow G\), \(G \Rightarrow F\) and \(H\Rightarrow F\).As an example the commuting square associated with \(G \overset{\alpha}{\Rightarrow} F\) does not exist; a suitable morphism for \( \alpha_3 \) does not exist. \begin{matrix} \textbf{1} && \textbf{3} \\ 1_1 & \overset{G}{\rightarrow } & 2_3 \\ id_1 \downarrow & \Downarrow \alpha & \downarrow \alpha_3 \\ 1_1 &\underset{F}{\rightarrow} & 1_3 \end{matrix}

`> **Puzzle 130.** Let \\(\mathbf{3}\\) be the free category on this graph: How many functors are there from \\(\mathbf{1}\\) to \\(\mathbf{3}\\), and how many natural transformations are there between all these functors? In [comment 11](https://forum.azimuthproject.org/discussion/comment/19381/#Comment_19381) the candidates for natural transformation, \\(\alpha\\), are enumerated. > \\(F \Rightarrow G\\), \\(G \Rightarrow H\\) and \\(F\Rightarrow H\\) by composition. Likewise, \\(H\Rightarrow G\\), \\(G \Rightarrow F\\) and \\(H\Rightarrow F\\). By identity \\(F \Rightarrow F\\), \\(G \Rightarrow G\\) and \\(H \Rightarrow H\\). But, we need to prune some of them away. In particular \\(\alpha\\) needs to have a morphism by which it may be realized in **3**. Such a morphism is not present in the case of \\(H\Rightarrow G\\), \\(G \Rightarrow F\\) and \\(H\Rightarrow F\\). As an example the commuting square associated with \\(G \overset{\alpha}{\Rightarrow} F\\) does not exist; a suitable morphism for \\( \alpha_3 \\) does not exist. \begin{matrix} \textbf{1} && \textbf{3} \\\\ 1_1 & \overset{G}{\rightarrow } & 2_3 \\\\ id_1 \downarrow & \Downarrow \alpha & \downarrow \alpha_3 \\\\ 1_1 &\underset{F}{\rightarrow} & 1_3 \end{matrix}`

re

Puzzle 134I think the answer is simpler: a natural transformation between functors1\(\rightarrow\)Cis just a map inC.`re **Puzzle 134** I think the answer is simpler: a natural transformation between functors **1** \\(\rightarrow\\) **C** is just a map in **C**.`

Frederick wrote:

Just to corroborate, I get the same count.

I also count three identity morphisms, giving me a total of 6 - are we not supposed to be counting those?

`[Frederick wrote:](https://forum.azimuthproject.org/discussion/comment/19393/#Comment_19393) > In [comment 11](https://forum.azimuthproject.org/discussion/comment/19381/#Comment_19381) the candidates for natural transformation, \\(\alpha\\), are enumerated. > > > \\(F \Rightarrow G\\), \\(G \Rightarrow H\\) and \\(F\Rightarrow H\\) by composition. Likewise, \\(H\Rightarrow G\\), \\(G \Rightarrow F\\) and \\(H\Rightarrow F\\). By identity \\(F \Rightarrow F\\), \\(G \Rightarrow G\\) and \\(H \Rightarrow H\\). > > But, we need to prune some of them away. > > In particular the natural transformation needs to have a morphism by which it may be realized in **3**. Such a morphism is not present in the case of \\(H\Rightarrow G\\), \\(G \Rightarrow F\\) and \\(H\Rightarrow F\\). Just to corroborate, I get the same count. I also count three identity morphisms, giving me a total of 6 - are we not supposed to be counting those?`

$$ F \in Obs(\mathcal{C} ) $$

$$ F \in Arr(\mathcal{C} ) $$

`>**Puzzle 132.** For any category \\(\mathcal{C}\\), what's another name for a functor \\(F: \mathbf{1} \to \mathcal{C}\\)? There's a simple answer using concepts you've already learned in this course. \[ F \in Obs(\mathcal{C} ) \] >**Puzzle 133.** For any category \\(\mathcal{C}\\), what's another name for a functor \\(F: \mathbf{2} \to \mathcal{C}\\)? Again, there's a simple answer using concepts you've already learned here. \[ F \in Arr(\mathcal{C} ) \]`

Addendum base on comment 22.

The commuting squares of which \(G \overset{\alpha}{\Rightarrow} G\) is typical do exist. $$ \begin{matrix} \textbf{1} && \textbf{3} \\\\ 1_1 & \overset{G}{\rightarrow } & 2_3 \\\\ id_1 \downarrow & \Downarrow \alpha & \downarrow \alpha_3 \\\\ 1_1 &\underset{G}{\rightarrow} & 2_3 \end{matrix} $$ as well for \(G \overset{\alpha}{\Rightarrow} H\) and its kin $$ \begin{matrix} \textbf{1} && \textbf{3} \\\\ 1_1 & \overset{G}{\rightarrow } & 2_3 \\\\ id_1 \downarrow & \Downarrow \alpha & \downarrow \alpha_3 \\\\ 1_1 &\underset{H}{\rightarrow} & 3_3 \end{matrix} $$ Giving the counts of three functors and six natural transformations (including identities).

`Addendum base on [comment 22](https://forum.azimuthproject.org/discussion/comment/19396/#Comment_19396). The commuting squares of which \\(G \overset{\alpha}{\Rightarrow} G\\) is typical do exist. \[ \begin{matrix} \textbf{1} && \textbf{3} \\\\ 1_1 & \overset{G}{\rightarrow } & 2_3 \\\\ id_1 \downarrow & \Downarrow \alpha & \downarrow \alpha_3 \\\\ 1_1 &\underset{G}{\rightarrow} & 2_3 \end{matrix} \] as well for \\(G \overset{\alpha}{\Rightarrow} H\\) and its kin \[ \begin{matrix} \textbf{1} && \textbf{3} \\\\ 1_1 & \overset{G}{\rightarrow } & 2_3 \\\\ id_1 \downarrow & \Downarrow \alpha & \downarrow \alpha_3 \\\\ 1_1 &\underset{H}{\rightarrow} & 3_3 \end{matrix} \] Giving the counts of three functors and six natural transformations (including identities).`

An assertion that there exists a natural transformation implies that there exists a path between two objects.

$$ \alpha \in Path(\mathcal{C} ) $$

`>**Puzzle 134.** For any category \\(\mathcal{C}\\), what's another name for a natural transformation \\(\alpha : F \Rightarrow G\\) between functors \\(F,G: \mathbf{1} \to \mathcal{C}\\)? Yet again there's a simple answer using concepts you've learned here. An assertion that there exists a natural transformation implies that there exists a path between two objects. \[ \alpha \in Path(\mathcal{C} ) \]`

cocone, colimit, coproduct and join?

`>**Puzzle 135.** For any category \\(\mathcal{C}\\), what are functors \\(F : \mathcal{C} \to \mathbf{1} \\) like? cocone, colimit, coproduct and join?`

Its closer to "ex falso quodlibet" in logic. Because the Functor 0 to C doesn't tell you anything about C.

`Its closer to "ex falso quodlibet" in logic. Because the Functor 0 to C doesn't tell you anything about C.`

Anindya Bhattacharyya wrote:

Are you sure? The category \(\mathbf{1}\) is the same thing as a one element set with one unique identity morphism.

Edit: I want to test something. Since we can hyperlink inline formulas can we hyperlink centered formulas?

\[ \huge \mathbf{1} \\ \begin{array}{c|ccc} Obj(\mathbf{1}) & Arr(\mathbf{1}) \\ \hline \overset{1}\bullet & \overset{1}\bullet \overset{id_{1}}\rightarrow \overset{1}\bullet \\ \end{array} \]

Edit: Oh neat. we can.

`Anindya Bhattacharyya wrote: >re **Puzzle 134** I think the answer is simpler: a natural transformation between functors **1** \\(\rightarrow\\) **C** is just a map in **C**. Are you sure? The [category \\(\mathbf{1}\\)](https://ncatlab.org/nlab/show/terminal+category) is the same thing as a one element set with one unique identity morphism. Edit: I want to test something. Since we can hyperlink inline formulas can we hyperlink centered formulas? [ \\[ \huge \mathbf{1} \\\\ \begin{array}{c|ccc} Obj(\mathbf{1}) & Arr(\mathbf{1}) \\\\ \hline \overset{1}\bullet & \overset{1}\bullet \overset{id\_{1}}\rightarrow \overset{1}\bullet \\\\ \end{array} \\] ](https://ncatlab.org/nlab/show/terminal+category) Edit: Oh neat. we can.`

Keith wrote:

The only morphism in \(\mathbf{1}\) is \({id}_{v_1}\), and the only object is \(v_1\), so a natural transformation is a morphism \(\alpha_{v_1} : F(v_1) \to G(v_1)\) such that \(\alpha_{v_1} \circ {id}_{F(v_1)} = {id}_{G(v_1)} \circ \alpha_{v_1}\) -- which is all of them.

EDIT: Whoa, I did not expect that hyperlinked formula to work. Neat!

`Keith wrote: > Are you sure? The [category \\(\mathbf{1}\\)](https://ncatlab.org/nlab/show/terminal+category) is the same thing as a one element set with one unique identity morphism. The only morphism in \\(\mathbf{1}\\) is \\({id}\_{v\_1}\\), and the only object is \\(v\_1\\), so a natural transformation is a morphism \\(\alpha\_{v\_1} : F(v\_1) \to G(v\_1)\\) such that \\(\alpha\_{v\_1} \circ {id}\_{F(v\_1)} = {id}\_{G(v\_1)} \circ \alpha\_{v\_1}\\) -- which is all of them. EDIT: Whoa, I did not expect that hyperlinked formula to work. Neat!`

Puzzle 131.How many functors are there from \(\mathbf{2}\) to \(\mathbf{3}\), and how many natural transformations are there between all these functors? Again, it may help to draw a graph.There are three functors \(F\), \(F'\), and \(F''\) mapping \(f_1\) in \(\mathbf{2}\) to morphisms of lengths 0, 1 and 2 sending \(v_1\) in \(\mathbf{2}\) to \(v_1\) in \(\mathbf{3}\). Similarly two functors \(G\) and \(G'\) sending \(f_1\) to morphisms of length 0 or 1 starting at \(v_2\). Last a functor \(H\) sending \(f_1\) to the identity on \(v_3\).

So six functors.

I drew a graph of natural transformations between them, and avoiding the urge to invent new backwards morphisms this time, came up with \(F \Rightarrow F' \Rightarrow F''\), and \(G \Rightarrow G' \Rightarrow H\), with further transformations \(F' \Rightarrow G\) and \(F'' \Rightarrow G'\).

The total number of natural transformations will be the count of all paths on this graph:

That's a total of 24 natural transformations between functors from \(\mathbf{2}\) to \(\mathbf{3}\).

`**Puzzle 131.** How many functors are there from \\(\mathbf{2}\\) to \\(\mathbf{3}\\), and how many natural transformations are there between all these functors? Again, it may help to draw a graph. There are three functors \\(F\\), \\(F'\\), and \\(F''\\) mapping \\(f_1\\) in \\(\mathbf{2}\\) to morphisms of lengths 0, 1 and 2 sending \\(v_1\\) in \\(\mathbf{2}\\) to \\(v_1\\) in \\(\mathbf{3}\\). Similarly two functors \\(G\\) and \\(G'\\) sending \\(f_1\\) to morphisms of length 0 or 1 starting at \\(v_2\\). Last a functor \\(H\\) sending \\(f_1\\) to the identity on \\(v_3\\). So six functors. I drew a graph of natural transformations between them, and avoiding the urge to invent new backwards morphisms this time, came up with \\(F \Rightarrow F' \Rightarrow F''\\), and \\(G \Rightarrow G' \Rightarrow H\\), with further transformations \\(F' \Rightarrow G\\) and \\(F'' \Rightarrow G'\\). The total number of natural transformations will be the count of all paths on this graph: - 6 of length 0 (the identity transformations) - 6 of length 1 (the transformation arrows on the graph) - 6 of length 2 (three via F'', three via G) - 4 of length 3 (two via F'', two via G) - 2 of length 4 (one via F'', one via G) That's a total of 24 natural transformations between functors from \\(\mathbf{2}\\) to \\(\mathbf{3}\\).`

@Keith – my thinking is that:

— a

functor1\(\rightarrow\)Cis simply anobjectofC— so a

natural transformationbetween such functors is simply amapbetween such objectsThe most useful intuition here, it seems to me, is that a functor from

BtoCis a "picture ofBinC".And a natural transformation of such functors is a way of "sliding" the first picture onto the second along judiciously chosen

C–morphisms.In the case where

B=1the picture is just a single object, and the slide is just a single map inC.In the case where

B=0the picture is empty. There is always exactly one such empty picture for every categoryC.In the case where

C=1there is exactly one possible picture (collapse everything down to the point).In the case where

C=0there is no "canvas" to draw the picture upon, so there is no picture/functor – unlessBis also0.`@Keith – my thinking is that: — a _functor_ **1** \\(\rightarrow\\) **C** is simply an _object_ of **C** — so a _natural transformation_ between such functors is simply a _map_ between such objects The most useful intuition here, it seems to me, is that a functor from **B** to **C** is a "picture of **B** in **C**". And a natural transformation of such functors is a way of "sliding" the first picture onto the second along judiciously chosen **C**–morphisms. In the case where **B** = **1** the picture is just a single object, and the slide is just a single map in **C**. In the case where **B** = **0** the picture is empty. There is always exactly one such empty picture for every category **C**. In the case where **C** = **1** there is exactly one possible picture (collapse everything down to the point). In the case where **C** = **0** there is no "canvas" to draw the picture upon, so there is no picture/functor – unless **B** is also **0**.`

@ Alan & Jonathan :

Regarding

Puzzle 131:This is at odds with Jonathan's answer. He has a formula:

Jonathan's answer is based off of StackExchange

Based on this formula, there should be 4.

I think Alan is right.

We can fix your formula, Jonathan, by writing instead:

$$ \binom{m + n - 1}{n - 1} \text{ functors from } \mathbf{m} \text{ to } \mathbf{n} $$ This agrees with Alan's count (and my count too, for what its worth).

`@ [Alan](https://forum.azimuthproject.org/discussion/comment/19404/#Comment_19404) & [Jonathan](https://forum.azimuthproject.org/profile/2316/Jonathan%20Castello) : Regarding **Puzzle 131**: > There are three functors \\(F\\), \\(F'\\), and \\(F''\\) mapping \\(f_1\\) in \\(\mathbf{2}\\) to morphisms of lengths 0, 1 and 2 sending \\(v_1\\) in \\(\mathbf{2}\\) to \\(v_1\\) in \\(\mathbf{3}\\). Similarly two functors \\(G\\) and \\(G'\\) sending \\(f_1\\) to morphisms of length 0 or 1 starting at \\(v_2\\). Last a functor \\(H\\) sending \\(f_1\\) to the identity on \\(v_3\\). > > So six functors. This is at odds with Jonathan's answer. He has a formula: > In general, there are \\(\binom{n + (m - 1)}{m - 1}\\) functors from \\(\mathbf{m}\\) to \\(\mathbf{n}\\). Jonathan's answer is based off of [StackExchange](https://math.stackexchange.com/questions/1552233/counting-monotonically-increasing-functions) Based on this formula, there should be 4. I think Alan is right. We can fix your formula, Jonathan, by writing instead: \[ \binom{m + n - 1}{n - 1} \text{ functors from } \mathbf{m} \text{ to } \mathbf{n} \] This agrees with Alan's count (and my count too, for what its worth).`

Yep, you're right. I normally put \(n\) before \(m\), completely against alphabetical order, so I'm not surprised I slipped up when forced to go the opposite way with \(F : \mathbf{m} \to \mathbf{n}\). Thanks for the catch!

Incidentally, we can verify this graphically using the stars and bars method. Notice that stars are input elements, whereas bars separate output elements. So adjacent stars go to the same location in the output space, and each bar increments the "current" output location. Here are all of the functors from \(\textbf{2}\) to \(\textbf{3}\) in this notation: **||, *|*|, *||*, |**|, |*|*, ||**.

`Yep, you're right. I normally put \\(n\\) before \\(m\\), completely against alphabetical order, so I'm not surprised I slipped up when forced to go the opposite way with \\(F : \mathbf{m} \to \mathbf{n}\\). Thanks for the catch! Incidentally, we can verify this graphically using the stars and bars method. Notice that stars are input elements, whereas bars separate output elements. So adjacent stars go to the same location in the output space, and each bar increments the "current" output location. Here are all of the functors from \\(\textbf{2}\\) to \\(\textbf{3}\\) in this notation: \*\*||, \*|\*|, \*||\*, |\*\*|, |\*|\*, ||\*\*.`

@ Allan

I don't count that many.

I only count 20.

Following the shorthand suggested here, we have the following functors in \(\mathbf{3}^\mathbf{2}\):

(I am counting them the same way as you are, just notating them differently.)

As Jonathan noted in #8 each one of these acts like a monotone function.

We need to count how many pairs \(F \) and \(G\) such that \(\forall x. F(x) \leq G(x)\), because those situations correspond to natural transformations.

For each choice of \(F\), here are the choices of \(G\) I could find that work:

6 + 5 + 3 + 3 + 2 + 1 = 20

I tried to provide a general equation for this in #13:

$$ \binom{m + n - 1}{n - 1}^2 - \binom{m+n}{n} \binom{m + n - 2}{n - 2} \text{ natural transformations from } \mathbf{m} \text{ to } \mathbf{n} $$

`@ [Allan](https://forum.azimuthproject.org/discussion/comment/19404/#Comment_19404) > That's a total of 24 natural transformations between functors from \\(\mathbf{2}\\) to \\(\mathbf{3}\\). I don't count that many. I only count 20. Following the shorthand suggested [here](https://math.stackexchange.com/a/1552568), we have the following functors in \\(\mathbf{3}^\mathbf{2}\\): - 200 - 110 - 101 - 020 - 011 - 002 (I am counting them the same way as you are, just notating them differently.) As Jonathan noted in [#8](https://forum.azimuthproject.org/discussion/comment/19378/#Comment_19378) each one of these acts like a monotone function. We need to count how many pairs \\(F \\) and \\(G\\) such that \\(\forall x. F(x) \leq G(x)\\), because those situations correspond to natural transformations. For each choice of \\(F\\), here are the choices of \\(G\\) I could find that work: - \\(F = 200\\): {200, 110, 101, 020, 011, 002} - \\(F = 110\\): {110, 101, 020, 011, 002} - \\(F = 101\\): {101, 011, 002} - \\(F = 020\\): {020, 011, 002} - \\(F = 011\\): {011, 002} - \\(F = 002\\): {002} 6 + 5 + 3 + 3 + 2 + 1 = 20 I tried to provide a general equation for this in [#13](https://forum.azimuthproject.org/discussion/comment/19390/#Comment_19390): \[ \binom{m + n - 1}{n - 1}^2 - \binom{m+n}{n} \binom{m + n - 2}{n - 2} \text{ natural transformations from } \mathbf{m} \text{ to } \mathbf{n} \]`

I wanted to see where the overcount in comment 13 came from.

Which is correct? Are these overcounts? Or are they distinct natural transformations?

When composing natural transformations do they always commute?

Edit: 'commute' is ambiguous here. It means "produce a commuting square" or does composition of natural transformations produce a natural transformation? The answer is, as Robert says, yes!

The details for this are covered in the subsequent lecture.

This is different than commuting of composition.

`> **Puzzle 131.** ... Again, it may help to draw a graph. I wanted to see where the overcount in [comment 13](https://forum.azimuthproject.org/discussion/comment/19404/#Comment_19404) came from. ![diagram](https://docs.google.com/drawings/d/e/2PACX-1vSux2Gbr40h292IpzbIXWFHmpqctSTatIMKNvtJi6DHw-vsFKv5tBGjHmfjsJw5EDstfNAZG59zMmR4/pub?w=384&h=239) - 6:6 of length 0 (the identity transformations) - 6:6 of length 1 [black] (the transformation arrows on the graph) - 5:6 of length 2 [blue] (three via F'', three via G) one commuting pair i.e. F'->G->G' = F'->F"->G' - 2:4 of length 3 [red] (two via F'', two via G) two commuting pairs e.g. F->F'->G->G' = F->F'->F"->G' - 1:2 of length 4 [green] (one via F'', one via G) these commute Which is correct? Are these overcounts? Or are they distinct natural transformations? When composing natural transformations do they always commute? Edit: 'commute' is ambiguous here. It means "produce a commuting square" or [does composition of natural transformations produce a natural transformation](https://forum.azimuthproject.org/discussion/2249/lecture-45-chapter-3-composing-natural-transformations/p1)? The answer is, as Robert says, yes! The details for this are [covered in the subsequent lecture](https://forum.azimuthproject.org/discussion/2249/lecture-45-chapter-3-composing-natural-transformations/p1). This is different than [commuting of composition](https://forum.azimuthproject.org/discussion/comment/19478/#Comment_19478).`

Jonathan, Matthew, and Fredrick: thank you for all the insight. And thanks esp Frederick for unifying my scrappy notation with that of the MO answer,

andwith colorsI can see now that all the various squares and triangles in the graph do have some commuting natural transformations. Here it is worked out for \( F' \Rightarrow F'' \Rightarrow G' \) commuting with \( F' \Rightarrow G \Rightarrow G' \)

And so using up all the identity laws:

showing that they are indeed the same natural transformation, and that the square does commute.

`Jonathan, Matthew, and Fredrick: thank you for all the insight. And thanks esp Frederick for unifying my scrappy notation with that of the [MO answer](https://math.stackexchange.com/a/1552568), **and** with colors I can see now that all the various squares and triangles in the graph do have some commuting natural transformations. Here it is worked out for \\( F' \Rightarrow F'' \Rightarrow G' \\) commuting with \\( F' \Rightarrow G \Rightarrow G' \\) - for \\( \alpha : F' \Rightarrow F'' \\) we have \\(\alpha_{v_1} = 1_{v_1}\\) and \\(\alpha_{v_2} = f_2 \\) - for \\( \beta: F'' \Rightarrow G' \\) we have \\( \beta_{v_1} = f_1 \\) and \\( \beta_{v_2} = 1_{v_3} \\) - for \\( \alpha^\prime : F' \Rightarrow G \\) we have \\( \alpha^\prime_{v_1} = f_1 \\) and \\( \alpha^\prime_{v_2} = 1_{v_2} \\) - for \\( \beta^\prime : G \Rightarrow G' \\) we have \\( \beta^\prime_{v_1} = 1_{v_2} \\) and \\( \beta^\prime_{v_2} = f_2 \\) And so using up all the identity laws: - \\( ( \beta\circ\alpha)_{v_1} = f_1\\) - \\( ( \beta\circ\alpha)_{v_2} = f_2\\), but also - \\( ( \beta'\circ\alpha')_{v_1} = f_1\\), and - \\( ( \beta'\circ\alpha')_{v_2} = f_2 \\) showing that they are indeed the same natural transformation, and that the square does commute.`

Fredrick Eisele asked:

Yes, associativity means exactly that composition of natural transformations always commutes!

Nice graphs, btw!

`Fredrick Eisele asked: > When composing natural transformations do they always commute? Yes, associativity means exactly that composition of natural transformations always commutes! Nice graphs, btw!`

Consider a slightly modified problem where

3contains an additional free morphism.In this case there are two distinct natural transformations \(\alpha, \beta : F \rightarrow H\) where \(\alpha_3 = c \circ a, \beta_3 = c \circ b \).

It first seemed to me that if the composition of natural transformations necessarily produces natural transformations (commuting squares) then the Hasse diagram of natural transformations must be a preorder. This example shows that it is not quite that simple, as this produces more than one morphism between two objects.

`Consider a slightly modified problem where **3** contains an additional free morphism. ![example](https://docs.google.com/drawings/d/e/2PACX-1vSBgDdMV108-fg1OIfOPZt3C2Ba6RAR__n6zMYLqGZlvY-0pZnhbVwnb3GGVhZWn-cOvq35882gZupw/pub?w=181&h=142) In this case there are two distinct natural transformations \\(\alpha, \beta : F \rightarrow H\\) where \\(\alpha_3 = c \circ a, \beta_3 = c \circ b \\). It first seemed to me that if the composition of natural transformations necessarily produces natural transformations (commuting squares) then the Hasse diagram of natural transformations must be a preorder. This example shows that it is not quite that simple, as this produces more than one morphism between two objects.`

Let me try a puzzle.

It's easiest, at least for me, to 'cheat' and think more generally. It may be easier for other people to do special cases that lead up to this more general puzzle:

But I want to grab the bull by the horns.

Functors \(F: \mathbf{1} \to \mathcal{C}\) correspond toobjectsof \(\mathcal{C}\).Why?

For any category \(\mathcal{C}\) a functor \(F: \mathbf{1} \to \mathcal{C}\) is determined by the object \(x = F(v_1)\), since we must then have

$$ F(1_{v_1}) = 1_{F(v_1)} = 1_x $$ and once we know what \(F\) does to the only object \(v_1\) of \(\mathbf{1}\) and the only morphism \(1_{v_1}\) of \(\mathbf{1}\), we know \(F\) completely!

Moreover for any object \(x\) of \(\mathcal{C}\) we can define \(F(v_1) = x\) and \(F(1_v) = 1_x\) and check that this is indeed a functor.

This other general puzzle will also help:

Natural transformations \(\alpha : F \Rightarrow G\) between functors \(F,G: \mathbf{1} \to \mathcal{C}\) correspond tomorphismsof \(\mathcal{C}\).The reason is that a natural transformation \(\alpha : F \Rightarrow G\) simply picks out a morphism \(\alpha_{v_1} : F(v_1) \to F(v_2) \). Any morphism will do: the naturality condition is automatic, because \(\mathbf{1}\) has just one morphism in it, which is the identity \(1_{v_1}\), so naturality says that

\[ \alpha_{v_1} F(1_{v_1}) = G(1_{v_1}) \alpha_{v_1}, \]

which is true. (Ask if you have trouble checking this equation!)

So, back to Puzzle 129:

We see there are 2 functors from \(\mathbf{1}\) to \(\mathbf{2}\), one for each

objectof \(\mathbf{2}\), and 3 natural transformations between such functors, one for eachmorphismof \(\mathbf{3}\).`Let me try a puzzle. > **Puzzle 129.** Let \\(\mathbf{1}\\) be the free category on the graph with one node and no edges: > <center><img src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/category_1.png"></center> > Let \\(\mathbf{2}\\) be the free category on the graph with two nodes and one edge from the first node to the second: > <center><img src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/category_2.png"></center> > How many functors are there from \\(\mathbf{1}\\) to \\(\mathbf{2}\\), and how many natural transformations are there between all these functors? It's easiest, at least for me, to 'cheat' and think more generally. It may be easier for other people to do special cases that lead up to this more general puzzle: > **Puzzle 132.** For any category \\(\mathcal{C}\\), what's another name for a functor \\(F: \mathbf{1} \to \mathcal{C}\\)? There's a simple answer using concepts you've already learned in this course. But I want to grab the bull by the horns. **Functors \\(F: \mathbf{1} \to \mathcal{C}\\) correspond to _objects_ of \\(\mathcal{C}\\).** Why? For any category \\(\mathcal{C}\\) a functor \\(F: \mathbf{1} \to \mathcal{C}\\) is determined by the object \\(x = F(v_1)\\), since we must then have \[ F(1_{v_1}) = 1_{F(v_1)} = 1_x \] and once we know what \\(F\\) does to the only object \\(v_1\\) of \\(\mathbf{1}\\) and the only morphism \\(1_{v_1}\\) of \\(\mathbf{1}\\), we know \\(F\\) completely! Moreover for any object \\(x\\) of \\(\mathcal{C}\\) we can define \\(F(v_1) = x\\) and \\(F(1_v) = 1_x\\) and check that this is indeed a functor. This other general puzzle will also help: > **Puzzle 134.** For any category \\(\mathcal{C}\\), what's another name for a natural transformation \\(\alpha : F \Rightarrow G\\) between functors \\(F,G: \mathbf{1} \to \mathcal{C}\\)? Yet again there's a simple answer using concepts you've learned here. **Natural transformations \\(\alpha : F \Rightarrow G\\) between functors \\(F,G: \mathbf{1} \to \mathcal{C}\\) correspond to _morphisms_ of \\(\mathcal{C}\\).** The reason is that a natural transformation \\(\alpha : F \Rightarrow G\\) simply picks out a morphism \\(\alpha_{v_1} : F(v_1) \to F(v_2) \\). Any morphism will do: the naturality condition is automatic, because \\(\mathbf{1}\\) has just one morphism in it, which is the identity \\(1_{v_1}\\), so naturality says that \\[ \alpha_{v_1} F(1_{v_1}) = G(1_{v_1}) \alpha_{v_1}, \\] which is true. (Ask if you have trouble checking this equation!) So, back to Puzzle 129: > **Puzzle 129.** How many functors are there from \\(\mathbf{1}\\) to \\(\mathbf{2}\\), and how many natural transformations are there between all these functors? We see there are 2 functors from \\(\mathbf{1}\\) to \\(\mathbf{2}\\), one for each _object_ of \\(\mathbf{2}\\), and 3 natural transformations between such functors, one for each _morphism_ of \\(\mathbf{3}\\).`

By the way, Matthew: you keep spelling Jonathan's name "Jonathon", and he keeps not mentioning this, and I keep correcting it.

`By the way, Matthew: you keep spelling Jonathan's name "Jonathon", and he keeps not mentioning this, and I keep correcting it.`

Fredrick Eisele asked:

Robert Figura replied:

Oh? I have the feeling that I'm missing the real meaning of this exchange, since I didn't carefully read the context. But in my role as teacher I feel I must say this:

Composition of natural transformations is associative: given natural transformations \(\alpha,\beta,\gamma\) between functors from some category \(\mathcal{C}\) to some category \(\mathcal{D}\) we always have

$$ \alpha \circ (\beta \circ \gamma) = (\alpha \circ \beta) \circ \gamma $$ whenever either side (hence both) is well-defined. But natural transformation do not always commute: we may have

$$ \alpha \circ \beta \ne \beta \circ \alpha $$ even when both sides are well-defined!

The reason is that composition of morphisms in \(\mathcal{D}\) is associative but not necessarily commutative.

`Fredrick Eisele asked: > When composing natural transformations do they always commute? Robert Figura replied: > Yes, associativity means exactly that composition of natural transformations always commutes! Oh? I have the feeling that I'm missing the real meaning of this exchange, since I didn't carefully read the context. But in my role as teacher I feel I must say this: Composition of natural transformations is associative: given natural transformations \\(\alpha,\beta,\gamma\\) between functors from some category \\(\mathcal{C}\\) to some category \\(\mathcal{D}\\) we always have \[ \alpha \circ (\beta \circ \gamma) = (\alpha \circ \beta) \circ \gamma \] whenever either side (hence both) is well-defined. But natural transformation do not always commute: we may have \[ \alpha \circ \beta \ne \beta \circ \alpha \] even when both sides are well-defined! The reason is that composition of morphisms in \\(\mathcal{D}\\) is associative but not necessarily commutative.`

I wrote:

Fredrick wrote:

When I asked what these functors are "like" I did't mean "what do they remind you of?" I meant

"classify all such functors!"But the classification is so simple that I didn't want to say "classify all such functors", since that makes the task sound harder and more intimidating than it is.

Anyway, what are all the functors \(F : \mathcal{C} \to \mathbf{1} \)?

`I wrote: >**Puzzle 135.** For any category \\(\mathcal{C}\\), what are functors \\(F : \mathcal{C} \to \mathbf{1} \\) like? Fredrick wrote: > cocone, colimit, coproduct and join? When I asked what these functors are "like" I did't mean "what do they remind you of?" I meant _"classify all such functors!"_ But the classification is so simple that I didn't want to say "classify all such functors", since that makes the task sound harder and more intimidating than it is. Anyway, what are all the functors \\(F : \mathcal{C} \to \mathbf{1} \\)?`

Keith wrote:

Right. So, how many functors \(F : \mathcal{C} \to \mathbf{1} \) are there?

Maybe I should stop asking questions of the form "what are \(X\) like?" When I ask such questions, I'm not asking for poetic descriptions of what \(X\) feels like. I'm asking for a classification. These questions are a bit open-ended, because what counts as a suitable classification may vary. But there's a more or less unique right answer.

For example, if I asked "what are odd perfect numbers like?" I'd be looking for the answer "they're numbers of the form \(2^{p−1}(2^p − 1)\) where \(2^p - 1\) is prime". If I asked "what are abelian groups of prime order \(p\) like?" I'd be looking for the answer "they're all isomorphic to cyclic groups \(\mathbb{Z}/p\)."

So, here I'm asking for a classification of all functors \(F: \mathbf{0} \to \mathcal{C}\). Luckily, this question is a lot easier than the other two I just mentioned!

Any old \(\mathcal{C}\). There's a classification of all functors \(F : \mathcal{C} \to \mathbf{0} \), which depends on \(\mathcal{C}\), but in a simple way.

`Keith wrote: > >**Puzzle 135.** For any category \\(\mathcal{C}\\), what are functors \\(F : \mathcal{C} \to \mathbf{1} \\) like? > Such functors map all objects into a single object and maps all morphisms into the identity morphism. Right. So, how many functors \\(F : \mathcal{C} \to \mathbf{1} \\) are there? > > **Puzzle 138.** For any category, what are functors \\(F : \mathbf{0} \to \mathcal{C}\\) like? > Well, \\(\mathbf{0}\\) is empty, so a map \\(F : \mathbf{0} \to \mathcal{C}\\) just "pops" \\(\mathcal{C}\\) out of nothing. This mind as well be called *creatio ex nihilo,* since \\(\mathcal{C}\\) is created out of nothingness. Maybe I should stop asking questions of the form "what are \\(X\\) like?" When I ask such questions, I'm not asking for poetic descriptions of what \\(X\\) feels like. I'm asking for a classification. These questions are a bit open-ended, because what counts as a suitable classification may vary. But there's a more or less unique right answer. For example, if I asked "what are odd perfect numbers like?" I'd be looking for the answer "they're numbers of the form \\(2^{p−1}(2^p − 1)\\) where \\(2^p - 1\\) is prime". If I asked "what are abelian groups of prime order \\(p\\) like?" I'd be looking for the answer "they're all isomorphic to cyclic groups \\(\mathbb{Z}/p\\)." So, here I'm asking for a classification of all functors \\(F: \mathbf{0} \to \mathcal{C}\\). Luckily, this question is a lot easier than the other two I just mentioned! >**Puzzle 139.** For any category, what are functors \\(F : \mathcal{C} \to \mathbf{0} \\) like? > Such a map is as if \\(\mathcal{C}\\) just vanishes from existence as if it never existed. If my Latin isn't bad, this would be *destructio in nihilio*. Also, what \\(\mathcal{C}\\)? Any old \\(\mathcal{C}\\). There's a classification of all functors \\(F : \mathcal{C} \to \mathbf{0} \\), which depends on \\(\mathcal{C}\\), but in a simple way.`

Anindya wrote:

Right!

By the way, I'd say 'morphism' instead of 'map', because I'm trying to crush any delusion people may have that morphisms in a general category \(\mathcal{C}\) are maps between sets. You don't seem to be suffering from that delusion! Sometimes in a relaxed mood we can call any morphism a 'map'. But I have to set a good example, so I'll keep saying 'morphism'. Another good neutral term is 'arrow'.

Right!

Right! Where "judiciously chosen" means "natural": that is, making all naturality squares commute. Otherwise we'd just have a transformation.

Right. So a functor from \(\mathcal{1}\) to any category \(\mathcal{C}\) is just an object of \(\mathcal{C}\), and a natural transformation between such functors is just a morphism in \(\mathcal{C}\).

Puzzle.How can can we say that last sentence, and more, in a single equation? We are saying that something is the same as something else. We've learned enough in this class by now to say it very tersely and precisely.Right! So you've quietly answered this puzzle, which I'm now stating more formally:

And the answer is:

there is always exactly one, since there are no objects nor morphisms in \(\mathbf{0}\).Right! Now you've answered this puzzle:

And the answer is:

this always exactly one, since such a functor must map all the objects of \(\mathcal{B}\) to the one object of \(\mathbf{1}\), and all morphisms of \(\mathcal{B}\) to the one morphism of \(\mathbf{1}\).Right! You've provided all the insights needed for a precise answer to this puzzle:

I'll let someone else state the precise answer, though!

`Anindya wrote: > a _functor_ \\(\mathbf{1} \to \mathcal{C}\\) is simply an _object_ of \\(\mathcal{C}\\). > so a _natural transformation_ between such functors is simply a _map_ between such objects. Right! By the way, I'd say 'morphism' instead of 'map', because I'm trying to crush any delusion people may have that morphisms in a general category \\(\mathcal{C}\\) are maps between sets. You don't seem to be suffering from that delusion! Sometimes in a relaxed mood we can call any morphism a 'map'. But I have to set a good example, so I'll keep saying 'morphism'. Another good neutral term is 'arrow'. > The most useful intuition here, it seems to me, is that a functor from \\(\mathcal{B}\\) to \\(\mathcal{C}\\) is a "picture of \\(\mathcal{B}\\) in \\(\mathcal{C}\\)". Right! > And a natural transformation of such functors is a way of "sliding" the first picture onto the second along judiciously chosen \\(\mathcal{C}\\)–morphisms. Right! Where "judiciously chosen" means "natural": that is, making all naturality squares commute. Otherwise we'd just have a transformation. > In the case where \\(\mathcal{B} = \mathbf{1}\\) the picture is just a single object, and the slide is just a single map in \\(\mathcal{C}\\). Right. So a functor from \\(\mathcal{1}\\) to any category \\(\mathcal{C}\\) is just an object of \\(\mathcal{C}\\), and a natural transformation between such functors is just a morphism in \\(\mathcal{C}\\). **Puzzle.** How can can we say that last sentence, and more, in a single equation? We are saying that something is the same as something else. We've learned enough in this class by now to say it very tersely and precisely. > In the case where \\(\mathcal{B} = \mathbf{0}\\) the picture is empty. There is always exactly one such empty picture for every category \\(\mathcal{C}\\) Right! So you've quietly answered this puzzle, which I'm now stating more formally: > **Puzzle 138.** For any category \\(\mathcal{C}\\), classify all functors \\(F : \mathbf{0} \to \mathcal{C}\\). And the answer is: **there is always exactly one, since there are no objects nor morphisms in \\(\mathbf{0}\\).** > In the case where \\(\mathcal{C} = \mathbf{1}\\) there is exactly one possible picture (collapse everything down to the point). Right! Now you've answered this puzzle: > **Puzzle 135.** For any category \\(\mathcal{B}\\), classify all functors \\(F : \mathcal{B} \to \mathbf{1}\\). And the answer is: **this always exactly one, since such a functor must map all the objects of \\(\mathcal{B}\\) to the one object of \\(\mathbf{1}\\), and all morphisms of \\(\mathcal{B}\\) to the one morphism of \\(\mathbf{1}\\).** > In the case where \\(\mathcal{C} = \mathbf{0}\\) there is no "canvas" to draw the picture upon, so there is no picture/functor – unless \\(\mathcal{B}\\) is also \\(\mathbf{0}\\). Right! You've provided all the insights needed for a precise answer to this puzzle: > **Puzzle 139.** For any category \\(\mathcal{B}\\), classify all functors \\(F : \mathcal{B} \to \mathbf{0} \\). I'll let someone else state the precise answer, though!`

John wrote:

I'm betting you're looking for \(\mathcal{C}^\textbf{1} \cong \mathcal{C}\). (It never ceases to amaze me how the same patterns always show up throughout mathematics.)

The other puzzles you remark on have similar one-liners.

Puzzle 138has \(\mathcal{C}^\textbf{0} \cong \textbf{1}\).Puzzle 135has \(\textbf{1}^\mathcal{B} \cong \textbf{1}\). AndPuzzle 139has \(\textbf{0}^\mathcal{B} \cong \textbf{0}\) whenever \(\mathcal{B} \not\cong \textbf{0}\); otherwise we're back in the territory of Puzzle 138.These isomorphisms are all justified in \(\textbf{Cat}\) by invertible functors that formalize the answers that have been given for these puzzles.

;)

`John wrote: > **Puzzle.** How can can we say that last sentence, and more, in a single equation? We are saying that something is the same as something else. We've learned enough in this class by now to say it very tersely and precisely. I'm betting you're looking for \\(\mathcal{C}^\textbf{1} \cong \mathcal{C}\\). (It never ceases to amaze me how the same patterns always show up throughout mathematics.) The other puzzles you remark on have similar one-liners. **Puzzle 138** has \\(\mathcal{C}^\textbf{0} \cong \textbf{1}\\). **Puzzle 135** has \\(\textbf{1}^\mathcal{B} \cong \textbf{1}\\). And **Puzzle 139** has \\(\textbf{0}^\mathcal{B} \cong \textbf{0}\\) whenever \\(\mathcal{B} \not\cong \textbf{0}\\); otherwise we're back in the territory of Puzzle 138. These isomorphisms are all justified in \\(\textbf{Cat}\\) by invertible functors that formalize the answers that have been given for these puzzles. > By the way, Matthew: you keep spelling Jonathan's name "Jonathon", and he keeps not mentioning this, and I keep correcting it. ;)`

Jonathan wrote:

Yes!

Me neither! But category theory is designed to explain some of these patterns. Minutes ago, over here, I confirmed Reuben's guess that \(\mathbf{Cat}\) is cartesian closed, meaning it has finite products and also exponentials. In any cartesian closed category we have

$$ x^1 \cong x \textrm{ and } 1^x \cong 1 \textrm{ and } (x \times y)^z \cong x^y \times x^z \textrm{ and } x^{y \times z} \cong (x^y)^z . $$ The most famous example is the category of sets; another is the category of finite sets, and that's ultimately the reason we learn these facts as equations in high school.

\(\mathbf{Cat}\) also has finite coproducts. In any cartesian closed category with finite coproducts we get other good things, like

$$ x^0 \cong 1 \textrm{ and } x^{y + z} \cong x^y \times x^z .$$ So, most of the isomorphisms you wrote down hold at this level of generality. However, it's not always true that \(0^x \cong 0\) for all \(x \ncong 0\).

`<img width = "150" src = "http://math.ucr.edu/home/baez/mathematical/warning_sign.jpg"> Jonathan wrote: > I'm betting you're looking for \\(\mathcal{C}^\textbf{1} \cong \mathcal{C}\\). Yes! > It never ceases to amaze me how the same patterns always show up throughout mathematics. Me neither! But category theory is designed to explain some of these patterns. Minutes ago, [over here](https://forum.azimuthproject.org/discussion/comment/19491/#Comment_19491), I confirmed Reuben's guess that \\(\mathbf{Cat}\\) is [cartesian closed](https://en.wikipedia.org/wiki/Cartesian_closed_category), meaning it has finite products and also exponentials. In any cartesian closed category we have \[ x^1 \cong x \textrm{ and } 1^x \cong 1 \textrm{ and } (x \times y)^z \cong x^y \times x^z \textrm{ and } x^{y \times z} \cong (x^y)^z . \] The most famous example is the category of sets; another is the category of finite sets, and that's ultimately the reason we learn these facts as equations in high school. \\(\mathbf{Cat}\\) also has finite coproducts. In any cartesian closed category with finite coproducts we get other good things, like \[ x^0 \cong 1 \textrm{ and } x^{y + z} \cong x^y \times x^z .\] So, most of the isomorphisms you wrote down hold at this level of generality. However, it's not always true that \\(0^x \cong 0\\) for all \\(x \ncong 0\\).`

On a related note, for the functional programmers out there, I remember trying to prove that, in set theory, the function spaces a^(bxc) and (a^b)^c were in bijection. Doing this formally was driving me mad because there were so many levels to keep track of, and it wasn't apparent WHY it was true. Then someone pointed out to me that this proof was equivalent (see the Curry Howard isomorphism) to the higher-order function "curry" used in programming. Suddenly it was both trivial and intuitive. This was and is simple but compelling evidence for the power of the sort of abstract thinking that category theory seems to employ.

`On a related note, for the functional programmers out there, I remember trying to prove that, in set theory, the function spaces a^(bxc) and (a^b)^c were in bijection. Doing this formally was driving me mad because there were so many levels to keep track of, and it wasn't apparent WHY it was true. Then someone pointed out to me that this proof was equivalent (see the Curry Howard isomorphism) to the higher-order function "curry" used in programming. Suddenly it was both trivial and intuitive. This was and is simple but compelling evidence for the power of the sort of abstract thinking that category theory seems to employ.`

John Baez wrote:

Although it's not stated explicitly, don't the natural numbers also form a cartesian closed category with finite coproducts? After all, the above equations hold of the natural numbers when treated as a category.

`John Baez wrote: >In any cartesian closed category we have >\[ x^1 \cong x \textrm{ and } 1^x \cong 1 \textrm{ and } (x \times y)^z \cong x^y \times x^z \textrm{ and } x^{y \times z} \cong (x^y)^z . \\\\ \cdots\] >In any cartesian closed category with finite coproducts we get other good things, like >\[ x^0 \cong 1 \textrm{ and } x^{y + z} \cong x^y \times x^z .\] Although it's not stated explicitly, don't the natural numbers also form a cartesian closed category with finite coproducts? After all, the above equations hold of the natural numbers when treated as a category.`

I have simply been cheating, Fredrick Eisele. The fact that natural transformations and composition give a category implies that any square you can come up with has to commute. Or, put another way, eithet at least one of the transformations you gave isn't in fact a natural transformation, or they're equal.

John said:

Argh! Of course I didn't mean to talk about commutativity! It's all about commuting diagrams! And if you look at Fredrick's latest comment you can see that he writes:

proposing that they're not equal.

I'm sorry for the slightly excessive delay on, my part, I couldn't quite figure out what was going awry, and then forgot about it.

`I have simply been cheating, Fredrick Eisele. The fact that natural transformations and composition give a category implies that any square you can come up with has to commute. Or, put another way, eithet at least one of the transformations you gave isn't in fact a natural transformation, or they're equal. John said: > commutative Argh! Of course I didn't mean to talk about commutativity! It's all about commuting diagrams! And if you look at Fredrick's latest comment you can see that he writes: > α = c o a, β = c o b proposing that they're not equal. I'm sorry for the slightly excessive delay on, my part, I couldn't quite figure out what was going awry, and then forgot about it.`

Keith E. Peterson wrote:

Yes and no: it depends on how you make the natural numbers into a category. If you think of the natural numbers as a category via its preorder structure, then for it to be "cartesian closed" it would mean that for each natural number \(n\), the functor \(n \times \cdot\) has a right adjoint—but in the preorder, \(\times\) means "min", and the monotone \(\mathrm{min}(n,\cdot)\) doesn't have a right adjoint.

But if you make the natural numbers a category where the morphisms from \(m\) to \(n\) are the functions from \(\{1,\dots,m\}\) to \(\{1,\dots,n\}\), then this category's products and coproducts are given by the usual \(\times\) and \(+\), and it

iscartesian closed, and the exponentiation operation is the usual one too. So that's one way you can get these identities for natural numbers.(Incidentally, this works because this category of natural numbers is

equivalentto the category of finite sets. Roughly speaking, this is because every finite set is isomorphic to \(\{1,\dots,n\}\) for some natural number \(n\), and we're keeping the full set of morphisms between such sets.)`Keith E. Peterson wrote: > Although it's not stated explicitly, don't the natural numbers also form a cartesian closed category with finite coproducts? After all, the above equations hold of the natural numbers when treated as a category. Yes and no: it depends on how you make the natural numbers into a category. If you think of the natural numbers as a category via its preorder structure, then for it to be "cartesian closed" it would mean that for each natural number \\(n\\), the functor \\(n \times \cdot\\) has a right adjoint—but in the preorder, \\(\times\\) means "min", and the monotone \\(\mathrm{min}(n,\cdot)\\) doesn't have a right adjoint. But if you make the natural numbers a category where the morphisms from \\(m\\) to \\(n\\) are the functions from \\(\\{1,\dots,m\\}\\) to \\(\\{1,\dots,n\\}\\), then this category's products and coproducts are given by the usual \\(\times\\) and \\(+\\), and it *is* cartesian closed, and the exponentiation operation is the usual one too. So that's one way you can get these identities for natural numbers. (Incidentally, this works because this category of natural numbers is *equivalent* to the category of finite sets. Roughly speaking, this is because every finite set is isomorphic to \\(\\{1,\dots,n\\}\\) for some natural number \\(n\\), and we're keeping the full set of morphisms between such sets.)`