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

- All Categories 2.3K
- Chat 501
- Study Groups 21
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 2
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 339
- MIT 2019: Lectures 79
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 69
- Azimuth Code Project 110
- Statistical methods 4
- Drafts 5
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 148
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 714

Options

Chapter 3 of *Seven Sketches* is about databases, which are a great excuse to finally introduce the main theme of this course: *categories!*

So, with no further ado:

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

a collection \(\mathrm{Ob}(\mathcal{C})\), elements of which are called

**objects**;for each pair of objects \(c,c'\), a set \(\mathcal{C}(c,c')\). Elements of this set are called

**morphisms from \(c\) to \(c'\)**. If \(f\) is a morphism from \(c\) to \(c'\) we write \(f: c \to c'\).

Furthermore:

a) given morphisms \(f : c \to c'\) and \(g : c' \to c''\) there is a morphism \(g \circ f : c \to c''\) called the **composite** of \(f\) and \(g\).

b) given any object \(c\) there is a morphism \(1_c : c \to c\) called the **identity morphism** of \(c\).

Finally, we require that these laws hold:

i) the **associative law**: \(h \circ (g \circ f) = (h \circ g) \circ f\) holds for any morphisms \(f: c \to c', g: c' \to c'', h: c'' \to c'''\);

ii) the **left and right unit laws**: \(1_{c'} \circ f = f = f \circ 1_c \) holds for any morphism \(f : c \to c'\).

To understand all this, it's important to know a bunch of examples. I'll start you out with two, and make you come up with some others in some puzzles.

First, *every preorder gives a category!* This is why we spent so much time on preorders.

Suppose we have a preorder \( (X, \le ) \). Here's how to build a category \(\mathcal{C}\). Take the objects of \(\mathcal{C}\) to be the elements of \(X\), and let \(C\) have exactly one morphism from \(x\) to \(y\) when \(x \le y\), and none otherwise. Then there is just one way to define composition and identity morphisms to create a category!

To see this, notice:

a) Given morphisms \(f : x \to x'\) and \(g : x' \to x''\) in \(\mathcal{C}\), we must have \(x \le x'\) and \(x' \le x''\), so by transitivity we have \(x \le x''\). Thus, there is exactly one morphism \(h: x \to x''\), so we have to define \(g \circ f = h\). So, *transitivity gives composition, without any choice about how to do it!*

b) Given an object \(x\), we must have \(x \le x\), by reflexivity. Thus, there is exactly one morphism \(f: x \to x\), so we have to define \(1_x = f\). So, *reflexivity gives identity morphisms, without any choice about how to do it!*

Then:

i) The associative law is automatic: for any morphisms \(f: x \to x', g: x' \to x'', h: x'' \to x'''\), we must have \(h \circ (g \circ f) = (h \circ g) \circ f\) because there's at most one morphism from \(x\) to \(x''\).

ii) The left and right unit laws are automatic: for any morphism \(f: x \to x'\) we must have \(1_{x'} \circ f = f = f \circ 1_x\) because there's at most one morphism from \(x\) to \(x'\).

So, preorders give rise to a very special sort of category: a category where there's at most one morphism \(f : c \to c'\) from any object \(c\) to any object \(c'\) Conversely, you can turn around the argument I just made and show that any category of this sort comes from a preorder!

So, you know lots of categories: all the preorders you know give examples of categories. And in fact, everything we've done so far is a special case of something one can do with categories!

So let's look at an example of another sort. There's a category \(\mathbf{Set}\) where:

the objects of \(\mathbf{Set}\) are sets;

if \(S,S'\) are sets, a morphism \(f: S \to S'\) is a function from \(S\) to \(S'\).

To make this into a category, we need to define composition and identity morphisms.

a) Given functions \(f : S \to S'\) and \(g : S' \to S''\), the composite function \(g \circ f : S \to S''\) is defined in the usual way:

$$ (g \circ f)(x) = g(f(x)) $$ for all \(x \in S\).

b) Given any set \(S\), the identity function \(1_S : S \to S\) is defined in the usual way:

$$ 1_S (x) = x $$ for all \(x \in S\).

It's easy to check the associative law and the left and right unit laws - if you haven't done this before, you've gotta do now!

Notice that this category \(\mathbf{Set}\) is not a preorder, because in this category there are usually *lots* of morphisms from one object to another.

Okay, let's conclude with a few puzzles.

**Puzzle 97.** How many different categories are there with exactly 4 morphisms?

**Puzzle 98.** What does a category with exactly one object amount to? It's something we've already discussed!

**Puzzle 99.** There is a category whose only object \(x\) is this picture:

with morphisms \(f : x \to x\) being all the ways of rotating and/or reflecting this picture to get the same picture, and with composition and the identity morphism defined in the obvious way. How many morphisms are there in this category? Is this category a preorder?

**Puzzle 100.** There is a category with these 8 pictures as objects:

and all ways of rotating and/or reflecting a picture \(x\) to get a picture \(y\) as morphisms \(f : x \to y\), with composition and identities defined in the obvious way. How many morphisms are there in this category? Is this category a preorder?

**Puzzle 101.** There are certain sets \(S\) such that there's at most one function from any set to \(S\) and also at most one function from \(S\) to any set. If we take sets of this sort and functions between them, we get a "subcategory" of \(\mathbf{Set}\) that's actually a preorder. What is this preorder like?

## Comments

I am going to do the first two in reverse order:

These are monoids.

This question involves a lot of counting.

Here's a lower bound: There are at least as many categories as there are monoids of order 4. According to OEIS A058129, there are 35 monoids of order 4.

There are just the categories with one object. There are also categories with two objects, three objects, and one with four.

`I am going to do the first two in reverse order: > **Puzzle 98.** What does a category with exactly one object amount to? It's something we've already discussed! These are [monoids](https://en.wikipedia.org/wiki/Monoid). > **Puzzle 97.** How many different categories are there with exactly 4 morphisms? This question involves a lot of counting. Here's a lower bound: There are at least as many categories as there are monoids of order 4. According to [OEIS A058129](https://oeis.org/A058129), there are 35 monoids of order 4. There are just the categories with one object. There are also categories with two objects, three objects, and one with four.`

PZ100- edit: my guess..16 + 8 identities =24 morphisms total and yes, its a preorder.

`PZ100- edit: my guess..16 + 8 identities =24 morphisms total and yes, its a preorder.`

The set with at most one function out of it is the

empty set, \(\varnothing\), and the set with at most one function into it is any one element set, \(\mathbb{1}\).A preorder, with \(\varnothing\) as the bottom element and any \(\mathbb{1}\) as the top element is equivalent to preorder \(\mathbf{Bool}\).

`>**Puzzle 101.** There are certain sets \\(S\\) such that there's at most one function from any set to \\(S\\) and also at most one function from \\(S\\) to any set. If we take sets of this sort and functions between them, we get a "subcategory" of \\(\mathbf{Set}\\) that's actually a preorder. What is this preorder like? The set with at most one function out of it is the *empty set*, \\(\varnothing\\), and the set with at most one function into it is any one element set, \\(\mathbb{1}\\). A preorder, with \\(\varnothing\\) as the bottom element and any \\(\mathbb{1}\\) as the top element is equivalent to preorder \\(\mathbf{Bool}\\).`

16 morphisms seems too small IMO.

Here are all of the objects in the category:

\[ \newcommand\T{\Rule{0pt}{1em}{.3em}} \begin{array}{|c|c|c|c|} \hline \ \ ^◤& \ \ _◥& _◢\ \ & ^◣\ \ \\ \hline \ \ _◣ & _◤\ \ & ^◥\ \ & \ \ ^◢ \\ \hline \end{array} \]

For any pair of objects, there are at least two morphisms.

For instance, take \(\boxed{\ \ ^◤}\) and \(\boxed{^◣ \ \ }\). We can get from the first diagram to the second with two reflections:

\[ \begin{eqnarray} \boxed{\ \ ^◤} & \underset{\text{vertical reflection}}{\longrightarrow} & \boxed{^◥\ \ } \\ \boxed{^◥\ \ } & \underset{\text{NW-SE diagonal reflection}}{\longrightarrow} & \boxed{^◣ \ \ } \end{eqnarray} \]

We can get back by doing the same two reflections in reverse order.

Since there are are also identity morphisms,

there must be at least 64 morphisms.There are multiple transformations to get from \(\boxed{\ \ ^◤}\) to \(\boxed{^◣ \ \ }\), however. I don't know if John wants to count these as the same...

`> PZ100- my guess..16 morphisms and yes, its a preorder. 16 morphisms seems too small IMO. Here are all of the objects in the category: \\[ \newcommand\T{\Rule{0pt}{1em}{.3em}} \begin{array}{|c|c|c|c|} \hline \ \ ^◤& \ \ _◥& _◢\ \ & ^◣\ \ \\\\ \hline \ \ _◣ & _◤\ \ & ^◥\ \ & \ \ ^◢ \\\\ \hline \end{array} \\] For any pair of objects, there are at least two morphisms. For instance, take \\(\boxed{\ \ ^◤}\\) and \\(\boxed{^◣ \ \ }\\). We can get from the first diagram to the second with two reflections: \\[ \begin{eqnarray} \boxed{\ \ ^◤} & \underset{\text{vertical reflection}}{\longrightarrow} & \boxed{^◥\ \ } \\\\ \boxed{^◥\ \ } & \underset{\text{NW-SE diagonal reflection}}{\longrightarrow} & \boxed{^◣ \ \ } \end{eqnarray} \\] We can get back by doing the same two reflections in reverse order. Since there are are also identity morphisms, **there must be at least 64 morphisms**. There are multiple transformations to get from \\(\boxed{\ \ ^◤}\\) to \\(\boxed{^◣ \ \ }\\), however. I don't know if John wants to count these as the same...`

Regarding puzzle 99 and 100: The rotational and reflectional symmetries of a geometric object are given by the Dihedral group on that object.

`Regarding puzzle 99 and 100: The rotational and reflectional symmetries of a geometric object are given by the [Dihedral group](https://en.wikipedia.org/wiki/Dihedral_group) on that object.`

yes..identities i didnt count it..see [edit-pz100-24 morphisms total] above. I wonder if the total morphisms (arrows?) is or isnt related to the minimum necessary amount of arrows ,considering possible compositions..so far yes..

`yes..identities i didnt count it..see [edit-pz100-24 morphisms total] above. I wonder if the total morphisms (arrows?) is or isnt related to the minimum necessary amount of arrows ,considering possible compositions..so far yes..`

I want to get more specific.

In the case of

Puzzle 99, since we only have one object we know the category is a monoid as perPuzzle 98. Since every reflection or rotation has an inverse, this monoid must be a group.Specifically, the group here is the Dihedral 8 Group \(D_8\) (using algebraic indexing). This group has 8 elements, so to answer part of

Puzzle 99:there are 8 morphisms in that category.In the case of

Puzzle 100, I think the objectsrepresentthe morphisms inPuzzle 99. So they aren't quite the same.Perhaps

Puzzle 100is a vehicle for looking a topic in Category Theory that's missing inSeven Sketches?`> Regarding puzzle 99 and 100: The rotational and reflectional symmetries of a geometric object are given by the [Dihedral group](https://en.wikipedia.org/wiki/Dihedral_group) on that object. I want to get more specific. In the case of **Puzzle 99**, since we only have one object we know the category is a monoid as per **Puzzle 98**. Since every reflection or rotation has an inverse, this monoid must be a group. Specifically, the group here is the [Dihedral 8 Group](https://en.wikipedia.org/wiki/Dihedral_group#Matrix_representation) \\(D_8\\) (using algebraic indexing). This group has 8 elements, so to answer part of **Puzzle 99**: *there are 8 morphisms in that category*. In the case of **Puzzle 100**, I think the objects *represent* the morphisms in **Puzzle 99**. So they aren't quite the same. Perhaps **Puzzle 100** is a vehicle for looking a topic in Category Theory that's missing in *Seven Sketches*?`

Puzzle 97:Since we require identity morphisms, any category with four morphisms must have at most four objects. In fact, there is only one such category: the four-object discrete category. With three objects, we can put our fourth morphism between any two objects, or add it as a loop on a single object. In the latter case, we can choose to make this loop idempotent (\(f \circ f = f\)) or involutive (\(f \circ f = I_X\)). Thus, we have three options in categories with three objects.With two objects, we can place both morphisms in the same direction, or put them in opposing directions and demand that they be inverses. We can also add two loops to any given object, as long as the set of endomorphisms on that object gives a monoid; with three morphisms on an object, there are apparently seven such monoids up to isomorphism (OEIS A058129). Another option is to add one self-loop to each object; this gives three more possibilities, where we pick the same monoid (two choices) or different monoids (one choice) for each object. We can add a morphism \(f : X \to Y\) between the objects and add a loop \(g : X \to X\); we must have \(f \circ g = f\) since we don't have any other morphisms, but we can still choose the monoid on \(X\), for two options. Dually, we can add a morphism \(f : X \to Y\) and add a loop \(g : Y \to Y\), giving another pair of options. In total, we have \(2 + 7 + 3 + 2 + 2 = 16\) categories with two objects and four morphisms.

Lastly, with one object, we are concerned only with the number of monoids (up to isomorphism) on four elements, which is 35.

This gives \(1 + 3 + 16 + 35 = 54\) categories with four morphisms.

EDIT:OEIS disagrees. The sequence A125697 suggests my counting is off for categories with 2 objects.EDIT 2:Okay, I've gone through and corrected my counting. I missed a possibility in the class where we add one loop to each object: we can have the monoids be the same in two different ways (both idem. or both invol.) and we can have the monoids be different in one way (one idem, one invol.). The rest of my errors were just caused by referencing the wrong OEIS sequence -- I believe OEIS A058129 does count monoids up to isomorphism, even though it doesn't say so explicitly.`**Puzzle 97:** Since we require identity morphisms, any category with four morphisms must have at most four objects. In fact, there is only one such category: the four-object discrete category. With three objects, we can put our fourth morphism between any two objects, or add it as a loop on a single object. In the latter case, we can choose to make this loop idempotent (\\(f \circ f = f\\)) or involutive (\\(f \circ f = I_X\\)). Thus, we have three options in categories with three objects. With two objects, we can place both morphisms in the same direction, or put them in opposing directions and demand that they be inverses. We can also add two loops to any given object, as long as the set of endomorphisms on that object gives a monoid; with three morphisms on an object, there are apparently seven such monoids up to isomorphism ([OEIS A058129](https://oeis.org/A058129)). Another option is to add one self-loop to each object; this gives three more possibilities, where we pick the same monoid (two choices) or different monoids (one choice) for each object. We can add a morphism \\(f : X \to Y\\) between the objects and add a loop \\(g : X \to X\\); we must have \\(f \circ g = f\\) since we don't have any other morphisms, but we can still choose the monoid on \\(X\\), for two options. Dually, we can add a morphism \\(f : X \to Y\\) and add a loop \\(g : Y \to Y\\), giving another pair of options. In total, we have \\(2 + 7 + 3 + 2 + 2 = 16\\) categories with two objects and four morphisms. Lastly, with one object, we are concerned only with the number of monoids (up to isomorphism) on four elements, which is 35. This gives \\(1 + 3 + 16 + 35 = 54\\) categories with four morphisms. **EDIT:** [OEIS disagrees.](https://oeis.org/A125696) The sequence [A125697](https://oeis.org/A125697) suggests my counting is off for categories with 2 objects. **EDIT 2:** Okay, I've gone through and corrected my counting. I missed a possibility in the class where we add one loop to each object: we can have the monoids be the same in two different ways (both idem. or both invol.) and we can have the monoids be different in one way (one idem, one invol.). The rest of my errors were just caused by referencing the wrong OEIS sequence -- I believe [OEIS A058129](https://oeis.org/A058129) does count monoids up to isomorphism, even though it doesn't say so explicitly.`

Puzzle 98: As alluded to in my solution to Puzzle 97, a category with just one object is equivalent to a monoid.Puzzle 99: A cute way to keep track of morphisms is to imagine placing the square on a table, drawing numbers on each corner of the square, and drawing matching numbers on the table next to the square. (Draw the same numbers on the same corners of the back face, as though the square were see-through or something. We're just labeling vertices.) Now every possible placement of the square on the table (including passing it through a mirror first) corresponds to a permutation map, where each number on the table maps to the adjacent corner on the square.As Keith mentioned, the symmetries of the square are given by the dihedral group \(D_8\) (using the algebraic indexing convention). The permutations I described above correspond to the elements of this group (remember, every group is a permutation group). Since categories with one object are just monoids, we expect that our construction here ought to be a monoid -- and indeed, groups are just monoids with inverses.

There are eight morphisms in this category, whence the name \(D_8\). This category is

nota preorder, since in a preorder, there is at most one morphism between any pair of objects. This would necessitate that the only endomorphism on an object must be the identity, which is not the case here.Puzzle 100: We have all the same permutations as in the case of \(D_8\), meaning every object will have eight morphisms coming out of it. Because this is a group, every object also has eight morphisms coming into it -- just take inverses.Consider the effect of any particular permutation in \(D_8\) on the colored triangle. An assignment of the colored triangle to a location also uniquely determines the rest of the square; hence, if any pair of permutations send the triangle to the same place, they must be the same. So there is a unique morphism between any two objects \(X\) and \(Y\), since every object has a unique placement of the triangle. Hence, this category is just the codiscrete preorder on eight objects. This also means that there are \(8 \cdot 8 = 64\) morphisms in this category.

Puzzle 101: The requirement that a set \(S\) have at most one function from any particular set to \(S\) necessitates that \(S\) be either a singleton set or the empty set. A larger set would support at least two constant functions from any other set. On the other hand, the requirement that there be at most one function out of \(S\) into any particular set mandates that \(S\) be the empty set, since any larger set would support multiple functions into any set of size at least two. So the only candidate is the empty set, which has no maps in and the trivial, "impossible" map out for every other set. (Whichdoescount as the identity on the empty set.)Not only is this subcategory a preorder, it's also a partial order. And a total order.

`**Puzzle 98**: As alluded to in my solution to Puzzle 97, a category with just one object is equivalent to a monoid. **Puzzle 99**: A cute way to keep track of morphisms is to imagine placing the square on a table, drawing numbers on each corner of the square, and drawing matching numbers on the table next to the square. (Draw the same numbers on the same corners of the back face, as though the square were see-through or something. We're just labeling vertices.) Now every possible placement of the square on the table (including passing it through a mirror first) corresponds to a permutation map, where each number on the table maps to the adjacent corner on the square. [As Keith mentioned](https://forum.azimuthproject.org/discussion/comment/18690/#Comment_18690), the symmetries of the square are given by the dihedral group \\(D_8\\) (using the algebraic indexing convention). The permutations I described above correspond to the elements of this group (remember, [every group is a permutation group](https://en.wikipedia.org/wiki/Cayley%27s_theorem)). Since categories with one object are just monoids, we expect that our construction here ought to be a monoid -- and indeed, groups are just monoids with inverses. There are eight morphisms in this category, whence the name \\(D_8\\). This category is _not_ a preorder, since in a preorder, there is at most one morphism between any pair of objects. This would necessitate that the only endomorphism on an object must be the identity, which is not the case here. **Puzzle 100**: We have all the same permutations as in the case of \\(D_8\\), meaning every object will have eight morphisms coming out of it. Because this is a group, every object also has eight morphisms coming into it -- just take inverses. Consider the effect of any particular permutation in \\(D_8\\) on the colored triangle. An assignment of the colored triangle to a location also uniquely determines the rest of the square; hence, if any pair of permutations send the triangle to the same place, they must be the same. So there is a unique morphism between any two objects \\(X\\) and \\(Y\\), since every object has a unique placement of the triangle. Hence, this category is just the codiscrete preorder on eight objects. This also means that there are \\(8 \cdot 8 = 64\\) morphisms in this category. **Puzzle 101**: The requirement that a set \\(S\\) have at most one function from any particular set to \\(S\\) necessitates that \\(S\\) be either a singleton set or the empty set. A larger set would support at least two constant functions from any other set. On the other hand, the requirement that there be at most one function out of \\(S\\) into any particular set mandates that \\(S\\) be the empty set, since any larger set would support multiple functions into any set of size at least two. So the only candidate is the empty set, which has no maps in and the trivial, "impossible" map out for every other set. (Which _does_ count as the identity on the empty set.) Not only is this subcategory a preorder, it's also a partial order. And a total order.`

I don't think it's a partial order.

Some of the objects in this category are \(\varnothing, \{\varnothing\},\) and \( \{\{\varnothing\}\}\).

There is a unique morphism \(f : \{\varnothing\} \to \{\{\varnothing\}\}\), and another unique morphism \(g: \{\{\varnothing\}\} \to \{\varnothing\} \). So \(\{\varnothing\} \leq \{\{\varnothing\}\}\) and \(\{\{\varnothing\}\} \leq \{\varnothing\} \). But \(\{\varnothing\} \neq \{\{\varnothing\}\}\), so anti-symmetry is violated.

The quotient algebra for this partial order is

Bool. However, while there is only one initial object \(\varnothing\) (same as \(\mathtt{false}\) inBool), there is a proper class of singleton sets as final objects rather than just \(\mathtt{true}\).`> Not only is this subcategory a preorder, it's also a partial order. And a total order. I don't think it's a partial order. Some of the objects in this category are \\(\varnothing, \\{\varnothing\\},\\) and \\( \\{\\{\varnothing\\}\\}\\). There is a unique morphism \\(f : \\{\varnothing\\} \to \\{\\{\varnothing\\}\\}\\), and another unique morphism \\(g: \\{\\{\varnothing\\}\\} \to \\{\varnothing\\} \\). So \\(\\{\varnothing\\} \leq \\{\\{\varnothing\\}\\}\\) and \\(\\{\\{\varnothing\\}\\} \leq \\{\varnothing\\} \\). But \\(\\{\varnothing\\} \neq \\{\\{\varnothing\\}\\}\\), so anti-symmetry is violated. The quotient algebra for this partial order is **Bool**. However, while there is only one [initial object](https://en.wikipedia.org/wiki/Initial_and_terminal_objects) \\(\varnothing\\) (same as \\(\mathtt{false}\\) in **Bool**), there is a proper class of singleton sets as final objects rather than just \\(\mathtt{true}\\).`

Matthew wrote:

That's not the case under my reading of the problem. There are multiple maps \(\{\varnothing\} \to \{1, 2\}\), so \(\{\varnothing\}\) is not a set with the property we want.

John wrote:

I interpreted "any set" in John's problem statement to refer to all sets, not just the class of sets closed under our desired property. If we took the alternative reading, then we get a category containing the null set and all singleton sets; certainly this category is a preorder simply because we demanded it be one, but it is not a partial order for the reason you give.

`[Matthew wrote](https://forum.azimuthproject.org/discussion/comment/18698/#Comment_18698): > Some of the objects in this category are \\(\varnothing, \\{\varnothing\\},\\) and \\( \\{\\{\varnothing\\}\\}\\). That's not the case under my reading of the problem. There are multiple maps \\(\\{\varnothing\\} \to \\{1, 2\\}\\), so \\(\\{\varnothing\\}\\) is not a set with the property we want. [John wrote](https://forum.azimuthproject.org/discussion/2198/lecture-34-chapter-3-categories): > There are certain sets S such that there's at most one function from any set to S and also at most one function from S to any set. I interpreted "any set" in John's problem statement to refer to all sets, not just the class of sets closed under our desired property. If we took the alternative reading, then we get a category containing the null set and all singleton sets; certainly this category is a preorder simply because we demanded it be one, but it is not a partial order for the reason you give.`

Gotcha.

If \(\varnothing\) is the only object with just one morphism, this category is the same as

Unit.You are right, it's a partial order, a total order, and also a complete lattice.

`> I interpreted "any set" in John's problem statement to refer to all sets, not just the class of sets closed under our desired property. Gotcha. If \\(\varnothing\\) is the only object with just one morphism, this category is the same as **Unit**. You are right, it's a partial order, a total order, and also a complete lattice.`

Jonathan - great answers in comment #10! I

wantedto include both 0-element and 1-element sets in Puzzle 101, but the way I worded it, I included only the 0-element sets, of which there is only one.`Jonathan - great answers in comment #10! I _wanted_ to include both 0-element and 1-element sets in Puzzle 101, but the way I worded it, I included only the 0-element sets, of which there is only one.`

I'm having some trouble understanding Example 3.6 in the textbook. It seems to suggest the small circle arrow on the object is

nottheidentity morphismbut apath of length 1. Then how is the identity morphism represented as an arrow? I can't think of any other way than drawing an arrow from an object to itself (hence a path of length 1)...`I'm having some trouble understanding Example 3.6 in the textbook. It seems to suggest the small circle arrow on the object is **not** the _identity morphism_ but a _path of length 1_. Then how is the identity morphism represented as an arrow? I can't think of any other way than drawing an arrow from an object to itself (hence a path of length 1)...`

@Julio – That's correct, the arrow

sin the diagram is NOT the identity morphism – in fact the diagram is a graph not a category, so there is no concept of identity or composition (yet). We can turn it into a category by considering paths fromztoz– in which case the identity is the path of length zero, ie "stay where you are".`@Julio – That's correct, the arrow *s* in the diagram is NOT the identity morphism – in fact the diagram is a graph not a category, so there is no concept of identity or composition (yet). We can turn it into a category by considering paths from *z* to *z* – in which case the identity is the path of length zero, ie "stay where you are".`

There is the potential for confusing morphisms with paths.

(3.7) in Example 3.6 and Exercise 3.7\( \mathcal{N} = \textbf{Free} ( \) \( ) \)

Has many paths, \(\aleph_0\), each of which is a distinct morphism. If we add equations the number of morphisms can be limited.

Regarding comment 4 if two paths produce the same result they are the same morphism.

`There is the potential for confusing morphisms with paths. **(3.7) in Example 3.6 and [Exercise 3.7](https://forum.azimuthproject.org/discussion/2134)** \\( \mathcal{N} = \textbf{Free} ( \\) ![diagram](https://docs.google.com/drawings/d/e/2PACX-1vSNq8tGaSP6a6b5IEKXbFSWVhXVfLV5_JgG6Dmk8Awd7BTesSBvq3DKftqXOf93k_NMZbc0Z_7IV0pS/pub?w=120&h=146) \\( ) \\) Has many paths, \\(\aleph_0\\), each of which is a distinct morphism. If we add equations the number of morphisms can be limited. Regarding [comment 4](https://forum.azimuthproject.org/discussion/comment/18689/#Comment_18689) if two paths produce the same result they are the same morphism.`

By the way, Julio: it's no big deal, but the best place for asking questions about Chapter 3 is in the discussion called Chapter 3. This here is the best place for asking questions about Lecture 34, or answering puzzles from that lecture.

Sometime really soon, like in Lecture 35, I'll talk about the free category on a graph. That's what your question is really about: the difference between a graph, and the free category on that graph.

But it's much more important to ask questions than to worry about where and when to ask them! If you're puzzled by the answers so far, ask more!

`By the way, Julio: it's no big deal, but the best place for asking questions about Chapter 3 is in the discussion called [Chapter 3](https://forum.azimuthproject.org/discussion/2196/chapter-3/p1). This here is the best place for asking questions about Lecture 34, or answering puzzles from that lecture. Sometime really soon, like in Lecture 35, I'll talk about the free category on a graph. That's what your question is really about: the difference between a graph, and the free category on that graph. But it's much more important to ask questions than to worry about where and when to ask them! If you're puzzled by the answers so far, ask more!`

Puzzle 101We have a collection of sets which, due to unique arrows among themselves, necessarily forms a preorder. As the arrow between members of this 'subcategory' are unique they do not carry any additional information.

The 'subcategory' has afferent and efferent arrows to other members of

Set. It seems like there should be something interesting about those arrows.Given that we are constrained to members of

Setthe only member of this 'subcategory' seems to only be \(\emptyset\). The only inbound arrow being from itself, its identity arrow. It has a single morphism to every member ofSet. Are these properties of \(\emptyset\) only true for the categorySet?`**Puzzle 101** We have a collection of sets which, due to unique arrows among themselves, necessarily forms a preorder. As the arrow between members of this 'subcategory' are unique they do not carry any additional information. The 'subcategory' has afferent and efferent arrows to other members of **Set**. It seems like there should be something interesting about those arrows. Given that we are constrained to members of **Set** the only member of this 'subcategory' seems to only be \\(\emptyset\\). The only inbound arrow being from itself, its identity arrow. It has a single morphism to every member of **Set**. Are these properties of \\(\emptyset\\) only true for the category **Set**?`

Thanks a lot @Anindya and @Fredrick! I see the difference now. And okay @John I will shift my questions to Chapter 3 next time.

`Thanks a lot @Anindya and @Fredrick! I see the difference now. And okay @John I will shift my questions to [Chapter 3](https://forum.azimuthproject.org/discussion/2196/chapter-3/p1) next time.`

@John - Is the category in

Puzzle 100the Arrow category for the categoryPuzzle 99?`@John - Is the category in **Puzzle 100** the [Arrow category](https://en.m.wikipedia.org/wiki/Comma_category#Arrow_category) for the category **Puzzle 99**?`

About

Puzzle 97as stated the answer is infinite, because I can have say two distinct discrete categories of four objects just relabeling objects or identities. Possibly the fun is counting them up to isomorphism or maybe equivalence of cageories.`About **Puzzle 97** as stated the answer is infinite, because I can have say two distinct discrete categories of four objects just relabeling objects or identities. Possibly the fun is counting them up to isomorphism or maybe equivalence of cageories.`

Good point, Jesus! It's not totally clear what it means for two categories to be the same or different. And somehow equivalence seems like the wrong notion, since two categories can be equivalent with different numbers of objects and morphisms. Assuming isomorphism is meant, it might first be helpful to count the isomorphism classes of monoids with four or fewer elements, since every object's endomorphism monoid (the monoid of morphisms from it to itself—see Puzzle 98) must be one of these.

`Good point, Jesus! It's not totally clear what it means for two categories to be the same or different. And somehow equivalence seems like the wrong notion, since two categories can be equivalent with different numbers of objects and morphisms. Assuming isomorphism is meant, it might first be helpful to count the isomorphism classes of monoids with four or fewer elements, since every object's endomorphism monoid (the monoid of morphisms from it to itself—see Puzzle 98) must be one of these.`

Jesus wrote:

Great! I was waiting to see if anyone would notice this.

Normally when mathematicians ask you to do something like "count the number of groups with four elements", they mean to count

isomorphism classesof groups with four elements. Otherwise the answer is usually infinite, and not very interesting, since lots of groups differ only by what names you use for their elements.That's happening here too. There are infinitely many different (= unequal) categories with four morphisms.

A more interesting interpretation of Puzzle 97, therefore, is to count

isomorphism classesof categories with four morphisms. And it looks like that's what people were doing!The reason I didn't phrase the question more precisely is: 1) it's good for people to discover these issues on their own, and more importantly 2) I couldn't really define "isomorphism of categories" until after we talk about functors.

"Equivalence" is interesting too, but a definition of that concept will have to wait until after we talk about natural transformations!

I can say this now, though: if you have two equivalent categories with four morphisms, they must be isomorphic.

`Jesus wrote: > About Puzzle 97 as stated the answer is infinite, because I can have say two distinct discrete categories of four objects just relabeling objects or identities. Great! I was waiting to see if anyone would notice this. Normally when mathematicians ask you to do something like "count the number of groups with four elements", they mean to count _isomorphism classes_ of groups with four elements. Otherwise the answer is usually infinite, and not very interesting, since lots of groups differ only by what names you use for their elements. That's happening here too. There are infinitely many different (= unequal) categories with four morphisms. A more interesting interpretation of Puzzle 97, therefore, is to count _isomorphism classes_ of categories with four morphisms. And it looks like that's what people were doing! The reason I didn't phrase the question more precisely is: 1) it's good for people to discover these issues on their own, and more importantly 2) I couldn't really define "isomorphism of categories" until after we talk about functors. > Possibly the fun is counting them up to isomorphism or maybe equivalence of categories. "Equivalence" is interesting too, but a definition of that concept will have to wait until after we talk about natural transformations! I can say this now, though: if you have two equivalent categories with four morphisms, they must be isomorphic.`

Late to the party here, and actually stuck with a simple question, maybe someone will return back and will help to resolve my struggle :)

As Johnatan shown in his comment, the monoidal category with 2 morphisms, \(1\) and \(f\) has only 2 "realizations", so there are only two possible such categories (\(f \circ f = f\) and \(f \circ f = 1\)).

And, according to OEIS, there are 7 possible monoidal categories with 3 morphisms. Following the logic, if we have 3 morphisms \(1, s_1, s_2\), then \(s_1 \circ s_2 \) may be any of these 3, similar reasoning goes for \(s_1 \circ s_1\), \(s_2 \circ s_2\), and \(s_2 \circ s_1\). So if we are not counting up to isomorphism, there are \(3^4=81\) such categories. And then I've tried to reduce this number to 7 with no luck, even taking into account 2 permutations of \(s_1\) and \(s_2\), the number is not even close.

So how one achieves this magic number 7? :)

`Late to the party here, and actually stuck with a simple question, maybe someone will return back and will help to resolve my struggle :) As Johnatan shown in his [comment](https://forum.azimuthproject.org/discussion/comment/18696/#Comment_18696), the monoidal category with 2 morphisms, \\(1\\) and \\(f\\) has only 2 "realizations", so there are only two possible such categories (\\(f \circ f = f\\) and \\(f \circ f = 1\\)). And, according to OEIS, there are 7 possible monoidal categories with 3 morphisms. Following the logic, if we have 3 morphisms \\(1, s_1, s_2\\), then \\(s_1 \circ s_2 \\) may be any of these 3, similar reasoning goes for \\(s_1 \circ s_1\\), \\(s_2 \circ s_2\\), and \\(s_2 \circ s_1\\). So if we are not counting up to isomorphism, there are \\(3^4=81\\) such categories. And then I've tried to reduce this number to 7 with no luck, even taking into account 2 permutations of \\(s_1\\) and \\(s_2\\), the number is not even close. So how one achieves this magic number 7? :)`

The fact that monoids have to be associative heavily constrains the set of possibilities. This blog post goes into some detail about counting monoids and similar structures. They give a formula for "pseudomonoids" (which are really pointed magmas) as \(n \cdot n^{n \cdot n}\) (read: \(n\) choices of point and \(n^{n \cdot n}\) choices of binary operator), which can be adapted to account for the behavior of the (fixed) unit as \(n^{(n-1) \cdot (n-1)}\). When \(n = 3\), this gives exactly your result of \(81\), showing that the objects you're counting need not be associative!

`> So how one achieves this magic number 7? The fact that monoids have to be associative heavily constrains the set of possibilities. [This blog post](https://kavigupta.org/2016/07/20/Counting-Monoids/) goes into some detail about counting monoids and similar structures. They give a formula for "pseudomonoids" (which are really [pointed magmas](https://en.wikipedia.org/wiki/Magma_(algebra))) as \\(n \cdot n^{n \cdot n}\\) (read: \\(n\\) choices of point and \\(n^{n \cdot n}\\) choices of binary operator), which can be adapted to account for the behavior of the (fixed) unit as \\(n^{(n-1) \cdot (n-1)}\\). When \\(n = 3\\), this gives exactly your result of \\(81\\), showing that the objects you're counting need not be associative!`

Jonathan, you saved me, thanks a lot!

I completely forgot about associativity requirement!

EDIT:as with the monoidal category with 2 morphisms, the one with 3 gives rise to only 1 group and 6 monoids, so 6 rings may be formed from these.The group (up to isomorphism) looks like \(s_2 \circ s_2 = s_3\), \(s_3 \circ s_3 = s_2\) and \(s_2 \circ s_3 = s_3 \circ s_2 = 1\) and is abelian - it's \(\mathbb{Z}/3\).

`Jonathan, you saved me, thanks a lot! I completely forgot about associativity requirement! **EDIT:** as with the monoidal category with 2 morphisms, the one with 3 gives rise to only 1 group and 6 monoids, so 6 rings may be formed from these. The group (up to isomorphism) looks like \\(s_2 \circ s_2 = s_3\\), \\(s_3 \circ s_3 = s_2\\) and \\(s_2 \circ s_3 = s_3 \circ s_2 = 1\\) and is abelian - it's \\(\mathbb{Z}/3\\).`

Btw, since categories are associative structures, it is interesting how are they applied to octonions, which are notoriously known for their lack of associativity property?

`Btw, since categories are associative structures, it is interesting how are they applied to octonions, which are notoriously known for their lack of associativity property?`