2
$\begingroup$

A commutative semiring-like structure is a structure $(R, {+}, {\cdot})$ where $+$ and $\cdot$ are associative and commutative, and $\cdot$ distributes over $+$.

Is there a commutative semiring-like $R$ such that we can embed the two element lattice $\{\bot, \top\}$ into $R$ so that meet and join are affine mappings? More precisely, we seek a semirig $R$ with distinct elements $F, T \in R$ such that, for some $a, b, c \in R$ we have the "truth table for disjunction" \begin{align*} a \cdot F + b \cdot F + c &= F \\ a \cdot F + b \cdot T + c &= T \\ a \cdot T + b \cdot F + c &= T \\ a \cdot T + b \cdot T + c &= T \end{align*} and there are some $d, e, f \in R$ that give us the "truth table for conjunction": \begin{align*} d \cdot F + e \cdot F + f &= F \\ d \cdot F + e \cdot T + f &= F \\ d \cdot T + e \cdot F + f &= F \\ d \cdot T + e \cdot T + f &= T ? \end{align*} A cursory search reveals that no such structure of size 2, 3, 4 or 5 exists.

Supplemental: Ludwig Maes, who originally asked me this question, observes that \begin{align*} F + F &= (d \cdot F + e \cdot T + f) + (d \cdot T + e \cdot F + f) \\ &= (d \cdot T + e \cdot T + f) + (d \cdot F + e \cdot F + f) \\ &= T + F. \end{align*} Thus, if there is such a structure, it can't have good cancellation properties, or at least $F$ and $T$ should not, or else we get $F = T$. This rules out all rings, for example.

Additional question: It turns out the original question did not assume commutativity of $\cdot$ (in which case we assume both the left and right distributivity of $\cdot$ over $+$). It would be interesting to have an answer also for the non-commutative case. Unfortunately, Keith Kearnes's beautiful use of the majorit function does not work without commutativity of $\cdot$.

$\endgroup$
  • 1
    $\begingroup$ Why give semiring a new name 'semirig' or am I missing something new? or just typo? $\endgroup$ – Henry.L May 29 '17 at 14:50
  • 1
    $\begingroup$ Doesn't a semiring have a unit for $+$? Maybe a "non-unital semiring"? I can fix the question if there is an established name for these. $\endgroup$ – Andrej Bauer May 29 '17 at 14:56
  • $\begingroup$ "unital" would refer to the multiplicative unit $\endgroup$ – YCor May 29 '17 at 15:20
  • 2
    $\begingroup$ And we know that the quotient is non-trivial? $\endgroup$ – Andrej Bauer May 29 '17 at 17:03
  • 1
    $\begingroup$ @YCor The term "rig" is actually pretty well-established: google.com/… It's certainly very commonplace in the categorical community (and "semirig" in that community means what Andrej says, although it's perhaps not quite as commonly used). $\endgroup$ – Todd Trimble May 29 '17 at 19:10
5
$\begingroup$

There is no commutative semiring with the desired properties.

To see this, suppose instead that the semiring $R$ contains a subset $\{F, T\}$ supporting affine operations $\vee, \wedge$ that are lattice operations on $\{F, T\}$. $R$ then has an affine operation $m(x,y,z) := (x\wedge y)\vee (x\wedge z)\vee (y\wedge z)$ that is a majority operation on $\{F, T\}$. Let $m(x,y,z)=A_1x+A_2y+A_3z+B$ be an affine representation for this operation. By comparing coefficients and constant terms, observe that

$$ m(m(x_{11},x_{12},x_{13}),m(x_{21},x_{22},x_{23}),m(x_{31},x_{32},x_{33}))\\ = m(m(x_{11},x_{21},x_{31}),m(x_{12},x_{22},x_{32}),m(x_{13},x_{23},x_{33})) $$

holds throughout $R$. (Specifically, the coefficient of $x_{ij}$ on either side is $A_iA_j$, while the constant term on either side is $A_1B+A_2B+A_3B+B$.)

But under the substitution $x_{11}=x_{12}=x_{22}=x_{23}=T$ and $x_{13}=x_{21}=x_{31}=x_{32}=x_{33}=F$ the left side gives $T$ while the right side gives $F$ (since $m(x,y,z)$ acts like majority on $\{F, T\}$). This is a contradiction. $\Box$


edit 6/23/17.

The question was edited to ask

Is there a noncommutative semiring $R$ such that we can embed the 2-element lattice into $R$ so that meet and join are affine mappings?

Let me explain how to convert this question to a more tractable one, and then I will answer the tractable version.


Conversion:

Part 1. An algebra $A$ is embeddable in a semiring so that its operations have affine polynomial representations iff $A$ is embeddable in a semimodule so that its operations have polynomial representations. (Here to embed $A$ means to represent $A$ as a subalgebra of a reduct of the polynomial expansion.)

[Reasoning: If $A$ is affinely embeddable in a semiring $R$, view $R$ as a semimodule over itself to get $A$ embedded in a semimodule. For the other direction, if $A$ is embedded in an $S$-semimodule $M$, can affinely embed $A$ in the matrix semiring $\left[\begin{matrix} S&M\\0&0\end{matrix}\right]$.]

Part 2. The 2-element lattice is embeddable in a semimodule iff the 2-element majority algebra is embeddable.

[Reasoning: If $\{T,F\}$ supports lattice polynomials $\vee, \wedge$, then it supports a majority polynomial $m(x,y,z) = (x\vee y)\wedge (x\vee z)\wedge (y\vee z)$. Conversely, if $\{T,F\}$ supports a majority polynomial $m(x,y,z)$, then it supports lattice polynomials $x\vee y = m(x,y,T)$ and $x\wedge y = m(x,y,F)$.]


I reformulate the edited question as:

Is there a semimodule $M$ over a noncommutative semiring $R$ such that we can embed the 2-element majority algebra into $M$ as a subalgebra of a reduct of the polynomial expansion?

Answers: (1) Yes, it is possible to embed the 2-element majority algebra into a semimodule, but (2) not into a finite semimodule.

The explanation of why it is possible to embed the 2-element majority algebra into a semimodule can be found in

Jaroslav Jezek, Terms and semiterms, Commentationes Mathematicae Universitatis Carolinae 20 (1979), 447-460.

In this paper it is shown that every algebra is embeddable in a semimodule. (Hence every algebra is affinely embeddable in a semiring.)


However, it is not possible to embed the 2-element majority algebra into a finite semimodule. (Equivalently, it is not possible to embed the 2-element lattice into a finite semiring so that its operations have affine polynomial representations.)

This can be proved by modifying my proof for the commutative case. The modification is a bit long, but I will include it here for those who want to check.

Proof (That you can't embed the 2-element majority algebra into a finite semimodule.)

Assume that $M$ is a finite semimodule over the semiring $R$, which we may assume acts faithfully on $M$. The faithfulness assumption forces $R$ to be finite as well. Assume also that the semimodule polynomial $m(x,y,z) = \alpha x + \beta y + \gamma z + d$ acts like a majority operation on the set $\{T, F\}\subseteq M$.

Call $m^{(2)}(x,y,z):= m(m(x,y,z),y,z)$ the 2nd first-variable iterate of $m$, $m^{(3)}(x,y,z):=m(m(m(x,y,z),y,z),y,z)$ the 3rd first-variable iterate of $m$, ETC. Each $m^{(k)}(x,y,z)$ is a majority polynomial on $\{T,F\}$, and has the form $\alpha^{(k)} x + \beta^{(k)} y + \gamma^{(k)} z + d^{(k)}$. I may select any one of these to be my majority polynomial as I continue the argument.

Since we are iterating in the first variable, $\alpha^{(k)} = \alpha^k$. Since $M$ is a semimodule over a finite semiring, it is possible to choose $k$ so that $\alpha^{2k}=\alpha^k$. This allows me to replace the original majority polynomial with some first variable iterate, change notation back, and henceforth assume that the majority polynomial $m(x,y,z) = \alpha x + \beta y + \gamma z + d$ was selected to satisfy $\alpha^2=\alpha$. (This is where the finiteness is used!)

Now $T=m(T,F,T)=\alpha T + (\beta F + \gamma T + d)$ is not equal to $F=m(F,F,T)=\alpha F + (\beta F + \gamma T + d)$, so necessarily $\alpha T\neq \alpha F$. Let $T' = \alpha T$ and $F' = \alpha F$. I claim that

  • there are inverse semimodule polynomial bijections $f\colon\{T, F\}\to \{T',F'\}$ and $g\colon\{T', F'\}\to \{T,F\}$,

  • these bijections allow us to conjugate $m$ to a majority polynomial $\mu (x,y,z):=f(m(g(x),g(y),g(z))$ on $\{T', F'\}$,

  • $\mu (x,y,z)$ can be further modified to a majority polynomial $\overline{\mu}(x,y,z)$ on $\{T',F'\}$ where the coefficient of $x$ commutes with the coefficients of $y$ and $z$, and finally

  • this is enough commutativity to make the proof for the commutative case work here.

    To establish the first bulleted item, let $f(x)=\alpha x$ and $g(x)=x+\beta F+\gamma T+d$. That $f\colon \{T, F\}\to \{T',F'\}$ is a bijection follows from the definitions of $T'$ and $F'$. That $g\colon\{T', F'\}\to \{T,F\}$ is the inverse follows from the majority equations for $m$.

    The second bulleted item follows from the fact that conjugation preserves the majority identities.

    For the third bulleted item, it is easy to see that the coefficient of $x$ in $\mu (x,y,z) = f(m(g(x),g(y),g(z))$ is $\alpha^2 = \alpha$. That is, $\mu (x,y,z) = \alpha x + (\textrm{some stuff})$. If it helps to write it out, we have $$ \mu(x,y,z) = \alpha x + \alpha \beta y + \alpha\gamma z + D $$ where $$ \begin{array}{rl} D &= \alpha\beta F + \alpha\gamma T + \alpha d + \alpha\beta^2 F +\alpha\beta\gamma T + \alpha\beta d\\ &+ \alpha\gamma\beta F + \alpha\gamma^2 F \alpha\gamma^2 T+\alpha\gamma d + \alpha d. \end{array} $$

    Let $\overline{\mu}(x,y,z)=x + \alpha\beta y + \alpha\gamma z + D$. That is, delete the coefficient $\alpha$ from $x$ in the polynomial expression for $\mu(x,y,z)$ (or think of it as replacing $\alpha$ with $1$). Observe that the semimodule polynomials $\mu (x,y,z)$ and $\overline{\mu}(x,y,z)$ both have the same restriction to $\{T',F'\} = \{\alpha T, \alpha F\}$, since the polynomials only differ in their $x$-coefficient, the inputs all have $\alpha$ as a prefix, and $\alpha^2 = \alpha$. For example, $$ \begin{array}{rl} \overline{\mu}(F',T',T')&= \overline{\mu}(\alpha F,\alpha T,\alpha T)\\ &=(\alpha F) + \alpha\beta (\alpha T) + \alpha\gamma (\alpha T) + D\\ &= \alpha(\alpha F) + \alpha\beta (\alpha T) + \alpha\gamma (\alpha T) + D\\ &= \mu(\alpha F,\alpha T,\alpha T)\\ &= \mu(F',T',T'). \end{array}$$

    [Stock-taking:] We started with the assumption that a $2$-element subset $\{T, F\}$ of $M$ supports a majority polynomial $m(x,y,z)$, and constructed a new instance $\{T', F'\}$ and $\overline{\mu}(x,y,z)$, but in the latter instance the coefficient of $x$ commutes with the coefficients of $y$ and $z$ (since in the latter case the coefficient of $x$ is $1$).

    Now, modifying the proof in the commutative case, we have $$ \overline{\mu} (\overline{\mu}(x_{11},x_{12},x_{13}),\overline{\mu}(x_{21},x_{22},x_{23}),\overline{\mu}(x_{31},x_{32},x_{33}))\\ = \overline{\mu} (\overline{\mu}(x_{11},x_{21},x_{31}),\overline{\mu}(x_{12},x_{22},x_{23}),\overline{\mu}(x_{13},x_{32},x_{33})). $$ But under the substitution $x_{11}=x_{12}=x_{13}=x_{23}=x_{33}=T'$ and $x_{21}=x_{22}=x_{31}=x_{32}=F'$ the left side gives $F'$ while the right side gives $T'$. $\Box$

  • $\endgroup$
    • $\begingroup$ Did you mean semiring or semirig? $\endgroup$ – Andrej Bauer May 29 '17 at 18:23
    • 2
      $\begingroup$ Whichever you want. The proof only uses plus and times. $\endgroup$ – Keith Kearnes May 29 '17 at 18:24
    • $\begingroup$ I see that you're not using any property of rings, but still, just to match the questions, you should probably say "there is no semirig with the desired properties" or (better) "there is no such structure". $\endgroup$ – Andrej Bauer May 29 '17 at 18:25

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

    Not the answer you're looking for? Browse other questions tagged or ask your own question.