#### Howdy, Stranger!

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

Options

# Lecture 39 - Chapter 3: Databases

edited June 2018

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:

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

2. 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:

1. 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:

1. $$\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:

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

2. 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.

3. 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?

To read other lectures go here.

«1

## Comments

• Options
1.
edited June 2018

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)$$

Comment Source: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)$ 
• Options
2.
edited June 2018

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}.$

Comment Source:>**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}. \$
• Options
3.
edited June 2018

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?

Comment Source: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?
• Options
4.

But still, what's the number?

Oh, the number is 16.

Comment Source:>But still, what's the number? Oh, the number is 16. 
• Options
5.
edited June 2018

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.

Comment Source:**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.
• Options
6.
edited June 2018

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.

Comment Source: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.
• Options
7.
edited June 2018

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.

(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.)

Comment Source: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.)
• Options
8.

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}$$?

Comment Source: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}\$$?
• Options
9.
edited June 2018

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?

Comment Source:> 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?
• Options
10.

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 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 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)$$.

Comment Source:**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)\$$.
• Options
11.

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?

Comment Source: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?
• Options
12.
edited June 2018

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.)

Comment Source: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.)
• Options
13.

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!

Comment Source:> 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!
• Options
14.
edited June 2018

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 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 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:

CREATE TABLE Person (
Name VARCHAR(128) PRIMARY KEY,
BestFriend VARCHAR(128) NOT NULL REFERENCES Person (Name)
);


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. 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:

CREATE TABLE Person (
Name VARCHAR(128) PRIMARY KEY,
BestFriend VARCHAR(128) REFERENCES Person (Name)
);


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.

Comment Source:> **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.
• Options
15.
edited June 2018

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.

Comment Source: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.
• Options
16.
edited June 2018

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 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.

Comment Source:> 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.
• Options
17.
edited June 2018

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 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$$.

Comment Source: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\$$.
• Options
18.

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.

Comment Source: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. 
• Options
19.

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!

Comment Source: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!
• Options
20.
edited June 2018

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

Comment Source:Why not simply take \$$\mathbb{N}\$$ as the free category on one object and one (non-identity) morphism?
• Options
21.
edited June 2018

Keith wrote:

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.

Comment Source:[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.
• Options
22.
edited June 2018

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'...

Comment Source: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'...
• Options
23.

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.

Comment Source: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.
• Options
24.

@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.

Comment Source:@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.
• Options
25.

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!

Comment Source: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!
• Options
26.

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.

Comment Source: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.
• Options
27.
edited June 2018

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.$

Comment Source: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. \$
• Options
28.
edited June 2018
Comment Source:Here you go, Owen: https://forum.azimuthproject.org/discussion/2227/history-of-databases
• Options
29.
edited June 2018

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!

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.

Comment Source: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. 
• Options
30.
edited June 2018

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?

Comment Source: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?
• Options
31.
edited June 2018

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)}.$

Comment Source:>**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)}. \$
• Options
32.
edited June 2018

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 and note that the decategorification of $$\mathbf{FinSet}$$ is $$\mathbb{N}$$, the usual set of natural numbers.

Comment Source: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. 
• Options
33.
edited June 2018

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}$$?

Comment Source: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}\$$? 
• Options
34.
edited June 2018

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).

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$$

Comment Source:> **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\$$
• Options
35.
edited June 2018

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?

Comment Source: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?
• Options
36.
edited June 2018

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.

Comment Source: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.
• Options
37.
edited June 2018

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'.

Comment Source: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'. 
• Options
38.
edited June 2018

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

Comment Source:> 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
• Options
39.

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.

Comment Source: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.
• Options
40.
edited June 2018

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

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.

Comment Source:> 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.
• Options
41.

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

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

Comment Source: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.
• Options
42.
edited June 2018

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.

Comment Source: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. 
• Options
43.

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 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.

Comment Source: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.
• Options
44.
edited June 2018

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!

Comment Source: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!
• Options
45.
edited June 2018

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.

Comment Source: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.
• Options
46.
edited June 2018

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.

Comment Source: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.
• Options
47.
edited June 2018

"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.

Comment Source:"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.
• Options
48.
edited June 2018

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}$

Comment Source: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} \$ 
• Options
49.

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.

Comment Source: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.
• Options
50.
edited June 2018

"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).

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 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$$

Comment Source:> "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 \$$
Sign In or Register to comment.