Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Preorders and monoidal preorders

Julius (Jul 23 2023 at 14:01):

A preorder is a binary relation that is reflexive and transitive. Right?

If so, why is it called a “preorder”?

I anticipate the obvious answer is because it’s a few steps away from being an order. But does it have to be conceptually viewed as a kind of “order”?

For example, why not just call it a “reflexive transitive binary relation”?

Julius (Jul 23 2023 at 14:04):

A monoidal preorder has a binary operation which has an identity object and is associative.

A binary operation is (X, X) -> X. A binary relation is R \subset X x X.

But I think there is some discussion in Spivak and Fong, chapter 5, about how XxX -> X is structurally identical to just XxXxX. They say, “it’s just a matter of book-keeping”.

Julius (Jul 23 2023 at 14:05):

Is there a presentation of a monoidal preorder where it’s actually a binary relation and a trinary relation?

Are there analogous concepts to “associative” and “identity object”, for a trinary relation?

Julius (Jul 23 2023 at 14:06):

Thanks very much :pray:

Mike Shulman (Jul 23 2023 at 14:35):

Julius said:

But does it have to be conceptually viewed as a kind of “order”?

It doesn't have to be viewed that way, but it can be, and it's very often useful to view it that way. Most names in mathematics come from some way of viewing the definiens; often there are others, but the one giving rise to the name is either most useful, historically first, or both.

For example, why not just call it a “reflexive transitive binary relation”?

Well, it's nine syllables longer, for one.

Mike Shulman (Jul 23 2023 at 14:39):

Julius said:

Is there a presentation of a monoidal preorder where it’s actually a binary relation and a trinary relation?

(Side note: I think "ternary" is more common than "trinary" for a three-place relation.)

Just as you can always encode an ordinary function as a binary relation (its graph), you can always encode a binary function as a ternary relation. So yes, a monoidal preorder can be defined as a set with a binary relation and a ternary relation satisfying some axioms. For instance, one of the axioms on the ternary relation $M \subseteq X\times X\times X$ would be "for all $x,y\in X$ there exists a unique $z\in X$ such that $(x,y,z)\in M$", ensuring that $M$ is the graph of a binary function. And then you can formulate associativity as something like "for all $x,y,z,u,v\in X$, if $(x,y,u)\in M$ and $(u,z,v)\in M$, then there exists $w\in X$ such that $(y,z,w)\in M$ and $(x,w,v)\in M$".

Julius (Jul 23 2023 at 14:50):

Thanks. But does that lead you somewhere interest or insightful, to blur the difference between the preorder relation, and the binary operation, and consider it just a set with two relations (one binary, one ternary)? I can check Chapter 5, but I think Spivak and Fong talk about how “new difficulties emerge” or something when you allow yourself a certain kind of abstraction. Let me check.

Julius (Jul 23 2023 at 14:53):

This is what I’m currently studying, it’s a challenge for me.E45ED9A1-50B5-4EEE-9CBF-CBD41DB82079.png

Julius (Jul 23 2023 at 14:58):

A v-category or enriched category is a set of objects Ob(X) where the hom-sets (a, b) \in X x X are associated to some element in some (symmetric) monoidal preorder V (-> question to self: what happens if the preorder is not symmetric? what is the intuitive significance of the monoidal operation on the preorder, a canonical example?) -

Mike Shulman (Jul 23 2023 at 14:59):

Well, yes and no. If you're actually working with monoidal preorders in practice, then there's little to be gained by complicating your notation this way. But it can be technically useful, e.g. it enables the theory to be described in a framework of logic that has only relations and not functions, which is simpler for some metatheoretic purposes. More importantly, it can lead to useful generalizations of the notion of monoidal preorder.

Mike Shulman (Jul 23 2023 at 15:00):

These generalizations tend to be explored more in the context of a monoidal category, and include structures such as [[multicategories]] and [[promonoidal categories]].

Julius (Jul 23 2023 at 15:00):

Yes exactly^, I’d love to hear more about that (and I’m writing further info right now in my above message as well). Thank you 🙏

Julius (Jul 23 2023 at 15:00):

Ah I see, Wow

Mike Shulman (Jul 23 2023 at 15:01):

In particular, regarding your message about enrichment, it's possible to enrich a category in any multicategory.

Mike Shulman (Jul 23 2023 at 15:02):

Symmetry isn't required for enrichment, either. But the non-symmetric case requires a bit more care to make sure you write all the products in a consistent order, and lacks some features of the symmetric case, e.g. categories enriched over a non-symmetric monoidal category (or multicategory) don't have opposite categories or (tensor) product categories.

Julius (Jul 23 2023 at 15:02):

My attempt to put everything about enriched categories together:

What is the “point” of the preorder? Is the point to have the weakest concept of order possible? What about leaving out the reflexivity condition? Or what about enriching a category over any collection plus a relation? Is that what you mean by multi category?

Julius (Jul 23 2023 at 15:02):

(to be continued)

Mike Shulman (Jul 23 2023 at 15:03):

The point is to have something with which to replace the word "set" in the hom-sets of an ordinary category.

Mike Shulman (Jul 23 2023 at 15:03):

A monoidal category, or multicategory, abstracts the structure possessed by the category $\rm Set$ that enables you to define a category as having a collection of objects and hom sets $C(x,y) \in \rm Set$.

Julius (Jul 23 2023 at 15:12):

I see. So because hom sets can be composed - for every f:a -> b, g:b -> c, there exists f;g: a->c - they imply a partial ordering on the arrows/morphisms. Therefore, simply relax the condition of partial ordering - in which a \leq b and b \leq a implies a = b - and you have a preorder. Is that it?

1. What useful properties open up when you relax that condition?
2. If we think of the composition of arrows as implying a kind of binary relation on the collection of all arrows in a category… then the above partial order condition I wrote.. what is it saying? I’m trying to understand if it says something about inverses, equivalence, or isomorphism, perhaps?

I believe the point was made that a preorder and a graph are I think “adjoint” to each other in that in a preorder you can have multiple parallel “relation” elements between two objects a and b, but in a graph, they would be viewed as one single edge, or something. (Gotta work through & refresh my recollection of this section now.)

(My questions may be repetitive because I am circling around the same thing from different angles, trying to tie it all together. Thanks for your help, it’s really helpful to me.)

Mike Shulman (Jul 23 2023 at 15:14):

No, that's not it. The hom sets are getting replaced by objects of the monoidal category. So instead of a set $C(x,y)$ whose elements are morphisms in $C$, you have an object $C(x,y) \in V$, which doesn't in general even have "elements".

Mike Shulman (Jul 23 2023 at 15:15):

The monoidal and category structure on the enriching category $V$ (not on the morphisms of the enriched category) is necessary to generalize composition of morphisms, which is expressed in terms of the hom-sets as a function $C(y,z) \times C(x,y) \to C(x,z)$. If now each $C(x,y)$ is an object of $V$ instead of a set, then you need some structure on $V$ to mean by $\times$ and $\to$. The former is the monoidal structure, the latter is the category (or preorder) structure.

Mike Shulman (Jul 23 2023 at 15:17):

I don't know how Spivak and Fong approach it, but the usual intuition for enriched category theory comes from categories whose hom-sets are structured sets. For instance, in many categories it is possible to "add" two parallel arrows, e.g. in the category $\rm Vect$ of vector spaces you can add two linear transformations $f,g:U\to W$ pointwise to get another linear transformation $(f+g)(u) = f(u) + g(u)$. Such a category is then enriched over the monoidal category $\rm Ab$ of abelian groups, so that each hom-set ${\rm Vect}(U,W)$ is actually a hom-abelian-group.

Mike Shulman (Jul 23 2023 at 15:18):

In such cases, the hom-objects do have "elements", but also extra structure. But then once you write down the definition abstractly, you can let the enriching category be any monoidal category, not just one composed of structured sets.

John Baez (Jul 23 2023 at 15:45):

Julius said:

A preorder is a binary relation that is reflexive and transitive. Right?

That's one definition, but actually in the book you're reading, Seven Sketches, a preorder is not a reflexive transitive binary relation but rather an ordered pair consisting of a set together with a reflexive binary relation on that set. See Definition 1.30, where they first define a 'preorder relation' and then say a preorder is a set equipped with a preorder relation. That's why they say things like

Given a preorder (P, ≤)

in Example 1.54.

But does it have to be conceptually viewed as a kind of “order”?

I don't think in math you ever have to view anything in some particular way. In this subject I believe people first invented "orders" and then realized that "partial orders" were a useful generalization and then realized that "preorders" were another important and even more general generalization. All three concepts are important so we need some name for them all, and it makes sense to have names that indicate that we're successively generalizing the original concept.

But often in math the names don't mean much. For example, [[rings]] are very important, and they're called that because some of the first examples literally looked like rings, but most people don't even know that anymore, and nobody thinks rings need to look ring-shaped.

For example, why not just call it a “reflexive transitive binary relation”?

When I'm talking about preorders a lot, I'd rather say something short like "preorder" rather than "set equipped with a reflexive transitive binary relation". But if you want to say "set equipped with a reflexive transitive binary relation" I don't think anyone will complain too much.

John Baez (Jul 23 2023 at 15:53):

Julius said:

My attempt to put everything about enriched categories together:

What is the “point” of the preorder? Is the point to have the weakest concept of order possible? What about leaving out the reflexivity condition?

In general there are lots of "points" of the concept of preorder; I guess you're using them in enriched category theory, but it's good to know that a preorder is the same as a category that has at most one morphism from any object $x$ to any other object $y$.

Thus, a preorder is a kind of category where any equation between morphisms that could possibly make sense is automatically true! Since a lot of category theory involves checking equations between morphisms, this makes preorders quite interesting.

Mike Shulman (Jul 23 2023 at 16:07):

John Baez said:

For example, [[rings]] are very important, and they're called that because some of the first examples literally looked like rings, but most people don't even know that anymore...

I didn't know that! What were those examples?

John Baez (Jul 23 2023 at 16:15):

The rings $\mathbb{Z}/n$.

John Baez (Jul 23 2023 at 16:20):

Hmm, that's what I read somewhere, but now I'm questioning it.

John Baez (Jul 23 2023 at 16:22):

Wikipedia presents two alternative theories, and it seems that the German word "Zahlring" (number ring) appeared before the word "ring".

John Baez (Jul 23 2023 at 16:24):

So, I'll have to back off and simply say that lots of mathematical terms have mysterious origins and we use them mainly because we need words for things, not because these terms guide our thinking!

Julius (Jul 24 2023 at 03:45):

Ok, thanks very much, both of you.

I’ll come back with some more questions soon.

Thanks a lot!

Julius (Jul 24 2023 at 05:15):

Here are some basic questions to check if I actually understand what I’m reading.

Spivak and Fong, Ch. 2, pg. 40, says that wiring diagrams were invented by Joyal and Street in the context of monoidal categories. Why were wiring diagrams invented for monoidal categories and not earlier? I mean, is there a pictorial property of wiring diagrams that is intrinsically linked to monoidal categories, but not categories more generally?

Julius (Jul 24 2023 at 05:26):

Can the difference between a monoidal preorder and a monoidal category be expressed in a succinct sentence, a change in one condition? Is it that the preorder relation is replaced by existence of hom-sets, which act like a partial order because the composition of morphisms is like the transitivity of the preorder relation, and the identity property of the hom sets is like the reflexivity of the preorder?

Sorry to repeat the question, in case I missed the answer, but what is the corresponding notion in a category of a \leq b and b \leq a implying a = b, for an order relation? Equivalence up to isomorphism? Like, if two objects have the same hom set but the arrows are in the opposite direction, we regard them as one object?

Sorry if I’m completely butchering this!

But also: a preorder assigns only one element (the ordered pair) to some pair of objects a, b. But the corresponding notion (I think), a hom-set, assigns a whole set of arrows for a pair of objects. Right?

But a monoidal preorder is fundamentally equivalent to a multi category, in which you can have multiple arrows between the same objects. Right?

Is the point here that in a category, we do have a whole set of arrows between two objects, but when we draw it, we just draw one arrow, for exactly the reason that in a category our view collapses the distinction between parallel arrows?

But what if the actual category were working in has multiple valid arrows between two objects? Like the category of sets. There are many functions between two sets S1 and S2. Is part of the benefit of seeing sets as a category that we no longer are thinking about the distinction between individual functions, only seeing higher level patterns, structures, etc?

Thank you

Jean-Baptiste Vienney (Jul 24 2023 at 05:37):

Julius said:

Here are some basic questions to check if I actually understand what I’m reading.

Spivak and Fong, Ch. 2, pg. 40, says that wiring diagrams were invented by Joyal and Street in the context of monoidal categories. Why were wiring diagrams invented for monoidal categories and not earlier? I mean, is there a pictorial property of wiring diagrams that is intrinsically linked to monoidal categories, but not categories more generally?

Yes, these wiring diagrams are intrinsically linked to monoidal categories which are categories where you can compose morphisms sequentially like in any category, ie. from $f:A \rightarrow B$ and $g:B \rightarrow C$, you can get $f;g:A \rightarrow C$ but also can compose in parallel, which is a specific feature of monoidal categories -- to compose two morphisms $f:A \rightarrow B$ and $g:C \rightarrow D$ in parallel, you take their tensor product $f \otimes g: A \otimes C \rightarrow B \otimes D$.

These wiring diagrams are more usually called string diagrams. They were formalized by Joyal and Street in the early 1990s in the context of monoidal categories but date from Penrose notations introduced in the 1970s in a more mathematical physics, and not yet category-theoretic, perspective.

James Deikun (Jul 24 2023 at 12:08):

In a category we very much care about the distinction between two parallel arrows (i.e. arrows that belong to the same homset). This is what makes categories more powerful than preorders.

A monoidal preorder is not equivalent to a multicategory. A monoidal category is (basically) equivalent to a multicategory. A multicategory is not distinguished from a category by having "multiple arrows between the same objects"; a category already has that. A multicategory is distinguished by having multiple (or no) "tails" for the same arrow. An example of a multicategory is the multicategory of sets and multiple-argument functions. The monoidal category that represents this multicategory is the monoidal category of sets and functions with Cartesian product as monoidal product.

James Deikun (Jul 24 2023 at 12:13):

The notion that most directly corresponds, in category theory, to the notion of "partial order" is that of [[skeletal category]]. However, as a rule, passing to skeletal categories is only used for size arguments and instead the principle that corresponds to using partial orders is the [[principle of equivalence]].

James Deikun (Jul 24 2023 at 12:21):

There is a way of viewing both categories and preorders as special cases of each other.

Every category has an underlying preorder, where $X \leq Y$ means "there is an arrow from $X$ to $Y$". Thus a category is a preorder with extra stuff: for each inequality $X \leq Y$, a set of "reasons why".

Similarly, every preorder has an underlying category, where $\mathrm{Hom}(X,Y)$ contains a single arrow if $X \leq Y$ and is otherwise empty. Thus a preorder is a category with an extra property: all parallel arrows are equal.

John Baez (Jul 24 2023 at 14:27):

By the way, James Deikun's last sentence is a way to say precisely what I said a while ago:

Thus, a preorder is a kind of category where any equation between morphisms that could possibly make sense is automatically true!

However he's assuming you know what 'parallel arrows' are... or that you can guess from his penultimate sentence.

Mike Shulman (Jul 24 2023 at 15:07):

James Deikun said:

A monoidal category is (basically) equivalent to a multicategory.

Obviously the meaning of this sentence depends on the meaning of "basically", but it's not one that I would ordinarily regard as true.

James Deikun (Jul 24 2023 at 18:35):

Mike Shulman said:

James Deikun said:

A monoidal category is (basically) equivalent to a multicategory.

Obviously the meaning of this sentence depends on the meaning of "basically", but it's not one that I would ordinarily regard as true.

Fair. It's definitely easier to interpret in a way that makes it true than "A monoidal preorder is fundamentally equivalent to a multi category" though.

Julius (Jul 25 2023 at 15:27):

Thanks. I’ll come back to this to understand it better.
I’m now at the first step of trying to understand monotone maps, monoidal monotones, proving Bool-categories are preorders (and lawvere metric spaces are cost-categories), and lastly, “V-variations”.

Julius (Jul 25 2023 at 15:27):

Will return shortly with some definitions and/or questions. Thanks