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: Connection between commutativity and associativity

Jencel Panic (Nov 05 2024 at 13:40):

I found this in the notes of Edsger W. Dijkstra (a legendary computer scientist):

Let • be a binary infix operator. Depending on how we Curry, we can form two classes of unary operators from , the general elements of which are often denoted by (x•) and (•y), defined

(x•) = 〈λy: x•y〉      (•y) = 〈λx: x•y〉

We call them in this note "the derived unary operators".

To begin with we observe —with apologies for the two different usages of parentheses—

(x•z)•y = x•(z•y)

=        {definition of derived operators}

(•y).((x•).z) = (x•).((•y).z)

=        {definition of functional composition}

((•y)◦(x•)).z = ((x•)◦(•y)).z  ,

hence, that a binary operator is "associative" means that its derived unary operators commute.

Source

Seems very cool on first glance, but I think that it is not formally correct. If we take right curried operators, they do not commute, even if the binary operator does (i.e. (•y)◦(•x)).z =/= ((•x)◦(•y)).z).

Am I missing something? Is there a formal connection between commutativity and associativity?

I am reminded of the periodic table of n-categories but don't understand the progression from a monoid to a commutative monoid.

Kevin Carlson (Nov 05 2024 at 16:22):

What do you mean? Of course it's correct; Dijkstra didn't say that two right-curried operators commute but that any left-curried operator commutes with any right-curried operator.

Kevin Carlson (Nov 05 2024 at 16:24):

I'm not sure about a connection to the periodic table. I see the temptation though.

Jencel Panic (Nov 05 2024 at 16:49):

Where did he say that?
In the note that I quote he says "the derived unary operators commute".

Kevin Carlson (Nov 05 2024 at 17:04):

In the equation finishing the proof of the result he's paraphrasing in the text you quoted...

Kevin Carlson (Nov 05 2024 at 17:05):

It's true that if you read that sentence without reading the argument above you could take him to be claiming something that isn't true, but given the context and how obvious it is that right-curried operators don't commute with each other unless the operation is commutative, it's a pretty mild case of imprecision. You have to read carefully.

Alex Kreitzberg (Nov 05 2024 at 17:32):

I guess that means hom Functors commute as well? $f_* h^* = h^* f_*$, that's cute! Thanks for sharing.

Kevin Carlson (Nov 05 2024 at 17:34):

Yeah! This is part of saying that hom is a bimodule/profunctor.

Jencel Panic (Nov 06 2024 at 04:22):

@Kevin Carlson it is mild if you already know about the connection, if not, it's actually pretty confusing :) I do read carefully, hence this conversation.

Can you elaborate a bit on the profunctor part?

Kevin Carlson (Nov 06 2024 at 17:07):

The connection between…the sentence you asked about and the math right above it? Well, anyway, whatever. Clearly there’s at least one case of it being confusing and it doesn’t do any good for me to just tell you it shouldn’t have been.

Kevin Carlson (Nov 06 2024 at 17:18):

About the hom profunctor, you can write a profunctor $H:Ato B$ as a partial binary operation where you can multiply heteromorphisms on the right with matching morphisms from $B$ and vice versa for morphisms from $A$, so $f,h\mapsto f*h$ if $f:A(a,a’),h:H(a’,b)$ and $h,g\mapsto h*g$ for $g:B(b,b’)$. So we have (partial) operators of left and right multiplication by morphisms of A and B respectively, putting us almost back in the same setting from Dijkstra.

Kevin Carlson (Nov 06 2024 at 17:18):

But what if we want to talk about $f*h*g$? Is it well defined? Part of the definition of a functor $B^{\mathrm{op}}\times A\to\mathbf{Set}$ translates into saying that yes, $(f*h)*g=f*(h*g)$, so we have an associativity condition that can again be expressed as a commutativity of operators.

Kevin Carlson (Nov 06 2024 at 17:19):

In fact, Dijkstra might not have confused you had he framed his point in this setting because it’s harder to mix up the left and right operators when the actions are one-sided! But he probably didn’t know about profunctors.

Kevin Carlson (Nov 06 2024 at 17:22):

By the way, in case you’re interested in my reflections on why I was overly prickly above, the point I really wanted to make was not that you shouldn’t have been confused, which indeed would be a stupid thing for me to tell you, but that you shouldn’t have had “Dijkstra is formally incorrect” very central in your hypothesis space. It’s common for students to waste a lot of time on the hypothesis that something they read from some very excellent scientist was wrong. In 97% of cases (although there’s lots of detail in this number; just from the shape of this case I was practically certain it couldn’t be wrong, but everybody is sometimes wrong about certain kinds of things) they’re misunderstanding and it’s more productive to focus on figuring out how than to try to prove the author wrong.

Kevin Carlson (Nov 06 2024 at 17:22):

I mixed up this possibly valuable points with feelings of defensiveness toward Dijkstra, I think, which is hilarious since he certainly doesn’t need my help. Sorry about that.

John Baez (Nov 06 2024 at 17:41):

It’s common for students to waste a lot of time on the hypothesis that something they read from some very excellent scientist was wrong. In 97% of cases [...] they’re misunderstanding and it’s more productive to focus on figuring out how than to try to prove the author wrong.

That's an interesting point. I forget if I ever did tend to think math papers and books I was reading were wrong. But now - and it seems like always - when I'm trying to learn something and read something that doesn't make sense, I assume it's due to me being confused. I'm perfectly willing to blame the author for explaining things badly or using too many symbols and not enough plain English. But usually they wind up being correct - so when I'm puzzled or in a state of downright disbelief, I know that's when I'll soon be learning something.

John Baez (Nov 06 2024 at 17:43):

My priors are completely different for the many unsolicited manuscripts I get in my email. Many of these are complete junk. Luckily, complete junk is fairly easy to spot.

Kevin Carlson (Nov 06 2024 at 17:43):

Yes, I meant to emphasize that I definitely remember cases of making these kinds of assumptions personally. To be fair, in exactly one case I was right enough to get a paper out of it, but that took a while!

Alex Kreitzberg (Nov 06 2024 at 18:09):

When I read Terrance Tao's distinction between "compilation errors" vs real conceptual errors, that helped me manage my feelings around what Kevin is concerned with.

Suddenly what counted as a substantive mistake from experts in my mind went from "very occasionally" to "never." (Unless you count famous big problems, Atiyah near the end of his life comes to mind)

Kevin Carlson (Nov 06 2024 at 18:11):

Well, it’s not fully never, especially for mistakes in proofs (my paper I mentioned corrected an old substantial mistake of Alex Heller, who was an unimpeachable expert, and there are more famous stories around Daniel Biss, the Italian school, etc...) But it really is remarkably rare, especially to have ineluctable errors in statements as opposed to proofs.

Alex Kreitzberg (Nov 06 2024 at 18:16):

Sure, that's fair, Voevodsky worked on HOTT because of a mistake he made that nobody found.

What I meant by "never" was I personally haven't rooted out a real error from a pro.

Kevin Carlson (Nov 06 2024 at 18:17):

Yeah it seems like a plausible heuristic is something like you find a median of one per decade of professional math work

Kevin Carlson (Nov 06 2024 at 18:17):

Or even less? Have you uncovered serious errors in your career John?

John Baez (Nov 06 2024 at 19:07):

Alex Kreitzberg said:

Sure, that's fair, Voevodsky worked on HOTT because of a mistake he made that nobody found.

That story is a bit exaggerated. A lot of people knew his 1991 paper with Kapranov was wrong in claiming strict $\infty$-groupoids model general homotopy types. In fact James Dolan and I studied that paper and convinced ourselves this result was wrong. But other people must have done that too. Since it was a highly implausible result to begin with, I imagine many experts just disregarded it! Luckily in 1998 Carlos Simpson wrote up a proof that this result was wrong.

What Voevodsky seemed to be complaining about is that nobody pinpointed the error that he and Kapranov made. But it's not really the responsibility of the math community to find the error in a paper that claims an implausible result. The math community succeeded just fine in not accepting his claim, and it was really his job to find the mistake.

John Baez (Nov 06 2024 at 19:13):

From the sublime to the ridiculous: a lot of people claiming to prove Fermat's Last Theorem, or now the Riemann Hypothesis or Golbach's Conjecture, write manuscripts and then run around demanding that people either find the mistake or accept their argument. But no successful scientist has time to find all the mistakes in all the unwanted papers we get in our email. That's why I put this in the crackpot index:

• 10 points for offering prize money to anyone who proves and/or finds any flaws in your theory.

Mike Shulman (Nov 06 2024 at 19:14):

I wrote some of the same things here.

Alex Kreitzberg (Nov 06 2024 at 19:18):

I really appreciate the added context Baez and Shulman!

Nathanael Arkor (Nov 06 2024 at 20:30):

John Baez said:

What Voevodsky seemed to be complaining about is that nobody pinpointed the error that he and Kapranov made. But it's not really the responsibility of the math community to find the error in a paper that claims an implausible result. The math community succeeded just fine in not accepting his claim, and it was really his job to find the mistake.

For what it's worth, Amar Hadzihasanovic later exhibited a specific error in Diagrammatic sets and rewriting in weak higher categories.

Kevin Carlson (Nov 06 2024 at 20:33):

Oh, that’s very interesting lore!

Jencel Panic (Nov 07 2024 at 09:44):

Kevin Carlson said:

...you shouldn’t have had “Dijkstra is formally incorrect” very central in your hypothesis space.

But I did the exact opposite! I assumed he was correct and created this topic to understand why it seems to me that he is not.

Kevin Carlson (Nov 07 2024 at 18:28):

This is probably past the point of significance but for what it's worth, you said "but I think it is not formally correct" which didn't read to me as you assuming it was correct. I understand now that that's what you were thinking internally hough.

Alex Kreitzberg (Nov 07 2024 at 18:55):

I remember as an undergrad pointing at the blackboard saying "that's wrong" and the professor looked at me and said "no it's right" and I just said, more nervously, "no it's wrong?" And he said louder "It's right" and I replied, more nervously, again "...no it's wrong :exhausted:", and he started "NO IT'S..." looked at the board, cleaned up a borked transcription - it suddenly made sense to me - and he immediately went back to the lecture like nothing happened.

My rough takeaway from this experience is something like "asking a question about what I'm confused about, is hard when I'm confused" but I also left with the question "if my confusion is of the sort, that I have the impression that what was said is wrong, how do I communicate this without offending the other person?"

Because clearly repeating "that's not right", obviously wasn't a winning strategy here :joy:

Kevin Carlson (Nov 07 2024 at 18:56):

Oof that sounds like an extremely anxiogenic experience

Kevin Carlson (Nov 07 2024 at 18:57):

Reminds me of the famous old story where the professor says some result is trivial, and somebody asks him to flesh that out, and he mutters for a minute or two and gets so flustered that he walks out to his office to think privately for ten minutes then comes back and says "yes, I was right, it's trivial" and continues

David Egolf (Nov 07 2024 at 19:53):

I'm reminded of the joke a math professor once told my class: "Sometimes a mathematician writes one thing, says a second, means a third, and it should have been a fourth!"

Alex Kreitzberg (Nov 07 2024 at 21:09):

Fwiw, I'm open to advice from anybody here for "if my confusion is of the sort, that I have the impression that what was said is wrong, how do I communicate this without offending the other person?"

Panic's "But I think that it is not formally correct" reads to me like an honest attempt to say "reasonable, to me, interpretations of this aren't parsing, what's wrong?" If a student, for whatever reason, can't clarify their point of confusion when it looks wrong, how would you all prefer the student phrase their question about their confusion?

Kevin Carlson (Nov 07 2024 at 21:23):

One idea is to make statements about your own perceptions, rather than the truth. “I can’t see how to parse that as true, because [details] would imply [contradiction],” for instance, or just “that looks wrong to me, because [details]”…I don’t know, I think it’s hard to say much useful in terms of plain text, at least for in person interactions it’s more about being sure to interact with a sense of curiosity and openness.

David Egolf (Nov 07 2024 at 21:34):

Going through undergrad, I asked my professors a lot of somewhat tricky questions during lectures. Many of these questions arose from the sense of "Wait, isn't that wrong/incomplete?". In this context, the initial phrasing of a question I think is important, but I also found that how I responded to the professor's response was important too. I found that professors seemed to respond positively even to bluntly stated questions, as long as I thanked them for their response and thought over their response carefully before asking a followup question.

David Egolf (Nov 07 2024 at 21:37):

I think it can also be helpful to phrase questions in terms of "Why is [the particular point at hand] interesting/correct given XYZ?" as opposed to "I think what you said is wrong because of XYZ". In general, I found it good to phrase a question so that it indicated I was interested and engaged with the presentation.

David Egolf (Nov 07 2024 at 21:41):

All that being said, I still find I have to be careful about this - and in contexts more broad than just math and lectures. It can be easy to criticize and undermine, but it's much more rewarding to try and ask questions or make comments that encourage mutual learning and exploration.

Mike Shulman (Nov 07 2024 at 22:17):

I second Kevin's suggestion. I think asking "I don't understand why..." is one of the best ways to get a positive response. The phrasing presumes that the other is actually correct and the fault is with the asker, which may in fact be the case; and if it isn't, then often the responder will realize this themselves in the process of trying to explain.

Kevin Carlson (Nov 08 2024 at 00:45):

Maybe this is a good moment to recall a story in my first analysis course, where the professor had put a typo on the board and I asked about it in a somewhat sneaky way that led him to notice an implied contradiction and then have to find his own way back to the typo; I think it wasn't malicious of me but I was just being anxious and indirect, but he responded by telling me I'd end up with no friends if I kept acting like that :laughing: Could have been crushing in a certain context but it was the right response for me at the time.

Todd Trimble (Nov 08 2024 at 13:55):

Kevin, did he say that with a smile on his face?

Kevin Carlson (Nov 08 2024 at 15:32):

Yeah, he did, I remember him as rather impish and wry.

Jencel Panic (Nov 10 2024 at 17:17):

Alex Kreitzberg said:

I guess that means hom Functors commute as well? $f_* h^* = h^* f_*$, that's cute! Thanks for sharing.

I want to understand this very well, before I try to delve into what Kevin is saying (as I assume I won't be able to do that at all), so here is an attempt to prove it:

So, I guess to be able to compose two hom functors, they both would all be $Set \to Set$. So you are saying that if you have one covariant hom functor $f_*: Set \to Set$ and one contravariant one $h^*: Set \to Set$, then $f_* h^* = h^* f_*$.

Why? let's attempt to apply one combination, then the other.
Say you have a morphism $g$ in $Set$. Then, applying $f_*$ would add another morphism to $g$, which, if we call the new morphism $f'$ would become $f' g$.

Then, applying $h^*$, to the same morphism $f' g$ would make it into a $f' g h'$ ($h'$ being the new part that is added).

And if we apply $h^*$ first, then it will be the same? Am I on the right track?

Kevin Carlson (Nov 10 2024 at 17:35):

Yes! In fact the only way to even notice there’s something to prove is to add parentheses. $f_*$ should probably just compose $f$ with $g$ to get $fg$ and then $h^*$ sends they to $(fg)h$.