From mboxrd@z Thu Jan  1 00:00:00 1970
X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/3568
Path: news.gmane.org!not-for-mail
From: Vaughan Pratt <pratt@cs.stanford.edu>
Newsgroups: gmane.science.mathematics.categories
Subject: Small semirings
Date: Thu, 04 Jan 2007 13:26:36 -0800
Message-ID: <48672.1482397572$1241019383@news.gmane.org>
NNTP-Posting-Host: main.gmane.org
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-2; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: ger.gmane.org 1241019382 9291 80.91.229.2 (29 Apr 2009 15:36:22 GMT)
X-Complaints-To: usenet@ger.gmane.org
NNTP-Posting-Date: Wed, 29 Apr 2009 15:36:22 +0000 (UTC)
To: categories@mta.ca
Original-X-From: rrosebru@mta.ca Thu Jan  4 17:26:46 2007 -0400
X-Keywords: 
X-UID: 60
Original-Lines: 60
Xref: news.gmane.org gmane.science.mathematics.categories:3568
Archived-At: <http://permalink.gmane.org/gmane.science.mathematics.categories/3568>

Example (1) of section 3.2 of "Temporal Structures", MSCS 1:2 179-213 
(1991), also at http://boole.stanford.edu/pub/man.pdf, enumerates the 
commutative semirings both of whose operations are idempotent (thus 
defining two partial orders), with the additive order furthermore being 
linear.  We showed there are 2^{n-2} of these having n elements, and 
indicated where the first three (those with n = 2 or 3) have previously 
appeared in the literature.

Interestingly the linearity of the additive order implies that of the 
multiplicative order.  Once this has been shown it is an easy step to 
the following pleasant representation.

Start with an n-element chain, n>1, viewed as a string of n beads with 0 
at the bottom.  Select any nonzero element as the (multiplicative) unit, 
and then determine the multiplication by allowing the portions of the 
string on either side of the unit to dangle down, with the beads 
interleaving arbitrarily subject to 0 remaining below the rest.  One can 
then readily show that there are 2^{n-2} choices for the unit and 
multiplication.

For each n exactly one of these is a Heyting algebra (example 2 of 
Andrej's list), namely the one for which the additive top was selected 
as the unit.  (So for n = 2 or 3 only the one non-Heyting semiring will 
be at all unfamiliar.)  I would be interested to hear of appearances in 
the literature of any of the three non-Heyting such with four elements.

As a class exercise around 1989 I assigned the enumeration problem for 
various weakenings of these conditions, which I can't locate right now 
though Ken Ross, kar at cs columbia edu, might conceivably have kept a 
record.

Vaughan Pratt

Andrej Bauer wrote:
> Dear categorists,
> 
> I have no idea where to ask the following algebra question. Hoping that
> some of you are algebraists, I am asking it here.
> 
> I am looking for examples of small (finite and with few elements, say up
> to 8) commutative semirings with unit, by which I mean an algebraic
> structure which has +, *, 0 and 1, both operations are commutative and *
> distributes over +. The initial such structure are the natural numbers.
> 
> Here are the examples I know:
> 
> 1) Modular arithmetic, i.e., (Z_n, +, *, 0, 1)
> 
> 2) Distributive lattices with 0 and 1.
> 
> 3) "Cut-off" semiring, in which we compute like with natural numbers,
> but if a value exceeds a given constant N, then we cut it off at N. For
> example, if N = 7 then we would have 3 + 3 = 6, 3 + 6 = 7, 4 * 4 = 7,
> etc. Do such semirings have a name?
> 
> There must be a census of small commutative rings, or even semirings.
> Does anyone know?
> 
> Andrej