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: deprecated: monoids

Topic: Tropical Fun

James Wood (Apr 04 2020 at 10:30):

Morgan Rogers said:

James Wood said:

I think some good motivating examples of semirings are the tropical semirings, where the addition is a meet and the multiplication is an addition.

So you can construct a tropical semiring from any ordered monoid? If so, I hadn't thought about that before!

I'm not sure where you get distributivity from, but it's believable that any semilattice which is compatibly a monoid forms a semiring. I'll have to check it.

James Wood (Apr 04 2020 at 10:37):

Having thought about it, no, I don't think it's possible to get distributivity from anywhere other than just requiring it.

James Wood (Apr 04 2020 at 10:39):

There's no way to get ⊤ + x ≥ ⊤, for example. It could be that all sums are smaller than ⊤, or something.

James Wood (Apr 04 2020 at 10:39):

General monoids and semilattices can get pretty wild, I suppose.

Morgan Rogers (he/him) (Apr 04 2020 at 11:19):

James Wood said:

I'm not sure where you get distributivity from, but it's believable that any semilattice which is compatibly a monoid forms a semiring. I'll have to check it.

Isn't distributivity that $a + (x \wedge y) = (a + x) \wedge (a + y)$? To be an ordered monoid, you want the addition to be order-preserving (on each side, for non-commutativity), so if $b \leq x$ we have $a+b \leq a+x$ and similarly for $y$, so distributivity holds by the universal property of meets :+1: .

James Wood (Apr 04 2020 at 11:22):

By “distributivity”, I also mean annihilation, which I'm not quite seeing (as I said above).

James Wood (Apr 04 2020 at 11:25):

Also, how do you get (a + x) ∧ (a + y) ≤ a + (x ∧ y)? It's not immediately obvious to me.

James Wood (Apr 04 2020 at 11:26):

(this is also the binary version of what I was stumped on before)

Morgan Rogers (he/him) (Apr 04 2020 at 11:32):

Ah good point, I've only proved the other inequality. Oops!

Morgan Rogers (he/him) (Apr 04 2020 at 11:35):

So you could construct a pathological counterexample as soon as the monoid isn't totally ordered :smiley:

Morgan Rogers (he/him) (Apr 04 2020 at 11:45):

Imagine a Y constructed as follows: Take three copies of $R_+ \cup \infty$, pointing upwards, and glue the zeros of two of them together strictly above the infinity of the third. I think one could come up with an addition on that which preserves the order but violates the other inequality? (just being lazy here by not coming up with it myself...)

James Wood (Apr 04 2020 at 12:07):

Even ℤ/2 might be a counterexample, now I think of it.

James Wood (Apr 04 2020 at 12:10):

Yeah. Take {0≤1}, with 1 + 1 = 0. Then 1 + (1 ∧ 0) = 1 + 1 = 0, but (1 + 1) ∧ (1 + 0) = 0 ∧ 1 = 1.

James Wood (Apr 04 2020 at 12:10):

Wait, no, that's not monotonic, sorry.

Morgan Rogers (he/him) (Apr 04 2020 at 12:12):

James Wood said:

Wait, no, that's not monotonic, sorry.

If it's totally ordered then $x \wedge y$ is just $x$ or $y$ and since addition is required to be monotonic you get the reverse inequality for free

James Wood (Apr 04 2020 at 12:13):

Aah, yeah, that makes sense.

James Wood (Apr 04 2020 at 12:13):

And that makes up an interesting result.

James Wood (Apr 04 2020 at 12:15):

Though, do we need something more to get a + ⊤ = ⊤?

Morgan Rogers (he/him) (Apr 04 2020 at 12:20):

I still don't see where that axiom comes from haha

Morgan Rogers (he/him) (Apr 04 2020 at 12:21):

(ie why you expect/want it to hold)

James Wood (Apr 04 2020 at 12:21):

This is a × 0 = 0.

Morgan Rogers (he/him) (Apr 04 2020 at 12:26):

Right, but I would take that as a theorem in ring theory, not one of the axioms, and I can't see a way that I would prove it there without additive inverses

Morgan Rogers (he/him) (Apr 04 2020 at 12:27):

(not that I've looked very hard, mind you)

James Wood (Apr 04 2020 at 12:27):

I think it's only not one of the axioms of a ring because it happens to be a theorem of the others. But what you really want to say is that “a × any finite sum is a finite sum of a × each element”.

James Wood (Apr 04 2020 at 12:28):

Related nLab concept: https://ncatlab.org/nlab/show/biased+definition

James Wood (Apr 04 2020 at 12:29):

This is one of the classic “peeling away inverses” moves.

Morgan Rogers (he/him) (Apr 04 2020 at 12:56):

Consider the three element commutative monoid $\bot < x < \top$ with $\bot + x = x = \top +x$. It's trivially monotone and totally ordered but fails to have the property you're asking for, so the answer is no. :oh_no:

James Wood (Apr 04 2020 at 13:06):

Does this counterexample even need the ⊥?

Morgan Rogers (he/him) (Apr 04 2020 at 13:09):

I guess not, thinking about it. In fact, one can always just take addition and meet to coincide, since meet is idempotent and commutative, in order to demonstrate a counterexample!

James Wood (Apr 04 2020 at 13:10):

It reminds me of some conditions I've thought of requiring before: “everything bigger than 0 is itself 0” and “everything bigger than a sum is itself a sum of bigger summands”.

James Wood (Apr 04 2020 at 13:12):

∀x. 0 ≤ x → 0 = x
∀x y z. x + y ≤ z → ∃x′ y′. x ≤ x′ & y ≤ y′ & x′ + y′ = z

Morgan Rogers (he/him) (Apr 04 2020 at 13:25):

This rekindles my curiosity about what internal monoids in a localic topos can look like.