Zur Struktur freier regulärer unärer Halbgruppen

Diplomarbeit von

Florence Micol

�

Technische Universität Darmstadt

Fachbereich Mathematik

1997

Betreuer: Prof. Dr. Chr. Herrmann

Inhaltsverzeichnis

1 Die freien Algebren in Varietäten und das Wortproblem 5

1.1 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.1 Aus der Allgemeinen Algebra . . . . . . . . . . . . . . 5 1.1.2 Aus der Kategorientheorie . . . . . . . . . . . . . . . . 6 1.1.3 Universelle Eigenschaft . . . . . . . . . . . . . . . . . . 9 1.1.4 Unäre Monoide und reguläre unäre Monoide . . . . . . 10

1.2 Modelle für die freien Algebren in Varietäten . . . . . . . . . . 11 1.2.1 Ein graphisches Modell für die Termalgebren . . . . . . 11 1.2.2 Faktorisierung . . . . . . . . . . . . . . . . . . . . . . . 11

1.3 Das Wortproblem: Grenzen der Faktorisierung — Beispiele . . 14 1.3.1 Assoziativ gemachte Verkettung . . . . . . . . . . . . . 14 1.3.2 Ein graphisches Modell . . . . . . . . . . . . . . . . . . 16 1.3.3 Freie reguläre unäre Monoide . . . . . . . . . . . . . . 17

2 Hilfskonstruktionen für die Erweiterung der Signatur 20

2.1 Polynomiale Algebren . . . . . . . . . . . . . . . . . . . . . . . 20 2.1.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.1.2 Eigenschaften . . . . . . . . . . . . . . . . . . . . . . . 24

2.2 Gemischte Coprodukte . . . . . . . . . . . . . . . . . . . . . . 26 2.2.1 Gemischte Diagramme . . . . . . . . . . . . . . . . . . 27 2.2.2 Gemischte Coprodukte . . . . . . . . . . . . . . . . . . 28

2.3 Konkrete Konstruktionen . . . . . . . . . . . . . . . . . . . . . 32 2.3.1 Binäres Coprodukt von Monoiden . . . . . . . . . . . . 32 2.3.2 Gemischtes Coprodukt einer Halbgruppe und eines Mo-

noids . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.3 Polynomiale Algebren über Monoiden . . . . . . . . . . 36

2.4 Erweiterungen mit polynomialen Algebren . . . . . . . . . . . 36 3 Die freien unären Monoide 39

3.1 Ein Modell für die freien unären Monoide . . . . . . . . . . . . 39 3.1.1 Erzeugung der unären Monoide als Monoide . . . . . . 39 3.1.2 Ein Modell für die freien unären Monoide . . . . . . . . 43 3.1.3 Eine Methode für die Signaturerweiterung . . . . . . . 45

3.2 Von den freien unären zu den freien regulären unären Monoiden 47 3.2.1 Dualität . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.2.2 Hilfsmittel für das Aussuchen der Normalformen …. 49 3.2.3 Axiomatische Formulierung . . . . . . . . . . . . . . . 53

4 Die freien regulären unären Monoide 56

4.1 Ein Rahmen für die Konstruktion: d-Reihen . . . . . . . . . . 56 4.1.1 Definition und Beispiele . . . . . . . . . . . . . . . . . 56 4.1.2 Weitere Hilfsoperationen . . . . . . . . . . . . . . . . . 58 4.1.3 Eigenschaften . . . . . . . . . . . . . . . . . . . . . . . 58

4.2 Poláks Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.2.1 Konstruktion . . . . . . . . . . . . . . . . . . . . . . . 60 4.2.2 Korrektheit . . . . . . . . . . . . . . . . . . . . . . . . 61

Einleitung

L. Polák hat in [Pol89] ein Modell für die freien regulären unären Halbgruppen angegeben, das das Wortproblem löst; das heißt, seine Konstruktion liefert auch ein Entscheidungsverfahren für die Gleichungstheorie der regulären unären Halbgruppen.

In dieser Konstruktion geht er von den freien unären Halbgruppen aus, und wählt Elemente aus, die die Grundmenge der freien regulären unären Halbgruppe sein werden. Auf dieser Grundmenge von Normalformen werden neue Operationen definiert, die diese zu einer regulären unären Halbgruppe machen.

In dieser Arbeit geht es darum, die Konstruktion als Verfahren zu analysieren, nicht zuletzt mit der Hoffnung, daß man für freie reguläre unäre Ringe ähnlich vorgehen könnte. Ein erster Schwerpunkt der Arbeit ist das Prinzip der Erweiterung der Signatur, ohne bei der Termalgebra anfangen zu müssen. Ein zweiter Schwerpunkt besteht darin, die Technik der Faktorisierung zu untersuchen.

Dafür werden einige Hilfsmittel eingesetzt: für die Erweiterung der Signatur werden bestimmte Algebren konstruiert, die den Begriff der polynomialen Algebren verallgemeinern. Spezielle Colimites bieten sich an, um Beweise zu strukturieren. Für das Auswählen der Normalformen und die Definition der Operationen wird eine Relation verwendet, die hier axiomatisch formuliert wird.

An dieser Stelle möchte ich denjenigen danken, die meinen Aufenthalt in Darmstadt ermöglicht haben, insbesondere Herrn Prof. Dr. Keimel, der sich für das Doppel-Diplom Programm TUD-ECL eingesetzt hat.

Ich bedanke mich herzlich bei Herrn Prof. Dr. Herrmann für die Betreuung der Arbeit, für seine Ermunterung und seine anregenden Vorschläge.

Schließlich möchte ich Christian Elsholtz und Thomas Erker für ihre Hilfsbereitschaft, die ausführlichen Korrekturen sowie ihre freundliche Ratschläge danken.

Kapitel 1

Die freien Algebren in Varietäten und das Wortproblem

1.1 Grundlagen

1.1.1 Aus der Allgemeinen Algebra

Die grundlegenden Definitionen und Konstruktionen (Termalgebra, Faktorisierung) der Allgemeinen Algebra befinden sich z. B. in dem ersten Abschnitt des ersten Kapitels von [LN73]. Diese werden hier als Stichwörter aufgelistet. Dabei legen wir auch einige Bezeichnungen fest.

• Eine (allgemeine) Algebra bezeichnen wir meistens mit A (als Objekt einer Kategorie).

• Für die Grundmenge wollen wir keine Notation einführen, sie heißt auch A falls der Bezug zu Mengen klar ist, sonst wendet man den Vergißfunktor auf die Algebra an: VA. Die Ordnung einer Algebra ist die Kardinalität der Grundmenge.

• Die Signatur (oder den Typ) bezeichnen wir mit Σ, und die Algebren der Signatur Σ sind Σ-Algebren. Algebren derselben Signatur heißen ähnliche Algebren. Beispiele für die Benutzung der Operationssymbole ∘, ′ und f^{N} sind x ∘ y oder xy, x′ und f^{N}(x) … • Für eine Unteralgebra B mit Erzeugermenge E schreiben wir

B =< E > .

• Für einen injektiven Homomorphismus ι (Einbettung) schreiben wir ⊂ ^{ι}^{}.

• Kongruenz, Faktoralgebra sind üblicherweise mit γ, A_{/γ} bezeichnet.

• Die Varietät der Σ-Algebren bezeichnen wir mit 𝔎_{0}. Die freie Algebra in 𝔎_{0} über der Variablenmenge X ist T (X), die Termalgebra über X.

• Wir interessieren uns lediglich für Gesetze, die mit Gleichungen beschrieben werden (insbesondere gibt es keinen Existenz-Quantor in den Formeln, siehe die Bemerkung 1.1.4 für ”reguläre Ringe“, die nicht unär sind).

• Menge von Gesetzen über Σ sind G, G′. Die durch G, bzw. G′ bestimmten Varietäten bezeichnen wir mit 𝔎, 𝔎′ und die freien Algebren über X in diesen Varietäten mit F (X) und F′(X).

• Für eine aufsteigende Folge von ähnlichen Algebren (A_{n})_{n∈ℕ} wird das Supremum mit ⨆_{n∈ℕ} A_{n} oder kurz ⨆ A_{n} bezeichnet (Vereinigung der Grundmengen, Erweiterung der Operationen).

Auf weitere Ergebnisse des Abschnitts 1.3 in [LN73] wird im nächsten Abschnitt hingewiesen. Der Abschnitt 1.4 liefert den Ausgangspunkt des Kapitels 2.

1.1.2 Aus der Kategorientheorie

Die Kategorientheorie bietet eine präzise und knappe Sprache an, die für die Varietäten besonders geeignet ist. Die Begriffe, die für die Algebra schon allgemein genug sind, werden z. B. in [MLB88] erklärt und anhand von Beispielen veranschaulicht. In den Abschnitten 1 bis 6 des Kapitel IV von [MLB88] werden Objekte, Morphismen (Mono-, Epi-, Isomorphismen), Funktoren, insbesondere Vergißfunktoren (Varietäten ”sind“ konkrete Kategorien) eingeführt, und universelle Eigenschaften und adjungierte Funktoren in den Abschnitten 1 bis 5 und 7 des Kapitels XV. Andere, etwas formalere Begriffe, die wir auch verwenden wollen, werden in [ML72] definiert: Kommakategorien, universelle Pfeile, Adjunktionen, Colimites. Wichtige Notationen:

die Kategorie \underline{ω} sei die linear geordnete Menge aller endlichen Ordinalzahlen (also, die freie Kategorie, die vom Graphen {0 ^{}1 ^{}2 ^{}⋯ } erzeugt wird). Ein Funktor F mit der Kategorie \underline{ω} als Quelle ist also schon durch die Werte für die Objekte n und die Pfeile der Form n ^{}n + 1 eindeutig bestimmt.

Colimites für Funktoren werden in [ML72] folgenderweise definiert: Gegeben seien der Funktor F: \underline{J} ^{}\underline{C} und ein Diagonalfunktor Δ : \underline{C} ^{}\underline{C}\underline{J}, dann ist ein Colimes für den Funktor F ein universeller Pfeil < r, u > von F nach Δ, wobei u = F ⟹ Δr die natürliche Transformation bezeichnet und lim_{→} F := r für die Spitze des Colimeskegels steht.

Folgenfunktor und Approximationsfunktoren sind ein Spezialfall hiervon, dem wir öfters begegnen werden.

1. Eine wachsende Folge von ähnlichen Algebren (A_{n})_{n∈ℕ} in einer Varietät 𝔅 definiert einen Folgenfunktor

A: \underline{ω} → \underline{𝔅}
n ↦ A_{n}
(n^{⊂} ^{}n + 1) ↦ (A_{n} ^{⊂} ^{}A_{n+1}),

in Zeichen:

A: A_{0} ^{⊂} ^{e_{0}}^{}A_{1} ^{⊂} ^{e_{1}}^{}A_{2} ^{⊂} ^{e_{2}}^{}⋯ A_{n} ^{⊂} ^{e_{n}}^{}⋯

Das mit ⨆_{n} A_{n} bezeichnete Supremum der Folge ergibt sich als Colimes für den Folgenfunktor A:

[figure: A_{0}; ⊂; e_{0}; A_{1}; ⊂; e_{1}; A_{2}; ⋯; A_{n}; ⊂; e_{n}; ⋯]
⋯
[figure: ⨆ A_{n}.; ⊂; a_{n}; ⊂; a_{2}; ⊂; a_{1}; ⊂; a_{0}]

2. Sei (B_{n})_{n∈ℕ} eine weitere aufsteigende Folge in 𝔅 mit ihrem Folgenfunktor B. Wenn es eine natürliche Transformation (f_{n})_{n∈ℕ} von A nach B gibt (beachte, im Spezialfall von \underline{ω} muß nur nachgeprüft werden, daß alle Vierecke der Form

[figure: A_{n}; ⊂; A_{n+1}; B_{n}; f_{n}; ⊂; B_{n+1}; f_{n+1}]

kommutieren), dann existiert ein eindeutiger Homomorphismus f von ⨆ A_{n} nach ⨆ B_{n}, so daß das folgende Diagramm kommutiert:

[figure: A_{0}; ⊂; A_{1}; ⊂; A_{2}; ⊂; ⋯; A_{n}; ⋯; ⨆ A_{n}; B_{0}; f_{0}; ⊂; B_{1}; f_{1}; ⊂; B_{2}; f_{2}; ⊂; ⋯; B_{n}; f_{n}; ⋯; ⨆ B_{n}.; . . . . . . .; f]

3. Man kann eine Folge von Approximationsfunktoren (A_{n})_{n} definieren, die mit dem Folgenfunktor A bis zum Rang n übereinstimmen und dann stehenbleiben:

A_{n}: \underline{ω} → \underline{𝔅}
k ↦ \{ \begin{matrix}A_{k} & für k < n \\ A_{n} & für k ≥ n \end{matrix}
(k ^{⊂} ^{}k + 1) ↦ \{ \begin{matrix}e_{k} & für k < n \\ Id_{A_{n}} & für k ≥ n . \end{matrix}

Es ist A_{n} = lim_{→} A_{n} für alle n ∈ ℕ. Durch

r_{n,k} := \{ \begin{matrix}Id_{A_{k}} & für k < n \\ e_{n} & für k ≥ n \end{matrix}

wird offensichtlich eine natürliche Transformation r_{n} von A_{n} nach A_{n+1} definiert.

Der Folgenfunktor A ist Colimes für den Funktor:

\underline{ω} → \underline{𝔅}\underline{ω}
n ↦ A_{n}
(n^{⊂} ^{}n + 1) ↦ (A_{n} =^{r_{n}}⇒ A_{n+1})

Durch den Folgenfunktor oder die Folge der Approximationen wird dieselbe Folge dargestellt. Die Darstellung durch die Folge der Approximationen wird in dem Kapitel 4.2 für die d-Reihen verwendet. Die Folgenfunktoren werden besonders interessant für Konstruktionen, bei denen linksadjungierte Funktoren eintreten, denn es gilt folgender Satz.

Satz 1.1 Linksadjungierte erhalten Colimites. Der Funktor F: \underline{X} ^{}\underline{A} besitze einen Rechtsadungierten, während der Funktor S: \underline{J} ^{}\underline{X} einen Colimeskegel τ: S ⟹ s in \underline{X} besitze. Dann besitzt F ∘ S den Colimeskegel Fτ: F ∘ S ⟹ Fs in \underline{A}.

Die (duale) Aussage wird z. B. in [ML72, V. Limites, 5. Verhalten von Adjungierten auf Limites] bewiesen. Unter Vertauschen von Colimites und Linksadjungierten verstehen wir

F(lim_{→} S) = lim_{→}(F ∘ S)

1.1.3 Universelle Eigenschaft

Wir übernehmen die Bezeichnungen aus [ML72, IV.1] für die Adjunktionen. Die Einheit einer Adjunktion < F, V, φ >: \underline{X} ⇀ \underline{A} bezeichnen wir insbesondere mit η. Die Aussage ”der Pfeil η_{X} ist universell von V nach X“ bedeutet, daß zu jedem Objekt A in \underline{A} und jedem Pfeil X ^{h}^{}VA ein eindeutiger Pfeil FX ^{h^{+}}^{}A aus \underline{A} existiert, so daß das Diagramm kommutiert.

[figure: X; ⊂; η_{X}; V ∘ FX; VA; Vh^{+}; h]

Es ist dann h^{+} = φ_{X,A}^{−1}h.

1.1.4 Unäre Monoide und reguläre unäre Monoide

Das Wort ”unär“ steht als Übersetzung des Englischen ”unary“, es weist darauf hin, daß die Signatur der üblichen Struktur um eine einstellige Operation erweitert wird. Für die Monoide haben wir also die folgenden Definitionen:

Halbgruppe (allgemeine) Algebra mit einer zweistelligen assoziativen Verkettung.

Monoid Halbgruppe mit einer Konstante λ, die links- und rechtsneutrales Element der Verkettung ∘ ist. (Konvention: die Klammern für die Verkettung werden nicht mehr hingeschrieben)

unäres Monoid Monoid mit einstelliger Operation ′ und Gesetz λ′ = λ.

reguläres unäres Monoid unäres Monoid mit den Gesetzen a ∘ a′ ∘ a = a und a′ ∘ a ∘ a′ = a′. Man sieht leicht ein, daß λ′ = λ aus der Neutralität von λ und a ∘ a′ ∘ a = a folgt.

Die folgende Tabelle faßt die Bezeichnungen der entsprechenden Kategorien zusammen:

Varietät  Bezeichnung der entsprechenden Kategorie
Halbgruppen  \underline{Hbgr}
Monoide  \underline{Mon}
unäre Monoide  \underline{unMon}
reguläre unäre Monoide \underline{runMon}

Die Kategorie \underline{runMon} ist eine volle Unterkategorie von \underline{unMon}. Eine ähnliche Bezeichnung existiert für (nicht notwendigerweise kommutative) Ringe: unäre, reguläre unäre Ringe, dabei sind diese als Monoide für die Multiplikation zu verstehen. Bemerkung: In der Literatur findet man auch den Begriff ”reguläre Ringe“. Beide sind aber nicht äquivalent! Ein Ring R heißt regulär, wenn für jedes r ∈ R es (mindestens) ein Element q existiert (Quasi-Inverses), so daß gilt: rqr = r und qrq = q. Mit dieser Definition bilden die regulären Ringe keine Varietät. Beispiele, für die die Eindeutigkeit des Quasi-Inversen nicht vorliegt, sind in [Bur80] zu finden.

1.2 Modelle für die freien Algebren in Varietäten

1.2.1 Ein graphisches Modell für die Termalgebren

Bekanntlich sind Bäume mit markierten Knoten eine mögliche Beschreibung der Termalgebren. Die Blätter sind Variablen und die Knoten sind mit den Namen der Operationssymbole versehen (die Stelligkeit der Operationen bestimmt die Anzahl der Eingaben in den Knoten hinein). Die Definition der Operationen auf den Bäumen ist offensichtlich, ein Teilterm ist ein Ast des ganzen Baums …

1.2.2 Faktorisierung

Faktorisierung in der Termalgebra

Sei eine Kongruenzrelation σ auf einer Algebra A. Die Abbildung, die einem Element a ∈ A seine Äquivalenzklasse [a] zuordnet, ist ein surjektiver Homomorphismus A ^{π_{σ}}^{}A_{/σ}. Wir beschränken uns auf Klassen von Algebren deren Eigenschaften mit Hilfe einer (endlichen) Gleichungsmenge beschrieben werden. Diese Klassen sind Varietäten, und man kann die von den Gleichungen erzwungene (erzeugte) Kongruenzrelation auf der Termalgebra definieren. Die Faktorisierung einer Termalgebra nach der von den Gleichungen erzeugten Kongruenzrelation liefert einen Beweis zur Existenz der freien Algebren in Varietäten:

Satz 1.2 Jede nicht triviale Varietät hat freie Algebren über Erzeugermengen beliebiger Kardinalität.

Den Beweis kann man z. B. im Abschnitt 3.21 von [LN73] finden. Hier wird die Idee kurz wiederholt. Gegeben seien eine Variablenmenge X und eine Signatur Σ. Sei G eine Gleichungsmenge über Σ. Wir übernehmen die Bezeichnungen von 1.1.1 für 𝔎_{0}, 𝔎, T (X), F (X). Wir nennen γ die von der Gleichungsmenge G erzeugte Kongruenzrelation in T (X). Wir haben bereits das kommutierende Diagramm:

[figure: X; ⊂; η_{X}^{0}; VT (X); VT (X)_{/γ}; Vπ_{γ}; ⊂; η_{X}]

Sei nun eine Algebra H in 𝔎, und eine Abbildung X ^{h}^{}VH. Wir wollen h homomorph auf T (X)_{/γ} fortsetzen. Existenz: Zuerst setzen wir h zu einem Homomorphismus h_{0} (in 𝔎_{0}) auf T (X) fort. Da H die Gesetze von G erfüllt, gilt Kern(π_{γ}) ⊆ Kern(t_{0}). Es existiert also ein Homomorphismus h_{γ}, so daß das folgende Diagramm kommutiert:

[figure: T (X); π_{γ}; T (X)_{/γ}; H; h_{γ}; h_{0}]

Es ist h_{γ} ein Homomorphismus in 𝔎, der h auf T (X)_{/γ} fortsetzt. Eindeutigkeit: Die Fortsetzung auf T (X) ist eindeutig und π_{γ} ist ein Epimorphismus, also ist die Fortsetzung auf T (X)_{/γ} eindeutig.

Lemma 1 Für eine Teilmenge N ⊇ X von T (X) und eine Kongruenzrelation γ sind äquivalent:

1. N ist ein Repräsentantensystem für γ.

2. Zu jedem Term t ∈ T (X) gibt es ein n_{t} ∈ N mit n_{t}γt, und man kann auf N Operationen (f^{N})_{f∈Σ} so definieren, daß

(a) man eine von X erzeugte algebraische Struktur erhält, die G erfüllt,

(b) f^{N}(n_{1}, …, n_{k})γf(n_{1}, …, n_{k}) für n_{i} ∈ N.

𝔎  F (X) T (X) π_{γ} 𝔎_{0}

Abbildung 1.1: Faktorisierung in der Termalgebra

Definition 1 Falls diese Bedingungen erfüllt sind, nennen wir die Elemente von N Normalformen (bzgl. G). Es ist dann (N, (f^{N})_{f∈Σ}) ein Modell für F (X).

Leider ist im allgemeinen Fall die Kongruenzrelation γ nicht so handlich, daß man ”direkt, unmittelbar“ feststellen kann, ob zwei Elemente in derselben Äquivalenzklasse liegen; es ist dann natürlich schwierig, auf Kandidaten für die Normalformen zu kommen.

Faktorisierung in mehreren Etappen

Um die Faktorisierung nach der Kongruenzrelation zu vereinfachen, kann man versuchen, die Gleichungen in mehreren Stufen zu behandeln. Sind etwa die freien Algebren für eine größere Varietät bekannt, so möchte man in dieser größeren Varietät arbeiten. Wir halten in diesem Abschnitt die Variablenmenge X und die Signatur Σ fest, und untersuchen die Rolle einer Gleichungsmenge G über Σ. Eine Erweiterung von G ist eine (endliche) Gleichungsmenge G′ = G ∪ {g_{1}, …, g_{n}}, wobei g_{1}, …, g_{n} endlich viele neue Gleichungen über Σ sind.

Wir ergänzen die Notationen des Abschnitts 1.2.2:

Varietät Gleichungsmenge erzeugte Kongruenz freie Algebra über X

in T(X)

𝔎_{0}  ∅  T (X)
𝔎  G  γ  F (X)
𝔎′  G′  γ′  F′(X)

Nach dem Abschnitt 1.2.2 haben wir linksadjungierte Funktoren F, bzw. F′ zu den Vergißfunktoren von \underline{𝔎}, bzw. \underline{𝔎′} nach \underline{Set}. Falls der Inklusionsfunktor K von \underline{𝔎′} nach \underline{𝔎} auch linksadjungierbar ist (man sagt: die Kategorie \underline{𝔎′} ist reflexiv in \underline{𝔎}, mit Reflektor R), dann gilt

Satz 1.3 RF (X) ≅ F′(X) in 𝔎′ .

Denn: R ∘ F ist linksadjungiert zu V ∘ K, der isomorph zu V′ ist, also ist R ∘ F isomorph zu F′. Wenn die Pfeile der Einheit des Reflektors auch die Faktorisierung nach einer Kongruenzrelation beschreiben — wie das für Varietäten stets den Fall ist, dann kann man in mehreren Etappen faktorisieren.

1.3 Das Wortproblem: Grenzen der Faktorisierung — Beispiele

Die Konstruktion mit der Faktoralgebra ist zwar ein Beweis für die Existenz der freien Algebren in den Varietäten, aber wenn man damit ”rechnen“ will, zum Beispiel wissen, ob zwei Elemente der Termalgebra modulo der Kongruenzrelation gleich sind, dann hilft die Faktoralgebra nicht weiter. Man bräuchte etwa ein Repräsentantensystem für die Äquivalenzklassen der Kongruenzrelation (Normalformen).

1.3.1 Assoziativ gemachte Verkettung

Als erstes Beispiel betrachten wir Halbgruppen. Die Signatur Σ besteht aus einer zweistelligen Verkettung, die Gleichungmenge G aus dem Axiom der Assoziativität:

a(bc) = (ab)c  (1.1)

T (X) 𝔎_{0}  𝔎 F (X)  F′(X) π_{γ′}  𝔎′ π_{σ} π_{γ}

Abbildung 1.2: Faktorisierung in mehreren Etappen Die linksgeklammerten Terme liefern ein Repräsentantensystem für die Assoziativität. Man kann leicht feststellen, ob zwei Terme in derselben Äquivalenzklasse liegen.

1.3.2 Ein graphisches Modell

Nun beschreiben wir (ohne Beweis) ein graphisches Modell für die freien unären Monoide, das das Wortproblem löst. Das Modell läßt sich intuitiv als Mittelweg zwischen Bäumen und Listen auffassen. Auf den Beweis verzichten wir an dieser Stelle, da diesem Thema ein großer Teil des Kapitels 3 gewidmet wird …): die Schwierigkeit besteht darin, die Rekursivität der Definition zu beschreiben. Die Grundmenge eines freien unären Monoids läßt sich graphisch darstellen, indem man die von dem neutralen Element verschiedenen Argumente der assoziativen Verkettung auf einer waagerechten Linie von links nach rechts schreibt (wie bei Listen). Das Ergebnis der einstelligen Operation steht unter dem Argument und sie sind mit einer gestrichelten Linie verbunden (wie bei Bäumen). Für die Operationen geschieht Folgendes: Die Verkettung mit dem neutralen Element ändert nichts. Zwei andere Elemente werden bei der Verkettung nebeneinander geschrieben und mit einer vollen Linie verbunden. Für die einstellige Operation wird unter das Argument eine gestrichelte Linie gehängt. Zum Beispiel hat der Term (als Term in der Termalgebra, linksgeklammert) x(x′x)′x′x folgende Darstellung:

x x  x x  x x x  x x  x x x  x x  x x x  x x  x x x  x x  x x x  x x  x

1.3.3 Freie reguläre unäre Monoide

Hier geben wir ein Beispiel an, wo die Gleichheit modulo der Kongruenzrelation sich nicht so leicht feststellen läßt: reguläre unäre Monoide. Ein Entscheidungsverfahren für die Gleichungstheorie der regulären unären Monoide wurde von L. Polák in [Pol89] beschrieben. Sein Verfahren wird im Kapitel 4 analysiert. Nun konstruieren wir eine Folge (a_{n})_{n∈ℕ} von Termen, die alle äquivalent zueinander sind, wo man aber die Gleichung in beiden Richtungen verwenden soll, um die Äquivalenz zu zeigen. Sei X eine nichtleere Menge von Variablen und U(X) das freie unäre Monoid über X. Sei a ∈ U(X) (etwa: eine Variable x ∈ X). Wir definieren induktiv für n ∈ ℕ (dabei verzichten wir auf die Klammerung für die assoziative Verkettung, und ihr Symbol wird nicht geschrieben):

b_{0} := a
b_{n+1} := b′_{n}b_{n} also b_{n+1} = b′_{n} … b′_{0}a
a_{n} := ab_{n+1} also a_{n} = ab′_{n}b_{n}

Die ersten Terme der Folge sind

a_{0} = a \underbrace{a′a}
a_{1} = a \underbrace{(a′a)′a′a}
a_{2} = a \underbrace{((a′a)′a′a)′(a′a)′a′a}
…

Behauptung 1 Es gilt:

a_{n}σa für alle n ∈ ℕ  (1.2)

Zur Herleitung dieser Äquivalenzen führen wir drei Notationen ein, die spezielle Herleitungsregeln abkürzen:

Den Schluß \frac{w := uu′uσu}{t[w, …]σt[u, …]} nennen wir je nach Richtung entweder

• Reduktion von w in t[w, …], und wir schreiben dafür t[\underline{w}_{↓}, …]σt[u, …], oder • Aufblasen von u in t[u, …], und wir schreiben dann t[\underline{u}_{↑}, …]σt[w, …].

• Wenn das Ergebnis wσu durch Kombination der zwei vorigen entsteht, dann bezeichnen wir das partielle Einsetzen von u für w mit t[\underline{w}, …]σt[u, …].

Beweis durch vollständige Induktion über n:

Der Fall n = 0 ist klar.

Mit der Definition von a_{n} und der Induktionsannahme gilt aσab_{n}:

a_{n+1} =^{Def.} \underline{a}b′_{n}b_{n}
a_{n+1} σ a\underline{b_{n}b′_{n}b_{n}}_{↓}
σ \underline{ab_{n}}
σ a

Bemerkung: Es ist naheliegend, zunächst zu versuchen, nur mit einer ausgezeichneten Regel zu arbeiten, etwa nur mit der Reduktion. Das Beispiel zeigt aber, daß manche Äquivalenzen in dieser Weise nicht herzuleiten sind. Graphisch bedeutet die Reduktion, daß ein Teil der Form

u  u u

durch

u  B

ersetzt wird. Im vorigen Abschnitt wurde die graphische Darstellung des Elements x(x′x)′x′x angegeben, also a_{1} mit der Variable x als Element a. Das obige Muster liegt für keine der drei gestrichelten Linien vor. Für die oberste und die untere rechts fehlt nämlich ein x auf der linken Seite, und für die untere Linie links fehlt ein x′ auf der linken Seite.

Hilfskonstruktionen für die Erweiterung der Signatur

Polynomiale Algebren und ähnliche Strukturen bieten sich als Möglichkeit an, um Erweiterungen zu konstruieren. Sie stehen sogar im Mittelpunkt der Konstruktion, wenn man diese als Verfahren analysieren will. In diesem Rahmen werden manche Beweise klarer, weil sie sich aus einfachen Eigenschaften der polynomialen Algebren ergeben.

2.1 Polynomiale Algebren

2.1.1 Definition

Motivation: In dem vierten Abschnitt des ersten Kapitels in [LN73] werden sogenannte polynomiale Algebren konstruiert. Wir gehen von der dort angegebenen Definition aus, und wollen eine Charakterisierung der polynomialen Algebren aufstellen. Es stellt sich heraus, daß die polynomialen Algebren durch eine universelle Eigenschaft charakterisiert sind (und folglich, daß sie nur bis auf Isomorphie in der Varietät definiert sind). Wir weisen zunächst auf Eigenschaften hin, die sich aus der Konstruktion der polynomialen Algebren ergeben. Dann zeigen wir, daß alle Algebren, die diese Bedingungen erfüllen, eigentlich isomorph zu der Konstruktion sind.

Notwendige Bedingungen für die Konstruktion

Gegeben seien eine Varietät 𝔅, eine Algebra A der Varietät 𝔅 und eine Variablenmenge X. Die polynomiale Algebra A(X, 𝔅) wird mittels Faktorisierung durch eine Kongruenzrelation in der Termalgebra über A ∪ X (hier: Grundmenge von A) konstruiert. In der Proposition 4.11 in [LN73] werden folgende Eigenschaften für A(X, 𝔅) formuliert: Es ist A(X, 𝔅) eine Algebra aus 𝔅, A eine Unteralgebra von A(X, 𝔅) und A(X, 𝔅) wird von A ⊎ X erzeugt. Ein Ergebnis über die Eindeutigkeit der Darstellung der Elemente in A(X, 𝔅) wird in Proposition 4.21 gegeben: Falls |A| = 1 und 𝔅 halbausgeartet^{1}, dann werden alle Elemente von A ∪ X in A(X, 𝔅) identifiziert. Sonst sind die Elemente alle verschieden.

Satz 2.1 (Bilanz) Falls die Elemente von A∪X in A(X, 𝔅) verschieden sind, erhalten wir zwei Einbettungen in \underline{Set} und \underline{𝔅}:

ι_{X}: X ↪ A(X, 𝔅)
x ↦ x ∈ A(X, 𝔅)

und

ι_{A}: A ↪ A(X, 𝔅)
a ↦ a ∈ A(X, 𝔅) .

Bemerkung: In der Tat ist für die Einbettung in \underline{Set} die Grundmenge der Algebra A(X, 𝔅) als Zielmenge der Abbildung gemeint, während für die Einbettung in \underline{𝔅} die Algebra selbst das Ziel des Homomorphismus ist. Konvention: der Lesbarkeit halber schreiben wir keinen Vergißfunktor. So entsteht ein gemischtes Diagramm (den Begriff werden wir in 2.2.1 systematischer definieren). Die linke Hälfte des Diagramms ist in \underline{Set} und die rechte Hälfte in \underline{𝔅} zu lesen. Wir schreiben also:

1𝔅 ist halbausgeartet, genau dann wenn keine Algebra A von 𝔅 mit Ordnung ungleich 1 eine Unteralgebra der Ordnung 1 enthält.

\underline{Set} ⋆ \underline{𝔅} ; [figure: X; ⊂; ι_{X}; A(X, 𝔅); ι_{A} ^{⊃}; A] statt

[figure: \underline{Set}; X; ⊂; ι_{X}; V(A(X, 𝔅)); und; \underline{𝔅}; A(X, 𝔅); ι_{A}  ^{⊃}; A]

Behauptung 2 Sei eine Algebra H der Varietät 𝔅, mit einem Homomorphismus h_{A} in 𝔅 und einer Abbildung h_{X}, in Zeichen:

\underline{Set} ⋆ \underline{𝔅} ; [figure: X; h_{X}; H; h_{A}; A] ,

dann existiert ein eindeutiger Homomorphismus A(X, 𝔅) ^{h}^{}H in 𝔅, der h_{A} und h_{X} auf A(X, 𝔅) fortsetzt.

Beweis Die Fortsetzung existiert, weil A(X, 𝔅) durch A ⊎ X erzeugt wird, und die Eindeutigkeit liegt vor, weil die Werte schon durch h_{A}, h_{X} bestimmt sind und die Einbettungen ι_{A} und ι_{X} injektiv sind.

Bemerkung: Die Bedingung der homomorphen Fortsetzung bedeutet, daß das folgende gemischte Diagramm kommutiert (die zwei Hälften kommutieren im üblichen Sinne):

\underline{Set} ⋆ \underline{𝔅} ; [figure: X; ⊂; ι_{X}; A(X, 𝔅); ι_{A} ^{⊃}; A; H; . . . . . . . . .; h; h_{A}; h_{X}] kommutiert, das heißt

[figure: \underline{Set}; X; ⊂; ι_{X}; V(A(X, 𝔅)); VH; . . . . . . . . .; Vh; h_{X}; kommutiert , sowie; \underline{𝔅}; A(X, 𝔅); ι_{A}  ^{⊃}; A; H; . . . . . . . . .; h; h_{A}; .]

Charakterisierung mit einer universellen Eigenschaft Sei umgekehrt eine Algebra A′ der Varietät 𝔅, zusammen mit einem Homomorphismus i_{A} in 𝔅 und einer Abbildung i_{X}: \underline{Set} ⋆ \underline{𝔅} ; [figure: X; i_{X}; A′; i_{A}; A] , so daß zu jeder Algebra H und jeder Abbildung h_{X} bzw. jedem Homomorphismus h_{A} in 𝔅 der Form \underline{Set} ⋆ \underline{𝔅} ; [figure: X; h_{X}; H; h_{A}; A] , eine eindeutige homomorphe Fortsetzung A′ ^{h}^{}H in 𝔅 existiert mit

\underline{Set} ⋆ \underline{𝔅} ; [figure: X; i_{X}; A′; i_{A}; A; H; . . . . . . . . .; h; h_{A}; h_{X}] , dann gilt A′ ≅ A(X, 𝔅).

Das Einsetzen von X ^{i_{X}}^{}A′ ^{}^{i_{A}} A bzw. X ^{⊂} ^{ι_{X}}^{}A(X, 𝔅) ^{}^{ι_{A}} ^{⊃} A anstelle von X ^{h_{X}}^{}H ^{}^{h_{A}} A in das Diagramm für A(X, 𝔅) bzw. A′ liefert das Gewünschte.

Satz 2.2 (Bilanz für die Definition) Es ist A(X, 𝔅) bis auf Isomorphie durch folgende universelle Eigenschaft eindeutig bestimmt:

Für alle \underline{Set} ⋆ \underline{𝔅} ; [figure: X; h_{X}; H; h_{A}; A] existiert ein eindeutiger Homomor-

phismus A(X, 𝔅) ^{h}^{}H, so daß folgendes Diagramm kommutiert. \underline{Set} ⋆ \underline{𝔅}

[figure: X; ⊂; ι_{X}; A(X, 𝔅); ι_{A} ^{⊃}; A; H; . . . . . . . . .; h; h_{A}; h_{X}]

2.1.2 Eigenschaften

Das Theorem 4.6 in [LN73] besagt, daß A(X, 𝔅) ≅ (A(Y, 𝔅))(Z, 𝔅), falls X = Y ⊎ Z. Daraus folgt insbesondere:

Korollar 1 1.

Für S_{n} = ⨄_{k=0...n} X_{k} gilt: A(X, 𝔅) ≅ ((A(X_{n}, 𝔅))(X_{n−1}, 𝔅) …)(X_{0}, 𝔅).

2. Für Y ⊆ X kommutiert das folgende Diagramm. \underline{Set} ⋆ \underline{𝔅}

[figure: Y; ⊂; ι_{Y}; A(Y, 𝔅); ⊃; A; X; ∩; ⊂; ι_{X}; A(X, 𝔅); ∩; ⊃]

Bemerkung:

1. Allgemeiner gilt: Für Algebren A_{1}, A_{2} der Varietät 𝔅 mit einem Homomorphismus A_{1} ^{h_{A}}^{}A_{2} in 𝔅 und Mengen X_{1}, X_{2} mit einer Abbildung X_{1} ^{h_{X}}^{}X_{2} existiert ein eindeutiger Homomorphismus A_{1}(X_{1}, 𝔅) ^{h}^{}A_{2}(X_{2}, 𝔅) in 𝔅, so daß das folgende gemischte Diagramm kommutiert.

\underline{Set} ⋆ \underline{𝔅}

[figure: X_{1}; ⊂; ι_{X_{1}}; A_{1}(X_{1}, 𝔅); ι_{A_{1}}  ^{⊃}; A_{1}; X_{2}; h_{X}; ⊂; ι_{X_{2}}; A_{2}(X_{2}, 𝔅); . . . . . . . . .; h; ι_{A_{2}}  ^{⊃}; A_{2}; h_{A}]

Es ist h durch (h_{X}, h_{A}) eindeutig bestimmt. Die Zuordnung (mit den obigen Notationen)

P: \underline{Set} × \underline{𝔅} → \underline{𝔅}
(X; A) ↦ A(X, 𝔅)
(h_{X}; h_{A}) ↦ h

ist funktoriell, denn sie respektiert die Identitäten und die Verkettung (klar).

2. Freie Algebren in 𝔅 sind Spezialfälle von polynomialen Algebren: Sei O die freie Algebra in 𝔅 über ∅, also das initiale Objekt in 𝔅. Für eine Menge X ist die polynomiale Algebra O(X, 𝔅) die freie Algebra in 𝔅 über X (es gilt insbesondere O(∅, 𝔅) ≅ O). Die universelle Eigenschaft für die freien Algebren drückt man üblicherweise auch mit kommutierenden Diagrammen aus:

Zu jedem h existiert ein eindeutiges h^{+}, so daß das Diagramm kommutiert:

[figure: \underline{Set}; X; VH; h; \underline{𝔅}; FX; H; . . . . . . . . .; h^{+}; \underline{Set}; X; ⊂; η_{X}; VFX; VH; Vh^{+}; h]

Äquivalent dazu ist das folgende gemischte Diagramm.

\underline{Set} ⋆ \underline{𝔅}

[figure: X; ⊂; ι_{X}; O(X, 𝔅); ι_{O} ^{⊃}; O; H; . . . . . . . . .; h^{+}; h_{O}; h_{X}]

Die Bedingungen über den Pfeilen von dem initialen Objekt O aus sind nämlich immer erfüllt. Überleitung: In der Tat bestehen solche Zusammenhänge, weil diese universellen Eigenschaften einfach bedeuten, daß bestimmte Funktoren adjungiert sind. Das wollen wir im nächsten Abschnitt mit den gemischten Coprodukten beschreiben.

2.2 Gemischte Coprodukte

Motivation: Die polynomialen Algebren sind ein Spezialfall von “gemischten Coprodukten“. Wir haben eine Menge mit einer Algebra einer Varietät verknüpft, um eine neue Algebra zu gewinnen. Die neue Algebra sollte einer gewissen universellen Eigenschaft genügen. Diese universelle Eigenschaft läßt sich aber mit Hilfe von adjungierten Funktoren ”leicht“ beschreiben und diese Vorgehensweise weist darauf hin, wie die neuen Objekte zu konstruieren sind. Wie angekündigt führen wir zunächst eine Schreibweise systematischer ein, die uns erlaubt, zwei bestimmte Diagramme in einem einzigen zusammenzufassen: das gemischte Diagramm.

2.2.1 Gemischte Diagramme

Angenommen, wir haben drei Kategorien \underline{C}, \underline{C_{1}}, \underline{C_{2}} und zwei Vergißfunktoren V_{1} bzw. V_{2} von \underline{C}, die wir die Hauptkategorie nennen, nach \underline{C}_{1} bzw. \underline{C_{2}}:

C_1^{V1} C^{V2} C_2

Die Idee der gemischten Diagramme besteht darin, daß man die Vergißfunktoren nicht mehr hinschreibt. Dafür ist für beide Kategorien \underline{C_{1}} und \underline{C_{2}} jeweils eine Hälfte des Diagramms reserviert. Ganz oben werden die Kategorien angegeben: \underline{C_{1}} wird links eingetragen, \underline{C_{2}} rechts und die Hauptkategorie \underline{C} in die Mitte (die Pfeile symbolisieren die Vergißfunktoren).

\underline{C_{1}} ← \underline{C} → \underline{C_{2}}

\underline{C_{1}}  \underline{C}  \underline{C_{2}}

Objekte und Pfeile auf der linken Seite gehören zu C_{1}, die auf der rechten Seite zu C_{2} und die in der Mitte zu C. Pfeile von der Mitte weg oder auf die Mitte zu gehören zu C_{i}, wobei auf die Objekte von C der Vergißfunktor (implizit) angewendet wird. Ein gemischtes Diagramm kommutiert, wenn seine zwei Hälften jeweils kommutieren (im üblichen Sinne). Konvention: in allen Diagrammen werden (implizit) alle Dreiecke kommutierend vorausgesetzt.

Beispielsweise schreiben wir: \underline{C_{1}} ← \underline{C} → \underline{C_{2}} ; [figure: C_{1}; ι_{1}; C; ι_{2}; C_{2}; C′; f; f_{2}; f_{1}] (kommutiert)

für:

[figure: \underline{C_{1}}; C_{1}; ι_{1}; V_{1}C; V_{1}C′; V_{1}f; f_{1}; und; \underline{C_{2}}; V_{2}C; ι_{2}; C_{2}; V_{2}C′; V_{2}f; f_{2}; (kommutieren).]

2.2.2 Gemischte Coprodukte

Mit δ bezeichnen wir den Diagonalfunktor δ: \underline{C} → \underline{C × C}. Wir geben drei äquivalente Formulierungen der Eigenschaft, die die gemischten Coprodukte charakterisieren soll:

1. Wir wollen jedem Paar (A_{1}; A_{2}) der Kategorie \underline{C_{1} × C_{2}} ein Objekt A_{1} ∗A_{2} in der Hauptkategorie \underline{C} zusammen mit einem Paar von Pfeilen (ι_{1}; ι_{2}) in \underline{C_{1} × C_{2}} zuordnen, wobei A_{i} ^{ι_{i}}^{}V_{i}(A_{1}∗A_{2}) für i = 1, 2; oder,

mit der gemischten Schreibweise: \underline{C_{1}} ← \underline{C} → \underline{C_{2}} ; [figure: A_{1}; ι_{1}; A_{1} ∗ A_{2}; ι_{2}; A_{2}] , so

daß Folgendes gilt:

Zu jedem Objekt H in \underline{C} mit Pfeilen h_{i} in \underline{C_{i}} für i = 1, 2, in Zeichen

\underline{C_{1}} ← \underline{C} → \underline{C_{2}} ; [figure: A_{1}; h_{1}; H; h_{2}; A_{2}] , gibt es einen eindeutigen Morphismus h von A_{1} ∗ A_{2} nach H in \underline{C}, der das Diagramm kommutieren läßt:

\underline{C_{1}} ← \underline{C} → \underline{C_{2}}

[figure: A_{1}; ι_{1}; A_{1} ∗ A_{2}; ι_{2}; A_{2}; H; . . . . . . . . .; h; h_{2}; h_{1}]

2. Wir wollen jedem Paar (A_{1}; A_{2}) der Kategorie \underline{C_{1} × C_{2}} ”das“ initiale Objekt in der Kommakategorie ((A_{1}; A_{2}) ↓ V_{1} × V_{2} ∘ δ) zuordnen.

3. Wir wollen jedem Paar (A_{1}; A_{2}) der Kategorie \underline{C_{1} × C_{2}} den universellen Pfeil (ι_{1}; ι_{2}) von (A_{1}; A_{2}) nach dem Funktor (V_{1} × V_{2}) ∘ δ zuordnen.

Satz 2.3 (und Definition) Mit den obigen Notationen, existiert ein —bis auf Isomorphie in \underline{C}— eindeutiges Objekt A_{1} ∗ A_{2} (zusammen mit den Pfeilen ι_{1}, ι_{2}), und wir nennen es das gemischte Produkt von A_{1} und A_{2}.

Beweis Zur Existenz:

Wir suchen einen universellen Pfeil (ι_{1}; ι_{2}) von (A_{1}; A_{2}) nach dem Funktor (V_{1} × V_{2}) ∘ δ. Idee: den Funktor V_{1} × V_{2} ∘ δ in mehreren Schritten ”behandeln“. Die Einzelteile 1. und 3. befinden sich sogar in einer Tabelle in [ML72] (IV Adjungierte Funktoren, 2. Beispiele für Adjungierte).

1. Schritt: Angenommen, V_{1} bzw. V_{2} hat einen linksadjungierten Funktor F_{1} bzw. F_{2}, dann ist A_{i} ^{}(V_{i} ∘ F_{i})A_{i} initial in (A_{i} ↓ V_{i}).

2. Schritt: Der Funktor F_{1} × F_{2} ist linksadjungiert zu V_{1} × V_{2}, es ist also

(A_{1}; A_{2}) ^{}((V_{1} × V_{2}) ∘ (F_{1} × F_{2}))(A_{1}; A_{2})

initial in ((A_{1}; A_{2}) ↓ V_{1} × V_{2}).

3. Schritt: Das initiale Objekt in ((C_{1}; C_{2}) ↓ δ) ist auch wohl bekannt: es ist das Coprodukt C_{1} ⨿ C_{2} von C_{1} und C_{2}.

Die Bezeichnung ⨿ steht für den Bifunktor von \underline{C × C} nach \underline{C}, der einem Paar (C_{1}; C_{2}) die Spitze seines Coprodukts C_{1} ⨿ C_{2} zuordnet.

\underline{C_{1}} ← \underline{C} → \underline{C_{2}}

[figure: A; A ⨿ B; B; A′; a; A′ ⨿ B′; a ⨿ b; B′; b]

4. Schritt:

jetzt werden die Teile zusammengesetzt: ein Kandidat für das initiale Objekt in ((A_{1}; A_{2}) ↓ V_{1}×V_{2}∘δ) ist das Coprodukt von F_{1}A_{1} und F_{2}A_{2}.

Behauptung 3 Der Funktor ⨿ ∘ (F_{1} × F_{2}) ist linksadjungiert zum Funktor (V_{1} × V_{2}) ∘ δ.

Begründung:

Die Verkettung von linksadjungierten Funktoren ist (bis auf natürliche Isomorphie) der Linksadjungierte der Verkettung der Funktoren.

Bemerkung: 1. Zu den Namen ”gemischtes Coprodukt“ und ”gemischtes Diagramm“: Wenn man nur in der Hauptkategorie arbeitet, so hat man tatsächlich die üblichen Coprodukte und die gemischten Diagramme sind übliche Diagramme.

2. Die polynomialen Algebren über einer Varietät 𝔅 sind spezielle gemischte Coprodukte für \underline{C} := \underline{C_{1}} := \underline{𝔅} und \underline{C_{2}} := \underline{Set}.

3. Die Hauptkategorie habe endliche Coprodukte und sie sei Quelle von Funktoren V_{i}, i = 1, …, n mit Linksadjungierten F_{i}, i = 1, …, n. Dann existieren gemischte Coprodukte und man erhält sie über die Linksadjungierten: ⨿_{n} ∘ (F_{1} × ⋯ × F_{n}) zu (V_{1} × ⋯ × V_{n}) ∘ δ_{n}. Linksadjungierbare Funktoren sind abgeschlossen unter Verkettung und ”verträglich“ mit der Produktkategorie. Beispiel: 1. Die polynomialen Algebren über \underline{Mon} lassen sich also mit einem Funktor P_{Mon} beschrieben.

\begin{matrix}P_{Mon}: \underline{Mon × Set} & → & \underline{Mon} \\ (M; X) & ↦ & M[X] := M ⨿_{Mon} X^{∗} \end{matrix}

Der Funktor P_{Mon} ergibt sich aus der Verkettung folgender Funktoren:

1. Coproduktbildung in \underline{Mon},

2. Adjunktion eines neutralen Elements (Linksadjungierter des Vergißfunktors von \underline{Mon} nach \underline{Hbgr}),

3. Bildung der freien Halbgruppen (nichtleere Listen).

2. Adjunktion eines neutralen Elements: Offensichtlich wird eine beliebige Halbgruppe S zu einem Monoid S_{λ} , wenn man ein neues Element λ als neutrales Element hinzunimmt und die Definition der assoziativen Verkettung für λ entsprechend erweitert. Die Morphismen in \underline{Hbgr} werden auch zu Morphismen in \underline{Mon} gemacht, indem das neutrale Element auf das neutrale Element abgebildet wird.

Behauptung 4 Diese Zuordnung definiert einen Funktor −_{λ}, der Linksadjungierter zum Vergißfunktor von \underline{Mon} nach \underline{Hbgr} ist (die eindeutige homomorphe Fortsetzung der Halbgruppen-Morphismen ist klar).

Wir haben also folgendes Diagramm für die Linksadjungierten zu den Vergißfunktoren:

\underline{Mon}

[figure: \underline{Hbgr}; −_{λ}; \underline{Mon}; Id]

[figure: \underline{Set}; F; −^{∗}]

Wir bezeichnen das gemischte Coprodukt einer Halbgruppe S und eines Monoids M mit S ⋆ M.

Satz 2.4 (Bilanz für die Beispiele) Für eine Menge Y und ein Monoid M gilt folgende Isomorphie in \underline{Mon}: F(Y) ⋆ M ≅ M[Y] ≅ M ⨿_{Mon} Y^{∗}.

2.3 Konkrete Konstruktionen

2.3.1 Binäres Coprodukt von Monoiden

Wir geben zunächst eine Konstruktion von A ⨿_{Mon} B für beliebige Monoide A und B an. Die Rolle der Monoide A und B sind natürlich symmetrisch (man lese etwa die Elemente in der Grundmenge von rechts nach links). Die Grundmenge besteht aus den Elementen der Länge k für alle k ≥ 0: (A^{−} steht für A \ {λ}). Die Menge der Elemente der Länge 0 ist A × B. Die Menge der Elemente der Länge k (k ≥ 1) ist

A × \underbrace{(B^{−} × A^{−}) × ⋯ × (B^{−} × A^{−})}_{k} ×B.

Die Länge eines Elements ist eindeutig bestimmt. Ein Element läßt sich also eindeutig als Tupel (a_{0}, (b_{1}, a_{1}), …, (b_{k}, a_{k}), b_{k+1}) schreiben (für k = 0: (a_{0}, b_{1})). Der Lesbarkeit halber lassen wir die Klammern weg und gehen davon aus, daß die Bestandteile in der Mitte alternierend aus B^{−} und A^{−} sind: a_{0}b_{1}a_{1} … b_{k}a_{k}b_{k+1}. Verkettung: Sei p = a_{0}b_{1}a_{1} … b_{k}a_{k}b_{k+1}, und q = c_{0}d_{1}c_{1} … d_{l}c_{l}d_{l+1}. Den Anfang von p bezeichnen wir mit u := a_{0}b_{1}a_{1} … b_{k}, und das Ende von q mit v := c_{1} … d_{l}c_{l}d_{l+1}; es ist also: p = ua_{k}b_{k+1} und q = c_{0}d_{1}v. Konvention: der Teil u bzw v entfällt, falls k = 0, bzw l = 0. So kann man die Fälle, bei denen die Rekursion hält, formal wie die anderen angeben. Das Prinzip der Verkettung ist das Zusammenfassen der Bestandteile, solange (Rekursion …) sie in demselben Monoid liegen, und das Weglassen der neutralen Elemente.

p ∘ (λ_{A}, λ_{B}) := p
(λ_{A}, λ_{B}) ∘ p := p.

p ∘ q := \{ \begin{matrix}ua_{k}b_{k+1}c_{0}d_{1}v & falls b_{k+1} ≠ λ_{B} und c_{0} ≠ λ_{A} & (a) \\ u(a_{k} ∘_{A} c_{0})d_{1}v & falls b_{k+1} = λ_{B} und a_{k} ∘_{A} c_{0} ≠ λ_{A} & (b) \\ u ∘ (λ_{A}d_{1}v) & falls b_{k+1} = λ_{B} und a_{k} ∘_{A} c_{0} = λ_{A} & (c) \\ ua_{k}(b_{k+1} ∘_{B} d_{1})v & falls c_{0} = λ_{A} und b_{k+1} ∘_{B} d_{1} ≠ λ_{B} & (d) \\ (ua_{k}λ_{B}) ∘ v & falls c_{0} = λ_{A} und b_{k+1} ∘_{B} d_{1} = λ_{B} & (e) \end{matrix}

Diese Verkettung ist wohldefiniert:

* alle Fälle sind abgedeckt,

* die Rekursion terminiert,

* die Eindeutigkeit liegt vor, auch wenn mehrere Regeln anwendbar sind,

* sie liefert ein Element der Grundmenge (Fallunterscheidung!). Die Verkettung ist assoziativ und hat (λ_{A}, λ_{B}) als neutrales Element. Wegen der Rekursion ist der Beweis der Wohldefiniertheit und der Assoziativität der Verkettung aufwendig, man kann ähnlich wie Polák in [Pol89] vorgehen und induktiv über die Länge eine schwächere Variante der Assoziativität zeigen. Im Laufe des Induktionsbeweises zeigt man Folgendes (die Regel (a) ist stets anwendbar):

Behauptung 5 Jedes Element wird durch Verkettung seiner Bestandteile erzeugt, es gilt:

p = a_{0}b_{1}a_{1} … b_{k}a_{k}b_{k+1} = a_{0} ∘ b_{1} ∘ a_{1} ⋯ ∘ b_{k} ∘ a_{k} ∘ b_{k+1}.

Somit ist A ⨿_{Mon} B ein Monoid. Einbettungen: Man prüft nach, daß die Zuordnung a ↦ (a, λ_{B}) bzw. b ↦ (λ_{A}, b) Einbettungen in \underline{Mon} definiert:

ι_{A}: A ↪ A ⨿_{Mon} B
ι_{B}: B ↪ A ⨿_{Mon} B

Satz 2.5 (Eindeutige homomorphe Fortsetzung) Zu beliebigen Pfeilen A ^{h_{A}}^{}H und B ^{h_{B}}^{}H gibt es einen eindeutigen Morphismus h: A ⨿ B ^{}H, so daß das Diagramm kommutiert.

[figure: A; ⊂; ι_{A}; A ⨿ B; ι_{B} ^{⊃}; B; H; . . . . . . . . . .; h; h_{B}; h_{A}]

Beweis Die Fortsetzung der Homomorphismen definiert man nach der obigen Behauptung:

h(p) = h_{A}(a_{0}) ∘ h_{B}(b_{1}) ∘ h_{A}(a_{1}) ⋯ ∘ h_{B}(b_{k}) ∘ h_{A}(a_{k}) ∘ h_{B}(b_{k+1}).

Die Abbildung h ist wohldefiniert wegen der Eindeutigkeit der Darstellung der Elemente in A ⨿_{Mon} B. Sie ist mit jeder Regel der Definition der Verkettung verträglich, also ist h ein Morphismus. Die Eindeutigkeit der Fortsetzung liegt vor, weil der Morphismus durch die Werte für die Bestandteile schon überall definiert ist.

2.3.2 Gemischtes Coprodukt einer Halbgruppe und eines Monoids

Wir haben bereits: S ⋆ M ≅ S_{λ} ⨿ M. In der Grundmenge ändert man folgenderweise die Darstellung und die Definition der Länge der Elemente: Mit der vorigen Schreibweise gilt S_{λ}^{−} = S. Man sieht leicht ein, daß die Mengen

M_{0} := ⨄_{k≥0} S_{λ} × \underbrace{(M^{−} × S) × ⋯ × (M^{−} × S)}_{k} ×M

und

M_{1} := M ∪ ⋃_{k≥0} M × \underbrace{(S × M^{−}) × ⋯ × (S × M^{−})}_{k} ×(S × M)

isomorph sind. Von M_{0} nach M_{1}:

p = s_{0}m_{1}s_{1} … m_{k}s_{k}m_{k+1} → i(p) := \{ \begin{matrix}λ_{M}s_{0}m_{1}s_{1} … m_{k}s_{k}m_{k+1} & falls s_{0} ≠ λ \\ m_{1}s_{1} … m_{k}s_{k}m_{k+1} & falls s_{0} = λ \end{matrix}

Von M_{1} nach M_{0} zurück: Wenn ein Element von M_{1} mit λ_{M} anfängt, dann wird das λ_{M} weggelassen, sonst fügt man ein λ am Anfang dazu. Wir nehmen M_{1} als Beschreibung der Grundmenge von S ⋆ M. Ein Element läßt sich also eindeutig schreiben als: m oder m_{0} \underbrace{s_{1}m_{1} … s_{k}m_{k}}_{nichts für k=0} s_{k+1}m_{k+1}. Da-

bei lassen wir wie vorher die Klammer weg und gehen davon aus, daß die Bestandteile alternierend aus M und S sind. In der Definition der Verkettung und der Einbettungen wird die neue Darstellung (also i(s) statt s für alle Elemente s ∈ S) eingesetzt: Sei p = m_{0}s_{1}m_{1} … s_{k}m_{k}, q = n_{0}t_{1}n_{1} … t_{l}n_{l} (für die Fälle p ∈ M oder Q ∈ M gibt es kein s, bzw. kein t). Die Regeln (c), (d), (e) der Definition der Verkettung treten nicht mehr auf. Es bleibt:

p ∘ λ_{M} := p
λ_{M} ∘ p := p

p ∘ q := \{ \begin{matrix}m_{0}s_{1}m_{1} … s_{k}(m_{k} ∘_{M} n_{0})t_{1}n_{1} … t_{l}n_{l} & falls m_{k} ∘_{M} n_{0} ≠ λ_{M} & (a) \\ m_{0}s_{1}m_{1} … (s_{k} ∘_{S} t_{1})n_{1} … t_{l}n_{l} & sonst (λ_{M} falls s und t leer) & (b) \end{matrix}

Die Einbettungen sind:

ι_{M}: M ↪ S ⋆ M
m ↦ m

bzw.

ι_{S}: S ↪ S ⋆ M
s ↦ (λ_{M}, s, λ_{M}).

2.3.3 Polynomiale Algebren über Monoiden

Wir wissen: F (Y) ⋆ M ≅ M[Y]. Wir gehen wie im letzten Abschnitt vor und ändern noch einmal die Beschreibung der Grundmenge, die Definition der Verkettung und die Einbettungen: Man überlegt sich leicht, daß

M ∪ ⋃_{k≥0} M × \underbrace{(Y × M) × ⋯ × (Y × M)}_{k}

auch die Grundmenge beschreibt. Ein Element läßt sich eindeutig schreiben als: m_{0} \underbrace{y_{1}m_{1} … y_{k}m_{k}}_{nichts für k=0}. Wir lassen wie immer die Klammer weg und gehen

davon aus, daß die Bestandteile alternierend aus M und Y sind. Sei p = m_{0}y_{1}m_{1} … y_{k}m_{k}, q = n_{0}z_{1}n_{1} … z_{l}n_{l}, die Verkettung von p und q wird mit Hilfe der folgenden Regeln definiert: Sei p = m_{0}y_{1}m_{1} … y_{k}m_{k}, q = n_{0}z_{1}n_{1} … z_{l}n_{l}, definiere:

p ∘ q := \{ \begin{matrix}(m_{0} ∘_{M} n_{0})z_{1}n_{1} … z_{l}n_{l} & falls k = 0 & (a) \\ m_{0}y_{1}m_{1} … y_{k}(m_{k} ∘_{M} n_{0}) & falls l = 0 & (b) \\ m_{0}y_{1}m_{1} … y_{k}(m_{k} ∘_{M} n_{0})z_{1}n_{1} … z_{l}n_{l} & sonst & (c) \end{matrix}

Die Einbettungen sind:

ι_{M}: M ↪ M[Y]
m ↦ m

bzw.

ι_{Y} : Y ↪ M[Y]
y ↦ (λ_{M}, y, λ_{M}).

2.4 Erweiterungen mit polynomialen Algebren

Wir schreiben kurz X^{f} für die freie Algebra über X in 𝔅 (das heißt: O(X, 𝔅)), und A[X] für A(X, 𝔅).

Wir definieren induktiv über n eine wachsende Folge (A_{n})_{n∈ℕ} von Algebren in 𝔅:

A_{0} := X^{f}
U_{0} := A_{0} \ ∅^{f}
A_{n+1} := A_{n}[U_{n}]
U_{n+1} := A_{n+1} \ A_{n}

Die Notationen für die Einbettungen sind aus dem Diagramm abzulesen: \underline{Set} ⋆ \underline{𝔅}

[figure: U_{n}; ⊂; ()′_{n}; A_{n}[U_{n}]; e_{n} ^{⊃}; A_{n}] Sei noch

S_{n} := X ⊎ ⨄_{k=0,...,n} U′_{k}

und

S := X ⊎ ⨄_{k≥0} U′_{k}.

Mit dem Korollar 1 erhalten wir:

A_{n+1} = A_{n}[U_{n}] = A_{n−1}[U_{n−1}][U_{n}] = ⋯ = A_{0}[U_{0}] … [U_{n}].

Mit A_{0} = X^{f} haben wir A_{n+1} = ∅^{f}[X][U_{0}] … [U_{n}], und somit folgenden Satz:

Satz 2.6 Es gilt A_{n+1} ≅ S_{n+1}^{f}.

Die Supremumbildung kann auch gleich untersucht werden.

Satz 2.7 Es gilt ⨆_{k≥0} A_{k} ≅ (⋃_{k≥0} S_{k})^{f} in 𝔅.

Beweis Es ist (−)^{f} Linksadjungierter des Vergißfunktor und ⋃_{k≥0} S_{k} Colimes in \underline{Set}. Mit dem Satz über die Vertauschbarkeit von Linksadjungierten und Colimites erhalten wir die Aussage.

Bemerkung: Formal sieht dieser Limesübergang auch so aus:

A_{n} = ⨆_{k≤n} A_{k} = ∅^{f}[X][U_{0}] … [U_{n−1}]

U = ⨆_{k≥0} A_{k} = ∅^{f}[X][U_{0}] … [U_{n}] …

Die freien unären Monoide

3.1 Ein Modell für die freien unären Monoide

Motivation: In diesem Abschnitt konstruieren wir ein Modell für die freien unären Monoide. Das Prinzip der Konstruktion ist aber allgemeiner und liefert eine Methode für die Signaturerweiterung.

3.1.1 Erzeugung der unären Monoide als Monoide

Motivation: Ein freies unäres Monoid U(X) über einer Variablenmenge X ist insbesondere ein unäres Monoid, das von X erzeugt wird. Wir bemerken auch gleich, daß U(X) das kleinste Untermonoid von U(X) ist, das X umfaßt und unter ′ abgeschlossen ist (die Gleichung λ′ = λ gilt ohnehin). Wir betrachten zunächst einmal allgemein das folgende Problem: Gegeben sei ein unäres Monoid U, das (nicht notwendigerweise frei) von einer Menge E erzeugt wird, in Zeichen: U =< E >\underline{unMon}. Gesucht ist ein Verfahren, das eine Menge E′ liefert, die U als Monoid erzeugt, in Zeichen: U =< E′ >\underline{Mon} (in dem Rest des Abschnitts lassen wir diesen Index weg und schreiben einfach U =< E′ >). Man versucht in der Tat, den Verlust an Struktur durch eine Vergrößerung der Erzeugermenge auszugleichen. Dann wenden wir dieses Verfahren auf den Fall an, in dem U frei über X ist: wir bekommen eine Erzeugermenge S, die den Schlüssel für die Konstruktion von U liefert.

Zerlegung

Sei U ein unäres Monoid, das von einer Menge E erzeugt wird. Nun wird induktiv U als Monoid zerlegt und die Tiefe der Elemente definiert. Bemerkung: Das Verfahren wird stationär, falls eines der U_{n} leer ist. Das geschieht schon beim ersten Schritt, wenn die Erzeugermenge leer ist. Dann besteht das von ∅ erzeugte unäre Monoid nur aus dem neutralen Element (dieses ist offensichtlich das freie unäre Monoid über ∅).

△ Induktionsanfang Wir definieren, welche Elemente die Tiefe 0 haben. Sei V_{0}, das von E erzeugte Untermonoid, in Zeichen also: V_{0} :=< E >. Die Menge der Elemente der Tiefe 0 sei U_{0} := V_{0} \ {λ}; die (einzige) Konstante λ bekommt die Tiefe −∞. Somit besteht V_{0} aus den Elementen der Tiefe ≤ 0. △ Induktionsschritt Wir nehmen an, die Elemente der Tiefe ≤ n sind schon definiert, und geben an, welche die Tiefe n + 1 haben. Setze V_{n+1} :=< V_{n} ∪ U′_{n} >. Die Menge der Elemente der Tiefe n + 1 sei U_{n+1} := V_{n+1} \ V_{n}: das sind die Elemente, die nicht ohne U′_{n} erzeugt werden können. Per Definition gilt insbesondere U′_{n} ⊂ V_{n+1}. V_{n+1} besteht aus den Elementen der Tiefe ≤ n + 1. △ Supremumbildung Das Supremum der Folge (V_{n})_{n∈ℕ} ist wohldefiniert, da die Folge wachsend ist, und das folgende Lemma gilt.

Lemma 2 Für n ≥ 0 gilt:

V_{n+1} =< E ∪ ⋃_{0≤k≤n} U′_{k} >= ⋃_{0≤k≤n+1} U_{k} ∪ {λ}  (3.1)

U = ⋃_{k≥0} U_{k} ∪ {λ}  (3.2)

U  V_{n+1} V_{n} U_{1} U_{0} U_{n} ⋮{λ} U′_{n}  ⋮U_{n+1}

Abbildung 3.1: Zerlegung eines unäres Monoids U

U ist Cokegel des Folgenfunktor der Folge (V_{n})_{n∈ℕ}

Beweis Zu 3.1: Induktion.

Zu 3.2:

Die Menge ⋃_{k≥0} U_{k} ∪ {λ} ist ein Untermonoid von U, das unter ′ abgeschlossen ist und E umfaßt. Also muß sie nach der Definition von ”erzeugt als unäres Monoid“ gleich U sein. Die Einbettungen von den V_{n} nach U kommutieren. Sie bilden die Kanten eines Cokegels mit Spitze U.

Die Mengen {λ} und U_{n} (für n ≥ 0) sind paarweise disjunkt, so daß die Tiefe als Funktion tiefe wohldefiniert ist. Unter bestimmten Voraussetzungen, die wir als nächstes betrachten, ist die Funktion tiefe ein Monoid-Homomorphismus …

Rolle der Tiefe

Wir konstruieren ein unäres Monoid 𝔗, das mit der Tiefe zusammenhängt.

Definition 2 (𝔗) Die Grundmenge von 𝔗 ist {−∞} ∪ ℕ. Die assoziative Verknüpfung ist das Supremum mit −∞ als neutrales Element. Die einstellige Operation ′ wirkt wie die Nachfolgerfunktion für die natürlichen Zahlen und man definiert −∞′ := −∞.

Bemerkung: (Einige Eigenschaften des Monoids 𝔗)

1. Offensichtlich ist 𝔗 kommutativ.

2. Linearität: Die Operation′ ist linear bezüglich der Verknüpfung (das heißt: (a∘b)′ = a′∘b′ für a, b ∈ 𝔗). Wir nennen ein unäres Monoid linear, wenn die Operation′ diese Eigenschaft hat. Da die Linearität mit einer Gleichung definiert werden kann, bilden die linearen unären Monoide eine Untervarietät der Varietät der unären Monoide, \underline{lunMon} ist also eine volle Unterkategorie von \underline{unMon}. Ist U(X) frei, so existiert ein eindeutiger Homomorphismus U(X) ^{}𝔗, der die Nullabbildung von X nach 𝔗 auf U(X) fortsetzt und dieser ist gerade wie die Funktion tiefe definiert, die man durch die Zerlegung des freien unären Monoid über X mit X als Erzeugermenge erhält

tiefe : U(X) → 𝔗
λ ↦ −∞
u ∈ U_{n} ↦ n .

Eigentlich hängt der Morphismus tiefe von der Erzeugermenge ab, das heißt daß man einen Morphismus tiefe_{X} für jede Erzeugermenge X definieren sollte. Für die leere Menge ist tiefe_{∅} konstant (mit Wert neutrales Element), sonst ist tiefe_{X} surjektiv. Seien X, Y Mengen mit X ⊆ Y, dann existiert ein eindeutiger Morphismus f von U(X) nach U(Y) mit f(x) = x für x ∈ X. Es gilt tiefe_{X} = tiefe_{Y} ∘ f.

Dies liefert einen Cokegel über den freien unären Monoiden:

[figure: U(∅); ⊂; U(X); ⊂; f; U(Y); ⋯]

[figure: 𝔗; ^{tiefe^{X}}; tiefe_{Y}]

3.1.2 Ein Modell für die freien unären Monoide

Konstruktion

Wir konstruieren induktiv eine wachsende Folge von Monoiden (V_{n})_{n∈ℕ}, das heißt einen Folgenfunktor:

U: \underline{ω} → \underline{Mon}
n ↦ V_{n}

△ Induktionsanfang Wir konstruieren die Elemente der Tiefe ≤ 0. Setze V_{0} := X^{∗} für die Grundmenge sowie für die assoziative Verknüpfung · und das neutrale Element λ. Sei U_{0} := V_{0} \ {λ} die Menge der Elemente der Tiefe 0. Die Tiefe von λ wird gleich −∞ gesetzt. Da {λ} und U_{0} disjunkt sind, ist die Tiefe eindeutig bestimmt. △ Induktionsschritt Wir nehmen an, wir haben die Approximationen bis zum Rang n folgenderweise definiert: Wir haben paarweise disjunkte Mengen U_{k} (für k ≤ n), deren Vereinigung mit einer neuen Konstante λ die Grundmenge eines Monoids V_{n} ist:

V_{n} = {λ} ∪ ⋃_{0≤k≤n} U_{k}

und es ist V_{n} = S_{n}^{∗}, mit

S_{n} := X ∪ ⋃_{0≤k≤n−1} U′_{k}.

Wir konstruieren eine Erweiterung V_{n+1} von V_{n}. Sei V_{n+1} := V_{n}[U_{n}] (siehe gemischte Coprodukte). Das Monoid V_{n} läßt sich mit e_{n} und die Menge U_{n} mit ()′_{n} in V_{n+1} einbetten:

\underline{Set} ⋆ \underline{Mon}

[figure: U_{n}; ⊂; ()′_{n}; V_{n}[U_{n}]; e_{n} ^{⊃}; V_{n}] Setze U_{n+1} := V_{n+1} \ V_{n} (das sind die neuen Elemente, die nicht ohne U′_{n} erzeugt werden können, sie haben die Tiefe n+1). V_{n+1} besteht aus Elementen der Tiefe ≤ n + 1. Nach dem Satz 2.6 im Abschnitt 2.4 gilt V_{n+1} = S_{n+1}^{∗}, wobei S_{n+1} := S_{n} ∪U′_{n}. △ Supremumbildung Der Abschnitt 2.4 liefert auch die Konstruktion für U als Colimes des Folgenfunktors der Folge (V_{n})_{n∈ℕ}. Nach dem Satz 2.7 ist U das freie Monoid über S, mit S := ⋃_{n≥0} S_{n}. Definiert man noch λ′ := λ, dann ist U ein unäres Monoid.

Satz 3.1 U ist das freie unäre Monoid über X.

Ein ähnlicher Beweis wird im nächsten Abschnitt geführt.

Bilanz für das Wortproblem

Wie sind nun imstande, das graphische Modell von 1.3.2 zu rechtfertigen. Mit der konkreten Konstruktion der polynomialen Algebren über Monoiden können wir die Darstellung der Elemente von U angeben. Es ist

U_{0} := ⨄_{k≥0}{x_{1} ⋯ x_{k+1}|x_{i} ∈ X}

U_{n+1} := ⨄_{k≥1} {v_{1}u′_{1}v_{2} ⋯ v_{k}u′_{k}v_{k+1}|v_{i} ∈ V_{n}, u_{i} ∈ U_{n}}

Die Verknüpfung von zwei Elementen p, q hängt von der Tiefe der Elemente ab: (p = v_{1}u′_{1}v_{2} ⋯ v_{k}u′_{k}v_{k+1} und q = t_{1}s′_{1}t_{2} ⋯ t_{k}s′_{k}t_{l+1})

p ∘ q = \begin{cases}(p ∘ t_{1})s′_{1}t_{2} ⋯ t_{k}s′_{k}t_{l+1} & falls tiefe (p) < tiefe (q), \\ v_{1}u′_{1}v_{2} ⋯ v_{k}u′_{k}(v_{k+1} ∘ q) & falls tiefe (p) > tiefe (q), \\ v_{1}u′_{1}v_{2} ⋯ v_{k}u′_{k}(v_{k+1} ∘ t_{1})s′_{1}t_{2} ⋯ t_{k}s′_{k}t_{l+1} & falls tiefe (p) = tiefe (q). \end{cases}

Die einstellige Operation ′ ist klar.

3.1.3 Eine Methode für die Signaturerweiterung

Wir interessieren uns für einen Spezialfall, wo die Signatur um eine einzige einstellige Operation erweitert wird. In der Tat kann man die letzte Konstruktion für die unären Monoide beinahe ”abschreiben“. In der letzten Konstruktion haben wir auch gleich die Gleichung λ′ = λ behandelt. Wir gehen also ähnlich wie im Falle der Monoide vor, und nehmen uns eine beliebige Algebra A^{+} in 𝔎^{+} her, die eine Erzeugermenge E besitzt, zerlegen sie, um auf eine Charakterisierung zu kommen, die den Schlüssel zu der eigentlichen Konstruktion liefert, falls die Erzeugermenge eine Basis ist. Zunächst ein paar Notationen: Wir bezeichnen mit X eine beliebige Variablenmenge. Wir betrachten zwei Varietäten, die sich nur um eine einstellige Operation in der Signatur unterscheiden, und legen folgende Notationen fest:

Bezeichnung der Varietät: 𝔎  𝔎^{+}
Signatur:  Σ  Σ^{+} = Σ ∪ {g} (g: die neue einstellige Operation)
Gleichungsmenge:  E  E
Freie Algebra über X:  F (X) F (X)^{+}

Die Strategie lautet:

1. ”Vergessen“, daß die Algebra A^{+} in 𝔎^{+} lebt und diese als Algebra in 𝔎 betrachten,

2. Induktiv über die Tiefe zerlegen. Die Zerlegung kann dabei stationär werden (etwa für eine leere Erzeugermenge bei den unären Monoiden, oder für eine Algebra in 𝔎, wo g als Identität interpretiert wird, so daß die Algebra auch in 𝔎^{+} liegt, oder g^{2} = Id, usw. ). Man hofft dabei, daß man ”am Ende“ A^{+} ausgeschöpft hat.

3. Alle Stücke wieder zusammenbauen (Supremum der Folge der im Laufe der Zerlegung entstandenen Stücke), um die ganze Algebra zu gewinnen,

4. Sich auf F (X)^{+} konzentrieren und in diesem Fall die Stücke als freie Strukturen identifizieren,

5. Das Modell nach dem erhaltenen Muster konstruieren (Anfang, Induktionsschritt, Supremum, Definition der neuen Operation)!

6. Die universelle Eigenschaft beweisen.

Zerlegung

Wir zerlegen also eine Algebra A^{+}, die von einer Menge E in 𝔎^{+} (nicht unbedingt frei) erzeugt wird: Da A^{+} die Erzeugermenge E umfaßt, existiert das Erzeugnis (bezüglich der alten Signatur Σ) von E in A^{+}, wir bezeichnen es mit < E >_{Σ}. Dies liefert uns den Induktionsanfang: △ Induktionsanfang Wir setzen

B_{0} :=< E >_{Σ} und A_{0} := B_{0}

△ Induktionsschritt

B_{n+1} :=< B_{n} ∪ g(A_{n}) >_{Σ} und A_{n+1} := B_{n+1} \ B_{n}

△ Supremumbildung Es ist A^{+} = ⋃_{k≥0} A_{k}, wegen des Satzes über die Vertauschbarkeit von Linksadjungierten und Colimites. Ferner gilt für die freie Algebra über X in 𝔎^{+}:

Satz 3.2 Falls A^{+} = F (X)^{+} gilt, dann sind folgende Algebren isomorph in 𝔎:

B_{0} ≅ F (X)
B_{n+1} ≅ F (X ⊎ ⨄_{0≤k≤n} g(A_{k})) für n ≥ 0
F (X)^{+} ≅ F (X ⊎ ⨄_{k≥0} g(A_{k}))

Beweis Die Operation g ist injektiv und die A_{k} disjunkt, so daß die Mengen g(A_{k}) disjunkt sind. Dann kann man mit dem Korollar 1 schließen.

Ein Modell für die freie Algebra der erweiterten Signatur

△ Induktionsanfang Wir konstruieren die Elemente der Tiefe 0. Setze B_{0} := F (X) . Sei A_{0} := B_{0}, die Menge der Elemente der Tiefe 0, und S_{0} := X.

△ Induktionsschritt Wir haben schon paarweise disjunkte Mengen A_{k} (für k ≤ n) konstruiert, deren Vereinigung mit die Grundmenge einer Algebra B_{n} in 𝔎 ist:

B_{n} = X ⊎ ⨄_{0≤k≤n} A_{k},

so daß gilt: B_{n} = F (S_{n}), für S_{n} := X ⊎ ⨄_{0≤k≤n−1} g(A_{k}).

Wir konstruieren eine Erweiterung B_{n+1} von B_{n}. Seien B_{n+1} := B_{n}[A_{n}] und A_{n+1} := B_{n+1} \ B_{n}. Die Menge A_{n+1} enthält die neuen Elemente, die nicht ohne g(A_{n}) erzeugt werden können, sie haben die Tiefe n+1. B_{n+1} besteht aus Elementen der Tiefe ≤ n + 1. △ Supremumbildung Nach dem Abschnitt 2.4 konstruieren wir den Colimes des Folgenfunktors der Folge (B_{n})_{n∈ℕ}, und nach 2.7 ist dieser Colimes die freie Algebra in 𝔎 über S, mit S := X ⊎ ⨄_{n≥0} g(A_{n}). Die neue Operation g kann nun als solche auf F (S) eingeführt werden.

Satz 3.3 Es ist F (S) die freie Algebra der Varietät 𝔎^{+} über X.

Beweis Induktiv über n prüft man nach, daß die Algebren der Folge, die wir hier konstruiert haben, und die Unteralgebren die bei der Zerlegung der freien Algebra über X in 𝔎^{+} entstehen, isomorph sind. Daraus folgt die Isomorphie für den Colimes.

3.2 Von den freien unären zu den freien regulären unären Monoiden

3.2.1 Dualität

Symmetrie Eigenschaften

Jedem unären Monoid M = (M, ∘,′ , λ) ordnet man wie folgt ein unäres Monoid M^{d} zu:

M^{d} := M
m1 ∘^{d} m2 := m2 ∘ m1 für alle m1, m2 ∈ M
m′^{d} := m^{d}′ für alle m ∈ M

Für ein freies unäres Monoid gilt U(X)^{d} ≅\underline{unMon} U(X). Das bedeutet einfach, daß man die Elemente (Listen) von links nach rechts oder von rechts nach links lesen kann. Der Isomorphismus ist offensichtlich eine Involution: rückw : U → U. Die Definition geschieht über Termaufbau:

x ∈ X rückw (x)  := x
t1, t2 rückw (t1 ∘ t2) := rückw (t2) ∘ rückw (t1)
t  rückw (t′)  := rückw (t)′
λ  rückw (λ)  := λ.

Definition 3 (T ⊆ U) T heißt symmetrisch, genau dann wenn T unter dem Morphismus rückw abgeschlossen ist. In diesem Fall gilt rückw T = T wegen der Involution.

Beispiel: Die U_{n} sind symmetrisch; (Beweis: Induktion über n)

Dualisierung der Hilfsrelationen und Operationen

Hat man eine 2-stellige Relation ≥ auf einer symmetrischen Teilmenge T von U, so entsteht folgendermaßen eine weitere 2-stellige Relation ≤ auf T (wenn es möglich ist, wählen wir das umgedrehte Relationssymbol für die neue Relation):

t1, t2 ∈ T t1 ≤ t2 :⇔ rückw (t2) ≥ rückw (t1)  (3.3)

Entsprechend läßt sich eine 2-stellige Operation / auf T dualisieren (die neue Operation schreiben wir \):

t1, t2 ∈ T t1\t2 := rückw (rückw (t2)/rückw (t1))  (3.4)

Beispiel:

a ⊢ b :⇔ aσab′b
b ⊣ a ⇔^{Def} rückw (a) ⊢ rückw (b)

Es gilt x(x′x)′x′xσx also x ⊢ x′x und folglich xx′ ⊣ x. Die im Beispiel eingeführte binäre Relation ⊢ liefert eigentlich den Schlüssel für das Aussuchen der Normalformen in U. Nun kann man aber wenig mit dieser axiomatischer Formulierung anfangen, vor allem ist sie nicht entscheidbar in dieser Form … Deshalb geben wir eine andere Relation ≥ an, mit der man ”rechnen“ kann, und wir beweisen im Laufe der Konstruktion, daß diese konkrete Relation tatsächlich die Axiome der Relation ⊢ erfüllt. Im Abschnitt über axiomatische Formulierung analysiert man hinreichende und notwendige Bedingungen, die zur Äquivalenz zwischen der konkreten Definition und dem gewünschten Ergebnis führen.

3.2.2 Hilfsmittel für das Aussuchen der Normalformen

Motivation: Für eine gegebene nichtleere Erzeugermenge X haben wir eine Folge von Monoiden (V_{n})_{n∈ℕ} konstruiert, die wir jetzt mit einer einstelligen Operation und einer binären Relation versehen wollen. Wir werden induktiv über n Teilmengen D_{n} von V_{n} konstruieren. Die binäre Relation ist ein Hilfsmittel, um bestimmte Elemente von V_{n} auszuschließen: manche Kombinationen von Bestandteilen werden nicht mehr zugelassen. Notation: Die einstellige Operation nennen wir ˆ und die binäre Relation ≥, und die ”zugehörige“ duale Operation bzw. Relation nennen wir ˜ bzw. ≤ (die entsprechenden Definitionen wurden in 3.3 bzw. 3.4 gegeben). Die Definition vonˆ geschieht mit Hilfe vollständiger Induktion über die Tiefe n (also eigentlich jedesmal mit einem Index n, aber da jede Operation die vorige erweitert, kann man auf die Indizes verzichten). Konstruktion: △ Induktionsanfang In U_{0}: Wir setzen

p̂, p̃:= p für alle p ∈ V_{0}.  (3.5)

Für alle p, q ∈ V_{0},

q ≥_{0} p :⇔ q = up̂ für ein u ∈ V_{0}.  (3.6)

Bemerkung: Die Relation ändert sich nicht, wenn man statt u ∈ V_{0} lediglich u ∈ U verlangt: es gibt höchstens ein solches Element, und falls es überhaupt existiert, dann liegt es tatsächlich in V_{0}. Zur Begründung: Da tiefe ein Morphismus ist, gilt tiefe (u) ≥ tiefe (q)); also liegt u in V_{0}. Die Eindeutigkeit ergibt sich aus der Eindeutigkeit der Darstellung der Elemente in V_{0}. △ Induktionsschritt In U_{n+1} für n ≥ 0: Sei p = a_{1}b′_{1} … a_{k+1} ∈ U_{n+1} (für die alten Elemente, wie vorher), wir unterscheiden folgende Fälle:

p erfüllt \{ \begin{matrix}CASE A: & a_{1} ≠ λ & b_{1} ≥_{n} a_{1} \\ CASE B: & a_{1} ≠ λ & ¬b_{1} ≥_{n} a_{1} \\ CASE C: & a_{1} = λ & b_{1} ≤_{n} a_{2} \\ CASE D: & a_{1} = λ & ¬b_{1} ≤_{n} a_{2}. \end{matrix}

Definiere

p̂:= \{ \begin{matrix}{ \atop b′_{1} … a_{k+1}} & CASE A \\ â_{1}b′_{1} … a_{k+1} & CASE B \\ { \atop a_{2} … a_{k+1}} & CASE C \\ p & CASE D. \end{matrix}

Definiere für p, q ∈ V_{n+1}

q ≥_{n+1} p :⇔ q = up̂ für ein u ∈ V_{n+1}.

Bemerkung: Falls ein u mit q = up̂ existiert, muß es tatsächlich in V_{n+1} liegen, also kann man die Bedingung auch ”u ∈ U“ formulieren. Die Begründung ist ähnlich wie in V_{0}. Daraus folgt, daß diese Definition die alte binäre Relation auf V_{n} erweitert, das heißt: die alten Elemente stehen genau dann in der neuen Relation, wenn sie schon in der alten standen).

Hilfssatz 1 Für p ∈ V_{n} gilt ˆ p̂ = p̂.

Beweis induktiv über n und k In CASE B wird die Induktionsannahme bezüglich n verwendet, in den anderen Fällen nicht:

ˆp̂ = { \atop â_{1}b′_{1} … a_{k+1}}
ˆp̂ =^{CASEB} ˆ â_{1}b′_{1} … a_{k+1}
ˆp̂ =^{IA}  â_{1}b′_{1} … a_{k+1}
ˆp̂ =^{CASEB} p̂

Für a_{1} ≠ λ gilt â_{1} ≠ λ und falls nicht b_{1} ≥_{n} a_{1}, dann auch nicht b_{1} ≥_{n} â_{1}, denn: u ˆâ_{1} = uâ_{1}.

△ Supremumbildung Wie üblich in U, da wir bemerkt haben, daß die Relationen sich erweitern. Beispiel: 1 Sei p := a(a′a)′a′a ∈ U_{k+2} für a ∈ U_{k}. Es gilt

p̂ =^{CASEA} { \atop (a′a)′a′a}
=^{CASEC} â′a
=^{CASEC} â

Insbesondere gilt { \atop x(x′x)′x′x} = x für eine Variable x =: a. Beispiel: 2 Wir greifen wieder nach unserer Lieblingsfolge (a_{n})_{n∈ℕ}, die folgendermaßen definiert war:

\begin{matrix}b_{0} & =^{Def} & a \\ a_{0} & =^{Def} & ab′_{0}b_{0} \\ b_{n+1} & =^{Def} & b′_{n}b_{n} \\ a_{n} & =^{Def} & ab′_{n}b_{n} \end{matrix} .

Es gilt b_{n} ≥ a. Es gilt b̂_{n} = â, denn:

b̂_{0} =^{Def} â

und

b̂_{n+1}  =^{Def}  b̂′_{n}b_{n}
=^{CASEC} b̂_{n}

Wir haben b̃_{0} = ã und b̃_{n+1} = b′_{n}, denn:

b̃_{n+1}  =^{Def}  b̃′_{n}b_{n}
=^{CASEA} b̃′_{n}
=^{CASED} b′_{n}

Es gilt â_{n} = â und ã_{n} = ã, denn:

â_{n+1}  =^{Def}  { \atop ab′_{n}b_{n}}
=^{CASEA} b̂′_{n}b_{n}
=^{Def}  b̂_{n+1}

und

ã_{n}  =^{Def}  { \atop ab′_{n}b_{n}}
=^{CASEA} ãb′_{n}
=^{CASEC} ã

Mit der axiomatischen Formulierung des nächsten Abschnitts werden wir folgende Behauptungen beweisen.

Behauptung 6

p ≥ q ⇔ p ≥ q̂,

p ≥ q ⇒ pq̂′q̂σp,

p ≥ q ⇒ pq′qσp.

Bemerkung: Die Rückrichtung in der letzten Aussage gilt auch, und sie wird mit der Konstruktion von Polák bewiesen. Die Relation, die wir hier konstruiert haben ist also tatsächlich die Relation ⊢ aus dem Beispiel in 3.2.1.

3.2.3 Axiomatische Formulierung

Gegeben ein System von drei einstelligen Operationen auf U, f, f^{L}, f^{∗} so daß gilt:

f^{2} = f  (3.7)
id = ·(f^{L}, f)  (3.8)
fσ · (f^{∗}, id), (punktweise).  (3.9)

Eine binäre Relation ≥ wird folgenderweise auf U definiert:

a ≥ b :⇔ es existiert u ∈ U mit a = ·(u, f(b)).  (3.10)

Hilfssatz 2 Es gilt:

a ≥ b ⇔ a ≥ f(b)  (3.11)
a ≥ b ⇒ af(b)′f(b)σa  (3.12)
a ≥ b ⇒ ab′bσa  (3.13)

Beweis Zu 3.11: f^{2}(b) = f(b) (verwendet nur 3.7)

Zu 3.12: nach Voraussetzung gilt a = uf(b) und σ ist eine Kongruenzrelation auf U. Für den Beweis wurde 3.10 verwendet. Zu 3.13:

f(b) σ f^{∗}(b)\underline{b}_{↑}
σ \underline{f^{∗}(b)b}b′b
σ f(b)b′b.

Also gilt

af(b)′\underline{f(b)} σ \underline{af(b)′f(b)}b′b
σ ab′b ,

denn af(b)′f(b)σa.

Bemerkung: Für den Beweis wurden 3.12, also 3.10 und 3.9 verwendet. Glücklicherweise erfüllt die Operationˆ die Voraussetzungen für f, falls man f^{L} wie ()^{L} definiert (da hat man sowieso keine andere Möglichkeit wegen der Eindeutigkeit der Darstellung):

p^{L} := \{ \begin{matrix}a_{1}(b′_{1}a_{2} …)^{L} & CASE A \\ (a_{1})^{L} & CASE B \\ b′_{1}(a_{2} …)^{L} & CASE C \\ λ & CASE D, V_{0}. \end{matrix}

Für f^{∗} kann man zum Beispiel folgende Operation ()^{∗} nehmen:

p^{∗} := \{ \begin{matrix}(b′_{1}a_{2} …)^{∗}b′_{1}b_{1}a′_{1} & CASE A \\ (a_{1})^{∗} & CASE B \\ (a_{2} …)^{∗}b_{1} & CASE C \\ λ & CASE D, V_{0}. \end{matrix}

Behauptung 7 Es gilt

T_{n} p̂σp^{∗}p für alle p ∈ V_{n}.  (3.14)

Daraus folgt natürlich

a ≥ b ⇒ ab′bσa für alle a ∈ U, b ∈ V_{n}.  (3.15)

Beweis Es gilt T_{0}, weil p̂ = p für alle p ∈ V_{0}.

Von T_{n} nach T_{n+1}: mit Hilfe vollständiger Induktion L_{k} über Länge k, die nur für den Fall CASE C benötigt wird: die anderen sind direkt beweisbar. Zu L_{0}: Für CASE D: klar. Für CASE B: klar mit T_{n} für a_{1}. Für CASE C: b_{1} ≤ a_{2} also a_{2}σb_{1}b′_{1}a_{2}. Daraus folgt für L_{0}:

p^{∗}p = a_{2}^{∗}\underline{b_{1}b′_{1}a_{2}}
σ a_{2}^{∗}a_{2}
σ p̂ (wegen T_{n} für a_{2}).

Von L_{k} nach L_{k+1}:

p^{∗}p = (a_{2} …)^{∗}\underline{b_{1}b′_{1}a_{2}} …
σ (a_{2} …)^{∗}a_{2} …
σ p̂ (Induktionsannahme bezüglich der Länge).

Für CASE A: nach Voraussetzung gilt b_{1} ≥ a_{1}. Also mit der Induktionsannahme T_{n} gilt b_{1}a′_{1}a_{1}σb_{1} und somit

b′_{1}\underline{b_{1}a′_{1}a_{1}}b′_{1}σ\underline{b′_{1}b_{1}b′_{1}}_{↓}σb′_{1}.  (3.16)

Daher

p^{∗}p = (b′_{1}a_{2} …)^{∗}\underline{b′_{1}b_{1}a′_{1}a_{1}b′_{1}}a_{2} …
σ (b′_{1}a_{2} …)^{∗}b′_{1}a_{2} …
σ p̂ (mit CASE C, bzw. CASE D, Tiefe n + 1).

Die freien regulären unären Monoide

4.1 Ein Rahmen für die Konstruktion: d-Reihen

4.1.1 Definition und Beispiele

Definition

Mit Hilfe der aufsteigenden Folge der Monoide (V_{n})_{n∈ℕ} haben wir U mit zusätzlichen Operationen versehen: wir haben zwei aufsteigende Folgen von einstelligen Operationen mit Supremum und ()^{L} definiert. Die dualen Operationen haben wir mit und ()^{R} bezeichnet. Das waren Hilfsmittel für das Aussuchen der Normalformen in U. Nun bereiten wir die induktive Konstruktion der Operationen auf der Menge der Normalformen vor. Wenn die Hilfsoperationen und Relationen auf einem D_{n} gewisse Bedingungen erfüllen, läßt sich die Korrektheit der Konstruktion im nächsten Schritt beweisen. Die Voraussetzungen fassen wir in einem Begriff d-Reihe zusammen.

Definition 4 Eine d-Reihe D wird definiert durch:

• eine aufsteigende Folge von Teilmengen (D_{n})_{n∈ℕ}, wobei D_{n} ⊆ V_{n}. Wir bezeichnen mit D das Supremum der D_{n}, und setzen

C_{0} := D_{0} \ {λ}
C_{n+1} := D_{n+1} \ D_{n} für n ≥ 0,

• eine aufsteigende Folge von zweistelligen Operationen

∘_{n}: D_{n} × D_{n} → D_{n}

(das Supremum wird ohne Index notiert),

• eine aufsteigende Folge von einstelligen Operationen

()_{L,n}: D_{n} × D_{n} → D_{n}

(das Supremum wird auch ohne Index notiert, und die duale Operation mit ()_{R} bezeichnet),

• folgende Voraussetzungen:

(0) \begin{cases}X ⊆ D_{n} ⊆ V_{n}, \\ D_{n}ist unter und ()^{L} abgeschlossen, \\ D_{n} ist symmetrisch, \\ rückw (a ∘ b) = rückw (b) ∘ rückw (a) für alle a, b ∈ D, \end{cases}

(1) (D_{n}, ∘_{n}, λ) ist ein Monoid,

(2) für p, q ∈ U gilt pq ∈ C_{n} ⇒ p, q ∈ D_{n} und p ∘ q = pq,

(3) für p ∈ D_{n}, q ∈ C_{n} gilt p ∘ q̂ = rq̂ für ein r ∈ D_{n},

(4) für p ∈ D gilt p̂ = p_{L} ∘ p. Bemerkung: In (3) kann man wegen (2) auch r ∈ U voraussetzen.

Beispiele

• Die Folge (V_{n})_{n∈ℕ} mit der ”alten“ Verkettung als ∘ und ()^{L} als ()_{L} ist eine d-Reihe.

• Die stationäre Folge (V_{0})_{n∈ℕ} mit ∘ und ()_{L} wie oben ist eine weitere d-Reihe.

• Allgemeiner kann eine d-Reihe D durch die Folge ihrer Approximationen definiert werden, das heißt eine aufsteigende Folge von d-Reihen (D_{n})_{n∈ℕ}, wobei die d-Reihe D_{n} bis zum Rang n mit D übereinstimmt und dann stehen bleibt. Wir nennen stehenbleibende d-Reihen stationär. Für die Konstruktion des Modells von Polák werden wir eine d-Reihe durch ihre Approximationen definieren.

4.1.2 Weitere Hilfsoperationen

Für eine d-Reihe D schränken wir die Hilfsrelation ≥ auf D × D ein. Aus der Voraussetzung (2) folgt für Elemente p, q ∈ D :

p = uq̂ mit u ∈ D ⇔ p = uq̂ mit u ∈ U  (4.1)

Falls es existiert, ist das Element u eindeutig bestimmt. Also ist die partielle zweistellige Operation / wohldefiniert auf D: für p, q ∈ D, setze

p/q := \begin{cases}u ∘ q_{L} & falls p ≥ q, p = uq̂ \\ undefiniert & sonst \end{cases}

Falls p/q definiert ist, liefert es einen Wert in D, weil das u auch in D liegt. Die Hilfsoperation läßt sich natürlich als \ dualisieren. Mit Hilfe dieser Relationen und Operationen lassen sich Eigenschaften der d-Reihen formulieren, die uns erlauben, eine Folge stationärer d-Reihen induktiv zu konstruieren.

4.1.3 Eigenschaften

Für eine beliebige d-Reihe D haben wir folgende Eigenschaften:

Lemma 3 (für jedes n)

(5) für p ∈ D_{n}, q ∈ C_{n} gilt p ∘ q ≥ q, (6) für p, r ∈ D_{n}, q ∈ C_{n} mit p ≥ q ≤ r gilt (p/q) ∘ r = p ∘ (q\r),

(7) für p ∈ D_{n}, q ∈ C_{n} gilt p ≥ q ⇒ p/q ∘ q = p,

(8) für p ∈ D_{n}, q ∈ C_{n} gilt p ≥ q ⇔ p = r ∘ q für ein r ∈ D_{n},

(9) für p, r ∈ D_{n}, q ∈ C_{n} mit p ≥ q und r ≤ p/q gilt r ≤ p. Beweis (mit den obigen Notationen)

Zu (5)

p ∘ q =^{[4]} p ∘ (q^{L}q̂)
=^{[2]} p ∘ q^{L} ∘ q̂
=^{[1]} (p ∘ q^{L}) ∘ q̂
=^{[3]} rq̂, für r ∈ D_{n}.

Zu (6)

(p/q) ∘ r =^{Def} (u ∘ q_{L}) ∘ r
=^{V or} (u ∘ q_{L}) ∘ (q̃∘ v)
=^{[4dual]} (u ∘ q_{L}) ∘ ((q ∘ q_{R}) ∘ v)
=^{[1]}  u ∘ q_{L} ∘ q ∘ q_{R} ∘ v

Dual gilt auch

rückw (p ∘ (q\r)) = rückw (u ∘ q_{L} ∘ q ∘ q_{R} ∘ v),

also (p/q) ∘ r = p ∘ (q\r). Zu (7)

p ≥ q heißt p = uq̂.

(u ∘ q_{L}) ∘ q =^{[1]} u ∘ (q_{L} ∘ q)
=^{[4]} u ∘ q̂
=^{[2]} uq̂
=^{[V or]} p.

Zu (8) ”⇒“ erhält man mit r := u ∘ q_{L} in [7].

”⇐“ gilt wegen p = r ∘ q in [5].

Zu (9) Mit [8dual] gilt p/q = r∘v für ein v ∈ D_{n}, und mit [7] (p/q)∘q = p.

(p/q) ∘ q =^{[8dual]} (r ∘ v) ∘ q
=^{[1]}  r ∘ (v ∘ q)
(p/q) ∘ q =^{[7]}  p,

Daraus folgt p = r ∘ (v ∘ q) und r ≤ p mit [8dual].

4.2 Poláks Modell

Motivation: In diesem Abschnitt konstruieren wir induktiv eine Folge von d-Reihen (D_{n})_{n∈ℕ}.

4.2.1 Konstruktion

△ Induktionsanfang

Die d-Reihe D_{0} ist schon bekannt: wir nehmen die stationäre d-Reihe (V_{0})_{n∈ℕ}, wie sie im Abschnitt 4.1.1 definiert wurde … △ Induktionsschritt

Aus einer d-Reihe D, die ab der Tiefe n stehen bleibt, konstruieren wir nun eine d-Reihe D^{+}, die ab der Tiefe n + 1 stehen bleibt.

1. Folge der unterliegenden Mengen (D_{k}^{+})_{k∈ℕ} Die Folge bleibt bis zur Tiefe n unverändert: D_{k}^{+} = D_{k} für k ≤ n, und wir erweitern die unterliegende Menge bis zur Tiefe n + 1 mit D_{n+1}^{+} := C_{n+1}^{+} ⊎ D_{n}, wobei C_{n+1} ⊆ U_{n+1},

C_{n+1} := ⨄_{k≥1} {a_{1}b′_{1}a_{2} ⋯ a_{k}b′_{k}a_{k+1}|a_{i} ∈ D_{n}, b_{i} ∈ C_{n} und ♣}

♣ heißt ¬(a_{i} ≥ b_{i} ≤ a_{i+1}) und ¬(b_{i} = a_{i+1} = b_{i+1}) für alle i. Es ist klar, daß C_{n+1}^{+} symmetrisch ist.

2. Erweiterung der Operationen Die Verknüpfung ∘_{n+1} muß für ein altes und ein neues Element sowie für zwei neue Elemente definiert werden, die Hilfsoperation ()_{L,n+1} für die neuen Elemente. Die Definitionen von Polák können in [Pol89, 186] nachgelesen werden. Die Definition der Verknüpfung ist rekursiv über die Länge k der Elemente (siehe die obige Beschreibung der Grundmenge) und basiert auf fünf Regeln, die man nicht deterministisch anwenden kann. Es ist zu zeigen, daß die Verkettung auf D^{+} korrekt definiert ist, und daß sie assoziativ ist. Dieses wird induktiv über die Summe der Länge der Elemente gezeigt. Dafür werden die Aussagen (1) bis (9) des Lemmas 1 in 4.1.3 benutzt. Der Beweis der Aussagen (1) bis (4) des Lemmas 1 zeigt, daß die Folge (D_{k}^{+})_{k∈ℕ} tatsächlich eine d-Reihe D^{+} definiert. Mit der Voraussetzungen, die wir an der d-Reihen gestellt haben, erhalten wir die Eigenschaften, die in 4.1.3 bewiesen wurden, also die Aussagen (5) bis (9) des Lemmas 1 in [Pol89, 187].

△ Supremumbildung Mit der Folge der d-Reihen (D_{n})_{n∈ℕ} bekommt man ein Monoid als Supremum der Monoide (D_{n}, ∘_{n}, λ). Es ist die Grundmenge C := ⋃ V_{n} unter der Operation ′ abgeschlossen, also ist (C, ∘,′ , λ) ein unäres Monoid. Im nächsten Abschnitt weisen wir nach, daß C die gewünschten Gesetze erfüllt.

4.2.2 Korrektheit

Die Beweise stehen in [Pol89, 193]. Zunächst zitieren wir noch die Aussagen (10) und (11) des Lemmas 1 von Polák. Sie werden hier natürlich für die d-Reihen formuliert. Der Beweis wird induktiv über n geführt. Die Aussagen sind klar für n = 0. Für den Induktionsschritt darf man die Aussagen (1) bis (9) des Lemmas 1 von Polák benutzen. Die Aussagen (1) bis (4) gelten nach der Definition der d-Reihen. Die Aussagen (5) bis (9) sind Eigenschaften der d-Reihen.

Lemma 4 (für jedes n) In der d-Reihe D_{n+1} haben wir:

(10) Für p, r ∈ D_{n}, q ∈ C_{n} mit p ≥ q ≤ r gilt pq′rσ(p/q) ∘ r.

(11) Für alle p, r ∈ D_{n} gilt p ∘ rσpr .

Bemerkung: Es ist p ≥ q ≤ q, also gilt insbesondere p ≥ q ⇔ pq′qσp.

Satz 4.1 Es ist (C, ∘,′ , λ) das frei unäre reguläre Monoid über X.

Ein Entscheidungsverfahren für das Wortproblem

Man erhält die Normalform c(p) eines Elements p = a_{1}b′_{1} ⋯ a_{k}b′_{k}a_{k+1} indem man rekursiv die alte Verkettung durch die neue Verkettung ∘ ersetzt:

c(p) = c(a_{1}) ∘ c(b_{1})′ ∘ ⋯ c(a_{k}) ∘ c(b_{k})′ ∘ c(a_{k+1}).

Literaturverzeichnis

[Bur80] W. D. Burgess. On free commutative regular rings. In Communications in Algebra, volume 8(7), pages 671–683, 1980.

[LN73] Hans Lausch and Wilfried Nöbauer. Algebra of Polynomials. North-Holland Publishing Compagny, Amsterdam, 1973.

[ML72] Saunders Mac Lane. Categories. For the Working Mathematician. Springer Verlag, 1972.

[MLB88] Saunders Mac Lane and Garrett Birkoff. Algebra. Chelsea Publishing Compagny, New York, third edition edition, 1988.

[Pol89] Libor Polák. Free regular unary semigroups. In John Rhodes Ed., editor, Monoids and Semigroups with applications, pages 184–197, Singapore, 1989. World Scientific.