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: mathematics

Topic: Are boolean rigs commutative?

Jean-Baptiste Vienney (Dec 19 2022 at 13:46):

I cross-post a question I put on the nForum here.

Define a boolean rig as a rig such that $x^{2}=x$. The question is whether such a rig is necessarily commutative. Every boolean ring is commutative. They also show in this paper: The variety of Boolean semirings that boolean rigs which verify $1+x+x=1$ are commutative. The only boolean rigs of cardinal $\le 2$ are $0$, $\mathbb{Z}/2\mathbb{Z}$ and $\mathbb{B}=\{0,1\}$ with $1+1=1$ (you can interpret this with $0=$"False", $1=$"True", $+ =$"exclusive disjunction", $*=$"conjonction" whereas in $\mathbb{Z}/2\mathbb{Z}$, $*$ must be seen as the classical disjunction).

Therefore if a noncommutative boolean rig exists, it must be of cardinal $\ge 3$, not be a ring and not verify $1+x+x=1$.

Morgan Rogers (he/him) (Dec 19 2022 at 14:45):

Seems a bit strange to call that a Boolean rig; "idempotent rig" seems more transparent to me.
Observe that the idempotent condition results in $xyxy = xxyy$; this is close enough to commutativity that one can see how it might collapse to commutativity in a bunch of special cases.
Let's try considering the free rig on two elements $x,y$, which has formal sums of words on those letters as elements, with products of these formal sums defined via distributivity. To get the free idempotent rig, we quotient by the congruence generated by $\{(s^2,s) \mid s \in \langle x,y \rangle \}$. Since this rig represents pairs of elements in arbitrary idempotent rigs (universal property of the free object), there exists a non-commutative idempotent rig if and only if this rig is not commutative, since commutativity is preserved under rig homomorphisms.

Morgan Rogers (he/him) (Dec 19 2022 at 14:46):

(I tried to check whether $(xy,yx)$ is in this congruence, but haven't succeeded; see how you get on!)

Jean-Baptiste Vienney (Dec 19 2022 at 15:23):

Thanks, very good start! I'm gonna try.

Tim Campion (Dec 19 2022 at 15:59):

I think not. Let $M$ be an idempotent monoid which is not commutative (these exist). We think of the monoid operation on $M$ as multiplication. Let $M' = M \cup \{0,\infty\}$. Extend the monoid structure on $M$ to one on $M'$ by setting $m \cdot 0 = 0\cdot m = 0 \cdot 0 = 0$ and $m \cdot \infty = \infty \cdot m = \infty \cdot \infty = \infty$ for $m \in M$, and $\infty \cdot 0 = 0 \cdot \infty = \infty$. Then define addition on $M'$ by making $0$ be the additive identity (so $x + 0 = 0 + x = x$ for all $x \in M'$), making $\infty$ an absorbing element (so $x + \infty = \infty + x = \infty$ for all $x \in M'$), and setting $m + n = \infty$ for $m,n \in M$. Then I believe that $M'$ is an idempotent semiring which is not commutative.

Morgan Rogers (he/him) (Dec 19 2022 at 16:42):

@Tim Campion not enough info there to see that the free idempotent monoid on two generators is not commutative; once again it's sufficient to check the free such monoid on two generators, which should look like $\{1,x,y,xy,yx,xyx,yxy\}$; from your link it has 7 elements, so all of these are distinct, and so we indeed have non-commutativity. :ok:🏻

Jean-Baptiste Vienney (Dec 19 2022 at 18:14):

Congrats @Tim Campion @Morgan Rogers (he/him) ! Problem solved so.

Morgan Rogers (he/him) (Dec 19 2022 at 23:33):

Incidentally, extending the reasoning means that the free idempotent rig on two generators is finite: its elements are formal sums of the elements of the free idempotent monoid, whose positive coefficients are reduced modulo 2 to $1$ or $2$, since $1 + 1 \sim 1+1+1+1$ and hence $3 \sim 9 \sim 1$ (note that we don't have $2 \sim 0$ without subtraction!)
There are some further identifications here meaning that there are far fewer than $3^7$ elements; for example, $(x+y)^2 = x + y +xy +yx \sim x+y$. I'm sure there's an algebra package that can handle a reduction to a neat explicit presentation. I wonder how many elements there are!

John Baez (Dec 20 2022 at 07:24):

Maybe I'll pose that as a puzzle on Mathstodon!

John Baez (Dec 20 2022 at 08:39):

How are you getting 3 $\sim$ 1, @Morgan Rogers (he/him)?

Morgan Rogers (he/him) (Dec 20 2022 at 09:45):

By mistake, apparently :sweat_smile:

Jean-Baptiste Vienney (Dec 20 2022 at 11:25):

Boolean rings are maybe named liked this because if you put $x \vee y := x + xy + y$, and $\neg x = x+1$, then you get a boolean algebra. But without the commutativity, it seems difficult to prove anything. We nevertheless have at least $(x \vee y) \vee z = x \vee (y \vee z)$ in an idempotent rig. As @Toby Bartels wrote on the nLab page Boolean rig, it seems difficult to prove these kind of order-theoretic/boolean properties without further assumptions.

But so, knowing everything about the free idempotent rig on two generators would be very interesting ahah.

John Baez (Dec 20 2022 at 11:31):

I edited my question on Mathstodon so it doesn't put Morgan on the spot for claiming 3 = 1.

Jean-Baptiste Vienney (Dec 20 2022 at 11:35):

The identity $a+ab+ba+b=a+b$ looks useful.

Jean-Baptiste Vienney (Dec 20 2022 at 11:41):

Jean-Baptiste Vienney said:

Boolean rings are maybe named liked this because if you put $x \vee y := x + xy + y$, and $\neg x = x+1$, then you get a boolean algebra. But without the commutativity, it seems difficult to prove anything. We nevertheless have at least $(x \vee y) \vee z = x \vee (y \vee z)$ in an idempotent rig. As Toby Bartels wrote on the nLab page Boolean rig, it seems difficult to prove these kind of order-theoretic/boolean properties without further assumptions.

But so, knowing everything about the free idempotent rig on two generators would be very interesting ahah.

Well, well, with $4=2$ I'm gonna recheck these things.

Jean-Baptiste Vienney (Dec 20 2022 at 12:01):

Wonderfull, using $4=2$, you also get, by defining $x \wedge y := \neg(\neg x \vee \neg y) = 2x+2y+xy+2$, that $(x \wedge y) \wedge z = x \wedge (y \wedge z)$.

Jean-Baptiste Vienney (Dec 20 2022 at 12:03):

I would want to know what properties of skew lattices you get.

Jean-Baptiste Vienney (Dec 20 2022 at 12:05):

Sadly, you don't even get $x \vee x = x$ or $x \wedge x = x$...

Jean-Baptiste Vienney (Dec 20 2022 at 12:51):

$4=2$, also gives $\neg\neg\neg\neg x =\neg\neg x$..., so by iterating negations, you only get $x,\neg x, \neg\neg x$ and $\neg\neg\neg x$

Morgan Rogers (he/him) (Dec 20 2022 at 14:43):

If we work out a systematic method for how big the free idempotent rig is, it would be fun to submit the first few values to the OEIS

Morgan Rogers (he/him) (Dec 20 2022 at 14:47):

For no generators we get two elements; if I haven't missed any identities then for one generator we get 13:
$\{0,a,2a,3a,1,1+a,1+2a,2,2+a,2+2a,3,3+a,3+2a\}$
and the current upper bound for two generators is over 2000.

John Baez (Dec 20 2022 at 15:18):

The free idempotent rig on 3 generators is probably infinite, because the free idempotent monoid on 3 generators is:

John Baez (Dec 20 2022 at 15:21):

https://en.m.wikipedia.org/wiki/Square-free_word

Morgan Rogers (he/him) (Dec 20 2022 at 16:01):

Aha, beware @John Baez, according to @Tim Campion 's link earlier, the free idempotent monoid on any number of generators is actually finite: it's not simply the set of squarefree words, since there can be non-trivial identities between these. Counterintuitive!

Tim Campion (Dec 20 2022 at 19:39):

Interesting -- I hadn't appreciated this before -- it seems to be a quite nontrivial claim that the free idempotent monoid $F(x,y,z)$ on 3 generators is finite. So I suppose a general element of $F(x,y,z)$ must typically have infinitely many representations as a square-free word. Whatever references that OEIS page has must have some interesting methods to study this sort of thing...

John Baez (Dec 21 2022 at 09:48):

Wow, I just assumed that taking an element of the free idempotent monoid on n letters and repeatedly using the rewrite rule

$ABBC \to ABC$

where $A,B,C$ are words would be a terminating confluent algorithm taking any element to a unique 'normal form', and that any square-free word would be one of these normal forms.

John Baez (Dec 21 2022 at 09:51):

It's definitely a terminating algorithm, and any square-free word is 'terminal' (i.e. you can't apply the algorithm anymore), so I guess my error was assuming it's confluent!

John Baez (Dec 21 2022 at 09:58):

But I'm not finding a counterexample to confluence.

John Baez (Dec 21 2022 at 10:00):

On another note, 2 people seem to have shown that the free idempotent ring on 2 generators has 284 elements, and Greg Egan seems to be getting close to agreeing with that.

John Baez (Dec 21 2022 at 10:14):

ababcbc $\to$ abcbc $\to$ abc

ababcbc $\to$ ababc $\to$ abc

Hmm, that one was confluent.

Morgan Rogers (he/him) (Dec 21 2022 at 10:44):

I'm also struggling to find non-confluent reductions! But I've only had a few tries.

Jean-Baptiste Vienney (Dec 21 2022 at 10:55):

Can you explain why this rewrite rule should be non-confluent? I think that if we take the words over an alphabet $\mathcal{A}$, if you take any word $w \in \mathcal{A}^*$, write $w$ under the unique form $w=a_{1}^{n_{1}}...a_{p}^{n_{p}}$ where $a_{1}, ..., a_{n}$ are distinct letters $\in \mathcal{A}$, $p \ge 0$ and $n_{1},...,n_{p} \ge 1$, then the only normal form $w_{0}$ such that $w \rightarrow^{*} w_{0}$ is $w_{0} = a_{1}...a_{p}$. I don't think that it is non-confluent...

Jean-Baptiste Vienney (Dec 21 2022 at 11:24):

Sorry, it's false.

Jean-Baptiste Vienney (Dec 21 2022 at 11:25):

You can't write any $w$ under this form (example: $w=xyzx$).

Jean-Baptiste Vienney (Dec 21 2022 at 11:30):

What is true is that any word $w \in \mathcal{A}^*$ can be written under a unique form $w=a_{1}^{n_{1}}...a_{p}^{n_{p}}$ where $a_{1}, ..., a_{n}$ are letters $\in \mathcal{A}$ such that $a_{i+1}\neq a_{i}$, $p \ge 0$,$n_{1},...,n_{p} \ge 1$, and then $w \rightarrow^{*}a_{1}...a_{n}$ (which is not necessarily a normal form :sad: ).

John Baez (Dec 21 2022 at 11:31):

Can you explain why this rewrite rule should be non-confluent?

Simply because if it were confluent the free idempotent monoid on 3 generators would be infinite (since there are infinitely many square-free words in 3 letters), yet we've been told it's finite.

This is an annoyingly indirect argument.

John Baez (Dec 21 2022 at 11:34):

It's possible I'm making some sort of conceptual error here....

Jean-Baptiste Vienney (Dec 21 2022 at 11:35):

There also infinitely many words in 3 letters so...

Jean-Baptiste Vienney (Dec 21 2022 at 11:36):

maybe it's simply that, I should think two minutes

Jean-Baptiste Vienney (Dec 21 2022 at 11:42):

If two words represent the same element of the free idempotent monoid on three generators iff they have the same normal form under this rewrite rule then the free idempotent monoid on three generators is infinite

Jean-Baptiste Vienney (Dec 21 2022 at 11:43):

And I think it's true that two words represent the same element of the free idempotent monoid on three generators iff they have the same normal form under this rewrite rule?

Jean-Baptiste Vienney (Dec 21 2022 at 11:44):

But we should first be sure that every word has a unique normal form maybe

Jean-Baptiste Vienney (Dec 21 2022 at 11:44):

So if this rewrite rule is confluent then it is non-confluent, I think there is something like this in the argument.

Jean-Baptiste Vienney (Dec 21 2022 at 11:54):

But I don't know either how to prove that this rewrite rule is confluent. (I tried to above, and it doesn't look easy.)

Jean-Baptiste Vienney (Dec 21 2022 at 12:05):

Honestly I don't know. One should write the argument why it is non confluent with all the details.

John Baez (Dec 21 2022 at 13:23):

I wrote a blog article about this stuff:

• Idempotent rigs and monoids.

Dylan McDermott (Dec 21 2022 at 13:28):

Here is a counterexample to confluence:
ababcbabc $\to$ ababc $\to$ abc
ababcbabc $\to$ abcbabc
abc and abcbabc denote the same element of the free idempotent monoid, but they are different square-free words.

John Baez (Dec 23 2022 at 17:59):

Nice! That's so much simpler than the example given on page 32 of the canonical reference:

• Jean Berstel and Christophe Reuteneur, Square-free words and idempotent semigroups, in Combinatorics on Words, ed. M. Lothaire, Encyclopedia of Mathematics and its Applications volume 17, Addison-Wesley Publishing Co., Reading, Massachusetts, 1983.

Graham Manuell (Dec 26 2022 at 16:54):

Btw, it's really confusing to call these idempotent rigs, since idempotent semiring has an established usage meaning that the addition is idempotent.

Morgan Rogers (he/him) (Jan 09 2023 at 15:48):

I'm writing this up this week. Any suggestions for what it should be called? It seems @Toby Bartels created the nLab page and called them Boolean rigs, but I've already said why I don't like that name (too far from anything Boole did for the association to be valid).

John Baez (Jan 09 2023 at 16:01):

I don't know a good name, if people reject both "boolean rig" and "idempotent rig". It's true there's a huge study, often called "idempotent analysis", of rigs where the addition is idempotent - like the tropical rig.

John Baez (Jan 09 2023 at 16:02):

Multiplicatively idempotent rig? Mir?

John Baez (Jan 09 2023 at 16:02):

Luckily for me, I don't care about this much.

Morgan Rogers (he/him) (Jan 09 2023 at 16:03):

If we had a compelling example besides the free ones we've discussed, it would probably help with choosing a name. Otherwise I could just call it a Bartels rig :rolling_on_the_floor_laughing:

Jean-Baptiste Vienney (Jan 09 2023 at 16:32):

First it is not new, a little Google search would show you that it is much older than the nlab page, examples:
Boolean semirings (1962)
The variety of Boolean semirings (1992)
Boolean semirings (1993)
There are also references which use "multiplicatively idempotent rig/semi-ring".
There are multiple such papers where you could find examples.

Secondly, as to the link with Boole: Boole studied logic from an algebraic point of view, with a so-called Calculus of thoughts. Boolean rigs (mainly the free maybe) can be understood as a set of propositions with $0 := False$, $1 := True$, $+$ as exclusive disjunction and $*$ as conjunction. I pointed out before that it would be interesting to understand the link with logic/lattices which will help to use the best name. This is what Toby Bartels wrote on the nlab.

Feel free to use the name that you prefer. People always speak of the same thing for dozen of years with different names before things stabilize.

Toby Bartels (Jan 09 2023 at 17:30):

While I'd be flattered to have these named after me, I only wrote down a definition and failed to prove any interesting properties, which doesn't really justify getting them named after me. Since {0,1} with 1 + 1 = 1 (and isn't this inclusive disjunction?) is a prominent example, I think that ‘Boolean’ is justified. And besides, it's already been used in the literature, albeit with ‘semiring’ rather than ‘rig’.

Morgan Rogers (he/him) (Jan 09 2023 at 17:40):

Hah it's clear I was lazy in my search. Thanks for the references @Jean-Baptiste Vienney.

If 0 is false and 1 is true then what should 2 be when it's not identified with 0? Double true? A general such rig doesn't look enough like the more constrained Boolean rings to inherit the name, and not just because of the failure of commutativity.

Jean-Baptiste Vienney (Jan 09 2023 at 17:47):

Oh sorry, I was mistaken. In the boolean ring formed from a boolean algebra by putting $x+y := (x \wedge \neg y) \vee (y \wedge \neg x)$, $+$ is the exclusive disjunction. You can also get a boolean algebra from a boolean ring, so the two notions are equivalent. But $\{0,1\}$ with $1+1=1$ is not a boolean ring but only a semi-ring with $x^{2}=x$. So, it doesn't apply and yes it is the inclusive disjunction here!

Jean-Baptiste Vienney (Jan 09 2023 at 17:52):

The semi-ring such that $x^{2}=x$ with elements $\{0,1\}$ and $1+1=0$, ie. + as an exclusive disjunction, which is a boolean ring, is $\mathbb{Z}/2\mathbb{Z}$.

Jean-Baptiste Vienney (Jan 09 2023 at 19:48):

Oh I'm super confused. Boolean algebras and boolean rings are equivalent by going from inclusive disjunction to exclusive disjunction and vice versa. Now the two are examples of commutative semi-rings such that $x^{2}=x$. And $\{0,1\}$ with $1.1=1$ is the boolean algebra associated to the boolean ring $\mathbb{Z}/2\mathbb{Z}$.

Jean-Baptiste Vienney (Jan 09 2023 at 19:52):

So, as examples which are not rings you have all the boolean algebras!!

Morgan Rogers (he/him) (Jan 24 2023 at 09:56):

Jean-Baptiste Vienney said:

Secondly, as to the link with Boole: Boole studied logic from an algebraic point of view, with a so-called Calculus of thoughts.

As someone whose favourite genre is scientific biography, I am glad I made time to read this article about Boole; thanks for sharing it. A quote from Boole that appears towards the end of the piece which might speak to people here is the following:

“We have as an elemental part of our nature the ability to observe imperfection and from that imperfection deduce the laws of Nature – deduce perfection. This ability is our capacity to ‘abstract’ and it may well be the case that a different capacity to abstract, even in the face of a universal order of things, would lead to a different perception of that order.”

Matteo Capucci (he/him) (Jan 25 2023 at 13:57):

This quote is so nice it made it to my webpage. Lovely!