Pseudo-Magma

Ein Pseudo-Magma (neutrum, Mehrzahl Pseudo-Magmen), partielles Magma, Pseudo-Gruppoid, partielles Gruppoid oder Halbgruppoid (in Anlehnung an das englische halfgroupoid), ist eine algebraische Struktur (genauer: partielle Algebra) ${\displaystyle (M,f)}$, die aus einer Menge ${\displaystyle M}$ und einer partiellen Abbildung ${\displaystyle f\colon M\times M\rightsquigarrow M}$ besteht.

Es ist eine Verallgemeinerung des mathematischen Begriffes des Magmas bzw. Gruppoids, in dem die Abbildung ${\displaystyle f}$ eine zweistellige, innere Verknüpfung sein muss (${\displaystyle f\colon M\times M\rightarrow M}$), also nicht mehr partiell sein darf.

Alternative Definition

Ein Pseudo-Magma ${\displaystyle (M,f)}$ kann auch als eine Menge ${\displaystyle M}$ zusammen mit einer äußeren zweistelligen Verknüpfung zweiter Art ${\displaystyle f\colon M\times M\rightarrow B}$ definiert werden.

Ein Pseudo-Magma ${\displaystyle (M,f)}$ definiert über eine partielle Abbildung kann in ein äquivalentes Pseudo-Magma ${\displaystyle (M,f')}$ mit einer äußeren zweistelligen Verknüpfung zweiter Art umgewandelt werden, indem man ${\displaystyle B:=M\cup \{x\}}$ mit ${\displaystyle x\notin M}$ festlegt und ${\displaystyle f'(a,b)=x}$ setzt, falls ${\displaystyle (a,b)\notin {\mbox{Def}}(f)}$, sonst ${\displaystyle f'(a,b)=f(a,b)}$.

Andersherum kann ein Pseudo-Magma ${\displaystyle (M,f')}$ mit einer äußeren zweistelligen Verknüpfung zweiter Art in ein äquivalentes Pseudo-Magma ${\displaystyle (M,f)}$ definiert über eine partielle Abbildung umgewandelt werden, indem man ${\displaystyle f}$ als undefiniert an der Stelle ${\displaystyle (a,b)}$ setzt, falls ${\displaystyle f'(a,b)\notin M}$, sonst ${\displaystyle f(a,b)=f'(a,b)}$.

Beide Definitionen sind daher in einem gewissen Sinne äquivalent.

Weitere Definitionen

Unterpseudomagma

Analog zu einem Untermagma oder einer Untergruppe kann ein Unterpseudomagma (oder Teilhalbgruppoid oder Unterhalbgruppoid in Anlehnung an das englische subhalfgroupoid) von einem Pseudo-Magma definiert werden. Hierbei muss jedoch der Definitionsbereich der Verknüpfung gesondert betrachtet werden.

Sei ${\displaystyle {\boldsymbol {M}}=(M,*)}$ ein Pseudo-Magma. Ein Pseudo-Magma ${\displaystyle {\boldsymbol {U}}=(U,\circ )}$ heißt Unterpseudomagma von ${\displaystyle {\boldsymbol {M}}}$, wenn ${\displaystyle U\subseteq M}$ und ${\displaystyle \circ =*|_{{\mbox{Def}}(\circ )}}$, d. h. die Verknüpfung ${\displaystyle \circ }$ ist die Einschränkung von ${\displaystyle *}$ auf ${\displaystyle {\mbox{Def}}(\circ )\subseteq U\times U}$.

Genau dann ist also ${\displaystyle {\boldsymbol {U}}}$ ein Unterpseudomagma von ${\displaystyle {\boldsymbol {M}}}$, wenn ${\displaystyle U\subseteq M}$ und es gilt

${\displaystyle {\mbox{Def}}(\circ )\subseteq {\mbox{Def}}(*)\cap U\times U}$

und

${\displaystyle a*b=a\circ b\in U}$ für alle ${\displaystyle (a,b)\in {\mbox{Def}}(\circ )}$.

Ein Magma ${\displaystyle {\boldsymbol {M}}=(M,*)}$ kann demnach ein Unterpseudomagma enthalten, das kein Untermagma ist, nämlich wenn gilt:

${\displaystyle {\mbox{Def}}(\circ )\subsetneq U\times U={\mbox{Def}}(*)\cap U\times U}$.

Beispiel

Seien ${\displaystyle {\boldsymbol {M}}=(M,*)}$ und ${\displaystyle {\boldsymbol {U}}=(U,\circ )}$ mit ${\displaystyle M=\{a,b,c\}}$, ${\displaystyle U=\{a,b\}}$ und folgenden Verknüpfungstafeln für ${\displaystyle *}$ und ${\displaystyle \circ }$:

${\displaystyle *}$ a b c a a b - b c b a c c a -

${\displaystyle \circ }$ a b a a b b - b

Dann ist ${\displaystyle {\boldsymbol {U}}}$ Unterpseudomagma von ${\displaystyle {\boldsymbol {M}}}$.

Anmerkungen:

• Der Wert von ${\displaystyle b*a}$ kann beliebig sein (er könnte auch ${\displaystyle a}$, ${\displaystyle b}$ oder undefiniert sein), da ${\displaystyle (b,a)\notin {\mbox{Def}}(\circ )}$.
• Falls jedoch ${\displaystyle (a,b)\notin {\mbox{Def}}(*)}$ wäre, dann wäre ${\displaystyle {\boldsymbol {U}}}$ kein Unterpseudomagma von ${\displaystyle {\boldsymbol {M}}}$, da dann wegen ${\displaystyle (a,b)\in {\mbox{Def}}(\circ )}$ nicht ${\displaystyle {\mbox{Def}}(\circ )\subset {\mbox{Def}}(*)\cap U\times U}$ gelten würde.

Weitere Eigenschaften von Unterpseudomagmen

Sei ${\displaystyle {\boldsymbol {M}}=(M,*)}$ ein Pseudo-Magma und ${\displaystyle {\boldsymbol {U}}=(U,\circ )}$ ein Unterpseudomagma von ${\displaystyle {\boldsymbol {M}}}$.

• ${\displaystyle {\boldsymbol {U}}}$ heißt abgeschlossen in ${\displaystyle {\boldsymbol {M}}}$ (engl. „closed in M“), wenn aus ${\displaystyle a,b\in U}$ und ${\displaystyle (a,b)\in {\mbox{Def}}(*)}$ und ${\displaystyle a*b=c}$ folgt ${\displaystyle (a,b)\in {\mbox{Def}}(\circ )}$ und ${\displaystyle a\circ b=c}$. Beispiel:

${\displaystyle *}$ a b c a a b - b b - a c c a -

${\displaystyle \circ }$ a b a a b b b -

• ${\displaystyle {\boldsymbol {M}}}$ heißt Erweiterung von ${\displaystyle {\boldsymbol {U}}}$ (engl. „extension of U“), wenn aus ${\displaystyle a,b\in M}$ und ${\displaystyle (a,b)\in {\mbox{Def}}(*)}$ folgt ${\displaystyle a,b\in U}$, und aus ${\displaystyle c\in M\land c\notin U}$ folgt ${\displaystyle \exists (a,b)\in U\times U:(a,b)\in {\mbox{Def}}(*)\land c=a*b}$. Beispiel:

${\displaystyle *}$ a b c a a - - b b c - c - - -

${\displaystyle \circ }$ a b a a - b b -

• Eine Erweiterung ${\displaystyle {\boldsymbol {M}}}$ von ${\displaystyle {\boldsymbol {U}}}$ heißt vollständige Erweiterung von ${\displaystyle {\boldsymbol {U}}}$ (engl. „complete extension of U“), wenn ${\displaystyle \forall (a,b)\in U\times U:(a,b)\in {\mbox{Def}}(*)}$. Beispiel:

${\displaystyle *}$ a b c a a b - b b c - c - - -

${\displaystyle \circ }$ a b a a - b b -

• Eine Erweiterung ${\displaystyle {\boldsymbol {M}}}$ von ${\displaystyle {\boldsymbol {U}}}$ heißt offene Erweiterung von ${\displaystyle {\boldsymbol {U}}}$ (engl. „open extension of U“), wenn aus ${\displaystyle (a,b)\in {\mbox{Def}}(*)}$, ${\displaystyle a*b=c}$ und ${\displaystyle c\in U}$ folgt ${\displaystyle (a,b)\in {\mbox{Def}}(\circ )}$ und ${\displaystyle a\circ b=c}$, und aus ${\displaystyle c\in M\land c\notin U}$ und ${\displaystyle (a,b)\in {\mbox{Def}}(*)\land (a',b')\in {\mbox{Def}}(*)\land a*b=a'*b'=c}$ folgt ${\displaystyle a=a'\land b=b'}$. Beispiel:

${\displaystyle *}$ a b c d a a - - - b d c - - c - - - - d - - - -

${\displaystyle \circ }$ a b a a - b - -

Anmerkungen:

• Jedes Pseudo-Magma ist ein abgeschlossenes Unterpseudomagma von sich selbst.
• Jedes Pseudo-Magma ist eine offene Erweiterung von sich selbst.
• Ein Pseudo-Magma, das eine vollständige Erweiterung von sich selbst ist, ist ein Magma.
• Ein Pseudo-Magma, das kein Magma ist, kann eine offene, oder vollständige, oder offene und vollständige Erweiterung haben. Beispiel einer offenen und vollständigen Erweiterung:

${\displaystyle *}$ a b c d e a a e - - - b d c - - - c - - - - - d - - - - - e - - - - -

${\displaystyle \circ }$ a b a a - b - -

Rechengesetze

Ein Pseudo-Magma kann analog zu einem Magma assoziativ oder kommutativ sein, jedoch muss hier der Definitionsbereich genauer berücksichtigt werden. Es gelten somit folgende, abgewandelte Rechengesetze:

• Ein Pseudo-Magma ${\displaystyle (M,\circ )}$ ist assoziativ (und heißt dann auch partielle Halbgruppe), wenn für alle ${\displaystyle x,y,z\in M}$ mit ${\displaystyle x\circ y\in M}$ und ${\displaystyle y\circ z\in M}$ gilt

1. ${\displaystyle x\circ (y\circ z)\in M}$ genau dann wenn ${\displaystyle (x\circ y)\circ z\in M}$
2. und ${\displaystyle x\circ (y\circ z)=(x\circ y)\circ z}$, wenn ${\displaystyle x\circ (y\circ z)\in M}$ (und somit nach 1. auch ${\displaystyle (x\circ y)\circ z\in M}$)

• Ein Pseudo-Magma ${\displaystyle (M,\circ )}$ ist kommutativ, wenn für alle ${\displaystyle x,y\in M}$ gilt

1. ${\displaystyle x\circ y\in M}$ genau dann wenn ${\displaystyle y\circ x\in M}$
2. und ${\displaystyle x\circ y=y\circ x}$, wenn ${\displaystyle x\circ y\in M}$ (und somit nach 1. auch ${\displaystyle y\circ x\in M}$)

Beispiele

• Ein Beispiel eines assoziativen Pseudo-Magmas findet sich bei den sogenannten kleinen Kategorien, in denen die Klasse der Pfeile eine Menge ist. Diese Menge bildet zusammen mit der für Pfeile erklärten Verknüpfung ein assoziatives Pseudo-Magma. – Die formale Voraussetzung, dass die Kategorie klein sein muss, ist jedoch meist vernachlässigbar. In der Regel lassen sich alle Erkenntnisse über Pseudo-Magmen auch auf die Klasse der Pfeile mit der zugehörigen Verknüpfung übertragen.
• Im Allgemeinen lassen sich die Anforderungen für Kategorien auf eine Kompositionsoperation reduzieren, um ein Pseudo-Magma zu erhalten, dieses muss dann allerdings nicht assoziativ sein und auch keine Einselemente haben.
• Auch jede beliebige Menge M von Abbildungen wird vermöge der Hintereinanderausführung als Komposition ${\displaystyle \circ \colon M\times M\to M,(\operatorname {f} ,\operatorname {g} )\mapsto \operatorname {f} \circ \operatorname {g} }$ zu einem assoziativen Pseudo-Magma ${\displaystyle (M,\circ ).}$
• Formale Sprachen sind im Allgemeinen assoziative Pseudo-Magmen in Bezug auf die Verkettung (Hintereinanderschreibung) als Verknüpfung. Die sogenannte *-Sprache ${\displaystyle \Sigma ^{*}}$ (sprich: „Stern-Sprache“, vgl. Kleene-Stern) über einem Alphabet Σ ist zwar zunächst eine Halbgruppe (sogar ein Monoid), da in ihr die Verkettung zweier Worte zu einem neuen Wort erklärt ist und das neue Wort wieder in der Sprache liegt. Formale Sprachen sind aber als beliebige Untermengen beliebiger solcher *-Sprachen definiert, so dass in einer speziellen Sprache die Verkettung zweier Worte zwar immer noch erklärt/erklärbar ist, jedoch zu keinem Wort derselben Sprache führt.

Einzelnachweise

1. 1 2 Günther Eisenreich: Lexikon der Algebra. Akademie-Verlag/Springer-Verlag, Berlin 1989, ISBN 3-05-500231-8. 
2. 1 2 3 4 5 6 Richard Hubert Bruck: A survey of binary systems. In: P.J.Hilton (Hrsg.): Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Auflage. Band 20. Springer Verlag, Berlin / Heidelberg / New York 1971, ISBN 978-3-662-42837-5. 
3. ↑ Yoshifumi Inui, François Le Gall: Quantum Property Testing of Group Solvability. S. 2, arxiv:0712.3829 (Definition am Anfang von § 2.1). 
4. ↑ Shelp, R. H.: Proc. London Math. Soc. (1972) s3-24 (1). London Mathematical Soc., 1972, A Partial Semigroup Approach to Partially Ordered Sets, S. 46–58 (englisch).