Partiell geordnete Gruppoide

Unter einer partiellen Ordnung auf einer Menge S versteht man eine reflexive, antisymmetrische und transitive binäre Relation auf S, d. h. für alle a, b, c aus S müssen gelten

(1)  a a,

(2)  a b   und   b a    =>    a = b,

und

(3)  a b   und   b c    =>    a c.

Man nennt dann (S,) auch eine partiell geordnete Menge. Gilt für alle a, b aus S noch

(4)  a b   oder   b a,

so heißt die partiell geordnete Menge linear geordnet oder total geordnet. Existiert in einer partiell geordneten Menge (S,) ein Element 0 mit 0 a [ein Element 1 mit a 1] für alle a aus S, so heißt dieses kleinstes [größtes] Element von (S,) und die partiell geordnete Menge nach unten beschränkt oder initial [nach oben beschränkt oder terminal oder unital]. Man nennt dann 0 auch Nullelement bzw. 1 Einselement von (S,). Eine nach oben und unten beschränkte partiell geordnete Menge heißt beschränkt.

Unter einem partiell geordneten Gruppoid (S,*,) versteht man ein Gruppoid (S,*) mit einer partiellen Ordnung , so daß das folgende Monotoniegesetz für alle a, b, c aus S erfüllt ist:

(5)  a b   =>   a*c b*c   und   c*a c*b .

Diese Bedingung ist gleichwertig zu

(5')  a b   und   c d   =>   a*c b*d

für alle a, b, c, d aus S, denn ersichtlich ergibt sich (5) aus (5'), indem man a = b bzw. c = d setzt, und umgekehrt folgt aus (5) und der Voraussetzung von (5') zunächst a*c b*c sowie b*c b*d. Die Transitivität von zeigt dann (5').

Handelt es sich bei (S,*) sogar um eine Halbgruppe, Quasigruppe, Gruppe etc., so spricht man von einer partiell geordneten Halbgruppe, Quasigruppe, Gruppe etc. Ist im Fall einer partiell geordneten Gruppe (S,*,) die partiell geordnete Menge (S,) sogar ein Verband (S,,), so nennt man sie eine verbandsgeordnete Gruppe oder kurz l-Gruppe (von englisch: lattice = Verband).

Satz: In einem partiell geordneten Gruppoid (S,*,) gilt genau dann a*b = inf{a,b} für alle a, b aus S, wenn die drei Ungleichungen a*b a, a*b b und a a*a für alle a, b aus S erfüllt sind. Insbesondere handelt es sich bei (S,*) dann um einen Halbverband und ist gerade die natürliche partielle Ordnung auf diesem Halbverband. Die ersten beiden Ungleichungen sind speziell dann erfüllt, wenn das Gruppoid (S,*) ein neutrales Element e besitzt, welches gleichzeitig größtes Element in der partiell geordneten Menge (S,) ist.

Beweis: Gilt a*b = inf{a, b}, so ist a*b stets untere Schranke von {a, b} und die ersten beiden Ungleichungen sind erfüllt. Außerdem ist die Multiplikation dann idempotent, woraus die dritte Ungleichung folgt. Umgekehrt besagen die ersten beiden Ungleichungen, daß a*b untere Schranke von {a, b} ist. Für jede weitere untere Schranke c dieser Menge folgt dann aber aus der dritten Ungleichung c c*c a*b, wobei im letzten Schritt c a, c b und das Monotoniegesetz verwendet wurde. Also ist a*b größte untere Schranke von {a, b}. Ist schließlich das neutrale Element e größtes Element der partiell geordneten Menge, so folgt aus b e und dem Monotoniegesetz sofort a*b a*e = a. Entsprechend erhält man a*b b.

Durch Dualisierung erhält man eine entsprechende Aussage für das Übereinstimmen der Multiplikation und der Supremumsbildung.

Ist (S,*) eine Gruppoid und eine partielle Ordnung auf S, so nennt man eine zweistellige Operation \ auf S rechtsresidual zu *, wenn

(6r)  a * b c   <=>   b a\c

für alle a, b, c aus S gilt. Entsprechend heißt eine zweistellige Operation / auf S linksresidual zu *, wenn stets

(6l)  a * b c   <=>   a c/b

gilt. Aus a b und (6r) folgt wegen c*b c*b zunächst a b c\(c*b) und hieraus dann wiederum mit (6r) c*a c*b. Analog folgt mit (6l) a*c b*c. Existieren also sowohl eine rechts- als auch eine linksresiduale Verknüpfung zu *, so ist (S,*,) ein partiell geordnetes Gruppoid und man nennt es ein residuiertes partiell geordnetes Gruppoid und notiert es genauer als (S,*,\,/,). Falls * assoziativ ist, spricht man natürlich von einer residuierten partiell geordneten Halbgruppe.
Ist in einem residuierten partiell geordneten Gruppoid (S,*,) die Multiplikation * kommutativ, so gilt

(7)  a\b = b/a

für alle a, b aus S. Es ist nämlich a\b a\b und dies ist wegen (6r) gleichwertig zu a*(a\b) b und weiter wegen der Kommutativität zu (a\b)*a b und schließlich wegen (6l) gleichwertig zu a\b b/a. Analog ist b/a b/a gleichwertig zu b/a a\b, woraus (7) folgt. In diesem Fall schreibt man a -> b anstelle von a/b bzw. b/a.
Ist (S,*,\,/,) eine residuierte partiell geordnete Halbgruppe mit einem neutralen Element e bezüglich * und außerdem (S,) ein Verband (S,,), so nennt man (S,,,*,\,/,e) einen residuierten Verband. Ist (S,*) kommutativ, so schreibt man gemäß der obigen Bemerkung (S,,,*,->,e)
Ein residuierter Verband (S,,,*,\,/,e) heißt integral, wenn e größtes Element des Verbandes (S,,) ist.
Ein residuierter Verband (S,,,*,\,/,e) heißt idempotent-wachsend wenn a a*a für alle a aus S gilt. Nach dem oben bewiesenen Satz für partiell geordnete Gruppoide stimmen in einem residuierten Verband genau dann die Multiplikation und die Infimumsbildung überein, wenn er integral und idempotent-wachsend ist.

Beispiele für partiell geordnete Gruppoide

  • Die natürlichen Zahlen N bilden mit der üblichen (linearen) Ordnungsrelation total geordnete Halbgruppen (N,+,) und (N,*,).
  • Die ganzen Zahlen Z bilden mit der üblichen (linearen) Ordnungsrelation eine l-Gruppe (Z,+,).
  • Für jeden Halbverband (S,*) wird durch a b <=> a*b = a eine partielle Ordnung auf S definiert, die (S,*,) zu einer partiell geordneten Halbgruppe macht. Man nennt diese partielle Ordnung auch die natürliche partielle Ordnung auf dem Halbverband.
  • Jede l-Gruppe (S,,,*,-1,e) ist ein residuierter Verband (S,,,*,\,/,e) mit den residualen Verknüpfungen gemäß a\b = a-1*b und b/a = b*a-1.