#### Howdy, Stranger!

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

Options

# Lecture 43 - Chapter 3: Natural Transformations

edited February 2020

We've been having fun with databases using categories and functors. To go any further we need 'natural transformations'. These are one of the most important aspects of category theory. They give it a special flavor different from almost all previous branches of mathematics!

In most branches of math you study gadgets and maps between gadgets, like:

• sets and functions between sets,
• vector spaces and linear maps between vector spaces,
• posets and monotone functions between posets,

and so on.

We do this in category theory too! We have categories and functors between categories. But category theory has an extra layer. It also has natural transformations between functors.

The reason is not hard to find. Some people think categories are abstract, but I don't. When you say the word 'category', a picture sort of like this pops into my head: It's a bunch of objects, which look like dots, and a bunch of morphisms, which look like arrows between dots.

Now, you might object that this is a picture of a graph, not a category. And you'd be right! In a category we can compose morphisms, and we also have identity morphisms. So a more detailed mental picture of the same category would look like this: Let's call this category $$\mathcal{C}$$. Then, a functor $$F$$ from this category $$\mathcal{C}$$ to some other category $$\mathcal{D}$$ would look a bit like this: $$F$$ maps each object of $$\mathcal{C}$$ to an object in $$\mathcal{D}$$, and it maps each morphism to a morphism. So, a functor from $$\mathcal{C}$$ to $$\mathcal{D}$$ is like a picture of $$\,\mathcal{C}$$ drawn on the blackboard of $$\,\mathcal{D}$$.

The category $$\mathcal{D}$$ may, of course, contain other objects and morphisms that aren't in our picture. To keep things simple I haven't drawn those. Also, two objects or morphisms of $$\mathcal{C}$$ may get mapped to the same object in $$\mathcal{D}$$, so the picture of $$\mathcal{C}$$ in $$\mathcal{D}$$ could be 'squashed down'. But I haven't drawn that either! You can draw these other possibilities.

Now for the fun part.

Suppose we have two functors from $$\mathcal{C}$$ to $$\mathcal{D}$$, say $$F$$ and $$G$$. Let me draw them in a stripped-down way: Then we can define a 'natural transformation' from $$F$$ to $$G$$, written $$\alpha : F \Rightarrow G$$. It looks like this: For each object $$x \in \mathcal{C}$$, the natural transformation gives a morphism from $$F(x)$$ to $$G(x)$$. In the picture above I've drawn every objects of $$\mathcal{C}$$ as a mere dot, but that's a bit sloppy. So let's give all the objects and morphisms names: Now we see more clearly that for each object $$x \in \mathcal{C}$$, the natural transformation $$\alpha$$ gives a morphism $$\alpha_x : F(x) \to G(x)$$.

Note that this creates a lot of parallelograms in our picture... or squares, if you draw them like this: What makes the transformation natural is that all these squares must 'commute': that is, going down and across gives the same morphism as going across and down.

It takes a while to see why this it's so important, but this condition is one of the first really big ideas in category theory. Ways of going between functors that feel 'natural' in an intuitive sense, meaning that they don't involve disorganized random choices, tend to be natural in this technical sense! And it turns out that one can do a lot using this idea.

Indeed, when Eilenberg and Mac Lane came out with their first paper on category theory in 1945, the main topic was natural transformations. Mac Lane later said:

I didn't invent categories to study functors; I invented them to study natural transformations.

Okay, now let me give the formal definition:

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

$$\alpha_x : F(x) \to G(x)$$ for each object $$x \in \mathcal{C}$$. We say the transformation $$\alpha$$ is natural if for each morphism $$f : x \to y$$ in $$\mathcal{C}$$, this square commutes: In other words,

$$G(f) \alpha_x = \alpha_y F(f) .$$ We call a square diagram of this sort a naturality square.

Okay, now let's start figuring out what natural transformations are good for!

Puzzle 126. Let $$\mathcal{C}$$ be the free category on this graph: If we treat this as a database schema, a functor $$F: \mathcal{C} \to \mathbf{Set}$$ is a database built using this schema, and you can draw it as a table, like this:

$\begin{array}{c|c} \text{People} & \mathrm{FriendOf} \\ \hline Alice & Bob \\ Bob & Alice \\ Stan & Alice \\ Tyler & Stan \\ \end{array}$

Suppose $$G: \mathcal{C} \to \mathbf{Set}$$ is another such database:

$\begin{array}{c|c} \text{People} & \mathrm{FriendOf} \\ \hline Alice & Bob \\ Bob & Alice \\ Stan & Alice \\ Tyler & Stan \\ Mei-Chu & Stan \\ \end{array}$

Can you find a natural transformation $$\alpha : F \Rightarrow G$$ in this example? What is its practical meaning: that is, what could it be used for? What is the significance of naturality in this example?

Puzzle 127. Suppose $$H : \mathcal{C} \to \mathbf{Set}$$ is yet another database built using the same schema, namely

$\begin{array}{c|c} \text{People} & \mathrm{FriendOf} \\ \hline Alice & Bob \\ Bob & Alice \\ Tyler & Bob \\ \end{array}$

Can you find a natural transformation $$\beta : F \Rightarrow H$$? What is its practical meaning? What is the significance of naturality in this example?

Puzzle 128. How many natural transformations $$\gamma: H \Rightarrow H$$ are there? What is their practical meaning?

To read other lectures go here.

• Options
1.
edited June 2018

I was always quite confused by natural transformations, but it seems they're just a selection of morphisms in the target category? How interesting!

Puzzle 126. Define $$\alpha_{\textrm{People}}$$ to be the inclusion map between the sets $$\{\textrm{Alice}, \textrm{Bob}, \textrm{Stan}, \textrm{Tyler}\}$$ and $$\{\textrm{Alice}, \textrm{Bob}, \textrm{Stan}, \textrm{Tyler}, \textrm{Mei-Chu}\}$$. As a restriction of the identity function, all squares commute.

Practically speaking, the inclusion map allows us to extend a database in a consistent way. As long as all relations in the source database are preserved by the target database, we can add new rows.

Puzzle 127. Let $$\alpha_{\textrm{People}}$$ be the identity map on everyone except Stan, who instead gets mapped to Bob. It is notable that the database instance $$H$$ replaces Stan with Bob as Tyler's friend, which ensures that all induced squares commute.

This seems to be a kind of reduction or compaction, where equivalent rows are coalesced and existing relationships involving the coalesced rows are updated. It reminds me a lot of minimization of deterministic finite-state automata.

Puzzle 128. We can leave everything the same (identity) or project Tyler onto Alice. We cannot project Alice onto Tyler or swap Tyler and Alice, since $$\mathrm{FriendOf}(\alpha(\textrm{Bob})) = \textrm{Alice} \neq \textrm{Tyler} = \alpha(\mathrm{FriendOf}(\textrm{Bob}))$$.

Comment Source:I was always quite confused by natural transformations, but it seems they're just a selection of morphisms in the target category? How interesting! **Puzzle 126.** Define \$$\alpha_{\textrm{People}}\$$ to be the inclusion map between the sets \$$\\{\textrm{Alice}, \textrm{Bob}, \textrm{Stan}, \textrm{Tyler}\\}\$$ and \$$\\{\textrm{Alice}, \textrm{Bob}, \textrm{Stan}, \textrm{Tyler}, \textrm{Mei-Chu}\\}\$$. As a restriction of the identity function, all squares commute. Practically speaking, the inclusion map allows us to extend a database in a consistent way. As long as all relations in the source database are preserved by the target database, we can add new rows. **Puzzle 127.** Let \$$\alpha_{\textrm{People}}\$$ be the identity map on everyone except Stan, who instead gets mapped to Bob. It is notable that the database instance \$$H\$$ replaces Stan with Bob as Tyler's friend, which ensures that all induced squares commute. This seems to be a kind of reduction or compaction, where equivalent rows are coalesced and existing relationships involving the coalesced rows are updated. It reminds me a lot of [minimization of deterministic finite-state automata](https://en.wikipedia.org/wiki/DFA_minimization). **Puzzle 128.** We can leave everything the same (identity) or project Tyler onto Alice. We cannot project Alice onto Tyler or swap Tyler and Alice, since \$$\mathrm{FriendOf}(\alpha(\textrm{Bob})) = \textrm{Alice} \neq \textrm{Tyler} = \alpha(\mathrm{FriendOf}(\textrm{Bob}))\$$. 
• Options
2.
edited June 2018

Jonathan wrote:

I was always quite confused by natural transformations, but it seems they're just a selection of morphisms in the target category? How interesting!

Yes!

Well, a transformation between functors $$F, G : \mathcal{C} \to \mathcal{D}$$ is just an arbitrary selection of a morphism $$\alpha_x : F(x) \to G(x)$$ in the target category for each object $$x$$ in the source category. That's enough to create the vertical 'struts' in this picture: But it's natural when the squares with these struts as their vertical sides commute. And that's the cool part.

Your answer to Puzzle 126 is very nice, and the nugget of insight lurks here:

Practically speaking, the inclusion map allows us to extend a database in a consistent way.

The commuting of the squares, which makes our transformation 'natural', is a kind of consistency condition!

This seems to be a kind of reduction or compaction, where equivalent rows are coalesced and existing relationships involving the coalesced rows are updated.

Right, and the commuting of the naturality squares says we are doing this in a consistent way.

It is notable that the database instance $$H$$ replaces Stan with Bob as Tyler's friend, which ensures that all induced squares commute.

Maybe someone can expound a bit more on the notion of 'consistency' that I'm vaguely alluding to. All I mean is that a bunch of squares commute... but it's good to try to tease out the meaning of this, and express it in something resembling plain English.

Comment Source:Jonathan wrote: > I was always quite confused by natural transformations, but it seems they're just a selection of morphisms in the target category? How interesting! Yes! Well, a **transformation** between functors \$$F, G : \mathcal{C} \to \mathcal{D}\$$ is just an arbitrary selection of a morphism \$$\alpha_x : F(x) \to G(x) \$$ in the target category for each object \$$x\$$ in the source category. That's enough to create the vertical 'struts' in this picture: <center><img src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/diagram_natural_transformation.png"></center> But it's **natural** when the squares with these struts as their vertical sides _commute_. And that's the cool part. Your answer to Puzzle 126 is very nice, and the nugget of insight lurks here: > Practically speaking, the inclusion map allows us to extend a database in a consistent way. The commuting of the squares, which makes our transformation 'natural', is a kind of _consistency condition!_ Your answer to Puzzle 127 is also very nice: > This seems to be a kind of reduction or compaction, where equivalent rows are coalesced and existing relationships involving the coalesced rows are updated. Right, and the commuting of the naturality squares says we are doing this in a _consistent_ way. > It is notable that the database instance \$$H\$$ replaces Stan with Bob as Tyler's friend, which ensures that all induced squares commute. Maybe someone can expound a bit more on the notion of 'consistency' that I'm vaguely alluding to. All I mean is that a bunch of squares commute... but it's good to try to tease out the meaning of this, and express it in something resembling plain English.
• Options
3.
edited June 2018

John wrote:

Maybe someone can expound a bit more on the notion of 'consistency' that I'm vaguely alluding to. All I mean is that a bunch of squares commute... but it's good to try to tease out the meaning of this, and express it in something resembling plain English.

Well, I'm not sure if this is exactly what you're referring to, but maybe it's close?

Generally speaking, homomorphisms identify a substructure of a target object that resembles (i.e. preserves the behavior of) the source object. This is why group homomorphisms identify subgroups of the codomain -- though you could also take the perspective that this is why we define subgroups the way we do.

Functors are "just" homomorphisms between categories, so a functor identifies a subcategory of the codomain. Thus, given two functors from a common source category, we obtain two subcategories of the target category. It seems like a natural transformation ought to be a homomorphism between these two subcategories. Perhaps the strange part is that this homomorphism is "internal" to the containing category: it decomposes into morphisms between pairs of objects across the subcategories. I'm tempted to call this a "representation" of a functor between the two subcategories, but I know that word is heavily loaded in category theory.

On the other hand, there seems to be no guarantee that an object $$F(X)$$ must correspond with exactly one object $$G(X)$$. For instance, we can let $$F$$ project $$C$$ all the way down to the one-object one-morphism category, and let $$G$$ leave $$C$$ unchanged. If a natural transformation $$\alpha$$ exists between $$F$$ and $$G$$, it must necessarily associate a morphism $$\alpha_X : \mathbf{1} \to X$$ for every object in $$C$$. This is an extreme example, but if a situation even remotely like this is possible, then natural transformations can't induce a functor, since it would need to associate multiple objects in $$G(C)$$ with a single object in $$F(C)$$.

Comment Source:John wrote: > Maybe someone can expound a bit more on the notion of 'consistency' that I'm vaguely alluding to. All I mean is that a bunch of squares commute... but it's good to try to tease out the meaning of this, and express it in something resembling plain English. Well, I'm not sure if this is exactly what you're referring to, but maybe it's close? Generally speaking, homomorphisms identify a substructure of a target object that resembles (i.e. preserves the behavior of) the source object. This is why group homomorphisms identify subgroups of the codomain -- though you could also take the perspective that this is _why_ we define subgroups the way we do. Functors are "just" homomorphisms between categories, so a functor identifies a subcategory of the codomain. Thus, given two functors from a common source category, we obtain two subcategories of the target category. It seems like a natural transformation ought to be a homomorphism between these two subcategories. Perhaps the strange part is that this homomorphism is "internal" to the containing category: it decomposes into morphisms between pairs of objects across the subcategories. I'm tempted to call this a "representation" of a functor between the two subcategories, but I know that word is heavily loaded in category theory. On the other hand, there seems to be no guarantee that an object \$$F(X)\$$ must correspond with exactly one object \$$G(X)\$$. For instance, we can let \$$F\$$ project \$$C\$$ all the way down to the one-object one-morphism category, and let \$$G\$$ leave \$$C\$$ unchanged. If a natural transformation \$$\alpha\$$ exists between \$$F\$$ and \$$G\$$, it must necessarily associate a morphism \$$\alpha_X : \mathbf{1} \to X\$$ for every object in \$$C\$$. This is an extreme example, but if a situation even remotely like this is possible, then natural transformations _can't_ induce a functor, since it would need to associate multiple objects in \$$G(C)\$$ with a single object in \$$F(C)\$$.
• Options
4.
edited June 2018

Reading through Jonathan's answers, it seems like what natural transformations are doing is overlaying each instantiation of graphs to find similarities and if there is any leftovers in the domain then it folds it so that edges line up in the most natural way kind of like origami where the rule is you have to match corners ie no half folds meaning you must match points to points and edges to edges and not points to edges.

So there are two ways you can "fold" : 1. Matching edge to edge which is more like folding 2. Matching a sequence of arrows to identities which is more like pinching and twisting off. Hope this is making sense LOL...

Not sure but I think when you fold you can't fold the arrows countercurrent. If this happens, you must pinch?

Comment Source:Reading through Jonathan's answers, it seems like what natural transformations are doing is overlaying each instantiation of graphs to find similarities and if there is any leftovers in the domain then it folds it so that edges line up in the most natural way kind of like origami where the rule is you have to match corners ie no half folds meaning you must match points to points and edges to edges and not points to edges. So there are two ways you can "fold" : 1. Matching edge to edge which is more like folding 2. Matching a sequence of arrows to identities which is more like pinching and twisting off. Hope this is making sense LOL... Not sure but I think when you fold you can't fold the arrows countercurrent. If this happens, you must pinch? 
• Options
5.
edited June 2018

@Jonathan

Puzzle 128 What about projecting Alice onto Bob? Wouldn't this commute as well?

$$\mathrm{FriendOf}(\alpha(\textrm{Alice})) = \alpha(\mathrm{FriendOf}(\textrm{Alice})) = \textrm{Bob}$$

There is also the transformation where you collapse everything down to one dot : Alice to Bob and Tyler to Bob which is trivial.

Comment Source:@Jonathan **Puzzle 128** What about projecting Alice onto Bob? Wouldn't this commute as well? \$$\mathrm{FriendOf}(\alpha(\textrm{Alice})) = \alpha(\mathrm{FriendOf}(\textrm{Alice})) = \textrm{Bob}\$$ There is also the transformation where you collapse everything down to one dot : Alice to Bob and Tyler to Bob which is trivial. 
• Options
6.

Regarding the consistency condition of a natural transformation of database instances (set-valued functors), the field of relational database theory studies relational databases and their morphisms. In the relational context (or Rel-valued functor context), a morphism of databases/sets of relations must preserve 'facts'; i.e., h : I => J when I(x,y,...,z) implies J(h(x),h(y),...,h(z)). It turns out that this relational definition of 'consistency as fact-preservation', when restricted to databases comprised of total functions only, is exactly the naturality condition for transformations between set valued functors. So to summarize: if you were talking to a database theorist you could say 'fact preserving' instead of 'consistent' to describe the same concept.

Comment Source:Regarding the consistency condition of a natural transformation of database instances (set-valued functors), the field of relational database theory studies relational databases and their morphisms. In the relational context (or Rel-valued functor context), a morphism of databases/sets of relations must preserve 'facts'; i.e., h : I => J when I(x,y,...,z) implies J(h(x),h(y),...,h(z)). It turns out that this relational definition of 'consistency as fact-preservation', when restricted to databases comprised of total functions only, is exactly the naturality condition for transformations between set valued functors. So to summarize: if you were talking to a database theorist you could say 'fact preserving' instead of 'consistent' to describe the same concept.
• Options
7.

Hi Jonathan (#3), it is not the case that the image of a functor F : C -> D is a subcategory of D. See https://math.stackexchange.com/questions/413138/can-it-happen-that-the-image-of-a-functor-is-not-a-category

Comment Source:Hi Jonathan (#3), it is not the case that the image of a functor F : C -> D is a subcategory of D. See https://math.stackexchange.com/questions/413138/can-it-happen-that-the-image-of-a-functor-is-not-a-category
• Options
8.
edited June 2018

Puzzle 126 : I am not sure if this is what you were looking for but looking at the examples you have chosen, the naturality forces us to find the exact same structure (or any of its subsidiaries) inside another larger universe. So maybe we can use this to see if a certain structure resides inside of another bigger structure like asking the question how many love triangles exist in the world of dating?

Puzzle 127 : Following along the previous observation, this case can ask the question can this structure be the general structure of the universe? Is the world of dating just a big love triangle? Maybe even what is the category of these functors?

Comment Source:**Puzzle 126** : I am not sure if this is what you were looking for but looking at the examples you have chosen, the naturality forces us to find the exact same structure (or any of its subsidiaries) inside another larger universe. So maybe we can use this to see if a certain structure resides inside of another bigger structure like asking the question how many love triangles exist in the world of dating? **Puzzle 127** : Following along the previous observation, this case can ask the question can this structure be the general structure of the universe? Is the world of dating just a big love triangle? Maybe even what is the category of these functors? 
• Options
9.

Michael Hong wrote:

Puzzle 128 What about projecting Alice onto Bob? Wouldn't this commute as well?

I don't believe so. With this transformation, $$\alpha(\textrm{FriendOf}(\textrm{Bob})) = \alpha(\textrm{Alice}) = \textrm{Bob}$$, but $$\textrm{FriendOf}(\alpha(\textrm{Bob})) = \textrm{FriendOf}(\textrm{Bob}) = \textrm{Alice}$$.

The same reasoning denies the collapse-everything transformation. The key here is that we're using the same $$\textrm{FriendOf}$$ function either before or after applying the natural transformation, meaning we can easily escape the "collapse" after following one of the natural transformation arrows.

Ryan Wisnesky wrote:

Hi Jonathan (#3), it is not the case that the image of a functor F : C -> D is a subcategory of D. See https://math.stackexchange.com/questions/413138/can-it-happen-that-the-image-of-a-functor-is-not-a-category

Wow! I did not expect this twist. I'll have to reflect on that...

Comment Source:Michael Hong wrote: > **Puzzle 128** What about projecting Alice onto Bob? Wouldn't this commute as well? I don't believe so. With this transformation, \$$\alpha(\textrm{FriendOf}(\textrm{Bob})) = \alpha(\textrm{Alice}) = \textrm{Bob}\$$, but \$$\textrm{FriendOf}(\alpha(\textrm{Bob})) = \textrm{FriendOf}(\textrm{Bob}) = \textrm{Alice}\$$. The same reasoning denies the collapse-everything transformation. The key here is that we're using the same \$$\textrm{FriendOf}\$$ function either before or after applying the natural transformation, meaning we can easily escape the "collapse" after following one of the natural transformation arrows. Ryan Wisnesky wrote: > Hi Jonathan (#3), it is not the case that the image of a functor F : C -> D is a subcategory of D. See https://math.stackexchange.com/questions/413138/can-it-happen-that-the-image-of-a-functor-is-not-a-category Wow! I did not expect this twist. I'll have to reflect on that...
• Options
10.

Puzzle 128: So there are exactly 2 natural transformations from H to H? How can we solve this question if the image of the dot under H is a much bigger set than only 3 individuals?

Comment Source:Puzzle 128: So there are exactly 2 natural transformations from H to H? How can we solve this question if the image of the dot under H is a much bigger set than only 3 individuals?
• Options
11.
edited June 2018

@Jonathan

When you say projecting Tyler onto Alice, are you equating the two? ie Alice = Tyler? I think I understand what you are saying but now confused by your answer. I can see why it works but not sure what you meant by project.

Comment Source:@Jonathan When you say projecting Tyler onto Alice, are you equating the two? ie Alice = Tyler? I think I understand what you are saying but now confused by your answer. I can see why it works but not sure what you meant by project. 
• Options
12.
edited June 2018

Michael wrote:

When you say projecting Tyler onto Alice, are you equating the two? ie Alice = Tyler? I think I understand what you are saying but now confused by your answer. I can see why it works but not sure what you meant by project.

No, I mean that Tyler and Alice both map to Alice. For functors from a one-object category into $$\mathbf{Set}$$, a natural transformation is just a certain kind of function between sets. For natural transformations $$\gamma : H \Rightarrow H$$, it's an endomorphism. When I say "projecting Tyler onto Alice", I mean the function $$\{\textrm{Bob} \mapsto \textrm{Bob}, \textrm{Alice} \mapsto \textrm{Alice}, \textrm{Tyler} \mapsto \textrm{Alice}\}$$.

Comment Source:Michael wrote: > When you say projecting Tyler onto Alice, are you equating the two? ie Alice = Tyler? I think I understand what you are saying but now confused by your answer. I can see why it works but not sure what you meant by project. No, I mean that Tyler and Alice both map to Alice. For functors from a one-object category into \$$\mathbf{Set}\$$, a natural transformation is just a certain kind of function between sets. For natural transformations \$$\gamma : H \Rightarrow H\$$, it's an endomorphism. When I say "projecting Tyler onto Alice", I mean the function \$$\\{\textrm{Bob} \mapsto \textrm{Bob}, \textrm{Alice} \mapsto \textrm{Alice}, \textrm{Tyler} \mapsto \textrm{Alice}\\}\$$.
• Options
13.

@Jonathan

Cool. I just worked it out and see what you mean. Have another question : what if we project Tyler onto Bob. This one seems to be an endomorphism. Is this one not allowed for some reason?

Comment Source:@Jonathan Cool. I just worked it out and see what you mean. Have another question : what if we project Tyler onto Bob. This one seems to be an endomorphism. Is this one not allowed for some reason? 
• Options
14.
edited June 2018

Michael Hong wrote:

what if we project Tyler onto Bob

It is an endomorphism, but not all squares over this endomorphism commute. Slipping into somewhat less formal language, we either go from Tyler to Bob to Bob, or Tyler to Bob to Alice, depending on whether we take the projection or $$\textrm{FriendOf}$$ first.

Ryan Wisnesky wrote:

it is not the case that the image of a functor F : C -> D is a subcategory of D.

Okay, I've reflected on this a bit, by which I mean I've read a few nLab pages. I see why a functor must be injective on objects if its range is a subcategory, for reasons closely related to my "counter"example earlier in the context of natural transformations. I'm not sure yet if I understand why a functor must also be injective on hom-sets.

Given arrows $$F(f) : F(X) \to F(Y)$$ and $$F(g) : F(Y) \to F(Z)$$, we want to show that $$F(g) \circ F(f)$$ is well-defined and is in the range of $$F$$. Note that there might be multiple $$f$$ and $$g$$ giving the same arrows; for now, pick any representatives. If $$F$$ is injective on objects, then we know that the codomain of $$f$$ and the domain of $$g$$ are the same; so the two are compatible. So $$g \circ f$$ exists, and $$F(g) \circ F(f) = F(g \circ f)$$ is in the range of $$F$$.

Now consider $$f', g'$$ distinct from $$f, g$$ such that $$F(f) = F(f')$$ and $$F(g) = F(g')$$. Then $$g \circ f$$ and $$g' \circ f'$$ exist, but need not be the same. Nonetheless, $$F(g' \circ f') = F(g') \circ F(f') = F(g) \circ F(f) = F(g \circ f)$$.

This would seem to imply that no matter which representatives $$f, g$$ we pick, their composition gives the same image under $$F$$. So the range of $$F$$ is closed under a well-defined composition.

What am I missing?

Comment Source:Michael Hong wrote: > what if we project Tyler onto Bob It is an endomorphism, but not all squares over this endomorphism commute. Slipping into somewhat less formal language, we either go from Tyler to Bob to Bob, or Tyler to Bob to Alice, depending on whether we take the projection or \$$\textrm{FriendOf}\$$ first. Ryan Wisnesky wrote: > it is not the case that the image of a functor F : C -> D is a subcategory of D. Okay, I've reflected on this a bit, by which I mean I've [read](https://ncatlab.org/nlab/show/subcategory) a [few](https://ncatlab.org/nlab/show/full+image) nLab [pages](https://ncatlab.org/nlab/show/faithful+functor). I see why a functor must be injective on objects if its range is a subcategory, for reasons closely related to my "counter"example earlier in the context of natural transformations. I'm not sure yet if I understand why a functor must also be injective on hom-sets. Given arrows \$$F(f) : F(X) \to F(Y)\$$ and \$$F(g) : F(Y) \to F(Z)\$$, we want to show that \$$F(g) \circ F(f)\$$ is well-defined and is in the range of \$$F\$$. Note that there might be multiple \$$f\$$ and \$$g\$$ giving the same arrows; for now, pick any representatives. If \$$F\$$ is injective on objects, then we know that the codomain of \$$f\$$ and the domain of \$$g\$$ are the same; so the two are compatible. So \$$g \circ f\$$ exists, and \$$F(g) \circ F(f) = F(g \circ f)\$$ is in the range of \$$F\$$. Now consider \$$f', g'\$$ distinct from \$$f, g\$$ such that \$$F(f) = F(f')\$$ and \$$F(g) = F(g')\$$. Then \$$g \circ f\$$ and \$$g' \circ f'\$$ exist, but need not be the same. Nonetheless, \$$F(g' \circ f') = F(g') \circ F(f') = F(g) \circ F(f) = F(g \circ f)\$$. This would seem to imply that no matter which representatives \$$f, g\$$ we pick, their composition gives the same image under \$$F\$$. So the range of \$$F\$$ is closed under a well-defined composition. What am I missing?
• Options
15.

@Jonathan

agh I kept getting confused which morphism to use but I figured out why. I've been treating each arrow as a separate entity but in this case its a monoid! Sorry and thx for being patient and answering my questions.

Comment Source:@Jonathan agh I kept getting confused which morphism to use but I figured out why. I've been treating each arrow as a separate entity but in this case its a monoid! Sorry and thx for being patient and answering my questions. 
• Options
16.
edited June 2018

Given arrows $$F(f) : F(X) \to F(Y)$$ and $$F(g) : F(Y) \to F(Z)$$, we want to show that $$F(g) \circ F(f)$$ is well-defined and is in the range of $$F$$. Note that there might be multiple $$f$$ and $$g$$ giving the same arrows; for now, pick any representatives. If $$F$$ is injective on objects, then we know that the codomain of $$f$$ and the domain of $$g$$ are the same; so the two are compatible. So $$g \circ f$$ exists, and $$F(g) \circ F(f) = F(g \circ f)$$ is in the range of $$F$$.

Now consider $$f', g'$$ distinct from $$f, g$$ such that $$F(f) = F(f')$$ and $$F(g) = F(g')$$. Then $$g \circ f$$ and $$g' \circ f'$$ exist, but need not be the same. Nonetheless, $$F(g' \circ f') = F(g') \circ F(f') = F(g) \circ F(f) = F(g \circ f)$$.

This would seem to imply that no matter which representatives $$f, g$$ we pick, their composition gives the same image under $$F$$. So the range of $$F$$ is closed under a well-defined composition.

What am I missing?

In a category, if you have a set of morphisms $$\mathbf{Mor}(\mathcal{C})$$, then you need if $$f: A \to B,g: B \to C \in \mathbf{Mor}(\mathcal{C})$$ then there must be some $$h : A \to C \in \mathbf{Mor}(\mathcal{C})$$ such that $$g \circ f = h$$.

Unfortunately, the image of a functor might not be closed under composition like that.

I have tried to make a picture of the example in that link below. Above on the left is the original category $$\mathcal{C}$$, and on the right is the category $$\mathcal{D}$$ that the functor $$F : \mathcal{C} \to \mathcal{D}$$ maps to.

As you can see, if we look at the morphisms in the image of $$F$$ we have $$\mathbf{Mor}(F(\mathcal{C})) = \lbrace F(f): X \to Y, F(g): Y \to Z, F(id_A): X \to X, F(id_B): Y \to Y, F(id_C): Y \to Y, F(id_D): Z \to Z \rbrace$$.

I have also drawn the missing morphism $$? : X \to Z$$, where $$? = F(g) \circ F(f)$$.

If $$F(\mathcal{C})$$ was a category then we would have $$? \in \mathbf{Mor}(F(\mathcal{C}))$$, but it is not.

Does this help clarify what is going on?

Comment Source:[Jonathan wrote](https://forum.azimuthproject.org/profile/2316/Jonathan%20Castello): > Given arrows \$$F(f) : F(X) \to F(Y)\$$ and \$$F(g) : F(Y) \to F(Z)\$$, we want to show that \$$F(g) \circ F(f)\$$ is well-defined and is in the range of \$$F\$$. Note that there might be multiple \$$f\$$ and \$$g\$$ giving the same arrows; for now, pick any representatives. If \$$F\$$ is injective on objects, then we know that the codomain of \$$f\$$ and the domain of \$$g\$$ are the same; so the two are compatible. So \$$g \circ f\$$ exists, and \$$F(g) \circ F(f) = F(g \circ f)\$$ is in the range of \$$F\$$. > > Now consider \$$f', g'\$$ distinct from \$$f, g\$$ such that \$$F(f) = F(f')\$$ and \$$F(g) = F(g')\$$. Then \$$g \circ f\$$ and \$$g' \circ f'\$$ exist, but need not be the same. Nonetheless, \$$F(g' \circ f') = F(g') \circ F(f') = F(g) \circ F(f) = F(g \circ f)\$$. > > This would seem to imply that no matter which representatives \$$f, g\$$ we pick, their composition gives the same image under \$$F\$$. So the range of \$$F\$$ is closed under a well-defined composition. > > What am I missing? In a category, if you have a set of morphisms \$$\mathbf{Mor}(\mathcal{C})\$$, then you need if \$$f: A \to B,g: B \to C \in \mathbf{Mor}(\mathcal{C})\$$ then there must be some \$$h : A \to C \in \mathbf{Mor}(\mathcal{C})\$$ such that \$$g \circ f = h\$$. Unfortunately, the image of a functor might not be closed under composition like that. Ryan linked to this stackexchange question about this: https://math.stackexchange.com/questions/413138/can-it-happen-that-the-image-of-a-functor-is-not-a-category I have tried to make a picture of the example in that link below. <center>![](https://svgshare.com/i/72W.svg)</center> Above on the left is the original category \$$\mathcal{C}\$$, and on the right is the category \$$\mathcal{D}\$$ that the functor \$$F : \mathcal{C} \to \mathcal{D}\$$ maps to. As you can see, if we look at the morphisms in the image of \$$F\$$ we have \$$\mathbf{Mor}(F(\mathcal{C})) = \lbrace F(f): X \to Y, F(g): Y \to Z, F(id_A): X \to X, F(id_B): Y \to Y, F(id_C): Y \to Y, F(id_D): Z \to Z \rbrace\$$. I have also drawn the missing morphism \$$? : X \to Z\$$, where \$$? = F(g) \circ F(f)\$$. If \$$F(\mathcal{C})\$$ was a category then we would have \$$? \in \mathbf{Mor}(F(\mathcal{C}))\$$, but it is not. Does this help clarify what is going on?
• Options
17.

For puzzle 128 I get three natural transformations:

1. $$\{\textrm{Bob} \mapsto \textrm{Bob}, \textrm{Alice} \mapsto \textrm{Alice}, \textrm{Tyler} \mapsto \textrm{Tyler}\}$$
2. $$\{\textrm{Bob} \mapsto \textrm{Bob}, \textrm{Alice} \mapsto \textrm{Alice}, \textrm{Tyler} \mapsto \textrm{Alice}\}$$
3. $$\{\textrm{Bob} \mapsto \textrm{Alice}, \textrm{Alice} \mapsto \textrm{Bob}, \textrm{Tyler} \mapsto \textrm{Bob}\}$$

Here is the diagram for the third mapping: Note: in the above picture, the arrows are not morphisms but they depict element mappings by either the natural transformation $$\alpha$$ (horizontal arrows) or the $$H(\textrm{FriendOf})$$ function (vertical arrows).

Comment Source:For **puzzle 128** I get three natural transformations: 1. \$$\\{\textrm{Bob} \mapsto \textrm{Bob}, \textrm{Alice} \mapsto \textrm{Alice}, \textrm{Tyler} \mapsto \textrm{Tyler}\\}\$$ 2. \$$\\{\textrm{Bob} \mapsto \textrm{Bob}, \textrm{Alice} \mapsto \textrm{Alice}, \textrm{Tyler} \mapsto \textrm{Alice}\\}\$$ 3. \$$\\{\textrm{Bob} \mapsto \textrm{Alice}, \textrm{Alice} \mapsto \textrm{Bob}, \textrm{Tyler} \mapsto \textrm{Bob}\\}\$$ Here is the diagram for the third mapping: ![](https://doneata.bitbucket.io/applied-category-theory/nat-trans-friend-of-small.png) Note: in the above picture, the arrows are not morphisms but they depict element mappings by either the natural transformation \$$\alpha\$$ (horizontal arrows) or the \$$H(\textrm{FriendOf})\$$ function (vertical arrows). 
• Options
18.
edited June 2018

Database editing is made of natural transformations! Let's have a schema $$\mathcal{C}$$

$\mathcal{C}: Record \rightarrow Integer$

for a very simple database type. Lets make instances over Set so we can have each integer exactly once in it. Here's one with 1 in it:

$Gr(F) = \{1\}$

Gr stands for Grothendieck and I'm using it to show off, but it simply meas that I want to talk about F's elements. Really, I wouldn't know what else to call it. Slightly more interestingly I've decided that specifying the elements says everything about databases of the $$\mathcal{C}$$ kind. Let's have another one with another element 2 in it:

$Gr(G) = \{1,2\}$

Then we can relate the two databases F and G using a natural transformation called insert(2):

$insert(2): F \rightarrow G$

or using an arrow pointing the other way called delete(2):

$delete(2): F \leftarrow G$

Let's only call those natural transformations database editing that don't change the schema. Then we'd have to check that this square commutes:

$\begin{array}{ccc} & id & \\ \mathcal{C} & \longrightarrow & \mathcal{C} \\ F \downarrow & & \downarrow G \\ Gr(F) & \longrightarrow & Gr(G) \\ & insert(2) & \\ \end{array}$

Erm, we just defined that insert(2) is the name for how Gr(F) and Gr(G) are related, so of course it commutes! Then, by label symmetry, the opposite one for delete will also commute %-P

It's conceivable to compose insert and delete to implement an update operation, let's say we want to change G such that this H is the result:

$Gr(H) = \{1,3\}$

The corresponding update has two parameters and it's type is a map from G to H:

$update(2,3) : G \rightarrow H = delete(2) \circ insert(3)$

I should still read some stuff, maybe later. I'm sorry, Ryan.

Puzzle rf43.1: What's the "schema" for these database editing operations? What's the most general way to capture what insert does such that we can compare it against a similar description of what delete does.

Comment Source:Database editing is made of natural transformations! Let's have a schema \$$\mathcal{C} \$$ \$\mathcal{C}: Record \rightarrow Integer \$ for a very simple database type. Lets make instances over Set so we can have each integer exactly once in it. Here's one with 1 in it: \$Gr(F) = \\{1\\} \$ Gr stands for Grothendieck and I'm using it to show off, but it simply meas that I want to talk about F's elements. Really, I wouldn't know what else to call it. Slightly more interestingly I've decided that specifying the elements says everything about databases of the \$$\mathcal{C} \$$ kind. Let's have another one with another element 2 in it: \$Gr(G) = \\{1,2\\} \$ Then we can relate the two databases F and G using a natural transformation called insert(2): \$insert(2): F \rightarrow G \$ or using an arrow pointing the other way called delete(2): \$delete(2): F \leftarrow G \$ Let's only call those natural transformations database editing that don't change the schema. Then we'd have to check that this square commutes: \$\begin{array}{ccc} & id & \\\\ \mathcal{C} & \longrightarrow & \mathcal{C} \\\\ F \downarrow & & \downarrow G \\\\ Gr(F) & \longrightarrow & Gr(G) \\\\ & insert(2) & \\\\ \end{array} \$ Erm, we just defined that insert(2) is the name for how Gr(F) and Gr(G) are related, so of course it commutes! Then, by label symmetry, the opposite one for delete will also commute %-P It's conceivable to compose insert and delete to implement an update operation, let's say we want to change G such that this H is the result: \$Gr(H) = \\{1,3\\} \$ The corresponding update has two parameters and it's type is a map from G to H: \$update(2,3) : G \rightarrow H = delete(2) \circ insert(3) \$ I should still read some stuff, maybe later. I'm sorry, Ryan. **Puzzle rf43.1:** What's the "schema" for these database editing operations? What's the most general way to capture what insert does such that we can compare it against a similar description of what delete does.
• Options
19.
edited June 2018

Matthew wrote:

Unfortunately, the image of a functor might not be closed under composition like that.

In my "proof", I already assume that the functor is indeed injective on objects. The StackExchange question being referenced shows precisely why this is necessary, and I acknowledge it in my post. What I am confused about is why it must also be faithful, i.e. injective on hom-sets. This is not addressed by the StackExchange example.

To quote the nLab:

Just as subsets of a set $$X$$ can be identified with isomorphism classes of monic functions into $$X$$, subcategories of a category $$C$$ can be identified with isomorphism classes of monic functors into $$C$$. A functor is easily verified to be monic iff it is faithful and injective on objects.

Comment Source:Matthew wrote: > Unfortunately, the image of a functor might not be closed under composition like that. In my "proof", I already assume that the functor is indeed injective on objects. The StackExchange question being referenced shows precisely why this is necessary, and I acknowledge it in my post. What I am confused about is why it must also be [faithful](https://ncatlab.org/nlab/show/faithful+functor), i.e. injective on hom-sets. This is not addressed by the StackExchange example. To quote [the nLab](https://ncatlab.org/nlab/show/subcategory): > Just as subsets of a set \$$X\$$ can be identified with isomorphism classes of [monic](https://ncatlab.org/nlab/show/monomorphism) functions into \$$X\$$, subcategories of a category \$$C\$$ can be identified with isomorphism classes of monic functors into \$$C\$$. A functor is easily verified to be monic iff it is [faithful](https://ncatlab.org/nlab/show/faithful+functor) and injective on objects.
• Options
20.
edited June 2018

Gotcha. Thanks for the clarification Jonathan!

As you can see, I am trying to puzzle this out too...

Comment Source:Gotcha. Thanks for the clarification Jonathan! As you can see, I am trying to puzzle this out too...
• Options
21.

Dan wrote:

$$\{\textrm{Bob} \mapsto \textrm{Alice}, \textrm{Alice} \mapsto \textrm{Bob}, \textrm{Tyler} \mapsto \textrm{Bob}\}$$

Ooh! I didn't think about that, but I see why it works! This map is precisely $$\mathrm{FriendOf}$$, so of course it commutes with itself!

It would be nice if there was a constructive presentation of natural tranformations between databases -- or even over the same database, as with $$H \Rightarrow H$$. I've been trying to figure out a general procedure to find all natural transformations without using brute force, but I'm not seeing anything yet.

Comment Source:Dan wrote: > \$$\\{\textrm{Bob} \mapsto \textrm{Alice}, \textrm{Alice} \mapsto \textrm{Bob}, \textrm{Tyler} \mapsto \textrm{Bob}\\}\$$ Ooh! I didn't think about that, but I see why it works! This map is precisely \$$\mathrm{FriendOf}\$$, so of course it commutes with itself! It would be nice if there was a constructive presentation of natural tranformations between databases -- or even over the same database, as with \$$H \Rightarrow H\$$. I've been trying to figure out a general procedure to find all natural transformations without using brute force, but I'm not seeing anything yet.
• Options
22.

Hi Jonathan (#21), relational database theory can help find all the natural transformations I => J quickly, where I, J : C -> Set, and I is small relative to J. The reason is that I can be thought of as a 'conjunctive query' Q^I (this is getting a bit far afield but these are great slides: https://classes.soe.ucsc.edu/cmps277/Winter10/Lectures/lect8-w10.pdf ). It turns out that finding all the natural transformations I => J is the same problem as evaluating Q^I on instance J.

Anyway, the key idea is that if I is small and J is large, you can translate I into a SQL query and J into a SQL database, run the query, and then recover the set of natural transformations I => J. In fact you can even arrange these onto the schema C, since the category C->Set is cartesian closed, J^I is also an object of C.

To try to make this concrete, suppose C is the arrow category f : A -> B, and for each natural number n, let I_n be the functor C -> Set defined as I_n(a) = I_n(b) = {n} and I_n(f)(n) = n. Suppose we want to find the natural transformations I_1 + I_2 => I_3 + I_4 + I_5. The instance J := I_3 + I_4 + I_5 has J(A) = J(B) = {3,4,5} and J(f) = id. The SQL query Q^I(J) for instance I_1 + I_2 is "FROM J as I_1, J as I_2", and returns 9 rows, as expected. What's neat is that no matter how complicated I is, you can still write Q^I using SELECT, FROM, WHERE, and the SQL query optimizer takes care of finding a way to quickly execute the query.

Comment Source:Hi Jonathan (#21), relational database theory can help find all the natural transformations I => J quickly, where I, J : C -> Set, and I is small relative to J. The reason is that I can be thought of as a 'conjunctive query' Q^I (this is getting a bit far afield but these are great slides: https://classes.soe.ucsc.edu/cmps277/Winter10/Lectures/lect8-w10.pdf ). It turns out that finding all the natural transformations I => J is the same problem as evaluating Q^I on instance J. Anyway, the key idea is that if I is small and J is large, you can translate I into a SQL query and J into a SQL database, run the query, and then recover the set of natural transformations I => J. In fact you can even arrange these onto the schema C, since the category C->Set is cartesian closed, J^I is also an object of C. To try to make this concrete, suppose C is the arrow category f : A -> B, and for each natural number n, let I_n be the functor C -> Set defined as I_n(a) = I_n(b) = {n} and I_n(f)(n) = n. Suppose we want to find the natural transformations I_1 + I_2 => I_3 + I_4 + I_5. The instance J := I_3 + I_4 + I_5 has J(A) = J(B) = {3,4,5} and J(f) = id. The SQL query Q^I(J) for instance I_1 + I_2 is "FROM J as I_1, J as I_2", and returns 9 rows, as expected. What's neat is that no matter how complicated I is, you can still write Q^I using SELECT, FROM, WHERE, and the SQL query optimizer takes care of finding a way to quickly execute the query. 
• Options
23.

What's neat is that no matter how complicated I is, you can still write $$Q^I$$ using SELECT, FROM, WHERE, and the SQL query optimizer takes care of finding a way to quickly execute the query.

This is a bit optimistic.

There are many ways a database query can be suboptimal and the optimizer can't always improve performance.

For instance, PSQL does not automatically optimize subqueries into joins even when they are equivalent. Here is a quora discussion about this.

It is important not to rely on the query optimizer and routinely check out the query planner.

There are many gotchas in SQL queries. You sometimes have to manually make indexes to improve performance. Even if you have an index, it is easy to write a SQL query that accidentally does not use it. Here is a datadog blog post where they go over this an example of this exercise, where a one line change gave a 100x performance improvement.

Comment Source:> What's neat is that no matter how complicated I is, you can still write \$$Q^I\$$ using SELECT, FROM, WHERE, and the SQL query optimizer takes care of finding a way to quickly execute the query. This is a bit optimistic. There are many ways a database query can be suboptimal and the optimizer can't always improve performance. For instance, PSQL does not automatically optimize subqueries into joins even when they are equivalent. Here is a [quora discussion](https://www.quora.com/Which-is-faster-joins-or-subqueries) about this. It is important not to rely on the query optimizer and routinely check out the query planner. There are many gotchas in SQL queries. You sometimes have to manually make indexes to improve performance. Even if you have an index, it is easy to write a SQL query that accidentally does not use it. Here is a [datadog blog post](https://www.datadoghq.com/blog/100x-faster-postgres-performance-by-changing-1-line/) where they go over this an example of this exercise, where a one line change gave a 100x performance improvement.
• Options
24.
edited June 2018

Jonathan wrote:

John wrote:

Maybe someone can expound a bit more on the notion of 'consistency' that I'm vaguely alluding to. All I mean is that a bunch of squares commute... but it's good to try to tease out the meaning of this, and express it in something resembling plain English.

Well, I'm not sure if this is exactly what you're referring to, but maybe it's close?

Generally speaking, homomorphisms identify a substructure of a target object that resembles (i.e. preserves the behavior of) the source object [...]

Your answer is great, but I was fishing for a more down-to-earth answer connected to the database examples we're looking at. Something like this:

When we change databases using a natural transformation, relationships are preserved.
For example if Vanessa is a friend of Bodo and we rename Bodo as "Herr Schmidt" and rename Vanessa as "Signora Cucinelli", naturality demands that Signora Cucinelli be a friend of Herr Schmidt!

We say a transformation $$\alpha: F \Rightarrow G$$ between database instances $$F,G : \mathcal{C} \to \mathbf{Set}$$ is natural if for each morphism $$f : x \to y$$ in $$\mathcal{C}$$, this square commutes: or in other words,

$$G(f) \alpha_x = \alpha_y F(f) .$$ In our database examples, $$F$$ and $$G$$ each map every "data type" (=object of $$\mathcal{C}$$ to a set of entities of that type, and every "relationship" (=morphism of $$\mathcal{C}$$ to a function between sets. Here I'm using the word "relationship" for morphisms of $$\mathcal{C}$$ simply because we've seen examples like

$$\textrm{FriendOf} : \textrm{German} \to \textrm{Italian} .$$ The natural transformation $$\alpha$$ "renames" elements of the set $$F(x)$$, turning them into elements of $$G(x)$$ via

$$\alpha_x : F(x) \to G(x) .$$ Similarly, it renames elements of $$F(y)$$, turning them into elements of $$G(y)$$. We want this renaming process to be consistent in the sense that if $$a \in F(x)$$ is related to $$b \in F(y)$$ by the relationship $$f$$ in our first database:

$$b = F(f) (a)$$ then $$\alpha_x (a) \in G(x)$$ is related to $$\alpha_y (b) \in G(y)$$ by the relationship $$f$$ in our second database:

$$\alpha_y (b) = G(f) (\alpha_x(a)) .$$ So for example if $$b =$$ Vanessa is a friend of $$a =$$ Bodo and we rename Bodo as "Herr Schmidt" and rename Vanessa as "Signora Cucinelli", we want Signora Cucinelli to be a friend of Herr Schmidt.

Saying

$$b = F(f) (a) \quad \implies \quad \alpha_y (b) = G(f) (\alpha_x(a))$$ is just another way of saying that this square commutes: Comment Source:Jonathan wrote: > John wrote: > > Maybe someone can expound a bit more on the notion of 'consistency' that I'm vaguely alluding to. All I mean is that a bunch of squares commute... but it's good to try to tease out the meaning of this, and express it in something resembling plain English. > Well, I'm not sure if this is exactly what you're referring to, but maybe it's close? > Generally speaking, homomorphisms identify a substructure of a target object that resembles (i.e. preserves the behavior of) the source object [...] Your answer is great, but I was fishing for a more down-to-earth answer connected to the database examples we're looking at. Something like this: When we change databases using a natural transformation, relationships are preserved. For example if Vanessa is a friend of Bodo and we rename Bodo as "Herr Schmidt" and rename Vanessa as "Signora Cucinelli", naturality demands that Signora Cucinelli be a friend of Herr Schmidt! We say a transformation \$$\alpha: F \Rightarrow G \$$ between database instances \$$F,G : \mathcal{C} \to \mathbf{Set}\$$ is **natural** if for each morphism \$$f : x \to y\$$ in \$$\mathcal{C}\$$, this square commutes: <center><img width = "200" src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/naturality_square.png"></center> or in other words, $G(f) \alpha_x = \alpha_y F(f) .$ In our database examples, \$$F\$$ and \$$G\$$ each map every "data type" (=object of \$$\mathcal{C}\$$ to a set of entities of that type, and every "relationship" (=morphism of \$$\mathcal{C}\$$ to a function between sets. Here I'm using the word "relationship" for morphisms of \$$\mathcal{C}\$$ simply because we've seen examples like $\textrm{FriendOf} : \textrm{German} \to \textrm{Italian} .$ The natural transformation \$$\alpha\$$ "renames" elements of the set \$$F(x)\$$, turning them into elements of \$$G(x)\$$ via $\alpha_x : F(x) \to G(x) .$ Similarly, it renames elements of \$$F(y)\$$, turning them into elements of \$$G(y)\$$. We want this renaming process to be **consistent** in the sense that if \$$a \in F(x) \$$ is related to \$$b \in F(y)\$$ by the relationship \$$f\$$ in our first database: $b = F(f) (a)$ then \$$\alpha_x (a) \in G(x) \$$ is related to \$$\alpha_y (b) \in G(y)\$$ by the relationship \$$f\$$ in our second database: $\alpha_y (b) = G(f) (\alpha_x(a)) .$ So for example if \$$b = \$$ Vanessa is a friend of \$$a = \$$ Bodo and we rename Bodo as "Herr Schmidt" and rename Vanessa as "Signora Cucinelli", we want Signora Cucinelli to be a friend of Herr Schmidt. Saying $b = F(f) (a) \quad \implies \quad \alpha_y (b) = G(f) (\alpha_x(a))$ is just another way of saying that this square commutes: <center><img width = "200" src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/naturality_square.png"></center> 
• Options
25.
edited June 2018

Above, I had the curious idea to post about natural transformations for a database type which had no relations. Incidentally, in most SQL database engines, you have to explicitly represent relations using numbers (you'd better use numbers). So instead of directly relating employees to the department they work in, we'd have to assign a unique key to every department record, and mention that key in the employee record:

$department: Employee \rightarrow Integer \\ primaryKey: Department \rightarrow Integer$

This works if every employee is working in either zero or one appartment. Zero can happen because in these "relational" database engines (I'm picturing you folks starting to wonder why people call those databases "relational" in the first place) you can alternatively put the special value NULL into any field. That can be turned off, but it's the default behaviour.

The best way to implement m:n relations is to use an extra Relation table like this:

$primaryKey: Employee \rightarrow Integer \\ primaryKey: Department \rightarrow Integer \\ employeeKey: Relation \rightarrow Integer \\ departmentKey: Relation \rightarrow Integer$

You see, the schema graph isn't even connected!

Okay. So any natural transformation between functors over a category without any arrows is bound to be trivial. It is also the reason why the commutative square I came up with looks so different than the ones the other people talked about. I had no arrows in my database schema, so I couldn't talk about them!

All this lack of consistency implies that any categorical version of SQL (like FQL or AQL) cannot be isomorphic to SQL, as SQL has no real way to establish the constraints given by a schema category. Well, some dialects allow to declare the meaning of constructions like the ones I just gave, such that if you try to remove a department, the database will try to also remove the employees related to it (or the corresponding relations from the Relation table).

I'm glad that so many answers address John's puzzles directly, without tweaking them as much as I seem to be doing! Without them, my confusion might be a much more serious issue!

Comment Source:Above, I had the curious idea to post about natural transformations for a database type which had no relations. Incidentally, in most SQL database engines, you have to explicitly represent relations using numbers (you'd better use numbers). So instead of directly relating employees to the department they work in, we'd have to assign a unique key to every department record, and mention that key in the employee record: \$department: Employee \rightarrow Integer \\\\ primaryKey: Department \rightarrow Integer \$ This works if every employee is working in either zero or one appartment. Zero can happen because in these "relational" database engines (I'm picturing you folks starting to wonder why people call those databases "relational" in the first place) you can alternatively put the special value NULL into any field. That can be turned off, but it's the default behaviour. The best way to implement m:n relations is to use an extra Relation table like this: \$primaryKey: Employee \rightarrow Integer \\\\ primaryKey: Department \rightarrow Integer \\\\ employeeKey: Relation \rightarrow Integer \\\\ departmentKey: Relation \rightarrow Integer \$ You see, the schema graph isn't even connected! Okay. So any natural transformation between functors over a category without any arrows is bound to be trivial. It is also the reason why the commutative square I came up with looks so different than the ones the other people talked about. I had no arrows in my database schema, so I couldn't talk about them! All this lack of consistency implies that any categorical version of SQL (like FQL or AQL) cannot be isomorphic to SQL, as SQL has no real way to establish the constraints given by a schema category. Well, some dialects allow to declare the meaning of constructions like the ones I just gave, such that if you try to remove a department, the database will try to also remove the employees related to it (or the corresponding relations from the Relation table). I'm glad that so many answers address John's puzzles directly, without tweaking them as much as I seem to be doing! Without them, my confusion might be a much more serious issue!
• Options
26.

Hi Robert, I think what you're noticing is that every column in a SQL database is an attribute; i.e., it contains meaningful data of a certain type, which means that as graphs SQL schemas are very 'pointy'. To faithfully encode SQL foreign keys as edges requires adding additional edges and some path equalities.

For example, suppose we are given

CREATE TABLE Employee(id INT PRIMARY KEY, first VARCHAR(255), last VARCHAR(255), manager INT, worksIn INT
);

CREATE TABLE Department( id INT PRIMARY KEY,name VARCHAR(255), secretary INT,
);

ALTER TABLE Employee ADD CONSTRAINT e1 FOREIGN KEY (manager) REFERENCES Employee (id);

ALTER TABLE Employee ADD CONSTRAINT e2 FOREIGN KEY (worksIn) REFERENCES Department (id);

ALTER TABLE Department ADD CONSTRAINT d1 FOREIGN KEY (secretary) REFERENCES Employee (id);


the equivalent category presentation (i.e., the class of models of this presentation is isomorphic to the class of models of the SQL schema, provided the type sorts (INT, etc) are interpreted identically):

    nodes
DEPARTMENT, VARCHAR, EMPLOYEE, INTEGER;
edges
DEPARTMENT__SECRETARY__EMPLOYEE_ID : DEPARTMENT -> EMPLOYEE,
SECRETARY : DEPARTMENT -> INTEGER,
ID : DEPARTMENT -> INTEGER,
NAME : DEPARTMENT -> VARCHAR,
EMPLOYEE__WORKSIN__DEPARTMENT_ID : EMPLOYEE -> DEPARTMENT,
EMPLOYEE__MANAGER__EMPLOYEE_ID : EMPLOYEE -> EMPLOYEE,
ID : EMPLOYEE -> INTEGER,
MANAGER : EMPLOYEE -> INTEGER,
WORKSIN : EMPLOYEE -> INTEGER,
LAST : EMPLOYEE -> VARCHAR,
FIRST : EMPLOYEE -> VARCHAR;
equations
WORKSIN = ID o EMPLOYEE__WORKSIN__DEPARTMENT_ID,
MANAGER = ID o EMPLOYEE__MANAGER__EMPLOYEE_ID,
SECRETARY = ID o DEPARTMENT__SECRETARY__EMPLOYEE_ID;

Comment Source:Hi Robert, I think what you're noticing is that every column in a SQL database is an attribute; i.e., it contains meaningful data of a certain type, which means that as graphs SQL schemas are very 'pointy'. To faithfully encode SQL foreign keys as edges requires adding additional edges and some path equalities. For example, suppose we are given <pre> CREATE TABLE Employee(id INT PRIMARY KEY, first VARCHAR(255), last VARCHAR(255), manager INT, worksIn INT ); CREATE TABLE Department( id INT PRIMARY KEY,name VARCHAR(255), secretary INT, ); ALTER TABLE Employee ADD CONSTRAINT e1 FOREIGN KEY (manager) REFERENCES Employee (id); ALTER TABLE Employee ADD CONSTRAINT e2 FOREIGN KEY (worksIn) REFERENCES Department (id); ALTER TABLE Department ADD CONSTRAINT d1 FOREIGN KEY (secretary) REFERENCES Employee (id); </pre> the equivalent category presentation (i.e., the class of models of this presentation is isomorphic to the class of models of the SQL schema, provided the type sorts (INT, etc) are interpreted identically): <pre> nodes DEPARTMENT, VARCHAR, EMPLOYEE, INTEGER; edges DEPARTMENT__SECRETARY__EMPLOYEE_ID : DEPARTMENT -> EMPLOYEE, SECRETARY : DEPARTMENT -> INTEGER, ID : DEPARTMENT -> INTEGER, NAME : DEPARTMENT -> VARCHAR, EMPLOYEE__WORKSIN__DEPARTMENT_ID : EMPLOYEE -> DEPARTMENT, EMPLOYEE__MANAGER__EMPLOYEE_ID : EMPLOYEE -> EMPLOYEE, ID : EMPLOYEE -> INTEGER, MANAGER : EMPLOYEE -> INTEGER, WORKSIN : EMPLOYEE -> INTEGER, LAST : EMPLOYEE -> VARCHAR, FIRST : EMPLOYEE -> VARCHAR; equations WORKSIN = ID o EMPLOYEE__WORKSIN__DEPARTMENT_ID, MANAGER = ID o EMPLOYEE__MANAGER__EMPLOYEE_ID, SECRETARY = ID o DEPARTMENT__SECRETARY__EMPLOYEE_ID; </pre> 
• Options
27.

Here's a bit general question:

Why do we need to establish some relation between functors using morphisms in a category?

If we consider functors F and G as "images" of a category C in a category D, I suspect that there are ways to make them feel similarly, but there is no way to smoothly move F to G along morphisms in D.

If such transformations indeed exist, they feel more like discrete jumps rather than smooth sliding, but still may preserve everything we need (or even be isomorphisms). So it seems that the "continuous" maps provided by natural transformations form a subset of all possible transformations, and obviously bear some advantages compared to other types.

Comment Source:Here's a bit general question: Why do we need to establish some relation between functors using morphisms in a category? If we consider functors F and G as "images" of a category C in a category D, I suspect that there are ways to make them feel similarly, but there is no way to smoothly move F to G along morphisms in D. If such transformations indeed exist, they feel more like discrete jumps rather than smooth sliding, but still may preserve everything we need (or even be isomorphisms). So it seems that the "continuous" maps provided by natural transformations form a subset of all possible transformations, and obviously bear some advantages compared to other types.
• Options
28.
edited July 2018

Also a more concrete question, following the previous one:

Some of the categories we've seen form directed lattices with a single source and sink (initial and terminal objects), like a power set of some set S with $$\subseteq$$ as morphisms.

Is it true that if we have images F and G in such a category, the F can only be naturally transformed into G in a limited number of ways - it may slide upwards (if morphisms allow) and/or expand/shrink sideways and upwards? What are we getting from following the topology of this category, except for constraints on possible natural transformations?

Other categories, resembling manifolds, have a property of having non-empty two-way sets of morphisms for all objects and their "neighborhoods". In such categories possible natural transformations greatly expand their repertoire, so there are "translations", "rotations", "scaling", non-rigid deformations, everything having topological taste, because natural transformations require all these to happen continuously along morphisms. Is this mental picture right, can it somehow be expanded, or, conversely, constrained?

EDIT: writing this I realized that at least the category FinSet without the empty set has a codiscrete (indiscrete) "topology", where each object is connected to another. So if there is a nice way (preserving object relationships) to morph F into G, it is a natural transformation. Btw, from what I see at the moment, a natural transfomation between F and G always exists in this category, don't know whether this is true or not.

Comment Source:Also a more concrete question, following the previous one: Some of the categories we've seen form directed lattices with a single source and sink (initial and terminal objects), like a power set of some set S with \$$\subseteq\$$ as morphisms. Is it true that if we have images F and G in such a category, the F can only be naturally transformed into G in a limited number of ways - it may slide upwards (if morphisms allow) and/or expand/shrink sideways and upwards? What are we getting from following the topology of this category, except for constraints on possible natural transformations? Other categories, resembling manifolds, have a property of having non-empty two-way sets of morphisms for all objects and their "neighborhoods". In such categories possible natural transformations greatly expand their repertoire, so there are "translations", "rotations", "scaling", non-rigid deformations, everything having topological taste, because natural transformations require all these to happen continuously along morphisms. Is this mental picture right, can it somehow be expanded, or, conversely, constrained? **EDIT:** writing this I realized that at least the category **FinSet** without the empty set has a codiscrete (indiscrete) "topology", where each object is connected to another. So if there is a nice way (preserving object relationships) to morph F into G, it is a natural transformation. Btw, from what I see at the moment, a natural transfomation between F and G always exists in this category, don't know whether this is true or not.
• Options
29.

Igor wrote:

Why do we need to establish some relation between functors using morphisms in a category?

Are you asking why do we need natural transformations? The short answer is that category theory would be extremely boring without natural transformations: most of the subject would be gone. Most of the interesting concepts in category theory, like adjoint functors, rely on natural transformations.

If we consider functors F and G as "images" of a category C in a category D, I suspect that there are ways to make them feel similarly, but there is no way to smoothly move F to G along morphisms in D.

In general the concepts of 'continuously' and 'smoothly' make no sense in a category, because a category has no topology (which is what we need to define 'continuously') or smooth structure (which is what we need to define 'smoothly').

People do study topological categories and smooth categories, and I've used those in my work on mathematical physics, but we won't get to those in this course.

Comment Source:Igor wrote: > Why do we need to establish some relation between functors using morphisms in a category? Are you asking why do we need natural transformations? The short answer is that category theory would be extremely boring without natural transformations: most of the subject would be gone. Most of the interesting concepts in category theory, like adjoint functors, rely on natural transformations. > If we consider functors F and G as "images" of a category C in a category D, I suspect that there are ways to make them feel similarly, but there is no way to smoothly move F to G along morphisms in D. In general the concepts of 'continuously' and 'smoothly' make no sense in a category, because a category has no [topology](https://en.wikipedia.org/wiki/Topology) (which is what we need to define 'continuously') or [smooth structure](https://en.wikipedia.org/wiki/Smooth_structure) (which is what we need to define 'smoothly'). People do study topological categories and smooth categories, and I've used those in my work on mathematical physics, but we won't get to those in this course.
• Options
30.
edited July 2018

Igor wrote:

Some of the categories we've seen form directed lattices with a single source and sink (initial and terminal objects), like a power set of some set S with $$\subseteq$$ as morphisms.

Yes; more generally we spent a lot of time talking about posets, where we can only have a morphism $$f: x \to y$$ and a morphism $$g: y \to x$$ if $$x = y$$.

Is it true that if we have images F and G in such a category, the F can only be naturally transformed into G in a limited number of ways - it may slide upwards (if morphisms allow) and/or expand/shrink sideways and upwards?

It sounds like you're taking the visual metaphors very seriously here: the concept of 'sideways' doesn't mean much in a general category or even a poset. However, here is what's true: if we have two functors $$F,G: \mathcal{C} \to \mathcal{D}$$ and $$\mathcal{D}$$ is actually a poset, we can only have a natural transformation $$\alpha: F \Rightarrow G$$ if

$$F(x) \le G(x)$$ for all $$x \in \mathrm{Ob}(\mathcal{C})$$.

This follows immediately from the definitions.

But posets are very special categories.

What are we getting from following the topology of this category, except for constraints on possible natural transformations?

The word 'topology' doesn't apply here: there is no topology here.

Comment Source:Igor wrote: >Some of the categories we've seen form directed lattices with a single source and sink (initial and terminal objects), like a power set of some set S with \$$\subseteq\$$ as morphisms. Yes; more generally we spent a lot of time talking about posets, where we can only have a morphism \$$f: x \to y\$$ and a morphism \$$g: y \to x\$$ if \$$x = y\$$. > Is it true that if we have images F and G in such a category, the F can only be naturally transformed into G in a limited number of ways - it may slide upwards (if morphisms allow) and/or expand/shrink sideways and upwards? It sounds like you're taking the visual metaphors very seriously here: the concept of 'sideways' doesn't mean much in a general category or even a poset. However, here is what's true: if we have two functors \$$F,G: \mathcal{C} \to \mathcal{D}\$$ and \$$\mathcal{D}\$$ is actually a poset, we can only have a natural transformation \$$\alpha: F \Rightarrow G\$$ if $F(x) \le G(x)$ for all \$$x \in \mathrm{Ob}(\mathcal{C})\$$. This follows immediately from the definitions. But posets are very special categories. > What are we getting from following the topology of this category, except for constraints on possible natural transformations? The word 'topology' doesn't apply here: there is no topology here.
• Options
31.

Here's a Python program that uses Z3 to find all the solutions to Puzzle 128:

from z3 import *
s = Solver()

# Define H(People) = {Alice, Bob, Tyler}
_, (Alice, Bob, Tyler) = H_People, People = EnumSort('H(People)', ('Alice', 'Bob', 'Tyler'))

# Define H(Friend)
H_Friend = Function('H(Friend)', H_People, H_People)

# Define commutativity constraints on a_Friend
a_Friend = Function('a_Friend', H_People, H_People)
H_person = Const('H_person', H_People)

# Print all satisfying models
while s.check() == sat:
m = s.model()
print(", ".join("{} -> {}".format(person, m.evaluate(a_Friend(person))) for person in People))


Output:

Alice -> Alice, Bob -> Bob, Tyler -> Alice

Alice -> Bob, Bob -> Alice, Tyler -> Bob

Alice -> Alice, Bob -> Bob, Tyler -> Tyler

If for fun I define $$H(Friend)$$ to be the identity function, this gives all $$3^3 = 27$$ functions from $$H(People)$$ to itself.

Comment Source:Here's a Python program that uses Z3 to find all the solutions to **Puzzle 128**: from z3 import * s = Solver() # Define H(People) = {Alice, Bob, Tyler} _, (Alice, Bob, Tyler) = H_People, People = EnumSort('H(People)', ('Alice', 'Bob', 'Tyler')) # Define H(Friend) H_Friend = Function('H(Friend)', H_People, H_People) s.add(H_Friend(Alice) == Bob) s.add(H_Friend(Bob) == Alice) s.add(H_Friend(Tyler) == Bob) # Define commutativity constraints on a_Friend a_Friend = Function('a_Friend', H_People, H_People) H_person = Const('H_person', H_People) s.add(ForAll(H_person, H_Friend(a_Friend(H_person)) == a_Friend(H_Friend(H_person)))) # Print all satisfying models while s.check() == sat: m = s.model() print(", ".join("{} -> {}".format(person, m.evaluate(a_Friend(person))) for person in People)) s.add(Exists(H_person, a_Friend(H_person) != m.evaluate(a_Friend(H_person)))) Output: > Alice -> Alice, Bob -> Bob, Tyler -> Alice > Alice -> Bob, Bob -> Alice, Tyler -> Bob > Alice -> Alice, Bob -> Bob, Tyler -> Tyler If for fun I define \$$H(Friend)\$$ to be the identity function, this gives all \$$3^3 = 27\$$ functions from \$$H(People)\$$ to itself.
• Options
32.

I expanded my above program and found 5, 3, and 3 solutions to Puzzles 126, 127, and 128 respectively: https://bitbucket.org/snippets/thealexvarga/derzG5

Comment Source:I expanded my above program and found 5, 3, and 3 solutions to **Puzzles 126, 127, and 128** respectively: https://bitbucket.org/snippets/thealexvarga/derzG5