Halbring (algebraische Struktur)

Halbring

berührt die Spezialgebiete

* Mathematik
* Abstrakte Algebra
* Gruppentheorie
* Zahlentheorie

ist Spezialfall von

* Links-Halbring

umfasst als Spezialfälle

* Boolesche Algebra
* Dioid (m. E., siehe links)
* Halbkörper
* ( {\displaystyle (} natürliche Zahlen , + , ⋅ ) {\displaystyle ,+,\cdot )}
* Ring

Ein Halbring ist in der Mathematik die Verallgemeinerung der algebraischen Struktur eines Ringes, in der die Addition nicht mehr eine kommutative Gruppe, sondern nur noch eine kommutative Halbgruppe sein muss.

Halbringe werden ebenso mit nicht-kommutativer Addition sowie mit (absorbierender)  0 {\displaystyle 0} und/oder  1 {\displaystyle 1} definiert, die Definitionen in der Literatur sind nicht einheitlich.

## Inhaltsverzeichnis

* 1 Definitionen
* 1.1 Halbring
* 1.2 Nullelement
* 1.3 Einselement
* 1.4 Dioid
* 2 Beispiele
* 3 Literatur
* 4 Anmerkungen und Einzelnachweise
* 5 Weblinks

## Definitionen

[Bearbeiten | Quelltext bearbeiten]

### Halbring

[Bearbeiten | Quelltext bearbeiten]

Ein Halbring (engl.: Semiring) ist eine algebraische Struktur ( H , + , ⋅ ) {\displaystyle (H,+,\cdot )} mit einer (nichtleeren) Menge H {\displaystyle H} und mit zwei zweistelligen Verknüpfungen + : H × H -> H {\displaystyle +\colon H\times H\to H} (Addition) und  ⋅ : H × H -> H {\displaystyle \cdot \colon H\times H\to H} (Multiplikation), für die gilt:

1. ( H , + ) {\displaystyle (H,+)} ist eine kommutative Halbgruppe.
2. ( H , ⋅ ) {\displaystyle (H,\cdot )} ist eine Halbgruppe.
3. Es gelten die Distributivgesetze, d. h. für alle  a , b , c ∈ H {\displaystyle a,b,c\in H} gilt

( a + b ) ⋅ c = a ⋅ c + b ⋅ c {\displaystyle (a+b)\cdot c=a\cdot c+b\cdot c} sowie  c ⋅ ( a + b ) = c ⋅ a + c ⋅ b . {\displaystyle c\cdot (a+b)=c\cdot a+c\cdot b.} [1]

Ist auch  ( H , ⋅ ) {\displaystyle (H,\cdot )} kommutativ, so spricht man von einem kommutativen Halbring.

### Nullelement

[Bearbeiten | Quelltext bearbeiten]

Besitzt ein Halbring  ( H , + , ⋅ ) {\displaystyle (H,+,\cdot )} ein neutrales Element 0 ∈ H {\displaystyle 0\in H} bezüglich der Addition, d. h.

0 + a = a + 0 = a {\displaystyle 0+a=a+0=a} für alle  a ∈ H , {\displaystyle a\in H,}

so nennt man dieses das Nullelement oder kurz die Null des Halbringes.

Die Null  0 {\displaystyle 0} eines Halbringes heißt absorbierend (bezüglich der Multiplikation), falls

0 ⋅ a = a ⋅ 0 = 0 {\displaystyle 0\cdot a=a\cdot 0=0} für alle  a ∈ H . {\displaystyle a\in H.}

Ein Halbring  ( H , + , 0 , ⋅ ) {\displaystyle (H,+,0,\cdot )} mit einer absorbierenden Null heißt auch Hemiring.[2]

### Einselement

[Bearbeiten | Quelltext bearbeiten]

Wenn ein Halbring ein neutrales Element 1 ∈ H {\displaystyle 1\in H} bezüglich der Multiplikation enthält, also

1 ⋅ a = a ⋅ 1 = a {\displaystyle 1\cdot a=a\cdot 1=a} für alle  a ∈ H , {\displaystyle a\in H,}

dann nennt man dieses das Einselement oder kurz die Eins des Halbringes.

Ein Hemiring  ( H , + , 0 , ⋅ , 1 ) {\displaystyle (H,+,0,\cdot ,1)} mit einer Eins  1 ≠ 0 {\displaystyle 1\neq 0} heißt auch Bewertungshalbring.[3]

### Dioid

[Bearbeiten | Quelltext bearbeiten]

Ein Hemiring  ( D , + , 0 , ⋅ , 1 ) {\displaystyle (D,+,0,\cdot ,1)} mit Eins und idempotenter Addition wird als Dioid bezeichnet, d. h. bei einem Dioid sind  ( D , + , 0 ) {\displaystyle (D,+,0)} und  ( D , ⋅ , 1 ) {\displaystyle (D,\cdot ,1)} u. a. Monoide.

## Beispiele

[Bearbeiten | Quelltext bearbeiten]

* ( N , + , 0 , ⋅ , 1 ) {\displaystyle (\mathbb {N} ,+,0,\cdot ,1)} ;
* ( Q + , + , 0 , ⋅ , 1 ) {\displaystyle (\mathbb {Q} _{+},+,0,\cdot ,1)} ist sogar ein Halbkörper.
* ( R ∪ { ∞ } , min , ∞ , + , 0 ) {\displaystyle (\mathbb {R} \cup \\{\infty \\},\operatorname {min} ,\infty ,+,0)} , die sogenannte Min-Plus-Algebra;
* Für jede Menge  X {\displaystyle X} ist die Potenzmenge  ( P ( X ) , ∪ , ∅ , ∩ , X ) {\displaystyle ({\mathcal {P}}(X),\cup ,\emptyset ,\cap ,X)} ein Halbring.
* Allgemeiner ist jede Boolesche Algebra ein Halbring.
* Ist  H {\displaystyle H} ein Halbring mit 0 und 1, so bildet die Menge aller  n × n {\displaystyle n\times n} -Matrizen mit Einträgen aus  H {\displaystyle H} zusammen mit den naheliegenden Operationen darauf für Addition und Multiplikation einen Halbring mit 0 und 1.

## Literatur

[Bearbeiten | Quelltext bearbeiten]

* François Baccelli, Guy Cohen, Geert J. Olsder, Jean-Pierre Quadrat: Synchronization and Linearity (online version). Wiley, New York 1992, ISBN 0-471-93609-X.
* Jonathan S. Golan: Semirings and their applications. Updated and expanded version of The theory of semirings, with applications to mathematics and theoretical computer science. Longman Sci. Tech., Harlow 1992 [3]. Kluwer Academic Publishers, Dordrecht 1999. ISBN 0-7923-5786-8 [4].
* Udo Hebisch, Hanns J. Weinert: Halbringe. Algebraische Theorie und Anwendungen in der Informatik. Teubner, Stuttgart 1993. ISBN 3-519-02091-2.

## Anmerkungen und Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]

1. ↑ Man sagt auch:  ⋅ {\displaystyle \cdot } distribuiert über  + {\displaystyle +} .
2. ↑ D. R. La Torre: On h-ideals and k-ideals in hemirings. Publ. Math. Debrecen 12, 219–226 (1965) [1] [2].
3. ↑ Hebisch, Weinert; S. 257

## Weblinks

[Bearbeiten | Quelltext bearbeiten]

* Fun with Semirings (PDF; 252 kB)