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: Imperfect world

Soichiro Fujii (Apr 30 2020 at 12:10):

Hi, I just noticed that the following (apparently common) conventions are incompatible with each other, if one works in a sufficiently general setting.

• In a category $\mathcal{C}$, the composition operation is of type $\mathcal{C}(y,z)\times\mathcal{C}(x,y)\longrightarrow\mathcal{C}(x,z)$ (as opposed to $\mathcal{C}(x,y)\times\mathcal{C}(y,z)\longrightarrow\mathcal{C}(x,z)$).

• A profunctor $H\colon\mathcal{A}\longrightarrow\mathcal{B}$ is defined as a functor $H\colon\mathcal{B}^\mathrm{op}\times\mathcal{A}\longrightarrow\mathbf{Set}$ (as opposed to $H\colon\mathcal{A}^\mathrm{op}\times\mathcal{B}\longrightarrow\mathbf{Set}$).

The former convention may be defended on the basis of the (very common) Leibniz convention for composition. The latter can be justified because this lets us view the bicategory $\mathscr{P}rof$ of profunctors as an extension of $\mathscr{C}at$ (as well as of $\mathscr{C}at^\mathrm{coop}$), rather than an extension of $\mathscr{C}at^\mathrm{op}$ or $\mathscr{C}at^\mathrm{co}$.

However, if one works in the enriched setting where the base monoidal category is not symmetric (or even where the base is a bicategory), then unfortunately the above conventions are incompatible. More precisely, one cannot view the representable presheaf $\mathcal{C}(-,x)$ as a profunctor (between $\mathcal{C}$ and the unit category $\mathcal{I}$). (In this general setting, one defines profunctor as a family of objects in the base monoidal category equipped with a suitable two-sided action; see e.g., Section 3 of Enriched categories and cohomology by Street.)

So how do you deal with this difficult situation?

sarahzrf (Apr 30 2020 at 14:32):

personally i deal with it poorly

sarahzrf (Apr 30 2020 at 14:32):

(sorry)

Fabrizio Genovese (Apr 30 2020 at 14:57):

I define the first thing as you do when you say "as opposed to". I never use the $\circ$ to denote composition, but always the $;$. This is because I mainly work with diagrams so writing $f;g$ to stand for $X \xrightarrow{f} Y \xrightarrow{g} Z$ is more intuitive for me. :slight_smile:

John Baez (Apr 30 2020 at 15:22):

So how do you deal with this difficult situation?

I complain about it, try various conventions, get annoyed, and ultimately shrug my shoulders and decide to wait for civilization to collapse, hoping the next civilization adopts more consistent notation.

The ultimate problem is that we like to write $f \circ g$ to mean "do $g$ first then $g$" as if we were reading from right to left, yet we write $f \colon x \to y$, with the arrow going from left to right.

So, one solution is to consistently write from left to right. This means we should use $f ; g$ to mean "do $f$ first, then $g$. This is not too hard for people to accept until we have to apply functions to arguments; then we should say

$(x) (f; g) = ((x)f)g$

and most people find this upsetting, since they've been trained in the opposite convention (except when using calculators with reverse Polish notation). It's fun to think about how this convention would work:

$\displaystyle{ (x)\sin^2 \frac{d}{xd} = (x)\sin \, (x)\cos 2 }$

The other convention is to systematically write from right to left, which also upsets people:

$y \leftarrow x : f$

Nathaniel Virgo (Apr 30 2020 at 15:45):

John Baez said:

most people find this upsetting, since they've been trained in the opposite convention (except when using calculators with reverse Polish notation).

Or C++:

x.f().g()

I think it'd be quite nice if we wrote $x f g$ for $f;g$ applied to $x$, though I don't think I'd use that in a paper.

Sam Tenka (Apr 30 2020 at 17:10):

@Fabrizio Genovese

Could $f:Y \leftarrow X$ be less upsetting than the other possibilities? (My friends have teased me about this notation, so perhaps the answer is no.)

Here's my reasoning. There seem to be 4 possibilities (when writing in plain text on a computer):
(a) $f:Y \leftarrow X$
(b) $f:X \to Y$
(c) $Y \leftarrow X:f$
(d) $X \to Y:f$,

I often use (a). The styles (a) and (c) have the advantage that they align with conventions for function composition, matrix multiplication, and so on. The styles (a) and (b) have the advantage that they align with conventions for judgements in type theory. The styles (a) and (d) have the advantage that the target is written more closely to f. This is nice because f's type is more like the type of its target than of its source. More precisely, only one of the two hom functors is covariant! This corresponds to a common goal-oriented approach to interactive proving and to vanilla functional programming. So, for all three matchings on the tetrahedral graph, (a)'s pair wins!

Fabrizio Genovese (Apr 30 2020 at 22:28):

B is the only viable one for me.All the others have the great disadvantage to be read right to left, that in a left-to-right language is very confusing imho

Fabrizio Genovese (Apr 30 2020 at 22:29):

In any case, as long as one chooses two symbols for composition (e.g. $f;g$ and $f \circ g$ or even better $fg$) I don't see too much ambiguity in using both

Fabrizio Genovese (Apr 30 2020 at 22:30):

"Let's consider the composition $f;g: X \to Z$. Then on an element $x \in X$ we compute $gf(x)$ ..." Makes perfect sense to me

Fabrizio Genovese (Apr 30 2020 at 22:30):

So I don't really get what this fuss is about. You don't have to pick one convention and stick to it, it's not a religion. You can just be very opportunistic and use whatever you see fit whenever you see fit.

Fabrizio Genovese (Apr 30 2020 at 22:32):

And, as usual, the point is: Notation should help you writing mathematics, not the other way around. So as long as something works for you (e.g. it helps you reasoning) then go for it :slight_smile:

John Baez (Apr 30 2020 at 22:37):

((x)f)g makes a lot of sense: you start with x, you apply f to it, then you apply g. But we've all been trained to write g(f(x)) so it looks very unsettling to see ((x)f)g.

Sam Tenka (Apr 30 2020 at 23:03):

Fabrizio Genovese said:
B is the only viable one for me.All the others have the great disadvantage to be read right to left, that in a left-to-right language is very confusing imho
I think I see what you're saying.

For me, I read all of them from left to right, just the same way that I read the membership "$f \in Y^X$" or the conditional probability "Prob(coin Y | bias X)" from left to right. For example, I read (A) as:

• "f is an instance of Y that is indexed by X" or
• "f completes the proof goal Y and creates the proof goal X", or
• "f produces Y given X".

That way, halfway through reading, what's in my brain is:

• "f is an instance of Y" or
• "f completes the proof goal Y", or
• "f produces Y",
  In many categories, insofar as a map to a vector space is itself an element of different vector space (i.e. an internal hom), these aren't lies!

This preference is very personal though!

Nathanael Arkor (Apr 30 2020 at 23:08):

John Baez said:

((x)f)g makes a lot of sense: you start with x, you apply f to it, then you apply g. But we've all been trained to write g(f(x)) so it looks very unsettling to see ((x)f)g.

No time to start a culture shift like the present.

Reid Barton (Apr 30 2020 at 23:09):

You can find some old papers by Barr, I believe, if you want to see how good or bad an idea this might be.

John Baez (May 01 2020 at 00:34):

I have no desire to spend any time trying to reform the world in this way.... well, except to raise the idea that there are other ways we could write.

Soichiro Fujii (May 01 2020 at 01:17):

Thanks for the comments. Yes, the diagrammatic order convention $f;g$ makes a lot of sense, so it is unfortunate that the other convention has become so common.

But the convention to define a profunctor $H\colon \mathcal{A}\longrightarrow \mathcal{B}$ as a functor $H\colon \mathcal{B}^\mathrm{op}\times\mathcal{A}\longrightarrow \mathbf{Set}$ also involves some “reversal”, so I am not sure if the diagrammatic order convention alone solves the problem completely...

For example, even using the diagrammatic order convention throughout (but using the above convention for profunctors), the composition of the profunctors $H\colon\mathcal{A}\longrightarrow\mathcal{B}$ and $K\colon\mathcal{B}\longrightarrow \mathcal{C}$ is given by $(H;K)(c,a)=\int^{b\in\mathcal{B}}K(c,b)\times H(b,a)$, which might lead to some notational inconsistency sometime later.

Matteo Capucci (he/him) (May 02 2020 at 13:50):

I try to never write down a composition explictly exactly for this reason. The convention is cursed and alternative notation is not widespread.
My go-to alternatives are:

• words: "$f$ followed by $g$", "the composite of ...", etc
• pictures: $X \overset{f}\to Y \overset{g}\to Z$

Of course I'm not always able to do it, but I strive.

Jules Hedges (May 02 2020 at 13:59):

I'm going to stand up for just not caring. I write $fg$ in notes for myself and $g \circ f$ in papers, I think life's far too short to worry about something so tedious

John Baez (May 02 2020 at 14:02):

I write things both ways; this is not something I actually lose sleep over. Nonetheless it's interesting to me how our conventions have become locked into this problem, so I enjoy talking about it once or twice a year.

Jules Hedges (May 02 2020 at 14:03):

Matrix multiplication is backwards too, but somehow nobody cares about that

Henry Story (May 02 2020 at 14:04):

Nathaniel Virgo said:

Or C++: x.f().g()

It's fun to think that OO notation had it right all along.

"Hello World!".length

:smiling_devil:

Jules Hedges (May 02 2020 at 14:04):

If you start with a vector $v$ and then you apply a linear map $M$ and then apply a linear map $N$, the resulting vector is $NMv$

Jules Hedges (May 02 2020 at 14:05):

So if you write your categorical composition as $;$ then you have to be careful that the matrix representing the linear map $M;N$ is $NM$

Reid Barton (May 02 2020 at 14:06):

I think "nobody cares about that" because it's consistent with the other conventions that everyone uses. $(NM)v = N(Mv)$.

Reid Barton (May 02 2020 at 14:07):

It would be very bad to write it the other way!

Jules Hedges (May 02 2020 at 14:07):

It's not consistent with the way you write diagrams in the category of vector spaces $V_1 \overset{M}\longrightarrow V_2 \overset{N}\longrightarrow V_3$

John Baez (May 02 2020 at 14:08):

Lots of people get upset about this, but it's just a special case of how function composition is backward; there's nothing special about matrix multiplication here.

Reid Barton (May 02 2020 at 14:08):

Of course it is, because $gf$ is how you write the composition of functions.

John Baez (May 02 2020 at 14:09):

Jules seems to be pointing out that doing M first and then N is written MN when you do matrix multiplication, but I'm saying this annoying fact is just a fact about how we write the composition of anything.

John Baez (May 02 2020 at 14:10):

In the the theory of Markov processes they multiply vectors by matrices on the right so in Jules' example they'd write $vMN$ for a vector v in $V_1$.

John Baez (May 02 2020 at 14:11):

They want to do it this way because they think about the relation between matrix multiplication and composing paths, and most people write $\gamma_1 \gamma_2$ for moving first along a path $\gamma_1$ and then along a path $\gamma_2$.

Jules Hedges (May 02 2020 at 14:11):

That issue should come up in representation theory of quivers too, I guess?

John Baez (May 02 2020 at 14:12):

It should, yes. Right now I forget what people usually do.

John Baez (May 02 2020 at 14:13):

Anyway, I sometimes tell people if they can't deal with a problem like this they're not cut out for math.

Jules Hedges (May 02 2020 at 14:13):

If you think the order of composition is annoying, wait till you find out how many pointless meetings you have to do as an academic...

Henry Story (May 02 2020 at 14:15):

That's without counting people who write string diagrams starting from the bottom scanning left to right, and others who do it scanning right to left :-)
https://twitter.com/bblfish/status/1221425869899599873

@BartoszMilewski Best to read the article "Category Theory Using String Diagrams" last after going through Bartosz course and reading the bicategories of relations. Also annotate the diagrams in the article carefully, for it to make sense, and try writing a few equations like this https://twitter.com/bblfish/status/1221425869899599873/photo/1

- The 🐟‍‍ BabelFish (@bblfish)

John Baez (May 02 2020 at 14:15):

Right, and I'm left-handed, and people force me to write dragging my hand over the stuff I've just written.

John Baez (May 02 2020 at 14:15):

Life is cruel.

Jules Hedges (May 02 2020 at 14:16):

String diagrams are different, people who write string diagrams bottom-to-top are Objectively Wrong and possibly heretical

John Baez (May 02 2020 at 14:16):

I agree with that of course. When I become king they'll be punished.

John Baez (May 02 2020 at 14:17):

But physicists starting with Feynman always write Feynman diagram bottom-to-top since t increases up the page in $(x,t)$ coordinates.

John Baez (May 02 2020 at 14:18):

My advisor complained that physicists should use $(t,x)$ because $t$ is the independent variable.

Fabrizio Genovese (May 02 2020 at 14:19):

Jules Hedges said:

String diagrams are different, people who write string diagrams bottom-to-top are Objectively Wrong and possibly heretical

Well, considering that this is the CQM convention and CQM is what made string diagrams popular in the first place, I'd say everyone else is wrong. In any case the right standard is clearly writing left-to-right, wrt clarity and space taken in papers.

John Baez (May 02 2020 at 14:20):

James Dolan tries to do everything logically: he writes left-to-right and then top-to-bottom. So when he graphs things the first variable goes across the page and the second one goes down... I think.

Oscar Cunningham (May 02 2020 at 14:20):

Does writing string diagrams left-to-right mean that $\circ$ is left-to-right or $\otimes$?

John Baez (May 02 2020 at 14:20):

The title of this thread, "Imperfect world", is exactly right. We live in an imperfect world.

Fabrizio Genovese (May 02 2020 at 14:22):

Oscar Cunningham said:

Does writing string diagrams left-to-right mean that $\circ$ is left-to-right or $\otimes$?

$\circ$ is left to right, $\otimes$ is top to bottom. The point is that in this way "the flow" of the diagram is left-to-right

Fabrizio Genovese (May 02 2020 at 14:23):

(modulo snake equations etc, obviously)

Oscar Cunningham (May 02 2020 at 14:24):

That does seem like the nicest convention.

John Baez (May 05 2020 at 05:32):

Okay, I'll get a job in Ulan Bator and learn Mongolian.

Daniel Geisler (May 05 2020 at 06:42):

First lesson in Mongolian.

Fabrizio Genovese (May 05 2020 at 10:00):

I always found mongolian script one of the most beautiful around. Unfortunately I don't think I'll ever find the time to learn mongolian, too many languages to tackle already T_T

John Baez (May 05 2020 at 14:17):

Rongmin Lu said:

Oops... turns out Mongolian is written left-to-right, sorry! :sweat_smile:

Now I have to cancel my plane ticket!

James Wood (May 06 2020 at 18:33):

Jules Hedges said:

Matrix multiplication is backwards too, but somehow nobody cares about that

My solution to this, which I use with good reason in my recent paper, is to primarily work with row vectors.