1
$\begingroup$

Let $\mathcal{S}=(S,\oplus,\otimes,0,1)$ be a commutative semiring and define functions $\nu:S\to \lbrace 0,1\rbrace$ and $\bar\nu:S\to \lbrace 0,1\rbrace$ as: $$ \text{$\nu(s)=0$ if $s=0$; and $\nu(s)=1$ otherwise} $$ and $$ \text{$\bar\nu(s)=1$ if $s=0$; and $\bar\nu(s)=0$ otherwise}. $$ Consider $\mathcal{S}$ extended with $\nu$ and $\bar\nu$, that is, $(S,\oplus,\otimes,\nu,\bar\nu,0,1)$.

I have the following questions:

  1. Are such extended semirings known and studied?

  2. Can these algebraic structures be described by identities?

Any comments are welcome!

$\endgroup$

2 Answers 2

2
$\begingroup$

I don’t know about your first question; but for the second one, the answer is no — these structures can’t be axiomatised by algebraic identities.

If they could be, then any product of such structures, with the natural induced operations, would again be one. But this is not the case: if $S$, $T$ are any such structures with $0 \neq 1$ in each of them, then the resulting operation $\nu_{S \times T}$ on their product will satisfy $\nu_{S \times T}(0_S,1_T) = (0_S,1_T)$, which is equal to neither $0_{S \times T}$ or $1_{S \times T}$. So $\nu_{S \times T}$ does not satisfy the desired defining property.

The big picture here is Birkhoff’s HSP theorem: a class of algebraic structures, over a fixed language, can be axiomatised by algebraic identities if and only if it is closed under arbitrary products and subobjects (in categorical language: under all limits), and under direct images along homorphisms.

$\endgroup$
4
$\begingroup$

Peter LeFanu Lumsdaine has answered your second question. I would add that though your exact class of structures is not described by an equational theory, some related classes are, and others by Horn sentences, which are of the form: conjunction of identities implies an identity. You might be interested in quasivarieties which are defined by Horn sentences and which contain your semiring.

A discriminator term in an algebra is a term which satisfies a similar kind of behaviour: $t(x,y,z,w)$ returns $z$ if $x=y$ and returns $w$ otherwise. Varieties which have algebras with such a term are called discriminator varieties. I believe your semiring generates a discriminator variety, and that the literature you seek may be one or at most two citation links away from the literature on discriminator varieties.

Gerhard "Ask Me About System Design" Paseman, 2011.07.29

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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