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

Topic: Tripped up by composition ordering?

Shea Levy (Oct 09 2020 at 08:45):

Does anyone else regularly find themselves momentarily mixed around due to composition being written in the "wrong" order? I've been working with composition in some form or another for over 15 years now and I still on some level find myself subconsciously expecting $\circ : (A \to B) \to (B \to C) \to (A \to C)$. Anyone have any good tips for getting past this/alternate notations?

Shea Levy (Oct 09 2020 at 08:47):

Related twitter vent

@robert_hensing Application order should match composition order because of course application just is composition. But *both* should match type sig order and natural diagram order, which in turn match natural language order. This last is arbitrary (given computers), but determines the rest.

- Shea Levy (@shlevy)

Morgan Rogers (he/him) (Oct 09 2020 at 09:01):

It is widely acceptable to use semi-colon notation for composition in the other order, so $f ; g \equiv g \circ f$. Some authors use fancy fonts for that, others just use ordinary punctuation.

Morgan Rogers (he/him) (Oct 09 2020 at 09:03):

As someone who only saw left group actions in the first few years of university, and became stupidly critical of a lecturer using the opposite convention later, right-to-left comes more naturally to me, but there is no reason for me to force that arbitrary choice on others. :blush:

Chad Nester (Oct 09 2020 at 09:16):

I learned category theory in diagrammatic order, and while $fg = f;g = g \circ f$ are all fine, I still struggle a little with $gf = g \circ f$.

Fawzi Hreiki (Oct 09 2020 at 09:17):

A bunch of algebraists (mostly category theorists) tried for a while to change the convention by writing composition in diagrammatic order but it never took off. See for example any of Lawvere's papers from the 60s / 70s or Categories, Allegories by Freyd and Ščedrov.

Chad Nester (Oct 09 2020 at 09:18):

I don't understand why it never took off haha. It seems much more natural to me!

Jules Hedges (Oct 09 2020 at 09:18):

I write $fg$ in all my private notes and then translate it into $g \circ f$ for anything to be read by anyone else

Fawzi Hreiki (Oct 09 2020 at 09:19):

Well that's because you probably don't work in analysis. Consider how the Riemann zeta function would look in diagrammatic

Fawzi Hreiki (Oct 09 2020 at 09:19):

*diagrammatic order

Shea Levy (Oct 09 2020 at 09:20):

Fawzi Hreiki said:

Well that's because you probably don't work in analysis. Consider how the Riemann zeta function would look in diagrammatic

Can you expand on this? What would the issue be?

Jules Hedges (Oct 09 2020 at 09:20):

Another data point from the Haskell standard library: the standard operator for pure composition . is right to left, and the standard operator for kleisli composition >=> is left to right

Shea Levy (Oct 09 2020 at 09:20):

Reassuring to know I'm not alone in this! I guess I'll give the semicolon notation a try for now

Fawzi Hreiki (Oct 09 2020 at 09:22):

Well I imagine most analysts would find an expression such as $s\zeta = (1/n^{s})\sum_{n=1}^{\infty}$ unnatural.

Shea Levy (Oct 09 2020 at 09:25):

Fawzi Hreiki said:

Well I imagine most analysts would find an expression such as $s\zeta = (1/n^{s})\sum_{n=1}^{\infty}$ unnatural.

Ah I see. Yeah I suspect we can speculate all we want about what things could be like in a different convention but as far as I can tell no one has any good idea in general for how conventions like this can be changed once established :shrug:

Jules Hedges (Oct 09 2020 at 09:26):

This feels unnatural because English uses verb-object order

Jules Hedges (Oct 09 2020 at 09:26):

Kick the ball, zeta the s

Fawzi Hreiki (Oct 09 2020 at 09:26):

In fact, I think most analysts wouldn't think of the above explicitly as function composition at all. More generally, most people don't think of function application $f(x)$ as function composition $xf$. They view the element $x$ as of a 'different nature' to the function $f$.

Fawzi Hreiki (Oct 09 2020 at 09:26):

But yeah, purely idealistically, I agree with you.

Fawzi Hreiki (Oct 09 2020 at 09:27):

Well what we learn in basic category theory is that objects are special kinds of verbs

Fawzi Hreiki (Oct 09 2020 at 09:28):

(either identity 'verbs' if thinking of objects of the category, or 'verbs' from the terminal object if thinking of the points of objects)

Fabrizio Genovese (Oct 09 2020 at 09:41):

Shea Levy said:

Does anyone else regularly find themselves momentarily mixed around due to composition being written in the "wrong" order? I've been working with composition in some form or another for over 15 years now and I still on some level find myself subconsciously expecting $\circ : (A \to B) \to (B \to C) \to (A \to C)$. Anyone have any good tips for getting past this/alternate notations?

OMG yes. All. The. Time.

Fabrizio Genovese (Oct 09 2020 at 09:42):

I do prefer diagrammatic order but there are some circumstances where understanding things left to right is better. I find this especially true when dealing with adjunctions, e.g. when writing $Hom(FY,FY) \simeq Hom(Y, GFY)$

Fabrizio Genovese (Oct 09 2020 at 09:43):

Here $GFY$ stands for $G(F(Y))$, and using the right-to-left convention allows you to just flip letters from one side to the other. It would be a mess using diagrammatic convention. Still, 99% of the time I find diagrammatic order more natural to use. My personal strategy is to apologize in advance with whoever it is I'm talking with, since it's certain I'll make a mess.

David Michael Roberts (Oct 09 2020 at 12:15):

Sometimes number theorists write Hecke operators on the right, eg https://math.stackexchange.com/questions/1828616/how-did-hecke-come-up-with-hecke-operators

Reid Barton (Oct 09 2020 at 13:07):

For those who learned/use the diagrammatic order, do you also write $XF$ for the application of a functor $F$ to an object $X$?

Fabrizio Genovese (Oct 09 2020 at 13:20):

No, that would be heresy! xD

Fabrizio Genovese (Oct 09 2020 at 13:21):

Jokes apart, some people do if I recall correctly. From a logical point of view it makes perfect sense, but my eyes bleed when I see it

Chad Nester (Oct 09 2020 at 13:29):

I write $FX$, but I don't think this is is really a problem, since we (or at least, I) usually think of objects as a separate sort of thing instead of global sections in functor categories. For composite functors I try to do $(G \circ F)X$, although it does get a bit hairy sometimes.

Fawzi Hreiki (Oct 09 2020 at 13:39):

Except, if you want to be consistent, objects in a category $\mathscr{C}$ are just functors $1 \xrightarrow{X} \mathscr{C}$ and morphisms in $\mathscr{C}$ are functors $2 \xrightarrow{f} \mathscr{C}$, so the action of a functor $F: \mathscr{C} \rightarrow \mathscr{D}$ on objects and morphisms of $\mathscr{C}$ should also be written diagrammatically (i.e. $XF$ and $fF$) no?

Jules Hedges (Oct 09 2020 at 13:42):

I get around this by saying that elements are not the same thing as global points, they are merely isomorphic to global points. That isomorphism doesn't have to preserve your notation

Fawzi Hreiki (Oct 09 2020 at 13:44):

But you wouldn't say this in a category that wasn't $\textbf{Cat}$?

Fawzi Hreiki (Oct 09 2020 at 13:45):

As in, why treat the global points of a category different to the global points of a group, metric space, etc..

Fawzi Hreiki (Oct 09 2020 at 13:46):

Group is a bad example actually since the category is pointed, but anyway

Chad Nester (Oct 09 2020 at 13:46):

This is kind of like asking why nobody works with the single-sorted presentation of categories.

Reid Barton (Oct 09 2020 at 13:47):

It's fine not to think of the application $FX$ as $F$ composed with the functor picking out the object $X$. But regardless, there's still going to be a problem with $(GF)X = GFX = G(FX)$.

Fawzi Hreiki (Oct 09 2020 at 13:47):

Actually, I don't think it is. Once someone has internalised the definition of a category, it doesnt matter which definition you use (single sorted, two sorted, dependently sorted). On the other hand, notation is something you deal with every day

Fawzi Hreiki (Oct 09 2020 at 13:48):

(replying to Chad)

Chad Nester (Oct 09 2020 at 13:49):

I don't write $f : \square f \to f \square$ for the same reasons I write $FX$ instead of $XF$, I feel.

Fawzi Hreiki (Oct 09 2020 at 13:57):

Anyhow, my opinion on this is that many mathematicians already (falsely) find category theory strange enough - this feeling should not be promoted further by changing something as simple as function composition.

Fabrizio Genovese (Oct 09 2020 at 14:00):

This discussion is interesting, but I feel it is a bit off topic. In my opinion the most important purpose of notation is making life easier (as long as what one does notationally is not straight up wrong). So I'd motivate the $FX$ vs $XF$ thing as a matter of personal preference. It is imho pointless to say which one of the two is more correct. The point is which one of the two makes you more productive :smile:

Henry Story (Oct 09 2020 at 14:39):

In the book Institution-independent Model Theory Razvan Diaconescu uses $X F$ actually for what we usually write as $F X$ . That is a book length example to consider.

Reid Barton (Oct 09 2020 at 15:57):

These discussions are also complicated by the wide range of backgrounds and applications. In math there is a strong bias towards considering categories whose objects have some kind of elements/points/values/objects/sections/... on which morphisms act as functions, and this action is nearly universally written on the left. This forces the notation for composition of morphisms to use the standard order, otherwise you have to permute subexpressions when applying a composition. Even pure category theory itself is subject to this bias if you want to consider Cat = {categories + functors}, hence the earlier discussion about $(GF)X$.
On the other hand there is another class of categories such as relations, cobordism categories, free monoidal categories on [various things] which don't have this functional nature, and if you consider mainly examples of this kind then a priori you have no reason to prefer the standard composition order.

Simon Burton (Oct 09 2020 at 16:50):

Working with string diagrams you have four cardinal directions to choose from as your "composition order". I find it's best to be comfortable with all of these. Only the right-to-left order corresponds to the usual algebraic order. (Feynman talks about this somewhere aswell when introducing braket notation & the "Hebrew" convention.) I guess with 2d string diagrams you get the whole dihedral group of order 8 to choose from.

Simon Burton (Oct 09 2020 at 16:51):

I always annotate my string diagrams with a "time" arrow somewhere, because this is so confusing.

Nikolaj Kuntner (Oct 09 2020 at 17:15):

In programming the "right" order (in the sense that transformation goes along the same direction as we write) of course developed, as in
x.f().g()
But also only in the object oriented context where we think of f more closely tied to each x (and not only think of f as having domain X where x:X)

Shea Levy (Oct 09 2020 at 17:17):

Nikolaj Kuntner said:

In programming the "right" oder (in the sense that transformation goes along the same direction as we write) of course developed, as in
x.f().g()
But also only in the object oriented context where we think of f more closely tied to each x (and not only think of f as having domain X where x:X)

Oooh I both like this and hate it :sweat_smile:

Nikolaj Kuntner (Oct 09 2020 at 17:17):

Afaik there was also a time in history where $f(x)$ was called "the function" and now that we moved on to call the relation $f$ itself the function, we seem to have a lot conflicting texts in math and the sciences.

Nikolaj Kuntner (Oct 09 2020 at 17:20):

@Shea Levy I think it might be hard to like because nobody defines a sort of concatenation "$\circ$" on the back of objects, at least not for what I've seen and surely not in programming practice. Effectively, this would dynamically append/extend/provide/create methods on the back of already given instances. Some sort of adjoining methods that can be reached by concatenating with methods from object instances in the codomain.
Maybe there's some coalgebra perspective that makes it work, hopefully concisely.

Jules Hedges (Oct 09 2020 at 19:31):

Nikolaj Kuntner said:

Afaik there was also a time in history where $f(x)$ was called "the function" and now that we moved on to call the relation $f$ itself the function, we seem to have a lot conflicting texts in math and the sciences.

This is the inevitable result of not having $\lambda$ abstraction in your basic toolkit. If you don't have a convenient notation for $\lambda x. x^2 + 1$ then you're just going to write $x^2 + 1$ and hope for the best

Jules Hedges (Oct 09 2020 at 19:34):

That is: $\lambda$ is the "inverse operation" of function application. If $f (x) = x^2 + 1$ then $f =$ what? $f = \lambda x. x^2 + 1$

Fabrizio Genovese (Oct 10 2020 at 00:48):

Indeed, this is the kind of problem that becomes evident in computer science, becaue that's where confusing things in this way actually matters

Fabrizio Genovese (Oct 10 2020 at 00:49):

Same thing holds with compositionality: It is a principle that is only recently (and slowly) starting to be recognized by pure mathematicians. I spoke with a pure logician during my PhD in Ox and he never ever heard the word. Clearly, this becomes increadibly important in compSci, especially given that many problems are solved via a divide-et-impera strategy

John Baez (Oct 10 2020 at 01:59):

Or as we Britons say, "divide and conquer". :upside_down:

David Michael Roberts (Oct 10 2020 at 07:13):

C*-algebra people work with the single-sorted definition of groupoid all the time, and use multiplication order for composition (so, I think, not composition order).

Robert Seely (Oct 10 2020 at 15:52):

This discussion reminds me of the experience of writing a paper with authors who differed on this "which order" issue. During the writing of the paper, we used a TeX macro (something like \compose{f}{g}) with two definitions (one for each order), so when TeXing it, each could use his own preference. I cannot recall how we decided the issue for the final version for publication - I suspect we let the editor decide! This "solution" was partly inspired by the famous story concerning the "triple" vs "monad" issue, but "standard construction" was too long a phrase to use ;-) ...

Nikolaj Kuntner (Oct 10 2020 at 17:00):

At least they didn't seem to bother about the meta-level. One could have made the case that the temp solution \compose{f}{g} is already discriminating.

Robert Seely (Oct 10 2020 at 17:15):

Well, not really - there was no dispute about the idea that we were composing functions in a particular order (first f then g) - the only "issue" was how to denote the result, of course.

Nikolaj Kuntner (Oct 10 2020 at 18:37):

Okay but I mean there's a choice to be made on what \compose{}{} means during writing the file.
If the math discussed has $f\colon X\to Y$ and $g\colon Y\to Z$, so that $g\circ f$ is the well-typed expression, and we write the document together, we can use the temporary \compose{f}{g} or \compose{g}{f}for that.

Nikolaj Kuntner (Oct 10 2020 at 18:41):

There's btw. a long Wikipedia article dedicated just to the history of the function concept
https://en.wikipedia.org/wiki/History_of_the_function_concept

Eric M Downes (Mar 30 2024 at 14:03):

Somewhat belated, and I'm not the only one to have had this realization, but if you draw your arrows right-to-left, then there is no difference between composition and diagram order.
ba-ckwards

John Baez (Mar 30 2024 at 16:01):

I've done this where I'm writing about how to functorially turn spans into linear operators. Otherwise I'd have to write composition of linear operators in the order nobody uses, or else say $F(ST) = F(T) F(S)$.

Nathanael Arkor (Mar 30 2024 at 17:26):

Eric M Downes said:

Somewhat belated, and I'm not the only one to have had this realization, but if you draw your arrows right-to-left, then there is no difference between composition and diagram order.
ba-ckwards

Diagrammatic composition order is from source-to-target, not from left-to-right.

Eric M Downes (Mar 31 2024 at 19:11):

Nathanael Arkor said:

Diagrammatic composition order is from source-to-target, not from left-to-right.

I don't think we are in disagreement? I would consider $b\circ a$ to be source-to-target in the diagram I drew. Like, the source of $a$ is on the right, and the target of $b$ is on the left... what am I missing here? (I believe "composition order" was being used in this discussion for the "f after g" $f\circ g$ vs. "l-to-r arrow order" of "f and then g" $f ⨾ g$.)

If I'm making a mistake, its one Emily Reihl is also making, fwiw.
https://youtu.be/SsgEvrDFJsM?si=0FLxFm_1PJ8fyU5Z

John Baez (Mar 31 2024 at 19:24):

Arkor is noting out that "diagrammatic order" can be left-to-right, right-to-left, top-to-bottom or bottom-to-top depending on which way the arrows in the diagram point. And this is not news to you, since you noted that if you make those arrows point right to left, diagrammatic order matches the traditional order of function composition, where $(f \circ g)(x) = f(g(x))$.

Nathanael Arkor (Mar 31 2024 at 19:49):

Eric M Downes said:

Nathanael Arkor said:

Diagrammatic composition order is from source-to-target, not from left-to-right.

I don't think we are in disagreement? I would consider $b\circ a$ to be source-to-target in the diagram I drew. Like, the source of $a$ is on the right, and the target of $b$ is on the left... what am I missing here? (I believe "composition order" was being used in this discussion for the "f after g" $f\circ g$ vs. "l-to-r arrow order" of "f and then g" $f ⨾ g$.)

Ah, perhaps I misunderstood what you meant. People often use the phrase "diagrammatic order" to mean (in your example) "$a$ followed by $b$", which is not the order that it appears in the diagram, read from left-to-right, but rather follows the order of the arrows (regardless of which direction they point). But that's not what you meant by "diagram order".

Eric M Downes (Mar 31 2024 at 20:32):

Gotcha. Yeah, so we need a new relative term. Kind of like "left / right" vs "north / south"