From: Vaughan Pratt <pratt@cs.stanford.edu>
To: categories@mta.ca
Subject: Small semirings
Date: Thu, 04 Jan 2007 13:26:36 -0800 [thread overview]
Message-ID: <48672.1482397572$1241019383@news.gmane.org> (raw)
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
next reply other threads:[~2007-01-04 21:26 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
2007-01-04 21:26 Vaughan Pratt [this message]
-- strict thread matches above, loose matches on Subject: below --
2007-01-05 0:25 Josh Nichols-Barrer
2007-01-04 16:52 Marco Grandis
2007-01-03 22:09 Andrej Bauer
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='48672.1482397572$1241019383@news.gmane.org' \
--to=pratt@cs.stanford.edu \
--cc=categories@mta.ca \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).