#### Howdy, Stranger!

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

Options

# Lecture 35 - Chapter 3: Categories versus Preorders

edited May 2018

Why did I spend the first 33 lectures in a course on category theory talking, not about categories, but about preorders? It's because preorders are categories with at most one morphism from any object $$x$$ to any object $$y$$. Since there's at most one, we don't need to give it a name: we just write $$x \le y$$ if such a morphism exists. And then your experience with inequalities helps you understand what's going on!

But beware! Since there's at at most one morphism from any object $$x$$ to any object $$y$$ in a preorder, any time you have two morphisms $$f, g : x \to y$$ they are automatically equal. This hid one of the most important features of category theory, namely equations between morphisms.

The definition of category theory starts out with three fundamental equations between morphisms: the associative law

$$(h \circ g) \circ f = h \circ (g \circ f)$$ whenever we have three morphisms that can be composed, and the left and right unit laws

$$1_y \circ f = f = f \circ 1_x$$ whenever we have a morphism $$f : x \to y$$. These were all automatic and thus not mentioned in our study of preorders. As we continue, we'll see a lot more equations between morphisms - so get ready for this change of focus!

Eventually, we'll take almost everything we've done with preorders and generalize it to categories. Here's a little list of these things. It won't make sense yet, so don't worry about it too much - but I still want to show it to you:

• Preorders are a special case of "categories": they are categories with at most one object from any object to any object.
• Monotone maps between preorders are a special case of "functors" between categories: they are functors between categories that happen to be preorders.
• Left and right adjoint monotone maps between preorders are a special case of "left and right adjoint functors" between categories: they are left and right functors between categories that happen to be preorders.
• Monoidal preorders are a special case of "monoidal categories": they are monoidal categories that happen to be preorders.
• Symmetric monoidal preorders are a special case of "symmetric monoidal categories": they are symmetric monoidal categories that happen to be preorders.
• Categories enriched in monoidal preorders are a special case of "categories enriched in monoidal categories": they are categories enriched in monoidal categories that happen to be preorders.

So, there's a lot of stuff to learn - but whenever you meet one of these concepts and need some examples and insights, you can fall back on your knowledge of preorders!

In Lecture 25 we saw this Petri net:

Since we were studying preorders we treated each reaction, like "fill crust", as a mere inequality. The name of the reaction didn't really matter in our work. If there were two different ways to transform crust and filling into a lemon pie, that wouldn't affect anything at all.

Now that we're studying categories we can treat each reaction as a morphism, and write:

$$[\textrm{fill crust}] : [\textrm{crust}] + [\textrm{filling}] \to [\textrm{lemon pie}] .$$ This lets us distinguish between two different morphisms from $$[\textrm{crust}] + [\textrm{filling}]$$ to $$[\textrm{lemon pie}]$$. For example, we can distinguish between

$$[\textrm{fill crust slowly}] : [\textrm{crust}] + [\textrm{filling}] \to [\textrm{lemon pie}] .$$ and

$$[\textrm{fill crust quickly}] : [\textrm{crust}] + [\textrm{filling}] \to [\textrm{lemon pie}]$$ This is very important when we're studying real-world manufacturing processes, where there are often several ways to turn the same inputs into the same outputs.

You'll notice the $$+$$ sign in these formulas, which lets us combine resources. That's a sign that we're working with a symmetric monoidal preorder, or symmetric monoidal category. That's too fancy for us now: we'll start by studying plain old categories. So, instead of using manufacturing as an example, we'll look at something else: databases.

Puzzle 102. What is the category with the fewest morphisms that is not a preorder?

Puzzle 103. Figure out the best way to take any category $$\mathcal{C}$$ and "squash it down", getting a preorder whose elements are the objects of $$\mathcal{C}$$.

To read other lectures go here.

• Options
1.

Comment Source:In case you read this already, I just added two puzzles.
• Options
2.
edited May 2018

Puzzle 102. What is the category with the fewest morphisms that is not a preorder?

A monoid $$\mathcal{M}$$ with two morphisms, the identity $$id_\mathcal{M}$$ and a non-identity morphism $$f$$, such that $$f \circ f = f$$. $$\qquad \square$$

Puzzle 103. Figure out the best way to take any category $$\mathcal{C}$$ and "squash it down", getting a preorder whose elements are the objects of $$\mathcal{C}$$.

Let $$\mathcal{C}$$ be a category, then we can make a preorder, $$\mathcal{C}_\leq$$, via the following construction:

The objects of $$\mathcal{C}_\leq$$ are the same as $$\mathcal{C}$$,

$Ob( \mathcal{C}_\leq ) = Ob( \mathcal{C} )$

the preordering comes from there existing at least one morphism between objects (ignore how many there are if there are more than one),

\begin{align} x \leq_\mathcal{C} y = [\exists f \mid f\in \mathcal{C}(x,y)] \\ = \min(1,|\mathcal{C}(x,y)|) \end{align}

this gives reflexivity from identities, \begin{align} x \leq_\mathcal{C} x = [\exists id_x \mid id_x \in \mathcal{C}(x,x)] \\ = \min(1,|\mathcal{C}(x,x)|) \end{align}

and transitivity from composition, \begin{align} x \leq_\mathcal{C} y \wedge y \leq_\mathcal{C} z \implies x \leq_\mathcal{C} z \\ = [\exists f \mid f \in \mathcal{C}(x,y)] \wedge [\exists g \mid g \in \mathcal{C}(y,z)] \implies [\exists h \mid h = g \circ f \wedge h \in \mathcal{C}(x,z)] \\ = \min(1,|\mathcal{C}(x,y)|) \cdot \min(1,|\mathcal{C}(y,z)|) = \min(1,|\mathcal{C}(x,z)|) \end{align}

$$\qquad \square$$

Comment Source:>**Puzzle 102.** What is the category with the fewest morphisms that is not a preorder? A monoid \$$\mathcal{M}\$$ with two morphisms, the identity \$$id_\mathcal{M}\$$ and a non-identity morphism \$$f \$$, such that \$$f \circ f = f \$$. \$$\qquad \square \$$ >**Puzzle 103.** Figure out the best way to take any category \$$\mathcal{C}\$$ and "squash it down", getting a preorder whose elements are the objects of \$$\mathcal{C}\$$. Let \$$\mathcal{C}\$$ be a category, then we can make a preorder, \$$\mathcal{C}_\leq \$$, via the following construction: The objects of \$$\mathcal{C}_\leq \$$ are the same as \$$\mathcal{C} \$$, \$Ob( \mathcal{C}_\leq ) = Ob( \mathcal{C} ) \$ the preordering comes from there existing at least one morphism between objects (ignore how many there are if there are more than one), \\begin{align} x \leq_\mathcal{C} y = [\exists f \mid f\in \mathcal{C}(x,y)] \\\\ = \min(1,|\mathcal{C}(x,y)|) \end{align} \ this gives reflexivity from identities, \\begin{align} x \leq_\mathcal{C} x = [\exists id_x \mid id_x \in \mathcal{C}(x,x)] \\\\ = \min(1,|\mathcal{C}(x,x)|) \end{align} \ and transitivity from composition, \\begin{align} x \leq_\mathcal{C} y \wedge y \leq_\mathcal{C} z \implies x \leq_\mathcal{C} z \\\\ = [\exists f \mid f \in \mathcal{C}(x,y)] \wedge [\exists g \mid g \in \mathcal{C}(y,z)] \implies [\exists h \mid h = g \circ f \wedge h \in \mathcal{C}(x,z)] \\\\ = \min(1,|\mathcal{C}(x,y)|) \cdot \min(1,|\mathcal{C}(y,z)|) = \min(1,|\mathcal{C}(x,z)|) \end{align} \ \$$\qquad \square \$$
• Options
3.

Puzzle 102. What is the category with the fewest morphisms that is not a preorder?

Inspired by Jonathan's answer to puzzle 97, I would say the category with a single object, $$\star$$, and two morphisms, $$1_{\star}$$ and $$f$$. The morphisms have to obey one of the following sets of equations:

$$\begin{array}{c|cc} \circ & 1_\star & f \\ \hline 1_\star & 1_\star & f \\ f & f & 1_\star \end{array}$$ or

$$\begin{array}{c|cc} \circ & 1_\star & f \\ \hline 1_\star & 1_\star & f \\ f & f & f \end{array}$$

Comment Source:> **Puzzle 102.** What is the category with the fewest morphisms that is not a preorder? Inspired by [Jonathan's answer to puzzle 97](https://forum.azimuthproject.org/discussion/comment/18696/#Comment_18696), I would say the category with a single object, \$$\star\$$, and two morphisms, \$$1_{\star}\$$ and \$$f\$$. The morphisms have to obey one of the following sets of equations: $\begin{array}{c|cc} \circ & 1_\star & f \\\\ \hline 1_\star & 1_\star & f \\\\ f & f & 1_\star \end{array}$ or $\begin{array}{c|cc} \circ & 1_\star & f \\\\ \hline 1_\star & 1_\star & f \\\\ f & f & f \end{array}$
• Options
4.
edited May 2018

I want to try puzzle 103 again, but I want to make an algorithm.

Let's define a helper function,

$\texttt{CategoryToPreorder}( \mathrm{Obj}( \mathcal{C}_1), \mathrm{Obj}(\mathcal{C}_2), \mathrm{Obj}(\mathcal{C}_{\leq}), \mathrm{Mor}(\mathcal{C}_{\leq}) ) \overset{\mathrm{def}}{=}$

$\texttt{case } [ \exists x \mid x \in \mathrm{Obj}(\mathcal{C}_1) ] \land [ \exists y \mid y \in \mathrm{Obj}(\mathcal{C}_2) ] \land [ \exists f \mid f \in \mathcal{C}(x,y) ] \\ \texttt{ CategoryToPreorder}( \mathrm{Obj}(\mathcal{C}_1), \mathrm{Obj}(\mathcal{C}_2) \setminus \lbrace y \rbrace, \mathrm{Obj}(\mathcal{C}_\leq) \cup \lbrace x \rbrace \cup \lbrace y \rbrace, \mathrm{Mor}(\mathcal{C}_\leq) \cup \lbrace x \leq y \rbrace)$

$\texttt{case } [\exists x \mid x \in \mathrm{Obj}(\mathcal{C}_1)] \land [\exists y \mid y \in \mathrm{Obj}(\mathcal{C}_2)] \land \neg[\exists f \mid f \in \mathcal{C}(x,y)] \\ \texttt{ CategoryToPreorder}( \mathrm{Obj}(\mathcal{C}_1), \mathrm{Obj}(\mathcal{C}_2) \setminus \lbrace y \rbrace, \mathrm{Obj}(\mathcal{C}_\leq), \mathrm{Mor}(\mathcal{C}_\leq))$

$\texttt{case } [\exists x \mid x \in \mathrm{Obj}(\mathcal{C}_1)] \land [\mathrm{Obj}(\mathcal{C}_2) = \varnothing] \\ \texttt{ CategoryToPreorder}( \mathrm{Obj}(\mathcal{C}_1) \setminus \lbrace x \rbrace, \mathrm{Obj}(\mathcal{C}), \mathrm{Obj}(\mathcal{C}_\leq), \mathrm{Mor}(\mathcal{C}_\leq))$

$\texttt{case } [\mathrm{Obj}(\mathcal{C}_1) = \varnothing] \\ \texttt{ output} \langle \mathrm{Obj}(\mathcal{C}_\leq), \mathrm{Mor}(\mathcal{C}_\leq) \rangle ; \\ \texttt{ Done!}$

The idea here is that we iterate over the object set of $$\mathrm{C}$$, removing elements as we go along to avoid double counting, and adding any elements to $$\mathrm{C}_\leq$$ as we iterate.

Now we define our change-of-base proper,

$\mathrm{Preorderfy}(\mathcal{C}) \overset{\mathrm{def}}{=} \\ \texttt{CategoryToPreorder}(\mathrm{Obj}(\mathcal{C}),\mathrm{Obj}(\mathcal{C}), \varnothing, \lbrace \varnothing \leq \varnothing \rbrace).$

Edit: If anyone can pinpoint where the $$\LaTeX$$ failed, that would be wonderful.

Edit edit: Well it ain't pretty, but there it is.

Edit$$^3$$: Hmm, I think my helper function needs an extra dummy variable...

Comment Source:I want to try puzzle 103 *again*, but I want to make an algorithm. Let's define a helper function, \$\texttt{CategoryToPreorder}( \mathrm{Obj}( \mathcal{C}\_1), \mathrm{Obj}(\mathcal{C}\_2), \mathrm{Obj}(\mathcal{C}\_{\leq}), \mathrm{Mor}(\mathcal{C}\_{\leq}) ) \overset{\mathrm{def}}{=} \$ \$\texttt{case } [ \exists x \mid x \in \mathrm{Obj}(\mathcal{C}\_1) ] \land [ \exists y \mid y \in \mathrm{Obj}(\mathcal{C}\_2) ] \land [ \exists f \mid f \in \mathcal{C}(x,y) ] \\\\ \texttt{ CategoryToPreorder}( \mathrm{Obj}(\mathcal{C}\_1), \mathrm{Obj}(\mathcal{C}\_2) \setminus \lbrace y \rbrace, \mathrm{Obj}(\mathcal{C}\_\leq) \cup \lbrace x \rbrace \cup \lbrace y \rbrace, \mathrm{Mor}(\mathcal{C}\_\leq) \cup \lbrace x \leq y \rbrace) \$ \$\texttt{case } [\exists x \mid x \in \mathrm{Obj}(\mathcal{C}\_1)] \land [\exists y \mid y \in \mathrm{Obj}(\mathcal{C}\_2)] \land \neg[\exists f \mid f \in \mathcal{C}(x,y)] \\\\ \texttt{ CategoryToPreorder}( \mathrm{Obj}(\mathcal{C}\_1), \mathrm{Obj}(\mathcal{C}\_2) \setminus \lbrace y \rbrace, \mathrm{Obj}(\mathcal{C}\_\leq), \mathrm{Mor}(\mathcal{C}\_\leq)) \$ \$\texttt{case } [\exists x \mid x \in \mathrm{Obj}(\mathcal{C}\_1)] \land [\mathrm{Obj}(\mathcal{C}\_2) = \varnothing] \\\\ \texttt{ CategoryToPreorder}( \mathrm{Obj}(\mathcal{C}\_1) \setminus \lbrace x \rbrace, \mathrm{Obj}(\mathcal{C}), \mathrm{Obj}(\mathcal{C}\_\leq), \mathrm{Mor}(\mathcal{C}\_\leq)) \$ \$\texttt{case } [\mathrm{Obj}(\mathcal{C}\_1) = \varnothing] \\\\ \texttt{ output} \langle \mathrm{Obj}(\mathcal{C}\_\leq), \mathrm{Mor}(\mathcal{C}\_\leq) \rangle ; \\\\ \texttt{ Done!} \$ The idea here is that we iterate over the object set of \$$\mathrm{C}\$$, removing elements as we go along to avoid double counting, and adding any elements to \$$\mathrm{C}_\leq\$$ as we iterate. Now we define our change-of-base proper, \$\mathrm{Preorderfy}(\mathcal{C}) \overset{\mathrm{def}}{=} \\\\ \texttt{CategoryToPreorder}(\mathrm{Obj}(\mathcal{C}),\mathrm{Obj}(\mathcal{C}), \varnothing, \lbrace \varnothing \leq \varnothing \rbrace). \$ Edit: If anyone can pinpoint where the \$$\LaTeX\$$ failed, that would be wonderful. Edit edit: Well it ain't pretty, but there it is. Edit\$$^3\$$: Hmm, I think my helper function needs an extra dummy variable...
• Options
5.
edited May 2018

Keith – escaping the underscores (that is, replacing _ with \_) seems to fix the issues. For example, the following:

$\texttt{CategoryToPreorder}(\mathrm{Obj}( \mathcal{C}\_1 ), \mathrm{Obj}(\mathcal{C}\_2), \mathrm{Obj}(\mathcal{C}\_\leq), \mathrm{Mor}(\mathcal{C}\_\leq) ) :=$


renders as:

$$\texttt{CategoryToPreorder}(\mathrm{Obj}( \mathcal{C}_1 ), \mathrm{Obj}(\mathcal{C}_2), \mathrm{Obj}(\mathcal{C}_\leq), \mathrm{Mor}(\mathcal{C}_\leq) ) :=$$

Comment Source:Keith – escaping the underscores (that is, replacing _ with \_) seems to fix the issues. For example, the following: $\texttt{CategoryToPreorder}(\mathrm{Obj}( \mathcal{C}\_1 ), \mathrm{Obj}(\mathcal{C}\_2), \mathrm{Obj}(\mathcal{C}\_\leq), \mathrm{Mor}(\mathcal{C}\_\leq) ) :=$ renders as: $\texttt{CategoryToPreorder}(\mathrm{Obj}( \mathcal{C}\_1 ), \mathrm{Obj}(\mathcal{C}\_2), \mathrm{Obj}(\mathcal{C}\_\leq), \mathrm{Mor}(\mathcal{C}\_\leq) ) :=$
• Options
6.
edited May 2018

Yes, the problem is that _ has two meanings here: in Markdown it indicates italics:

_this_ gives this

while in MathJax it indicates a subscript:

\$$x_2\$$ gives $$x_2$$

Since Markdown is more fundamental here than MathJax, there's always the possibility that MathJax commands will be interpreted as Markdown. What puzzles me is how often they aren't. But you can avoid the problem by using _, as Dan explains.

The conflict seems to happen when you include text in MathJax. Let's see if I can find a minimal example:

\$$\texttt{C}_1 \to \texttt{C}_2 \$$

gives

$$\texttt{C}_1 \to \texttt{C}_2$$

No problem there!

\$$\mathrm{C}_1 \to \mathrm{C}_2 \$$

gives

$$\mathrm{C}_1 \to \mathrm{C}_2$$

No problem there either!

But this is enough to cause a problem - you'll see italics appearing after one of the underscores:

$\texttt{CategoryToPreorder}(\mathrm{Obj}( \mathcal{C}_1 ), \mathrm{Obj}(\mathcal{C}_2), \mathrm{Obj}(\mathcal{C}_\leq),$

gives

$$\texttt{CategoryToPreorder}(\mathrm{Obj}( \mathcal{C}1 ), \mathrm{Obj}(\mathcal{C}_2), \mathrm{Obj}(\mathcal{C}\leq),$$

Comment Source:Yes, the problem is that _ has two meanings here: in Markdown it indicates italics: _this_ gives _this_ while in MathJax it indicates a subscript: \$$x_2\$$ gives \$$x_2\$$ Since Markdown is more fundamental here than MathJax, there's always the possibility that MathJax commands will be interpreted as Markdown. What puzzles me is how often they _aren't_. But you can avoid the problem by using \_, as Dan explains. The conflict seems to happen when you include text in MathJax. Let's see if I can find a minimal example: \$$\texttt{C}_1 \to \texttt{C}_2 \$$ gives \$$\texttt{C}_1 \to \texttt{C}_2 \$$ No problem there! \$$\mathrm{C}_1 \to \mathrm{C}_2 \$$ gives \$$\mathrm{C}_1 \to \mathrm{C}_2 \$$ No problem there either! But this is enough to cause a problem - you'll see italics appearing after one of the underscores: $\texttt{CategoryToPreorder}(\mathrm{Obj}( \mathcal{C}_1 ), \mathrm{Obj}(\mathcal{C}_2), \mathrm{Obj}(\mathcal{C}_\leq),$ gives $\texttt{CategoryToPreorder}(\mathrm{Obj}( \mathcal{C}_1 ), \mathrm{Obj}(\mathcal{C}_2), \mathrm{Obj}(\mathcal{C}_\leq),$ 
• Options
7.

Just trying to fix the above, Mathjax also doesn't like long formulas.

Comment Source:Just trying to fix the above, Mathjax *also* doesn't like long formulas.
• Options
8.

Puzzle 103. Figure out the best way to take any category $$\mathcal{C}$$ and "squash it down", getting a preorder whose elements are the objects of $$\mathcal{C}$$.

I would define $$\leq_{\mathcal{C}}$$ with:

$X \leq_{\mathcal{C}} Y \equiv \mathrm{Hom}(X,Y) \neq \varnothing$

Where $$\mathrm{Hom}(X,Y)$$ is the set of morphisms between $$X$$ and $$Y$$.

If $$\mathcal{C}$$ is already a preorder, this doesn't do anything to it.

Comment Source:> **Puzzle 103.** Figure out the best way to take any category \$$\mathcal{C}\$$ and "squash it down", getting a preorder whose elements are the objects of \$$\mathcal{C}\$$. I would define \$$\leq_{\mathcal{C}}\$$ with: \$X \leq_{\mathcal{C}} Y \equiv \mathrm{Hom}(X,Y) \neq \varnothing \$ Where \$$\mathrm{Hom}(X,Y)\$$ is the [set of morphisms](https://en.wikipedia.org/wiki/Morphism#Hom-set) between \$$X\$$ and \$$Y\$$. If \$$\mathcal{C}\$$ is already a preorder, this doesn't do anything to it.
• Options
9.

Actually, if anyone knows any good literature on set-based algorithms, maybe I can clean up my attempt above.

Comment Source:Actually, if anyone knows any good literature on set-based algorithms, maybe I can clean up my attempt above.
• Options
10.
edited May 2018

Actually, if anyone knows any good literature on set-based algorithms, maybe I can clean up my attempt above.

Well, in Haskell there's Data.Set in the containers module. This is for representing finite sets. The docs carefully talk about the complexity of all operations. This is nice if you want to micro-optimize your algorithm.

There's also Data.HashSet which is more like sets in Python or Clojure.

In a computer proof system definitions tend to be declarative rather than recursive. This is because proving the correctness of recursive algorithms is hard. For instance, check out John Wiegley's Comma-Category construction in Coq. He just declares his Comma category hom-set in terms of a base hom-set and proves the definition is well defined, rather than using recursion or fixedpoints.

If there's a HoTT expert around, I am curious how they approach this problem.

Comment Source:> Actually, if anyone knows any good literature on set-based algorithms, maybe I can clean up my attempt above. Well, in Haskell there's [Data.Set](https://hackage.haskell.org/package/containers-0.5.11.0/docs/Data-Set.html) in the containers module. This is for representing finite sets. The docs carefully talk about the complexity of all operations. This is nice if you want to micro-optimize your algorithm. There's also [Data.HashSet](https://hackage.haskell.org/package/unordered-containers-0.2.9.0/docs/Data-HashSet.html) which is more like sets in Python or Clojure. In a computer proof system definitions tend to be declarative rather than recursive. This is because proving the correctness of recursive algorithms is hard. For instance, check out John Wiegley's [Comma-Category construction in Coq](https://github.com/jwiegley/category-theory/blob/master/Construction/Comma.v). He just declares his Comma category *hom-set* in terms of a base *hom-set* and proves the definition is well defined, rather than using recursion or fixedpoints. If there's a HoTT expert around, I am curious how they approach this problem.
• Options
11.

I am not quite sure what you mean by set based algorithms?

Comment Source:I am not quite sure what you mean by set based algorithms?
• Options
12.

An algorithm that works on sets, as opposed to one that works on trees or lists...

Chop it up to loose terminology.

Comment Source:An algorithm that works on sets, as opposed to one that works on trees or lists... Chop it up to loose terminology. 
• Options
13.
edited May 2018

Hey Chris,

I am not quite sure what you mean by set based algorithms?

If you read Keith's definition you can see he's trying to do structural recursion on sets to define his preorder relation.

Comment Source:Hey Chris, > I am not quite sure what you mean by set based algorithms? If you read Keith's definition you can see he's trying to do structural recursion on sets to define his preorder relation.
• Options
14.

Ah, well, can't you just .. check if the hom set is empty? I mean being able to index the morphisms by source and target is pretty fundamental to doing anything useful with the category.

Comment Source: Ah, well, can't you just .. check if the hom set is empty? I mean being able to index the morphisms by source and target is pretty fundamental to doing anything useful with the category.
• Options
15.
edited May 2018

@Chris, if you scroll up a bit I think you’ll see what I think of your proposal...

Comment Source:@Chris, if you scroll up a bit I think you’ll see what I think of your proposal...
• Options
16.

Yeah, but that's nowhere near as fun as a full recursive algorithm.

Comment Source:Yeah, but that's nowhere near as fun as a full recursive algorithm.
• Options
17.
edited May 2018

Puzzle 102. What is the category with the fewest morphisms that is not a preorder?

Dan Oneata gave a nice answer in comment #3: he chose the unique category with a single object, $$\star$$, and two morphisms, $$1_{\star}$$ and $$f$$, such that $$f \circ f = 1_\star$$.

Puzzle 102$${}^\prime$$. What's the usual name for this category?

Hint: a category with one object is the same as a monoid, and a monoid where every element has an inverse is called a group.

Comment Source:**Puzzle 102.** What is the category with the fewest morphisms that is not a preorder? Dan Oneata gave a nice answer in comment #3: he chose the unique category with a single object, \$$\star\$$, and two morphisms, \$$1_{\star}\$$ and \$$f\$$, such that \$$f \circ f = 1\_\star\$$. **Puzzle 102\$${}^\prime\$$.** What's the usual name for this category? Hint: a category with one object is the same as a [monoid](https://en.wikipedia.org/wiki/Monoid), and a monoid where every element has an inverse is called a [group](https://en.wikipedia.org/wiki/Group_(mathematics)).
• Options
18.
edited May 2018

Puzzle 103. Figure out the best way to take any category $$\mathcal{C}$$ and "squash it down", getting a preorder whose elements are the objects of $$\mathcal{C}$$.

Matthew wrote:

I would define $$\leq_{\mathcal{C}}$$ with:

$$X \leq_{\mathcal{C}} Y \equiv \mathrm{Hom}(X,Y) \neq \varnothing$$ where $$\mathrm{Hom}(X,Y)$$ is the
set of morphisms between $$X$$ and $$Y$$.

1. Given a category, create a preorder by decreeing $$x \le y$$ iff there's a morphism from $$x$$ to $$y$$.

2. Given a category, identify all morphisms from $$x$$ to $$y$$ - that is, decree them all to be equal - so that there's at most one morphism from $$x$$ to $$y$$.

These are equivalent because we can think of a preorder as a category with at most one morphism from any object $$x$$ to any object $$y$$: we write $$x \le y$$ iff such a morphism exists.

Comment Source:**Puzzle 103.** Figure out the best way to take any category \$$\mathcal{C}\$$ and "squash it down", getting a preorder whose elements are the objects of \$$\mathcal{C}\$$. Matthew wrote: > I would define \$$\leq_{\mathcal{C}}\$$ with: > $X \leq_{\mathcal{C}} Y \equiv \mathrm{Hom}(X,Y) \neq \varnothing$ > where \$$\mathrm{Hom}(X,Y)\$$ is the [set of morphisms](https://en.wikipedia.org/wiki/Morphism#Hom-set) between \$$X\$$ and \$$Y\$$. Right! Here are two equivalent ways to think about this trick: 1. Given a category, create a preorder by decreeing \$$x \le y\$$ iff there's a morphism from \$$x\$$ to \$$y\$$. 2. Given a category, identify all morphisms from \$$x\$$ to \$$y\$$ - that is, decree them all to be equal - so that there's at most one morphism from \$$x\$$ to \$$y\$$. These are equivalent because we can think of a preorder as a category with at most one morphism from any object \$$x\$$ to any object \$$y\$$: we write \$$x \le y\$$ iff such a morphism exists.
• Options
19.
edited May 2018

How is #17 not a preorder.

I presume that the unique category with a single object, $$\star$$, and one morphism, $$1_{\star}$$ is a preorder.

Is it because $$f \neq 1_{\star}$$?

Why does that matter?

Comment Source:How is [#17](https://forum.azimuthproject.org/discussion/comment/18836/#Comment_18836) not a preorder. I presume that the unique category with a single object, \$$\star\$$, and one morphism, \$$1_{\star}\$$ is a preorder. Is it because \$$f \neq 1_{\star} \$$? Why does that matter?
• Options
20.

John wants two unique morphisms.

Comment Source:John wants two *unique* morphisms.
• Options
21.
edited May 2018

Puzzle 102$${}^\prime$$. What's the usual name for this category?

The group $$\mathbb{Z}_2$$!

Comment Source:> **Puzzle 102\$${}^\prime\$$.** What's the usual name for this category? The group \$$\mathbb{Z}_2\$$!
• Options
22.
edited May 2018

Sophie - yes! It's the smallest group worth getting excited about - not to knock our humble friend the trivial group.

Comment Source:Sophie - yes! It's the [smallest group worth getting excited about](https://mathoverflow.net/questions/148925/fantastic-properties-of-z-2z) - not to knock our humble friend the trivial group. 
• Options
23.

John, in your solution to Puzzle 102 why have you chosen one of two categories mentioned by Dan in #3? Aren't they both equally valid answers?

Comment Source:John, in your solution to Puzzle 102 why have you chosen one of two categories mentioned by Dan in #3? Aren't they both equally valid answers?
• Options
24.
edited May 2018

Fredrick wrote in comment #19:

I presume that the unique category with a single object, $$\star$$, and one morphism, $$1_{\star}$$ is a preorder.

Yes.

A preorder is a category where there's at most one morphism from any object to any object. So, the smallest category that's not a preorder will have one object, say $$\star$$, and two morphisms from that object to itself.

What are these morphisms like? One of them must be the identity $$1_\star : \star \to \star$$. The other is something else, call it $$f : \star \to \star.$$

We must have

$$1_\star \circ 1_\star = 1_\star$$ and we must have

$$f \circ 1_\star = f= 1_\star \circ f .$$ So, the only question is: what's $$f \circ f$$? Apparently there are two possibilities: $$1_\star$$ and $$f$$.

Puzzle. Why did Dan Oneata choose $$f \circ f = 1_\star$$?

Comment Source:Fredrick wrote in comment #19: > I presume that the unique category with a single object, \$$\star\$$, and one morphism, \$$1_{\star}\$$ is a preorder. Yes. A preorder is a category where there's at most one morphism from any object to any object. So, the smallest category that's _not_ a preorder will have one object, say \$$\star\$$, and _two_ morphisms from that object to itself. What are these morphisms like? One of them must be the identity \$$1\_\star : \star \to \star\$$. The other is something else, call it \$$f : \star \to \star.\$$ We must have $1\_\star \circ 1_\star = 1\_\star$ and we must have $f \circ 1\_\star = f= 1\_\star \circ f .$ So, the only question is: what's \$$f \circ f \$$? Apparently there are two possibilities: \$$1\_\star\$$ and \$$f\$$. **Puzzle.** Why did Dan Oneata choose \$$f \circ f = 1\_\star\$$?
• Options
25.

Erm, didn't Dan give both alternatives rather than choosing one? (We are talking about his comment #3, right?)

Comment Source:Erm, didn't Dan give both alternatives rather than choosing one? (We are talking about his comment #3, right?) 
• Options
26.
edited May 2018

Oh, so he did! I only noticed the first one, for some reason! Sorry, Dan!

The answer to my puzzle was going to be: "he chose $$f \circ f = 1_\star$$ because he felt like it."

But anyway, $$f \circ f = f$$ also works fine. It gives a monoid with two elements that's not a group.

Puzzle 102$${}^{\prime\prime}$$. What's are some names for this monoid?

Comment Source:Oh, so he did! I only noticed the first one, for some reason! Sorry, Dan! The answer to my puzzle was going to be: "he chose \$$f \circ f = 1\_\star\$$ because he _felt like it_." <img src = "http://math.ucr.edu/home/baez/emoticons/tongue2.gif"> But anyway, \$$f \circ f = f\$$ also works fine. It gives a monoid with two elements that's not a group. **Puzzle 102\$${}^{\prime\prime}\$$.** What's are some names for this monoid?
• Options
27.

If we are talking about comment #3 then you are right Simon.

But if we ignore the fact that Dan didn't choose one over the other, then presumably John preferred the version with $$f \circ f = 1_\star$$ because then f has an inverse (and hence is then a group).

Comment Source:If we are talking about comment #3 then you are right Simon. But if we ignore the fact that Dan didn't choose one over the other, then presumably John preferred the version with \$$f \circ f = 1\_\star\$$ because then f has an inverse (and hence is then a group). 
• Options
28.
edited May 2018

I would call such a monoid an idempotent monoid since $$f$$ follows the rule, $$f\circ f = f$$.

Edit: Or more generally, if we let, $\large f^{\circ n} = \underbrace{f\circ f\circ f\circ \cdots f}_{n \text{ times}}$

then an idempotent monoid is a monoid with a unique morphism, $\large f = f^{\circ n}, \text{for some } n \in \mathbb{N}.$

Comment Source:I would call such a monoid an *idempotent monoid* since \$$f\$$ follows the rule, \$$f\circ f = f \$$. Edit: Or more generally, if we let, \$\large f^{\circ n} = \underbrace{f\circ f\circ f\circ \cdots f}_{n \text{ times}} \$ then an *idempotent monoid* is a monoid with a unique morphism, \$\large f = f^{\circ n}, \text{for some } n \in \mathbb{N}. \$
• Options
29.

Is it the Any monoid?

Comment Source:Is it the Any monoid?
• Options
30.

What exactly is the Any monoid? What operations are valid on it?

Comment Source:What exactly is the Any monoid? What operations are valid on it?
• Options
31.

It's just another name for "or" with id=0, f=1. But I am calling it Any because a morphism to it is what you want if you are asking "is there some way to build it out of a list containing one of these elements."

Comment Source:It's just another name for "or" with id=0, f=1. But I am calling it Any because a morphism to it is what you want if you are asking "is there some way to build it out of a list containing one of _these_ elements."
• Options
32.
edited May 2018

So like the question "Does this word contain 'ab'?" is a homomorphism to Any.

Comment Source:So like the question "Does this word contain 'ab'?" is a homomorphism to Any.
• Options
33.

I would answer "$$\mathbb{Z}/(2)$$" to both Puzzle 102' and Puzzle 102''—but I would mean the group under addition in the first case, and the monoid under multiplication in the second!

Comment Source:I would answer "\$$\mathbb{Z}/(2)\$$" to both Puzzle 102' and Puzzle 102''—but I would mean the group under addition in the first case, and the monoid under multiplication in the second!
• Options
34.

The title says Chapter 2, it should be 3.

Comment Source:The title says Chapter 2, it should be 3.
• Options
35.

Whoops! Fixed.

Comment Source:Whoops! Fixed.
• Options
36.
edited May 2018

Owen wrote:

I would answer "$$\mathbb{Z}/2$$" to both Puzzle 102' and Puzzle 102''—but I would mean the group under addition in the first case, and the monoid under multiplication in the second!

Okay, good! If you want to be polite to mathematicians, you should say $$(\mathbb{Z}/2, +)$$ as your answer to Puzzle 102$${}^\prime$$ and $$(\mathbb{Z}/2, \cdot )$$ as your answer to Puzzle 102$${}^{\prime\prime}$$ - that's how mathematicians distinguish between the same set made into monoids with two different operations.

If you just write $$\mathbb{Z}/2$$, all mathematicians will assume you mean the group $$(\mathbb{Z}/2, +)$$.

Another nice name for the monoid $$( \mathbb{Z}/2, \cdot )$$ is $$(\textbf{Bool}, \wedge)$$, since we can think of 0 as "false" and 1 as "true", and then multiplication becomes "and".

This monoid is also isomorphic to $$(\textbf{Bool}, \vee)$$, but now the identity element is "false", not "true"!

Another nice name for the group $$(\mathbb{Z}/2, +)$$ is $$(\textbf{Bool}, \mathrm{XOR})$$, since "exclusive or" makes the Booleans into a group that's isomorphic to $$(\mathbb{Z}/2, +)$$.

And finally, if you make $$\mathbb{Z}/2$$ into a ring with both addition and multiplication as its operations, mathematicians often call it $$\mathbb{F}_2$$, because it's the field with two elements. You can also think of this field as the Booleans with "exclusive or" as addition and "and" as multiplication.

Comment Source:Owen wrote: > I would answer "\$$\mathbb{Z}/2\$$" to both Puzzle 102' and Puzzle 102''—but I would mean the group under addition in the first case, and the monoid under multiplication in the second! Okay, good! If you want to be polite to mathematicians, you should say \$$(\mathbb{Z}/2, +) \$$ as your answer to Puzzle 102\$${}^\prime\$$ and \$$(\mathbb{Z}/2, \cdot ) \$$ as your answer to Puzzle 102\$${}^{\prime\prime}\$$ - that's how mathematicians distinguish between the same set made into monoids with two different operations. If you just write \$$\mathbb{Z}/2\$$, all mathematicians will assume you mean the group \$$(\mathbb{Z}/2, +) \$$. Another nice name for the monoid \$$( \mathbb{Z}/2, \cdot ) \$$ is \$$(\textbf{Bool}, \wedge) \$$, since we can think of 0 as "false" and 1 as "true", and then multiplication becomes "and". This monoid is also isomorphic to \$$(\textbf{Bool}, \vee) \$$, but now the identity element is "false", not "true"! Another nice name for the group \$$(\mathbb{Z}/2, +) \$$ is \$$(\textbf{Bool}, \mathrm{XOR}) \$$, since ["exclusive or"](https://en.wikipedia.org/wiki/Exclusive_or) makes the Booleans into a group that's isomorphic to \$$(\mathbb{Z}/2, +) \$$. And finally, if you make \$$\mathbb{Z}/2\$$ into a _ring_ with both addition and multiplication as its operations, mathematicians often call it \$$\mathbb{F}_2\$$, because it's the [field with two elements](https://en.wikipedia.org/wiki/GF(2)). You can also think of this field as the Booleans with "exclusive or" as addition and "and" as multiplication. 
• Options
37.
edited June 2018

And finally, if you make $$\mathbb{Z}/2$$ into a ring with both addition and multiplication as its operations, mathematicians often call it $$\mathbb{F}_2$$, because it's the field with two elements.

Incidentally, fields -- along with rings, vector spaces, modules, etc -- are examples of objects which, like monoidal preorders, have multiple structures interacting in some way. Fields and rings have both a "multiplication" and an "addition", and impose constraints on how they may interact. Modules and vector spaces are even more fun, since they're basically just commutative groups (for vector addition) that are acted upon by a ring or field (for scalar multiplication).

Each piece of these objects is interesting on its own: you can fit all of the objects above together using little more than groups, group actions, and some coherence conditions between the structures. But you can often get more interesting structures from their composition than by studying the individual pieces.

We've already seen interesting structures arise this way in this very course. Preorders are another fundamental building block, and when we combine monoids and preorders in a certain way, we get monoidal preorders. $$\mathcal{V}$$-enriched categories combine a monoidal preorder (or a monoidal category more generally) with a binary function out of a set, satisfying certain coherence properties between these two pieces.

It wouldn't surprise me if there was a categorical way to frame this composition of structures. Like, a ring would be a special kind of object in the product category over rings.

Comment Source:[John wrote](https://forum.azimuthproject.org/discussion/comment/18880/#Comment_18880): > And finally, if you make \$$\mathbb{Z}/2\$$ into a _ring_ with both addition and multiplication as its operations, mathematicians often call it \$$\mathbb{F}_2\$$, because it's the [field with two elements](https://en.wikipedia.org/wiki/GF(2)). Incidentally, fields -- along with rings, vector spaces, modules, etc -- are examples of objects which, like monoidal preorders, have multiple structures interacting in some way. Fields and rings have both a "multiplication" and an "addition", and impose constraints on how they may interact. Modules and vector spaces are even more fun, since they're basically just commutative groups (for vector addition) that are _acted upon_ by a ring or field (for scalar multiplication). Each piece of these objects is interesting on its own: you can fit all of the objects above together using little more than [groups](https://en.wikipedia.org/wiki/Group_(mathematics)), [group actions](https://en.wikipedia.org/wiki/Group_action), and some coherence conditions between the structures. But you can often get more interesting structures from their composition than by studying the individual pieces. We've already seen interesting structures arise this way in this very course. Preorders are another fundamental building block, and when we combine monoids and preorders in a certain way, we get monoidal preorders. \$$\mathcal{V}\$$-enriched categories combine a monoidal preorder (or a monoidal category more generally) with a binary function out of a set, satisfying certain coherence properties between these two pieces. It wouldn't surprise me if there was a categorical way to frame this composition of structures. Like, a ring would be a special kind of object in the product category over rings.
• Options
38.

Jonathan Castello wrote:

It wouldn't surprise me if there was a categorical way to frame this composition of structures. Like, a ring would be a special kind of object in the product category over rings.

At least in some cases, there is! You may already know that the slogan "A monoidal preorder is a monoid object in the category of preorders" is a slick way of rolling up all the definitions into one categorical concept. In the same sense, a ring is just a "monoid object" in the category of abelian groups. I haven't looked ahead to see if the book covers "monoid objects," but I hope we will in this course.

Comment Source:Jonathan Castello wrote: > It wouldn't surprise me if there was a categorical way to frame this composition of structures. Like, a ring would be a special kind of object in the product category over rings. At least in some cases, there is! You may already know that the slogan "A monoidal preorder is a monoid object in the category of preorders" is a slick way of rolling up all the definitions into one categorical concept. In the same sense, a ring is just a "monoid object" in the category of abelian groups. I haven't looked ahead to see if the book covers "monoid objects," but I hope we will in this course.
• Options
39.
edited June 2018

If I recall, a commutative monoid is a monoid object in the category of monoids.

A monad is a monoid object in the category of endofunctors for some category $$\mathcal{C}$$.

And most impressively, a monoidal category is a monoid object in ($$\mathbf{Set}$$-category)-category.

Edit: I could also be wrong and I'm getting waaaaaaaay ahead of myself.

Comment Source:If I recall, a commutative monoid is a monoid object in the category of monoids. A monad is a monoid object in the category of endofunctors for some category \$$\mathcal{C}\$$. And most impressively, a monoidal category is a monoid object in (\$$\mathbf{Set}\$$-category)-category. Edit: I could also be wrong and I'm getting waaaaaaaay ahead of myself.
• Options
40.
edited June 2018

Owen wrote:

I haven't looked ahead to see if the book covers "monoid objects," but I hope we will in this course.

I hope so too, but I don't actually know! There is a lot to talk about.

Comment Source:Keith: all your remarks are right! But you're getting ahead of the course, so let's talk about this more later. Owen wrote: > I haven't looked ahead to see if the book covers "monoid objects," but I hope we will in this course. I hope so too, but I don't actually know! There is a lot to talk about.
• Options
41.
edited June 2018

Lots of insightful comments here, John thanks for showing how to relate monoids to groups and fields!

EDIT Btw, clearly $$\mathbb{F}_2$$ is a ring, because it is a monoid under "multiplication", but still it's called a field, why so?

Comment Source:Lots of insightful comments here, John thanks for showing [how to relate monoids to groups and fields](https://forum.azimuthproject.org/discussion/comment/18880/#Comment_18880)! **EDIT** Btw, clearly \$$\mathbb{F}_2\$$ is a **ring**, because it is a monoid under "multiplication", but still it's called a **field**, why so?
• Options
42.

Fields are just a special case of rings: for a ring to be a field, the multiplication operation must be commutative and every nonzero element must have a multiplicative inverse. (So, for example, the sets $$\mathbb{Q}$$, $$\mathbb{R}$$, and $$\mathbb{C}$$ of rational numbers, real numbers, and complex numbers all form fields, but the set $$\mathbb{Z}$$ of integers does not form a field because not every nonzero integer has a multiplicative inverse that is also an integer.)

Fields are nice, because (for example) a lot of matrix algorithms require you to be able to divide by nonzero entries, so it's useful to work with fields when you can. On the other hand, those extra axioms mean that you might come across situations where you have a ring but not a field, and then those algorithms don't work.

Comment Source:Fields are just a special case of rings: for a ring to be a field, the multiplication operation must be commutative and every nonzero element must have a multiplicative inverse. (So, for example, the sets \$$\mathbb{Q}\$$, \$$\mathbb{R}\$$, and \$$\mathbb{C}\$$ of rational numbers, real numbers, and complex numbers all form fields, but the set \$$\mathbb{Z}\$$ of integers does not form a field because not every nonzero integer has a multiplicative inverse that is *also* an integer.) Fields are nice, because (for example) a lot of matrix algorithms require you to be able to divide by nonzero entries, so it's useful to work with fields when you can. On the other hand, those extra axioms mean that you might come across situations where you have a ring but not a field, and then those algorithms don't work.
• Options
43.

Thanks Owen, but $$(\mathbb{Z}/2, \cdot)$$, which corresponds to the discussed example, when $$f \circ f = f$$, seems to be a monoid, because there is no inverse for $$f$$, right?

So $$(\mathbb{Z}/2, +)$$, $$(\mathbb{Z}/2, \cdot)$$ is a ring, but is called a field, and this is the source of my confusion :)

Comment Source:Thanks Owen, but \$$(\mathbb{Z}/2, \cdot)\$$, which corresponds to the discussed example, when \$$f \circ f = f\$$, seems to be a monoid, because there is no inverse for \$$f\$$, right? So \$$(\mathbb{Z}/2, +)\$$, \$$(\mathbb{Z}/2, \cdot)\$$ is a ring, but is called a field, and this is the source of my confusion :)
• Options
44.
edited June 2018

Hmm but in a field you can't divide by zero, so you are demanded a multiplicative group only after you strip zero away. In $$(\mathbb{Z}/2, \cdot)$$ you have two actions in $$\{0,1\}$$: the identity, and the one that zeroes all (and obeys $$f \circ f = f$$). You exclude the later, and you get a singleton group where the identity is its own inverse. You have operation tables here.

EDIT: to actions -> two actions

Comment Source:Hmm but in a field you can't divide by zero, so you are demanded a multiplicative group only after you strip zero away. In \$$(\mathbb{Z}/2, \cdot)\$$ you have two actions in \$$\\{0,1\\}\$$: the identity, and the one that zeroes all (and obeys \$$f \circ f = f\$$). You exclude the later, and you get a singleton group where the identity is its own inverse. You have operation tables [here](https://en.wikipedia.org/wiki/GF(2)). EDIT: to actions -> *two* actions
• Options
45.
edited June 2018

Thanks Jesus, this is what I've missed - exclusion of 0 ($$f$$) when searching for multiplicative inverses.

Indeed, we have 2 categories, which are separately mapped to $$(\mathbb{Z}/2, +)$$ and $$(\mathbb{Z}/2, \cdot)$$, so $$f \cong 0$$ under $$\cdot$$, but $$f \cong 1$$ under $$+$$.

Comment Source:Thanks Jesus, this is what I've missed - exclusion of 0 (\$$f\$$) when searching for multiplicative inverses. Indeed, we have 2 categories, which are separately mapped to \$$(\mathbb{Z}/2, +)\$$ and \$$(\mathbb{Z}/2, \cdot)\$$, so \$$f \cong 0\$$ under \$$\cdot\$$, but \$$f \cong 1\$$ under \$$+\$$.
• Options
46.
edited June 2018

John wrote:

And finally, if you make $$\mathbb{Z}/2$$ into a ring with both addition and multiplication as its operations, mathematicians often call it $$\mathbb{F}_2$$

So here what was meant is "field", not "ring" (although field is a ring, of course), or this is another subtlety which I'm missing - for some reason John emphasized the word ring.

Comment Source:John wrote: >And finally, if you make \$$\mathbb{Z}/2\$$ into a *ring* with both addition and multiplication as its operations, mathematicians often call it \$$\mathbb{F}_2\$$ So here what was meant is "**field**", not "**ring**" (although field is a ring, of course), or this is another subtlety which I'm missing - for some reason John emphasized the word *ring*. 
• Options
47.
edited June 2018

No more subtleties, he was remarking just that there was multiplication also beyond addition in the game. Agreed also with your #45.

Comment Source:No more subtleties, he was remarking just that there was multiplication also beyond addition in the game. Agreed also with your #45.
• Options
48.

I think John used the word ring just because rings are a lot more diverse then fields.

Comment Source: I think John used the word ring just because rings are a lot more diverse then fields.