Semiring

From Academic Kids

(Redirected from Idempotent semiring)

In abstract algebra, a semiring is an algebraic structure, similar to a ring, but without additive inverses. The term rig is also used occasionally—this originated as a joke, suggesting that rigs are rings without negative elements.

Contents

Definition

A semiring is a set R equipped with two binary operations + and ·, called addition and multiplication, such that:

  1. (R, +) is a commutative monoid with identity element 0:
    1. (a + b) + c = a + (b + c)
    2. 0 + a = a = a + 0 = a
    3. a + b = b + a
  2. (R, ·) is a monoid with identity element 1:
    1. (a·bc = a·(b·c)
    2. a = a·1 = a
  3. Multiplication distributes over addition:
    1. a·(b + c) = (a·b) + (a·c)
    2. (a + bc = (a·c) + (b·c)
  4. 0 annihilates R:
    1. a = a·0 = 0

Note that this last axiom is omitted from the definition of a ring as it follows automatically from the other ring axioms. Here it does not, and it is necessary to state it in the definition.

The difference between rings and semirings, then, is that addition yields only a commutative monoid, not necessarily an abelian group.

As usual, the symbol · is usually omitted from the notation; that is, a·b is just written ab. Similarly, an order of operations is accepted, according to which · is applied before +; that is, a + bc is a + (bc).

A commutative semiring is one whose multiplication is commutative. An idempotent semiring is one whose addition is idempotent: a + a = a.

N.B. There are some authors who prefer to leave out the requirement that a semiring have a 0 or 1. This makes the analogy between ring : semiring and group : semigroup work more smoothly. These authors often use rig for the concept defined here.

Examples

  • Any ring is also a semiring.
  • The simplest nontrivial example is the semiring N of natural numbers (including zero), with the ordinary addition and multiplication. Likewise, the non-negative rational numbers and the non-negative real numbers form semirings. All these semirings are commutative.
  • N[x], polynomials with natural number coefficients form a commutative semiring. In fact, this is the free commutative semiring on a single generator {x}.
  • Square n-by-n matrices with non-negative entries form a semiring under ordinary addition and multiplication of matrices.
  • R ∪ {−∞} is a commutative, idempotent semiring with max(a,b) serving as semiring addition (identity −∞) and ordinary addition (identity 0) serving as semiring multiplication.
  • The ideals of a ring form a semiring under addition and multiplication of ideals.
  • Any bounded, distributive lattice is a commutative, idempotent semiring under join and meet.
  • In particular, a Boolean algebra is a such a semiring. Note that a Boolean ring is also as semiring—indeed, a ring—but it is not idempotent under addition.
  • The set of cardinal numbers smaller than any given infinite cardinal form a semiring under cardinal addition and multiplication. (We can't form a semiring of all cardinal numbers because they do not form a set.)
  • A Kleene algebra is an idempotent semiring R with an additional unary operator * : RR called the Kleene star. Kleene algebras are important in the theory of formal languages and regular expressions.

Semiring theory

Much of the theory of rings continues to make sense when applied to arbitrary semirings. In particular, one can generalise the theory of algebras over commutative rings directly to a theory of algebras over commutative semirings. Then a ring is simply an algebra over the commutative semiring Z of integers. Some mathematicians go so far as to say that semirings are really the more fundamental concept, and specialising to rings should be seen in the same light as specialising to, say, algebras over the complex numbers.

Idempotent semirings are special to semiring theory as any ring which is idempotent under addition is trivial. One can define a partial order ≤ on an idempotent semiring by setting ab iff a + b = b (or equivalently if there exists an x such that a + x = b). It is easy to see that 0 is the least element with respect to this order: 0 ≤ a for all a. Addition and multiplication respect the ordering in the sense that ab implies acbc and cacb and (a+c) ≤ (b+c).

Further generalizations

A near-rig does not require addition to be commutative, nor does it require right-distributivity. Just as cardinal numbers form a rig, so do ordinal numbers form a near-rig.

In category theory, a 2-rig is a category with functorial operations analogous to those of a rig. That the cardinal numbers form a rig can be categorified to say that the category of sets (or more generally, any topos) is a 2-rig.

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools