Stetige Operationen auf kontinuierlichen Bereichen

Christine Strüder

�

Diplomarbeit am Fachbereich Mathematik

der TH Darmstadt

Betreuer: Privatdozent Dr. A. Jung

April 1995

Inhaltsverzeichnis

Einleitung 2 1 Grundlagen 4 2 Konstruktion freier Bereichsalgebren 10 3 Freie Bereichskegel 24 4 Präsentationen 30 Literaturverzeichnis 38

Einleitung

Möchte man Programme in der Informatik mathematisch beschreiben, so bietet der Begriff des Bereichs einen geeigneten Zugang. Bereiche sind spezielle geordnete Mengen, die sich dann zur Beschreibung von Programmen eignen, wenn man diese als eine Menge von Zuständen einer ”Rechenmaschine“ auffaßt. Auf Bereichen möchte man nun algebraische Strukturen einführen, also auf ihnen ”rechnen“ können. Dies führt zum Begriff der Bereichsalgebra; diese unterscheidet sich von Algebren im üblichen Sinn dadurch, daß die Operationen die spezielle Struktur der Trägermenge, nämlich die des Bereichs, erhalten. Oft soll dieses ”Rechnen“ nach bestimmten Gesetzen stattfinden, oder allgemeiner, die Algebra soll gewissen (Un-)Gleichungen genügen. Hat man nun einen Bereich, gewisse Operationen und Ungleichungen gegeben, stellt sich die Frage, welche Bereichsalgebren diese Anforderungen erfüllen und insbesondere wie unter diesen das allgemeinste Objekt aussieht.

Die Frage nach dieser sogenannten freien Bereichsalgebra kann man allgemein für Bereiche mit kategoriellen Methoden lösen, wie in [1] gezeigt wird. Ist der gegebene Bereich jedoch kontinuierlich, d.h. besitzt er eine Basis, ist diese Frage schon schwieriger. Für spezielle kontinuierliche Bereiche, die algebraischen, bei denen die Basis aus kompakten Elementen besteht, ist die Antwort schon länger bekannt. Dazu werden in [6] und [7] Ergebnisse präsentiert. Für beliebige kontinuierliche Bereiche wurden erst in jüngster Zeit Möglichkeiten zur Konstruktion von freien Bereichsalgebren gefunden. J. Koslowski benutzt in [3] kategorielle Methoden, um das gesuchte Objekt zu erhalten. In [1] zeigt A. Jung einen Weg zur Konstruktion von solchen Bereichsalgebren, mit dem sich konkrete Aussagen über die Basen der kontinuierlichen Bereiche machen lassen.

Diese Konstruktion wird in der vorliegenden Arbeit verallgemeinert: Es werden Signaturen betrachtet, bei denen die Operationssymbole selbst einen kontinuierlichen Bereich bilden. Zu einer solchen Signatur und vorgegebenen Ungleichungen wird im zweiten Kapitel dieser Diplomarbeit die freie Bereichsalgebra über einem gegebenen kontinuierlichen Bereich konstruiert. Die Konstruktion verbindet Methoden und Ergebnisse der Bereichstheorie mit denen der Allgemeinen Algebra. Die notwendigen Grundlagen dazu werden in Kapitel 1 bereitgestellt. Die freie Konstruktion ist so nur möglich, wenn die vorgegebene Menge von Ungleichungen bestimmte Bedingungen erfüllt. Genau hier treten Probleme auf, wenn man versucht, die Konstruktion auf Bereichskegel, einen speziellen Typ von Bereichsalgebra, anzuwenden, und so freie Bereichskegel erhalten will. Im dritten Kapitel wird dargelegt, worin diese Probleme liegen, wie sie zu lösen sind und warum freie Bereichskegel hierbei vermutlich einen Ausnahmefall darstellen. Eine weitere Anwendung der Methoden aus dem zweiten Kapitel stellen universelle Lösungen für Präsentationen dar. Präsentationen sind ein noch umfassenderes Beschreibungsmittel für Algebren. Im vierten Kapitel werden zwei verschiedene Möglichkeiten gezeigt, die gesuchte Bereichsalgebra zu konstruieren, und die Isomorphie der beiden Darstellungen bewiesen.

An dieser Stelle möchte ich allen danken, die mich in irgendeiner Weise bei dieser Diplomarbeit unterstützt haben, insbesondere meinen Eltern, die mir das Studium ermöglicht haben, und denen, die mir in den ”Frustphasen“ ein Rückhalt waren. Bei den Mitgliedern der Arbeitsgruppe Domains bedanke ich mich für viele Anregungen, Ermunterungen und Antworten auf Fragen ”zwischendurch“. Allen voran danke ich Herrn Dr. Achim Jung für die intensive Betreuung dieser Arbeit und sein persönliches Engagement.

1 Grundlagen

In diesem Kapitel werden die Definitionen der wichtigsten Begriffe aus der Theorie der Bereiche vorgestellt und einige ihrer Eigenschaften bewiesen. Diese Grundlagen sind [1], Kapitel 2, entnommen, das sich auch zur Vertiefung der Kenntnisse eignet. Die notwendigen Begriffe aus der Allgemeinen Algebra werden am Ende des Kapitels erklärt.

Definition 1.1 Es sei (D, ≤) eine geordnete Menge. Eine Teilmenge A von D heißt gerichtet, wenn A nicht leer ist und zu x, y ∈ A stets ein z ∈ A mit {x, y} ≤ z existiert. Die Menge (D, ≤) heißt Bereich, wenn jede gerichtete Teilmenge A von D ein Supremum besitzt. Dieses wird mit ^{⨆ ↑}A bezeichnet.

Jede endliche geordnete Menge ist ein Bereich. Ein weiteres einfaches Beispiel für einen Bereich, den wir im folgenden noch öfter betrachten werden, ist \overline{ℝ}_{+} = ℝ_{+}∪\{∞\}. Den nichtnegativen reellen Zahlen ℝ_{+} muß noch ein größtes Element ∞ hinzugefügt werden, damit diese einen Bereich bilden.

[figure: ·; ·; ·; 0; ∞; \overline{ℝ}_{+}]

Aus der Analysis ist bekannt, daß man jede reelle Zahl durch eine Folge von rationalen Zahlen annähern kann. Die Idee des Approximierens läßt sich auch für Bereiche definieren; über die Ordnung auf einem Bereich kann man eine zweite Relation einführen, die sogenannte Approximationsordnung. Diese Art der Näherung ist jedoch eine Approximation eines Elements ”von unten“, und nicht, wie in der Analysis, eine ”Einschachtelung“ des Elements von beiden Seiten.

Definition 1.2 Es seien x und y Elemente eines Bereichs D. Ein Element x approximiert y (in Zeichen: x ≪ y), wenn für alle gerichteten Teilmengen A von D mit y ≤ ^{⨆ ↑}A ein a ∈ A mit x ≤ a existiert. Man sagt dann auch: ”x liegt weit unter y.“ Liegt das Element x weit unter sich selbst (x ≪ x), dann heißt x kompakt.

Um alle Elemente betrachten zu können, die x in D approximieren, führen wir folgende Notation ein: ↓ ↓x := {y ∈ D | y ≪ x}. Der Gedanke, Elemente eines Bereichs über ”einfachere“ Elemente beschreiben zu können, wird im Begriff der Basis fortgeführt.

Definition 1.3 Eine Teilmenge B eines Bereiches D heißt Basis von D, wenn für jedes Element x ∈ D die Menge B_{x}: = ↓ ↓x∩B eine gerichtete Teilmenge mit Supremum x enthält.

Man kann also jedes Element aus D als gerichtetes Supremum von Basiselementen darstellen. Der Begriff ”gerichtetes Supremum“ steht dabei verkürzend für den Ausdruck ”Supremum einer gerichteten Menge“. Für den oben erwähnten Bereich der reellen Zahlen bilden die rationalen Zahlen ℚ_{+} eine Basis. Ebenso gut könnte man stattdessen die irrationalen Zahlen betrachten. Ein Bereich mit einer Basis bekommt einen speziellen Namen:

Definition 1.4 Ein Bereich heißt kontinuierlicher Bereich, wenn er eine Basis besitzt.

Die oben erwähnten Bereiche sind kontinuierlich. Bereiche kann man mittels spezieller Abbildungen miteinander in Beziehung setzen. Im folgenden bezeichne D, E, F … stets kontinuierliche Bereiche.

Definition 1.5 Eine Funktion f : D → E ist Scott-stetig, wenn sie monoton ist und wenn für jede gerichtete Teilmenge A von D gilt: f(^{⨆ ↑}A) = ^{⨆ ↑}f(A).

Da eine Verwechslung des Begriffs mit dem aus der Analysis nicht zu befürchten ist, wollen wir verkürzend nur von stetigen Funktionen sprechen. Die Eigenschaft, gerichtete Suprema zu erhalten, genügt bereits, um stetige Funktionen zu definieren. Um aber die Stetigkeit einer Funktion f tatsächlich nachzuweisen, muß man zeigen, daß f(A) gerichtet ist. Dies ist äquivalent zur Monotonie von f.

Im nächsten Kapitel werden wir Funktionen betrachten, die auf dem kartesischen Produkt von kontinuierlichen Bereichen definiert sind. Hilfreich ist dann die Tatsache, daß man diese Funktionen komponentenweise auf Stetigkeit prüfen kann, da die Ordnung auf dem Produkt von Bereichen komponentenweise definiert ist.

Satz 1.6 Eine Funktion f : D × E → F ist genau dann stetig, wenn sie in jeder Komponente stetig ist.

Beweis: ”⇐“: Sei f in jeder Komponente stetig. Die Monotonie von f ergibt sich aus der Monotonie von f in den einzelnen Komponenten: Aus (x_{1}, y_{1}) ≤ (x_{2}, y_{2}) folgt (x_{1}, y_{1}) ≤ (x_{1}, y_{2}) ≤ (x_{2}, y_{2}) und damit nach Voraussetzung f(x_{1}, y_{1}) ≤ f(x_{1}, y_{2}) ≤ f(x_{2}, y_{2}). Der Nachweis der Stetigkeit verläuft ähnlich. Es sei A ⊆ D × E gerichtet. Mit π_{1} : D × E → D bzw. π_{2} : D × E → E bezeichnen wir die Projektion des Produkts in die erste bzw. zweite Komponente. Es gilt:

\begin{matrix}⨆ & ↑ \\ (x,y)∈A \end{matrix} f(x, y) = \begin{matrix}⨆ & ↑ \\ x∈π_{1}(A) \end{matrix} \begin{matrix}⨆ & ↑ \\ y∈π_{2}(A) \end{matrix} f(x, y)
= \begin{matrix}⨆ & ↑ \\ x∈π_{1}(A) \end{matrix} f(x, \begin{matrix}⨆ & ↑ \\ y∈π_{2}(A) \end{matrix} y)
= f(\begin{matrix}⨆ & ↑ \\ x∈π_{1}(A) \end{matrix} x, \begin{matrix}⨆ & ↑ \\ y∈π_{2}(A) \end{matrix} y)
= f(\begin{matrix}⨆ & ↑ \\ (x,y)∈A \end{matrix}(x, y))
= f(^{⨆ ↑}A).

”⇒“: Die umgekehrte Richtung ist trivial. □

Den Begriff der ”Basis“ haben wir in Definition 1.3 als Teilmenge eines kontinuierlichen Bereiches eingeführt. Wir können dies jedoch auch auf andere, abstrakte Weise tun.

Definition 1.7 Eine abstrakte Basis ⟨B, ≺⟩ besteht aus einer Menge B und einer transitiven Relation ≺ auf B derart, daß das folgende Interpolationsaxiom für alle x ∈ B und für alle endlichen Teilmengen M von B erfüllt ist:

M ≺ x ⇒ ∃y ∈ B. M ≺ y ≺ x.

Der Zusammenhang zwischen beiden Basis-Begriffen wird über die Approximationsordnung des betrachteten kontinuierlichen Bereiches gegeben. Für eine Basis B eines kontinuierlichen Bereiches gilt bzgl. der Approximationsordnung ≪:

Satz 1.8 ⟨B, ≪⟩ ist eine abstrakte Basis.

Beweis: Die Transitivität der Relation ≪ ist klar. Für das Interpolationsaxiom gelte M ≪ x für eine endliche Teilmenge M von B. Wir betrachten die Menge A = {a ∈ B | ∃ a′ ∈ B : a ≪ a′ ≪ x}. A ist nicht leer, da die Mengen der Form ↓ ↓m, m ∈ M, nicht leer und in A enthalten sind. Außerdem ist A eine gerichtete Menge: Zu a ≪ a′ ≪ x und b ≪ b′ ≪ x finden wir, da ↓ ↓x gerichtet ist, ein c′ ∈ B mit a′ ≤ c′ ≪ x und b′ ≤ c′ ≪ x. Mit demselben Argument für ↓ ↓c′ existiert ein c ∈ B mit a ≤ c ≪ c′ und b ≤ c ≪ c′. Insgesamt gilt {a, b} ≤ c ≪ c′ ≪ x, also c ∈ A. Um das Supremum von A zu berechnen, betrachten wir ein y ∈ B mit y ≪ x. Es gilt ↓ ↓y ⊆ A und damit ^{⨆ ↑}A ≥ ^{⨆ ↑}↓ ↓y = y. Dies gilt für alle y ≪ x, und somit folgt x = ^{⨆ ↑}↓ ↓x ≤ ^{⨆ ↑}A. Da alle Elemente aus A kleiner als x sind, gilt in der Tat die Gleichheit: x = ^{⨆ ↑}A. Nun können wir die Definition der Approximation auf jedes m aus unserer Ausgangsmenge M anwenden: Nach Definition 1.2 gibt es für jedes m ∈ M ein a_{m} ∈ A mit m ≤ a_{m}. Für die zugehörigen a_{m} können wir nun eine obere Schranke y in A finden; y interpoliert zwischen M und x. □

Die Aussage von Satz 1.8 ist grundlegend für die Argumentation bzw. Konstruktion in Kapitel 2, da wir dort mit den Basen der betrachteten kontinuierlichen Bereiche arbeiten und die Interpolationseigenschaft benutzen wollen. Von einer abstrakten Basis kann man zu einem kontinuierlichen Bereich gelangen, wenn man die sogenannte Idealvervollständigung betrachtet.

Definition 1.9 Es sei ⟨B, ≺⟩ eine abstrakte Basis. Eine Teilmenge A von B heißt Ideal, wenn A gerichtet und eine untere Menge ist, d.h. aus x ∈ A folgt y ∈ A für alle y ≺ x. Die Idealvervollständigung von B (in Zeichen: Idl(B, ≺)) ist die Menge aller mittels Inklusion geordneten Ideale. Mit i : B → Idl(B, ≺) wollen wir die Funktion bezeichnen, die jedes x ∈ B auf ↓x: = {y ∈ B | y ≺ x} abbildet.

Satz 1.10 Idl(B, ≺) ist ein kontinuierlicher Bereich; eine Basis ist gegeben durch i(B).

Beweis: Das Supremum einer gerichteten Teilmenge A von Idl(B, ≺) ist die gerichtete Vereinigung aller Elemente von A. Diese Vereinigung bezeichnen wir mit ^{⋃ ↑}A. Offensichtlich ist ^{⋃ ↑}A = ^{⋃ ↑}_{A∈A} A wieder ein Ideal. Mengen der Form ↓x sind nach Definition untere Mengen und wegen des Interpolationsaxioms auch gerichtet, also Ideale. Jedes A ∈ Idl(B, ≺) kann geschrieben werden als A = ⋃_{a∈A} ↓a. Die Vereinigung ist gerichtet, da A gerichtet ist, und es gilt ↓a ≪ A. Damit ist i(B) als Basis des kontinuierlichen Bereichs Idl(B, ≺) nachgewiesen. □

Für die Idealvervollständigung kann man eine ”schwache universelle Eigenschaft“ zeigen:

Satz 1.11 Sei ⟨B, ≺⟩ eine abstrakte Basis und D ein kontinuierlicher Bereich. Für jede monotone Funktion f: B → D existiert eine größte stetige Funktion f̂ : Idl(B, ≺) → D mit (f̂ ∘ i)(x) ≤ f(x) für alle x ∈ B. Die Funktion f̂ ist gegeben durch f̂(A): = ^{⨆ ↑}f(A).

[figure: B; Idl(B, ≺); D; i; f; f̂]

Beweis: Um die Stetigkeit von f̂ zu prüfen, betrachten wir eine gerichtete Menge von Idealen (A_{i})_{i∈I}. Es gilt:

f̂(\begin{matrix}⨆ & ↑ \\ i∈I \end{matrix}A_{i}) = f̂(\begin{matrix}⋃ & ↑ \\ i∈I \end{matrix}A_{i})
= ^{⨆ ↑}\{f(x) | x ∈ \begin{matrix}⋃ & ↑ \\ i∈I \end{matrix}A_{i}\}
= \begin{matrix}⨆ & ↑ \\ i∈I \end{matrix}^{⨆ ↑}\{f(x) | x ∈ A_{i}\}
= \begin{matrix}⨆ & ↑ \\ i∈I \end{matrix}f̂(A_{i}).

Da f als monoton vorausgesetzt wurde, ist f(x) eine obere Schranke von f(↓x). Dies zeigt (f̂∘i)(x) ≤ f(x) für alle x ∈ B. Gibt es eine zweite Funktion g : Idl(B, ≺) → D mit dieser Eigenschaft, dann gilt: g(A) = g(⋃_{x∈A} ↓x) = ^{⨆ ↑}_{x∈A} g(↓x) = ^{⨆ ↑}_{x∈A} g(i(x)) ≤ ^{⨆ ↑}_{x∈A} f(x) = f̂(A). □

Mit den vorangegangenen Definitionen und Sätzen wurden die wichtigsten Grundlagen aus der Bereichstheorie vorgestellt. Wir wollen uns nun der Allgemeinen Algebra zuwenden.

Definition 1.12 Eine Signatur Σ = (Ω, α) besteht aus einer Menge Ω von Operationssymbolen und einer Abbildung α : Ω → ℕ, die jedem Operationssymbol eine Stelligkeit zuordnet. Eine Σ-Algebra \underline{A} = (A, J) wird durch eine Trägermenge A und eine Interpretation J der Operationssymbole definiert, derart, daß für jedes f ∈ Ω die Interpretation J (f) eine Abbildung von A^{α(f)} nach A darstellt. Man schreibt dann f_{A} statt J (f) für das Operationssymbol und spricht von der Operation f_{A} auf A.

Ein Beispiel für eine Signatur ist mit Ω = {+, −, 0} und α(+) = 2, α(−) = 1 und α(0) = 0 gegeben. Bzgl. dieser Signatur kann man auf der Menge ℤ der ganzen Zahlen mit der üblichen Interpretation der Symbole rechnen. Eine ganz andere Interpretation der Addition wird benutzt, wenn man als Trägermenge für eine Σ-Algebra bzgl. obiger Signatur die Menge ℝ^{n×n} aller (n × n)-Matrizen mit reellen Einträgen wählt.

Definition 1.13 Ein Homomorphismus zwischen zwei Σ-Algebren \underline{A} und \underline{B} ist eine Abbildung h : A → B mit der Eigenschaft, daß für alle f ∈ Ω folgende Bedingung erfüllt ist:

h (f_{A}(a_{1}, …, a_{α(f)})) = f_{B} (h(a_{1}), …, h(a_{α(f)})) .

Ein Homomorphismus erhält also die Struktur einer Algebra. Es bleibt sich gleich, ob man Elemente im Urbildraum miteinander verknüpft und dann abbildet oder erst abbildet und im Bildraum miteinander verknüpft.

Ein möglicher Homomorphismus h : ℤ → ℝ^{n×n} ist durch h(z) = z · I gegeben, wobei I die n × n-Einheitsmatrix bezeichnet.

Man kann auch auf abstrakte Weise eine Σ-Algebra definieren:

Definition 1.14 Zu einer gegebenen Menge X, deren Elemente wir als Variablen bezeichnen, erhält man auf folgende Weise die Trägermenge T_{Σ}(X) der sogenannten Termalgebra \underline{T_{Σ}(X)} über X:

(i) Für x ∈ X gilt: x ∈ T_{Σ}(X). (ii) Mit t_{1}, …, t_{n} ∈ T_{Σ}(X) und f ∈ Ω, α(f) = n, ist auch f(t_{1}, …, t_{n}) ∈ T_{Σ}(X).

Die Elemente von T_{Σ}(X) werden Terme genannt. Wendet man Operationen auf Elemente von T_{Σ}(X) an, erhält man einen neuen (längeren) Term: f_{T_{Σ}(X)}(t_{1}, …, t_{α(f)}) = f(t_{1}, …, t_{α(f)}).

Die Termalgebra \underline{T_{Σ}(X)} hat die Eigenschaft, daß jede Abbildung h : X → A, wobei \underline{A} = (A, J) eine Σ-Algebra darstellt, zu einem eindeutigen Homomorphismus h̄ : \underline{T_{Σ}(X)} → \underline{A} fortgesetzt werden kann.

Die Menge T_{Σ}(X) aller Terme über der Variablenmenge X kann auch benutzt werden, um Ungleichungen zu beschreiben: (τ_{1}, τ_{2}) ∈ T_{Σ}(X) × T_{Σ}(X) steht für die Ungleichung τ_{1} ⊑ τ_{2}. Damit eine Ungleichung in der Algebra \underline{A} ”gilt“, muß die Trägermenge A mit einer Ordnung ≤ versehen sein. Man sagt, ”die Ungleichung τ_{1} ⊑ τ_{2} gilt in \underline{A}“, wenn für alle Abbildungen h: X → A, h̄(τ_{1}) ≤ h̄(τ_{2}) erfüllt ist. Das Paar (h̄(τ_{1}), h̄(τ_{2})) nennt man dann eine Instanz der betrachteten Ungleichung. Ein Beispiel für eine Ungleichung, die in den natürlichen Zahlen mit der üblichen Ordnung und Addition gilt, ist x ⊑ x + y. Eine Instanz dieser Ungleichung ist dann (3, 3 + 5).

2 Konstruktion freier Bereichsalgebren

In der Allgemeinen Algebra sucht man für jede Klasse von Algebren, wie zum Beispiel für die Klasse der Gruppen oder die Klasse der Ringe, ein allgemeinstes Objekt dieser Klasse. Diese sogenannte freie Algebra erhält man, indem man die Termalgebra nach der Kongruenzrelation faktorisiert, die von den die Klasse definierenden Gleichungen erzeugt wird (vgl. auch [2]). Die Frage nach einem universellen Objekt bzgl. einer Signatur und vorgegebenen (Un)-Gleichungen übertragen wir nun auf kontinuierliche Bereiche, d.h. wir betrachten nicht mehr Mengen, sondern kontinuierliche Bereiche als Erzeuger von Algebren. Wir wollen in diesem Kapitel zu einem gegebenen kontinuierlichen Bereich D und einer Bereich-geordneten Signatur Σ sowie zu einer vorgegebenen Menge E von Ungleichungen die freie Bereichsalgebra \underline{F (D)} über D konstruieren. Wir werden in ähnlicher Weise wie in der Allgemeinen Algebra vorgehen, wobei das ”Faktorisieren“ in der Definition einer Approximationsordnung besteht; die Basen der betrachteten kontinuierlichen Bereiche spielen dabei eine wichtige Rolle. Bevor wir das Problem genauer fassen und dann lösen können, bedarf es noch der Klärung einiger Begriffe:

Definition 2.1 Eine Bereich-geordnete Signatur Σ = (Ω, ≤_{op}, α) ist eine Signatur, deren Menge Ω von Operationssymbolen bzgl. einer Ordnungsrelation ≤_{op} einen kontinuierlichen Bereich bildet. Für die Stelligkeiten α : Ω → ℕ der Operationssymbole gilt:

f ≤_{op} g ⇒ α(f) = α(g) für f, g ∈ Ω.

Die Definition einer Signatur aus Kapitel 1 (Definition 1.12) stellt einen Spezialfall der obigen Definition dar: Die einzelnen Operationen sind unvergleichbar und damit trivial geordnet. Ein einfaches Beispiel einer Bereich-geordneten Signatur bildet \overline{ℝ}_{+}, wenn man die reellen Zahlen als einstellige Operationssymbole (skalare Multiplikation) auffaßt: Es gilt α(r) = 1 für alle r ∈ \overline{ℝ}_{+}, und r ≤_{op} s ⇔ r ≤ s in \overline{ℝ}_{+}.

[figure: ·; ·; ·; 0; ∞; \overline{ℝ}_{+}]

Man könnte Definition 2.1 noch allgemeiner formulieren, indem man fordert, daß (Ω, ≤_{op}) nur einen Bereich bildet; die Eigenschaft von Ω, eine Basis zu besitzen, ist für die Konstruktion der freien Algebra von Bedeutung. Deshalb wurde die obige Form der Definition gewählt. Wichtig ist, daß nur Operationssymbole mit gleichen Stelligkeiten verglichen werden können. Der kontinuierliche Bereich Ω läßt sich also in kontinuierliche Teilbereiche Ω_{n}: = α^{−1}(n) = {f ∈ Ω | α(f) = n} zerlegen. Bzgl. einer Bereich-geordneten Signatur können wir nun definieren:

Definition 2.2 Eine Bereichsalgebra \underline{A} ist eine Algebra bzgl. einer Bereichgeordneten Signatur Σ, deren Trägermenge A so mit einer Ordnungsrelation versehen ist, daß sie einen kontinuierlichen Bereich bildet und die Auswertungsfunktionen eval_{n} : Ω_{n} × A^{n} → A, f(a_{1}, …, a_{n}) ↦ f_{A}(a_{1}, …, a_{n}), stetig sind. Für Homomorphismen zwischen Bereichsalgebren fordern wir ebenfalls Stetigkeit.

Um später mit Basen arbeiten zu können, fordern wir auch in Definition 2.2 kontinuierliche Bereiche statt, allgemeiner formuliert, nur Bereiche.

Eine Bereichsalgebra nach Definition 2.2 ist zum Beispiel (\overline{ℝ}_{+})^{m}, die Menge aller m-Tupel mit Einträgen aus \overline{ℝ}_{+}, bzgl. der Bereich-geordneten Signatur mit Ω: = \{+, 0, \overline{ℝ}_{+}\}. Die Ordnung auf (\overline{ℝ}_{+})^{m} ist wie üblich komponentenweise definiert: (x_{1}, …, x_{m}) ≤ (y_{1}, …, y_{m}) : ⇔ x_{i} ≤ y_{i} in \overline{ℝ}_{+} für i = 1, … m. Als Interpretation der Operationssymbole benutzt man die übliche, die Addition und die skalare Multiplikation müssen allerdings für das Element ∞ noch extra erklärt werden. Da α(+) = 2, α(0) = 0 und α(r) = 1 für alle r ∈ \overline{ℝ}_{+} gilt, ist die Stetigkeit der Auswertungsfunktionen eval_{n} : Ω_{n} × ((\overline{ℝ}_{+})^{m})^{n} → (\overline{ℝ}_{+})^{m} leicht zu überprüfen.

Wir wollen nun das hier betrachtete Problem formulieren: Es sei eine Bereich-geordne-te Signatur Σ und bzgl. dieser Signatur eine Menge E von Ungleichungen vorgegeben. Zu einem gegebenen kontinuierlichen Bereich D wollen wir eine Bereichsalgebra \underline{F (D)} und eine stetige Funktion η : D → F (D) konstruieren, so daß \underline{F (D)} den Ungleichungen aus E genügt und die universelle Eigenschaft besitzt, also zu jeder solchen Bereichsalgebra \underline{A} und jeder stetigen Funktion h : D → A genau ein stetiger Homomorphismus ext(h) : \underline{F (D)} → \underline{A} mit ext(h) ∘ η = h existiert.

Die universelle Eigenschaft der gesuchten Bereichsalgebra \underline{F (D)} kann man durch folgendes Diagramm veranschaulichen:

[figure: D; F (D); A; η; ∀h; \underline{F (D)}; ext(h); \underline{A}; ∃! ext(h)]

Der Weg zur Lösung dieses Problems führt über die Basen der betrachteten kontinuierlichen Bereiche. Wir wählen dazu eine Basis B von D und eine Basis B von Ω. Nach Satz 1.8 bilden ⟨B, ≪⟩ und ⟨B, ≪_{op}⟩ dann abstrakte Basen. Unser Ziel ist es, eine abstrakte Basis ⟨F B, ≺⟩ für die gesuchte freie Bereichsalgebra \underline{F (D)} zu konstruieren. Um im weiteren zwischen Termen mit Operationssymbolen aus ganz Ω und denen mit Operationssymbolen aus der Basis B unterscheiden zu können, bezeichnen wir mit T_{Ω}(X) die Menge aller Terme über der Variablenmenge X bzgl. der Signatur Σ mit Operationssymbolen aus Ω und mit T_{B}(X) entsprechend die andere Menge. Wir schreiben dann (τ_{1}, τ_{2}) ∈ E ⊆ T_{Ω}(X) × T_{Ω}(X) für die Ungleichung τ_{1} ⊑ τ_{2}.

Wir müssen bei der Konstruktion nicht nur wie in der Allgemeinen Algebra die Ungleichungsmenge E, sondern auch die Approximationsordnung auf B berücksichtigen. Um diese beiden Aspekte später miteinander verbinden zu können, fordern wir für E eine Art ”Interpolationseigenschaft“. Dazu führen wir auf T_{Ω}(X) induktiv die Relation ≺_{E} ein: Axiom: x ≺_{E} x für alle x ∈ X, Regel: Mit σ_{1} ≺_{E} τ_{1}, …, σ_{n} ≺_{E} τ_{n} und f, g ∈ Ω mit α(f) = α(g) = n und f ≪_{op} g ist auch f(σ_{1}, …, σ_{n}) ≺_{E} g(τ_{1}, …, τ_{n}).

Für die Ungleichungsmenge E fordern wir nun die folgende Eigenschaft:

(∗) Zu jeder Ungleichung (τ_{1}, τ_{2}) ∈ E und jedem Term δ ∈ T_{B}(X) mit δ ≺_{E} τ_{1} existiert eine Ungleichung (τ′_{1}, τ′_{2}) ∈ E mit τ′_{1}, τ′_{2} ∈ T_{B}(X), für die gilt: δ ≺_{E} τ′_{1}

und τ′_{2} ≺_{E} τ_{2}.

Es muß also zu jeder Ungleichung in E eine sie ”approximierende Ungleichung“ mit Termen aus T_{B}(X) geben. Graphisch kann man Bedingung (∗) folgendermaßen darstellen:

[figure: δ; τ′_{1}; τ′_{2}; τ_{1}; τ_{2}; ≺_{E}; ≺_{E}; ≺_{E}; ⊑; ⊑]

Bemerkung 2.3 Für die Konstruktion der freien Bereichsalgebra genügt es, die Existenz einer endlichen Kette ”approximierender Ungleichungen“ zu fordern. Die obige Form der Bedingung (∗) ist jedoch prägnanter (vgl. Bemerkung 2.9).

Ist Ω trivial geordnet, erfüllt E die Bedingung (∗) stets mit (τ′_{1}, τ′_{2}) := (τ_{1}, τ_{2}). Dieser Fall wird in [1] behandelt. Auch in anderen Fällen stellt die Bedingung (∗) keine übermäßige Forderung an E dar, wie wir an einem Beispiel verdeutlichen wollen. Wir betrachten dazu nochmal die Bereich-geordnete Signatur \overline{ℝ}_{+} und wählen als Basis ⟨ℚ_{+}, <⟩. Die Ungleichungsmenge E möge aus den Ungleichungen (r · s)(x) ⊑ r(s(x)) mit r, s ∈ \overline{ℝ}_{+} bestehen. Gilt nun q(x) ≺_{E} (r · s)(x) für einen Term q(x) ∈ T_{ℚ_{+}}(X), dann gilt nach Definition von ≺_{E} für die Zahl q ∈ ℚ_{+}, q < r · s. Durch einfache Rechnung lassen sich zwei Zahlen q_{1}, q_{2} ∈ ℚ_{+} finden mit q = q_{1} · q_{2} und q_{1} < r und q_{2} < s. Damit existieren auch p_{1}, p_{2} ∈ ℚ_{+} mit q_{1} < p_{1} < r und q_{2} < p_{2} < s. Dann gilt (p_{1} ·p_{2})(x) ⊑ p_{1}(p_{2}(x)) ist eine Ungleichung aus E mit Termen aus T_{ℚ_{+}}(X), q(x) ≺_{E} (p_{1} · p_{2})(x) und p_{1}(p_{2}(x)) ≺_{E} r(s(x)). Wir haben also eine ”approximierende Ungleichung“ gefunden. Nach diesen Vorbemerkungen können wir uns mit der eigentlichen Konstruktion beschäftigen. Wir gehen wie in der Allgemeinen Algebra vor und legen als Trägermenge F B der gesuchten abstrakten Basis die Menge T_{B}(B) aller Terme über B mit Operationssymbolen aus B zugrunde. Über die Ungleichungen und die Approximationsordnung auf B haben wir in natürlicher Weise zwei Relationen auf F B gegeben. Die erste, die wir mit ⊏ ∼ bezeichnen wollen, wird mittels der Ungleichungen eingeführt: Axiome: (A1) t ⊏ ∼ t für alle t ∈ F B. (A2) s ⊏ ∼ t, wenn dies eine Instanz einer Ungleichung aus E ist. Regeln: (R1) Ist f ∈ B ein n-stelliges Operationssymbol und s_{1} ⊏ ∼ t_{1}, …, s_{n} ⊏ ∼ t_{n}, dann ist auch f(s_{1}, …, s_{n}) ⊏ ∼ f(t_{1}, …, t_{n}). (R2) Aus s ⊏ ∼ t und t ⊏ ∼ u folgt s ⊏ ∼ u.

Die Relation ⊏ ∼ definiert eine mit den Operationen verträgliche Präordnung auf F B. Zu beachten ist, daß mit der Relation ⊏ ∼ nicht alle Ungleichungen (τ_{1}, τ_{2}) ∈ E berücksichtigt werden, sondern nur solche, für die τ_{1}, τ_{2} ∈ T_{B}(X) gilt.

Die zweite Relation ≺^{s} wird wie ⊏ ∼ induktiv definiert und besitzt ähnliche Eigenschaften, ist aber im Gegensatz zu letzterer im allgemeinen nicht reflexiv, da sie sich auf die Approximationsordnung von B stützt: Axiom: (A) a ≺^{s} b, wenn a ≪ b in B. Regel: (R) Ist s_{1} ≺^{s} t_{1}, …, s_{n} ≺^{s} t_{n} und f ≪_{op} g für f, g ∈ B mit α(f) = α(g) = n, dann gilt auch f(s_{1}, …, s_{n}) ≺^{s} f(t_{1}, …, t_{n}).

Bemerkung 2.4 Die auf T_{Ω}(X) eingeführte Relation ≺_{E} stellt einen Spezialfall von ≺^{s} dar. Während ≺_{E} nur die Approximationsordnung auf den Operationssymbolen berücksichtigt und strukturell gleiche Terme in Relation setzt, stellt ≺^{s} noch zusätzlich eine Beziehung zwischen den Konstanten her. Ist der gegebene kontinuierliche Bereich D trivial geordnet, entsprechen sich die Relationen ≺_{E} und ≺^{s}.

Allein aufgrund der Definition von ≺^{s} können wir zeigen:

Satz 2.5 ⟨F B, ≺^{s}⟩ ist eine abstrakte Basis.

Beweis: Da ≪ und ≪_{op} transitive Relationen sind und ≺^{s} nur Terme derselben Bauart in Beziehung setzt, ist auch ≺^{s} eine transitive Relation. Um das Interpolationsaxiom zu überprüfen, nehmen wir an, es gelte s ≺^{s} t für alle s einer endlichen Menge M ⊆ F B. Für jede Konstante a, die in t auftritt, sei M_{a} die Menge der Konstanten, die in den Termen s ∈ M an denselben Stellen stehen wie a in t. Da M_{a} endlich ist und M_{a} ≪ a nach Definition von ≺^{s} gilt, finden wir nach Satz 1.8 ein interpolierendes Element a′ ∈ B zwischen M_{a} und a. Ebenso verfahren wir mit den Operationen: Für jedes Element f in t sei M_{f} die Menge der Operationen, die in einem der Terme s an derselben Stelle auftreten wie f in t. Die Menge M_{f} ist endlich, und M_{f} ≪_{op} f gilt nach Definition von ≺^{s}. Da neben ≪ auch ≪_{op} das Interpolationsaxiom erfüllt, existiert ein f′ ∈ B mit M_{f} ≪_{op} f′ ≪_{op} f. Sei nun t′ der Term, in dem alle Konstanten und Operationen durch ihre entsprechenden interpolierenden Elemente ersetzt werden. Aufgrund der Konstruktion interpoliert t′ zwischen M und t in bezug auf ≺^{s}. □

Aus Bemerkung 2.4 und Satz 2.5 folgt sofort:

Korollar 2.6 ⟨T_{B}(X), ≺_{E}⟩ ist eine abstrakte Basis.

Wie sollen nun die beiden Relationen ⊏ ∼ und ≺^{s} miteinander verbunden werden? Aus der Theorie der Bereiche wissen wir, daß im Falle s_{1} ≤ t_{1} ≪ t_{2} ≤ s_{2} auch s_{1} ≪ s_{2} gilt. Diese Tatsache wollen wir auf die hier betrachteten Relationen anwenden und definieren daher als Approximationsordnung auf F B die Relation ≺ als die transitive Hülle von ⊏ ∼ ∘ ≺^{s} ∘ ⊏ ∼. Bevor wir jedoch zeigen können, daß F B bzgl. der eben definierten Relation ≺ eine abstrakte Basis bildet, müssen wir noch etwas Vorarbeit leisten und einige ziemlich technische, aber sehr nützliche Eigenschaften beweisen. Hier kommt die Bedingung (∗), die wir an die Ungleichungsmenge E gestellt haben, ins Spiel. Aufgrund der Definition von ⊏ ∼ wirkt nicht nur E auf die Konstruktion ein, sondern eine Ungleichungsmenge E′ ⊆ T_{B}(X) × T_{B}(X), die durch E induziert wird und zusätzlich noch aus den Ungleichungen besteht, die mittels Reflexivität, Operationsverträglichkeit und Transitivität hinzugefügt werden können. Formal können wir E′ folgendermaßen einführen: Axiome:

(1) (σ, σ) ∈ E′,

(2) (τ_{1}, τ_{2}) ∈ E′, falls dies eine Instanz einer Ungleichung aus E in T_{B}(X) ist. Regeln:

(3) Für ein n-stelliges Operationssymbol f ∈ B und (σ_{1}, τ_{1}), …, (σ_{n}, τ_{n}) ∈ E′ ist auch (f(σ_{1}, …, σ_{n}), f(τ_{1}, …, τ_{n})) ∈ E′,

(4) Mit (τ_{1}, τ_{2}), (τ_{2}, τ_{3}) ∈ E′ ist auch (τ_{1}, τ_{3}) ∈ E′. Die Elemente aus E′ beschreiben damit eine mit den Operationen verträgliche Präordnung ⊑ auf T_{B}(X). Wir haben damit auf zwei verschiedenen Ebenen jeweils zwei Relationen eingeführt, die wir zusammenfassend einander gegenüberstellen wollen:

Syntax  Semantik
Trägermenge:  T_{B}(X)  F B = T_{B}(B)
Präordnung:  ⊑  ⊏ ∼
Ordnungsrelation:  ≺_{E}  ≺^{s}
Abstrakte Basis: ⟨T_{B}(X), ≺_{E}⟩ ⟨F B, ≺^{s}⟩

Die auf F B eingeführten Relationen entsprechen, strukturell gesehen, denen auf T_{B}(X). Diese Tatsache wollen wir ausnutzen und zeigen einige Aussagen auf der syntaktischen Ebene und übertragen sie anschließend auf F B. Wir beweisen daher zunächst:

Satz 2.7 (1) Für alle n ≤ m ∈ ℕ gilt: (⊑ ∘ ≺_{E} ∘ ⊑)^{n} ⊆ (⊑ ∘ ≺_{E} ∘ ⊑)^{m}.

(2) Erfüllt E die Bedingung (∗), dann genügt E′ der schwächeren Bedingung (∗_{s}):

(∗_{s}) Zu jeder Ungleichung (σ, τ) ∈ E′ und jedem Term δ ∈ T_{B}(X) mit δ ≺_{E} σ existieren endlich viele Ungleichungen (σ_{1}, τ_{1}), …, (σ_{m}, τ_{m}) ∈ E′ mit δ ≺_{E} σ_{1},

τ_{i} ≺_{E} σ_{i+1} für i = 1, …, m − 1 und τ_{m} ≺_{E} τ.

Bemerkung 2.8 Die Aussage von Satz 2.7.(2) läßt sich auch noch folgendermaßen formulieren: Das Relationenprodukt ≺_{E} ∘ ⊑ ist enthalten in einer endlichen Kette der Form ≺_{E} ∘ ⊑ ∘ ≺_{E} … ⊑ ∘ ≺_{E} = (≺_{E} ∘ ⊑)^{t}∘ ≺_{E}.

[figure: ≺_{E}; ≺_{E}; ≺_{E}; ≺_{E}; ≺_{E}; δ; σ_{1}; τ_{1}; σ_{2}; τ_{2}; σ_{m}; τ_{m}; σ; τ; ⊑; ⊑; ⊑; ⊑]

Bemerkung 2.9 Die Aussage von Satz 2.7.(2) bleibt richtig, wenn man für E selbst die schwächere Bedingung (∗_{s}) fordert.

Beweis von Satz 2.7: (1) Da ⟨T_{B}(X), ≺_{E}⟩ eine abstrakte Basis ist, gilt ≺_{E}=≺_{E} ∘ ≺_{E} und damit auch ≺_{E} ⊆ ≺_{E} ∘ ⊑ ∘ ≺_{E} wegen der Reflexivität von ⊑. Hieraus folgt sofort:

⊑ ∘ ≺_{E} ∘ ⊑ ⊆ ⊑ ∘ ≺_{E} ∘ ⊑ ∘ ≺_{E} ∘ ⊑ ⊆ (⊑ ∘ ≺_{E} ∘ ⊑) ∘ (⊑ ∘ ≺_{E} ∘ ⊑).

Der allgemeine Fall folgt durch Induktion.

(2) Für Ungleichungen (σ, σ) ∈ E′ und δ ∈ T_{B}(X) mit δ ≺_{E} σ gibt es wegen des Interpolationsaxioms ein σ′ mit δ ≺_{E} σ′ ≺_{E} σ; die Ungleichung (σ,′ σ′) ist ein Element aus E′. Somit gilt δ ≺_{E} σ′ ⊑ σ′ ≺_{E} σ, und (∗_{s}) ist mit m = 1 erfüllt. Es sei jetzt (σ, τ) ∈ E′ eine Instanz der Ungleichung (σ̂, τ̂) ∈ E; somit existiert eine Abbildung h : X → T_{B}(X) mit h̄(σ̂) = σ und h̄(τ̂) = τ. Es gelte δ ≺_{E} σ für einen Term δ ∈ T_{B}(X). Damit existieren eine Abbildung g : X → T_{B}(X) und ein Term δ̂ ∈ T_{B}(X) mit ḡ(δ̂) = δ, g(x) ≺_{E} h(x) für alle x ∈ X und δ̂ ≺_{E} σ̂. Da E nach Voraussetzung die Bedingung (∗) erfüllt, gibt es für (σ̂, τ̂) ∈ E und δ̂ ≺_{E} σ̂ eine Ungleichung (σ̂′, τ̂′) ∈ E mit σ̂′, τ̂′ ∈ T_{B}(X) und δ̂ ≺_{E} σ̂′ und τ̂′ ≺_{E} τ̂. Mit dem Interpolationsaxiom findet man nun eine Abbildung h′ : X → T_{B}(X), so daß g(x) ≺_{E} h′(x) ≺_{E} h(x) für alle x ∈ X. Es gilt dann nach Konstruktion: δ = ḡ(δ̂) ≺_{E} h̄′(σ̂′) ⊑ h̄′(τ̂′) ≺_{E} h(τ̂) = τ und die Bedingung (∗_{s}) ist mit m = 1 erfüllt. Wir haben bis jetzt für eine Induktion den Anfang gesetzt. Es sei nun (f(σ_{1}, …, σ_{n}), f(τ_{1}, …, τ_{n})) ∈ E′ und es gelte δ ≺_{E} f(σ_{1}, …, σ_{n}) für den Term δ := g(δ_{1}, …, δ_{n}) ∈ T_{B}(X). Nach Regel (3) gilt für i = 1, … n, (σ_{i}, τ_{i}) ∈ E′, und nach Definition von ≺_{E} ist δ_{i} ≺_{E} σ_{i}. Aufgrund der Induktionsvoraussetzung existiert für jedes i eine endliche Kette der Form δ_{i} ≺_{E} σ_{i}^{(1)} ⊑ τ_{i}^{(1)} ≺_{E} σ_{i}^{(2)} ⊑ τ_{i}^{(2)} … ≺_{E} σ_{i}^{(m)} ⊑ τ_{i}^{(m)} ≺_{E} τ_{i}. Wegen Satz 2.7.(1) können alle diese Ketten auf dieselbe Länge m ausgedehnt werden. Wir betrachten nun die Operationen: Es gilt g ≪_{op} f nach Definition von ≺_{E}. Durch m-maliges Anwenden des Interpolationsaxioms erhält man f′_{1}, …, f′_{m} mit g ≪_{op} f′_{1} ≪_{op} f′_{2} ≪_{op} … ≪_{op} f′_{m} ≪_{op} f. Diese Operationen können nun auf die zuvor betrachteten Ketten angewandt werden; es folgt : δ := g(δ_{1}, …, δ_{n}) ≺_{E} f′_{1}(σ_{1}^{(1)}, …, σ_{n}^{(1)}) ⊑ f′_{1}(τ_{1}^{(1)}, …, τ_{n}^{(1)}) ≺_{E} f′_{2}(σ_{1}^{(2)}, …, σ_{n}^{(2)}) … ≺_{E} f′_{m}(σ_{1}^{(m)}, …, σ_{n}^{(m)}) ⊑ f′_{m}(τ_{1}^{(m)}, …, τ_{n}^{(m)}) ≺_{E} f(τ_{1}, …, τ_{n}). Die Bedingung (∗_{s}) ist also für Regel (3) erfüllt. Für die Regel (4) gelte (τ_{1}, τ_{2}), (τ_{2}, τ_{3}) ∈ E′ und damit auch (τ_{1}, τ_{3}) ∈ E′. Es sei δ ∈ T_{B}(X) mit δ ≺_{E} τ_{1}. Nach Induktionsvoraussetzung existiert eine endliche Kette der Form δ ≺_{E} σ′_{1} ⊑ τ′_{1} ≺_{E} … σ′_{m} ⊑ τ′_{m} ≺_{E} τ_{2}. Für τ′_{m} ≺_{E} τ_{2} und (τ_{2}, τ_{3}) ∈ E′ existiert mit demselben Argument eine Kette τ′_{m} ≺_{E} σ′′_{1} ⊑ τ′′_{1} ≺_{E} … σ′′_{k} ⊑ τ′′_{k} ≺_{E} τ_{3}. Diese beiden Ketten ergeben eine Kette der ”Länge“ m + k, nämlich δ ≺_{E} σ′_{1} ⊑ τ′_{1} ≺_{E} … σ′_{m} ⊑ τ′_{m} ≺_{E} σ′′_{1} ⊑ τ′′_{1} ≺_{E} … σ′′_{k} ⊑ τ′′_{k} ≺_{E} τ_{3}. Damit ist (∗_{s}) auch für Regel (4) erfüllt. □

Nach diesem Exkurs wollen wir zu unserem eigentlichen Problem zurückkehren und die Verknüpfung der Relationen ≺^{s} und ⊏ ∼ auf F B betrachten. Wir können nun zeigen:

Satz 2.10 (1) Für alle n ≤ m ∈ ℕ gilt: (⊏ ∼ ∘ ≺^{s} ∘ ⊏ ∼)^{n} ⊆ (⊏ ∼ ∘ ≺^{s} ∘ ⊏ ∼)^{m}.

(2) Zu s ≺^{s} t ⊏ ∼ u gibt es t′_{1}, u′_{1}, …, t′_{n}, u′_{n} mit s ≺^{s} t′_{1} ⊏ ∼ u′_{1} ≺^{s} … ≺^{s} t′_{n} ⊏ ∼ u′_{n} ≺^{s} u.

Beweis: (1) Der Beweis verläuft analog zum Beweis von Satz 2.7.(1).

(2) Es gelte s ≺^{s} t ⊏ ∼ u. Die Relation ≺^{s} berücksichtigt die Approximationsordnung ≪ auf den Elementen von B und die Approximationsordnung ≪_{op} auf den Operationssymbolen. Man kann also ≺^{s} auch eindeutig schreiben als das Relationenprodukt ≺^{se} ∘ ≺^{so} oder als ≺^{so} ∘ ≺^{se}, wobei x ≺^{se} y bedeutet, daß die Konstanten in x weit unter denen in y liegen, jedoch die Terme ansonsten identisch sind; bei der Relation ≺^{so} ”wachsen“ nur die Operationen, die Elemente aus B ändern sich nicht. Dieses Faktorisieren von ≺^{s} wollen wir ausnutzen und schreiben dazu s ≺^{s} t ⊏ ∼ u in der Form s ≺^{se} δ ≺^{so} t ⊏ ∼ u. Um auf δ ≺^{so} t ⊏ ∼ u Satz 2.7.(2) anwenden zu können, ersetzen wir in δ, t und u die Konstanten aus B eineindeutig durch Variablen und erhalten Terme δ̂, t̂und û aus T_{B}(X). Es gilt nach Konstruktion δ̂ ≺_{E} t̂und (t̂, û) ∈ E′. Satz 2.7.(2) liefert Terme t_{i}, u_{i}, i = 1, … n, n ∈ ℕ, mit (t_{i}, u_{i}) ∈ E′ für alle i, u_{i} ≺_{E} t_{i+1} für i = 1, …, n − 1, und δ̂ ≺_{E} t_{1} und u_{n} ≺_{E} û. In dieser Kette von Termen müssen nun die Variablen wieder durch Konstanten aus B ersetzt werden. Benutzt man dafür eine beliebige Funktion σ : X → B, erhält man zwar σ̄(t_{i}) ⊏ ∼ σ̄(u_{i}), denn dies ist eine Instanz der betrachteten Ungleichung, und σ̄(u_{i}) ≺^{so} σ̄(t_{i+1}), aber es gilt nicht σ̄(u_{i}) ≺^{s} σ̄(t_{i+1}) wie gefordert. Es darf nicht dieselbe Funktion σ für u_{i} und t_{i+1} benutzt werden, da sonst die Elemente nicht ”wachsen“. Um nun ein geeignetes σ = (σ_{i}), i = 1, … n, zu finden, geht man folgendermaßen vor: Zu jeder Variablen x, die in irgendeinem Term t_{i}, u_{i} oder in den Herleitungen für (t_{i}, u_{i}) ∈ E′ vorkommt, sei M_{x} die Menge der Konstanten, die in s an den Stellen stehen, die x in δ̂ einnimmt. Bei der Betrachtung von M_{x} ergeben sich drei Fälle: Fall 1: Die Variable x kommt weder in t̂ noch in û vor; damit ist M_{x} leer. Fall 2: Die Variable x kommt nicht in t̂, aber in û vor; M_{x} ist auch in diesem Fall leer, es existiert aber zusätzlich eine Konstante c_{x} ∈ B, die beim Übergang von δ, t und u zu δ̂, t̂ und û durch x ersetzt wurde. Fall 3: Die Variable x kommt in t̂vor. Dann ist M_{x} nicht leer, und wiederum existiert eine Konstante c_{x}. Für den ersten Fall wähle man eine beliebige Kette c_{x}^{1} ≪ c_{x}^{2} … ≪ c_{x}^{n} in B; im zweiten und im dritten Fall sind mit M_{x} ≪ c_{x}, M_{x} endlich, die Voraussetzungen geschaffen, um das Interpolationsaxiom auf B anzuwenden. Man erhält so eine Kette M_{x} ≪ c_{x}^{1} ≪ c_{x}^{2} … c_{x}^{n} ≪ c_{x} in B, wobei im zweiten Fall M_{x} ≪ c_{x}^{1} keine echte Bedingung darstellt, da M_{x} ja leer ist. Es sei nun σ_{i} : X → B die Funktion, die x auf die Konstante c_{x}^{i} abbildet. Es gilt wieder σ̄_{i}(t_{i}) ⊏ ∼ σ̄_{i}(u_{i}) (dies ist eine weitere Instanz der Ungleichung (t_{i}, u_{i}) ∈ E′). Jetzt haben wir aber auch σ̄_{i}(u_{i}) ≺^{s} σ̄_{i+1}(t_{i+1}) oder ausführlicher σ̄_{i}(u_{i}) ≺^{se} σ̄_{i+1}(u_{i}) ≺^{so} σ̄_{i+1}(t_{i+1}). Wegen M_{x} ≪ c_{x}^{1} für alle x, die in δ̂ vorkommen, ist auch s ≺^{se} σ̄_{1}(δ̂) ≺^{so} σ̄_{1}(t_{1}) und damit s ≺^{s} σ̄_{1}(t_{1}). Schließlich gilt σ̄_{n}(u_{n}) ≺^{so} σ̄_{n}(û) ≺^{se} u und deshalb σ̄_{n}(u_{n}) ≺^{s} u. Insgesamt erhalten wir die gewünschte Kette s ≺^{s} σ̄_{1}(t_{1}) ⊏ ∼ σ̄_{1}(u_{1}) ≺^{s} σ̄_{2}(t_{2}) … σ̄_{n}(t_{n}) ⊏ ∼ σ̄_{n}(u_{n}) ≺^{s} u. □

Mit diesen Eigenschaften des Relationenprodukts können wir nun für die Relation ≺:= (⊏ ∼ ∘ ≺^{s} ∘ ⊏ ∼)^{t} auf F B leicht zeigen:

Satz 2.11 ⟨F B, ≺⟩ ist eine abstrakte Basis.

Beweis: Da die Transitivität per definitionem gegeben ist, müssen wir nur das Interpolationsaxiom überprüfen. Es gelte M ≺ t für eine endliche Menge M. Aus der Definition von ≺ erhalten wir für jedes s ∈ M eine Kette von Termen s ⊏ ∼ s^{1} ≺^{s} s^{2} ⊏ ∼ … ⊏ ∼ s^{n(s)−1} ≺^{s} s^{n(s)} ⊏ ∼ t. Die letzten zwei Schritte können nach Satz 2.10.(2) durch die Kette s^{n(s)−1} ≺^{s} t′_{1} ⊏ ∼ u′_{1} ≺^{s} t′_{2} … ≺^{s} t′_{m} ⊏ ∼ u′_{m} ≺^{s} t ersetzt werden. Die Menge aller u′_{m} ist endlich; damit existiert nach Satz 2.5 ein u mit u′_{m} ≺^{s} u ≺^{s} t für alle u′_{m}. Mit der Reflexivität von ⊏ ∼ folgt dann M ≺ u ≺ t wie gewünscht. □

Somit können wir als Trägermenge der freien Bereichsalgebra über D die Idealvervollständigung von F B nehmen. Nach Satz 1.10 ist dies ein kontinuierlicher Bereich. Die Operationen auf F (D) = Idl(F B, ≺) sind punktweise definiert: Für Ideale A_{1}, …, A_{n} und f ∈ Ω mit α(f) = n sei f_{F (D)}(A_{1}, …, A_{n}) := ↓{g(a_{1}, …, a_{n}) | g ∈ B, g ≪_{op} f, a_{1} ∈ A_{1}, …, a_{n} ∈ A_{n}}.

Wir müssen prüfen, ob f_{F (D)}(A_{1}, …, A_{n}) wohldefiniert, also wieder ein Ideal ist. Eine untere Menge ist es nach Definition; zu prüfen gilt, ob f_{F (D)}(A_{1}, …, A_{n}) gerichtet ist. Es seien x, y ∈ f_{F (D)}(A_{1}, …, A_{n}), d.h. x ≺ g(s_{1}, …, s_{n}), y ≺ h(t_{1}, …, t_{n}) für gewisse s_{1}, t_{1} ∈ A_{1}, …, s_{n}, t_{n} ∈ A_{n} und g, h ≪_{op} f. Da A_{1}, …, A_{n} Ideale, also insbesondere gerichtet sind, finden wir u_{1} ∈ A_{1}, …, u_{n} ∈ A_{n} mit s_{1}, t_{1} ≺ u_{1}, …, s_{n}, t_{n} ≺ u_{n}. Jede Beziehung s_{i} ≺ u_{i}, i = 1, … n, läßt sich aufspalten in eine Kette der Form s_{i} ⊏ ∼ s_{i}^{1} ≺^{s} s_{i}^{2} ⊏ ∼ … ≺^{s} s_{i}^{m(i)} ⊏ ∼ u_{i}. Analog verfahren wir mit den Paaren t_{i}, u_{i} für i = 1, … n. Mit Satz 2.10.(1) können wir alle diese Ketten auf dieselbe Länge m ausdehnen. Für die Operationen existieren wegen des Interpolationsaxioms f′_{1}, …, f′_{m} ∈ B mit {g, h} ≪_{op} f′_{1} ≪_{op} … ≪_{op} f′_{m} ≪_{op} f. Diese Operationen können wir Schritt für Schritt auf die obigen Ketten anwenden, indem wir die Regeln für ⊏ ∼ und ≺^{s} benutzen: f′_{1}(s_{1}, …, s_{n}) ⊏ ∼ f′_{1}(s_{1}^{1}, …, s_{n}^{1}) ≺^{s} f′_{2}(s_{1}^{2}, …, s_{n}^{2}) ⊏ ∼ … ≺^{s} f′_{m}(s_{1}^{m}, …, s_{n}^{m}) ⊏ ∼ f′_{m}(u_{1}, …, u_{n}). Eine ähnliche Kette erhalten wir, wenn wir die Operationen auf die Ketten zwischen t_{i} und u_{i}, i = 1, … n, anwenden. Für z := f′_{m}(u_{1}, …, u_{n}) gilt dann nach Konstruktion z ∈ f_{F (D)}(A_{1}, …, A_{n}) und x, y ≺ z.

Wir haben nun die Trägermenge und die Operationen definiert; um im Falle von \underline{F (D)} wirklich von einer Bereichsalgebra sprechen zu können, müssen die Auswertungsfunktionen eval_{n} : Ω_{n} × F (D)^{n} → F (D) stetig sein. Nach Satz 1.6 genügt es, dies in jeder Komponente zu überprüfen. Um die Stetigkeit dieser Abbildungen in der ersten Komponente nachzuweisen, wählen wir beliebige, aber feste Ideale A_{1}, …, A_{n} ∈ \underline{F (D)} und eine gerichtete Teilmenge F von B. Es gilt:

eval_{n} (\begin{matrix}⨆ & ↑ \\ f∈F \end{matrix} f, A_{1}, …, A_{n}) = (\begin{matrix}⨆ & ↑ \\ f∈F \end{matrix} f_{F (D)}) (A_{1}, …, A_{n})
= ↓ \{g(a_{1}, …, a_{n}) | g ≪_{op} \begin{matrix}⨆ & ↑ \\ f∈F \end{matrix} f, a_{i} ∈ A_{i}\}
= ↓ (\begin{matrix}⋃ & ↑ \\ f∈F \end{matrix}\{g(a_{1}, …, a_{n}) | g ≪_{op} f, a_{i} ∈ A_{i}\})
= \begin{matrix}⋃ & ↑ \\ f∈F \end{matrix} (↓ \{g(a_{1}, …, a_{n}) | g ≪_{op} f, a_{i} ∈ A_{i}\})

= \begin{matrix}⋃ & ↑ \\ f∈F \end{matrix} (f_{F (D)}(A_{1}, …, A_{n}))
= \begin{matrix}⋃ & ↑ \\ f∈F \end{matrix} eval_{n} (f, A_{1}, …, A_{n}).

Diese Aussage ist wichtig, da wir bei unserer Konstruktion von \underline{F (D)} nicht alle Operationen aus Ω, sondern nur eine Basis B berücksichtigt haben. Eine beliebige Operation g ∈ Ω läßt sich zwar als gerichtetes Supremum von Basiselementen schreiben, diese Tatsache kann man aber nur auf \underline{F (D)} übertragen, wenn dabei gerichtete Suprema erhalten bleiben. Aufgrund der Stetigkeit ist es uns erlaubt, stets nur B zu betrachten. Zur Überprüfung der Stetigkeit in der zweiten bis (n+1)-Komponente wählen wir ein festes f ∈ B und n − 1 Ideale aus F (D) sowie o.B.d.A. in der zweiten Komponente eine gerichtete Vereinigung von Idealen A_{k}, k ∈ K. Nun gilt:

eval_{n} (f, \begin{matrix}⋃ & ↑ \\ k∈K \end{matrix} A_{k}, A_{2}, …, A_{n}) = f_{F (D)}(\begin{matrix}⋃ & ↑ \\ k∈K \end{matrix} A_{k}, A_{2}, …, A_{n})
= ↓ \{g(a_{1}, …, a_{n}) | g ≪_{op} f, a_{1} ∈ \begin{matrix}⋃ & ↑ \\ k∈K \end{matrix} A_{k}, a_{i} ∈ A_{i}\}
= ↓ \begin{matrix}⋃ & ↑ \\ k∈K \end{matrix} \{g(a_{1}, …, a_{n}) | g ≪_{op} f, a_{1} ∈ A_{k}, a_{i} ∈ A_{i}\}
= \begin{matrix}⋃ & ↑ \\ k∈K \end{matrix} ↓ \{g(a_{1}, …, a_{n}) | g ≪_{op} f, a_{1} ∈ A_{k}, a_{i} ∈ A_{i}\}
= \begin{matrix}⋃ & ↑ \\ k∈K \end{matrix} f_{F (D)}(A_{k}, A_{2}, …, A_{n})
= \begin{matrix}⋃ & ↑ \\ k∈K \end{matrix} eval_{n} (f, A_{k}, A_{2}, …, A_{n}).

Wir haben somit gezeigt, daß \underline{F (D)} eine Bereichsalgebra bzgl. der Bereich-geordneten Signatur Σ ist. Um beweisen zu können, daß \underline{F (D)} frei ist, also die universelle Eigenschaft besitzt, benötigen wir eine stetige Abbildung η : D → F (D). Wir wählen für η die Einbettung von D in F (D) mittels der Fortsetzung der monotonen Inklusion von B in F B.

[figure: B; D; F (D); F B; η; ⊆; i; ∩]

Die Stetigkeit von η folgt aus Satz 1.11 und der Tatsache, daß D und Idl(B, ≪) isomorph sind. Die beiden folgenden Sätze zeigen, daß \underline{F (D)} die gesuchte Bereichsalgebra ist.

Satz 2.12 \underline{F (D)} genügt den Ungleichungen aus E.

Beweis: Es sei (τ_{1}, τ_{2}) eine Ungleichung aus E und h : X → F (D) eine Abbildung, die jeder Variablen aus X ein Ideal in F B zuordnet, also die Variablen mit Werten aus F (D) belegt. Wir müssen zeigen, daß das Ideal h̄(τ_{1}) im Ideal h̄(τ_{2}) enthalten ist. Das Ideal h̄(τ_{1}) wird von den Termen der Form k̄(τ) erzeugt, wobei τ ∈ T_{B}(X) und τ ≺_{E} τ_{1} gilt und k eine Abbildung von X nach F B ist, so daß für jede Variable x ∈ X, k(x) ∈ h(x) gilt (vgl. dazu die Definition der Operationen auf F (D), Seite 19, und das Beispiel im Anschluß an diesen Beweis). Allgemein sei nun s ∈ h̄(τ_{1}), also s ≺ k̄(τ) für ein solches τ und k. Da E die Bedingung (∗) erfüllt, existiert für (τ_{1}, τ_{2}) und τ ≺_{E} τ_{1} eine Ungleichung (τ′_{1}, τ′_{2}) ∈ E mit τ ≺_{E} τ′_{1}, τ′_{2} ≺_{E} τ_{2} und τ′_{1}, τ′_{2} ∈ T_{B}(X). Es sei nun k′ : X → F B eine Abbildung derart, daß k(x) ≺ k′(x) und k′(x) ∈ h(x). Diese Abbildung existiert, da h(x) ein Ideal, also insbesondere gerichtet ist. Es gilt nach Konstruktion k̄(τ) ≺^{s} k̄′(τ′_{1}) ⊏ ∼ k̄′(τ′_{2}) und damit s ≺ k̄′(τ′_{2}). Der Term k̄′(τ′_{2}) ist ein Element, das das Ideal h̄(τ_{2}) erzeugt. Hieraus folgt s ∈ h̄(τ_{2}) wie gewünscht. □

Um den Beweis von Satz 2.12 zu erläutern, betrachten wir als Beispiel den Term τ_{1} := x ∘ y mit der Abbildung h : x ↦ A_{1}, y ↦ A_{2}. Dann ist h̄(τ_{1}) = A_{1} ∘ A_{2} =↓ {a_{1} ⋆ a_{2} | ⋆ ∈ B, ⋆ ≪_{op} ∘, a_{1} ∈ A_{1}, a_{2} ∈ A_{2}} und somit k̄(τ) = a_{1} ⋆ a_{2} mit τ = x ⋆ y und k : x ↦ a_{1}, y ↦ a_{2}. Es gilt: τ ∈ T_{B}(X), τ ≺_{E} τ_{1} und k(x) ∈ h(x) für alle x ∈ X.

Satz 2.13 \underline{F (D)} besitzt die universelle Eigenschaft.

Beweis: Es sei eine stetige Funktion h : D → A für eine Bereichsalgebra \underline{A} gegeben, die die Ungleichungen aus E erfüllt. Die Einschränkung von h auf die Menge B ⊆ D hat eine eindeutige monotone Fortsetzung h̄ auf der prägeordneten Algebra (F B, ⊏ ∼) mittels h̄ (f_{F B}(a_{1}, …, a_{n})) := f_{A} (h(a_{1}), …, h(a_{n})) für a_{1}, …, a_{n} ∈ B und ein nstelliges Operationssymbol f. Die Funktion h̄ erhält also ⊏ ∼. Wir wollen zeigen, daß h̄ auch ≺^{s} erhält. Für ein Axiom a ≺^{s} b ist das klar, da h stetig, also insbesondere monoton auf ⟨B, ≪⟩ ist. Für die Regel (R) benutzen wir, daß h̄ ein Homomorphismus ist und die Auswertungsfunktionen eval : Ω_{n} × A^{n} → A monoton sind:

h̄ (f(s_{1}, …, s_{n})) = f_{A} (h(s_{1}), …, h(s_{n}))
≤ g_{A} (h(t_{1}), …, h(t_{n}))
= h̄ (g(t_{1}, …, t_{n})) .

Insgesamt erhält h̄ also die Approximationsordnung ≺ auf F B und kann damit zu einem Homomorphismus ext(h) auf der Idealvervollständigung F (D) mittels ext(h)(A) = ^{⨆ ↑}h̄(A) fortgesetzt werden.

[figure: D; B; F B; F (D); A; η; ⊇; ⊆; i; h; h_{|B}; h̄; ext(h)]

Daß ext(h) wirklich ein Homomorphismus ist, folgt aus der Homomorphiebedingung für h̄ und der Stetigkeit der Operationen auf \underline{A}:

ext(h) (f_{F (D)}(A_{1}, …, A_{n})) = ^{⨆ ↑} h̄ (f_{F (D)}(A_{1}, …, A_{n}))
= ^{⨆ ↑}f_{A} (h̄(A_{1}), …, h̄(A_{n}))
= f_{A} (^{⨆ ↑} h̄(A_{1}), …,^{⨆ ↑} h̄(A_{n}))
= f_{A} (ext(h)(A_{1}), …, ext(h)(A_{n})) .

Satz 1.11 liefert uns die Stetigkeit und die Eindeutigkeit von ext(h) sowie eine Hälfte der geforderten Beziehung zwischen h und ext(h), nämlich ext(h) ∘ η ≤ h. Für die umgekehrte Ungleichung betrachten wir ein Element d ∈ D. Dieses wird in F (D) durch das Ideal η(d) dargestellt. Welche Elemente aus B das Ideal η(d) enthält, kann man allgemein nicht angeben, aber nach den Axiomen für ≺^{s} umfaßt η(d) mindestens ganz B_{d} = B ∩ ↓ ↓d. Wir können nun die Stetigkeit von h ausnutzen, und es gilt:

ext(h)(η(d)) = ^{⨆ ↑} h̄(η(d))
≥ ^{⨆ ↑} h̄(B_{d})
= ^{⨆ ↑} h(B_{d})
= h(^{⨆ ↑}B_{d})
= h(d).
□

Aus Satz 2.12 und Satz 2.13 folgt nun abschließend:

Satz 2.14 \underline{F (D)} ist die freie Bereichsalgebra über D in bezug auf Σ und E.

Wir haben somit das zu Anfang gestellte Problem gelöst und einen Weg zur Konstruktion von freien Bereichsalgebren gezeigt. Eine andere Möglichkeit der Konstruktion wird in [3] dargelegt. Dort werden kategorielle Methoden benutzt, um bzgl. einer Signatur im üblichen Sinne, d.h. mit unvergleichbaren Operationssymbolen, und einer Menge von Ungleichungen die freie Bereichsalgebra zu konstruieren. Ob sich die Methoden aus [3] für Bereich-geordnete Signaturen übertragen lassen, ist nicht geklärt.

3 Freie Bereichskegel

Eine Anwendung der freien Konstruktion aus dem vorherigen Kapitel findet sich bei der Betrachtung von Bereichskegeln. Welche Probleme auftreten, wenn man mit den Methoden aus Kapitel 2 zu einem gegebenen Bereich den freien Bereichskegel konstruieren will, und worin die Gründe für diese Probleme liegen, wird in diesem Kapitel vorgestellt; Lösungsansätze werden ebenfalls aufgezeigt.

Bereichskegel sind kontinuierliche Bereiche, auf denen man mittels Addition und skalarer Multiplikation nach bestimmten Gesetzen rechnen kann und die zudem noch ein ausgezeichnetes Element besitzen. Die Skalare für die Multiplikation sind Elemente aus dem kontinuierlichen Bereich \overline{ℝ}_{+}. Dieser Bereich bildet bzgl. der üblichen Addition und Multiplikation selbst eine Algebra, wobei die Operationen für das Element ∞ folgendermaßen erklärt sind:

r + ∞ = ∞ + r = ∞ für alle r ∈ \overline{ℝ}_{+},
r · ∞ = ∞ · r = ∞ für alle r ∈ \overline{ℝ}_{+}\\{0\},
0 · ∞ = ∞ · 0 = 0.

Wir können nun Bereichskegel formal einführen:

Definition 3.1 Eine Menge C heißt reeller Kegel, wenn ein ausgezeichnetes Element 0 ∈ C existiert, sowie zwei Operationen + : C × C → C und · : \overline{ℝ}_{+} × C → C definiert sind, so daß alle a, b, c ∈ C und r, s ∈ \overline{ℝ}_{+} die folgenden Eigenschaften erfüllen:

(a + b) + c = a + (b + c)  (1)
a + b = b + a  (2)
a + 0 = a  (3)
0 · a = 0  (4)
(r · s) · a = r · (s · a)  (5)
r · (a + b) = r · a + r · b  (6)
(r + s) · a = r · a + s · a  (7)
1 · a = a.  (8)

C heißt Bereichskegel, wenn C zusätzlich ein kontinuierlicher Bereich ist und die Funktionen + : C × C → C, (a, b) ↦ a + b und · : \overline{ℝ}_{+} × C → C, (r, a) ↦ r · a stetig sind.

In einem Bereichskegel ist 0 stets das kleinste Element, da wegen der Monotonie der Skalarmultiplikation 0 = 0 · a < 1 · a = a für alle a ∈ C\{0} gilt. Die Bezeichnung ”Kegel“ deckt sich dann mit dem Begriff aus der geometrischen Anschauung: Das Element 0 stellt die Spitze des Kegels dar. Beispiele für Bereichskegel bilden spezielle Funktionenräume, wenn man sowohl die Ordnung auf den Funktionen als auch die Addition und die skalare Multiplikation punktweise definiert. Es sei uns nun ein kontinuierlicher Bereich D gegeben, über dem wir den freien Bereichskegel konstruieren wollen. Bevor wir die Methoden des vorherigen Kapitels anwenden können, müssen wir den Begriff des Bereichskegels, wie er in Definition 3.1 eingeführt wurde, in die ”Sprache“ aus Kapitel 2 übertragen. Ein Bereichskegel stellt dann eine Bereichsalgebra bzgl. der Signatur Σ = (Ω, ≤_{op}, α) mit Ω = \{+, 0, \overline{ℝ}_{+}\} und α(+) = 2, α(0) = 0 und α(r) = 1 für alle r ∈ \overline{ℝ}_{+} dar. Die Menge (Ω, ≤_{op}) ist ein kontinuierlicher Bereich mit kompakten Elementen + und 0 und \overline{ℝ}_{+} als Teilbereich. Um die Stelligkeit der skalaren Multiplikation deutlich zu machen, schreiben wir nun r(a) statt r · a. Die Ungleichungen, denen die gesuchte Bereichsalgebra genügen soll, sind durch die Gleichungen (1) - (8) aus Definition 3.1 bestimmt. Wir ersetzen die Konstanten a, b, c ∈ C in den Gleichungen durch Variablen x, y, z ∈ X und schreiben jede Gleichung in Form von zwei Ungleichungen (Beispiel: Gleichung (3) liefert x + 0 ⊑ x und x ⊑ x + 0). Wir fassen die Ungleichungen, die aus den Gleichungen (1) - (7) hervorgegangen sind, zur Menge E zusammen. Gleichung (8) aus Definition 3.1 wollen wir gesondert betrachten. Jetzt können wir wie in Kapitel 2 vorgehen: Wir wählen eine Basis B des kontinuierlichen Bereichs D und als Basis B von Ω die Menge B = {+, 0, ℚ_{+}}. Auf der Menge T_{Ω}(X) der Terme über der Variablenmenge X sei die Relation ≺_{E} wie in Kapitel 2 definiert. Insbesondere gilt x + y ≺_{E} x + y und 0 ≺_{E} 0, da + und 0 kompakte Elemente in Ω sind, und r(x) ≺_{E} s(x) für r < s in \overline{ℝ}_{+}. Um den freien Bereichskegel konstruieren zu können, müssen wir folgende Bedingung überprüfen:

(∗) Zu jeder Ungleichung (τ_{1}, τ_{2}) ∈ E und jedem Term δ ∈ T_{B}(X) mit δ ≺_{E} τ_{1} existiert eine Ungleichung (τ′_{1}, τ′_{2}) ∈ E mit τ′_{1}, τ′_{2} ∈ T_{B}(X), für die gilt: δ ≺_{E} τ′_{1}

und τ′_{2} ≺_{E} τ_{2}.

Es soll also zu jeder Ungleichung aus E eine sie ”approximierende Ungleichung“ mit Termen geben, in denen nur Basisoperationen verwendet werden. Die Menge E, so wie wir sie bisher gewählt haben, erfüllt diese Forderung.

Lemma 3.2 E genügt der Bedingung (∗).

Beweis: Da +, 0 ∈ B mit + ≪_{op} + und 0 ≪_{op} 0 gilt, kann die Bedingung (∗) für Ungleichungen, die aus den Gleichungen (1) - (4) entstanden sind, mit (τ′_{1}, τ′_{2}): = (τ_{1}, τ_{2}) erfüllt werden. Wir betrachten nun exemplarisch die Ungleichung ((r + s)(x), r(x) + s(x)) ∈ E. Es gelte q(x) ≺_{E} (r + s)(x) für einen Term q(x) ∈ T_{B}(X). Dann gilt nach Definition von ≺_{E} für q ∈ ℚ_{+} und r, s ∈ \overline{ℝ}_{+}, q < r + s. Die Zahl q läßt sich schreiben als q = q_{1} + q_{2} mit q_{1}, q_{2} ∈ ℚ_{+} und q_{1} < r und q_{2} < s. Somit finden sich auch p_{1}, p_{2} ∈ ℚ_{+} mit q_{1} < p_{1} < r und q_{2} < p_{2} < s. Die Terme (p_{1} + p_{2})(x) und p_{1}(x) + p_{2}(x) sind Elemente von T_{B}(X); es gilt: ((p_{1} + p_{2})(x), p_{1}(x) + p_{2}(x)) ist eine Ungleichung aus E, q(x) ≺_{E} (p_{1} + p_{2})(x) und p_{1}(x) + p_{2}(x) ≺_{E} r(x) + s(x). Somit ist die Bedingung (∗) in diesem Fall erfüllt. Für die restlichen Ungleichungen aus E verläuft die Konstruktion von (τ′_{1}, τ′_{2}) analog. □

Wir haben bisher die Gleichung 1(x) = x, der ein Bereichskegel genügen soll (Gleichung (8) aus Definition 3.1), noch nicht in der Ungleichungsmenge E berücksichtigt. Erweitert man E um die Ungleichungen 1(x) ⊑ x und x ⊑ 1(x), ergibt sich ein Problem. Erstere Ungleichung erfüllt zwar mit (τ′_{1}, τ′_{2}): = (1(x), x) die Bedingung (∗), da x ≺_{E} x nach den Axiomen für die Relation ≺_{E} gilt, jedoch genügt die Ungleichung x ⊑ 1(x) der geforderten Bedingung nicht. Zu x ⊑ 1(x) und x ≺_{E} x müßte man eine Ungleichung (x, q(x)) ∈ E mit q < 1 finden; eine solche Ungleichung existiert jedoch nicht.

Wir wollen daher die Konstruktion der gesuchten Bereichsalgebra ohne die Gleichung 1(x) = x durchführen. Wir gehen dabei wie im letzten Kapitel vor. Auf F B = T_{B}(B) definieren wir über die Approximationsordnung von B die Relation ≺^{s}. Mittels der Ungleichungen aus E führen wir die Relation ≈ wie die Relation ⊏ ∼ aus Kapitel 2 auf F B ein. Da mit (τ_{1}, τ_{2}) ∈ E auch (τ_{2}, τ_{1}) ∈ E gilt, ist die Relation ≈ im Gegensatz zu ⊏ ∼ symmetrisch. Mit Lemma 3.2 sind alle notwendigen Voraussetzungen erfüllt, und somit ist ⟨F B, ≺⟩ mit ≺: = (≈ ∘ ≺^{s} ∘ ≈)^{t} eine abstrakte Basis. Damit ist F (D) = Idl(F B, ≺) ein kontinuierlicher Bereich. Mit η: D → F (D) als Fortsetzung der monotonen Inklusion von B in F B erhalten wir in Analogie zu Satz 2.14 sofort

Satz 3.3 \underline{F (D)} ist die freie Bereichsalgebra über D in bezug auf Σ und E.

Wir können im Falle von \underline{F (D)} nicht vom freien Bereichskegel über D sprechen. \underline{F (D)} genügt den Gleichungen (1) - (7) aus Definition 3.1; Gleichung (8) gilt in \underline{F (D)} nicht.

Um die Gültigkeit der Gleichung 1(x) = x zu erreichen, bilden wir F (D) mit der Funktion

1I: F (D) → Im(1I) ⊆ F (D), A ↦ 1(A),

in sich selbst ab. Diese Funktion ist als Operation stetig. Wendet man die Abbildung 1I auf Im(1I) nochmal an, erhält man wegen Gleichung (5) aus Definition 3.1 die Identität: 1(1(A)) = (1 · 1)(A) = 1(A). Wir haben also mit der Funktion 1I: F (D) → Im(1I) und 1I: Im(1I) → F (D) ein stetiges Sektion-Retraktion-Paar (vgl. dazu [1], Kapitel 3). Das Bild Im(1I) von F (D) ist als Retrakt eines kontinuierlichen Bereichs selbst ein kontinuierlicher Bereich. Die Funktion 1I: F (D) → Im(1I) ist sogar ein Homomorphismus, wie sich durch einfaches Ausrechnen mittels der Gleichungen, die in \underline{F (D)} gelten, ergibt. Für die Addition gilt mit Gleichung (6): 1I(A+B) = 1(A+B) = 1(A)+1(B) = 1I(A)+1I(B). Gleichung (5) liefert für die skalare Multiplikation : 1I(r(A)) = 1(r(A)) = (1·r)(A) = (r·1)(A) = r(1(A)) = r(1I(A)). Für die ”Null“ gilt mit Gleichung (4) und (5): 1I(0) = 1(0) = 1(0(A)) = (1 · 0)(A) = 0(A) = 0. \underline{Im(1I)} ist als homomorphes Bild einer Algebra selbst eine Algebra vom selben Typ, genau genommen eine Unteralgebra von \underline{F (D)}. In \underline{Im(1I)} gilt nun neben den Gleichungen (1) - (7) aus Definition 3.1 auch noch Gleichung (8): Da jedes Element A ∈ Im(1I) von der Form 1(B), B ∈ F (D), ist, liefert Gleichung (5): 1(A) = 1(1(B)) = (1 · 1)(B) = 1(B) = A.

Wir haben bisher gezeigt, daß \underline{Im(1I)} ein Bereichskegel ist. Das hatten wir mit \underline{F (D)} nicht erreicht, dafür hatte \underline{F (D)} die ”schöne“ Eigenschaft, ”frei“ zu sein. Die universelle Eigenschaft von \underline{F (D)} wollen wir nun ausnutzen und zeigen, daß auch \underline{Im(1I)} diese Eigenschaft besitzt und damit das gesuchte Objekt, der freie Bereichskegel über D, ist. Wir bilden dazu D mittels der Verknüpfung 1I ∘ η nach Im(1I) ab. Diese Verknüpfung ist stetig, da die einzelnen Funktionen η und 1I stetig sind. Gibt es nun einen Bereichskegel \underline{A} und eine stetige Funktion h: D → A, so konnten wir bisher schon h zu einem stetigen Homomorphismus ext(h): F (D) → A fortsetzen (vgl. dazu Beweis von Satz 2.13). Diese Funktion ext(h) können wir auf Im(1I) einschränken. Die Einschränkung bezeichnen wir mit ext(h)|_{Im}.

[figure: D; F (D); A; η; h; Im(1I); 1I; ext(h); ext(h)|_{Im}]

Es gilt, wie schon früher bewiesen, ext(h) ∘ η = h. Da ext(h) ein Homomorphismus ist und \underline{A} der Gleichung 1(x) = x genügt, gilt aber auch für jedes Ideal A ∈ F (D): (ext(h)|_{Im} ∘ 1I) (A) = ext(h)|_{Im} (1(A)) = ext(h) (1(A)) = 1(ext(h)(A)) = ext(h)(A). Im Ganzen gilt ext(h)|_{Im} ∘ 1I ∘ η = h wie gefordert. Gibt es eine zweite Funktion g mit dieser Eigenschaft, dann muß, da 1I eine surjektive Abbildung ist, g = ext(h)|_{Im} sein. Somit haben wir gezeigt:

Satz 3.4 Im(1I) ist der freie Bereichskegel über D.

Wir haben zwar das gesuchte Objekt konstruiert, es hat uns jedoch einige Mühe gekostet. Wir wollen daher noch einmal überlegen, warum die Konstruktion des freien Bereichskegels über D durch eine so ”harmlose“ Gleichung wie 1(x) = x so umständlich geworden ist. Da die Ungleichung x ⊑ 1(x) nicht der Bedingung (∗) genügt, liegt es nahe zu überlegen, ob diese Bedingung nicht abgeschwächt werden kann, so daß die betrachtete Ungleichung der schwächeren Bedingung genügt und dennoch die freie Konstruktion beibehalten werden kann. Daß dies nicht möglich ist, zeigen die folgenden Beobachtungen:

Lemma 3.5 Die Konstruktion der freien Bereichsalgebra aus Kapitel 2 erhält die Approximationsordnung auf dem betrachteten Bereich.

Beweis: Da ein Bereich D durch eine Basis B bereits bestimmt ist, genügt es, die Approximationsordnung dort zu betrachten. Für a ≪ b in B gilt a ≺^{s} b in F B und damit auch a ⊏ ∼ a ≺^{s} b ⊏ ∼ b, also a ≺ b in F B. Damit gilt a ∈ ↓b wie behauptet. □

Bei der Konstruktion des freien Bereichskegels gilt a ≺ b in F B, falls a ≪ b in B, aber nicht 1(a) ≺ 1(b), denn es ist nicht 1 < 1. Das zeigt, daß man Elemente a ∈ F B nicht mit 1(a) gleichsetzen kann. Daß für zwei Elemente q(a) und p(b) aus F B nur dann q(a) ≺ p(b) gelten kann, wenn q < p in ℚ_{+} und a ≪ b in B gilt, zeigen auch Ergebnisse aus der Theorie der Bewertungen. In [4] und [5] wird gezeigt, daß zwei einfache Bewertungen, die man in gewissem Sinn als Elemente von F B betrachten kann, genau dann weit untereinander liegen, wenn die Skalare in den Darstellungen der Bewertungen weit untereinander liegen. Das Problem der Konstruktion von freien Bereichskegeln kann also mit den Methoden aus Kapitel 2 allein nicht gelöst werden. Die Bedingung (∗), die wir an die Ungleichungsmenge E stellen, ist keine notwendige Bedingung für die Existenz freier Bereichsalgebren, wie wir am Beispiel des Bereichskegels sehen. Vermutlich ist diese spezielle Algebra jedoch ein Ausnahmefall. Es lassen sich leicht Beispiele von Algebren über Bereichen konstruieren, bei denen die Bedingung (∗) für die Ungleichungsmenge E verletzt ist und die freie Bereichsalgebra keinen kontinuierlichen Bereich bildet. Die freie Bereichsalgebra ist also ohne Forderungen an E nicht ”automatisch“ kontinuierlich. Ein solches Beispiel wollen wir hier angeben: Wir betrachten die Bereich-geordnete Signatur Σ = (Ω, ≤, α) mit Ω = [0, 1], also dem Einheitsintervall mit der üblichen Ordnung, und α(ω) = 0 für alle ω ∈ Ω. Die Signatur besteht demnach aus lauter Konstanten. Die Ungleichungsmenge E möge aus der einzigen Ungleichung x ⊑ 1 bestehen. Die Bedingung (∗), die wir an die Menge E stellen, ist also offensichtlich verletzt. Wir wollen nun bzgl. dieser Signatur und dieser Ungleichungsmenge die freie Bereichsalgebra \underline{F (D)} über dem einelementigen kontinuierlichen Bereich D = \{⋆\} betrachten. Der Bereich F (D) läßt sich graphisch folgendermaßen veranschaulichen:

[figure: 0; 1; ⋆; F (D)]

Die Menge F (D) bildet keinen kontinuierlichen Bereich, da die Menge ↓ ↓⋆ = {a ∈ F (D) | a ≪ ⋆} leer ist; das Element ⋆ wird von keinem Element r ∈ [0, 1] approximiert, aber liegt auch nicht weit unter sich selbst.

4 Präsentationen

In der Allgemeinen Algebra benutzt man Mengen als Erzeuger von Algebren, wir betrachten kontinuierliche Bereiche als solche Erzeuger. Bereiche sind im Gegensatz zu Mengen nicht strukturlos, sondern die Elemente eines Bereichs sind über die Ordnung miteinander in Beziehung gesetzt. Man kann auch auf andere Art bzw. zusätzlich Strukturen auf den erzeugenden Mengen schaffen, indem man fordert, daß die Menge selbst gewissen (Un-)Gleichungen in bezug auf die zugrundeliegende Signatur genügt. Dies führt zum Begriff der Präsentation.

Definition 4.1 Eine Präsentation (A, P, E) bzgl. einer Signatur Σ besteht aus einer Menge von Erzeugern A, einer Menge P ⊆ T_{Σ}(A) × T_{Σ}(A) von (Un-)Gleichungen zwischen Termen über A und einer Menge E ⊆ T_{Σ}(X)×T_{Σ}(X) von (Un-)Gleichungen über einer Variablenmenge X.

Der entscheidende Unterschied zwischen den Ungleichungen aus E und denen aus P besteht darin, daß diejenigen aus E allgemein gültig sind in dem Sinne, daß sie eine ”Substitutionsvorschrift“ darstellen: Man kann Instanzen in A von Ungleichungen aus E bilden. Die Ungleichungen aus P beziehen sich nur auf die Elemente, mit denen sie formuliert werden. Eine weitere Instanzbildung ist nicht möglich.

Wir haben bisher Algebren nur über ihre Trägermenge und die Ungleichungsmenge E beschrieben. Der allgemeinere Begriff der Präsentation bietet nun ein noch umfassenderes Beschreibungsmittel für Algebren. Oft ist die Menge E von Ungleichungen implizit gegeben. So gibt man z.B. nicht noch die Gleichungen, die eine Gruppe kennzeichnen an, sondern nur die Mengen A und P und spricht von der ”Präsentation einer Gruppe“. Ein Beispiel dafür bietet die Präsentation der Gruppe der Bewegungen, die ein regelmäßiges Fünfeck in sich selbst überführen. Mit A = {d, s} und P = {d^{5} = e, s^{2} = e, dsds = e} ist die Präsentation dieser Symmetriegruppe gegeben. Allgemein drängt sich nun wieder die Frage auf, wie zu einer Präsentation (A, P, E) eine universelle Lösung gefunden werden kann.

In der Allgemeinen Algebra bedeutet das, daß zu einer gegebenen Signatur Σ und einer Präsentation (A, P, E) eine Algebra \underline{F (A)} und eine Funktion η: A → F (A) konstruiert werden muß, so daß \underline{F (A)} den Gleichungen aus E genügt, η̄(t_{1}) = η̄(t_{2}) in \underline{F (A)} für alle (t_{1}, t_{2}) ∈ P gilt und \underline{F (A)} die universelle Eigenschaft besitzt; also für alle Algebren \underline{H}, die den Gleichungen aus E genügen, und allen Funktionen h: A → H mit h̄(t_{1}) = h̄(t_{2}) für alle (t_{1}, t_{2}) ∈ P muß ein eindeutiger Homomorphismus ext(h): \underline{F (A)} → \underline{H} mit ext(h) ∘ η = h existieren.

[figure: A; F (A); H; η; ∀h; \underline{F (A)}; ext(h); \underline{H}; ∃!ext(h)]

Dieses Problem wird in der Allgemeinen Algebra durch einen ”Trick“ gelöst: Man erweitert die zugrundeliegende Signatur Σ um die 0-stelligen Operationen c_{a} = a, a ∈ A. Es werden also alle Erzeugende der Trägermenge als Konstanten in die Signatur aufgenommen. Nun kann man bzgl. dieser erweiterten Signatur Σ′ die freie Algebra über der leeren Menge bzgl. E ∪P bilden. Diese Algebra wollen wir mit \underline{F (A)}′ bezeichnen. \underline{F (A)}′ genügt nun nach Konstruktion den Gleichungen aus E und den Gleichungen aus P; zudem besitzt \underline{F (A)}′ mit η′: ∅ → F (A)′, der leeren Abbildung, folgende universelle Eigenschaft: Zu jeder Algebra \underline{H}′, die auch den Gleichungen aus E und P genügt, und jeder Abbildung ∅_{h}: ∅ → H′ gibt es genau einen Homomorphismus ext(∅_{h}): \underline{F (A)}′ → \underline{H}′ mit ext(∅_{h}) ∘ η′ = ∅_{h}.

[figure: ∅; F (A)′; H′; η′; ∅_{h}; ext(∅_{h})]

Man beachte, daß ext(∅_{h}) die Konstanten aus \underline{F (A)}′, also insbesondere die Elemente a ∈ A, auf die Konstanten in \underline{H}′ abbildet.

\underline{F (A)}′ ist noch nicht die gesuchte universelle Lösung, aber wir können die oben erwähnten Eigenschaften von \underline{F (A)}′ ausnutzen, um die gesuchte Algebra zu konstruieren. Wir benutzen als Trägermenge von \underline{F (A)} die Trägermenge von \underline{F (A)}′, lassen aber nur Operationen aus der ursprünglichen Signatur Σ zu. Als Abbildung η von A nach F (A) wählen wir η: A → F (A), a ↦ c_{a}. Die Algebra \underline{F (A)} genügt nun den Gleichungen aus E, da \underline{F (A)}′ dies tut, und es gilt η̄(t_{1}) = η̄(t_{2}) für alle (t_{1}, t_{2}) ∈ P nach Konstruktion. \underline{F (A)} besitzt auch die geforderte universelle Eigenschaft: Gibt es eine Algebra \underline{H}, die den Gleichungen aus E genügt, und eine Abbildung h: A → H mit h̄(t_{1}) = h̄(t_{2}) für alle (t_{1}, t_{2}) ∈ P, dann gilt für ext(∅_{h}): F (A) → H die Beziehung ext(∅_{h}) ∘ η = h.

[figure: A; F (A); H; η; h; ext(∅_{h})]

Das Diagramm kommutiert, da ext(∅_{h}) die Konstanten c_{a}, a ∈ A, in \underline{F (A)} gerade auf (c_{a})_{H′}: = h(a) abbildet. Diese Funktion ist ein Homomorphismus und eindeutig, da ext(∅_{h}): \underline{F (A)}′ → \underline{H}′ ein eindeutiger Homomorphismus ist. Wir haben somit zur Präsentation (A, P, E) eine universelle Lösung gefunden.

Wir wollen nun die oben beschriebene Problematik auf kontinuierliche Bereiche übertragen, d.h. wir betrachten Bereich-geordnete Signaturen und diesbezüglich Präsentationen (D, P, E), wobei D einen kontinuierlichen Bereich bildet. Dank der Methoden aus Kapitel 2 können wir das Verfahren aus der Allgemeinen Algebra direkt übernehmen, um eine universelle Lösung zu einer solchen Präsentation zu finden.

Es sei uns also eine Bereich-geordnete Signatur Σ = (Ω, ≤_{op}, α) und eine Präsentation (D, P, E) mit einem kontinuierlichen Bereich D gegeben. Wir erweitern die Signatur um die Konstanten c_{d} = d, d ∈ D. Die erweiterte Signatur Σ′ ist immer noch Bereichgeordnet mit Ω′ = Ω ∪ D. Eine Basis B′ von Ω′ besteht dann aus einer Basis B von Ω und einer Basis B von D, also B′ = B ∪ B. Wir fassen die Ungleichungen aus E und P zur Menge E′ von Ungleichungen zusammen. Um die Methoden aus Kapitel 2 anwenden zu können, fordern wir wie dort für die Ungleichungsmenge folgende Bedingung:

(∗) Zu jeder Ungleichung (τ_{1}, τ_{2}) ∈ E′ und jedem Term δ ∈ T_{B′}(X) mit δ ≺_{E} τ_{1} existiert eine Ungleichung (τ′_{1}, τ′_{2}) ∈ E′ mit τ′_{1}, τ′_{2} ∈ T_{B′}(X), für die gilt: δ ≺_{E} τ′_{1}

und τ′_{2} ≺_{E} τ_{2}.

Man beachte, daß für die Ungleichungen aus E und P ”approximierende Ungleichungen“ mit Termen aus Basiselementen existieren müssen.

Mit diesen Voraussetzungen erhalten wir direkt aus Satz 2.14, daß \underline{F (D)}′ die freie Bereichsalgebra über dem leeren Bereich in bezug auf Σ′ und E′ ist. Wir können nun analog zur Lösungsmethode in der Allgemeinen Algebra \underline{F (D)} und η definieren. Im Unterschied zum dortigen Problem müssen wir hier überprüfen, ob η: D → F (D), d ↦ c_{d}, eine stetige Funktion ist. Dies gilt in der Tat, denn η kann geschrieben werden als η = eval_{0}|_{D}. Die Funktion eval_{0}|_{D}: D × (F (D)′)^{0} = D × 1 = D → F (D)′, d ↦ c_{d}, ist jedoch stetig, da \underline{F (D)}′ eine Bereichsalgebra ist. Somit gilt nun

Satz 4.2 \underline{F (D)} ist die universelle Lösung zur Präsentation (D, P, E).

Wir haben also das gesuchte Objekt als direkte Anwendung der Methoden aus dem zweiten Kapitel erhalten. Dies war uns nur möglich, da wir dort Bereich-geordnete Signaturen betrachtet haben. Hätten wir im Kapitel 2 nur Signaturen im üblichen Sinne, also solche mit unvergleichbaren Operationssymbolen, behandelt, könnte man den kontinuierlichen Bereich D nicht in die Signatur aufnehmen.

Im Ganzen erscheint die obige Konstruktion der gesuchten Algebra jedoch recht umständlich und mit der Erweiterung der Signatur etwas ”unnatürlich“. Ein weitaus intuitiverer Weg, um zu einer gegebenen Präsention (A, P, E) eine universelle Lösung zu erhalten, ist es, die freie Algebra über A bzgl. E zu betrachten und diese anschließend nach den (Un-)Gleichungen aus P zu faktorisieren. In der Allgemeinen Algebra kann man zeigen, daß auch diese Darstellung eine universelle Lösung der Präsentation ist. Wir wollen zeigen, daß dieser intuitive Weg auch bei Präsentationen mit kontinuierlichen Bereichen als Trägermenge möglich ist. Das ”Faktorisieren“ besteht dabei wieder aus der Definition einer neuen Approximationsordnung.

Zu einer gegebenen Bereich-geordneten Signatur Σ und einer Präsentation (D, P, E) mit einem kontinuierlichen Bereich D können wir mit der Technik aus Kapitel 2 die freie Bereichsalgebra \underline{F (D)} bzgl. Σ und E konstruieren, wenn E die dortige Bedingung (∗) erfüllt. Die Konstruktion aus Kapitel 2 liefert uns sogar noch mehr Information: Wir können F B = T_{B}(B) als Basis von F (D) wählen und wissen, daß ⟨F B, ≺⟩ mit ≺: = (⊏ ∼_{1} ∘ ≺^{s} ∘ ⊏ ∼_{1})^{t} eine abstrakte Basis ist (Die Relation ⊏ ∼_{1} wird wie ⊏ ∼ aus Kapitel 2 verwendet, die restliche Notation ist von dort übernommen). Mit den Relationen ⊏ ∼_{1} und ≺^{s} haben wir die Ungleichungen aus E und den kontinuierlichen Bereich D auf F B berücksichtigt. Wir müssen noch die Ungleichungen aus P in geeigneter Weise beachten. Um wieder die Methoden aus Kapitel 2 verwenden zu können, erweitern wir die Relation ≺^{s} auf die ganze Menge T_{Σ}(D) und fordern für P bzgl. der Relation ≺^{s} die folgende Bedingung:

(∗) Für jede Ungleichung (t_{1}, t_{2}) ∈ P und jeden Term s ∈ T_{B}(B) mit s ≺^{s} t_{1} existiert eine Ungleichung (t′_{1}, t′_{2}) ∈ P mit t′_{1}, t′_{2} ∈ T_{B}(B), s ≺^{s} t′_{1} und t′_{2} ≺^{s} t_{2}.

Die Forderung, die an die Ungleichungsmenge P gestellt wird, ist vom Wesen her dieselbe wie die Bedingung (∗), die in Kapitel 2 für die Ungleichungsmenge E gefordert wurde. Während dort durch die Relation ≺_{E} eine Möglichkeit der Approximation in den Operationen verlangt wurde, ist hier die Approximierbarkeit der Terme, die in den Ungleichungen aus P vorkommen, zur Bedingung gestellt.

Die Ungleichungen aus P führen wir nun wie die aus E über eine mit den Operationen verträgliche Präordnung ⊏ ∼_{2} auf F B ein: Axiome: (A1’) t ⊏ ∼_{2} t für alle t ∈ F B, (A2’) s ⊏ ∼_{2} t, wenn (s, t) ∈ P. Regeln: (R1’) Ist f ∈ B ein n-stelliges Operationssymbol und s_{1} ⊏ ∼_{2} t_{1}, …, s_{n} ⊏ ∼_{2} t_{n}, dann ist auch f(s_{1}, …, s_{n}) ⊏ ∼_{2} f(t_{1}, …, t_{n}). (R2’) Aus s ⊏ ∼_{2} t und t ⊏ ∼_{2} u folgt s ⊏ ∼_{2} u.

Man beachte, daß nicht alle Ungleichungen (t_{1}, t_{2}) ∈ P in der Präordnung ⊏ ∼_{2} berücksichtigt werden, sondern nur solche mit t_{1}, t_{2} ∈ T_{B}(B). Für diese zweite Präordnung auf F B können wir zeigen:

Lemma 4.3 Die Präordnung ⊏ ∼_{2} erfüllt bzgl. ≺^{s} die Bedingung (∗_{s}):

(∗_{s}) Zu s ≺^{s} t und t ⊏ ∼_{2} u existieren t′_{1}, u′_{1}, …, t′_{n}, u′_{n} mit s ≺^{s} t′_{1} ⊏ ∼_{2} u′_{1} ≺^{s} t′_{2} … t′_{n} ⊏ ∼_{2} u′_{n} ≺^{s} u.

Beweis: Für den Fall s ≺^{s} t und t ⊏ ∼_{2} t existiert, da ≺^{s} das Interpolationsaxiom erfüllt, ein t′ ∈ F B mit s ≺^{s} t′ ≺^{s} t, und damit gilt s ≺^{s} t′ ⊏ ∼_{2} t′ ≺^{s} t. Für s ⊏ ∼_{2} t mit (s, t) ∈ P ist (∗_{s}) wie bei Axiom (A1’) mit n = 1 erfüllt, da P der Bedingung (∗) genügt. Der Nachweis der Bedingung (∗_{s}) für die Regeln (R1’) und (R2’) verläuft analog zum Beweis von Satz 2.7.(2) mit ≺^{s} statt ≺_{E} und ⊏ ∼_{2} statt ⊑. □

Nun müssen die Relationen ≺ und ⊏ ∼_{2} in geeigneter Weise miteinander verbunden werden. Wie man eine neue Relation definieren kann und dabei wieder eine ”schöne“ Struktur auf F B erhält, zeigt der folgende Satz.

Satz 4.4 Es sei ⟨B, ≺⟩ eine abstrakte Basis und ⊏ ∼ eine Präordnung auf B, die bzgl. ≺ die Bedingung (∗_{s}) erfüllt. Dann ist auch ⟨B, <⟩ mit <: = (⊏ ∼ ∘ ≺ ∘ ⊏ ∼)^{t} eine abstrakte Basis.

Beweis: Wir müssen für ⟨B, ≺⟩ nur das Interpolationsaxiom überprüfen, da die Transitivität per definitionem gilt. Es gelte s ≺ u für alle s einer endlichen Menge M ⊆ B. Für jedes s existieren s^{1}, …, s^{m(s)} ∈ F B mit s ⊏ ∼ s^{1} ≺ s^{2} ⊏ ∼ … s^{m(s)−1} ≺ s^{m(s)} ⊏ ∼ u. Da ⊏ ∼ bzgl. ≺ die Bedingung (∗_{s}) erfüllt, können die beiden letzten Schritte ersetzt werden durch … s^{m(s)−1} ≺ t_{1}^{(s)} ⊏ ∼ u_{1}^{(s)} ≺ t_{2}^{(s)} … t_{n}^{(s)} ⊏ ∼ u_{n}^{(s)} ≺ u für bestimmte t_{i}^{(s)}, u_{i}^{(s)}, i = 1, … n. Die Menge aller u_{n}^{(s)} ist endlich, und da ≺ das Interpolationsaxiom erfüllt, gibt es ein v ∈ B mit u_{n}^{(s)} ≺ v ≺ u für alle u_{n}^{(s)}. Mit der Reflexivität von ⊏ ∼ folgt dann s < v < u für alle s ∈ M wie gefordert. □

Um Satz 4.4 für ⟨F B, ≺⟩ und ⊏ ∼_{2} anwenden zu können, müssen wir erst überprüfen, ob die notwendigen Voraussetzungen erfüllt sind. Die Präordnung ⊏ ∼_{2} erfüllt auch bzgl. ≺ die Bedingung (∗_{s}) in der Tat: Zu s ≺ t = s (⊏ ∼_{1} ∘ ≺^{s} ∘ ⊏ ∼_{1})^{t} t und t ⊏ ∼_{2} u existiert nach Satz 2.10.(2) eine endliche Kette der Form s (⊏ ∼_{1} ∘ ≺^{s} ∘ ⊏ ∼_{1})^{t} u′_{n} ≺^{s} t, und damit gilt nach Lemma 4.3 s (⊏ ∼_{1} ∘ ≺^{s} ∘ ⊏ ∼_{1})^{t} u′_{n} (≺^{s} ∘ ⊏ ∼_{2})^{t}∘ ≺^{s} u. Mit der Reflexivität von ⊏ ∼_{1} folgt dann s ≺ ∘ ⊏ ∼_{2} ∘ ≺ … ⊏ ∼_{2} ∘ ≺ u wie gewünscht. Der vorhergehende Satz 4.4 liefert nun, daß ⟨F B, <_{2}⟩ mit <_{2}: = (⊏ ∼_{2} ∘ ≺ ∘ ⊏ ∼_{2})^{t} = (⊏ ∼_{2} ∘(⊏ ∼_{1} ∘ ≺^{s} ∘ ⊏ ∼_{1})^{t}∘ ⊏ ∼_{2})^{t} eine abstrakte Basis ist. Wir können nun die restlichen Techniken aus Kapitel 2 übernehmen. Mit Satz 1.10 ist F (D)_{2} = Idl(F B, <_{2}) ein kontinuierlicher Bereich. Wir erklären die Operationen aus F (D)_{2} wieder punktweise: Für ein n-stelliges Operationssymbol f ∈ Ω und Ideale A_{1}, …, A_{n} ∈ F (D)_{2} ist f_{F (D)_{2}}(A_{1}, …, A_{n}): =↓_{2} {g(a_{1}, …, a_{n}) | g ∈ B, g ≪_{op} f, a_{1} ∈ A_{1}, …, a_{n} ∈ A_{n}}. Nach den Ergebnissen aus Kapitel 2 sind die Operationen wohldefiniert und die Auswertungsfunktionen eval_{n} stetig. Damit ist \underline{F (D)_{2}} eine Bereichsalgebra. Wir haben nun ausgehend von der bekannten Basis F B mittels der Definition einer neuen Approximationsordnung auf F B eine Bereichsalgebra \underline{F (D)_{2}} gefunden, die als universelle Lösung der Präsentation (D, P, E) dienen kann. Um zu zeigen, daß \underline{F (D)_{2}} eine Darstellung des gesuchten Objekts, also isomorph zu der am Anfang des Kapitels konstruierten universellen Lösung ist, müssen wir diese noch einmal etwas genauer untersuchen. Wir bezeichnen die universelle Lösung zur besseren Unterscheidung mit \underline{F (D)_{1}}. Die Trägermenge F (D)_{1} ist nach Konstruktion die Idealvervollständigung der abstrakten Basis ⟨F B′, ≺′⟩ mit F B′ = T_{B′}(∅) und ≺′= (⊏ ∼′ ∘ ≺^{s′} ∘ ⊏ ∼′)^{t}. Auf den ersten Blick scheinen F B′ und ≺′ mit den entsprechenden Mengen aus der Konstruktion von \underline{F (D)_{2}} nichts gemeinsam zu haben, doch das Gegenteil ist der Fall. Es gilt F B′ = F B, da alle Elemente der Basis B als Konstanten der Signatur eingeführt werden. Ebenso gilt ≺^{s′}=≺^{s}. Die Präordnung ⊏ ∼′ können wir aufgrund ihrer Definition als Relationenprodukt der Präordnungen ⊏ ∼_{1} und ⊏ ∼_{2} ausdrücken: In ⊏ ∼′ fließen die Ungleichungen aus E und P so ein, wie E in ⊏ ∼_{1} und P in ⊏ ∼_{2} eingeht. Als Präordnung ist ⊏ ∼′ eine transitive Relation, es können also Terme über Relationenketten miteinander verbunden werden. Somit ergibt sich ⊏ ∼′= (⊏ ∼_{1} ∘ ⊏ ∼_{2})^{t}. Wir können nun die Trägermenge der universellen Lösung schreiben als F (D)_{1} = Idl(F B, <_{1}) mit <_{1}: = ((⊏ ∼_{1} ∘ ⊏ ∼_{2})^{t}∘ ≺^{s} ∘(⊏ ∼_{1} ∘ ⊏ ∼_{2})^{t})^{t}.

Auf F B sind damit die Relationen <_{1} und <_{2} definiert. Die Komponenten D, E und P der Präsentation wirken durch die andersartige Verknüpfung der Relationen ≺^{s}, ⊏ ∼_{1} und ⊏ ∼_{2} auch verschieden auf F B ein. Um die beiden Bereichsalgebren \underline{F (D)_{1}} und \underline{F (D)_{2}} in Beziehung setzen zu können, wollen wir dies erst einmal mit den Relationen <_{1} und <_{2} tun. Man beachte, daß auf F B zwar <_{2}⊂<_{1} gilt, aber <_{1} und <_{2} echt verschieden sind. Es läßt sich folgendermaßen eine Verbindung zwischen beiden Relationen herstellen:

Lemma 4.5 (1) <_{1} ∘ <_{2} = <_{1}.

(2) <_{2} ∘ <_{1} = <_{2}.

Beweis: Mittels wiederholter Anwendung des Interpolationsaxioms für ≺^{s} und der Reflexivität von ⊏ ∼_{1} und ⊏ ∼_{2} kann der Beweis auf elementare Art geführt werden. □

Mit Hilfe dieser Aussagen können wir beweisen, daß auch \underline{F (D)_{2}} eine universelle Lösung der Präsentation (D, P, E) ist.

Satz 4.6 \underline{F (D)_{1}} ≅ \underline{F (D)_{2}}.

Beweis: Wir definieren zwei Abbildungen Φ : Idl(F B, <_{1}) → Idl(F B, <_{2}), A ↦↓_{2}A, und Ψ : Idl(F B, <_{2}) → Idl(F B, <_{1}), A ↦↓_{1}A, und zeigen als erstes deren Wohldefiniertheit. Um zu zeigen, daß Φ wohldefiniert ist, müssen wir nachweisen, daß ↓_{2}A ein Ideal, also insbesondere gerichtet ist. Es seien x, y ∈↓_{2}A, d.h. es existieren x′, y′ ∈ A mit x <_{2} x′ und y <_{2} y′. Da A ein Ideal bzgl. <_{1} (also insbesondere gerichtet) ist, gibt es ein z ∈ A mit x′ <_{1} z und y′ <_{1} z. Es gilt also mit Lemma 4.5.(2): x <_{2} x′ <_{1} z ⇒ x <_{2} z und y <_{2} y′ <_{1} z ⇒ y <_{2} z. Da <_{2} das Interpolationsaxiom erfüllt, existiert ein z′ mit {x, y} <_{2} z′ <_{2} z. Es ist z′ ∈ ↓_{2}A, x <_{2} z′ und y <_{2} z′. Das bedeutet, daß ↓_{2}A gerichtet ist. Die Wohldefiniertheit von Ψ zeigt man mit Hilfe von Lemma 4.5.(1) analog. Wir müssen noch zeigen, daß Φ und Ψ zueinander inverse Abbildungen sind und damit die Verknüpfung der beiden die Identität ergibt:

(Ψ ∘ Φ)(A) = Ψ(↓_{2} A)
= ↓_{1} (↓_{2} A)
= ↓_{1} (\begin{matrix}⋃ & ↑ \\ a∈A \end{matrix} ↓_{2} a)
= \begin{matrix}⋃ & ↑ \\ a∈A \end{matrix}(↓_{1} (↓_{2} a))
= \begin{matrix}⋃ & ↑ \\ a∈A \end{matrix}(↓_{1} a) (nach Lemma 4.5.(1))
= A.

Um zu zeigen, daß die umgekehrte Verknüpfung der beiden Abbildungen der Identität auf Idl(F B, <_{2}) entspricht, benutzt man analog Lemma 4.5.(2). Die Homomorphiebedingung ist ebenfalls erfüllt. Für Ideale A_{i} ∈ \underline{F (D)_{1}}, i = 1 … n, und ein n-stelliges Operationssymbol f gilt:

Φ (f_{F (D)_{1}}(A_{1}, …, A_{n})) = Φ (↓_{1} {g(a_{1}, …, a_{n}) | g ∈ B, g ≪_{op} f, a_{i} ∈ A_{i}})
= ↓_{2} (↓_{1} {g(a_{1}, …, a_{n}) | g ∈ B, g ≪_{op} f, a_{i} ∈ A_{i}})
= ↓_{2} {g(a_{1}, …, a_{n}) | g ∈ B, g ≪_{op} f, a_{i} ∈↓_{2} A_{i}}

(nach Lemma 4.5.(2))

= f_{F (D)_{2}}(Φ(A_{1}), …, Φ(A_{n}))

Man zeigt analog, daß Ψ die Homomorphiebedingung erfüllt. □

Wir haben somit gezeigt, daß auch der zweite, intuitivere Weg zu einer universellen Lösung der vorgegebenen Präsentation führt. Es ist mit den Methoden aus Kapitel 2 möglich geworden, die Darstellungsformen universeller Lösungen aus der Allgemeinen Algebra auf kontinuierliche Bereiche zu übertragen.

Literatur

[1] S. Abramsky, A. Jung, Domain Theory, in: Handbook of Logic in Computer Science, voraussichtlich 1995.

[2] Th. Ihringer, Allgemeine Algebra, Teubner-Verlag, Stuttgart, 1988.

[3] J. Koslowski, Note on Free Algebras over Continous Domains, Manuskript, Universität Hannover, 1994.

[4] C. Jones, Probabilistic Non-determinism, PhD thesis, University of Edinburgh, 1989.

[5] A. Edalat, Domain Theory and Integration, Manuskript, Imperial College London, 1993.

[6] B. Möller, Unendliche Objekte und Geflechte, Dissertation, Technische Universität München, 1981.

[7] B. Courcelle, M. Nivat, Algebraic Families of Interpretations, 17th Annual IEEE Symposium on Foundations of Computer Science, 1976, S.137-146.

\underline{Erklärung:}

Hiermit erkläre ich, daß ich diese Arbeit selbständig und nur mit den angegebenen Hilfsmitteln angefertigt habe.

Darmstadt, im April 1995