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

- All Categories 2.3K
- Chat 496
- Study Groups 10
- Epidemiology 5
- Network Theory 2
- Leaf Modeling 1
- Review Sections 9
- MIT 2020: Programming with Categories 52
- MIT 2020: Lectures 21
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 339
- MIT 2019: Lectures 79
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 64
- Azimuth Code Project 110
- Statistical methods 2
- Drafts 1
- Math Syntax Demos 15
- Wiki - Latest Changes 2
- Strategy 111
- Azimuth Project 1.1K
- - Spam 1
- News and Information 147
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 707

Options

Last time we saw how to treat a graph \(G\) as a 'database schema' and then consider databases built using this schema. The idea is to form the category

$$ \mathcal{C} = \mathbf{Free}(G) $$ whose morphisms are paths in \(G\). Then, a database built using this schema is a functor

$$ F: \mathcal{C} \to \mathbf{Set} .$$ Elegant and simple! Remember, objects of \(\mathcal{C}\) are just nodes of the graph \(G\), like the node \(\textrm{Employee}\) in this graph:

Then, our functor \(F\) sends each object to an actual set. For example, \(F(\textrm{Employee})\) will be the actual set of employees in our database!

The functor also sends each morphism in \(\mathcal{C}\) to an actual function. For example,

$$ F(\textrm{WorksIn}): F(\textrm{Employee}) \to F(\textrm{Department}) $$ will be the function mapping each employee in our database to their department.

Since each edge of our graph gives a morphism in \(\mathcal{C}\), our database needs to specify a function for each edge. And these functions can be whatever you want! It takes a bit of thought to see this is true.

More generally, each *path* in our graph gives a morphism in \(\mathcal{C}\). So actually our database needs to specify a function for each *path*. But in fact those are all determined, once we specify a function for each edge.

Let's see how it works in our example. There's a morphism

$$ \textrm{DepartmentName} \circ \textrm{WorksIn} : \textrm{Employee} \to \textrm{String} $$ in our category \(\mathcal{C}\), coming from a path of length 2 in our graph. So when we build a database, it must specify a function

$$ F(\textrm{DepartmentName} \circ \textrm{WorksIn}) : F(\textrm{Employee}) \to F(\textrm{String}). $$ However, a functor must preserve composition: we always have \(F(f \circ g) = F(f) \circ F(g)\). So, we must have

$$ F(\textrm{DepartmentName} \circ \textrm{WorksIn}) = F(\textrm{DepartmentName}) \circ F(\textrm{WorksIn}) .$$ I hope this makes complete sense intuitively — see the answers to Puzzle 109 if it doesn't. It also means we don't have any choice about the function \(F(\textrm{DepartmentName} \circ \textrm{WorksIn})\) once we've picked the functions \(F(\textrm{DepartmentName})\) and \(F(\textrm{WorksIn})\). In fact, knowing what \(F\) does to edges completely determines what it does to all paths of length \(1, 2, 3, \) and so on!

In summary: when our database schema is \(\mathcal{C} = \mathbf{Free}(G)\), to specify a database we simply:

Choose any set \(F(x)\) for each node \(x\) of our graph.

Choose any function \(F(e) : F(x) \to F(y)\) for each edge \(e\) in our graph, where \(x\) is the source and \(y\) is the target of that edge.

I haven't actually proved this; I'm just trying to make it plausible. Anyway, it's true, and this 'complete freedom' in choosing sets for nodes and functions for edges is why \(\mathbf{Free}(G)\) is called the 'free category' on the graph \(G\).

**Puzzle 110.** I said that knowing \(F\) does to edges completely determines what it does to paths of length \(1, 2, 3, \) and so on, due to the rule \(F(f \circ g) = F(f) \circ F(g)\). But what about paths of length 0?

All this is very pretty. But what if we want to impose some extra constraints on our database? In the answers to Puzzle 106 we saw two constraints we might want to impose. To keep things simple let's just look at one:

- The secretary of any department works in that department.

Constraints of this general sort can be handled using 'finitely presented' categories. To get one of these, we suppose our graph \(G\) is finite — if it's not, our database will be awfully big. Then, we replace the free category \(\mathcal{C} = \mathbf{Free}(G)\) by a new category, say \(\mathcal{D}\), in which we impose finitely many extra equations between morphisms.

In the example above, we'd impose this equation:

- \( \mathrm{WorksIn} \circ \mathrm{Secretary} = 1_{\mathrm{Department}}.\)

This equation may imply other equations, but that's okay.

Allowing equations between morphisms gives a more general, more powerful concept of database schema. Now a database schema is a finitely presented category \(\mathcal{D}\), and a database built using this schema is a functor \(F : \mathcal{D} \to \mathbf{Set}\).

In our example, where we've imposed the equation

$$ \mathrm{WorksIn} \circ \mathrm{Secretary} = 1_{\mathrm{Department}} , $$ the fact that \(F\) is a functor will imply

$$ F( \mathrm{WorksIn}) \circ F(\mathrm{Secretary}) = 1_{F(\mathrm{Department})}$$
So, only a database where this equation holds is allowed, if we're using this particular category \(\mathcal{D}\) as our schema! *When you enter data, you have to check this equation*.

So, our procedure for creating databases gets an extra step:

Choose any set \(F(x)\) for each node \(x\) of our graph.

Choose a function \(F(e) : F(x) \to F(y)\) for each edge \(e\) in our graph, where \(x\) is the source and \(y\) is the target of that edge.

Check that each equation \(F(f) = F(g)\) holds, whenever \(f = g\) is an equation between paths that we've imposed when defining our finitely presented category \(\mathcal{D}\).

The last step is bit of a nuisance, though it's not hard to do. As usual, adding more power to our setup makes it more complicated to use. But it may be worthwhile.

**Puzzle 111.** Suppose every person has one best friend. We get a database schema as possible. Start with a graph \(G\) having one node \(\textrm{Person}\) and one edge \(\textrm{BestFriend}\) from that node to itself. This gives a free category \(\mathcal{C} = \mathbf{Free}(G)\). Use this as our database schema. How many databases built on this schema are possible if

$$ F(\textrm{Person}) = \{ \textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan} \} ?$$
**Puzzle 112.** Now suppose every person is their best friend's best friend:

$$ \textrm{BestFriend} \circ \textrm{BestFriend} = 1_{\textrm{Person}} .$$ Create the finitely presented category \(\mathcal{D}\) by taking the free category \(\mathcal{C}\) and imposing this equation. How many databases built on this schema \(\mathcal{D}\) are possible if again we have

$$ F(\textrm{Person}) = \{ \textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan} \} ?$$
**Puzzle 113.** What if every person is their best friend's best friend's best friend?

## Comments

Inspired by matrix rig comment.

E := employee

D := department

S := string

m := manager

a := secretary [assistant]

d := department name

f := first name

w := works in

$$ A^0 = \left( \begin{array}{c | c c c} s \rightarrow t & E & D & S \\ \hline E & \lbrace 1_E \rbrace & \emptyset & \emptyset \\ D & \emptyset & \lbrace 1_D \rbrace & \emptyset \\ S & \emptyset & \emptyset & \lbrace 1_S \rbrace

\end{array} \right) $$ $$ A^1 = \left( \begin{array}{c | c c c} s \rightarrow t & E & D & S \\ \hline E & \lbrace m \rbrace & \lbrace w \rbrace & \lbrace f \rbrace \\ D & \lbrace a \rbrace & \emptyset & \lbrace d\rbrace \\ S & \emptyset & \emptyset & \emptyset

\end{array} \right) $$ Introduce the constraints. $$ WorksIn \circ Secretary =1_{Department} $$ $$ WorksIn \circ Manager = WorksIn $$ $$ A^2 = \left( \begin{array}{c | c c c} s \rightarrow t & E & D & S \\ \hline E & \lbrace m \circ m , \quad a \circ w \rbrace & \lbrace w \circ m = w \rbrace & \lbrace f \circ m, \quad d \circ w \rbrace \\ D & \lbrace m \circ a \rbrace & \lbrace w \circ a = 1_D \rbrace & \emptyset \\ S & \emptyset & \emptyset & \emptyset

\end{array} \right) $$ The equivalence group identifies duplicate paths. Should the duplicate be dropped or retained? I will presume retained and see where that takes us.

$$ A^3 = \left( \begin{array}{c | c c c} s \rightarrow t & E & D & S \\ \hline E & \lbrace m \circ m \circ m, \quad a \circ ( w \circ m ), \quad m \circ a \circ w \rbrace & \lbrace ( w \circ m ) \circ m = w, \quad ( w \circ a ) \circ w = w \rbrace & \lbrace f \circ m \circ m, \quad d \circ ( w \circ m ) \rbrace \\ D & \lbrace m \circ m \circ a, \quad a \circ ( w \circ a ) = a \rbrace & \lbrace ( w \circ m ) \circ a = 1_D \rbrace & \lbrace f \circ m \circ a, \quad d \circ ( w \circ a ) = d \rbrace \\ S & \emptyset & \emptyset & \emptyset

\end{array} \right) $$ From this it is obvious that all shorter paths will have already been generated and need not be carried forward.

$$ A^3 = \left( \begin{array}{c | c c c} s \rightarrow t & E & D & S \\ \hline E & \lbrace m \circ m \circ m, \quad m \circ a \circ w \rbrace & \emptyset & \lbrace f \circ m \circ m \rbrace \\ D & \lbrace m \circ m \circ a \rbrace & \emptyset & \lbrace f \circ m \circ a \rbrace \\ S & \emptyset & \emptyset & \emptyset

\end{array} \right) $$ One more time with pruning.

$$ A^4 = \left( \begin{array}{c | c c c} s \rightarrow t & E & D & S \\ \hline E & \lbrace m \circ m \circ m \circ m \rbrace & \emptyset & \lbrace f \circ m \circ m \circ m , \quad f \circ m \circ a \circ w \rbrace \\ D & \lbrace m \circ m \circ m \circ a \rbrace & \emptyset & \lbrace f \circ m \circ m \circ a \rbrace \\ S & \emptyset & \emptyset & \emptyset

\end{array} \right) $$

`Inspired by [matrix rig comment](https://forum.azimuthproject.org/discussion/comment/19020/#Comment_19020). E := employee D := department S := string m := manager a := secretary [assistant] d := department name f := first name w := works in \[ A^0 = \left( \begin{array}{c | c c c} s \rightarrow t & E & D & S \\\\ \hline E & \lbrace 1_E \rbrace & \emptyset & \emptyset \\\\ D & \emptyset & \lbrace 1_D \rbrace & \emptyset \\\\ S & \emptyset & \emptyset & \lbrace 1_S \rbrace \end{array} \right) \] \[ A^1 = \left( \begin{array}{c | c c c} s \rightarrow t & E & D & S \\\\ \hline E & \lbrace m \rbrace & \lbrace w \rbrace & \lbrace f \rbrace \\\\ D & \lbrace a \rbrace & \emptyset & \lbrace d\rbrace \\\\ S & \emptyset & \emptyset & \emptyset \end{array} \right) \] Introduce the constraints. \[ WorksIn \circ Secretary =1_{Department} \] \[ WorksIn \circ Manager = WorksIn \] \[ A^2 = \left( \begin{array}{c | c c c} s \rightarrow t & E & D & S \\\\ \hline E & \lbrace m \circ m , \quad a \circ w \rbrace & \lbrace w \circ m = w \rbrace & \lbrace f \circ m, \quad d \circ w \rbrace \\\\ D & \lbrace m \circ a \rbrace & \lbrace w \circ a = 1_D \rbrace & \emptyset \\\\ S & \emptyset & \emptyset & \emptyset \end{array} \right) \] The equivalence group identifies duplicate paths. Should the duplicate be dropped or retained? I will presume retained and see where that takes us. \[ A^3 = \left( \begin{array}{c | c c c} s \rightarrow t & E & D & S \\\\ \hline E & \lbrace m \circ m \circ m, \quad a \circ ( w \circ m ), \quad m \circ a \circ w \rbrace & \lbrace ( w \circ m ) \circ m = w, \quad ( w \circ a ) \circ w = w \rbrace & \lbrace f \circ m \circ m, \quad d \circ ( w \circ m ) \rbrace \\\\ D & \lbrace m \circ m \circ a, \quad a \circ ( w \circ a ) = a \rbrace & \lbrace ( w \circ m ) \circ a = 1_D \rbrace & \lbrace f \circ m \circ a, \quad d \circ ( w \circ a ) = d \rbrace \\\\ S & \emptyset & \emptyset & \emptyset \end{array} \right) \] From this it is obvious that all shorter paths will have already been generated and need not be carried forward. \[ A^3 = \left( \begin{array}{c | c c c} s \rightarrow t & E & D & S \\\\ \hline E & \lbrace m \circ m \circ m, \quad m \circ a \circ w \rbrace & \emptyset & \lbrace f \circ m \circ m \rbrace \\\\ D & \lbrace m \circ m \circ a \rbrace & \emptyset & \lbrace f \circ m \circ a \rbrace \\\\ S & \emptyset & \emptyset & \emptyset \end{array} \right) \] One more time with pruning. \[ A^4 = \left( \begin{array}{c | c c c} s \rightarrow t & E & D & S \\\\ \hline E & \lbrace m \circ m \circ m \circ m \rbrace & \emptyset & \lbrace f \circ m \circ m \circ m , \quad f \circ m \circ a \circ w \rbrace \\\\ D & \lbrace m \circ m \circ m \circ a \rbrace & \emptyset & \lbrace f \circ m \circ m \circ a \rbrace \\\\ S & \emptyset & \emptyset & \emptyset \end{array} \right) \]`

Conceptually speaking, possible outputs of the function, \(F(\text{BestFriend})\), when applied to the set, \(F(\textrm{Person})\), is like we're producing a repeated product of sets.

\[ F(\text{BestFriend})(\text{Anna}) \rightarrow \lbrace \textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan} \rbrace, \\ F(\text{BestFriend})(\text{Jordan}) \rightarrow

\lbrace \textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan} \rbrace, \\ F(\text{BestFriend})(\text{Lisa}) \rightarrow

\lbrace \textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan} \rbrace, \\ F(\text{BestFriend})(\text{Ryan}) \rightarrow

\lbrace \textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan} \rbrace, \\ \]

or using nicer notation,

\[ \prod_{p \in F(\textrm{Person})}F(\text{BestFriend})(p), \]

which would imply a formula of,

\[ \prod_{\# \lbrace p \mid p \in F(\text{Person}) \rbrace}{\# \lbrace q \mid q = F(\text{BestFriend})(p) \rbrace}. \]

`>**Puzzle 111.** Suppose every person has one best friend. We get a database schema as possible. Start with a graph \\(G\\) having one node \\(\textrm{Person}\\) and one edge \\(\textrm{BestFriend}\\) from that node to itself. This gives a free category \\(\mathcal{C} = \mathbf{Free}(G)\\). Use this as our database schema. How many databases built on this schema are possible if >\[ F(\textrm{Person}) = \\{ \textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan} \\} ?\] Conceptually speaking, possible outputs of the function, \\(F(\text{BestFriend})\\), when applied to the set, \\(F(\textrm{Person})\\), is like we're producing a repeated product of sets. \\[ F(\text{BestFriend})(\text{Anna}) \rightarrow \lbrace \textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan} \rbrace, \\\\ F(\text{BestFriend})(\text{Jordan}) \rightarrow \lbrace \textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan} \rbrace, \\\\ F(\text{BestFriend})(\text{Lisa}) \rightarrow \lbrace \textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan} \rbrace, \\\\ F(\text{BestFriend})(\text{Ryan}) \rightarrow \lbrace \textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan} \rbrace, \\\\ \\] or using nicer notation, \\[ \prod_{p \in F(\textrm{Person})}F(\text{BestFriend})(p), \\] which would imply a formula of, \\[ \prod_{\\# \lbrace p \mid p \in F(\text{Person}) \rbrace}{\\# \lbrace q \mid q = F(\text{BestFriend})(p) \rbrace}. \\]`

Keith: The final answer to Puzzle 111 is a number. It's very good to compute that number using a more general formula, as you seem to be doing. But still, what's the number?

`Keith: The final answer to Puzzle 111 is a number. It's very good to compute that number using a more general formula, as you seem to be doing. But still, what's the number?`

Oh, the number is 16.

`>But still, what's the number? Oh, the number is 16.`

Puzzle 110Since paths of length 0 in \( \mathbf{Free}(G)\) are the identity morphisms of that category and functors preserve identities, paths of length 0 from node \(x\) to itself must map to the identity function from the set \(F(x)\) to itself.

`**Puzzle 110** Since paths of length 0 in \\( \mathbf{Free}(G)\\) are the identity morphisms of that category and functors preserve identities, paths of length 0 from node \\(x\\) to itself must map to the identity function from the set \\(F(x)\\) to itself.`

I got a different answer from Keith for Puzzle 111 (although they both share the nice property of being a power of 4 :) )

Puzzle 111.To make a database we just need to define a set for every node in the graph and a set map for every edge. John defined the action of \(F\) on the single node

$$F(\textrm{Person}) = \{\textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan}\} $$ So to define a database, all that's left to do is define a function

$$ F(\textrm{BestFriend}): F(\textrm{Person}) \to F(\textrm{Person}) $$ There are four distinct options for each person's best friend (assuming that a person can be their own best friend), so there are \(4^4 = 256\) possible maps, and thus 256 possible databases!

Puzzle 112.With the new restriction that your best friend's best friend must be you, we now have to check all our 256 databases to see which ones satisfy:

$$ F(\textrm{BestFriend}) \circ F(\textrm{BestFriend}) = 1_{\{\textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan}\} }$$ In other words the one for which \(F(\textrm{BestFriend}) \) is its own inverse. There are several ways of doing this.

And so there are 10 possible databases built on \(\mathcal{D}\).

Puzzle 113.If you are your best friend's best friend's best friend, then either you are in a best friendship triangle or you are your own best friend. There are two ways of doing this:

So there are a total of 9 possible databases.

`I got a different answer from Keith for Puzzle 111 (although they both share the nice property of being a power of 4 :) ) **Puzzle 111.** To make a database we just need to define a set for every node in the graph and a set map for every edge. John defined the action of \\(F\\) on the single node \[F(\textrm{Person}) = \\{\textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan}\\} \] So to define a database, all that's left to do is define a function \[ F(\textrm{BestFriend}): F(\textrm{Person}) \to F(\textrm{Person}) \] There are four distinct options for each person's best friend (assuming that a person can be their own best friend), so there are \\(4^4 = 256\\) possible maps, and thus 256 possible databases! **Puzzle 112.** With the new restriction that your best friend's best friend must be you, we now have to check all our 256 databases to see which ones satisfy: \[ F(\textrm{BestFriend}) \circ F(\textrm{BestFriend}) = 1_{\\{\textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan}\\} }\] In other words the one for which \\(F(\textrm{BestFriend}) \\) is its own inverse. There are several ways of doing this. - No one is their own best friend. There are 3 of these maps corresponding to the 3 ways to pair up the four people. - Two people are their own best friend. There are \\( {4\choose 2} = 6 \\) of these maps. - Everyone is their own best friend. There are 1 of these maps (it is the identity map). And so there are 10 possible databases built on \\(\mathcal{D}\\). **Puzzle 113.** If you are your best friend's best friend's best friend, then either you are in a best friendship triangle or you are your own best friend. There are two ways of doing this: - One person is their own best friend and the other three people map to each other in a triangular loop. There are 4 ways to choose which person is the odd person out and 2 ways to choose the ordering for the triangular loop. So a total of 8 types of these maps. - Everyone is their own best friend. There is 1 of these maps. So there are a total of 9 possible databases.`

Sophie wrote:

Interesting! I'm glad you agree on that much at least.

What does our theory of databases say about this question? (As opposed to what a psychologist might say about it.)

`Sophie wrote: > I got a different answer from Keith for Puzzle 111 (although they both share the nice property of being a power of 4 :) ) Interesting! I'm glad you agree on that much at least. <img src = "http://math.ucr.edu/home/baez/emoticons/tongue2.gif"> > (assuming that a person can be their own best friend) What does our theory of databases say about this question? (As opposed to what a psychologist might say about it.)`

Is there a reason the cateogry \(\mathbf{Set}\) is the "chosen" category when we define databases? Will we get interesting properties that we wouldn't get if we just defined a database to be functor from \(\mathbf{Free}(G)\) to any category? Or to a specific category like \(\mathbf{Grp}\)?

`Is there a reason the cateogry \\(\mathbf{Set}\\) is the "chosen" category when we define databases? Will we get interesting properties that we wouldn't get if we just defined a database to be functor from \\(\mathbf{Free}(G)\\) to any category? Or to a specific category like \\(\mathbf{Grp}\\)?`

My understanding is that our theory of databases makes no restriction for a person being their own best friend. In the definition, John wrote:

So functions that map people to themselves are definitely allowed!

A follow up puzzle:

Puzzle SL 1Is there a finitely presented category which constrains people from being their own best friend?`> What does our theory of databases say about this question? (As opposed to what a psychologist might say about it.) My understanding is that our theory of databases makes no restriction for a person being their own best friend. In the definition, John wrote: > Choose any function \\(F(e) : F(x) \to F(y)\\) for each edge \\(e\\) in our graph So functions that map people to themselves are definitely allowed! A follow up puzzle: **Puzzle SL 1** Is there a finitely presented category which constrains people from being their own best friend?`

Puzzle 111:As John mentioned, without any extra equations, \(F\) may map arrows to any function. Since \(F(\textrm{Person})\) is a set of four people, and \(F(\textrm{BestFriend})\) is an endomorphism on this set, we have \(4^4\) choices of function, and hence \(4^4\) databases.Puzzle 112:With this equation, \(F(\textrm{BestFriend})\) must be aninvolution. Involutions are special kinds of permutations, i.e. those of degree at most two. OEIS A000085 tells us there are ten involutions on a set of four elements. (We can enumerate these using cycle notation: \((1)(2)(3)(4), (12)(3)(4), (13)(2)(4), (14)(2)(3), (23)(1)(4), (24)(1)(3), (34)(1)(2), (12)(34), (13)(24), (14)(23)\). Can you see how I produced these?)Puzzle 113:With this equation, \(F(\textrm{BestFriend})\) must be a permutation of degree at most three. This means that its cycle decomposition mustonlyconsist of cycles of order either 1 or 3; adding a 2 in the mix would force us to take the least common multiple of the degrees, forcing us to either degree 2 or 6, which is not what we want. Again, OEIS A001470 tells us there are nine such permutations on a set of four elements: \((1)(2)(3)(4), (123)(4), (132)(4), (124)(3), (142)(3), (134)(2), (143)(2), (234)(1), (243)(1)\).`**Puzzle 111:** As John mentioned, without any extra equations, \\(F\\) may map arrows to any function. Since \\(F(\textrm{Person})\\) is a set of four people, and \\(F(\textrm{BestFriend})\\) is an endomorphism on this set, we have \\(4^4\\) choices of function, and hence \\(4^4\\) databases. **Puzzle 112:** With this equation, \\(F(\textrm{BestFriend})\\) must be an _involution_. Involutions are special kinds of permutations, i.e. those of degree at most two. [OEIS A000085](https://oeis.org/A000085) tells us there are ten involutions on a set of four elements. (We can enumerate these using cycle notation: \\((1)(2)(3)(4), (12)(3)(4), (13)(2)(4), (14)(2)(3), (23)(1)(4), (24)(1)(3), (34)(1)(2), (12)(34), (13)(24), (14)(23)\\). Can you see how I produced these?) **Puzzle 113:** With this equation, \\(F(\textrm{BestFriend})\\) must be a permutation of degree at most three. This means that its cycle decomposition must _only_ consist of cycles of order either 1 or 3; adding a 2 in the mix would force us to take the least common multiple of the degrees, forcing us to either degree 2 or 6, which is not what we want. Again, [OEIS A001470](https://oeis.org/A001470) tells us there are nine such permutations on a set of four elements: \\((1)(2)(3)(4), (123)(4), (132)(4), (124)(3), (142)(3), (134)(2), (143)(2), (234)(1), (243)(1)\\).`

Jonathan, I like how you make explicit the connection to group theory. Is this connection a result of this particular example (maybe the fact that \(G\) has only one node and one edge) or a more general phenomenon?

`Jonathan, I like how you make explicit the connection to group theory. Is this connection a result of this particular example (maybe the fact that \\(G\\) has only one node and one edge) or a more general phenomenon?`

Sophie, it might be a combination of factors. The most important one is that we're requiring \(f^{(k)} = \mathrm{id}\) for some \(k\), which can only happen if \(f\) is a bijection. The fact that \(f\) is a loop on a single object is what allows us to iterate \(f\) like this, but I wouldn't say that's the most important part -- just a necessary detail.

Once you're working with bijections on finite sets, you quickly fall into the usual patterns of group theory.

(I

justgot a new copy of Dummit & Foote in the mail. Perhaps this is my cue to crack it open and refresh myself on group theory.)`Sophie, it might be a combination of factors. The most important one is that we're requiring \\(f^{(k)} = \mathrm{id}\\) for some \\(k\\), which can only happen if \\(f\\) is a bijection. The fact that \\(f\\) is a loop on a single object is what allows us to iterate \\(f\\) like this, but I wouldn't say that's the most important part -- just a necessary detail. Once you're working with bijections on finite sets, you quickly fall into the usual patterns of group theory. (I _just_ got a new copy of Dummit & Foote in the mail. Perhaps this is my cue to crack it open and refresh myself on group theory.)`

What fun!

`> I _just_ got a new copy of Dummit & Foote in the mail. Perhaps this is my cue to crack it open and refresh myself on group theory. What fun!`

Apart from Sophie and Jonathan's answer, I can think of a

thirdsolution.My answer: assuming the \(\mathrm{BestFriend}\) relation can be

`NULL`

, then there are \(5^4 = 625\)(This is the case where the \(\mathrm{BestFriend}\) relation can be a

totalorpartialfunction.)Background:SQL is theStructured Query Language. Almost all relational databases in industry are programmed some dialect of this language. SQL is what Spivak and Wisnesky's AQL database language compiles down to. AQL is a real world implementation of FQL, the categorical database language in Chapter 3 of7 Sketcheswe have been talking about.In SQL, there's basically two ways I could create the

`Person`

table.The first reflects Sophie and Jonathan's solution:

Notice that this has the

`NOT NULL`

constraint on`Person.BestFriend`

. This forces the`BestFriend`

column to behave like a total function and thus there are \(4^4 = 256\) permutations.(There is a

Wiredstory from 2015 aboutJohn Null. His name is often erroneously forbidden by this sort of database constraint. He has had a lot of difficulty due to widespread bad programming practices.)At any rate it's plausible that we don't always know everyone's best friend. In this case the table declaration looks like:

Here the

`NOT NULL`

constraint on`Person.BestFriend`

has been dropped.If

`Person`

has four rows, then now there's a fifth possible value for the`BestFriend`

column:`NULL`

.Hence there are \(5^4\) possibilities in this case.

Puzzle 112andPuzzle 113rule out`NULL`

by introducing algebraic constraints.`> **Puzzle 111.** Suppose every person has one best friend. We get a database schema as possible. Start with a graph \\(G\\) having one node \\(\textrm{Person}\\) and one edge \\(\textrm{BestFriend}\\) from that node to itself. This gives a free category \\(\mathcal{C} = \mathbf{Free}(G)\\). Use this as our database schema. How many databases built on this schema are possible if > > \[ F(\textrm{Person}) = \lbrace \textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan} \rbrace ?\] Apart from Sophie and Jonathan's answer, I can think of a *third* solution. My answer: assuming the \\(\mathrm{BestFriend}\\) relation can be `NULL`, then there are \\(5^4 = 625\\) (This is the case where the \\(\mathrm{BestFriend}\\) relation can be a *total* or *partial* function.) ---------------------------- **Background:** [SQL](https://en.wikipedia.org/wiki/SQL) is the *Structured Query Language*. Almost all relational databases in industry are programmed some dialect of this language. SQL is what Spivak and Wisnesky's [AQL](http://categoricaldata.net/aql.html) database language compiles down to. AQL is a real world implementation of FQL, the categorical database language in Chapter 3 of *7 Sketches* we have been talking about. In SQL, there's basically two ways I could create the `Person` table. The first reflects Sophie and Jonathan's solution: <pre> CREATE TABLE Person ( Name VARCHAR(128) PRIMARY KEY, BestFriend VARCHAR(128) NOT NULL REFERENCES Person (Name) ); </pre> Notice that this has the `NOT NULL` constraint on `Person.BestFriend`. This forces the `BestFriend` column to behave like a total function and thus there are \\(4^4 = 256\\) permutations. (There is a *Wired* story from 2015 about [*John Null*](https://www.wired.com/2015/11/null/). His name is often erroneously forbidden by this sort of database constraint. He has had a lot of difficulty due to widespread bad programming practices.) At any rate it's plausible that we don't always know everyone's best friend. In this case the table declaration looks like: <pre> CREATE TABLE Person ( Name VARCHAR(128) PRIMARY KEY, BestFriend VARCHAR(128) REFERENCES Person (Name) ); </pre> Here the `NOT NULL` constraint on `Person.BestFriend` has been dropped. If `Person` has four rows, then now there's a fifth possible value for the `BestFriend` column: `NULL`. Hence there are \\(5^4\\) possibilities in this case. **Puzzle 112** and **Puzzle 113** rule out `NULL` by introducing algebraic constraints.`

Matthew - partial functions aren't allowed if a database is a functor \( F: \mathcal{C} \to \mathbf{Set}\), as it is in my puzzles today. The morphisms in \( \mathbf{Set}\) are functions! But there's another category where the morphisms are partial functions. You are considering a modified concept of database, which is a functor from \(\mathcal{C}\) to that other category. I suppose we could call this a

partial database.It's a useful concept.`Matthew - partial functions aren't allowed if a database is a functor \\( F: \mathcal{C} \to \mathbf{Set}\\), as it is in my puzzles today. The morphisms in \\( \mathbf{Set}\\) are functions! But there's another category where the morphisms are partial functions. You are considering a modified concept of database, which is a functor from \\(\mathcal{C}\\) to that other category. I suppose we could call this a **partial database.** It's a useful concept.`

I am sorry for the confusion!

In that case the solution is \(4^4 = 256\).

Sure, I would maybe write the category of partial functions between sets as \(\bot \sqcup \mathbf{Set}\).

It's an uglier, less familiar category to pure mathematicians.

However, it is tragically a rather common situation in applied mathematics. For instance, a popular data set of chemical reactions in computational chemistry is derived from the US Patent registry. This data has a lot of errors and many missing fields. Other data sets, such as CWEEDS historical Canadian climate data also has many missing entries. The weather stations in that data set are sometimes offline for long periods of time. Dealing with incomplete data like this is a full time job.

`> Matthew - partial functions aren't allowed if a database is a functor \\( F: \mathcal{C} \to \mathbf{Set}\\), as it is in my puzzles. The morphisms in \\( \mathbf{Set}\\) are functions! But there's another category where the morphisms are partial functions. I am sorry for the confusion! In that case the solution is \\(4^4 = 256\\). > You are considering a modified concept of database, which is a functor from \\(\mathbf{C}\\) to that other category. Sure, I would maybe write the category of partial functions between sets as \\(\bot \sqcup \mathbf{Set}\\). It's an uglier, less familiar category to pure mathematicians. However, it is tragically a rather common situation in applied mathematics. For instance, a popular data set of chemical reactions in computational chemistry is derived from the US Patent registry. This data has a lot of errors and many missing fields. Other data sets, such as [CWEEDS](http://climate.weather.gc.ca/prods_servs/engineering_e.html) historical Canadian climate data also has many missing entries. The weather stations in that data set are sometimes offline for long periods of time. Dealing with incomplete data like this is a full time job.`

Sophie wrote:

In the modern understanding of things, a

groupis a category with one object where every morphism has an inverse. I cleverly chose the categories in Puzzles 112 and 113 to be groups, because I like groups. As I'm sure you've noticed, the category in Puzzle 112 is the group \(\mathbb{Z}/2\), while that in Puzzle 113 is \(\mathbb{Z}/3\).If the category \(\mathcal{C}\) is a group, a functor \(F : \mathcal{C} \to \mathbf{Set}\) is called an

actionof that group. If the one object of \(\mathcal{C}\) is \(x\), then \(S = F(x)\) is a set and we say we have an action of our groupon the set \(S\).There's a lot of fun to be had studying actions of groups on sets. This is how group theory originated in the first place! There are nice connections to number theory. Here's a generalization of Puzzles 112 and 113, that can be solved the same way:

Puzzle.If \(p\) is prime, how many actions of the group \(\mathbb{Z}/p\) are there on a set with \(n\) elements?I'm making \(p\) prime to make the problem easy, not to make it hard! But the formula is a bit complicated. It gets a tiny bit simpler when \(n\) is a multiple of \(p\).

`Sophie wrote: > Jonathan, I like how you make explicit the connection to group theory. Is this connection a result of this particular example (maybe the fact that \\(G\\) has only one node and one edge) or a more general phenomenon? In the modern understanding of things, a **group** is a category with one object where every morphism has an inverse. I cleverly chose the categories in Puzzles 112 and 113 to be groups, because I like groups. As I'm sure you've noticed, the category in Puzzle 112 is the group \\(\mathbb{Z}/2\\), while that in Puzzle 113 is \\(\mathbb{Z}/3\\). If the category \\(\mathcal{C}\\) is a group, a functor \\(F : \mathcal{C} \to \mathbf{Set}\\) is called an **[action](https://en.wikipedia.org/wiki/Group_action)** of that group. If the one object of \\(\mathcal{C}\\) is \\(x\\), then \\(S = F(x)\\) is a set and we say we have an action of our group **on the set \\(S\\)**. There's a lot of fun to be had studying actions of groups on sets. This is how group theory originated in the first place! There are nice connections to number theory. Here's a generalization of Puzzles 112 and 113, that can be solved the same way: **Puzzle.** If \\(p\\) is prime, how many actions of the group \\(\mathbb{Z}/p\\) are there on a set with \\(n\\) elements? I'm making \\(p\\) prime to make the problem easy, not to make it hard! But the formula is a bit complicated. It gets a tiny bit simpler when \\(n\\) is a multiple of \\(p\\).`

I agree with the above answers, but I can't help but feel we're cheating.

For one thing, we never explicitly gave a functor from \(\mathbf{Set}\) to \(\mathbb{N}\), even though \(\mathbb{N}\) is certainly a category.

I think the construction of such a functor would be a good exercise, given it also reinforces the notion of composition of functors.

`I agree with the above answers, but I can't help but feel we're cheating. For one thing, we never explicitly gave a functor from \\(\mathbf{Set}\\) to \\(\mathbb{N}\\), even though \\(\mathbb{N}\\) is certainly a category. I think the construction of such a functor would be a good exercise, given it also reinforces the notion of composition of functors.`

How are you making \(\mathbb{N}\) into a category, Keith? There are a few ways. I'm not sure why you want to do it, but first tell me how you're doing it!

`How are you making \\(\mathbb{N}\\) into a category, Keith? There are a few ways. I'm not sure why you want to do it, but first tell me how you're doing it!`

Why not simply take \(\mathbb{N}\) as the free category on one object and one (non-identity) morphism?

`Why not simply take \\(\mathbb{N}\\) as the free category on one object and one (non-identity) morphism?`

Keith wrote:

Can you elaborate on why we ought to consider \(\mathbb{N}\) as a category in this context? It seems we're only counting things, so a mere function \(\mathrm{Ob}(C) \to \mathbb{N}\) seems appropriate.

`[Keith wrote:](https://forum.azimuthproject.org/discussion/comment/19054/#Comment_19054) > For one thing, we never explicitly gave a functor from \\(\mathbf{Set}\\) to \\(\mathbb{N}\\), even though \\(\mathbb{N}\\) is certainly a category. Can you elaborate on why we ought to consider \\(\mathbb{N}\\) as a category in this context? It seems we're only counting things, so a mere function \\(\mathrm{Ob}(C) \to \mathbb{N}\\) seems appropriate.`

What John calls databases are actually constant lookup structures, whereas real-life databases are all about modifying such structures efficiently!

In this discussion, entering data means changing the functor! In fact, adding data means adding equations! And 'checking' means taking care that our new equations don't contradict ones that are already present.

If we want to reason about changing databases we'll have to introduce even higher kinds of functions! So far we have a functor I which creates a dataset from a schema:

\[ I: C \rightarrow Gr(I) \]

To make I encompass more data we need to apply a higher functor (a natural transformation) to I:

\[ A: I \rightarrow I \]

In real life, we'd parametrize A such that we can give the data record to be added as extra parameter:

\[ insert: record \rightarrow I \rightarrow I \]

Deleting stuff is quite popular:

\[ delete: index \rightarrow I \rightarrow I \]

Their combination is also very common, and having more primitives can help to make operations more efficient:

\[ replace: index \rightarrow record \rightarrow I \rightarrow I \]

Btw, I'm not quite sure how to express a selector like 'index' using categories. It seems it should be a schema including equations, like C, and compatible to it, but with more restrictions, so it matches (or rather the instanciation functor I produces) a subset of the whole.

Puzzle rf39.1: How should I write this? Should I mention our functor I? Is the following inclusion pointing in the right direction?

\[ C' \subset C \]

For now, let's assume C' encodes constraints as intended. In practice we'll further see querying as a primitive:

\[ select: C' \rightarrow I \rightarrow Gr'(I) \]

Once we can do that, we can give a series of similar changes very succinctly:

\[ update: C' \rightarrow I' \rightarrow I' \rightarrow I \rightarrow I \]

Okay, I'm really not sure how to do this, but I'm confident that this stuff will be part of a future lecture, possibly one titled 'natural transformations'...

`What John calls databases are actually constant lookup structures, whereas real-life databases are all about modifying such structures efficiently! > When you enter data, you have to check this equation! In this discussion, entering data means changing the functor! In fact, adding data means adding equations! And 'checking' means taking care that our new equations don't contradict ones that are already present. If we want to reason about changing databases we'll have to introduce even higher kinds of functions! So far we have a functor I which creates a dataset from a schema: \\[ I: C \rightarrow Gr(I) \\] To make I encompass more data we need to apply a higher functor (a natural transformation) to I: \\[ A: I \rightarrow I \\] In real life, we'd parametrize A such that we can give the data record to be added as extra parameter: \\[ insert: record \rightarrow I \rightarrow I \\] Deleting stuff is quite popular: \\[ delete: index \rightarrow I \rightarrow I \\] Their combination is also very common, and having more primitives can help to make operations more efficient: \\[ replace: index \rightarrow record \rightarrow I \rightarrow I \\] Btw, I'm not quite sure how to express a selector like 'index' using categories. It seems it should be a schema including equations, like C, and compatible to it, but with more restrictions, so it matches (or rather the instanciation functor I produces) a subset of the whole. Puzzle rf39.1: How should I write this? Should I mention our functor I? Is the following inclusion pointing in the right direction? \\[ C' \subset C \\] For now, let's assume C' encodes constraints as intended. In practice we'll further see querying as a primitive: \\[ select: C' \rightarrow I \rightarrow Gr'(I) \\] Once we can do that, we can give a series of similar changes very succinctly: \\[ update: C' \rightarrow I' \rightarrow I' \rightarrow I \rightarrow I \\] Okay, I'm really not sure how to do this, but I'm confident that this stuff will be part of a future lecture, possibly one titled 'natural transformations'...`

If people would like to read about it I might tell a bit about why SQL came into existence, and what modern relational databases have to offer.

`If people would like to read about it I might tell a bit about why SQL came into existence, and what modern relational databases have to offer.`

@John wrote:

One slightly pedantic caveat – we don't quite have "complete freedom" in choosing sets for nodes – if \(a\) is an arrow from node \(s\) to node \(t\), and we choose \(F(t)\) to be the empty set, then we are forced to have \(F(s)\) empty too, with \(F(a)\) the empty function.

`@John wrote: > this 'complete freedom' in choosing sets for nodes and functions for edges is why \\(\mathbf{Free}(G)\\) is called the 'free category' on the graph \\(G\\) One slightly pedantic caveat – we don't quite have "complete freedom" in choosing sets for nodes – if \\(a\\) is an arrow from node \\(s\\) to node \\(t\\), and we choose \\(F(t)\\) to be the empty set, then we are forced to have \\(F(s)\\) empty too, with \\(F(a)\\) the empty function.`

Robert Figura wrote:

I would like to hear about it!

`Robert Figura wrote: > If people would like to read about it I might tell a bit about why SQL came into existence, and what modern relational databases have to offer. I would like to hear about it!`

Jonathan Castello wrote:

If we were just counting the object set of \(C\), that would be fine, but we're in fact counting possible

morphismsof \(C\), ie the cardinality of \(C(F(\text{Person}), F(\text{Person}))\).Since this operator is acting on morphisms as well as objects, it is a functor.

`Jonathan Castello wrote: >Can you elaborate on why we ought to consider \\(\mathbb{N}\\) as a category in this context? It seems we're only counting things, so a mere function \\(\mathrm{Ob}(C) \to \mathbb{N}\\) seems appropriate. If we were just counting the object set of \\(C\\), that would be fine, but we're in fact counting possible *morphisms* of \\(C\\), ie the cardinality of \\(C(F(\text{Person}), F(\text{Person}))\\). Since this operator is acting on morphisms as well as objects, it is a functor.`

Actually, just thinking on it, you can give a really nice formula for cardinality, \(\mathrm{Card} : \mathbf{Set} \to \mathbb{N} \),

\[ \mathrm{Card}(X) = \sum_{x \in X}1, (X \in Obj(C)), \] and, \[ \mathbb{N}(\mathrm{Card}(X), \mathrm{Card}(Y)) = \prod_{y \in Y}\sum_{x \in X}1. \]

`Actually, just thinking on it, you can give a really nice formula for cardinality, \\(\mathrm{Card} : \mathbf{Set} \to \mathbb{N} \\), \\[ \mathrm{Card}(X) = \sum_{x \in X}1, (X \in Obj(C)), \\] and, \\[ \mathbb{N}(\mathrm{Card}(X), \mathrm{Card}(Y)) = \prod_{y \in Y}\sum_{x \in X}1. \\]`

Here you go, Owen:

https://forum.azimuthproject.org/discussion/2227/history-of-databases

`Here you go, Owen: https://forum.azimuthproject.org/discussion/2227/history-of-databases`

Sophie wrote:

The main reason is a practical one: we are often interested in databases that consist of a bunch of sets and functions between these sets. But we are often interested in other kinds, too - and that's the topic of Lecture 40!

Yes, lots. The category \(\textbf{Set}\) has a lot of nice properties, many of which can be summed up in the word "topos". The category of functors \(F : \mathcal{C} \to \textbf{Set}\) inherits many of these nice properties: it too is a topos!

But I haven't said what the

categoryof functors \(F : \mathcal{C} \to \textbf{Set}\) is, yet. Its objects are functors \(F : \mathcal{C} \to \textbf{Set}\) and its morphisms are "natural transformations". These are discussed in Section 3.3.4 of the book, so you may want to read about them and see how they help us think about databases... but we'll get to them soon.I also haven't said what a "topos" is; you can read about those starting in Section 7.2.

Of course practically speaking we are unlikely to have a database where there's a

groupof employees! "Hey, I just multiplied Bob and Mary and got Frank!"But functors \(F : \mathcal{C} \to \mathbf{Grp}\) are important in math: we call these "group objects in the topos of functors \(F : \mathcal{C} \to \textbf{Set}\)", and they behave a lot like groups.

`Sophie wrote: > Is there a reason the cateogry \\(\mathbf{Set}\\) is the "chosen" category when we define databases? The main reason is a practical one: we are often interested in databases that consist of a bunch of sets and functions between these sets. But we are often interested in other kinds, too - and that's the topic of [Lecture 40](https://forum.azimuthproject.org/discussion/2223/lecture-40-chapter-3-relations/p1)! > Will we get interesting properties that we wouldn't get if we just defined a database to be functor from \\(\mathbf{Free}(G)\\) to any category? Yes, lots. The category \\(\textbf{Set}\\) has a lot of nice properties, many of which can be summed up in the word "topos". The category of functors \\(F : \mathcal{C} \to \textbf{Set}\\) inherits many of these nice properties: it too is a topos! But I haven't said what the _category_ of functors \\(F : \mathcal{C} \to \textbf{Set}\\) is, yet. Its objects are functors \\(F : \mathcal{C} \to \textbf{Set}\\) and its morphisms are "natural transformations". These are discussed in Section 3.3.4 of the book, so you may want to read about them and see how they help us think about databases... but we'll get to them soon. I also haven't said what a "topos" is; you can read about those starting in Section 7.2. > Or to a specific category like \\(\mathbf{Grp}\\)? Of course practically speaking we are unlikely to have a database where there's a _group_ of employees! "Hey, I just multiplied Bob and Mary and got Frank!" But functors \\(F : \mathcal{C} \to \mathbf{Grp}\\) are important in math: we call these "group objects in the topos of functors \\(F : \mathcal{C} \to \textbf{Set}\\)", and they behave a lot like groups.`

Keith wrote:

Okay, that's one good way. The category with one object \(\star\), one morphism for each natural number, and addition as composition!

Now, you were talking about functors \( F: \mathbf{Set} \to \mathbf{N}\).

Puzzle.What's a functor \( F: \mathbf{Set} \to \mathbf{N}\) if we make \(\mathbf{N}\) into a category as you've suggested?This is actually a fun question I've never thought about. Let me start. \(\mathbf{N}\) has just one object \(\star\) so \(F\) must send every set to that object.

(So, if you were trying to use such a functor to count the number of elements in sets, it's not going to work.)

\(\mathbf{N}\) has just one invertible morphism, namely the identity \(1_\star\), so \(F\) must send every invertible morphism in \(\mathbf{Set}\) to this identity morphism. You see, functors map invertible morphisms to invertible morphisms. And the invertible morphisms in \(\mathbf{Set}\) are the bijections. So, \(F\) must send every bijection to the identity!

Based on this tiny bit of information, and my intuition, I'll make a wild guess:

Conjecture.Any functor \( F: \mathbf{Set} \to \mathbf{N}\) must send every morphism in \(\textbf{Set}\) to the identity morphism.Can someone prove it or find a counterexample?

`Keith wrote: > Why not simply take \\(\mathbf{N}\\) as the free category on one object and one (non-identity) morphism? Okay, that's one good way. The category with one object \\(\star\\), one morphism for each natural number, and addition as composition! Now, you were talking about functors \\( F: \mathbf{Set} \to \mathbf{N}\\). **Puzzle.** What's a functor \\( F: \mathbf{Set} \to \mathbf{N}\\) if we make \\(\mathbf{N}\\) into a category as you've suggested? This is actually a fun question I've never thought about. Let me start. \\(\mathbf{N}\\) has just one object \\(\star\\) so \\(F\\) must send every set to that object. (So, if you were trying to use such a functor to count the number of elements in sets, it's not going to work.) \\(\mathbf{N}\\) has just one invertible morphism, namely the identity \\(1_\star\\), so \\(F\\) must send every invertible morphism in \\(\mathbf{Set}\\) to this identity morphism. You see, functors map invertible morphisms to invertible morphisms. And the invertible morphisms in \\(\mathbf{Set}\\) are the bijections. So, \\(F\\) must send every bijection to the identity! Based on this tiny bit of information, and my intuition, I'll make a wild guess: **Conjecture.** Any functor \\( F: \mathbf{Set} \to \mathbf{N}\\) must send every morphism in \\(\textbf{Set}\\) to the identity morphism. Can someone prove it or find a counterexample?`

Would something like thing work?

\[ F(X) := \begin{cases} Id_{\mathbb{N}} & \text{ if } X =\varnothing, \\ succ \ \circ \ F(X \setminus \lbrace x \rbrace) & \text{ if } X \not= \varnothing, \end{cases} \]

and,

\[ F(\mathbf{Set}(X,Y)) := F(Y)^{F(X)}. \]

`>**Conjecture.** Any functor \\( F: \mathbf{Set} \to \mathbf{N}\\) must send every morphism in \\(\textbf{Set}\\) to the identity morphism. >Can someone prove it or find a counterexample? Would something like thing work? \\[ F(X) := \begin{cases} Id_{\mathbb{N}} & \text{ if } X =\varnothing, \\\\ succ \ \circ \ F(X \setminus \lbrace x \rbrace) & \text{ if } X \not= \varnothing, \end{cases} \\] and, \\[ F(\mathbf{Set}(X,Y)) := F(Y)^{F(X)}. \\]`

There's something bad going on here, Keith. You told me that \(\mathbf{N}\) has just one object. So, I pointed out that any functor \(F : \mathbf{Set} \to \mathbf{N}\) must send every object of \(\mathbf{Set}\) to that one object, and I wrote:

And yet you seem to be trying to do just that! In your formula you seem to be sending the objects of \(\mathbf{Set}\) to

morphismsof \(\mathbf{N}\). That's called a "level slip".You may want to change your definition of \(\mathbf{N}\) and see if that helps. But I believe you'll have trouble sending both the objects and morphisms of \(\mathbf{Set}\) to something involving natural numbers - even if we restrict attention to finite sets, as you're secretly doing.

I think the solution is to use decategorification and note that the decategorification of \(\mathbf{FinSet}\) is \(\mathbb{N}\), the usual set of natural numbers.

`There's something bad going on here, Keith. You told me that \\(\mathbf{N}\\) has just one object. So, I pointed out that any functor \\(F : \mathbf{Set} \to \mathbf{N}\\) must send every object of \\(\mathbf{Set}\\) to that one object, and I wrote: > So, if you were trying to use such a functor to count the number of elements in sets, it's not going to work. And yet you seem to be trying to do just that! In your formula you seem to be sending the objects of \\(\mathbf{Set}\\) to _morphisms_ of \\(\mathbf{N}\\). That's called a "level slip". You may want to change your definition of \\(\mathbf{N}\\) and see if that helps. But I believe you'll have trouble sending both the objects and morphisms of \\(\mathbf{Set}\\) to something involving natural numbers - even if we restrict attention to finite sets, as you're secretly doing. I think the solution is to use [decategorification](https://ncatlab.org/nlab/show/decategorification) and note that the decategorification of \\(\mathbf{FinSet}\\) is \\(\mathbb{N}\\), the usual set of natural numbers.`

Wait, since a set/finite set is a discrete preordering, and if we treat \(\mathbb(N)\) as a preorder, could we define not a functor (\(\mathbf{Set}\)-functor), but rather a monotone function (\(\mathbf{Bool}\)-functor) (in fact, a strict monoidal monotone)?

\[ F\lbrace \varnothing \rbrace = 0, \\ F(A \cup B) =F(A) +F(B) \]

Edit: Also, let's not forget,

\[ A \subseteq B \Leftrightarrow F(A) \leq F(B) \]

Is \(\mathbf{Bool}\) in some way "a level down" from \(\mathbf{Set}\)?

`Wait, since a set/finite set is a discrete preordering, and if we treat \\(\mathbb(N)\\) as a preorder, could we define not a functor (\\(\mathbf{Set}\\)-functor), but rather a monotone function (\\(\mathbf{Bool}\\)-functor) (in fact, a strict monoidal monotone)? \\[ F\lbrace \varnothing \rbrace = 0, \\\\ F(A \cup B) =F(A) +F(B) \\] Edit: Also, let's not forget, \\[ A \subseteq B \Leftrightarrow F(A) \leq F(B) \\] Is \\(\mathbf{Bool}\\) in some way "a level down" from \\(\mathbf{Set}\\)?`

I argue this conjecture is

falseThis might be true for functions in traditional ZF set theory.

However, category theorists define morphisms on \(\mathbf{Set}\) a little differently. In particular, an

initial objectis considered.(EDIT: After a little reread, I am wrong about this - everyone is using the same definition after all!)

Proof.To start, I am going to write \(\mathbf{1}_\ast\) as \(id_\ast\). This is because if \(\circ\) for \(\mathbf{N}\) is like \(+\) then \(\mathbf{1}_\ast\) feels more like 0...

Let \(\tilde{2}\) be some morphism in \(\mathbf{N}\) where \(\tilde{2} \neq id_\ast\).

For any set \(Y\), consider the unique morphism \(\phi : \varnothing \to Y \). This unique morphism exists because \(\varnothing\) is the

initial objectof \(\mathbf{Set}\) (see nLab).Now define the functor \(F : \mathbf{Set} \to \mathbf{N}\) such that for all \(f : X \to Y \) where \(X \neq \emptyset\) then \( F(f) = id_\ast\) and \(F(\phi) = \tilde{2}\) otherwise.

\(F\) obeys the functor laws and doesn't send everything to the identity morphism.

\(\Box\)

`> **Conjecture.** Any functor \\( F: \mathbf{Set} \to \mathbf{N}\\) must send every morphism in \\(\textbf{Set}\\) to the identity morphism. I argue this conjecture is *false* This might be true for functions in traditional ZF set theory. However, category theorists define morphisms on \\(\mathbf{Set}\\) a little differently. In particular, an *initial object* is considered. (EDIT: After a little reread, I am wrong about this - everyone is using the same definition after all!) **Proof.** To start, I am going to write \\(\mathbf{1}\_\ast\\) as \\(id\_\ast\\). This is because if \\(\circ\\) for \\(\mathbf{N}\\) is like \\(+\\) then \\(\mathbf{1}_\ast\\) feels more like 0... Let \\(\tilde{2}\\) be some morphism in \\(\mathbf{N}\\) where \\(\tilde{2} \neq id_\ast\\). For any set \\(Y\\), consider the unique morphism \\(\phi : \varnothing \to Y \\). This unique morphism exists because \\(\varnothing\\) is the *initial object* of \\(\mathbf{Set}\\) (see [nLab](https://ncatlab.org/nlab/show/initial+object#examples)). Now define the functor \\(F : \mathbf{Set} \to \mathbf{N}\\) such that for all \\(f : X \to Y \\) where \\(X \neq \emptyset\\) then \\( F(f) = id_\ast\\) and \\(F(\phi) = \tilde{2}\\) otherwise. \\(F\\) obeys the functor laws and doesn't send everything to the identity morphism. \\(\Box\\)`

In the employee database example, the objects of \(\mathbf{Set}\) seem to be "the most" abstract entity possible since any property associated to that object is manifested as arrows. For example, in the set of employees, the elements would be non-branded blobs only to be differentiated by their existence and the arrows seem to decorate each of these blobs with certain properties kind of like Mr. Potato Head. Is this a correct view of the objects in general? or is it true for only this specific example?

`In the employee database example, the objects of \\(\mathbf{Set}\\) seem to be "the most" abstract entity possible since any property associated to that object is manifested as arrows. For example, in the set of employees, the elements would be non-branded blobs only to be differentiated by their existence and the arrows seem to decorate each of these blobs with certain properties kind of like Mr. Potato Head. Is this a correct view of the objects in general? or is it true for only this specific example?`

Yes actually.

We could have said that,

\[ F(\text{Employee}) = \lbrace \bullet ,\bigstar ,\blacklozenge ,\blacksquare \rbrace \\ F(\text{Department}) = \lbrace \ast,\circ ,\triangle , \square \rbrace \\ F(\text{String}) = \lbrace \text{"oui"}, \text{"bluer"}, \text{"bop"}\rbrace \]

with,

\[ \begin{align} F(\text{WorkIn}) = \\ \bullet \mapsto \circ, \\ \bigstar \mapsto \triangle , \\ \blacklozenge \mapsto \ast ,\\ \blacksquare \mapsto \square, \end{align} \]

and,

\[ \begin{align} F(\text{DepartmentName}) = \\ \ast \mapsto \text{"bop"}, \\ \circ \mapsto \text{"bop"}, \\ \triangle \mapsto \text{"oui"}, \\ \square \mapsto \text{"bluer"}. \end{align} \]

This is a perfectly valid (if not very weird) instance.

`Yes actually. We could have said that, \\[ F(\text{Employee}) = \lbrace \bullet ,\bigstar ,\blacklozenge ,\blacksquare \rbrace \\\\ F(\text{Department}) = \lbrace \ast,\circ ,\triangle , \square \rbrace \\\\ F(\text{String}) = \lbrace \text{"oui"}, \text{"bluer"}, \text{"bop"}\rbrace \\] with, \\[ \begin{align} F(\text{WorkIn}) = \\\\ \bullet \mapsto \circ, \\\\ \bigstar \mapsto \triangle , \\\\ \blacklozenge \mapsto \ast ,\\\\ \blacksquare \mapsto \square, \end{align} \\] and, \\[ \begin{align} F(\text{DepartmentName}) = \\\\ \ast \mapsto \text{"bop"}, \\\\ \circ \mapsto \text{"bop"}, \\\\ \triangle \mapsto \text{"oui"}, \\\\ \square \mapsto \text{"bluer"}. \end{align} \\] This is a perfectly valid (if not very weird) instance.`

Michael: in informal math, a perfectly fine object of \( \mathbf{ Set}\) is

$$ \{ \text{Michael}, \text{Keith} \} . $$ This doesn't seem very abstract to me.

In more formal set theory we might identify you by numbers. That's a bit more abstract... but remember, computers do something similar, encoding everything as bit strings.

The objects of our database schema are what I'd call

reallyabstract. The database, \( F\), sends these objects to sets, which I'd consider 'concrete'.`Michael: in informal math, a perfectly fine object of \\( \mathbf{ Set}\\) is \[ \\{ \text{Michael}, \text{Keith} \\} . \] This doesn't seem very abstract to me. In more formal set theory we might identify you by numbers. That's a bit more abstract... but remember, computers do something similar, encoding everything as bit strings. The objects of our database schema are what I'd call _really_ abstract. The database, \\( F\\), sends these objects to sets, which I'd consider 'concrete'.`

01001001011011100110010001100101011001010110010000100001

`> In more formal set theory we might identify you by numbers. That's a bit more abstract... but remember, computers do something similar, encoding everything as bit strings. 01001001011011100110010001100101011001010110010000100001`

Conceptually speaking, a set is just a bunch of labeled dots.

That is to say, it's only the labeling that really matters, and any and all internal structure of objects is to be ignored.

`Conceptually speaking, a set is just a bunch of labeled dots. That is to say, it's only the labeling that really matters, and any and all internal structure of objects is to be ignored.`

You might be interested in combinatorial species, Keith. Plenty of fun categorical constructions to explore in that field, fwiw. Even the Day convolution that John mentioned in another thread shows up concretely there.

`> Conceptually speaking, a set is just a bunch of labeled dots. You might be interested in [combinatorial species](https://en.wikipedia.org/wiki/Combinatorial_species), Keith. Plenty of fun categorical constructions to explore in that field, fwiw. Even the Day convolution that John mentioned in another thread shows up concretely there.`

I know of them. I haven't really played with them.

I suspect Iverson brackets and combinatorial species go together like bread and butter.

`I know of them. I haven't really played with them. I suspect [Iverson brackets](https://en.wikipedia.org/wiki/Iverson_bracket) and combinatorial species go together like bread and butter.`

John wrote:

So in this case, we can have the objects be a set of numbers or equivalently identification using numbers can also be written as an arrow for example called employee ID. So what I was curious about was(with hopefully better wording than before) when dealing with categories or functors, must we write anything that can be written as arrows as arrows or can we just keep it inside the object?

But I think I get your point. I guess when writing any of this out you must use something to represent the object which includes using a dot like I was thinking but that is arbitrary of the writer... which made me realize the database schema is actually the "amorphous blob" that I had in mind on more levels than I had initially thought since categories are also objects. Now I can see why they call them categories.

`John wrote: >In more formal set theory we might identify you by numbers. So in this case, we can have the objects be a set of numbers or equivalently identification using numbers can also be written as an arrow for example called employee ID. So what I was curious about was(with hopefully better wording than before) when dealing with categories or functors, must we write anything that can be written as arrows as arrows or can we just keep it inside the object? But I think I get your point. I guess when writing any of this out you must use something to represent the object which includes using a dot like I was thinking but that is arbitrary of the writer... which made me realize the database schema is actually the "amorphous blob" that I had in mind on more levels than I had initially thought since categories are also objects. Now I can see why they call them categories.`

Michael Hong wrote:

In the category \(\mathbf{Set}\), the objects are sets! That's unarguable. To go further, you need to make some decisions about what you mean by "set". That's what set theory is all about. It's a big subject, with many different approaches. But almost any approach to set theory is willing to accept a set of numbers as an example of a set.

A set of

peopleis a bit trickier, because a person is (most likely) not a mathematical entity. But as I said before, computers encode everything in terms of mathematical entities, so in work on databases we don't actually need to deal with sets of people, just sets whose elements correspond to people in some way.`Michael Hong wrote: > So in this case, we can have the objects be a set of numbers [...?] In the category \\(\mathbf{Set}\\), the objects are sets! That's unarguable. To go further, you need to make some decisions about what you mean by "set". That's what [set theory](https://en.wikipedia.org/wiki/Set_theory) is all about. It's a big subject, with many different approaches. But almost any approach to set theory is willing to accept a set of numbers as an example of a set. A set of _people_ is a bit trickier, because a person is (most likely) not a mathematical entity. But as I said before, computers encode everything in terms of mathematical entities, so in work on databases we don't actually need to deal with sets of people, just sets whose elements correspond to people in some way.`

Matthew wrote:

Hey, I think you're right! If I get the gist of your argument, it goes like this. Pick a nonempty set \(S\) and define a functor \(F: \mathbf{Set} \to \mathbf{N}\) that sends the unique function \(f: \emptyset \to S\) to some non-identity morphism in \(\mathbf{N}\) and all other morphisms to the identity. Check that this is a functor.

(We need \(S\) to be nonempty so that \(f\) isn't an identity morphism, so that \(F(f)\) can be chosen to be a non-identity morphism.)

Very nice!

`Matthew wrote: > I argue this conjecture is _false_. Hey, I think you're right! If I get the gist of your argument, it goes like this. Pick a nonempty set \\(S\\) and define a functor \\(F: \mathbf{Set} \to \mathbf{N}\\) that sends the unique function \\(f: \emptyset \to S\\) to some non-identity morphism in \\(\mathbf{N}\\) and all other morphisms to the identity. Check that this is a functor. (We need \\(S\\) to be nonempty so that \\(f\\) isn't an identity morphism, so that \\(F(f)\\) can be chosen to be a non-identity morphism.) Very nice!`

The conjecture really is compelling, however. Here's a little modification I was thinking of to get it to work.

Consider \(\mathbf{Set}^\dagger\), which is the same as \(\mathbf{Set}\) but without \(\emptyset\).

Puzzle MD 1.Show that any functor \( F: \mathbf{Set}^\dagger \to \mathbf{N}\) must send every morphism in \(\textbf{Set}^\dagger \) to the identity morphism.`The conjecture really is compelling, however. Here's a little modification I was thinking of to get it to work. Consider \\(\mathbf{Set}^\dagger\\), which is the same as \\(\mathbf{Set}\\) but without \\(\emptyset\\). **Puzzle MD 1.** Show that any functor \\( F: \mathbf{Set}^\dagger \to \mathbf{N}\\) must send every morphism in \\(\textbf{Set}^\dagger \\) to the identity morphism.`

John, Matthew: I think there is a mild problem with your construction of a non-trivial functor \(F\colon \mathbf{Set}\to \mathbb{N}\). You have the map \(f\colon \emptyset\to \mathbb{R}\), with \(F(f)=n\), and with all other functions going to \(\mathrm{id}\). Let \(t \colon \mathbb{R}\to \{\ast\}\) be the function that send every number to \(\ast\). Of course with that domain and that codomain you have no choice. Then we have the composite \(t\circ f\colon \emptyset \to (\ast)\). We should then have \(n=\mathrm{id}\circ n = F(t)\circ F(f)= F(t\circ f) =\mathrm{id} \).

We need to send

allinitial functions to \(n\). I guess we have a functor from \(\mathbf{Set}\) to the category with two objects \(a\) and \(b\) and with precisely one non-identity morphism \(a\to b\): the empty set gets sent to \(a\), everything else goes to \(b\). The functor you want from \(\mathbf{Set}\) to \(\mathbb{N}\) factors through this.`John, Matthew: I think there is a mild problem with your construction of a non-trivial functor \\(F\colon \mathbf{Set}\to \mathbb{N}\\). You have the map \\(f\colon \emptyset\to \mathbb{R}\\), with \\(F(f)=n\\), and with all other functions going to \\(\mathrm{id}\\). Let \\(t \colon \mathbb{R}\to \\{\ast\\}\\) be the function that send every number to \\(\ast\\). Of course with that domain and that codomain you have no choice. Then we have the composite \\(t\circ f\colon \emptyset \to \(\ast\)\\). We should then have \\(n=\mathrm{id}\circ n = F(t)\circ F(f)= F(t\circ f) =\mathrm{id} \\). We need to send *all* initial functions to \\(n\\). I guess we have a functor from \\(\mathbf{Set}\\) to the category with two objects \\(a\\) and \\(b\\) and with precisely one non-identity morphism \\(a\to b\\): the empty set gets sent to \\(a\\), everything else goes to \\(b\\). The functor you want from \\(\mathbf{Set}\\) to \\(\mathbb{N}\\) factors through this.`

"Mild problem" - like it completely doesn't work? \(\qquad \)

Simon is much nicer than I am.

So is this a reasonable revised conjecture?

Revised Conjecture.Every functor \(F: \mathbf{Set} \to \mathbb{N}\) is of this form: \(F\) sends every object to \(\star\), it sends every morphism \(f: \emptyset \to Y\) to the same morphism \(n : \star \to \star\), and it sends every morphism \(f: X \to Y\) with \(X \ne \emptyset\) to the identity morphism \(1_\star : \star \to \star\).Perhaps it's better to phrase this conjecture in terms of functors from \(\mathbf{Set}\) to the category Simon brought in, also known as "\(\mathbf{2}\)": the category with two objects and one morphism from the first to the second.

`"Mild problem" - like it completely doesn't work? \\(\qquad \\) <img src = "http://math.ucr.edu/home/baez/emoticons/tongue2.gif"> Simon is much nicer than I am. So is this a reasonable revised conjecture? **Revised Conjecture.** Every functor \\(F: \mathbf{Set} \to \mathbb{N}\\) is of this form: \\(F\\) sends every object to \\(\star\\), it sends every morphism \\(f: \emptyset \to Y\\) to the same morphism \\(n : \star \to \star\\), and it sends every morphism \\(f: X \to Y\\) with \\(X \ne \emptyset\\) to the identity morphism \\(1\_\star : \star \to \star\\). Perhaps it's better to phrase this conjecture in terms of functors from \\(\mathbf{Set}\\) to the category Simon brought in, also known as "\\(\mathbf{2}\\)": the category with two objects and one morphism from the first to the second.`

Well the category \(\mathbf{2}\),

\[ \ast \rightarrow \bullet, \]

is really, up to isomorphism (aka relabeling), just our old friend \(\mathbf{Bool}\),

\[ \texttt{false} \rightarrow \texttt{true}, \]

which, because if such functors into \(\mathbb{N}\) out of \(\mathbf{Set}\) must factor through \(\mathbf{2} \cong \mathbf{Bool} \), that would imply that such "functors" are exactly the

monotone functionswe studied in the first two chapters.Edit, I believe Simon's constraints must amount to the diagram,

\[ \begin{matrix} \mathbf{Set }& & \\ f \downarrow & \overset F \searrow & \\ \mathbf{2} & \begin{matrix} \overset l \leftarrow \\ \underset r\rightarrow \end{matrix} & \mathbb{N}. \end{matrix} \]

`Well the category \\(\mathbf{2}\\), \\[ \ast \rightarrow \bullet, \\] is really, up to isomorphism (aka relabeling), just our old friend \\(\mathbf{Bool}\\), \\[ \texttt{false} \rightarrow \texttt{true}, \\] which, because if such functors into \\(\mathbb{N}\\) out of \\(\mathbf{Set}\\) must factor through \\(\mathbf{2} \cong \mathbf{Bool} \\), that would imply that such "functors" are exactly the *monotone functions* we studied in the first two chapters. Edit, I believe Simon's constraints must amount to the diagram, \\[ \begin{matrix} \mathbf{Set }& & \\\\ f \downarrow & \overset F \searrow & \\\\ \mathbf{2} & \begin{matrix} \overset l \leftarrow \\\\ \underset r\rightarrow \end{matrix} & \mathbb{N}. \end{matrix} \\]`

Thanks for the catch, Simon! I fixed my argument in my post.

Now that you mention this, it is very clear what is going on.

`Thanks for the catch, Simon! I fixed my argument in my post. > We need to send *all* initial functions to \\(n\\). I guess we have a functor from \\(\mathbf{Set}\\) to the category with two objects \\(a\\) and \\(b\\) and with precisely one non-identity morphism \\(a\to b\\): the empty set gets sent to \\(a\\), everything else goes to \\(b\\). The functor you want from \\(\mathbf{Set}\\) to \\(\mathbb{N}\\) factors through this. Now that you mention this, it is very clear what is going on.`

In the scale of mathematical disasters this construction really just suffered a minor glitch IMO.

If you want to see total disaster, one could look at David Hilbert's "proof" of the continuum hypothesis in

On the Infinite(1926).Hilbert is so revered, and that proof is such a failure, the mathematicians I know are reluctant to talk about it.

I am no Hilbert. I know I make mistakes, even grave ones.

I came here to learn.

For this I am thankful for the patience and guidance of the people on this forum as I muddle about.

I am reasonably confident this revised conjecture is true.

The second half is essentially the puzzle I wrote:

Here's my attempt at an answer.

Proof.Take any function \(f : A \to B\) in \(\mathbf{Set}^\dagger\).

We have to prove \(F(f) = id_{\star}\).

Since \(A\) is not empty, there is some \(a \in A\).

Let \(g : B \to A\) be the constant function where \(g(b) := a\) for all \(b \in B\).

We have

$$(g \circ f) \circ (g \circ f) = (g \circ f)$$ Applying the functor \(F\) to either side gives:

$$ F((g \circ f) \circ (g \circ f)) = F(g \circ f) $$ Since \(F\) is a functor, it distributes across morphism composition:

$$ F(g \circ f) \circ F(g \circ f) = F(g \circ f) $$ There's only one idempotent element of \(\mathbf{N}\) and it is \(id_{\star}\). Hence

$$ F(g \circ f) = id_{\star} $$ Distributing gives

$$ F(g) \circ F(f) = id_{\star} $$ In the monoid \(\langle \mathbb{N}, 0, + \rangle\), if \(x + y = 0\) then \(x = y = 0\). We also have the monoid \(\langle \mathbf{N}, id_{\star}, \circ \rangle \) is isomorphic to \(\langle \mathbb{N}, 0, + \rangle\). Hence:

$$ F(g) = F(f) = id_{\star} $$ Which gives \(F(f) = id_{\star}\) as desired.

\(\Box \)

`> "Mild problem" - like it completely doesn't work? > > Simon is much nicer than I am. In the scale of mathematical disasters this construction really just suffered a minor glitch IMO. If you want to see total disaster, one could look at David Hilbert's "proof" of the continuum hypothesis in [*On the Infinite* (1926)](https://math.dartmouth.edu/~matc/Readers/HowManyAngels/Philosophy/Philosophy.html). Hilbert is so revered, and that proof is such a failure, the mathematicians I know are reluctant to talk about it. I am no Hilbert. I know I make mistakes, even grave ones. I came here to learn. For this I am thankful for the patience and guidance of the people on this forum as I muddle about. > **Revised Conjecture.** Every functor \\(F: \mathbf{Set} \to \mathbb{N}\\) is of this form: \\(F\\) sends every object to \\(\star\\), it sends every morphism \\(f: \emptyset \to Y\\) to the same morphism \\(n : \star \to \star\\), and it sends every morphism \\(f: X \to Y\\) with \\(X \ne \emptyset\\) to the identity morphism \\(1\_\star : \star \to \star\\). I am reasonably confident this revised conjecture is true. The second half is essentially the puzzle I wrote: > Let \\(\mathbf{Set}^\dagger\\) be the same as \\(\mathbf{Set}\\) but without \\(\emptyset\\). > > **Puzzle MD 1.** Show that any functor \\( F: \mathbf{Set}^\dagger \to \mathbf{N}\\) must send every morphism in \\(\textbf{Set}^\dagger \\) to the identity morphism. Here's my attempt at an answer. **Proof.** Take any function \\(f : A \to B\\) in \\(\mathbf{Set}^\dagger\\). We have to prove \\(F(f) = id_{\star}\\). Since \\(A\\) is not empty, there is some \\(a \in A\\). Let \\(g : B \to A\\) be the constant function where \\(g(b) := a\\) for all \\(b \in B\\). We have \[(g \circ f) \circ (g \circ f) = (g \circ f)\] Applying the functor \\(F\\) to either side gives: \[ F((g \circ f) \circ (g \circ f)) = F(g \circ f) \] Since \\(F\\) is a functor, it distributes across morphism composition: \[ F(g \circ f) \circ F(g \circ f) = F(g \circ f) \] There's only one [idempotent](https://en.wikipedia.org/wiki/Idempotence) element of \\(\mathbf{N}\\) and it is \\(id_{\star}\\). Hence \[ F(g \circ f) = id_{\star} \] Distributing gives \[ F(g) \circ F(f) = id_{\star} \] In the monoid \\(\langle \mathbb{N}, 0, + \rangle\\), if \\(x + y = 0\\) then \\(x = y = 0\\). We also have the monoid \\(\langle \mathbf{N}, id_{\star}, \circ \rangle \\) is isomorphic to \\(\langle \mathbb{N}, 0, + \rangle\\). Hence: \[ F(g) = F(f) = id_{\star} \] Which gives \\(F(f) = id_{\star}\\) as desired. \\(\Box \\)`