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: commutative rigs, distributive lattices, etc

Mike Shulman (Dec 16 2024 at 19:17):

John Baez said:

Yes, that's fun. I believe a distributive lattice is the same as a commutative rig where x + x = x and x $\times$ x = x for all x.

That's cool, I don't think I knew that either. I knew that a semilattice is the same as an idempotent abelian monoid, where you define $x\le y$ to mean $xy=x$ (if it's to be a meet-semilattice) or $xy=y$ (if it's to be a join-semilattice). So a "bi-idempotent" commutative rig gives you two semilattice structures, where we can interpret one to be the meet and one the join, and of course you want one to distribute over the other. But we also need the two order relations to coincide. Why is it the case in a bi-idempotent commutative rig that $xy=x$ if and only if $x+y=y$?

John Baez (Dec 16 2024 at 21:11):

Umm, I don't know. (I said I believed my claim, not that knew it. I was just boldly extrapolating from the case of semilattices.)

I'm fiddling around trying to get one of those identities from the other using the idempotence and other laws we have. Multiplying $x + y = y$ by $y$ we get $xy + y = y$... and subtracting these two equations we get $xy = y$... but of course we're not allowed to subtract them.

Peva Blanchard (Dec 16 2024 at 21:17):

I'm fiddling too, this looks fun.

$$\begin{align*} (x + y)^2 &= x + y \\ x^2 + yx + xy + y^2 &= x + y \\ x + xy + y &= x + y \end{align*}$$

If we are allowed to cancel the $x$ on both sides, then, if $xy = x$ we obtain $x + y = y$.

On the other hand, if $x + y = y$ then

$$\begin{align*} xy + y &= y \\ xy + y &= x + y \\ \end{align*}$$

And, again, if we can cancel the $y$, we obtain $xy = x$.

I don't know if cancellability is a consequence of the definition of bi-idempotent commutative rig.

John Baez (Dec 16 2024 at 21:22):

No, $x + x = x$ is almost the opposite of cancellability, since taken together they imply $x = 0$.

Peva Blanchard (Dec 16 2024 at 21:22):

Ah yes of course

John Baez (Dec 16 2024 at 21:22):

So we seem to be getting the bidirectional implication Mike was asking about up to some cancellation that we can't do.

Aaron David Fairbanks (Dec 16 2024 at 21:23):

I think we need the additional law that $1 + x = 1$.

John Baez (Dec 16 2024 at 21:24):

Good point. I forgot to mention out loud the by-now-evident question: can we give a purely equational definition of a distributive lattice (as we can for semilattice), and what are some equations that will suffice?

Aaron David Fairbanks (Dec 16 2024 at 21:26):

Then $xy = x$ implies $x + y = xy + y = (x + 1)y = 1y = y$. Similarly, $x + y = y$ implies $xy = x(x+y) = x +xy = x(1+y) = x1 = x$.

Peva Blanchard (Dec 16 2024 at 21:35):

So additional required law seems to be $1 + x = 1$. Given the symmetry of the situation, I wonder if $0 \cdot x = 0$ would be enough too.

Aaron David Fairbanks (Dec 16 2024 at 21:37):

That one we are already assuming in the rig structure.

Peva Blanchard (Dec 16 2024 at 21:38):

Oh I see, I didn't know thanks.

Peva Blanchard (Dec 16 2024 at 21:41):

So, if I understand correctly, what makes the two partial orders coincide is really that, in addition to $0$ being "$\times$-abosrbant", $1$ is also "$+$-absorbant".

John Baez (Dec 16 2024 at 21:46):

Peva Blanchard said:

So additional required law seems to be $1 + x = 1$. Given the symmetry of the situation, I wonder if $0 \cdot x = 0$ would be enough too.

I think the problem is that the situation is not really symmetrical. We know $0 \cdot x = 0$ in any rig, which is good, but $+$ doesn't necessarily distribute over $\cdot$, so we can't repeat Aaron's argument with $+$ and $\cdot$ switched.

Rémy Tuyéras (Dec 16 2024 at 21:56):

Not sure if this clarifies the discussion, but I think the point of the argument is to have some sort of "maximal intersection" between the two pre-orders. Specifically:

Let $\Omega = \{y~|~\forall x:\,xy = x,\,x+y = y\}$ and assume $\omega \in \Omega$.

Then, copying @Aaron David Fairbanks's proof, we have:

1) $xy = x$ implies $x+y = xy + y = xy+\omega y = (x+\omega) y = \omega y = y$

2) $x+y = y$ implies $xy = x(x+y) = x+xy = x \omega + xy = x(\omega+y) = x \omega = x$

Peva Blanchard (Dec 16 2024 at 22:12):

John Baez said:

$+$ doesn't necessarily distribute over $\cdot$

I'm just realizing I was completely confused about the kind of objects we were dealing with: I thought we had two idempotent abelian monoids, with distributivity both ways. I was thinking too much as if we were in a Boolean algebra.

Thanks for highlighting the source of confusion!

Notification Bot (Dec 16 2024 at 22:37):

18 messages were moved here from #learning: questions > "probabilistic" algebraic geometry? by Madeleine Birchfield.

Mike Shulman (Dec 16 2024 at 23:12):

This is really interesting! Can we find an example of a rig in which both operations are idempotent but where 1 is not absorbing for addition?

Peva Blanchard (Dec 16 2024 at 23:35):

(It is a bit late here, so I'll be mostly waving hands.)

So we want a rig which contains some element $x$ such that $1 + x \ne x$.

Maybe we can start with the boolean rig $B = \{0,1\}$ with $+$ being the disjunction, and $\cdot$ being conjunction, and freely add an element $x$ to it. It feels like a "polynomial rig" $B[x]$.

(I'll try to formalize it)

Aaron David Fairbanks (Dec 16 2024 at 23:36):

I didn't check everything, but I think $\{0, 1, x, 1 + x\}$ is an example (and is the free such rig on an element $x$).

Aaron David Fairbanks (Dec 16 2024 at 23:38):

Ah, you had the same idea.

Peva Blanchard (Dec 16 2024 at 23:40):

I'm happy then, because rigs are relatively new to me, and I keep making mistakes. (which is probably not a good sign for you if you and I have the same idea).

Mike Shulman (Dec 16 2024 at 23:44):

Interesting! It looks like in this rig, the semilattice induced by multiplication is the total order $0\le x \le 1+x \le 1$, while the semilattice induced by addition is a diamond with $0 \le \{ 1, x \} \le 1+x$.

Madeleine Birchfield (Dec 17 2024 at 00:13):

Are there any commutative rigs where $1 + x = 1$ for all $x$ but which

1. addition is idempotent but multiplication is not idempotent?
2. multiplication is idempotent but addition is not idempotent?
3. neither multiplication nor addition are idempotent?

Aaron David Fairbanks (Dec 17 2024 at 00:23):

I want to use a "don't be so hard on yourself" reaction on your message @Peva Blanchard.

Aaron David Fairbanks (Dec 17 2024 at 00:24):

Addition is at least idempotent because $1 + 1 = 1$.

Madeleine Birchfield (Dec 17 2024 at 00:27):

...and thus by the distributive property we have $x + x = x (1 + 1) = x (1) = x$.

David Egolf (Dec 17 2024 at 00:27):

Interesting stuff! One way to see why $x+1=1$ is so important might be as follows. If we set $x \leq y$ iff $xy=x$ (this is the ordering we get from multiplication), then in particular $x \leq 1$ for all $x$, because $1$ is the multiplicative unit. So the order we get from multiplication always has a terminal object / "largest element" given by $1$. If our two orderings are going to coincide, then we need $x \leq 1$ for all $x$ when using our ordering induced by addition too. So we need $x+1=1$ for all $x$, to ensure that $1$ will be a terminal object in the ordering induced by addition.

Madeleine Birchfield (Dec 17 2024 at 00:29):

So then all we have left is to see if there are any commutative rigs where $1 + x = 1$ for all $x$ but which multiplication is not idempotent.

Madeleine Birchfield (Dec 17 2024 at 00:39):

Personally for distributive lattices, I'd prefer the axioms that $1 + x = 1$ and addition distributes over multiplication (dual axioms to $0 x = 0$ and multiplication distributes over addition in commutative rigs), since we can then prove that multiplication is idempotent: $x x = x + (0 0) = x + 0 = x$

Aaron David Fairbanks (Dec 17 2024 at 00:48):

Madeleine Birchfield said:

So then all we have left is to see if there are any commutative rigs where $1 + x = 1$ for all $x$ but which multiplication is not idempotent.

In this case the free thing on an element $x$ looks to be $\{0, 1, x, x^2, x^3, \ldots\}$, where $x^n + x^{n+m} = x^n(1 + x^m) = x^n$. Looking at just the exponents of $x$ this appears to be the rig $\{\infty, 0, 1, 2, 3, \ldots\}$ with min and plus.

David Egolf (Dec 17 2024 at 00:51):

The tropical rig has:

• a set $\mathbb{R} \cup \infty$
• addition given by min
• multiplication given by usual addition

Do we have $1+x=1$ for all $x$ in this rig? The multiplicative unit is $0$, and addition is min, so we just need $\mathrm{min}(0,x)=0$ for all $x$. But this is not true, so this doesn't give an example of what I was hoping.

Aaron David Fairbanks (Dec 17 2024 at 00:54):

If you restrict to just the nonnegative numbers it works, though.

David Egolf (Dec 17 2024 at 01:55):

Aaron David Fairbanks said:

If you restrict to just the nonnegative numbers it works, though.

That sounds right! We still have our "multiplicative" unit $0$, and we still have $\infty$, our "additive" unit. And we should still have closure with respect to taking minima and adding.

David Egolf (Dec 17 2024 at 01:57):

Our "addition" is idempotent as $\mathrm{min}(x,x)=x$ for all $x$, but our "multiplication" is not - because the usual addition isn't. And we do have $\mathrm{min}(0,x)=0$ for all $x$.

David Egolf (Dec 17 2024 at 01:58):

So we have a found a commutative rig where $1+x=1$ for all $x$, but where the multiplication is not idempotent.

John Baez (Dec 17 2024 at 02:19):

Nice! And that's a very useful example, not "pathological".

Valery Isaev (Dec 17 2024 at 06:03):

(deleted)

Peva Blanchard (Dec 17 2024 at 11:00):

From @Rémy Tuyéras message above, there seems to be a weaker assumption that lead to the coincidence of the two partial orders. Namely that the set

$$\Omega = \{ y ~|~ \forall x ~:~ xy =x, x + y = y \}$$

is not empty.

Requiring that $1 + x = 1$ amounts to assuming that $1 \in \Omega$.

Can we have a bi-idempotent commutative rig where $\Omega \ne \emptyset$ and where the witness $\omega \in \Omega$ is not the multiplicative unit?

Rémy Tuyéras (Dec 17 2024 at 11:14):

My renark was more about the principle behind the proof, rather than having an interesting $\omega \in \Omega$, at least in a r- i -g. The reason is that if you have a unit and $\omega$, then you have $1 \cdot \omega = 1$

In fact, the condition $x \omega = x$ makes $\omega$ a unit (at least in the commutative case)

Rémy Tuyéras (Dec 17 2024 at 11:46):

However, your question, @Peva Blanchard, might suggest some possible generalization. Here is
how I would make the proof more general:

Let $\Omega(x) = \{\omega_x~|~x\omega_x = x,\,\forall y:\omega_x+y \textrm{ is neutral for mult.}\}$ and assume that for every $z$, the set $\Omega(z)$ is non-empty.

Then we have the following implications:

1) $xy = x$ implies $x+y = xy + y = xy+\omega_y y = (x+\omega_y) y = y$

2) $x+y = y$ implies $xy = x(x+y) = x+xy = x \omega_x + xy = x(\omega_x+y) = x$

Rémy Tuyéras (Dec 17 2024 at 12:26):

Considering the rig $\{0,1,x,1+x\}$, we can take:

• $\omega_{0} \in \{0,1,x,1+x\}$,
• $\omega_{x} \in \{x, 1+x\}$ and
• $\omega_{1+x} \in \{1,1+x\}$

but there is no $\omega_1$.

Rémy Tuyéras (Dec 17 2024 at 13:37):

To conclude, we can use $\Omega(x)$ to eliminate all exceptions $x$ and find the intersection between the two pre-orders. Denote the underlying set of our rig $T_0$, then we can define recursively:

$T_{n} = \{x \in T_{n-1}~|~\Omega(x) \cap T_{n-1}\neq \emptyset\}$

and if $T_n$ converges, then it should give you a subset of $T_0$ for which the two pre-orders coincide. In the example $\{0,1,x,1+x\}$, you have the intersection: $0 \leq x \leq 1+x$.

Rémy Tuyéras (Dec 17 2024 at 14:27):

Mini-Conjecture: For any (bi-idempotent) rig $T_0$, a converging construction $T_n$ is a (bi-idempotent) rig (with same addition and multiplication) for which the multiplicative unit is absorbant for the addition.

Aaron David Fairbanks (Dec 17 2024 at 18:46):

Maybe relevant: we can consider the general case of a set equipped with two idempotent commutative monoid structures $+$ and $\cdot$, such that the induced posets are opposite. In other words, a set equipped with the structure of a (bounded) join-semilattice as well as the structure of a (bounded) meet-semilattice, such that they're the same poset. In other words, a poset with finite joins and meets. In other words, a (bounded) lattice.

That link tells us the laws for this are $x+(x\cdot y) = x$ and $x\cdot (x+y)=x$ in addition to the commutative monoid laws for $+$ and $\cdot$.