Die Hyperlimeskonstruktion

Christian Haack

August 1993 Diplomarbeit am

Fachbereich Mathematik der Technischen Hochschule Darmstadt

Betreuender Professor: Prof. Klaus Keimel Inhaltsverzeichnis

1 Einleitung 1 1.1 Vorgeschichte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Aufbau der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Einige Begriffe und Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Die Hyperlimeskonstruktion 6 2.1 Die kategorientheoretische Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Hyperlimeskegel in POSET und DCPO . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Hyperlimeskegel, deren Projektionen obere Adjungierte sind 16

4 Die Kategorie der Hyperlimites flacher Bereiche 27

5 Vererbung von Eigenschaften 36 5.1 Eigenschaften des Hyperlimesobjektes bei bekanntem Diagramm . . . . . . . . . . . 36 5.2 Rückschlüsse auf das Diagramm bei bekanntem Hyperlimesobjekt . . . . . . . . . . . 46

6 Der Zerlegungssatz 54

6.1 Die Struktur von Hyperlimesobjekten über zykelfreien Diagrammen beschränkt vollständi-

ger geordneter Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 6.2 Eine Charakterisierung der Halbfaktoren . . . . . . . . . . . . . . . . . . . . . . . . . 58 6.3 Der Verband der Halbfaktoren eines dI-Bereiches ist ein vollständiger Unterverband

des Verbandes aller Projektionsbilder . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 6.4 Der Zerlegungssatz für dI-Bereiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 6.5 Die Faktoren der dI-Bereichs-Zerlegung sind irreduzibel . . . . . . . . . . . . . . . . 72

7 Konkrete Datenstrukturen und Hyperlimes 78

1 Einleitung

1.1 Vorgeschichte

In dieser Arbeit beschäftigen wir uns mit einer dem Produkt von geordneten Mengen ähnlichen Konstruktion. Die Motivation liegt ursprünglich in der Idee, Datenbanken ordnungstheoretisch zu modellieren. In der klassischen relationalen Datenbanktheorie faßt man eine Datenbank als Teilmenge eines Produktes von Mengen, also als Relation, auf. Jedem Attribut ordnet man die Menge aller möglichen Ausprägungen zu und nimmt als Datenbankbereich das Produkt dieser Mengen. Ein Eintrag in der Datenbank ist dann ein Element dieses Produktes und eine Datenbank eine Teilmenge desselben. Der Relationsbegriff wird einer Datenbank jedoch nicht gerecht. In einer Datenbank will man nämlich auch Einträge erlauben, die nicht jedem Attribut, sondern nur manchen, eine Ausprägung zuordnen. Die Idee von Peter Bunemann war es nun, aus jedem Faktor des Datenbankbereiches eine geordnete Menge zu machen, indem man ein kleinstes Element hinzufügt. Dieses Element hat die Bedeutung ’keine Information’. Man faßt eine Datenbank dann auf als Teilmenge (oder genauer: als endliche Antikette) eines Produktes von flachen Bereichen. In [BJO] werden Begriffe aus der relationalen Datenbanktheorie in dieses ordnungstheoretische Datenbankmodell übersetzt. Dabei werden die Begriffe nicht nur für Produkte von flachen Bereichen formuliert, sondern allgemeiner für Scottbereiche, und zwar so, daß sie in Produkten von flachen Bereichen die adäquate Übersetzung der Begriffe aus der relationalen Datenbanktheorie sind. Was bedeutet in diesem allgemeineren Rahmen die Ordnung? Man kann sich dazu zwei verschiedene Vorstellungen machen. Einerseits kann man sich jedes Element eines Scott-Bereiches als Träger von Information vorstellen. Ein Element ist kleiner als ein anderes, wenn es eine Teilinformation des größeren trägt. Diese Vorstellung paßt zur Vorstellung eines Produktes von flachen Bereichen als Datenbankbereich. In diesem Fall ist ein Eintrag kleiner als ein anderer, wenn er in allen Attributen, in denen er eine Ausprägung hat, die gleiche Ausprägung hat wie der größere Eintrag. Andererseits kann man sich vorstellen, daß die maximalen Elemente eines Scott-Bereiches ’ideale’ Elemente sind. Ein ideales Element wird von den darunterliegenden Elementen approximiert. Ein Element ist größer als ein anderes, wenn alle Elemente, die von ihm approximiert werden, auch vom kleineren approximiert werden, und zwar schlechter. Auch diese Vorstellung paßt zur Vorstellung eines Produktes von flachen Bereichen als Datenbankbereich. Die idealen Einträge einer Datenbank sind die, bei denen jedes Attribut eine Ausprägung hat. Vorsicht ist geboten, wenn man anfängt, Teilmengen von Scott-Bereichen (zum Beispiel Datenbanken) miteinander zu vergleichen. Dann führen diese beiden Vorstellungen nämlich auf verschiedene Ordnungen. Ein wichtiger Begriff aus der Datenbanktheorie ist der der Projektion. Faßt man eine Datenbank als Relation auf, so ist das einfach eine Projektion auf einen oder mehrere Faktoren des Produktes. In unserem ordnungstheoretischen Datenbankmodell können wir jeden Faktor auf natürliche Weise mit einer Teilmenge des Produktes identifizieren. Den i-ten Faktor identifizieren wir nämlich mit der Menge, die aus den Elementen besteht, deren sämtliche Komponenten, außer der i-ten, das kleinste Element des jeweiligen Faktors sind. Solche Mengen sind Bilder von Ordnungsprojektionen. Sie haben jedoch Eigenschaften, die Bilder von Ordnungsprojektionen im allgemeinen nicht haben. So sind sie beispielsweise Anfangsstücke. Betrachten wir in einem Produkt zweier geordneter Mengen P, Q mit kleinstem Element ein Element x, dessen Q-Komponente das kleinste Element von Q ist, und ein anderes Element y, dessen P -Komponente kleiner ist als die P -Komponente von x, so existiert das Supremum von x und y. Eine Projektion p auf einen eingebetteten Faktor hat also die folgende Eigenschaft: Ist x ein Element des Bildes von p und ist y ein Element der zugrundeliegenden geordneten Menge, so daß p(y) kleiner ist als x, dann existiert das Supremum von x und y. Diese Eigenschaft heißt in [BJO] Slide-Bedingung. In Produkten von flachen Bereichen charakterisiert sie, gemeinsam mit der Bedingung, daß das Bild ein Anfangsstück ist, die Projektionen auf die eingebetteten Faktoren. Projektionen, die die Slide-Bedingung erfüllen und deren Bild ein Anfangsstück ist, werden deshalb zum Pendant der Projektionen aus der relationalen Datenbanktheorie erklärt. Herrmann Puhlmann nennt die Bilder solcher Projektionen in seiner Diplomarbeit ’lebendige Stümpfe’ und zeigt, daß die Menge der lebendigen Stümpfe eines distributiven Scott-Bereiches einen distributiven, algebraischen Verband bildet. Suprema in diesem Verband werden elementweise gebildet, und endliche Infima sind Mengenschnitte. In einem distributiven Scott-Bereich, dessen kompakte Elemente endliche Hauptanfänge erzeugen, (solche Bereiche nennen wir dI-Bereiche), sind sogar beliebige Infima im Verband der lebendigen Stümpfe Mengenschnitte. Achim Jung und Hermann Puhlmann interessierten sich nun für das Problem, Scott-Bereiche in ein Produkt von kleineren Scott-Bereichen zu zerlegen. Da die elementweisen Suprema der eingebetteten Faktoren eines Produktes von geordneten Mengen mit kleinstem Element einen distributiven, algebraischen Verband bilden, in dem Infima Mengenschnitte sind, bestand Hoffnung, daß man aus den lebendigen Stümpfen eines dI-Bereiches eine Produktzerlegung gewinnen kann. In einem Produkt von geordneten Mengen mit kleinstem Element gibt es zu einer Projektion p auf die Einbettung eines Faktors eine ‘komplementäre’ Projektion, die minimal ist mit der Eigenschaft, daß ihr punktweises Supremum mit p gleich der Identität ist. Hermann Puhlmann zeigte in seiner Diplomarbeit, daß es in einem dI-Bereich zu jeder Projektion auf einen lebendigen Stumpf eine in diesem Sinne komplementäre Projektion gibt. Allerdings muß ihr Bild kein Anfangsstück sein, und der zugrundeliegende Bereich ist deshalb nicht isomorph zum Produkt der Bilder der beiden Projektionen. Jedoch ist er isomorph zu einer Teilmenge dieses Produktes, welche sich mit Hilfe einer stetigen Funktion aus dem Bild der komplementären Projektion in den lebendigen Stumpf beschreiben läßt. Nennen wir die Projektion auf den lebendigen Stumpf p und die dazu komplementäre Projektion q, so ist er nämlich isomorph zur Menge aller Elemente des Produktes deren p-te Komponente größer ist als das Bild der q-ten Komponente unter p. Weil jeder lebendige Stumpf eines dI-Bereiches also ’fast’ Faktor einer Produktzerlegung ist, benannte Achim Jung lebendige Stümpfe um in ’Semifaktoren’. Er definierte eine Konstruktion, die einer Familie von Bereichen und einer Familie von verbindenden Morphismen zwischen diesen die Menge aller Elemente des Produktes zuordnet, deren Bild der i-ten Komponente unter einem verbindenden Morphismus vom i-ten in den j-ten Faktor kleiner ist als die j-te Komponente. Diese Konstruktion nannte er Hyper-Limes. Er zeigte, daß sich jeder endliche distributive Scott-Bereich darstellen läßt als Hyperlimes von in gewissem Sinne irreduziblen Bereichen. In dieser Arbeit wollen wir nun diese Hyperlimeskonstruktion genauer untersuchen. Gesondert betrachten werden wir die Kategorie, deren Objekte Hyperlimites von flachen Bereichen und deren Morphismen stetige Abbildungen sind. Man kann diese Kategorie auffassen als Kategorie der Datenbankbereiche. Jedoch hat sie auch Eigenschaften, die sie brauchbar machen zur Konstruktion von Lambda-Kalkül-Modellen. So ist sie kartesisch abgeschlossen, und sie hat Objekte, die isomorph sind zum Bereich ihrer stetigen Selbstabbildungen.

1.2 Aufbau der Arbeit

Wir beginnen damit, den Hyperlimes kategorientheoretisch zu definieren. Dazu müssen wir fordern, daß die Morphismenklassen der Kategorien, die wir betrachten, geordnete Mengen sind. Wir werden Diagramme betrachten, die zwar nicht kommutieren, bei denen aber der Pfeil ’links herum’ kleiner ist als der Pfeil ’rechts herum’. Wir können solche Diagramme schwach kommutierend nennen. Damit wir zwei schwach kommutierende Diagramme hintereinanderzeichnen können und das resultierende Diagramm wieder schwach kommutiert, müssen wir fordern, daß die Verknüpfungsoperation monoton operiert. Im zweiten Abschnitt der Arbeit betrachten wir Diagramme, die die Eigenschaft haben, daß jede Hyperlimesprojektion über dem Diagramm eine untere Adjungierte hat. Das sind gerade die Diagramme, für die man die Bilder der Hyperlimesprojektionen ins Hyperlimesobjekt einbetten kann, also als Bilder von internen Projektionen im Hyperlimesobjekt wiederfindet. Wir können ein Diagramm angeben, das sich vollständig mit Hilfe dieser internen Projektionen beschreiben läßt und den gleichen Hyperlimes hat wie das ursprüngliche Diagramm. Wir werden zeigen, daß wir annehmen können, daß jede Hyperlimesprojektion über einem Diagramm von beschränkt vollständigen Mengen eine untere Adjungierte hat. Mit Hilfe dieser Erkenntniss können wir dann ein Reihe von Ergebnissen für Hyperlimites von beschränkt vollständigen Bereichen beweisen: Wir können Hyperlimites von flachen Bereichen intern charakterisieren. Wir können zeigen, daß die Kategorie der Hyperlimites von flachen Bereichen kartesisch abgeschlossen ist, und daß sie ein Objekt hat, welches isomorph ist zum Bereich seiner stetigen Selbstabbildungen. Und wir können zeigen, daß Hyperlimites von stetigen, beschränkt vollständigen Bereichen stetig sind, und daß Hyperlimites von Scott-Bereichen Scott-Bereiche sind. Im vierten Abschnitt beschäftigen wir uns mit der Frage, ob sich bestimmte Eigenschaften von den Hyperlimesfaktoren auf das Hyperlimesobjekt vererben. Beschränkte Vollständigkeit vererbt sich immer. Distributivität vererbt sich, falls die verbindenden Morphismen Suprema erhalten. Damit ein Hyperlimes von dI-Bereichen wieder ein dI-Bereich ist, und damit ein Hyperlimes von bifiniten Bereichen wieder ein bifiniter Bereich ist, muß man Endlichkeitsforderungen an das Diagramm stellen. Wir werden uns auch mit der umgekehrten Frage beschäftigen und versuchen, aus den Eigenschaften des Hyperlimesobjektes Rückschlüsse auf das Diagramm zu ziehen. Im fünften Abschnitt werden wir einige Ergebnisse von Achim Jung und Herrmann Puhlmann neu darstellen, und wir werden beweisen, daß sich jeder dI-Bereich darstellen läßt als Hyperlimes über einem zykelfreien Diagramm, dessen Objekte sich nicht weiter in zykelfreie Hyperlimites zerlegen lassen. Im letzten Abschnitt werden wir die Zustandsmengen der in [Cur] definierten stabilen, konkreten Datenstrukturen charakterisieren als Hyperlimites von flachen Bereichen über Diagrammen, deren Indexkategorien geordnete Mengen mit endlichen Hauptenden sind, und deren verbindende Morphismen konstant sind auf den Mengen der ’Nicht-bottom-Elemente’.

1.3 Einige Begriffe und Definitionen

Zunächst einige weniger übliche Bezeichnungen: Eine geordnete Menge heiße beschränkt vollständig, falls jede beschränkte Teilmenge ein Supremum hat. Ein beschränkt vollständiger, algebraischer Bereich heiße Scott-Bereich. Eine beschränkt vollständige geordnete Menge heiße distributiv, falls jeder Hauptanfang ein distributiver Verband ist. Eine beschränkt vollständige geordnete Menge heiße schnittstetig, falls jeder Hauptanfang ein schnittstetiger vollständiger Verband ist. Ein Bereich heiße endlich algebraisch, falls er algebraisch ist, und jeder von einem kompakten Element erzeugte Hauptanfang endlich ist. Ein endlich algebraischer, distributiver Bereich heiße dI-Bereich. Wir wollen sagen, daß eine Abbildung f : P → Q zwischen zwei geordneten Mengen Suprema erhält, falls f(⋁ M) Supremum von f(M) ist für jede Teilmenge M von P, deren Supremum existiert.

Wir werden in dieser Arbeit häufig den Begriff der Adjunktion und den damit verwandten Begriff der Projektion brauchen: Sind P und Q geordnete Mengen, und ist (g : P → Q, d : Q → P) ein Paar von monotonen Abbildungen, so heißt dieses Paar Adjunktion, falls es eine der vier folgenden äquivalenten Bedingungen erfüllt:

(i) Für alle p ∈ P, q ∈ Q ist g(p) ≥ q äquivalent zu p ≥ d(q).

(ii) g ∘ d ≥ id_{Q} und d ∘ g ≤ id_{P}

(iii) Für alle p ∈ P ist g(p) = Max(d^{−1}(↓ p)).

(iv) Für alle q ∈ Q ist d(q) = Min(g^{−1}(↑ q)).

g heißt dann obere Adjungierte, und d heißt untere Adjungierte. Eine obere Adjungierte erhält Infima, eine untere Adjungierte erhält Suprema. Eine Adjunktion heiße Projektions-Einbettungspaar, falls die obere Adjungierte surjektiv ist (oder äquivalent: falls die untere Adjungierte injektiv ist). Ist (g : P → Q, d : Q → P) eine Adjunktion, so ist d ∘ g eine Retraktion von P, die punktweise kleiner ist als die Identität. Eine solche Abbildung wollen wir interne Projektion von P nennen. g ∘ d ist eine Retraktion von Q, die größer ist als die Identität. Eine solche Abbildung wollen wir Abschlußoperator von Q nennen. Ist P eine geordnete Menge, so bezeichne Q_{P} die geordnete Menge aller internen Projektionen von P mit der punktweisen Ordnung. Außerdem bezeichne Q̃_{P} die geordnete Menge aller Bilder von internen Projektionen mit der Inklusionsordnung. Q_{P} und Q̃_{P} sind zueinander isomorph. Der Isomorphismus von Q_{P} nach Q̃_{P} bildet eine Projektion auf ihr Bild ab. Seine Inverse bildet ein A aus Q̃_{P} ab auf die Abbildung p_{A}, welche gegeben ist durch p_{A}(x) = ⋁(↓ x ∪ A). Bilder von internen Projektionen sind abgeschlossen gegen existierende Suprema. Ist P beschränkt vollständig, so besteht Q̃_{P} genau aus den Teilmengen von P, welche abgeschlossen sind gegen existierende Suprema. Dann ist Q̃_{P} ein vollständiger Verband, in dem Suprema elementweise gebildet werden, und Infima Mengenschnitte sind. In Q_{P} weden Suprema dann punktweise gebildet. Eine interne Projektion heißt stabil, falls ihr Bild ein Anfangsstück ist. S_{P} bezeichne die Menge aller stabilen Projektionen einer geordneten Menge P und S̃_{P} die Menge aller ihrer Bilder. Ist D ein distributiver, stetiger Bereich, so ist ein elementweises Supremum von Anfangsstücken wieder ein Anfangsstück. Deshalb ist dann S_{D} ein vollständiger Unterverband von Q_{D}. Zwei Rechenregeln im Verband Q_{P} einer geordneten Menge P:

• Sind p, q ∈ Q_{P}, so ist

p ≤ q ⇔ p ∘ q = q ⇔ q ∘ p = p

• Sind p ∈ S_{P} und q ∈ Q_{P}, so ist auch q ∘ p ∈ Q_{p}, und es ist

q ∘ p = p ∧_{Q_{P}} q

Noch einige Bezeichnungen für Kategorien von geordneten Mengen:

POSET: Kategorie der geordneten Mengen und der monotonen Funktionen

DCPO: Kategorie der Bereiche und der stetigen Funktionen

Volle Unterkategorien von POSET:

BC: Beschränkt vollständige geordnete Mengen

DIST: Distributive beschränkt vollständige geordnete Mengen Volle Unterkategorien von DCPO: CONT: Stetige Bereiche ALG: Algebraische Bereiche B: Bifinite Bereiche dI: dI-Bereiche HF: Hyperlimesobjekte über Diagrammen von flachen Bereichen OHF: Hyperlimesobjekte über zykelfreien Diagrammen von flachen Bereichen.

Ist C irgendeine dieser Kategorien, so meinen wir mit C_{⊥} die volle Unterkategorie von C, deren Objekte gerade die Objekte von C sind, die ein kleinstes Element haben.

2 Die Hyperlimeskonstruktion

2.1 Die kategorientheoretische Definition

Definition 2.1 Eine Kategorie C heiße O-Kategorie, falls [A → B] eine geordnete Menge ist für jedes Paar (A, B) von Objekten , und

∘ : [A → B] × [B → C] → [A → C] : (f, g) ↦ g ∘ f

eine montone Abbildung ist für jedes Tripel (A, B, C) von Objekten.

Versieht man in P OSET jede Morphismenmenge mit der punktweisen Ordnung, so ist P OSET eine O-Kategorie. Sicher ist auch jede Unterkategorie einer O-Kategorie eine O-Kategorie, wenn man den Morphismenmengen die Ordnungen der Oberkategoriemorphismenmengen gibt. Sämtliche Bereichskategorien mit der punktweisen Ordnung auf den Morphismenmengen sind also O-Kategorien.

Zwischen den verschiedenen Morphismenmengen einer O-Kategorie gibt es Beziehungen. Sind nämlich A, B und C Objekte von C und ist φ ∈ [A → B], so folgt aus der Monotonie von ∘, daß f ↦ ϕ ∘ f eine monotone Abbildung von [C → A] nach [C → B] ist. Ist ϕ ein C-Isomorphismus, so ist diese Abbildung ein Ordnungsisomorphismus. Genauso ist f ↦ f ∘ ϕ eine monotone Abbildung von [B → C] nach [A → C], falls ϕ ein C-Morphismus ist, und ein Ordnungsisomorphismus, falls ϕ ein C-Isomorphismus ist.

Definition 2.2 Sei I eine kleine Kategorie und C eine O-Kategorie. Ein schwaches Diagramm D : I → C besteht aus einem Paar von Abbildungen

(D_{ob} : Ob(I) → Ob(C), D_{mor} : Mor(I) → Mor(C)),

mit den folgenden Eigenschaften:

(i) Sind i, j ∈ Ob(I), und ist a ∈ [i → j], so ist D_{mor}(a) ∈ [D_{ob}(i) → D_{ob}(j)].

(ii) Ist i ∈ Ob(I), so ist D_{mor}(id_{i}) = id_{D_{ob}(i)}.

(iii) Sind i, j, k ∈ Ob(I), a ∈ [i → j] und b ∈ [j → k], so ist

D_{mor}(b ∘ a) ≥ D_{mor}(b) ∘ D_{mor}(a).

D(i)

[figure: D(b ∘ a)]

D(j) {D(a) \atop ∨} \overline{_{D(b)>}} D(k)

Die Elemente des Bildes von D_{ob} nennen wir Diagrammobjekte von D, die Elemente des Bildes von D_{mor} nennen wir verbindende Morphismen von D. Eine schwach natürliche Transformation τ von D : I → C nach E : I → C ist eine Abbildung von Ob(I) nach Mor(C), derart daß

E(a) ∘ τ(i) ≤ τ(j) ∘ D(a)

für alle i, j ∈ Ob(I) und alle a ∈ [i → j].

D(i) \overline{\frac{D(a)}{>}} D(j)

≤

E(i) {τ(i) \atop ∨} \overline{_{E(a)>}} E(j)^{∨τ(j)}

Wir definieren nun eine Kategorie CI_{schwach}:

Objekte: schwache Diagramme von I nach C

Morphismen: schwach natürliche Transformationen

Verknüpfungsoperation: (τ ˙∘ν)(i) := τ(i) ∘ ν(i)

Proposition 2.1 a) CI_{schwach} ist eine Katgorie.

b) Isomorphismen in der Kategorie CI_{schwach} sind gerade natürliche Isomorphismen.

Beweis:

a) Seien τ : D → E und ν : E → F schwach natürliche Transformationen, und seien i, j ∈ Ob(I) und a ∈ [i → j].

D(i) \overline{\frac{D(a)}{>}} D(j)

≤

E(i) {τ(i) \atop ∨} \overline{\frac{E(a)}{>}} E(j)^{∨τ(j)}

≤

F (i) {ν(i) \atop ∨} \overline{_{F (a)>}} F (j)^{∨ν(j)}

F (a) ∘ (ν ˙∘τ)(i) = F (a) ∘ ν(i) ∘ τ(i)
≤ ν(j) ∘ E(a) ∘ τ(i)
≤ ν(j) ∘ τ(j) ∘ D(a)
= (ν ˙∘τ)(j) ∘ D(a).

Die Hintereinanderausführung zweier schwach natürlicher Transformationen ist also wieder eine schwach natürliche Transformation. Die Assoziativität von ˙∘ folgt aus der Assoziativität von ∘. Die Transformation, die jedes Objekt von I auf die Identität von D(i) abbildet, dient als Identität von D.

b) Sei τ : D → E ein CI_{schwach}-Isomorphismus. Wir stellen zunächst fest, daß τ^{−1}(i) = (τ(i))^{−1} für alle i ∈ Ob(I). Es ist

E(a) ∘ τ(i) = τ(j) ∘ τ^{−1}(j) ∘ E(a) ∘ τ(i)
≥ τ(j) ∘ D(a) ∘ τ^{−1}(i) ∘ τ(i)
= τ(j) ∘ D(a).

Definition 2.3 Sei I eine kleine Kategorie und C eine O-Kategorie. Δ : C → CI_{schwach} bezeichne den Diagonalfunktor. Für ein Objekt A von C ist also (ΔA)(i) = A für alle Objekte i von I und (ΔA)(a) = id_{A} für alle Morphismen a von I. Für einen Morphismus f von C ist (Δf)(i) = f für alle Objekte i von I. Sei nun ein schwaches Diagramm D : I → C gegeben. Ein schwacher Kegel über D sei ein Paar (A, τ) von einem Objekt A aus C und einem Pfeil τ : ΔA → D aus C_{schwach}^{I}.

A

[figure: τ(i); ≤; τ(j)]

D(i)  \overline{_{D(a)  >}} D(j)

Die Elemente des Bildes von τ wollen wir Projektionen von (A, τ) nennen, und das Objekt A nennen wir Spitze von (A, τ). Ein schwacher Kegel (A, τ) heiße Hyperlimeskegel über D, falls er ein universeller Pfeil von Δ nach D ist, d.h. falls es für alle schwachen Kegel (B, ν) über D genau einen Pfeil f von B nach A gibt, so daß τ ˙∘Δf = ν.

B

[figure: ν(i); ν(j)]

A \begin{matrix}∃!f \\ ∨ \end{matrix}

[figure: τ(i); ≤; τ(j)]

D(i)  \overline{_{D(a)  >}} D(j)

Die Projektionen eines Hyperlimeskegels über D nennen wir Hyperlimesprojektionen über D, die Spitze eines Hyperlimeskegels über D nennen wir Hyperlimesobjekt über D. Schreiben wir hypD, so meinen wir damit irgendein Hyperlimesobjekt über D.

Aus der Definition eines Hyperlimeskegels als universellen Pfeil folgt, daß ein Hyperlimeskegel bis auf natürliche Isomorphie eindeutig ist. Das heißt: Sind (A, τ) und (B, ν) zwei Hyperlimeskegel über demselben schwachen Diagramm D, so gibt es einen Isomorphismus φ : A → B, so daß ν ˙∘Δφ = τ und τ ˙∘Δφ^{−1} = ν.

2.2 Hyperlimeskegel in POSET und DCPO

Alle Kategorien, die wir in der Einleitung definiert haben, fassen wir im weiteren als O-Kategorien auf, und zwar mit der punktweisen Ordnung auf den Morphismenmengen. Einige Eigenschaften solcher O-Kategorien:

• In P OSET, BC, und DCP O sind die Morphismenmengen Objekte der Kategorie.

• Ist M eine Teilmenge von [B → C], deren punktweises Supremum existiert, und ist g ein Element von [A → B], so ist (⋁ M) ∘ g = ⋁(M ∘ g). Insbesondere: In jeder vollen Unterkategorie von DCP O ist (⋁ ^{↑}M) ∘ g = ⋁ ^{↑}(M ∘ g) für jede gerichtete Teilmenge M von [B → C]. In jeder vollen Unterkategorie von BC ist (⋁ M)∘g = ⋁(M ∘g) für jede beschränkte Teilmenge M von [B → C], also für jede Teilmenge M, deren Supremum existiert.

• In DCP O ist ∘ nicht nur monoton, sondern sogar stetig.

Proposition 2.2 In P OSET und DCP O existieren Hyperlimeskegel über beliebigen schwachen Diagrammen. Ist nämlich D ein schwaches Diagramm in einer dieser Kategorien, so ist ein Hyperlimeskegel (A, p) über D gegeben durch:

A := {(x_{i})_{i∈ObI} ∈ ∏_{i∈ObI} D(i) | ∀i, j ∈ ObI.∀a ∈ [i → j].D(a)(x_{i}) ≤ x_{j}},

mit der komponentenweisen Ordnung.

p(j) : \{ \begin{matrix}A → D(j) \\ (x_{i})_{i∈ObI} ↦ x_{j} \end{matrix}

Den so definierten Hyperlimeskegel nennen wir kanonischen Hyperlimeskegel über D.

Beweis: Sei zunächst D ein Diagramm von I nach P OSET. Daß die p(i) monoton sind, ist äquivalent dazu, daß A die komponentenweise Ordnung trägt. Sei (B, g) ein schwacher Kegel über D. Die Funktion h von B nach A sei gegeben durch die Vorschrift x ↦ (g(i)(x))_{i∈ObI}. Für jeden Pfeil a von i nach j und jedes x aus B ist D(a) ∘ g(i)(x) ≤ g(j)(x), da [B → D(j)] punktweise geordnet ist. h(x) ist also ein Element von A. Weil die g(i) monoton sind, und die Ordnung auf A komponentenweise definiert ist, ist h monoton. Weil zwei Funktionen gleich sind, wenn sie an jeder Stelle den gleichen Funktionswert haben, ist p(i) ∘ h = g(i) für jedes Objekt i von I. Sei nun h′ eine weitere monotone Abbildung von B nach A, so daß p(i) ∘ h′ = g(i) für alle Objekte i von I. Dann ist (h′(x))_{i} = g(i)(x) = (h(x))_{i} für alle Objekte i von I und alle Elemente x von B. Da zwei Elemente von A gleich sind, falls sämtliche Komponenten gleich sind, und da zwei Funktionen gleich sind, falls sie an jeder Stelle den gleichen Funktionswert haben, ist dann h = h′. Sei nun D ein Diagramm nach DCP O. Sei M eine gerichtete Teilmenge von A, und sei a ein Pfeil von i nach j. Da p(i) monoton ist, ist p(i)(M) gerichtet. Es ist

D(a)(⋁ ^{↑}p(i)(M)) = ⋁ ^{↑}D(a) ∘ p(i)(M) ≤ ⋁ ^{↑}p(j)(M)

A als Teilmenge von ∏_{i∈ObI} D(i) ist also abgeschlossen gegen gerichtete Suprema. Das heißt A ist ein Bereich, und die p(i) sind stetig. Für einen schwachen Kegel (B, g) über D ist das oben definierte h stetig, weil die g(i) stetig sind, und weil gerichtete Suprema in A komponentenweise gebildet werden.

Proposition 2.3 Sei D : I → P OSET ein schwaches Diagramm, (hypD, p) ein Hyperlimeskegel über D und A eine geordnete Menge.

a) Für f, g ∈ [A → hypD] ist

f ≤ g ⇔ ∀i ∈ ObI. p(i) ∘ f ≤ p(i) ∘ g

Die Implikation von rechts nach links gilt auch in beliebigen O-Kategorien, die von links nach rechts jedoch nicht.

b) Sogar mehr: Der Funktor [A → ..] erhält Hyperlimites.

Genauer: Der Endofunktor F auf P OSET sei definiert durch:

F (B) = [A → B]  für Objekte B
F (f : B → C)(g) = f ∘ g  für Morphismen f

\begin{matrix}[A & \overline{g >} & B] \\ [A & \overline{\overline{>}} & C] & ^{∨f} \end{matrix}

Dann ist (F (hypD), F p) ein Hyperlimeskegel über F ∘ D.

[A → hypD]

[figure: g ↦ p(i) ∘ g; ≤; g ↦ p(j) ∘ g]

[A → D(i)] \overline{_{g ↦ D(a) ∘ g>}} [A → D(j)]

c) Aussagen a) und b) gelten auch in der Kategorie DCP O, falls D ein Diagramm in DCP O und A ein Bereich ist.

Beweis:

a) Wir nehmen an (hypD, p) sei der kanonische Hyperlimeskegel über D.

∀i ∈ ObI. p(i) ∘ f ≤ p(i) ∘ g ⇔ ∀i ∈ ObI. ∀x ∈ A. (f(x))_{i} ≤ (g(x))_{i}
⇔ ∀x ∈ A. f(x) ≤ g(x)
⇔ f ≤ g

Wir stellen fest, daß die Implikation von rechts nach links auch aus der Monotonie der Verknüpfungsoperation folgt,

b) Daraus, daß die Morphismenmengen von P OSET punktweise geordnet sind, folgt, daß F (f) monoton ist, falls f monoton ist, und daß F (f) ≤ F (g), falls f ≤ g. Also operiert F monoton auf den Morphismenmengen. F ∘ D ist ein schwaches Diagramm, denn

(F ∘ D)(f ∘ g) = F (D(f ∘ g))
≤ F (D(f) ∘ D(g))
= F (D(f)) ∘ F (D(g))
= (F ∘ D)(f) ∘ (F ∘ D)(g)

(F (hypD), F p) ist ein schwacher Kegel über F ∘ D, denn

F (D(f)) ∘ F (p(i)) = F (D(f) ∘ p(i)) ≤ F (p(j))

Sei nun B das kanonische Hyperlimesobjekt über F ∘ D, also B = {(g_{i})_{i∈ObI} ∈ ∏[A → D(i)] | ∀a : i → j.F (D(a))(g_{i}) ≤ (g_{j})}. Wir zeigen, daß durch die Vorschrift g ↦ (g_{i})_{i∈ObI} ein Isomorphismus ϕ von [A → hypD] nach B gegeben ist. Die Monotonie und die Injektivität von ϕ folgen aus a). Sei (g_{i})_{i∈ObI} ∈ B. Wir definieren ein g ∈ [A → hypD] durch p(i) ∘ g = g_{i}. Es ist D(a) ∘ g_{i} = F (D(a))(g_{i}) ≤ g_{j} für alle Pfeile a von i nach j. Also ist g wohldefiniert. Damit ist ϕ surjektiv. Die Monotonie von ϕ^{−1} folgt aus a).

c) Weil [A → B]_{Dcpo} die von [A → B]_{P oset} induzierte Ordnung trägt, gilt a). Daraus, daß gerichtete Suprema in den Morphismenmengen punktweise gebildet werden, folgt, daß F (B) ein Bereich ist, falls B ein Bereich ist, und daß F (f) stetig ist, falls f stetig ist. F ∘D ist also ein Diagramm in DCP O, falls D ein Diagramm in DCP O ist. In Proposition 2.2 haben wir gesehen, daß ein schwacher Kegel eines Diagrammes in DCP O genau dann ein Hyperlimeskegel in DCP O ist, wenn er ein Hyperlimeskegel in P OSET ist. (F (hypD), F p) ist also ein Hyperlimeskegel in DCP O über F ∘ D.

Wir werden nun einige Beispiele für Hyperlimites in P OSET und DCP O geben:

a)

Ein Limes über einem endlichen kogerichteten Diagramm ist isomorph zum maximalen Objekt des Diagramms. An dem ersten Beispiel sieht man, daß das bei Hyperlimites nicht so sein muß. So gesehen ähnelt ein zykelfreier Hyperlimes in P OSET mehr einem Produkt als einem Limes.

b) Lassen wir Zykel im Diagramm zu, so können wir gewisse Limites in P OSET auch als Hyperlimites über Diagrammen, die auf den Objekten mit den Limesdiagrammen übereinstimmen, beschreiben:

Proposition 2.4 Sei D : I → P OSET ein Diagramm, derart daß jeder verbindende Morphismus eine obere Adjungierte ist. Für eine obere Adjungierte f von A nach B bezeichne f^{∗} die zugehörige untere Adjungierte von B nach A. Der gerichtete Graph G sei gegeben durch

V (G) := Ob(I) und E(i, j) := [i → j] ˙∪[j → i] für i, j ∈ Ob(I)

Ĩ sei die von diesem gerichteten Graphen erzeugte Kategorie. Das Diagramm D̃ : Ĩ → P OSET sei gegeben durch

D̃(i) := D(i) für i ∈ V (G)

D̃(a : i → j) := \{ \begin{matrix}D(a) & falls a ∈ [i → j]_{I} \\ D(a)^{∗} & falls a ∈ [j → i]_{I} \end{matrix} für a ∈ E(G)

Ist nun (P, p) ein Limeskegel über D, so ist (P, p) auch ein Hyperlimeskegel über D̃.

Beweis: Bezeichne hypD̃ das kanonische Hyperlimesobjekt über D̃. Zunächst zeigen wir, daß hypD̃ durch die verbindenden Morphismen über dem die Indexkategorie erzeugenden Graphen schon festgelegt ist. Wir zeigen also, daß

{(x_{i})_{i∈V (G)} ∈ ∏_{i∈V (G)} D̃(i) | ∀a : i → j ∈ E(G). D̃(a)(x_{i}) ≤ x_{j}} = hypD̃

Die Inklusion ‘⊇’ ist trivial. Sei nun x = (x_{i})_{i∈Ob(Ĩ)} ein Element der linken Menge. Sei a : i → j ein Pfeil aus Ĩ. Dann gibt es Pfeile b_{1} : i → k_{1}, b_{2} : k_{1} → k_{2}, .., b_{n} : k_{n−1} → j, so daß a = b_{n} ∘ b_{n−1} ∘ .. ∘ b_{1}. Es ist

D̃(a)(x_{i}) ≤ D̃(b_{n}) ∘ .. ∘ D̃(b_{1})(x_{i}) ≤ D̃(b_{n}) ∘ .. ∘ D̃(b_{2})(x_{k_{1}}) ≤ .. ≤ x_{j}

Da diese Ungleichung für alle Pfeile a von Ĩ gilt, ist x ein Element von hypD̃. Bezeichne nun limD das kanonische Hyperlimesobjekt über D. Sei x = (x_{i})_{i∈ObI} ein Element von limD und sei a : i → j ein Pfeil aus G. Falls a aus [i → j]_{I} kommt, so ist D̃(a)(x_{i}) = D(a)(x_{i}) = x_{j}. Falls a aus [j → i]_{I} kommt, so folgt aus D(a)(x_{j}) = x_{i}, daß x_{j} ≥ D(a)^{∗}(x_{i}). Also ist D̃(a)(x_{i}) = D(a)^{∗}(x_{i}) ≤ x_{j}. Für alle Pfeile a : i → j aus G ist also D̃(a)(x_{i}) ≤ x_{j}. Also ist x Element von hypD̃. Sei nun x = (x_{i})_{i∈ObI} ein Element von hypD̃, und sei a : i → j ein Pfeil aus I. Einerseits ist D(a)(x_{i}) = D̃(a)(x_{i}) ≤ x_{j}. Andererseits ist D(a)^{∗}(x_{j}) = D̃(a)(x_{j}) ≤ x_{i}, also D(a)(x_{i}) ≥ x_{j}. Es ist also D(a)(x_{i}) = x_{j} für alle Pfeile a : i → j aus I. Das heißt x ist ein Element von limD.

c) Eine disjunkte Summe von Bereichen mit kleinstem Element kann man auch als Hyperlimes beschreiben. Ist nämlich (A_{i})_{i∈I} eine Familie von Bereichen mit kleinstem Element, und ist das Diagramm D : I_{⊥}^{op} → DCP O gegeben durch

D(i) = A_{i} D(⊥) = I_{⊥}

D(⊥ ← i)(x) = \{ \begin{matrix}⊥ & falls x = ⊥ \\ i & sonst, \end{matrix}

so ist hypD ≃ ⨁_{i∈I} A_{i}.

d) In der Kategorie SET ist [M → N] isomorph zu ∏_{m∈M} N.

Das Pendant in der Kategorie P OSET: Seien P,Q Objekte von P OSET. Das Diagramm D von P nach P OSET sei gegeben durch:

\begin{matrix}D(x) = Q & für alle x ∈ P \\ D(y ← x) = id_{Q} & für alle (x, y) ∈≤_{P} \end{matrix}

Bezeichne weiterhin ev_{x} die Evaluierung einer Funktion f aus [P → Q] an der Stelle x. Dann ist ([P → Q], ev) ein Hyperlimeskegel über D. Folgerung: Sei A ein algebraischer Bereich und B ein Bereich. Das Diagramm D von K(A) nach DCP O sei gegeben durch

\begin{matrix}D(k) = B & für alle k ∈ K(A) \\ D(h ← k) = id_{B} & für alle (k, h) ∈≤_{K(A)} \end{matrix}

Dann ist ([A → B]_{Dcpo}, ev) ein Hyperlimeskegel über D.

e) Wir haben in der Einleitung erläutert, daß man eine Datenbank auffassen kann als eine Antikette in einem Produkt flacher Bereiche. Oft will man jedoch gewisse Einträge von vorneherein nicht zulassen. In einer Datenbank mit den Attributen ’NAME’, ’TELEFON(ja/nein?)’ und ’TELEFONNUMMER’ will man beispielsweise einen Eintrag, bei dem in der Spalte ’TELE-FON’ ein ’nein’, in der Spalte ’TELEFONNUMMER’ aber eine Nummer steht, nicht zulassen. Man würde als Datenbankbereich für so eine Datenbank das Hyperlimesobjekt über folgendem Diagramm wählen:

Wir schließen diesen Abschnitt ab mit der einfachen, aber nützlichen, Feststellung, daß Hyperlimesprojektionen über schwachen Diagrammen nach P OSET in gewissem Sinne Infima erhalten.

Proposition 2.5 Sei D : I → P OSET ein schwaches Diagramm und (P, p) ein Hyperlimeskegel über D.

a) Sei M eine Teilmenge von P, so daß das Infimum von p_{i}(M) für jedes i aus ObI existiert. Dann existiert auch das Infimum von M, und es ist p_{i}(⋀ M) = ⋀ p_{i}(M) für alle i aus ObI. Insbesondere: Sind sämtliche Objekte von D beschränkt vollständig, so ist auch P beschränkt vollständig.

b) D habe die zusätzliche Eigenschaft, daß verbindende Morphismen (endliche) Suprema erhalten. Sei M eine (endliche) Teilmenge von P, so daß für alle i aus ObI das Supremum von p_{i}(M) existiert. Dann existiert das Supremum von M, und es ist p_{i}(⋁ M) = ⋁ p_{i}(M) für alle i aus ObI.

Beweis:

a) Sei a : i → j ∈ MorI. Für alle m aus M ist

D(a)(⋀ p_{i}(M)) ≤ D(a)(p_{i}(m)) ≤ p_{j}(m)

Also ist D(a)(⋀ p_{i}(M)) ≤ ⋀ p_{j}(M). Das kanonische Hyperlimesobjekt über D ist also eine gegen Infima abgeschlossene Teilmenge des Produktes der Diagrammobjekte.

b) Sei a : i → j ∈ MorI.

D(a)(⋁ p_{i}(M)) = ⋁ D(a)(p_{i}(M)) ≤ ⋁ p_{j}(M)

Das kanonische Hyperlimesobjekt über D ist also eine gegen (endliche) Suprema abgeschlossene Teilmenge des Produktes der Diagrammobjekte.

3 Hyperlimeskegel, deren Projektionen obere Adjungierte sind

Wir haben bis jetzt keine Anforderungen an die Beschaffenheit von schwachen Diagrammen gestellt. So haben wir beispielsweise mehrere verbindende Morphismen zwischen zwei Objekten erlaubt. Andererseits kann man zu einer gegebenen Familie von Objekten oft mehrere Familien von verbindenden Morphismen angeben, die den gleichen Hyperlimes spezifizieren. Hat nun ein schwaches Diagramm die Eigenschaft, daß jede Hyperlimesprojektion obere Adjungierte ist, so kann man die ursprünglichen verbindenden Morphismen durch eine neue Familie von verbindenden Morphismen ersetzen, so daß es nur jeweils einen verbindenden Morphismus von einem Objekt zu einem anderen gibt. Wie diese Konstruktion genau funktioniert, beschreibt die nächste Proposition. Zunächst noch eine Schreibweise: Ist f : A → B eine Abbildung und C eine Teilmenge von A, so schreiben wir für die Restriktion von f auf C einfach f′, falls aus dem Zusammenhang klar ist, was die Menge C ist. Ist C eine Teilmenge von B, die das Bild von f enthält, so schreiben wir ′f für die Korestriktion von f auf C.

Proposition 3.1 Sei D : I → P OSET ein schwaches Diagramm, derart daß Hyperlimesprojektionen über D obere Adjungierte sind. Sei (P, p) ein Hyperlimeskegel über D. Für jedes Objekt i von I bezeichne d_{i} die untere Adjungierte zu p_{i}. Die Indexkategorie Ĩ habe die gleichen Objekte wie I, und von jedem Objekt gebe es genau einen Pfeil zu jedem anderen Objekt. ( Die Verknüpfungsoperation liegt dann bereits fest.) Das schwache Diagramm D̃ : Ĩ → P OSET sei gegeben durch

D̃(i) = im(p_{i})  für i ∈ Ob(I)
D̃(j ← i) = ′p_{j} ∘ d′_{i}  für (i, j) ∈ (Ob(I))^{2}

Dann ist (P, (′p_{i})_{i∈ObI}) ein Hyperlimeskegel über D̃.

Beweis: D̃ ist ein schwaches Diagramm, denn

D̃(k ← j) ∘ D̃(j ← i) = ′p_{k} ∘ d′_{j} ∘′p_{j} ∘ d′_{i} ≤ ′p_{k} ∘ d′_{i} = D̃(k ← i)

Das Ungleicheitszeichen steht, weil d′_{j} ∘′p_{j} kleiner ist als die Identität. (P,′p) ist ein schwacher Kegel, denn

D̃(j ← i) ∘′p_{i} = ′p_{j} ∘ d′_{i} ∘′p_{i} ≤ ′p_{j}

Sei nun (Q, q) ein weiterer schwacher Kegel über D̃. (Q, p˙∘d′ ˙∘q) ist ein schwacher Kegel über D, denn für jeden Pfeil a : i → j von I ist:

Q

[figure: q_{i}; ≤; q_{j}]

im(p_{i})  \overline{_{′p_{j} ∘ d′_{i}  >}} im(p_{j})

P {d′_{i} \atop ∨}  P^{∨d′_{j}}

[figure: p_{j}]

D(i) {p_{i} \atop ∨}  \overline{_{D(a)  >}} D(j)^{∨p_{j}}

D(a) ∘ p_{i} ∘ d′_{i} ≤ p_{j} ∘ d′_{i}
= p_{j} ∘ d′_{j} ∘′p_{j} ∘ d_{i}
D(a) ∘ p_{i} ∘ d′_{i} ∘ q_{i} ≤ p_{j} ∘ d′_{j} ∘′p_{j} ∘ d′_{i} ∘ q_{i}
= p_{j} ∘ d′_{j} ∘ D̃(j ← i) ∘ q_{i}
≤ p_{j} ∘ d′_{j} ∘ q_{j}

Das Gleicheitszeichen in der ersten Ungleichungskette steht, weil p_{j} ∘ d_{j} ∘ p_{j} = p_{j}. In der zweiten Ungleichungskette verwenden wir die erste Ungleichung. Da (P, p) ein Hyperlimeskegel über D ist:

(∗) ∃!g : Q → P. p˙∘d′ ˙∘q = p˙∘Δg

Dann ist aber

q = ′p˙∘d′ ˙∘q = ′p˙∘Δg,

wobei das erste Gleichheitszeichen steht, weil ′p_{i} ˙∘d′_{i} = id_{im(p_{i})}. Sei f : Q → P ein Morphismus, so daß ′p˙∘Δf = q. Dann ist

p˙∘d′ ˙∘q = p˙∘d′ ˙∘′p˙∘Δf = p˙∘Δf

Wegen (∗) ist dann f = g.

Definition 3.1 Ein schwaches Diagramm heiße einfach, falls es von jedem Diagrammobjekt zu jedem anderen höchstens einen verbindenden Morphismus gibt.

Folgerung 3.1 Zu einem schwachen Diagramm D in P OSET, dessen Hyperlimesprojektionen obere Adjungierte sind, gibt es ein einfaches schwaches Diagramm E, dessen Objekte die Bilder der Hyperlimesprojektionen über D sind, so, daß hypD ≃ hypE.

Hyperlimesprojektionen über einem schwachen Diagramm von geordneten Mengen, müssen nicht surjektiv sein. Man kann im allgemeinen auch nicht die verbindenen Morphismen durch Morphismen zwischen den Bildern der Hyperlimesprojektionen ersetzen, ohne den Hyperlimes zu ändern. Sind die Hyperlimesprojektionen jedoch obere Adjungierte, so geht das, wie wir in Proposition 3.1 gesehen haben:

Folgerung 3.2 Zu einem schwachen Diagramm D in P OSET, dessen Hyperlimesprojektionen obere Adjungierte sind, gibt es ein schwaches Diagramm E mit surjektiven Hyperlimesprojektionen, so, daß die Bilder der Hyperlimesprojektionen über D gerade die Objekte von E sind und daß hypD ≃ hypE.

Betrachten wir noch einmal das schwache Diagramm D aus Proposition 3.1. Falls es keinen verbindenden Morphismus von einem Objekt D(i) nach einem anderen Objekt D(j) gibt, so können wir auch im Diagramm D̃ auf den verbindenden Morphismus von D̃(i) nach D̃(j) verzichten:

Proposition 3.2 Voraussetzungen und Bezeichnungen seien wie in Proposition 3.1. Bezeichne außerdem |I| die durch die Kategorie I definierte Präordnung {(i, j) ∈ (ObI)^{2} | [i → j] ≠ ∅} auf ObI. Dann ist (P,′p) ein Hyperlimeskegel über der Restriktion von D̃ auf |I|.

Beweis: gleicher Beweis wie für Proposition 3.1.

Definition 3.2 Ein schwaches Diagramm D heiße zykelfrei, falls es keine zwei verschiedenen Objekte i und j gibt, so daß es sowohl einen verbindenden Morphismus von D(i) nach D(j) als auch einen von D(j) nach D(i) gibt, und D außer den Identitäten keine verbindenden Endomorphismen hat.

Folgerung 3.3 Zu einem zykelfreien schwachen Diagramm D in P OSET, dessen Hyperlimesprojektionen obere Adjungierte sind, gibt es ein zykelfreies, einfaches schwaches Diagramm E, dessen Objekte die Bilder der Hyperlimesprojektionen über D sind, so, daß hypD ≃ hypE.

Noch eine weitere kleine Ergänzung zu Proposition 3.1:

Proposition 3.3 Voraussetzungen und Bezeichnungen seien wie in Proposition 3.1. Für beliebige Objekte i, j von Ĩ ist dann

d′_{j} ∘ D̃(j ← i) ≤ d′_{i}.

(P, d) ist also ein schwacher Kokegel über D̃.

Beweis: d′_{j} ∘ D̃(j ← i) = d′_{j} ∘′p_{j} ∘ d′_{i} ≤ d′_{i}

Haben sämtliche Hyperlimesprojektionen über einem schwachen Diagramm geordneter Mengen untere Adjungierte, so findet man die Bilder der Hyperlimesprojektionen als Bilder interner Projektionen im Hyperlimesobjekt wieder. Nicht nur das, auch die verbindenden Morphismen des Diagrammes aus Proposition 3.1 sind nichts weiter als Restriktionen und Korestriktionen interner Projektionen des Hyperlimesobjektes. Sei nun umgekehrt eine Menge M interner Projektionen einer geordneten P gegeben. Zu dieser Menge definieren wir ein schwaches Diagramm D_{M} : I_{M} → P OSET. Dabei sei I_{M} die Kategorie, deren Objektmenge gleich M ist, und bei der es von jedem Objekt zu jedem anderen genau einen Pfeil gibt.Es seien

D_{M}(p) := im(p)  für p ∈ M
D_{M}(p ← q) := ′p′  für (p, q) ∈ M^{2}.

Was für Bedingungen muß man an M stellen, damit P isomorph ist zu hyp(D_{M}) ?

Proposition 3.4

a) Sei D : I → P OSET ein schwaches Diagramm derart, daß Hyperlimesprojektionen über D obere Adjungierte sind. Sei (P, p) ein Hyperlimeskegel über D, und für jedes Objekt i von I bezeichne d_{i} die untere Adjungierte zu p_{i}. Bezeichne M die Menge {d_{i} ∘ p_{i} | i ∈ ObI}. Dann hat M folgende Eigenschaften:

(i) id_{P} ist punktweises Supremum von M.

(ii) Ist (x_{p})_{p∈M} ∈ ∏_{p∈M} im(p), derart daß p(x_{q}) ≤ x_{p} für alle p, q ∈ M, dann hat {x_{p} | p ∈ M} ein Supremum.

(iii) Ist (x_{p})_{p∈M} ∈ ∏_{p∈M} im(p), derart daß p(x_{q}) ≤ x_{p} für alle p, q ∈ M, dann ist q(⋁_{p∈M} x_{p}) = x_{q} für alle q ∈ M.

Ist D ein Diagramm in DCPO, so sind alle Elemente von M stetig.

b) Umgekehrt: Sei P eine geordnete Menge und M eine Menge interner Projektionen von P, welche Bedingungen (i) bis (iii) erfüllt. Dann ist (P, (′p)_{p∈M}) ein Hyperlimeskegel über D_{M}. Sind sämtliche Elemente von M stetig, so ist D_{M} ein Diagramm in DCPO.

Beweis:

a) (i) Sei x ∈ P. Sicher ist x eine obere Schranke von {d_{i} ∘ p_{i}(x) | i ∈ Ob(I)}. Sei y ∈ P eine weitere obere Schranke dieser Menge. Dann ist p_{i}(y) ≥ p_{i} ∘ d_{i} ∘ p_{i}(x) = p_{i}(x) für alle Objekte i von I. Also ist y ≥ x.

(ii),(iii) Sei D̃ das Diagramm aus Proposition 3.1. Da ′d′_{i} ein Isomorphismus von im(p_{i}) nach im(d_{i}) ist mit der Inversen ′p′_{i}, ist durch τ(i) = ′d′_{i} ein natürlicher Isomorphismus von D̃ nach D_{M} gegeben.

\begin{matrix}im(p_{i}) = D̃(i) & \overline{′p_{j} ∘ d′_{i} = D̃(j ← i) >} & im(p_{j}) = D̃(j) \\ im(d_{i}) = D_{M}(i) & ^{{′d′_{i} \atop ∨} ∧′p′_{i}} & \overline{_{′d_{j} ∘ p′_{j} = D_{M}(j ← i) >}} & im(d_{j}) = D_{M}(j) & ^{{′d′_{j} \atop ∨} ∧′p′_{j}} \end{matrix}

Bezeichne (Q, q) den kanonischen Hyperlimeskegel über D_{M}. Durch q ˙∘Δφ = ′d˙∘p ist ein Isomorphismus φ von P nach Q gegeben, dessen Umkehrabbildung gegeben ist durch ′p˙∘φ^{−1} = ′p′ ˙∘q.

\begin{matrix}P & \overline{φ >} & Q & Q & \overline{φ^{−1} >} & P \\ D̃(i) & {′p_{i} \atop ∨} & \overline{_{′d′_{i}>}} & D_{M}(i) & ^{∨q_{i}} & D_{M}(i) & ^{∨q_{i}} & \overline{_{′p′_{i} >}} & D̃(i) & {′p_{i} \atop ∨} \end{matrix}

Es ist

φ^{−1} = id ∘ φ^{−1}
= ( ⋁_{i∈ObI} d_{i} ∘ p_{i}) ∘ φ^{−1}
= ⋁_{i∈ObI}(d_{i} ∘ p_{i} ∘ φ^{−1})
= ⋁_{i∈ObI}(d_{i} ∘ p′_{i} ∘ q_{i})

Sei x = (x_{i})_{i∈ObI} ∈ ∏ im(d_{i} ∘ p_{i}), so daß d_{i} ∘ p_{i}(x_{j}) ≤ x_{i} für alle i, j ∈ Ob(I). Wir müssen zeigen, daß {x_{i} | i ∈ I} eine kleinste obere Schranke hat. Wir behaupten, daß diese gegeben ist durch φ^{−1}(x). Es ist x ∈ Q und

φ^{−1}(x) = ⋁_{i∈ObI} d_{i} ∘ p′_{i} ∘ q_{i}(x) = ⋁_{i∈ObI} d_{i} ∘ p′_{i}(x_{i}) = ⋁_{i∈ObI} x_{i}

Nun zu Eigenschaft (iii):

d_{j} ∘ p_{j}( ⋁_{i∈ObI} x_{i}) = ′d_{j} ∘ p_{j} ∘ φ^{−1}(x) = q_{j} ∘ φ ∘ φ^{−1}(x) = q_{j}(x) = x_{j}

b) Bezeichne (P̃, (p̃)_{p∈M}) den kanonischen Hyperlimeskegel über D_{M}. Wir zeigen, daß

φ : P → P̃, p̃ ∘ φ = ′p

ein Isomorphismus ist mit der Umkehrabbildung

ψ : P̃ → P , ψ(x) = ⋁_{p∈M} p̃(x).

‘φ wohldefiniert’:

Seien p, q ∈ M. Dann ist ′q′ ∘ p̃ ∘ ψ = ′q′ ∘′p ≤ ′q.

‘ψ wohldefiniert’:

Sei x = (x_{p})_{p∈M} ∈ P̃. Wegen (ii) existiert dann ⋁_{p∈M} x_{p} = ⋁_{p∈M} p̃(x).

‘φ ∘ ψ = idP̃’:

Sei x ∈ P̃. Es ist

p̃ ∘ φ ∘ ψ = ′p ∘ ψ(x) = ′p( ⋁_{q∈M} q̃(x)) = ′p( ⋁_{q∈M} x_{q}) = x_{p}.

Das letzte Gleichheitszeichen steht wegen (iii).

‘ψ ∘ φ = id_{P} ’:

Sei x ∈ P. Es ist

ψ ∘ φ(x) = ⋁_{p∈M} p̃ ∘ φ(x) = ⋁_{p∈M} ′p(x) = x.

Das letzte Gleichheitszeichen steht wegen (i).

Für keine Menge M von internen Projektionen ist D_{M} zykelfrei. Es gibt jedoch sicher zykelfreie Diagramme, deren Hyperlimesprojektionen obere Adjungierte sind. Man betrachte nur ein Produkt von geordneten Mengen mit kleinstem Element. Wie kann man sehen, ob M von einem zykelfreien Diagramm herrührt?

Proposition 3.5 Sei D : I → P OSET ein schwaches Diagramm, so daß Hyperlimesprojektionen über D obere Adjungierte sind. Sei (P, p) ein Hyperlimeskegel über D, und für jedes Objekt i von I bezeichne d_{i} die untere Adjungierte zu p_{i}. Seien weiterhin i und j Objekte von I, so daß es keinen Pfeil von j nach i gibt. Dann ist d_{i} ∘ p_{i} ∘ d_{j} ∘ p_{j} kleinstes Element der Menge Q_{P} aller internen Projektionen von P.

Beweis: Wir zeigen zunächst, daß p_{i} ∘ d_{j} auf jeder Zusammenhangskomponente des Bildes von p_{j} konstant ist. Für zwei Elemente u, v von P mit u ≤ v sei das Element u ⋆ v von P definert durch

p_{k}(u ⋆ v) = \{ \begin{matrix}p_{k}(v) & falls [j → k] ≠ ∅ \\ p_{k}(u) & falls [j → k] = ∅ \end{matrix}

Da es keinen Pfeil von einem Objekt k mit [j → k] ≠ ∅ nach einem Objekt h mit [j → h] = ∅ gibt, ist dadurch ein Element des Produktes der Diagrammobjekte definiert, welches ‘verträglich’ ist mit den verbindenden Morphismen. Seien x, y ∈ im(p_{j}), so daß x ≤ y. Dann ist p_{j}(d_{j}(x) ⋆ d_{j}(y)) = p_{j} ∘ d_{j}(y) = y, denn [j → j] ist nichtleer. Weil d_{j} die untere Adjungierte zu p_{i} ist, ist dann d_{j}(x) ⋆ d_{j}(y) ≥ d_{j}(y). Da wir [j → i] als leer vorausgesetzt haben, ist p_{i}(d_{j}(x) ⋆ d_{j}(y)) = p_{i} ∘ d_{j}(x), und es ist p_{i} ∘ d_{j}(x) = p_{i}(d_{j}(x) ⋆ d_{j}(y)) ≥ p_{i} ∘ d_{j}(y). Mit der Monotonie von p_{i} ∘ d_{j} erhalten wir dann p_{i} ∘ d_{j}(x) = p_{i} ∘ d_{j}(y). Da diese Gleichung für alle x, y ∈ im(p_{j}) mit x ≤ y gilt, ist p_{i} ∘ d_{j} auf jeder Zusammenhangskomponente des Bildes von p_{j} konstant. Da p_{j}, als monotone Abbildung, Zusammenhangskomponenten von P auf zusammenhängende Teilmengen von D(j) abbildet, ist dann p_{i} ∘ d_{j} ∘ p_{j} konstant auf den Zusammenhangskomponenten von P. Also ist auch d_{i}∘p_{i}∘d_{j}∘p_{j} konstant auf den Zusammenhangskomponenten von P. Da d_{i}∘p_{i}∘d_{j}∘p_{j} kleiner ist als die Identität, hat dann jede Zusammenhangskomponente von P ein kleinstes Element, und d_{i} ∘p_{i} ∘d_{j} ∘p_{j} bildet ein Element x ab auf das kleinste Element der Zusammenhangskomponente von x. Diese Abbildung ist sicher das kleinste Element von Q_{P}.

Definition 3.3 Sei P eine geordnete Menge und M eine Teilmenge von Q_{P}. Wir definieren eine Präordnung ≤^{∗} auf M: Falls Q_{P} kein kleinstes Element hat, so sei ≤^{∗}= M^{2}. Falls Q_{P} ein kleinstes Element hat, so sei

pRq ⇔^{def} q ∘ p ≠ ⊥_{Q_{P}}

und ≤^{∗} sei die reflexive und transitive Hülle von R.

Betrachten wir die Situation aus Proposition 3.4 a). Wir haben die ∗-Präordnung auf {d_{i} ∘ p_{i} | i ∈ Ob(I)} so definiert, daß sie eine Teilmenge der Präordnung ist, welche durch |I| auf {d_{i} ∘ p_{i} | i ∈ Ob(I)} induziert wird:

Proposition 3.6 Voraussetzungen wie in Proposition 3.4 a). Sind i und j Objekte der Indexkategorie I, so daß d_{i} ∘ p_{i} ≤^{∗} d_{j} ∘ p_{j}, so ist [i → j] nichtleer. Insbesondere: Ist D zykelfrei, so ist die ∗-Präordnung auf {d_{i} ∘ p_{i} | i ∈ Ob(I)} eine Ordnung.

Beweis: Nach Proposition 3.5 ist

{(d_{i} ∘ p_{i}, d_{j} ∘ p_{j}) | d_{i} ∘ p_{i} ∘ d_{j} ∘ p_{j} ≠ ⊥_{Q_{P}} } ⊆ {(d_{i} ∘ p_{i}, d_{j} ∘ p_{j}) | [i → j] ≠ ∅}

Die rechte Seite der Ungleichung ist reflexiv und transitiv. Die ∗-Präordnung ist die reflexive und transitive Hülle der linken Seite der Ungleichung, ist also in der rechten Seite enthalten. Ist D zykelfrei, so ist die rechte Seite der Ungleichung eine Ordnung. Als Teilmenge einer Ordnung, ist die ∗-Präordnung dann antisymmetrisch.

Betrachten wir umgekehrt die Situation aus Proposition 3.4 b). Hat D_{M|≤∗} den gleichen Hyperlimes wie D_{M}?

Proposition 3.7 Voraussetzungen wie in 3.4 b). Zusätzlich sei P ordnungszusammenhängend. Dann ist (P, (′p)_{p∈M}) ein Hyperlimeskegel über D_{M|≤∗}.

Beweis: Ist P zusammenhängend und Q_{P} hat ein kleinstes Element, so hat P ein kleinstes Element. Das kleinste Element von Q_{P} ist gleich dem kleinsten Element von [P → P], nämlich die konstante Abbildung auf das kleinste Element von P. Sei (p, q) aus M^{2}\ ≤^{∗}. Nach Definition der ∗-Präordnung ist q ∘ p die konstante ⊥-Abbildung. Also ist D_{M}(q ← p) = ′q_{|im(p)} die konstante ⊥-Abbildung. In POSET ist ⊥ ∘ f = ⊥ für jeden Morphismus f. Also ist jeder schwache Kegel über D_{M|≤∗} ein schwacher Kegel über D_{M}.

Wir können nicht auf die Voraussetzung, daß P ordnungszusammenhängend ist, verzichten. Zum Beispiel:

M̃ = {{a, a′, b, b′}, {a, a′, c, c′}}, M = {p_{A} | A ∈ M̃}. Für stabile Projektionen p, q ist im(p ∘ q) = im(p) ∩ im(q). Der Schnitt der beiden Elemente von M̃ ist aber gerade das Bild des kleinsten Elementes von Q_{P}. Die ∗-Präordnung auf M besteht also nur aus der Diagonalen. P ist aber nicht isomorph zu

Wie muß ein Diagramm nun beschaffen sein, damit sämtliche Hyperlimesprojektionen über dem Diagramm untere Adjungierte haben? In der nächsten Proposition geben wir ein Kriterium für Diagramme von beschränkt vollständigen geordneten Mengen an, und ein anderes für Diagramme von beliebigen geordneten Mengen.

Proposition 3.8

a) Sei D : I → BC ein schwaches Diagramm, so daß für jeden Hyperlimeskegel (P, p) über D folgendes gilt:

• ∀i ∈ Ob(I). ∀x ∈ D(i). p_{i}^{−1}(↑ x) ≠ ∅

Dann sind Hyperlimesprojektionen über D obere Adjungierte.

b) Sei D : I → P OSET ein schwaches Diagramm, so daß

• Für beliebige Objekte i, j von I existiert das punktweise Supremum von {D(a) | a ∈ [i → j]}.

• Für beliebige Objekte i, j, k von I und für alle b ∈ [j → k] ist

D(b) ∘ (⋁ {D(a) | a ∈ [i → j]}) ≤ ⋁ {D(c) | c ∈ [i → k]}.

Dann sind Hyperlimesprojektionen über D obere Adjungierte.

Ist (P, p) ein Hyperlimeskegel über D, so ist die untere Adjungierte d_{i} zu p_{i} gegeben durch

p_{j} ∘ d_{i} = ⋁ {D(a) | a ∈ [i → j]}

Beweis:

a) Sei i ein Objekt von I, und sei x ein Element von D(i). Zu zeigen ist, daß p_{i}^{−1}(↑ x) ein Minimum hat. Da wir p_{i}^{−1}(↑ x) als nichtleer und P als beschränkt vollständig vorausgesetzt haben, hat p_{i}^{−1}(↑ x) ein Infimum. Da p_{i} Infima erhält (nach Propositon 2.5), ist dieses Infimum ein Element von p_{i}^{−1}(↑ x).

b) ‘ d_{i} ist wohldefiniert’:

Seien j, k Objekte von I, und sei b ∈ [j → k].

D(b) ∘ p_{j} ∘ d_{i} = D(b) ∘ (⋁ {D(a) | a ∈ [i → j]})
≤ ⋁ {D(c) | c ∈ [i → k]}
= p_{k} ∘ d_{i}

‘p_{i} ∘ d_{i} ≥ id_{D(i)}’:

p_{i} ∘ d_{i} = ⋁ {D(a) | a ∈ [i → i]} ≥ D(id_{i}) = id_{D(i)}

‘d_{i} ∘ p_{i} ≤ id_{P} ’:

p_{j} ∘ d_{i} ∘ p_{i} = ⋁ {D(a) | a ∈ [i → j]} ∘ p_{i}
= ⋁ {D(a) ∘ p_{i} | a ∈ [i → j]}
≤ p_{j}

Da diese Ungleichung für jedes Objekt j von I gilt, ist d_{i} ∘ p_{i} ≤ id_{P}

Wir formulieren einen Spezialfall des zweiten Teiles der letzten Proposition:

Folgerung 3.4 Sei D : I → P OSET ein einfaches Diagramm, so daß

• Jedes Objekt von D hat ein kleinstes Element.

• Jeder verbindende Morphismus von D erhält das kleinste Element.

Dann sind Hyperlimesprojektionen über D obere Adjungierte. Ist (P, p) ein Hyperlimeskegel über D, so ist die untere Adjungierte d_{i} zu p_{i} gegeben durch

p_{j} ∘ d_{i} = \{ \begin{matrix}⊥ & falls [i → j] = ∅ \\ D(j ← i) & falls [i → j] ≠ ∅ \end{matrix}

Hyperlimesprojektionen über D sind surjektiv. Eine Hyperlimesprojektion und ihre untere Adjungierte bildet also ein Projektions-Einbettungspaar.

Beweis: Wir weisen nach, daß die Bedingungen aus Proposition 3.8 b) erfüllt sind. Seien i, j Objekte von I. Da D einfach ist, ist [i → j] entweder einelementig oder leer. Im ersten Fall ist {D(a) | a ∈ [i → j]} einelementig, und das punktweise Supremum existiert trivialerweise. Im zweiten Fall ist {D(a) | a ∈ [i → j]} leer, und das punktweise Supremum ist die konstante Abbildung auf das kleinste Element. Seien i, j, k Objekte von I und b ein Element von [j → k]. Falls [i → j] einelementig ist, so ist die zweite Bedingung aus Proposition 3.8 trivialerweise erfüllt. Falls [i → j] leer ist, so ist sie erfüllt, weil D(b) das kleinste Element erhält. Zur Surjektivität der Hypelimesprojektonen: Sei i ein Objekt von I und x ein Element von D(i). Dann ist p_{i} ∘ d_{i}(x) = D(i ← i)(x) = id(x) = x.

Wir haben im ersten Teil von Proposition 3.8 eine Bedingung an ein Diagramm von beschränkt vollständigen geordneten Mengen gestellt, unter der Hyperlimesprojektionen über dem Diagramm obere Adjungierte sind. Ohne diese Bedingung kommen wir nicht aus. Jedoch können wir das Diagramm ‘einschränken’ auf ein Diagramm, dessen Objekte Anfangsstücke der Objekte des ursprünglichen Diagrammes sind. Dieses Diagramm erfüllt dann die Bedingung aus Proposition 3.8.

Proposition 3.9

a) Seien P, Q beschränkt vollständige geordnete Mengen und sei p eine Abbildung von P nach Q, die nichtleere Infima erhält. Bezeichne A die Menge {x ∈ Q | p^{−1}(↑ x) ≠ ∅}. Dann ist A ein Anfangsstück von Q, enthält das Bild von p, und die Korestriktion von p auf A ist eine obere Adjungierte. Sind P und Q Bereiche und ist p stetig, so ist A abgeschlossen gegen gerichtete Suprema.

b) Sei D : I → BC ein Diagramm und (P, p) ein Hyperlimeskegel über D.

Für ein Objekt i von I sei A_{i} = {x ∈ D(i) | p_{i}^{−1}(↑ x) ≠ ∅}. Für jeden Pfeil a : i → j von I ist dann D(a)(A_{i}) ⊆ A_{j}.

c) D̃ : I → BC sei definiert durch:

\begin{matrix}D̃(i) = A_{i} & für i ∈ Ob(I) \\ D̃(a) = ′D(a)′ & für a ∈ Mor(I) \end{matrix}

Dann ist (P,′p) ein Hyperlimeskegel über D̃.

Beweis:

a) ‘A ist ein Anfangsstück’:

Seien x aus A und y aus Q, so daß y ≤ x. Nach Definition von A ist p^{−1}(↑ x) nichtleer. Da p^{−1}(↑ x) eine Teilmenge von p^{−1}(↑ y) ist, ist dann auch p^{−1}(↑ y) nichtleer. Also ist y in A. ‘im(p) ⊆ A’: Wenn x im Bild von p enthalten ist, ist offensichtlich p^{−1}(↑ x) nichtleer. ‘′p ist eine obere Adjungierte’: Sei x aus A. Nach Definition von A gibt es ein y in P, so daß p(y) ≥ x. Dann ist ′p^{−1}(↑ x) nichtleer. Da P beschränkt vollständig ist, existiert dann das Infimum von ′p^{−1}(↑ x). Da ′p Infima erhält ist es ein Element von ′p^{−1}(↑ x). ‘Ist p stetig, so ist A abgeschlossen gegen gerichtete Suprema’: Sei d die untere Adjungierte der Korestriktion von p auf A. Sei M eine gerichtete Teilmenge von A. Es ist

p(⋁ ^{↑}d(M)) = ⋁ ^{↑}p ∘ d(M) = ⋁ ^{↑}′p ∘ d(M) ≥ ⋁ ^{↑}M

Also ist p^{−1}(↑ ⋁ ^{↑}M) nichtleer. b) Sei x aus A_{i}. Das heißt, es gibt ein y in P, so daß p_{i}(y) ≥ x.

Dann ist D(a)(x) ≤ D(a) ∘ p_{i}(y) ≤ p_{j}(y). Also ist p_{i}^{−1}(↑ D(a)(x)) nichtleer.

c)

Q

[figure: q_{i}; q_{j}]

P \begin{matrix}∃!f \\ ∨ \end{matrix}

[figure: p_{i}; ′p_{j}; p_{j}]

A_{i}  \overline{′D(a)′  >} A_{j}

D(i)^{∨ ∩}  \overline{_{D(a)  >}} D(j)^{∨ ∩}

Daß (P,′p) ein schwacher Kegel ist, kann man nicht am Diagramm sehen, folgt aber daraus, daß die Ordnung auf den Morphismenmengen punktweise gegeben ist. Sei (Q, q) ein schwacher Kegel über D̃. Dann ist (Q, incl ˙∘q) ein schwacher Kegel über D, denn D(a)∘incl∘q_{i} = incl∘′D(a)′∘q_{i} ≤ incl∘q_{i}. Also gibt es genau einen Pfeil f von Q nach P, so daß p˙∘f = incl ˙∘q. Da p = incl ˙∘′p und da incl injektiv ist, ist dann ′p˙∘f = q. Sei g ein weiterer Pfeil von P nach Q, so daß ′p˙∘g = q. Dann ist p˙∘g = incl ˙∘′p˙∘g = incl ˙∘q. Weil f der einzige Pfeil ist, für den p˙∘f gleich incl ˙∘q ist, ist f = g.

Wir bemerken, daß Anfangsstücke von beschränkt vollständigen geordneten Mengen beschränkt vollständig sind. Anfangstücke von flachen Bereichen sind flache Bereiche. Ein Anfangsstück A eines Bereiches B, welches abgeschlossen ist gegen gerichtete Suprema, ist ein Bereich. Ist B stetig (algebraisch, dI), so ist auch A stetig (algebraisch,dI).

4 Die Kategorie der Hyperlimites flacher Bereiche

Definition 4.1 HF bezeichne die volle Unterkategorie von DCP O, deren Objekte Hyperlimites flacher Bereiche sind. OHF bezeichne die volle Unterkategorie von DCP O, deren Objekte Hyperlimesobjekte über zykelfreien Diagrammen von flachen Bereichen sind. (’O’ für ’ordered’.)

In der Einleitung und in Beispiel e) im zweiten Kapitel haben wir erläutert, wie man Hyperlimites flacher Bereiche zum Modellieren von Datenbanken benutzen kann. In diesem Kapitel werden wir sehen, daß die Kategorien HF und OHF auch Eigenschaften haben, die sie brauchbar machen zur Konstruktion von Lambda-Kalkül-Modellen. So sind beide Kategorien kartesisch abgeschlossen, und die Kategorie HF hat Objekte, die isomorph sind zum Bereich ihrer stetigen Selbstabbildungen. Zunächst jedoch werden wir als Folgerung der Ergebnisse aus dem letzten Kapitel die Hyperlimites flacher Bereiche intern charakterisieren:

Proposition 4.1

a) Ein Bereich B ist ein HF -Objekt, genau dann wenn es eine Teilmenge M der Menge Q_{B} aller Projektionen von B gibt, welche Bedingungen (i) bis (iii) aus Propsition 3.4 erfüllt, so daß jedes Bild eines Elementes von M ein flacher Bereich ist.

b) Ein Bereich B ist ein OHF -Objekt, genau dann wenn es eine Teilmenge M der Menge Q_{B} aller Projektionen von B gibt, welche Bedingungen (i) bis (iii) aus Proposition 3.4 erfüllt, und deren ∗-Präordnung antisymetrisch ist, so daß jedes Bild eines Elementes von M ein flacher Bereich ist.

Beweis:

a) ‘wenn’: folgt direkt aus Proposition 3.4 b).

‘nur dann wenn’: Ist B Hyperlimesobjekt über einem Diagramm von flachen Bereichen, so gibt es, nach Proposition 3.9 ein Diagramm D, dessen Objekte Anfangsstücke von flachen Bereichen sind, so daß B Hyperlimesobjekt über D ist, und Hyperlimesprojektionen über D obere Adjungierte sind. Als Anfangsstück eines flachen Bereiches, ist jedes Objekt von D ein flacher Bereich. Nach Proposition 3.4 a) gibt es eine Teilmenge M von Q_{B}, die Bedingungen (i) bis (iii) erfüllt. Das Bild jedes beliebigen Elementes von M ist isomorph zum Bild eines Abschlußoperators eines Objektes von D. Der einzige Abschlußoperator eines flachen Bereiches ist aber die Identität.

b) ‘wenn’: Nach Proposition 3.4 b) ist B Hyperlimesobjekt über D_{M}. Das Bild jedes Elementes von M ist nach Voraussetzung ein flacher Bereich, hat also ein kleinstes Element. Man überlegt sich leicht, daß dieses auch das kleinste Element von B sein muß. B hat also ein kleinstes Element, ist also insbesondere ordnungszusammenhängend. Nach Proposition 3.7 ist B dann Hyperlimesobjekt über D_{|≤∗}. Die ∗-Präordnung ist nach Voraussetzung antisymmetrisch. Als Kategorie aufgefaßt, ist ≤^{∗} also zykelfrei. ‘nur dann wenn’: Ist B Hyperlimesobjekt über einem zykelfreien Diagramm, so ist auch das Diagramm D aus dem Beweis von Teil a) zykelfrei. Nach Propsition 3.6 ist dann die ∗-Präord-nung auf der Menge M aus dem Beweis von Teil a) antisymetrisch.

Wir wollen nun zeigen, daß die Kategorien HF und OHF kartesisch abgeschlossen sind. Dazu benutzen wir, daß wir nach Beispiel d) aus dem zweiten Kapitel den Bereich der stetigen Abbildungen zwischen zwei algebraischen Bereichen auffassen können als Hyperlimes eines Diagrammes, dessen sämtliche Objekte Kopien des Definitionsbereiches sind. Wir stoßen dann auf die Frage, ob ein Hyperlimes von Hyperlimites flacher Bereiche wieder ein Hyperlimes flacher Bereiche ist. Oder etwas allgemeiner formuliert:

Gegeben sei eine Familie (E_{k})_{k∈K} von Diagrammen, und ein Diagramm D, dessen Objekte gerade die Hyperlimesobjekte über den Diagrammen E_{k} sind. Gibt es dann ein Diagramm F, dessen Objekte gerade die Elemente von {E_{k}(i) | k ∈ K, i ∈ ObI_{k}} sind, so daß hypD ≃ hypF ?

Definition 4.2 Sei K eine kleine Kategorie und (I_{k})_{k∈ObK} eine Familie von kleinen Katgorien. Wir wollen daraus eine neue Kategorie ⨄_{K} I_{k} konstruieren:

Objektmenge: ⨄_{k∈ObK} Ob(I_{k})

Pfeilmengen: Falls i, j ∈ Ob(I_{k}):

[i → j]_{⊎I_{k}} := [i → j]_{I_{k}} ⊎ ([k → k]_{K} \ {id_{k}})
Falls i ∈ Ob(I_{h}), j ∈ Ob(I_{k}) und h ≠ k:
[i → j]_{⊎I_{k}} := [h → k]_{K}

Ist a ein K-Pfeil von h nach k, so gibt es in ⨄_{K} I_{k} mehrere Pfeile, die mit a bezeichnet werden, nämlich für jedes Paar (i, j) aus Ob(I_{h}) × Ob(I_{k}) einen. Wir kennzeichnen deshalb mit einem Index die Quelle und das Ziel von a.

Verknüpfung:

(i) Falls i, j, l ∈ Ob(I_{h}), a ∈ [i → j], b ∈ [j → l]:

b ∘ a := b ∘_{I_{h}} a

(ii) Falls i ∈ Ob(I_{h}), j ∈ Ob(I_{k}), l ∈ Ob(I_{r}), a ∈ [h → k]_{K}, b ∈ [k → r]_{K}:

b_{[j→l]} ∘ a_{[i→j]} := (b ∘_{K} a)_{[i→l]}

(iii) Falls i, j ∈ Ob(I_{h}), l ∈ Ob(I_{k}), a ∈ [i → j]_{I_{h}}, b ∈ [h → k]_{K}:

b_{[j→l]} ∘ a := b_{[i→l]}

(iv) Falls i ∈ ObI_{h}, j, l ∈ ObI_{k}, a ∈ [h → k]_{K}, b ∈ [j → l]_{I_{k}}:

b ∘ a_{[i→j]} := a_{[i→l]}

Beispiel: K = 1 ⟶ 2, I_{1} = I_{2} = a ⟶ b

a  \overline{\overline{>}} a

[figure]

b ∨  \overline{\overline{>}} b ∨

Man prüft leicht nach, daß die Verknüpfungsoperation von ⨄_{K} I_{k} assoziativ ist, und daß für ein Objekt i von I_{k} die Identität auf i in I_{k} auch Identität in ⨄_{K} I_{k} ist. ⨄_{K} I_{k} ist also eine Kategorie. Falls K zykelfrei ist, und sämtliche I_{k} zykelfrei sind, so ist auch ⨄_{K} I_{k} zykelfrei.

4 DIE KATEGORIE DER HYPERLIMITES FLACHER BEREICHE 29

Proposition 4.2 Sei K eine kleine Kategorie, (E_{k} : I_{k} → P OSET)_{k∈ObK} eine Familie von schwachen Diagrammen und D : K → P OSET ein schwaches Diagramm, so daß es für alle Objekte k von K einen Hyperlimeskegel (D(k), p_{k}) über E_{k} gibt. Jedes Diagramm E_{k} erfülle die folgenden Bedingungen:

• Für jedes Objekt i von I_{k} hat p_{k,i} eine untere Adjungierte d_{k,i}.

• Für jeden Pfeil a : i → j von I_{k} sei d_{k,j} ∘ E_{k}(a) ≤ d_{k,i}.

Das Diagramm ⨄_{D} E_{k} : ⨄_{K} I_{k} → P OSET sei gegeben durch: Für i ∈ ObI_{h}: (⨄_{D} E_{k})(i) := E_{h}(i) Für a ∈ Mor(I_{h}): (⨄_{D} E_{k})(a) := E_{h}(a) Für i ∈ Ob(I_{h}), j ∈ Ob(I_{r}), a ∈ [h → r]_{K}: (⨄_{D} E_{k})(a_{[i→j]}) := p_{r,j} ∘ D(a) ∘ d_{h,i}

Behauptung: ⨄_{D} E_{k} ist ein schwaches Diagramm.

Zusätzlich soll nun gelten:

• Verbindende Morphismen von D erhalten Suprema.

• Für jedes k ∈ Ob(K) erhalten verbindende Morphismen von E_{k} Suprema. Sei (P, π) ein Hyperlimeskegel über D. Behauptung: (P, (p_{k,i} ∘ π_{k})_{k∈ObK,i∈ObI_{k}}) ist ein Hyperlimeskegel über ⨄_{D} E_{k}. Beweis: ‘⨄_{D} E_{k} ist ein schwaches Diagramm’: Seien a, b wie in Definition 4.2 (i) bis (iv).

(i)

h
i
j {E_{h}(a) \atop ∨}
l {E_{h}(b) \atop ∨}
(⨄_{D}E_{k})(b) ∘ (⨄_{D}E_{k})(a) = E_{h}(b) ∘ E_{h}(a)
≤ E_{h}(b ∘ a)
= (⨄_{D}E_{k})(b ∘ a)

(ii)

\begin{matrix}h & & k & & r \\ i & \overline{_{p_{k,j} ∘ D(a) ∘ d_{h,i} >}} & j & \overline{_{p_{r,l} ∘ D(b) ∘ d_{k,j}>}} & l \end{matrix}

(⨄_{D}E_{k})(b_{[j→k]}) ∘ (⨄_{D}E_{k})(a_{[i→j]}) = p_{r,l} ∘ D(b) ∘ d_{k,j} ∘ p_{k,j} ∘ D(a) ∘ d_{h,i}
≤ p_{r,l} ∘ D(b) ∘ D(a) ∘ d_{h,i}
≤ p_{r,l} ∘ D(b ∘ a) ∘ d_{h,i}
= (⨄_{D}E_{k})((b ∘ a)_{[i→l]})
= (⨄_{D}E_{k})(b_{[j→l]} ∘ a_{[i→j]})

(iii)

h  k

i

j {E_{h}(a) \atop ∨} \overline{_{p_{k,l} ∘ D(b) ∘ d_{h,j}>}} l
(⨄_{D}E_{k})(b_{[j→l]}) ∘ (⨄_{D}E_{k})(a) = p_{k,l} ∘ D(b) ∘ d_{h,j} ∘ E_{h}(a)
≤ p_{k,l} ∘ D(b) ∘ d_{h,i}
= (⨄_{D}E_{k})(b_{[i→l]})
= (⨄_{D}E_{k})(b_{[j→l]} ∘ a)

(iv)

h  k
i p_{k,j} ∘ D(a) ∘ d_{h,i} > j
l^{∨E_{k}(b)}
(⨄_{D}E_{k})(b) ∘ (⨄_{D}E_{k})(a_{[i→j]}) = E_{k}(b) ∘ p_{k,j} ∘ D(a) ∘ d_{h,i}
≤ p_{k,l} ∘ D(a) ∘ d_{h,i}

= (⨄_{D}E_{k})(a_{[i→l]})
= (⨄_{D}E_{k})(b ∘ a_{[i→j]})

‘(P, (p_{h,i} ∘ π_{h})_{h∈ObK,i∈ObI_{h}}) ist Hyperlimeskegel über (⨄_{D}E_{k})’:

Sei (Q, q) ein schwacher Kegel über ⨄_{D}E_{k}.

Q

P \begin{matrix}∃!s \\ ∨ \end{matrix}

[figure: π_{h}; π_{k}]

D(h)  \overline{_{D(f)  >}} D(k)

E_{h}(i)  \overline{_{E_{h}(a)  >}} E_{h}(l)  E_{k}(j)  \overline{_{E_{k}(b)  >}} E_{k}(m)

Dann ist (Q, q_{h}) ein schwacher Kegel über E_{h} für alle Objekte h von K. Also: ∃!r_{h} : Q → D(h). p_{h} ˙∘Δr_{h} = q_{h} (∗) Sei f : h → k ∈ MorK. Dann ist für alle j ∈ ObI_{k}

p_{k,j} ∘ D(f) ∘ r_{h} = p_{k,j} ∘ D(f) ∘ id ∘ r_{h}
= p_{k,j} ∘ D(f) ∘ ( ⋁_{i∈ObI_{h}} d_{h,i} ∘ p_{h,i}) ∘ r_{h}
= p_{k,j} ∘ D(f) ∘ ⋁(d_{h,i} ∘ p_{h,i} ∘ r_{h})
= p_{k,j} ∘ ⋁_{i∈ObI_{h}} D(f) ∘ d_{h,i} ∘ p_{h,i} ∘ r_{h}
= ⋁_{i∈ObI_{h}} p_{k,j} ∘ D(f) ∘ d_{h,i} ∘ p_{h,i} ∘ r_{h}
= ⋁_{i∈ObI_{h}}(⨄_{D}E_{k}) (f_{[i→j]}) ∘ q_{h,i}
≤ q_{k,i}

Die vierte Gleichung der Gleichungskette gilt, weil D(f) nach Voraussetzung Suprema erhält. Die fünfte Gleichung gilt, weil mit den verbindenden Morphismen von E_{k} auch die Hyperlimesprojektionen über E_{k} Suprema erhalten, nach Proposition 2.5. Da die eben hergeleitete Ungleichung für alle k aus Ob(K) gilt, ist D(f) ∘ r_{h} ≤ r_{k}. (Q, r) ist also ein schwacher Kegel über D. Also: ∃!s : Q → P . π ˙∘Δs = r (∗∗) Dann ist aber für alle h ∈ ObK und alle i ∈ ObI_{h}

p_{h,i} ∘ π_{h} ∘ s =^{∗∗} p_{h,i} ∘ r_{h} =^{∗} q_{h,i}

Sei t : Q → P ein Pfeil, so daß p_{h,i} ∘ π_{h} ∘ t = q_{h,i} für alle h ∈ ObK und alle i ∈ ObI_{h}.
Wegen (∗) ist dann π_{h} ∘ t = r_{h} für alle h ∈ ObK. Wegen (∗∗) ist dann t = s.

Satz 4.1 Die Kategorien HF und OHF sind kartesich abgeschlossene Unterkategorien von DCP O.

Beweis: Der einelementige Bereich ist ein flacher Bereich, also ein OHF -Objekt. Sind A, B HF -Objekte (OHF -Objekte), dann sicher auch A × B. Bleibt zu zeigen, daß für HF -Objekte (OHF -Objekte) A, B auch [A → B] ein HF -Objekt (OHF - Objekt) ist: Seien also D : I → DCP O und E : J → DCP O schwache Diagramme von flachen Bereichen, (A, p) ein Hyperlimeskegel über D und (B, q) ein Hyperlimeskegel über E. Im nächsten Abschnitt werden wir sehen, daß A als Hyperlimes von beschränkt vollständigen, algebraischen Bereichen algebraisch ist. Nach Beispiel d) aus Kapitel 2 ist dann ([A → B], (ev_{k})_{k∈K(A)}) ein Hyperlimeskegel über F : K(A) → DCP O, wobei

\begin{matrix}F (k) = B & für alle k ∈ K(A) \\ F (k ← h) = id_{B} & für alle (h, k) ∈≤_{K(A)} \end{matrix}

Wegen Proposition 3.9 und weil Anfangsstücke von flachen Bereichen flache Bereiche sind, können wir annehmen, daß Hyperlimesprojektionen über E obere Adjungierte sind. Nach Proposition 3.2 ist dann (B,′q) ein Hyperlimeskegel über der Restriktion des Diagrammes Ẽ aus Proposition 3.1 auf |J|. Die Objekte von Ẽ_{||J|} sind Bilder von Abschlußoperatoren auf flachen Bereichen, sind also flache Bereiche. Wegen Proposition 3.3 und Propsition 4.2 ist ⨄_{F} Ẽ_{||J|} ein schwaches Diagramm. Die verbindenden Morphismen von F sind Identitäten, erhalten also sicher Suprema. Die verbindenden Morphismen von Ẽ_{||J|} sind monotone Abbildungen mit flachem Definitionsberich und erhalten als solche Suprema. Nach 4.2 ist ([A → B], (′q_{j} ∘ ev_{k})_{k∈K(A),j∈ObJ}) dann ein Hyperlimeskegel über ⨄_{F} Ẽ_{||J|}. Die Objekte von ⨄_{F} Ẽ_{||J|} sind die gleichen wie die Objekte von Ẽ_{||J|}, sind also flache Bereiche. Da F zykelfrei ist, ist ⨄_{F} Ẽ_{||J|} zykelfrei, falls J zykelfrei ist.

Satz 4.2 In der Kategorie HF gibt es Objekte A, für die A ≃ [A → A].

Beweis: Wir beschreiben zunächst eine Konstruktion, welche in der Kategorie DCP O ein Objekt liefert, welches isomorph ist zum Bereich seiner stetigen Selbstabbildungen: Sei A ein Bereich und h : [A → A] → A eine stetige obere Adjungierte. DCP O^{gd} sei die Unterkategorie von DCP O, deren Objekte die gleichen wie die von DCP O und deren Morphismen die stetigen oberen Adjungierten sind. Der Endofunktor F auf DCP O^{gd} sei gegeben durch

\begin{matrix}F (A) = [A → A] & für Objekte A \\ F (g)(f) = g ∘ f ∘ d & für Morphismen g : A → B \end{matrix}

wobei d die untere Adjungierte zu g bezeichnet.

\begin{matrix}[A & \overline{f >} & A] \\ [B & ^{d∧} & \overline{\overline{>}} & B] & ^{∨g} \end{matrix}

Das Diagramm D_{A,h} : N^{op} → DCP O^{gd} sei gegeben durch

\begin{matrix}D_{A,h}(0) = A & D_{A,h}(0 ← 1) = h \\ D_{A,h}(n) = F^{n}A & D_{A,h}(n ← n + 1) = F^{n}h \end{matrix}

A < \underline{h} F A < \underline{F h} F^{2}A <\underline{F^{2}h} ...

Dann ist das Limesobjekt limD_{A,h} isomorph zu [limD_{A,h} → limD_{A,h}]. (Für vollständige Verbände folgt das aus Satz 3.19 in [COMP]. Da im Beweis dieses Satzes nur Eigenschaften von Adjunktionen und die Stetigkeit der oberen Adjungierten verwendet werden, läßt sich der Satz auf Bereiche verallgemeinern.) Sei nun A ein beliebiges HF -Objekt. Wir definieren h : [A → A] → A durch

h(f) = f(⊥)

und e : A → [A → A] durch

e(x) = const_{x}

Wir zeigen, daß (h, e) ein Projektions-Einbettungspaar ist: Für f aus [A → A] und x aus A ist

(e ∘ h(f))(x) = e(f(⊥))(x) = const_{f(⊥)}(x) = f(⊥) ≤ f(x)

Also ist e ∘ h ≤ id_{[A→A]}. Für x aus A ist

h ∘ e(x) = h(const_{x}) = const_{x}(⊥) = x

Also h ∘ e = id_{A}. A ist Hyperlimes von flachen Bereichen, also beschränkt vollständig. Suprema in [A → A] werden also punktweise gebildet. Dann erhält h aber Suprema.

Erhält g : A → B Suprema, und sind A, B beschränkt vollständig, so erhält auch F (g) : [A → A] → [B → B] Suprema, denn

F (g)(⋁ M) = g ∘ ⋁ M ∘ d = ⋁ g ∘ M ∘ d = ⋁ F (g)(M)

Sämtliche verbindende Morphismen von D_{A,h} erhalten also Suprema. Wir zeigen nun, daß ein Limesobjekt über D_{A,h} ein HF -Objekt ist: Nach Satz 4.1 sind die Objekte von D_{A,h} HF -Objekte. Es gibt also eine Familie (E_{n})_{n∈N} von Diagrammen von flachen Bereichen, so daß D_{A,h}(n) Hyperlimesobjekt über E_{n} ist für jede natürliche Zahl n. Nach Proposition 3.9 können wir annehmen, daß Projektionen über E_{n} obere Adjungierte sind. Bezeichne D̃_{A,h} das Diagramm aus Proposition 2.4. Nach besagter Proposition ist ein Limesobjekt limD_{A,h} über D_{A,h} Hyperlimesobjekt über D̃_{A,h}. Jeder verbindende Morphismus von D̃_{A,h} entsteht durch Komposition von verbindenden Morphismen von D_{A,h} und unteren Adjungierten von verbindenden von D_{A,h}. Untere Adjungierte erhalten Suprema, und die verbindenden Morphismen von D_{A,h} erhalten nach Konstruktion von D_{A,h} Suprema. Also erhalten sämtliche verbindenden Morphismen von D̃_{A,h} Suprema. Für jedes n ∈ N sind die verbindenden Morphismen von E_{n} monotone Abildungen mit flachem Definitionsbereich, erhalten also Suprema. Nach Proposition 4.2 ist dann limD_{A,h} Hyperlimesobjekt über ⨄D̃_{A,h}E_{n}.

Eine weitere Abgeschlossenheitseigenschaft der Kategorien HF und OHF:

Proposition 4.3 Ist (A_{k})_{k∈K} eine Familie von HF -Objekten (OHF -Objekten), so ist auch die disjunkte Summe ⨁_{k∈K} A_{k} ein HF -Objekt (OHF -Objekt).

Beweisidee: Sei (D_{k} : I_{k} → DCP O)_{k∈K} eine Familie von Diagrammen, und für jedes k aus K sei (A_{k}, p_{k}) ein Hyperlimeskegel über D_{k}. Die Kategorie ⨁_{K} I_{k} entstehe aus den Kategorien I_{k} durch disjunkte Vereingung von Objektmengen und Pfeilmengen und Hinzufügen eines finalen Objektes ⊤. Das schwache Diagramm ⨁_{K} D_{k} : ⨁_{K} I_{k} → DCP O sei definiert durch

Falls i ∈ ObI_{h}:  (⨁_{K} D_{k})(i) := D_{h}(i)

Falls i = ⊤:  (⨁_{K} D_{k})(⊤) := K_{⊥}

Falls a : i → j ∈ Mor(I_{h}):  (⨁_{K} D_{k})(a) := D_{h}(a)

Falls a : i → ⊤ und i ∈ Ob(I_{h}):  (⨁_{K} D_{k})(a)(x) := \{ \begin{matrix}⊥ & falls x = ⊥ \\ h & falls x ≠ ⊥ \end{matrix}

Die schwach natürliche Transformation q : Δ(⨁_{k∈K} A_{k}) → ⨁_{K} D_{k} sei gegeben durch

Für x ∈ A_{h}:  q_{i}(x) := \{ \begin{matrix}p_{h,i}(x) & falls i ∈ Ob(I_{h}) \\ h & falls i = ⊤ \\ ⊥ & sonst \end{matrix}

4 DIE KATEGORIE DER HYPERLIMITES FLACHER BEREICHE 35

Für x = ⊥:  q_{i}(⊥) := ⊥ für alle i ∈ Ob(⨁_{K} I_{k})

Dann ist (⨁_{k∈K} A_{k}, q) ein Hyperlimeskegel über ⨁_{K} D_{k}. Falls sämtliche I_{k} zykelfrei sind, so ist auch ⨁_{K} I_{k} zykelfrei.

5 Eigenschaften des Hyperlimesobjektes bei gegebenem Diagramm und Eigenschaften des Diagrammes bei gegebenem Hyperlimesobjekt

5.1 Eigenschaften des Hyperlimesobjektes bei bekanntem Diagramm

Im folgenden bezeichne der Buchstabe D immer ein schwaches Diagramm. Sprechen wir vom Hyperlimes über einem Diagramm in einer Unterkategorie von DCP O ( bzw. P OSET), so meinen wir immer den Hyperlimes in DCP O ( bzw. P OSET).

Satz 5.1

a) Sei D : I → BC ∧ CONT. Dann ist das Hyperlimesobjekt über D stetig.

b) Sei D : I → BC ∧ ALG. Dann ist das Hyperlimesobjekt über D algebraisch.

Beweis:

a) Nach Proposition 3.9 gibt es ein Diagramm D̃, so daß jede Hyperlimesprojektion über D̃ eine untere Adjungierte hat, und D und D̃ die gleichen Hyperlimesobjekte haben. Für jedes Objekt i von I ist D̃(i) ein Anfangsstück von D(i) welches abgeschlossen ist gegen gerichtete Suprema. Als solches ist D̃(i) sicher stetig. Sei nun (A, p) ein Hyperlimeskegel über D̃. Für jedes Objekt i von I bezeichne d_{i} die untere Adjungierte zu p_{i}. Sei x aus A. Dann ist

x = ⋁_{i∈ObI} d_{i} ∘ p_{i}(x)  (1)
= ⋁_{i∈ObI} d_{i}(⋁ ^{↑}↓↓p_{i}(x))  (2)
= ⋁_{i∈ObI} ⋁ ^{↑}d_{i}(↓↓p_{i}(x))  (3)
= ⋁ ^{↑}{⋁ E | E ⊆ ⋃_{i∈ObI} d_{i}(↓↓p_{i}(x)), E endlich}  (4)

(2) gilt, weil D̃(i) stetig ist, (3) weil eine untere Adjungierte Suprema erhält. Für jedes Objekt i von I ist d_{i}(↓↓p_{i}(x)) eine Teilmenge von ↓↓d_{i} ∘p_{i}(x), da d_{i} untere Adjungierte einer stetigen Funktion ist. Weil d_{i}∘p_{i} kleiner ist als die Identität, ist ↓↓d_{i}∘p_{i}(x) eine Teilmenge von ↓↓x. Da endliche Suprema von Elementen weit unter x wieder weit unter x liegen, ist dann die Menge aus dem letzten Term der obigen Gleichungskette eine Teilmenge von ↓↓x. Also ist x gerichtetes Supremum von weit darunter liegenden Elementen, was zu zeigen war.

b) Wie in a) können wir annehmen, daß jede Hyperlimesprojektion über D eine untere Adjungierte hat. Sei nun (A, p) ein Hyperlimeskegel über D, für jedes Objekt i von I sei d_{i} die untere Adjungierte zu p_{i}, und sei x ein Element von A.

Dann ist

x = ⋁_{i∈ObI} d_{i} ∘ p_{i}(x)
= ⋁_{i∈ObI} d_{i}(⋁ ^{↑}K_{p_{i}(x)})
= ⋁_{i∈ObI} ⋁ ^{↑}d_{i}(K_{p_{i}(x)})
= ⋁ ^{↑}{⋁ E | E ⊆ ⋃_{i∈ObI} d_{i}(K_{p_{i}(x)}), E endlich}

Weil d_{i} die untere Adjungierte einer stetigen Funktion ist, ist d_{i}(K_{p_{i}(x)}) Teilmenge von K_{d_{i}∘p_{i}(x)}. Weil p_{i} ∘ d_{i} kleiner ist als die Identität, ist K_{d_{i}∘p_{i}(x)} eine Teilmenge von K_{x}. Da endliche Suprema von kompakten Elementen kompakt sind, ist die Menge in der letzten Zeile der obigen Gleichungskette eine Teilmenge von K_{x}. Also ist x gerichtetes Supremum von kompakten Elementen.

Ein Hyperlimesobjekt über einem Diagramm von dI-Bereichen muß kein dI-Bereich sein, selbst dann nicht wenn das Diagramm zykelfrei und einfach ist:

hypD_{1},hypD_{2} und hypD_{3} sind nicht endlich algebraisch. hypD_{4} enthält einen zu N_{3} isomorphen Unterverband, ist also nicht distributiv. Wir werden Bedingungen an einfache Diagramme von dI-Bereichen stellen, unter denen Hyperlimesobjekte darüber wieder dI-Bereiche sind.

Proposition 5.1 Sei D : I → DIST, so daß verbindende Morphismen von D endliche Suprema erhalten. Dann ist das Hyperlimesobjekt über D distributiv.

Beweis: Nach Proposition 2.5 erhalten Hyperlimesprojektionen über D Infima und endliche Suprema. Ein Hyperlimesobjekt über D ist also isomorph zu einer Teilmenge des Produktes der Diagrammobjekte, welche abgeschlossen ist gegen Infima und endliche Suprema, ist also distributiv.

Lemma 5.1 Sei D : I → BC ∧ ALG, so daß jede Hyperlimesprojektion über D eine untere Adjungierte hat. Sei (A, p) ein Hyperlimeskegel über D. Für jedes i ∈ Ob(I) bezeichne d_{i} die untere Adjungierte zu p_{i}. Sei k ein Element von A. Dann sind äquivalent:

(1) k ist kompakt.

(2) ∃E^{endl} ⊆ ObI. ∀i ∈ E. ∃k_{i} ∈ K(D(i)). k = ⋁_{i∈E} d_{i}(k_{i})

Beweis:

‘(2) ⇒ (1)’: Eine untere Adjungierte einer stetigen Funktion bildet kompakte Elemente ab auf kompakte Elemente. Endliche Suprema von kompakten Elementen sind kompakt.

‘(1) ⇒ (2)’: Sei k kompakt. Dann ist

k = ⋁_{i∈ObI} d_{i} ∘ p_{i}(k)
= ⋁_{i∈ObI} d_{i}(⋁ ^{↑}K_{p_{i}(k)})
= ⋁_{i∈ObI} ⋁ ^{↑}d_{i}(K_{p_{i}(k)})
= ⋁ ⋃_{i∈ObI} d_{i}(K_{p_{i}(k)})

Da k kompakt ist, gibt es eine endliche Teilmenge F von ⋃_{i∈ObI} d_{i}(K_{p_{i}(k)}) so daß ⋁ F = k. Da d_{i}(k_{1} ∨k_{2}) ein Element von d_{i}(K_{p_{i}(k)}) ist, falls k_{1} und k_{2} Elemente von K_{p_{i}(k)} sind, können

wir annehmen, daß F ∩ d_{i}(K_{p_{i}(k)}) höchstens ein Element hat für jedes i ∈ Ob(I).

Satz 5.2 Sei D : I → dI einfach. Weiterhin erfülle D die folgenden Bedingungen:

(i) Jeder verbindende Morphismus von D erhält endliche Suprema.

(ii) Jeder verbindende Morphismus von D bildet kompakte Elemente auf kompakte Elemente ab.

(iii) Für alle Objekte i von I und alle kompakten Elemente k von D(i) ist {j ∈ ObI | D(j ← i)(k) ≠ ⊥} endlich.

Dann ist das Hyperlimesobjekt über D auch ein dI-Bereich.

Beweis: Sei (A, p) ein Hyperlimeskegel über D. Nach Satz 5.1 ist A algebraisch. Da verbindende Morphismen von D endliche Suprema erhalten, ist A distributiv, nach Proposition 5.1. Bleibt zu zeigen, daß jeder von kompakten Elementen erzeugte Hauptanfang endlich ist. Da D einfach ist und die verbindenden Morphismen von D das kleinste Element erhalten, gibt es nach Folgerung 3.4 zu jeder Projektion p_{i} eine untere Adjungierte e_{i} definiert durch

p_{j} ∘ e_{i} = \{ \begin{matrix}D(j ← i) & falls [i → j] ≠ ∅ \\ ⊥ & falls [i → j] = ∅ \end{matrix}

Sei zunächst i aus ObI und k aus K(D(i)). Bezeichne E die Menge {j ∈ ObI | p_{j} ∘ e_{i}(k) ≠ ⊥}. Nach Voraussetzung (iii) ist E endlich. Es ist

↓ e_{i}(k) ⊆ {(x_{i})_{i∈I} | ∀j ∈ ObI.x_{j} ≤ p_{j} ∘ e_{i}(k)}
≃ ∏_{j∈E} ↓ p_{j} ∘ e_{i}(k) × ∏_{j∈ObI\E}{⊥}

Weil D(j ← i) kompakte Elemente auf kompakte Elemente abbildet, ist p_{j} ∘e_{i}(k) kompakt für jedes j aus E. Da D(j) endlich algebraisch ist, ist ↓ p_{j} ∘ e_{i}(k) endlich. ↓ e_{i}(k) ist also endlich. Sei nun k aus K(A). Nach Proposition 5.1 ist k = ⋁_{i∈E} e_{i}(k_{i}), wobei E eine endliche Teilmenge von ObI ist und k_{i} ∈ K(D(i)). Da in einem distributiven, stetigen Bereich elementweise Suprema von Anfangsstücken wieder Anfangsstücke sind, ist ↓ k das elementweise Supremum von {↓ e_{i}(k_{i}) | i ∈ E}. Als elementweises Supremum von endlich vielen endlichen Mengen ist ↓ k endlich.

Wir werden später sehen, daß Bedingungen (i) bis (iii) auch notwendig dafür sind, daß ein Hyperlimesobjekt über einem zykelfreien, einfachen Diagramm von dI-Bereichen wieder ein dI-Bereich ist, falls wir zusätzlich voraussetzen, daß alle Hyperlimesprojektionen surjektiv sind.

Ein Hyperlimes von bifiniten Bereichen muß nicht bifinit sein, selbst dann nicht, wenn das Diagramm zykelfrei und einfach ist, sämtliche Diagrammobjekte ein kleinstes Element haben, und die verbindenden Morphismen das kleinste Element erhalten. Zum Beispiel:

Die Objekte dieses Diagrammes sind endlich, also sicherlich bifinit. Wie sieht man, daß der Hyperlimes dieses Diagrammes nicht bifinit ist? Bezeichne U den Operator, der einer Teilmenge A eines Bereiches B die Menge der minimalen oberen Schranken von endlichen Teilmengen von A zuordnet. Weiterhin bezeichne U^{∞}(A) die Menge ⋃_{n∈N} U^{n}(A). Nach Plotkins Charakterisierungssatz (siehe [J]) ist in einem bifiniten Bereich für jede endliche Menge A von kompakten Elementen auch U^{∞}(A) endlich. Bezeichne A die Teilmenge {(1, 1, ..), (1′, 1′, ..)} des kanonischen Hyperlimesobjektes über unserem Diagramm. Die Elemente dieser Menge sind kompakt, denn es ist (1, 1, ..) = e_{1}(1) und (1′, 1′, ..) = e_{1}(1′). Für eine natürliche Zahl n ist

U^{n}(A) = U^{n−1}(A) ∪ {(1, 2, .., n, n + 1, n + 1, ..), (1′, 2′, .., n′, (n + 1)′, (n + 1)′, ..)}

U^{∞}(A) = {(1, 2, .., n − 1, n, n, ..) | n ∈ N} ∪ {(1′, 2′, .., (n − 1)′, n′, n′, ..) | n ∈ N}

U^{∞}(A) ist also unendlich, und somit ist das kanonische Hyperlimesobjekt über D nicht bifinit.

Wir werden Bedingungen an Diagramme von bifiniten Bereichen stellen, unter denen der Hyperlimes eines solchen Diagrammes wieder bifinit sind. Zunächst die Verallgemeinerung eines ordnungstheoretischen Begriffes auf Präordnungen und ein vorbereitendes Lemma:

Definition 5.1 Sei (P, ≤) eine prägeordnete Menge. Für i aus U bezeichne ↑ i die Menge aller j aus U mit j ≥ i. Eine Teilmenge U von P heiße Endstück von P, falls ↑ i eine Teilmenge von U ist für alle i ∈ U. Für die Menge aller Endstücke von P schreiben wir E(P).

Wir bemerken, daß die Menge aller Endstücke einer prägeordneten Menge ein vollständiger Verband ist, in dem das Infimum der Mengenschnitt und das Supremum die Mengenvereinigung ist.

Proposition 5.2 Sei D : I → P OSET_{⊥} ein einfaches Diagramm, dessen verbindende Morphismen das kleinste Element erhalten. (P, p) bezeichne einen Hyperlimeskegel über D. Da I einfach ist können wir I als prägeordnete Menge auffassen. Für ein Endstück U von I sei p^{U} : P → P definiert durch

p_{i} ∘ p^{U} = \{ \begin{matrix}p_{i} & falls i ∈ U \\ ⊥ & sonst \end{matrix}

Dann ist p^{U} ∈ Q_{P}. Sei weiterhin B eine Sup-Basis von E(I), d.h. jedes Element von E(I) sei Supremum einer Teilmenge von B. Das Diagramm D̃ : B^{op} → P OSET sei definiert durch

\begin{matrix}D̃(U) = im(p^{U}) & für U ∈ B \\ D̃(U ← V) = ′(p^{U})′ & für U ⊆ V \end{matrix}

Dann ist (P, (′(p^{U}))_{U∈B}) ein Limeskegel über D̃.

Beweis: p^{U} ist wohldefiniert, da U ein Endstück ist.

p^{U} ist eine Projektion: Für alle i aus ObI ist p_{i} ∘ p^{U} ≤ p_{i}. Also ist p^{U} ≤ id.

p_{i} ∘ p^{U} ∘ p^{U} = \{ \begin{matrix}p_{i} ∘ p^{U} & falls i ∈ U \\ ⊥ ∘ p^{U} & sonst \end{matrix}
= \{ \begin{matrix}p_{i} & falls i ∈ U \\ ⊥ & sonst \end{matrix}
= p_{i} ∘ p^{U}

D̃ ist ein Diagramm: Seien U, V, W Endstücke von I, so daß U ⊆ V ⊆ W.

D(U ← V) ∘ D(V ← W) = ′p^{U}′ ∘′p^{V} ′ = ′p^{U}′

Das letzte Gleichheitszeichen steht, weil p^{U} ≤ p^{V}.

Sei nun (Q, (q_{U})_{U∈B}) ein Limeskegel über D̃. Wir zeigen, daß Q isomorph ist zu P mittels φ : P → Q gegeben durch

q_{U} ∘ φ = ′p^{U}

mit der Umkehrabbildung ψ : Q → P gegeben durch

p_{i} ∘ ψ = p′_{i} ∘ q_{U}, wo U ∈ B, so daß i ∈ U

‘φ wohldefinert’:

Seien U, V aus B, so daß U ⊆ V.

D(U ← V) ∘′(p^{V}) = ′(p^{U})′ ∘′(p^{V}) = ′(p^{U})

Das letzte Gleichheitszeichen steht wieder, weil p^{U} ≤ p^{V}.

‘ψ wohldfefiniert’:

Sei i aus ObI. B ist eine Sup-Basis von E(I), das Supremum in E(I) ist die Mengenvereinigung und ObI ist sicher ein Element von E(I). Es gibt also ein U in B, so daß i in U ist. Seien nun U und V Elemente von B, so daß i ∈ U ∩ V. Da U ∩ V ein Endstück von I und B ein Sup-Basis von E(I) ist, ist U ∩ V Vereinigung von Elementen von B. Es gibt also ein Element W von B, welches in U ∩ V enthalten ist, so daß i ∈ W. Es ist

p′_{i} ∘ q_{U} = p_{i} ∘ (p^{W})′ ∘ q_{U} = p′_{i} ∘ D̃(W ← U) ∘ q_{U} = p′_{i} ∘ q_{W}

Genauso ist p′_{i} ∘ q_{V} = p′_{i} ∘ q_{W}. Sei nun a : i → j ein Pfeil von I, und sei U aus B, so daß i ∈ U. Dann ist auch j in U, und es ist

D(a) ∘ p_{i} ∘ ψ = D(a) ∘ p′_{i} ∘ q_{U} ≤ p′_{j} ∘ q_{U} = p_{j} ∘ ψ

‘ψ ∘ φ = id_{P} ’:

Sei i aus ObI und U aus B, so daß i ∈ U.

p_{i} ∘ ψ ∘ φ = p′_{i} ∘ q_{U} ∘ φ = p′_{i} ∘′(p^{U}) = p_{i}

‘φ ∘ ψ = id_{Q}’:

Nach Folgerung 3.4 existiert eine untere Adjungierte e_{i} zu p_{i} für jedes i aus ObI. Sei U aus B. Wir zeigen zunächst, daß p_{U} punktweises Supremum von { e_{i} ∘ p_{i} | i ∈ U} ist: Ist i aus U, so folgt aus p_{i} ≥ p_{i} ∘ p^{U}, daß e_{i} ∘ p_{i} ≤ p^{U}, denn p_{i} ist obere Adjungierte zu e_{i}. Also ist p^{U} eine obere Schranke von {e_{i} ∘ p_{i} | i ∈ U}. Sei nun r eine Selbstabbildung von P, die punktweise eine obere Schranke von {e_{i} ∘ p_{i} | i ∈ U} ist. Für jedes i aus U ist dann p_{i} ∘ r ≥ p_{i} ∘ e_{i} ∘ p_{i} = p_{i} = p_{i} ∘ p^{U}. Für jedes i aus Ob(I) \ U ist p_{i} ∘ p^{U} = ⊥ ≤ p_{i} ∘ r. Also ist r ≥ p^{U}.

q_{U} ∘ φ ∘ ψ = ′(p^{U}) ∘ ψ
= ′( ⋁_{i∈U} e_{i} ∘ p_{i}) ∘ ψ
= ′ ⋁_{i∈U} e_{i} ∘ p_{i} ∘ ψ
= ′ ⋁_{i∈U} e_{i} ∘ p′_{i} ∘ q_{U}
= ′( ⋁_{i∈U} e_{i} ∘ p_{i})′ ∘ q_{U}
= id_{im(p^{U})} ∘ q_{U}
= q_{U}

Satz 5.3 Sei D : I → B_{⊥} zykelfrei und einfach. Weiterhin erfülle D die folgenden Bedingungen:

(i) Verbindende Morphismen erhalten das kleinste Element und bilden kompakte Elemente auf kompakte Elemente ab.

(ii) Jedes Hauptende von I ist endlich.

Dann ist der Hyperlimes von D bifinit.

Beweis: Für einen Bereich A bezeichne cQ_{A}^{fin} die Menge der Deflationen von A, das heißt die Menge der stetigen Projektionen mit endlichem Bild. Wir bemerken, daß das Bild einer Deflation nur kompakte Elemente enhält. Da D(i) bifinit ist, ist id_{D(i)} = ⋁ ^{↑}cQ_{D(i)}^{fin} für jedes i aus I (siehe [J]). Für ein Endstück U von I bezeichne R_{U} die folgende Menge:

{(q_{i})_{i∈U} ∈ ∏_{i∈U} cQ_{D(i)}^{fin} | ∀a : i → j ∈ MorI. D(a)(im(q_{i})) ⊆ im(q_{j})}

Sei (A, p) ein Hyperlimeskegel über D. Für U aus E(|I|) und q aus R_{U} sei p^{U,q} : A → A definiert durch

p_{i} ∘ p^{U,q} = \{ \begin{matrix}q_{i} ∘ p_{i} & falls i ∈ U \\ ⊥ & sonst \end{matrix}

‘p^{U,q} ist wohldefiniert’:

Sei a : i → j ein Pfeil aus I. Falls i nicht aus U ist, so ist

D(a) ∘ p_{i} ∘ p^{U,q} = D(a) ∘ ⊥ = ⊥ ≤ p_{j} ∘ p^{U,q}

Falls i aus U ist, so ist auch j in U und es ist

D(a) ∘ p_{i} ∘ p^{U,q} = D(a) ∘ q_{i} ∘ p_{i}
= q_{j} ∘ D(a) ∘ q_{i} ∘ p_{i}
≤ q_{j} ∘ D(a) ∘ p_{i}
≤ q_{j} ∘ p_{j}
= p_{j} ∘ p^{U,q}

Die zweite Gleichung gilt, weil D(a)(im(q_{i})) ⊆ im(q_{j}).

‘p^{U,q} ist eine Projektion’:

Für jedes i aus ObI ist p_{i} ∘ p^{U,q} ≤ p_{i}, also ist p^{U,q} ≤ id_{A}.

p_{i} ∘ p^{U,q} ∘ p^{U,q} = \{ \begin{matrix}q_{i} ∘ p_{i} ∘ p^{U,q} & falls i ∈ U \\ ⊥ ∘ p^{U,q} & sonst \end{matrix}
= \{ \begin{matrix}q_{i} ∘ q_{i} ∘ p_{i} & falls i ∈ U \\ ⊥ & sonst \end{matrix}
= \{ \begin{matrix}q_{i} ∘ p_{i} & falls i ∈ U \\ ⊥ & sonst \end{matrix}
= p_{i} ∘ p^{U,q}

Bezeichne nun E^{fin}(I) die Menge der endlichen Endstücke von I. Es gilt die folgende Aussage:

∀U ∈ E^{fin}(|I|). ∀r ∈ ∏_{i∈U} cQ_{D(i)}^{fin}. ∃q ∈ R_{U}. q ≥ r (∗)

Wir zeigen die Aussage per Induktion über die Mächtigkeit von U. Das können wir machen, da wir I als zykelfrei vorausgesetzt haben. Nehmen wir also an, die Aussage sei bewiesen für alle Endstücke mit weniger als n Elementen. Sei U ein Endstück mit n Elementen. Sei r aus ∏_{i∈U} cQ_{D(i)}^{fin}. Sei k ein maximales Element von U. Für i aus (U \ {k})∩ ↑ k bezeichne r̃_{i} eine Deflation, deren Bild D(i ← k)(im(r_{k})) ∪ im(r_{i}) enthält. So eine Deflation existiert in einem bifiniten Bereich, da D(i ← k)(im(r_{k})) ∪ im(r_{i}) eine endliche Menge von kompakten Elementen ist. (Wir hatten vorausgesetzt, daß verbindende Morphismen kompakte Elemente auf kompakte Elemente abbilden.) Für i aus U\ ↑ k setzen wir r̃_{i} = r_{i}. Nach Induktionsannahme gibt es ein q in R_{U\{k}}, so daß q ≥ (r̃_{i})_{i∈U\{k}}. Setzen wir außerdem q_{k} = r_{k}, so ist (q_{i})_{i∈U} in R_{U}, und es ist (q_{i})_{i∈U} ≥ r.

Bezeichne nun B die folgende Teilmenge von E(I):

B := {↑ i_{1} ∪ ..∪ ↑ i_{n} | n ∈ N, i_{1}, .., i_{n} ∈ ObI}

Wegen Bedingung (ii) sind die Elemente von B endliche Endstücke von I. Da das Bild von p^{U,q} isomorph zu einer Teilmenge von ∏_{i∈U} im(q_{i}) × ∏_{i∈I\U}{⊥} ist, ist es endlich, falls U aus B und q aus R_{U} ist. p^{U,q} ist also eine Deflation, falls U aus B und q aus R_{U} ist.

‘{p^{U,q} | U ∈ B, q ∈ R_{U}} ist gerichtet’:

Seien U, V ∈ B, q ∈ R_{U}, r ∈ R_{V}. Sei i ∈ U ∩ V. Weil D(i) bifinit ist, gibt es eine Deflation s_{i}, die größer ist als q_{i} und r_{i}. Für i ∈ U \ (U ∩ V) setzen wir s_{i} = q_{i}, und für i ∈ V \ (U ∩ V) setzen wir s_{i} = r_{i}. Wegen (∗) gibt es ein t in R_{U∪V}, welches größer ist als s. U ∪ V ist ein Element von B und p^{U∪V,t} ist eine gemeinsame obere Schranke von p^{U,q} und p^{V,r}.

‘⋁ {p^{U,q} | U ∈ B, q ∈ R_{U}} = id_{A}’:

Zunächst zeigen wir, daß id_{A} = ⋁_{U∈B} p^{U}. Sei also r eine obere Schranke von {p^{U} | U ∈ B}. Sei i aus ObI. Es gibt ein U in B, welches i enthält, zum Beispiel U =↑ i. Es ist p_{i} ∘r ≥ p_{i} ∘p^{U} = p_{i}. Da diese Ungleichung für alle i aus ObI gilt, ist r ≥ id_{A}. Bleibt zu zeigen, daß p^{U} = ⋁_{q∈R_{U}} p^{U,q} für jedes U aus B. Sei also U aus B. Sicher ist p^{U} eine obere Schranke von {p^{U,q} | q ∈ R_{U}}. Sei r eine weitere obere Schranke dieser Menge. Seien i ∈ U und s_{i} ∈ cQ_{D(i)}^{fin}. Für j aus U \ {i} sei s_{j} die konstante ⊥-Abbildung. Wegen (∗) gibt es ein q in R_{U}, so daß q ≥ (s_{i})_{i∈U}. Dann ist

p_{i} ∘ r ≥ p_{i} ∘ p^{U,q} = q_{i} ∘ p_{i} ≥ s_{i} ∘ p_{i}.

Da diese Ungleichung für alle Deflationen s_{i} von D(i) gilt, und da das Supremum aller dieser die Identität auf D(i) ist, ist p_{i} ∘ r ≥ p_{i}. Da diese Ungleichung wiederum für alle i aus U gilt, ist r ≥ p^{U}.

Wir haben in Proposition 5.1 festgestellt, daß ein Hyperlimesobjekt über einem Diagramm von distributiven beschränkt vollständigen Mengen distributiv ist, falls die verbindenden Morphismen endliche Suprema erhalten. Jede monotone Funktion zwischen flachen Bereichen erhält Suprema. Wir wissen daher, daß HF -Objekte distributiv sind. Die nächste Proposition liefert uns eine weitere Eigenschaft von HF -Objekten.

Definition 5.2 Eine beschränkt vollständige Menge P heiße kohärent, falls sie die folgende Eigenschaft hat: Ist M eine Teilmenge von P, so daß jede zweielementige Teilmenge von M beschränkt ist, so ist M beschränkt. COH bezeichne die volle Unterkategorie von P OSET, deren Objekte kohärente geordnete Mengen sind.

Die folgende Menge ist beschränkt vollständig aber nicht kohärent:

Proposition 5.3 Sei D : I → COH so, daß verbindende Morphismen Suprema erhalten. Dann ist das Hyperlimesobjekt über D kohärent. Insbesondere sind also HF -Objekte kohärent.

Beweis: Sei (P, p) der kanonische Hyperlimeskegel über D. Sei M eine Teilmenge von P, so daß jede zweielementige Teilmenge von M beschränkt ist. Dann ist jede zweielementige Teilmenge von p_{i}(M) beschränkt für jedes Objekt i von I. Da D(i) kohärent ist, existiert dann das Supremum von p_{i}(M) für jedes Objekt i von I. Weil verbindende Morphismen von D Suprema erhalten, existiert dann auch das Supremum von M, nach Proposition 2.5.

Das obige Beispiel für eine nicht-kohärente Menge ist also ein Beispiel für einen distributiven Bereich, der kein HF -Objekt ist. Am folgenden Beispiel sieht man, daß man in Proposition 5.3 nicht auf die Voraussetzung, daß die verbindenden Morphismen Suprema erhalten, verzichten kann:

(Alle Elemente, von denen kein Pfeil weggeht, sollen auf ⊥ abgebildet werden.) Das Hyperlimesobjekt über diesem Diagramm ist gerade die oben abgebildete nicht-kohärente Menge.

5.2 Rückschlüsse auf das Diagramm bei bekanntem Hyperlimesobjekt

Wir werden uns später in dieser Arbeit mit der Frage beschäftigen, ob es zu einer gegebenen geordneten Menge P ein Diagramm D gibt, so daß P Hyperlimesobjekt über D ist. Dabei wollen wir zusätzlich fordern, daß Hyperlimesprojektionen über D surjektiv sind.

Definition 5.3 Sei C eine Unterkategorie von P OSET. Ein Hyperlimeskegel (P, p) über D heiße Darstellung von P über D in C, falls alle seine Projektionen surjektiv sind. Ist (P, p) eine Darstellung über einem zykelfreien (einfachen) Diagramm, so heiße sie zykelfrei (einfach).

Sei P eine geordnete Menge mit kleinstem Element und (P, p) eine Darstellung über einem Diagramm D. Was für Rückschlüsse können wir aus den Eigenschaften von P auf das Diagramm D ziehen?

Proposition 5.4 Sei P eine geordnete Menge mit kleinstem Element und sei (P, p) eine Darstellung über D : I → P OSET. Dann hat jedes Objekt von D ein kleinstes Element, und verbindende Morphismen erhalten das kleinste Element.

Beweis: Sei i ∈ ObI. Mit der Surjektivität und der Monotonie von p_{i} folgt, daß p_{i}(⊥) kleinstes Element von D(i) ist. Sei a : i → j ein Pfeil von I. Dann ist D(a)(⊥) = D(a) ∘ p_{i}(⊥) ≤ p_{j}(⊥) = ⊥.

Folgerung 5.1

a) Sei P ein geordnete Menge mit kleinstem Element, und sei (P, p) eine einfache Darstellung über D : I → P OSET. Dann hat jede Projektion eine untere Adjungierte.

b) Sei P eine beschränkt vollständige geordnete Menge und sei (P, p) eine einfache Darstellung über D : I → P OSET. Dann ist jedes Objekt von D beschränkt vollständig.

c) Sei A ein Bereich mit kleinstem Element und (A, p) eine einfache Darstellung über D : I → P OSET. Dann ist jedes Objekt von D ein Bereich.

Beweis:

a): Nach Proposition 5.4 hat jedes Objekt von D ein kleinstes Element und die verbindenden Morphismen erhalten es. Nach Folgerung 3.4 hat dann jede Hyperlimesprojektion eine untere Adjungierte.

b),c): Sei i aus ObI. Bezeichne e_{i} die untere Adjungierte zu p_{i}. Da p_{i} surjektiv ist, ist die Adjunktion (p_{i}, e_{i}) sogar ein Projektions-Einbettungspaar. Also ist D(i) isomorph zum Bild von e_{i}∘p_{i}. Das Bild einer internen Projektion von P ist abgeschlossen gegen existierende Suprema, ist also ein Bereich, falls P ein Bereich ist, und beschränkt vollständig, falls P beschränkt vollständig ist.

Als nächstes ein Beispiel für eine nicht-einfache Darstellung eines Bereiches über einem Diagramm D : I → P OSET, dessen Objekte nicht alle Bereiche sind:

Wir haben gesehen, daß die Objekte des Darstellungsdiagrammes D : I → P OSET einer einfachen Darstellung eines Bereiches mit kleinstem Element Bereiche sind. Sind die verbindenden Morphismen auch stetig? Im allgemeinen nicht. Zum Beispiel:

Jedoch:

Proposition 5.5

a) Sei A ein schnittstetiger Bereich und (A, p) eine Darstellung über einem einfachen Diagramm D : I → P OSET. Sei j ein Objekt von I, so daß es kein von j verschiedenes Objekt k gibt, so daß sowohl [j → k] als auch [k → j] nichtleer sind. Dann sind alle vebindenden Morphismen nach D(j) stetig. Insbesondere: Ist D zykelfrei, so sind sämtliche verbindende Morphismen von D stetig.

b) Sei P eine distributive, geordnete Menge und (P, p) eine Darstellung über einem einfachen Diagramm D : I → P OSET. Sei j ein Objekt von I, so daß es kein von j verschiedenes Objekt k gibt, so daß sowohl [j → k] als auch [k → j] nichtleer sind. Dann erhalten alle verbindenden Morphismen nach D(j) endliche Suprema. Insbesondere: Ist D zykelfrei, so erhalten sämtliche verbindenden Morphismen von D endliche Suprema.

Beweis:

a) Sei i ein Objekt von I so, daß [i → j] ≠ ∅, und M eine gerichtete Teilmenge von D(i). Nach Folgerung 5.1 sind D(i) und D(j) Bereiche. Also existieren die Suprema von M und D(j ← i)(M). Wir definieren Elemente x und y von A durch

p_{k}(x) = \{ \begin{matrix}⊥ & falls [j → k] = ∅ \\ D(k ← i)(⋁ ^{↑}M) & falls [j → k] ≠ ∅ \end{matrix}

p_{k}(y) = \{ \begin{matrix}⊥ & falls [j → k] = ∅ \\ ⋁ ^{↑}D(j ← i)(M) & falls k = j \\ D(k ← i)(⋁ ^{↑}M) & falls [j → k] ≠ ∅, k ≠ j \end{matrix}

Die erste Vorschrift liefert offensichtlich ein Element von A. Die zweite Vorschrift liefert ein Element von A, weil es kein von j verschiedenes Objekt k gibt, so daß sowohl [j → k] als auch [k → j] nichtleer sind. Bezeichne nun e_{i} die untere Adjungierte zu p_{i}. Diese existiert nach Folgerung 5.1 und ist nach Folgerung 3.4 gegeben durch

p_{k} ∘ e_{i} = \{ \begin{matrix}⊥ & falls [i → k] = ∅ \\ D(k ← i) & falls [i → k] ≠ ∅ \end{matrix}

Sei nun m aus M. Sei k aus Ob(I). Dann ist

p_{k}(x ∧ e_{i}(m)) = p_{k}(x) ∧ p_{k} ∘ e_{i}(m)
= \{ \begin{matrix}⊥ & falls [j → k] = ∅ \\ D(k ← i)(m) & falls [j → k] ≠ ∅ \end{matrix}
≤ p_{k}(y)

Da diese Ungleichung für alle k aus Ob(I) gilt, ist x ∧ e_{i}(m) ≤ y. Da diese Ungleichung wiederum für alle m aus M gilt, ist ⋁ ^{↑}(x ∧ e_{i}(M)) ≤ y. Nun ist

⋁ ^{↑}D(j ← i)(M) = p_{j}(y)
≥ p_{j}(⋁ ^{↑}(x ∧ e_{i}(M)))
= p_{j}(x ∧ ⋁ ^{↑}e_{i}(M))
= p_{j}(x ∧ e_{i}(⋁ ^{↑}M))
= p_{j}(x) ∧ p_{j} ∘ e_{i}(⋁ ^{↑}M)
= D(j ← i)(⋁ ^{↑}M)

Von der zweiten in die dritte Zeile haben wir die Schnittstetigkeit von A benutzt.

b) beweist man analog.

Folgerung 5.2 Sei P eine beschränkt vollständige geordnete Menge und (P, p) eine Darstellung über einem zykelfreien, einfachen Diagramm D : I → P OSET.

a) Ist P ein stetiger Bereich, so sind sämtliche verbindende Morphismen von D stetig, und jedes Objekt von D ist ein stetiger Bereich.

b) Ist P distributiv, so ist jedes Objekt von D distributiv.

c) Ist P ein stetiger, distributiver Bereich, so erhalten verbindende Morphismen von D beliebige Suprema.

d) Ist P ein algebraischer, beschränkt vollständiger Bereich, so ist jedes Objekt von D ein algebraischer Bereich.

e) Ist P ein dI-Bereich, so ist jedes Objekt von D ein dI-Bereich.

Beweis:

a) Als stetiger, beschränkt vollständiger Bereich ist P insbesondere schnittstetig, und die Stetigkeit der verbindenden Morphismen folgt mit Proposition 5.5. Nach Proposition 2.2 ist dann jede Hyperlimesprojektion über D stetig. Die Objekte von D sind also Bilder von stetigen Retraktionen, sind also stetig.

b) Nach Proposition 5.5 erhalten verbindende Morphismen von D endliche Suprema. Nach Proposition 2.5 erhalten dann Hyperlimesprojektionen über D Infima und endliche Suprema. Jedes Objekt von D ist also Bild einer distributiven geordneten Menge unter einer Abbildung die endliche Infima und Suprema erhält, ist also distributiv.

c) Verbindende Morphismen erhalten endliche Suprema nach Proposition 5.5 und gerichtete Suprema nach a). d) Sei i aus Ob(I). Sei k ein kompaktes Element von P, so daß p_{j}(k) = ⊥ für alle k aus Ob(I)\ ↑ i.

Wir zeigen zunächst, daß dann p_{i}(k) ein kompaktes Element von D(i) ist: Sei also M eine gerichtete Teilmenge von D(i), so daß ⋁ ^{↑}M = p_{i}(k). Für jedes m aus M definieren wir ein Element x_{m} aus P durch

p_{j}(x_{m}) = \{ \begin{matrix}⊥ & falls [i → j] = ∅ \\ m & falls j = i \\ p_{j}(k) & falls [i → j] ≠ ∅, j ≠ i \end{matrix}

{x_{m} | m ∈ M} ist gerichtet und es ist ⋁ ^{↑}{x_{m} | m ∈ M} = k. Da k kompakt ist, gibt es ein Element m von M, so daß x_{m} = k. Dann ist m = p_{i}(x_{m}) = p_{i}(k). Wir haben nun die folgende Implikation gezeigt: (⋁ ^{↑}M = p_{i}(k)) ⇒ (∃m ∈ M. m = p_{i}(k)). Da wir wissen, daß D(i) stetig ist, folgt daraus die Kompaktheit von p_{i}(k). Sei nun x aus D(i). Für alle j aus Ob(I)\ ↑ i ist p_{j} ∘ e_{i}(x) = ⊥. Also ist auch p_{j} ∘ e_{i}(k) = ⊥ für alle k aus K_{e_{i}(x)} und alle j aus Ob(I)\ ↑ i. Wie wir eben gezeigt haben, sind dann alle Elemente von p_{i}(K_{e_{i}(x)}) kompakt. Es ist

x = p_{i} ∘ e_{i}(x) = p_{i}(⋁ ^{↑}K_{e_{i}(x)}) = ⋁ ^{↑}p_{i}(K_{e_{i}(x)})

e) Objekte von D sind distributiv, nach a), und algebraisch, nach d). Ist k ein kompaktes Element von D(i), so ist e_{i}(k) ein kompaktes Element von P, denn e_{i} ist untere Adjungierte einer stetigen Abbildung. Da P endlich algebraisch ist, ist dann ↓ e_{i}(k) endlich. Wegen der Monotonie von e_{i} ist e_{i}(↓ k) eine Teilmenge von ↓ e_{i}(k). Also ist e_{i}(↓ k) endlich. Weil e_{i} injektiv ist, ist dann auch ↓ k endlich.

Die letzten Propositionen beruhen darauf, daß bei einer einfachen Darstellung einer geordneten Menge mit kleinstem Element jede Projektion eine untere Adjungierte hat. Diese Eigenschaft hat auch jede zykelfreie, nicht-einfache Darstellung eines endlich algebraischen Bereiches über einem Diagramm nach DCP O. Der Schlüssel zu dieser Erkenntniss liegt in dem folgenden einfachen Lemma:

Lemma 5.2 Sei A ein endlich algebraischer Bereich mit kleinstem Element und (A, p) eine zykelfreie Darstellung über D : I → DCP O. Dann:

(i) Verbindende Morphismen von D bilden kompakte Elemente auf kompakte Elemente ab.

(ii) {j ∈ Ob(I) | ∃a : i → j. D(a)(k) ≠ ⊥} ist endlich für alle Objekte i von I und alle kompakten Elemente k von D(i).

Beweis: Seien i aus Ob(I) und k aus K(D(i)). Da p_{i} surjektiv ist, gibt es ein Element y von A, so daß p_{i}(y) = k. Da A algebraisch ist, ist y = ⋁ ^{↑}K_{y}. Dann ist k = p_{i}(⋁ ^{↑}K_{y}) = ⋁ ^{↑}p_{i}(K_{y}). Da k kompakt ist, gibt es ein Element h von K_{y}, so daß p_{i}(h) = k. Für jedes j ∈↑ i und jedes x ∈↓ p_{j}(h) definieren wir uns nun ein Element z_{j,x} von ↓ h durch

p_{l}(z_{j,x}) := \{ \begin{matrix}⊥ & falls [j → l] = ∅ \\ x & falls l = j \\ p_{l}(h) & falls [j → l] ≠ ∅, l ≠ j \end{matrix}

Es ist z_{j,x} ≠ z_{r,y}, falls ((j, x) ≠ (r, y) und (x ≠ ⊥ oder y ≠ ⊥)). Also ist | ↓ h| ≥ Σ_{j∈↑i}| ↓ p_{j}(h) \ {⊥}|. Da ↓ h endlich ist, ist dann {j | p_{j}(h) ≠ ⊥} endlich, und für jedes j aus ↑ i ist ↓ p_{j}(h) endlich. Für jeden Pfeil a : i → j ist D(a)(k) = D(a) ∘ p_{i}(h) ≤ p_{j}(h). Also ist {j | ∃a : i → j. D(a)(k) ≠ ⊥} eine Teilmenge von {j | p_{j}(h) ≠ ⊥} und (ii) folgt. Für jeden Pfeil a : i → j ist ↓ D(a)(k) eine Teilmenge von ↓ p_{j}(h). Also erzeugt D(a)(k) einen endlichen Hauptanfang, und ist somit kompakt.

Proposition 5.6 Sei A ein endlich algebraischer, beschränkt vollständiger Bereich und sei (A, p) eine Darstellung über einem zykelfreien Diagramm D : I → DCP O. Dann hat jede Hyperlimesprojektion über D eine untere Adjungierte.

Beweis: Für jedes Objekt i von I und jedes kompakte Element x von D(i) bezeichne

M_{i,x} := {j ∈ Ob(I) | ∃a : i → j ∈ Mor(I). D(a)(x) ≠ ⊥}

Wir zeigen die folgende Aussage per Induktion über |M_{i,x}|:

∀i ∈ Ob(I). ∀x ∈ K(D(i)). p_{i}(⋀ p_{i}^{−1}(↑ x)) ≥ x

Seien i ∈ Ob(I) und x ∈ K(D(i)), so daß |M_{i,x}| = 1. Dann ist ⋀ p_{i}^{−1}(↑ x) gegeben durch

p_{j}(⋀ p_{i}^{−1}(↑ x)) = \{ \begin{matrix}x & falls j = i \\ ⊥ & falls j ≠ i \end{matrix}

Nehmen wir nun an wir hätten die Aussage bewiesen für alle i ∈ Ob(I), x ∈ K(D(i)) mit |M_{i,x}| < n. Seien nun i ∈ Ob(I) und x ∈ K(D(i)), so daß |M_{i,x}| = n. Wir definieren ein Element z von A durch

p_{j}(z) = \{ \begin{matrix}x & falls j = i \\ p_{j}(⋀ p_{i}^{−1}(↑ x)) & falls j ≠ i \end{matrix}

Wir müssen zeigen, daß dadurch wirklich ein Element von A definiert ist. Sei a : i → j ein Pfeil aus I, so daß j ≠ i. Falls j ∉ M_{i,x}, so ist D(a) ∘ p_{i}(z) = ⊥ ≤ p_{j}(z). Falls j ∈ M_{i,x}: Ist y ∈ p_{i}^{−1}(↑ x), so ist p_{j}(y) ≥ D(a) ∘ p_{i}(y) ≥ D(a)(x).

Also ist p_{i}^{−1}(↑ x) ⊆ p_{j}^{−1}(↑ D(a)(x)), also p_{j}(⋀ p_{i}^{−1}(↑ x)) ≥ p_{j}(⋀ p_{j}^{−1}(↑ D(a)(x))). Sicher ist M_{D(a)(x),j} eine echte Teilmenge von M_{i,x}. Nach Induktionsannahme ist also p_{j}(⋀ p_{j}^{−1}(↑ D(a)(x))) ≥ D(a)(x). Insgesamt erhalten wir also p_{j}(z) = p_{j}(⋀ p_{i}^{−1}(↑ x)) ≥ D(a)(x) = D(a) ∘ p_{i}(z). Sei nun a : j → i ein Pfeil aus I, so daß j ≠ i. Da p_{i} surjektiv ist, gibt es ein y ∈ A, so daß p_{i}(y) = x. Es ist D(a) ∘ p_{j}(z) = D(a) ∘ p_{j}(⋀ p_{i}^{−1}(↑ x)) ≤ D(a) ∘ p_{j}(y) ≤ p_{i}(y) = x = p_{i}(z). Wir haben nun gezeigt,daß durch obige Vorschrift tatsächlich ein Element z von A definiert ist. Offensichtlich ist z minimal in p_{i}^{−1}(↑ x). Sei nun i ein Objekt von I, und sei e_{i} : D(i) → A die stetige Fortsetzung der Funktion, die jedem kompakten Element k von D(i) das Minimum von p_{i}^{−1}(↑ k) zuordnet. Dann ist für x ∈ D(i)

p_{i} ∘ e_{i}(x) = p_{i}(⋁ ^{↑}e_{i}(K_{x}))
= ⋁ ^{↑}p_{i} ∘ e_{i}(K_{x})
= ⋁ _{k∈K_{x}}^{↑}p_{i}(⋀ p_{i}^{−1}(↑ k))
≥ ⋁ ^{↑}K_{x}
= x

Für x ∈ A ist

e_{i} ∘ p_{i}(x) = ⋁ ^{↑}e_{i}(K_{p_{i}(x)})
= ⋁ _{k∈K_{p_{i}(x)}}^{↑} ⋀ p_{i}^{−1}(↑ k)
≤ ⋀ p_{i}^{−1}(p_{i}(x))
≤ x

e_{i} ist also untere Adjungierte zu p_{i}.

Folgerung 5.3 Sei A ein endlich algebraischer, beschränkt vollständiger Bereich und (A, p) eine zykelfreie Darstellung über einem Diagramm D : I → DCP O.

a) Jedes Objekt von D ist ein endlich algebraischer, beschränkt vollständiger Bereich.

b) Bezeichne D̃ das Diagramm aus Proposition 3.1. Dann ist (A, p) eine Darstellung über D̃. Wir können also annehmen, daß jede zykelfreie Darstellung eines endlich algebraischen Scott-Bereiches einfach ist.

Beweis:

a) Als Bild eines endlich algebraischen, beschränkt vollständigen Bereiches unter einer stetigen oberen Adjungierten ist jedes Diagrammobjekt beschränkt vollständig und endlich algebraisch.

Mit Lemma 5.2 und Proposition 5.5 b) erhalten wir für zykelfreie, strikte Diagramme eine Umkehrung von Satz 5.2:

Korollar 5.1 Sei D : I → dI ein zykelfreies, einfaches Diagramm, derart daß Hyperlimesprojektionen über D surjektiv sind. Dann sind äquivalent:

(1) Das Hyperlimesobjekt über D ist ein dI-Bereich.

(2) D erfüllt Bedingungen (i) bis (iii) aus Satz 5.2.

Wir beenden diesen Abschnitt mit einem Beispiel für eine nichteinfache Darstellung eines Scott-Bereiches, deren Projektionen keine oberen Adjungierten sind:

Wären die Projektionen über D obere Adjungierte, so wären alle Objekte von D beschränkt vollständig, als Bilder einer beschränkt vollständigen Menge unter einer oberen Adjungierten. Es ist aber kein Objekt von D beschränkt vollständig.

6 Der Zerlegungssatz

In diesem Abschnitt werden wir zeigen, daß sich jeder dI-Bereich darstellen läßt als zykelfreier Hyperlimes von Bereichen, die sich nicht mehr als zykelfreie Hyperlimites von kleineren Bereichen darstellen lassen. Wir beginnen damit, die interne Struktur von Hyperlimesobjekten über zykelfreien Diagrammen beschränkt vollständiger geordneter Mengen genauer unter die Lupe zu nehmen.

6.1 Die Struktur von Hyperlimesobjekten über zykelfreien Diagrammen beschränkt vollständiger geordneter Mengen

Wir hatten in Kapitel 3 gesehen, daß surjektive Hyperlimesprojektionen über einem Diagramm von beschränkt vollständigen geordneten Mengen obere Adjungierte sind. Nach Proposition 3.4 können wir dann annehmen,daß das Diagramm von einer Menge interner Projektionen des Hyperlimesobjektes definiert wird, welche bestimmte Eigenschaften hat.Umgekehrt definiert eine Menge interner Projektionen einer geordneten Menge eine Darstellung der Menge, falls sie diese Eigenschaften hat.

Definition 6.1 Sei P eine geordnete Menge und M eine Menge interner Projektionen von P, welche die Eigenschaften (i) bis (iii) aus Proposition 3.4 hat. Dann wollen wir sagen, M definere eine Darstellung von P.

Proposition 6.1 Sei P eine beschränkt vollständige geordnete Menge und M eine Menge von internen Projektionen, welche eine Darstellung definiert. Sei P eine Partition von M. Dann definiert auch M_{P} := {⋁_{Q_{P}} K | K ∈ P} eine Darstellung von P.

( Zur Erinnerung: Q_{P} bezeichnet die Menge der internen Projektionen von P mit der punktweisen Ordnung. Ist P beschränkt vollständig, so ist Q_{P} ein vollständiger Verband und Suprema in Q_{P} werden punktweise gebildet.)

Beweis: Wir müssen zeigen, daß M_{P} Bedingungen (i) bis (iii) aus Proposition 3.4 erfüllt.

(i) ⋁ M_{P} = ⋁_{K∈P} ⋁ K = ⋁ M = id_{P}

(ii),(iii) Sei (x_{K})_{K∈P} ∈ ∏_{K∈P} im(⋁ K), so daß (⋁ K)(x_{H}) ≤ x_{K} für alle K, H ∈ P. Für q ∈ M bezeichne [q]P das Element von P, welches q enthält. Seien p, q ∈ M. Dann ist

p ∘ q(x_{[q]P}) ≤ p(x_{[q]P}) = p ∘ (⋁[p]P)(x_{[q]P}) ≤ p(x_{[p]P})

Es ist also (p(x_{[p]P}))_{p∈M} ∈ ∏_{p∈M} im(p), so daß p(q(x_{[q]P})) ≤ p(x_{[p]P}) für alle p, q ∈ M.

Weil M (ii) erfüllt, existiert also ⋁_{p∈M} p(x_{[p]P}).

Wegen x_{K} = (⋁ K)(x_{K}) = ⋁_{p∈K} p(x_{K}) = ⋁_{p∈K} p(x_{[p]P}) ist ⋁_{K∈P} x_{K} = ⋁_{p∈M} p(x_{[p]P}). Weiterhin ist

(⋁ K)( ⋁_{K∈P} x_{K}) = ⋁_{p∈K} p( ⋁_{q∈M} q(x_{[q]P}))
= ⋁_{p∈K} p(x_{[p]P})
= x_{K}

Die vorletzte Gleichung der Gleichungskette gilt, weil M (iii) erfüllt.

Wir werden nun sehr spezielle Partitionen von M betrachten, nämlich Partitionen in ein Endstück von M und dessen Komplement. Eine solche Partition definiert eine zykelfreie Darstellung über einem Diagramm mit nur zwei Objekten.

Definition 6.2 Sei P eine geordnete Menge mit kleinstem Element. (p, q) ∈ (Q_{P})^{2} heiße Halbfaktor-Kohalbfaktorprojektions-Paar von P, falls {p, q} eine Darstellung von P definiert und q ∘ p = ⊥. Das Bild von p nennen wir dann einen Halbfaktor von P, das Bild von q einen Kohalbfaktor. Entsprechend nennen wir p eine Halbfaktorprojektion und q eine Kohalbfaktorprojektion. Für die Menge aller Halbfaktorprojektionen von P schreiben wir H_{P}, für die Menge aller Halbfaktoren von P schreiben wir H̃_{P}.

Proposition 6.2 Sei P eine geordnete Menge mit kleinstem Element und (p, q) ein Halbfaktor-Kohalbfaktorprojektions-Paar von P. Dann:

a) p ist stabil.

b) Ist P beschränkt vollständig, so ist q = Min{r ∈ Q_{P} | r ∨ p = id}.

c) im(p) ∩ im(q) = {⊥}.

Beweis:

a) Sei x ∈ im(p) und y ∈↓ x. Weil q ∘ p = ⊥, ist q(y) ≤ q(x) = ⊥. Dann ist y = p(y) ∨ q(y) = p(y) ∨ ⊥ = p(y). Also y ∈ im(p). Die erste Gleichung in der letzten Gleichungskette steht wegen Eigenschaft (i) aus Proposition 3.4.

b) Nach Eigenschaft (i) aus 3.4 ist q ∨ p = id. Sei r ∈ Q_{P}, so daß r ∨ p = id. Sei x ∈ P. Dann ist

x = p(x) ∨ r(x) = p(x) ∨ (p ∨ q) ∘ r(x) = p(x) ∨ p ∘ r(x) ∨ q ∘ r(x) = p(x) ∨ q ∘ r(x)

Dabei haben wir benutzt, daß in Q_{P} Suprema punktweise gebildet werden, da P beschränkt vollständig ist. Wegen Eigenschaft (iii) ist q(x) = q(p(x) ∨ q ∘ r(x)) = q ∘ r(x). Da das für alle x aus P gilt, ist q = q ∘ r, also q ≤ r.

c) Da p stabil ist, ist im(p) ∩ im(q) = im(q ∘ p).

Definition 6.3 Sei P eine geordnete Menge, und seien p, q Elemente von Q_{P}, so daß q ≤ p. Falls {r ∈ Q_{P} | r ∨ q = p} ein Minimum hat, so schreiben wir für dieses p/q.

Ist also zum Beispiel (p, q) ein Halbfaktor-Kohalbfaktorprojektions-Paar, so ist q = id/p. Der nächste Satz besagt, daß wir sämtliche zykelfreien Darstellungen einer beschränkt vollständigen geordneten Menge P kennen, falls wir nur alle Halbfaktoren von P kennen. Zunächst zwei Definitionen:

Definition 6.4 Sei L ein vollständiger Verband. J(L) bezeichne die Menge der vollständig verbindungsirreduziblen Elemente von L, also

J(L) := {x ∈ L | (⋁ M = x) ⇒ (∃m ∈ M. x = m)}

S(L) bezeichne die Menge der vollständig schnittirreduziblen Elemente, also

S(L) := {x ∈ L | (⋀ M = x) ⇒ (∃m ∈ M. x = m)}

Ist x aus J(L), so bezeichne x^{↓} den unteren Nachbarn von x, also

x^{↓} := ⋁(↓ x \ {x})

Ist x aus S(L), so bezeichne x^{↑} den oberen Nachbarn von x, also

x^{↑} := ⋀(↑ x \ {x})

Definition 6.5 Sei P eine geordnete Menge und M ein Teilmenge von Q_{P}. Dann bezeichne

L_{M} := {⋁ U | U ⊆ M ist ein Endstück in der ∗ −P räordnung}

Satz 6.1 Sei P eine beschränkt vollständige geordnete Menge, und sei M eine Teilmenge von Q_{P}, welche eine Darstellung von P definiert. Dann:

a) Jedes Element von L_{M} ist eine Halbfaktorprojektion. Es ist also L_{M} ⊆ H_{P}.

b) L_{M} ist ein vollständiger Unterverband des Verbandes Q_{P} aller internen Projektionen.

c) Die Vorschrift U ↦ ⋁ U definiert einen Ordnungsisomorphismus von der Menge der ∗-Endstücke von M \ {⊥} mit der Inklusionsordnung nach L_{M}. Insbesondere ist L_{M} also algebraisch und vollständig distributiv.

d) Seien U, W ∗-Endstücke von M, derart daß W = U ∪ {p}.

Dann ist p = ⋁ W/ ⋁ U.

e) Wir setzen nun zusätzlich voraus, daß die ∗-Präordnung auf M antisymmetrisch ist. Dann ist (M \ {⊥}) = {p/p^{↓} | p ∈ J(L_{M})} = {p^{↑}/p | p ∈ S(L_{M})}.

Beweis:

a) Sei U ein Endstück von M. Dann ist {U, M \ U} eine Partition von M, und nach Proposition 6.1 ist {U, M \ U} eine Darstellung von P. Bleibt zu zeigen, daß ⋁ M \ U ∘ ⋁ U = ⊥. Sei p aus M \ U und sei x aus dem Bild von ⋁ U. Wir definieren ein Tupel (x_{q})_{q∈M} durch

x_{q} = \{ \begin{matrix}q(x) & falls q ∈ U \\ ⊥ & falls q ∈ M \ U \end{matrix}

Nach Definition der ∗-Präordnung ist r ∘ q = ⊥, falls q ∈ U und r ∈ M \ U. Es ist also r(x_{q}) ≤ x_{r} für alle r, q aus M. Nun ist x = (⋁ U)(x) = ⋁_{q∈M} x_{q} und p(x) = p(⋁_{q∈M} x_{q}) = x_{p} = ⊥. Die vorletzte Gleichung der letzten Gleichungskette gilt wegen Eigenschaft (iii). Wir haben nun gezeigt, daß p(x) = ⊥ für alle p aus M \ U und alle x aus dem Bild von ⋁ U. Also ist p ∘ ⋁ U = ⊥ für alle p aus M \ U. Also (⋁ M \ U) ∘ ⋁ U = ⋁_{p∈M\U}(p ∘ ⋁ U) = ⊥.

b) Sei {U_{i} | i ∈ I} eine Menge von ∗-Endstücken von M. Es ist ⋁_{i∈I} ⋁ U_{i} = ⋁ ⋃_{i∈I} U_{i}. Als Vereinigung von Endstücken ist ⋃_{i∈I} U_{i} wieder ein Endstück. L_{M} ist also abgeschlossen gegen Suprema. Wir behaupten nun, daß ⋀_{i∈I} ⋁ U_{i} = ⋁ ⋂_{i∈I} U_{i}. Daß die linke Seite größer ist als die rechte, folgt aus der Monotonie von ⋁ : P(Q_{P}) → Q_{P}. Um die andere Ungleichung zu zeigen, zeigen wir, daß das Bild von ⋀_{i∈I} ⋁ U_{i} im Bild von ⋁ ⋂_{i∈I} U_{i} enthalten ist. Für jedes i ∈ I ist ⋁ U_{i} ein Halbfaktor, ist also insbesondere stabil. Das Bild von ⋀_{i∈I} ⋁ U_{i} ist also gerade der Schnitt der Bilder der ⋁ U_{i}. Sei also x aus ⋂_{i∈I} im(⋁ U_{i}). Sei p aus M \ ⋂_{i∈I} U_{i}. Dann gibt es ein j aus I, so daß p ∉ U_{j}. Nach a) ist (⋁ U_{j}, ⋁(M \ U_{j})) ein Halbfaktor-Kohalbfaktorprojektionspaar. Also ist p ∘ ⋁ U_{j} ≤ ⋁(M \ U_{j}) ∘ ⋁ U_{j} = ⊥. Da x ein Element des Bildes von ⋁ U_{j} ist, ist dann p(x) = ⊥. Wir haben damit gezeigt, daß p(x) = ⊥, falls p aus M \ ⋂_{i∈I} U_{i}. Andererseits ist das punktweise Supremum von M gleich der Identität, nach Eigenschaft (i). Also ist x = (⋁ M)(x) = (⋁ ⋂_{i∈I} U_{i})(x). Damit ist x ein Element des Bildes von ⋁ ⋂_{i∈I} U_{i}.

c) Offensichtlich ist die durch die Vorschrift U ↦ ⋁ U definerte Abbildung surjektiv und monoton. Bleibt zu zeigen, daß aus ⋁ U ≤ ⋁ W folgt, daß U eine Teilmenge von W ist. Seien also U und W ∗-Endstücke von M \ {⊥}, so daß ⋁ U ≤ ⋁ W. Angenommen es gäbe ein Element p von U \ W. Dann wäre p ∘ ⋁ W ≤ ⋁(M \ W) ∘ ⋁ W = ⊥. Da p ≤ ⋁ U ≤ ⋁ W, wäre dann auch p^{2} = ⊥, also p = p^{2} = ⊥. Ein Widerspruch.

d) Sicher ist ⋁ U ∨ p = ⋁ W.

Sei r ein Element von Q_{P}, so daß ⋁ U ∨ r = ⋁ W. Sei x ein Element des Bildes von ⋁ W. Dann ist

x = (⋁ U)(x) ∨ r(x)
= (⋁ U)(x) ∨ (⋁ U) ∘ r(x) ∨ p ∘ r(x)
= (⋁ U)(x) ∨ p ∘ r(x)

Wegen Eigenschaft (iii) angewendet auf {U, M \ U} ist

(⋁ M \ U)((⋁ U)(x) ∨ p ∘ r(x)) = p ∘ r(x).

Mit diesen beiden Gleichungen erhalten wir

p(x) = p ∘ (⋁ M \ U)(x) = p ∘ r(x)

Diese Gleichung gilt zunächst für alle x aus dem Bild von ⋁ W. Da aber p kleiner ist als ⋁ W, gilt sie auch für alle x aus P. Also ist p ≤ r. e) Wir zeigen zunächst die erste Gleichung:

‘⊆’: Sei p ein Element von M \ {⊥}. Da wir die ∗-Präordnung als antisymmetrisch vorausgesetzt haben, ist ↑^{∗} p \ {p} ein ∗-Endstück von M, und ↑ p \ {p} ist der untere Nachbar von ↑^{∗} p in E(M \ {⊥}). Da U ↦ ⋁ U einen Isomorphismus von E(M \ {⊥}) nach L_{M} definiert, ist dann ⋁(↑^{∗} p \ {p}) der untere Nachbar von ⋁(↑^{∗} p) in L_{M}. Nach d) ist p = (⋁ ↑^{∗} p)/(⋁ ↑^{∗} p \ {p}).

‘⊇’: Sei p ein verbindundgsirreduzibles Element von L_{M}. Zu zeigen ist, daß es ein q ∈ M \{⊥} gibt, so daß q = p/p^{↓}. Nach Definition von L_{M} ist p = ⋁ U für ein U aus E(M \ {⊥}). Da durch U ↦ ⋁ U ein Isomorphismus von E(M \ {⊥}) nach L_{M} definiert ist, ist U verbindungsirreduzibel in E(M \ {⊥}). Das heißt U ist gleich ↑^{∗} q für ein q aus M \ {⊥}. Also p = ⋁(↑^{∗} q). Nach d) ist q = p/ ⋁(↑^{∗} q \ {q}). Wie wir bereits gesehen haben, ist ⋁(↑^{∗} q \ {q}) der untere Nachbar von p in L_{M}.

Die zweite Gleichung beweist man analog, wobei man benutzt, daß die schnittirreduziblen Elemente von E(M \ {⊥}) gerade die Komplemente von Hauptanfängen sind.

Was können wir mit dem Satz anfangen? Angenommen wir haben eine beschränkt vollständige Menge P gegeben und suchen nach zykelfreien Hyperlimesdarstellungen von P. Der Satz legt uns eine Strategie an die Hand: Wir müssen nach vollständigen Unterverbänden von Q_{P} suchen, deren Elemente Halbfaktorprojektionen sind. Diese Verbände müssen Eigenschaften von Endstückverbänden geordneter Mengen haben. So müssen sie zum Beispiel vollständig distributiv sein. Haben wir einen solchen Verband L gefunden, so sagt uns Teil e) des Satzes wie wir daraus eine Darstellung von P erhalten, falls sie existiert. Wir nehmen nämlich die vollständig verbundirreduziblen Elemente von L, und schauen, ob es zu jedem solchen Element p eine minimale Projektion p/p^{↓} gibt, so daß das Supremum von p/p^{↓} und dem unteren Nachbarn von p in L gleich p ist. Ist das der Fall, so müssen wir noch nachweisen, daß die Menge aller so gewonnenen Projektionen p/p^{↓} tatsächlich eine Darstellung definiert.

6.2 Eine Charakterisierung der Halbfaktoren

Wir werden nun die Halbfaktoren von beschränkt vollständigen geordneten Mengen genau beschreiben:

Proposition 6.3 Sei P eine beschränkt vollständige geordnete Menge, und sei p ∈ Q_{P}. Dann ist p eine Halbfaktorprojektion, genau dann wenn p die folgenden Eigenschaften hat:

(i) id/p existiert.

(ii) ∀x ∈ im(p).∀y ∈ P. [(p(y) ≤ x) ⇒ (x ∨ y existiert)] (Slide-Bedingung)

(iii) ∀x ∈ im(p).∀y ∈ P. [(p(y) ≤ x) ⇒ (p(x ∨ y) = x)] Beweis:

‘nur dann wenn’: (i) Nach Proposition 6.2 b) ist die Kohalbfaktorprojektion zu p gleich id/p.

(ii) Seien x ∈ P und y ∈ P, so daß p(y) ≤ x. {p, id/p} hat die Eigenschaften aus Proposition 3.4. Wegen Eigenschaft (ii) existiert x ∨ (id/p)(y). Nach Voraussetzung ist x ≥ p(y), und nach Eigenschaft (i) ist y = p(y) ∨ (id/p)(y). Also ist x ∨ (id/p)(y) ≥ y, also ist x ∨ (id/p)(y) = x ∨ y.

(iii) Seien x ∈ im(p) und y ∈ P, so daß p(y) ≤ x. Wegen Eigenschaft (iii) aus Proposition 3.4 ist p(x ∨ y) = p(x ∨ id/p(y)) = p(x).

‘wenn’: Wir behaupten, daß id/p Kohalbfaktorprojektion zu p ist. Zu zeigen ist, daß {p, id/p} die Eigenschaften aus Proposition 3.4 hat. Nach Definition von id/p ist p ∨ id/p = id. Da Suprema von Projektionen einer beschränkt vollständigen geordneten Menge punktweise gebildet werden, hat {p, id/p} also die Eigenschaft (i) aus Proposition 3.4. Eigenschaften (ii) und (iii) aus Proposition 3.4 sind offensichtlich schwächer als Eigenschaften (ii) und (iii) aus dieser Proposition.

Die Bedingung (i) aus der letzten Proposition hat den Nachteil, daß wir den ganzen Verband Q_{P} kennen müssen, um sie zu überprüfen. Wir werden deshalb die Halbfaktorprojektionen einer beschränkt vollständigen geordneten Menge noch auf eine andere Weise charakterisieren und dabei Eigenschaft (i) ersetzen. Diese andere Charakterisierung beruht darauf, daß wir den Kern einer Kohalbfaktorprojektion beschreiben können, ohne in dieser Beschreibung die Kohalbfaktorprojektionen selber zu benutzen. Zunächst eine Charakterisierung von Projektionskernen:

Definition 6.6 Sei P eine geordnete Menge. P roker(P) bezeichne die Menge aller Äquivalenzrelationen R auf P, die die folgenden beiden Bedingungen erfüllen:

(i) Jedes Element K von P/R hat ein kleinstes Element Min(K).

(ii) Sind K, H ∈ P/R, so daß ↑ K ∩ H nichtleer ist, so ist Min(K) ≤ Min(H).

Proposition 6.4 Sei P eine geordnete Menge. Die Abbildung φ : Q_{P} → P roker(P) sei gegeben durch φ(p) = ker(p). φ ist ein Ordnungsisomorphismus von Q_{P} nach P roker(P) mit der umgekehrten Inklusionsordnung. Seine Umkehrabbildung ψ : P roker(P) → Q_{P} ist gegeben durch ψ(R)(x) = Min([x]R).

Beweis:

‘φ wohldefiniert’: Seien p aus Q_{P} und K aus P/ker(p). Dann ist p(K) = {x} für ein x aus P. Da p kleiner ist als die Identität, ist x eine untere Schranke von K. Da p idempotent ist, ist x ein Element von K. Also ist x kleinstes Element von K. Seien K und H Elemente von P/ker(p), so daß es ein Element y von ↑ K ∩ H gibt. Dann ist Min(K) = p(Min(K)) ≤ p(y) = Min(H). Das Ungleichheitszeichen steht wegen der Monotonie von p.

‘φ antiton’: Seien p, q Elemente von Q_{P}, so das p ≤ q. Seien x, y aus P, so daß q(x) = q(y). Dann ist p(x) = p ∘ q(x) = p ∘ q(y) = p(y).

‘ψ wohldefiniert’: Sei R aus P roker(P). Sei x aus P.

Dann ist ψ(R)(x) = Min[x]R ≤ x,

und ψ(R) ∘ ψ(R)(x) = Min[Min[x]R]R = Min[x]R = ψ(R)(x).

Sei nun y aus P, so daß x ≤ y. Weil R die Bedingung (ii) erfüllt, ist dann ψ(R)(x) ≤ ψ(R)(y).

‘ψ antiton’: Seien R, S aus P roker(P), so daß R eine Teilmenge von S ist. Dann ist P/R eine feinere Partition als P/S. Also ist im(ψ(S)) = {MinK | K ∈ P/S} ⊆ {MinH | H ∈ P/R} =

im(ψ(R)).

‘φ ∘ ψ = id_{P roker(P)}’: Sei R ∈ P roker(P). Sei (x, y) ∈ R. Dann ist ψ(R)(x) = Min[x]R = Min[y]R = ψ(R)(y), also (x, y) ∈ kerψ(R) = φ ∘ ψ(R). Sei (x, y) ∈ kerψ(R). Das heißt Min[x]R = Min[y]R. Dann ist [x]R ∩ [y]R nichtleer. Also

[x]R = [y]R, also (x, y) ∈ R.

‘ψ ∘ φ = id_{Q_{P}} ’: Seien p ∈ Q_{P} und x ∈ P.

Es ist (ψ ∘ φ(p))(x) = ψ(ker(p))(x) = Min[x]ker(p).

Einerseits ist Min[x]ker(p) = Min[p(x)]ker(p) ≤ p(x), wobei wir die Idempotenz von p benutzt haben. Andererseits ist p(x) = p(Min[x]ker(p)) ≤ Min[x]ker(p), wobei wir benutzt haben, daß p kleiner ist als die Identität. Für alle x aus P ist also ψ ∘ φ(p)(x) = p(x). Also ist ψ ∘ φ(p) = p.

Definition 6.7 Sei P eine geordnete Menge, und sei p ein Element von Q_{P}. Die Relation Θ_{p} auf P sei definiert durch

(x, y) ∈ Θ_{p} ⇔^{def} ∃z ∈ P. (z ∨ p(x) = x und z ∨ p(y) = y)

Proposition 6.5 Sei P eine beschränkt vollständige geordnete Menge, und sei p ∈ Q_{P}, so daß Θ_{p} ∈ P rokerP. Dann existiert id/p und ist bestimmt durch ker(id/p) = Θ_{p}.

Beweis: Wir zeigen zunächst, daß die Identität auf P das punktweise Supremum von p und ψ(Θ_{p}) ist: Sei also x ein Element von P. Nach Definition von Θ_{p} gibt es ein z ∈ P, so daß x = p(x) ∨ z und Min[x]Θ_{p} = p(Min[x]Θ_{p}) ∨ z. Aus der zweiten dieser Gleichungen folgt, daß z ≤ Min[x]Θ_{p}. Da außerdem Min[x]Θ_{p} ≤ x, ist also x = p(x) ∨ z = p(x) ∨ Min[x]Θ_{p} = p(x) ∨ ψ(Θ_{p})(x). Sei nun r ∈ Q_{p}, so daß p ∨ r = id. Sei x ∈ P. Da P beschränkt vollständig ist, werden Suprema in Q_{P} punktweise gebildet, und es ist x = r(x) ∨ p(x). Weiterhin ist r(x) = r(x) ∨ p ∘ r(x). Also ist (x, r(x)) ∈ Θ_{p}, also r(x) ≥ Min[x]Θ_{p} = ψ(R)(x).

Umgekehrt folgt aus der Existenz von id/p noch nicht, daß Θ_{p} = ker(id/p). Zum Beispiel:

Θ_{p} ist nicht transitiv, denn (a, ⊤) und (⊤, b) sind Elemente von Θ_{p}, nicht jedoch (a, b).

Wir haben nun ein Werkzeug, um die Halbfaktorprojektionen einer geordneten Menge mit kleinstem Element zu charakterisieren. Man beachte, daß die folgende Charakterisierung für beliebige geordnete Mengen mit kleinstem Element, und nicht nur für beschränkt vollständige Mengen, gilt.

Proposition 6.6 Sei P eine geordnete Menge mit kleinstem Element und p ein Element von Q_{P}. Dann ist p eine Halbfaktorprojektion, genau dann wenn p die folgenden Eigenschaften hat:

(i) Θ_{p} ∈ P roker(P)

(ii) ∀x ∈ im(p).∀y ∈ P. [(p(y) ≤ x) ⇒ (x ∨ y existiert)]

(iii) ∀x ∈ im(p).∀y ∈ P. [(p(y) ≤ x) ⇒ (p(x ∨ y) = x)]

Beweis:

‘nur dann wenn’: (i) Bezeichne q die Kohalbfaktorprojektion zu p. Wir zeigen, daß Θ_{p} = ker(q). Sei (x, y) ∈ ker(q). Das heißt q(x) = q(y). Setzen wir z = q(x). Da das punktweise Supremum einer Halbfaktorprojektion und der zugehörigen Kohalbfaktorprojektion gleich der Identität ist, sind x = p(x) ∨ q(x) = p(x) ∨ z und y = p(y) ∨ q(y) = p(y) ∨ z. Also ist (x, y) ∈ Θ_{p}. Seien (x, y) ∈ Θ_{p}. Das heißt es gibt ein z ∈ P, so daß p(x) ∨ z = x und p(y) ∨ z = y. Es ist x = p(x) ∨ z = p(x) ∨ p(z) ∨ q(z) = p(x) ∨ q(z). Weil {p, q} Eigenschaft (iii) aus Proposition 3.4 hat, ist q(p(x) ∨ q(z)) = q(z). Also ist q(x) = q(z). Genauso ist q(y) = q(z). Also ist (x, y) ∈ ker(p).

Daß p Eigenschaften (ii) und (iii) hat, zeigt man genau wie in Proposition 6.3.

‘wenn’: Wir müssen zeigen, daß {p, ψ(Θ_{p})} die Bedingungen aus Proposition 3.4 erfüllt. Bedingungen (ii) und (iii) aus Proposition 3.4 sind schwächer als Bedingungen (ii) und (iii) aus dieser Proposition. Daß die Identität punktweises Supremum von p und ψ(Θ_{p}) ist, zeigt man genau wie in Proposition 6.5.

6.3 Der Verband der Halbfaktoren eines dI-Bereiches ist ein vollständiger Unterverband des Verbandes aller Projektionsbilder

Die in Proposition 6.6 gegebebene Charakterisierung der Halbfaktoren vereinfacht sich in dI-Bereichen. Schauen wir uns zunächst die Θ_{p}-Relation einer stabilen Projektion eines dI-Bereiches an.

Definition 6.8 Sei P eine beschränkt vollständige geordnete Menge, und sei Θ eine Relation auf P. Wir nennen Θ sup-verträglich, falls für jede beschränkte Teilmenge M von Θ auch ⋁ M ein Element von Θ ist. Θ heiße inf-verträglich, falls ⋀ M ein Element von Θ ist für jede nichtleere Teilmenge M von Θ.

Proposition 6.7 a) Sei P eine beschränkt vollständige geordnete Menge, und sei p ein Projektion von P. Dann ist Θ_{p} sup-verträglich.

b) Sei P eine distributive beschränkt vollständige Menge, und sei p eine stabile Projektion von P. Dann ist Θ_{p} eine Äquivalenzrelation.

c) Sei P eine beschränkt vollständige geordnete Menge, in der das folgende Distributivgesetz gilt:

∀x ∈ P. ∀{E_{i} | i ∈ I} ⊆ P^{fin}(↓ x). ⋀_{i∈I} ⋁ E_{i} = ⋁ {⋀_{i∈I} f_{i} | f ∈ ∏_{i∈I} E_{i}}

Sei p eine stabile Projektion von P. Dann ist Θ_{p} inf-verträglich.

Beweis:

a) Sei M eine beschränkte Teilmenge von Θ_{p}. Dann gibt es für alle m aus M ein z_{m} ∈ P, so daß p_{1}(m) = z_{m} ∨ p ∘ p_{1}(m) und p_{2}(m) = z_{m} ∨ p ∘ p_{2}(m). Da P beschränkt vollständig ist, existiert das Supremum von {z_{m} | m ∈ M}. Es ist

⋁ p_{1}(M) = ⋁_{m∈M}(z_{m} ∨ p ∘ p_{1}(m)) = ⋁ z_{M} ∨ ⋁ p ∘ p_{1}(M) = ⋁ z_{M} ∨ p(⋁ p_{1}(M)).

Das letzte Gleichheitszeichen steht, weil ⋁ p ∘ p_{1}(M) ≤ p(⋁ p_{1}(M)) ≤ ⋁ p_{1}(M). Genauso ist ⋁ p_{2}(M) = ⋁ z_{M} ∨ p(⋁ p_{2}(M)).

b) An der Definition von Θ_{p} sieht man, daß Θ_{p} immer reflexiv und symmetrisch ist. Wir brauchen also nur noch die Transitivität zu zeigen. Zunächst zeigen wir, daß in einer distributiven beschränkt vollständigen Menge die folgende Rechenregel gilt: Ist {x, u, v} eine beschränkte Teilmenge von P und ist x∨u = x∨v, so ist u = (u∧x)∨(u∧v). Aus x ∨ u = x ∨ v folgt nämlich, daß

x ∨ u = (x ∨ u) ∧ (x ∨ v) = x ∨ (u ∧ v).

Unter Verwendung dieser Gleichung erhalten wir, daß

u = (x ∨ u) ∧ u = (x ∨ (u ∧ v)) ∧ u = (x ∧ v) ∨ (u ∧ v).

Seien nun (x, y) ∈ Θ_{p} und (y, z) ∈ Θ_{p}. Das heißt es gibt Elemente u und v von P, so daß x = p(x) ∨ u, y = p(y) ∨ u = p(y) ∨ v und z = p(z) ∨ v. Mit der Rechenregel folgt u = (u ∧ p(y)) ∨ (u ∧ v). Dann ist x = p(x)∨u = p(x)∨(u∧p(y))∨(u∧v) = p(x)∨(u∧v). Das letzte Gleichheitszeichen steht, weil u ∧ p(y) ∈↓ x∩ ↓ im(p) =↓ x ∩ im(p), also u ∧ p(y) ≤ p(x). Genauso ist y = p(y) ∨ (u ∧ v). c) Sei M eine nichtleere Teilmenge von Θ_{p}. Dann gibt es für alle m aus M ein z_{m} aus P, so daß

p_{1}(m) = z_{m} ∨ p ∘ p_{1}(m) und p_{2}(m) = z_{m} ∨ p ∘ p_{2}(m). Es ist

⋀ p_{1}(M) = ⋀(z_{m} ∨ p ∘ p_{1}(m))
= ⋁ {⋀_{m∈M} f_{m} | f ∈ ∏_{m∈M}{z_{m}, p ∘ p_{1}(m)}}
= p(⋀ p_{1}(M)) ∨ ⋀ z_{M}

Das letzte Gleichheitszeichen steht, weil das Infimum jedes von (z_{m})_{m∈M} verschiedenen Elementes von ∏_{m∈M}{z_{m}, p ∘ p_{1}(m)} ein Element von ↓ im(p)∩ ↓ ⋀ p_{1}(M) = im(p)∩ ↓ ⋀ p_{1}(M) ist. Als solches ist es kleiner als p(⋀ p_{1}(M)). Genauso ist ⋀ p_{2}(M) = p(⋀ p_{2}(M)) ∨ ⋀ z_{M}.

Proposition 6.8 In einem dI-Bereich gilt das Distributivgesetz aus Proposition 6.7 c).

Beweis: Wir benutzen, daß in einem stetigen Verband das folgende Distributivgesetz gilt: Ist (M_{i})_{i∈I} eine Familie von gerichteten Teilmengen des Verbandes, so ist

⋀_{i∈I} ⋁ ^{↑}M_{i} = ⋁ ^{↑}{⋀_{i∈I} f_{i} | f ∈ ∏_{i∈I} M_{i}} (∗)

Sei D ein dI-Bereich, und sei x ein Element von D. Sei zunächst (E_{i})_{i∈I} eine Familie von endlichen Teilmengen von ↓ x ∩ K(D). Sicher ist

⋀_{i∈I} ⋁ E_{i} ≥ ⋁ {⋀_{i∈I} f_{i} | f ∈ ∏_{i∈I} E_{i}}

Für jedes i ∈ I ist ⋁ E_{i} kompakt. Da D endlich algebraisch ist, ist dann der von ⋁ E_{i} erzeugte Hauptanfang endlich. Also ist auch ↓ ⋀_{i∈I} ⋁ E_{i} endlich. Es gibt also eine endliche Teilmenge F von I, so daß

⋁ {⋀_{i∈F} f_{i} | f ∈ ∏_{i∈F} E_{i}} = ⋁ {⋀_{i∈I} f_{i} | f ∈ ∏_{i∈I} E_{i}}

Weil D distributiv ist, ist

⋁ {⋀_{i∈F} f_{i} | f ∈ ∏_{i∈F} E_{i}} = ⋀_{i∈F} ⋁ E_{i}

Mit den beiden letzten Gleichungen erhalten wir also

⋁ {⋀_{i∈I} f_{i} | f ∈ ∏_{i∈I} E_{i}} = ⋀_{i∈F} ⋁ E_{i} ≥ ⋀_{i∈I} ⋁ E_{i}

Sei nun (E_{i})_{i∈I} eine beliebige Familie von endlichen Teilmengen von ↓ x. Es ist

⋁ {⋀_{i∈I} f_{i} | f ∈ ∏_{i∈I} E_{i}} = ⋁ {⋀_{i∈I} ⋁ ^{↑}K_{f_{i}} | f ∈ ∏_{i∈I} E_{i}}
= ⋁ {⋁ ^{↑}{⋀_{i∈I} g_{i} | g ∈ ∏_{i∈I} K_{f_{i}}} | f ∈ ∏_{i∈I} E_{i}}
= ⋁ {⋀_{i∈I} g_{i} | g ∈ ∏_{i∈I} K(D)∩ ↓ E_{i}}
= ⋁ ^{↑}{⋁ {⋀_{i∈I} g_{i} | g ∈ ∏_{i∈I} F_{i}} | F ∈ ∏_{i∈I} P^{fin}(K(D)∩ ↓ E_{i})}
= ⋁ ^{↑}{⋀_{i∈I} ⋁ F_{i} | F ∈ ∏_{i∈I} P^{fin}(K(D)∩ ↓ E_{i})}
= ⋀_{i∈I} ⋁ ^{↑}{⋁ F_{i} | F_{i} ∈ P^{fin}(K(D)∩ ↓ E_{i})}
= ⋀_{i∈I} ⋁(K(D)∩ ↓ E_{i})
= ⋀_{i∈I} ⋁ E_{i}

Die zweite und die sechste Gleichung der Gleichungskette gelten wegen (∗). Die fünfte gilt, weil F_{i} eine endliche Menge von kompakten Elementen ist für jedes i ∈ I.

Die dritte Bedingung der Halbfaktorcharakterisierung aus Proposition 6.6 fordert, daß eine Halbfaktorprojektion bestimmte Suprema erhält. In distributiven, stetigen Bereichen erhält jede stabile Projektion beliebige Suprema:

Proposition 6.9

a) Ist D ein stetiger, beschränkt vollständiger Bereich, und ist p eine stabile Projektion von D, so ist p stetig.

b) Ist D ein stetiger,distributiver beschränkt vollständiger Bereich, und ist p eine stabile Projektion von D, so erhält p Suprema.

Beweis:

a) Sei A eine gerichtete Teilmenge von D. Da p stabil ist, ist p(a) = a ∧ p(⋁ ^{↑}A) für jedes a ∈ A. Es ist

⋁ ^{↑}p(A) = ⋁ _{a∈A}^{↑}(a ∧ p(⋁ ^{↑}A)) = ⋁ ^{↑}A ∧ p(⋁ ^{↑}A) = p(⋁ ^{↑}A)

Die dritte Gleichung der Gleichungskette gilt, weil D schnittstetig ist.

b) Nach a) erhält p gerichtete Suprema. Bleibt zu zeigen, daß p endlich Suprema erhält. Das zeigt man analog zum Beweis von a) unter Verwendung der Distributivität.

Wir können nun die Halbfaktoren eines dI-Bereiches einfach charakterisieren:

Proposition 6.10 Sei D ein dI-Bereich, und sei p : D → D eine Projektion . Dann ist p eine Halbfaktorprojektion, genau dann wenn p stabil ist und die Slide-Bedingung erfüllt.

Beweis:

‘nur dann wenn’: nach Proposition 6.2 und 6.3.

‘wenn’: Wir müssen zeigen, daß p Bedingungen (i) und (iii) aus Proposition 6.6 erfüllt. Bedingung (iii) ist erfüllt, weil p nach Proposition 6.3 Suprema erhält. Bleibt zu zeigen, daß Θ_{p} ein Projektionskern ist. Nach Propositionen 6.7 und 6.8 ist Θ_{p} eine Äquivalenzrelation und inf-verträglich. Wegen der inf-Verträglichkeit ist ⋀ K ∈ K für alle K ∈ D/Θ_{p}. Das heißt, ⋀ K ist kleinstes Element von K. Seien nun K, H ∈ D/Θ_{p}, so daß ↑ K ∩ H nichtleer ist. Es gibt also Elemente k von K und h von ↑ k ∩ H. Es ist (k, MinK ∧ MinH) = (k ∧ h, MinK ∧ MinH). Da Θ_{P} inf-verträglich ist, ist (k, MinK ∧ MinH) also ein Element von Θ_{p}. Also ist MinK ∧ MinH ∈ K, also MinK ∧ MinH = MinK, also MinK ≤ MinH.

Satz 6.2 Sei D ein dI-Bereich.

a) Der Verband H_{D} der Halbfaktorprojektionen von D ist ein vollständiger Unterverband des Verbandes Q_{D} aller internen Projektionen von D.

b) A ist vollständig verbundirreduzibel in H̃_{D}, genau dann wenn A die Hülle eines vollständig verbundirreduziblen Elementes von D ist, wenn also A = ⋂ {B ∈ H̃_{D} | x ∈ B} für ein vollständig verbundirreduzibles Element x von D.

c) Die Menge J(H_{D}) der vollständig verbundirreduziblen Elemente von H_{D} bildet eine Basis von H_{D}.

Beweis:

‘Suprema von Halbfaktorprojektionen sind Halbfaktorprojektionen’: In einem stetigen, distributiven Bereich ist ein elementweises Supremum von Anfangsstücken wieder ein Anfangsstück. Ein Supremum von stabilen Projektionen ist also stabil. Wir müssen noch zeigen, daß ein Supremum von Halbfaktorprojektionen die Slide-Bedingung erfüllt. Für endliche Teilmengen von H_{D} zeigen wir das per Induktion. Nehmen wir also an für jede Teilmenge E von H_{D} mit weniger als n Elementen erfülle ⋁ E die Slide-Bedingung. Seien p_{1}, .., p_{n} ∈ H_{D}. Seien x ∈ D und y ∈ im(⋁_{i=1}^{n} p_{i}), so daß ⋁_{i=1}^{n} p_{i}(x) ≤ y. Dann ist (⋁_{i=1}^{n−1} p_{i})(x) = (⋁_{i=1}^{n−1} p_{i}) ∘ (⋁_{i=1}^{n} p_{i})(x) ≤ ⋁_{i=1}^{n−1} p_{i}(y). Genauso ist p_{n}(x) ≤ p_{n}(y). Da ⋁_{i=1}^{n−1} p_{i} nach Induktionsannahme die Slide-Bedingung erfüllt, existiert x ∨ ⋁_{i=1}^{n−1} p_{i}(y). Es ist p_{n}(x ∨ ⋁_{i=1}^{n−1}(y)) = p_{n}(x) ∨ p_{n} ∘ (⋁_{i=1}^{n−1} p_{i})(y) ≤ p_{n}(y). Mit der Slide-Bedingung für p_{n} erhält man die Existenz von x ∨ y. Sei nun (p_{i})_{i∈I} eine beliebige Familie von Halbfaktorprojektionen. Seien x ∈ D und y ∈ im(⋁_{i∈I} p_{i}), so daß (⋁_{i∈I} p_{i})(x) ≤ y. Für jede endliche Teilmenge E von I ist dann (⋁_{i∈E} p_{i})(x) ≤ ⋁_{i∈E} p_{i}(y). Wie wir gezeigt haben, existiert dann x ∨ ⋁_{i∈E} p_{i}(y). Da D ein Bereich ist, existiert dann auch ⋁ ^{↑}{x ∨ ⋁_{i∈E} p_{i}(y) | E ∈ P^{fin}(I)} = x∨⋁_{i∈I} p_{i}(y) = x ∨ y.

‘Infima von Halbfaktorprojektionen sind Halbfaktorprojektionen ’: Da D beschränkt vollständig ist, ist das Infimum in Q̃_{D} der Mengenschnitt. Ein Durchschnitt von Anfangsstücken ist sicher ein Anfangsstück. Also ist ein Infimum von stabilen Projektionen stabil. Zur Slide-Bedingung: Sei (p_{i})_{i∈I} eine Familie von Halbfaktorprojektionen. Seien zunächst k ∈ K(D) und y ∈ im(⋀_{i∈I} p_{i}), so daß (⋀_{i∈I} p_{i})(k) ≤ y. Da ↓ k endlich ist, gibt es eine endliche Teilmenge E von I, so daß (⋀_{i∈I} p_{i})(k) = ⋁(⋂_{i∈I} im(p_{i})∩ ↓ k) = ⋁(⋂_{i∈E} im(p_{i})∩ ↓ k) = (⋀_{i∈E} p_{i})(k). Sagen wir E = i_{1}, .., i_{n}. Da p_{i_{1}}, .., p_{i_{n}} stabil sind, ist ⋀_{i∈E} p_{i} = p_{i_{1}} ∘ .. ∘ p_{i_{n}}. Aus p_{i_{1}} ∘ .. ∘ p_{i_{n}}(k) ≤ y folgt durch sukzessives Anwenden der Slide-Bedingung auf p_{i_{1}}, .., p_{i_{n}} die Existenz von k ∨ y. Sei nun x eine beliebiges Element von D, und sei y ein Element von im(⋀_{i∈I} p_{i}), so daß (⋀_{i∈I} p_{i})(x) ≤ y. Dann ist (⋀_{i∈I} p_{i})(k) ≤ y für alle k ∈ K_{x}. Also existiert k ∨ y für alle k ∈ K_{x}. Da D ein Bereich ist, existiert dann auch ⋁ ^{↑}(K_{x} ∨ y) = ⋁ ^{↑}K_{x} ∨ y = x ∨ y.

b) und c) folgert man leicht daraus, daß Suprema in H̃_{D} elementweise gebildet werden, und daß die vollständig verbundirreduziblen Elemente von D eine Basis bilden,

Der Halbfaktorenverband eines dI-Bereiches muß nicht endlich algebraisch sein. Betrachten wir zum Beispiel das folgende Diagramm D : IN_{⊥} → DCP O:

D(⊥) = IN_{⊥}

D(n) = {⊥, ⊤} für alle n ∈ IN

D(n ← ⊥)(x) = \{ \begin{matrix}⊤ & falls x = n \\ ⊥ & sonst \end{matrix}

Nach Satz 5.2 ist hypD ein dI-Bereich. Bezeichne

H := {∏_{n∈M} D(n) × ∏_{n∈IN\M}{⊥} × {⊥} | M ⊆ IN}

Jedes Element von H ist elementweises Supremum eingebettetter Hyperlimesfaktoren, ist also ein Halbfaktor von hypD. Wir behaupten,daß durch H∪{hypD} bereits der gesamte Halbfaktorverband von hypD gegeben ist. Dieser Verband ist nicht endlich algebraisch, denn er hat unendlich viele Elemente, sein größtes Element ist aber kompakt. Sei A ein Halbfaktor von hypD, welcher nicht Element von H ist. Da ∏_{n∈IN} D(n) × {⊥} kein Supabgeschlossenen Anfangsstück hat, das nicht schon Element von H ist, ist A eine echte Obermenge von ∏_{n∈IN} D(n) × ⊥. Für jedes n ∈ IN definieren wir ein y_{n} ∈ hypD durch

p_{i}(y_{n}) := \{ \begin{matrix}n & falls i = ⊥ \\ ⊤ & falls i = n \\ ⊥ & sonst. \end{matrix}

Da A ein Anfangsstück ist gibt es ein n ∈ IN mit y_{n} ∈ A. Angenommen A sei ungleich hypD. Wegen ⋁_{n∈IN} ↓ y_{n} = hypD gäbe es dann auch ein m ∈ IN mit y_{m} ∉ A. Sei nun z ∈ hypD definiert durch

p_{i}(z) := \{ \begin{matrix}n & falls i = ⊥ \\ ⊤ & falls i ∈ \{n, m\} \\ ⊥ & sonst. \end{matrix}

Es ist p_{A}(y_{m}) ≤ z ∈ A. Weil A der Slide-Bedingung genügt, müßte dann {y_{m}, z} beschränkt sein. Das ist jedoch nicht der Fall, da {p_{⊥}(y_{m}), p_{⊥}(z)} unbeschränkt ist.

6.4 Der Zerlegungssatz für dI-Bereiche

Zum Beweis des Satzes benötigen wir die folgenden drei Lemmata:

Lemma 6.1 Sei D ein dI-Bereich, und seien p und q stabile Projektionen von D, so daß q ≤ p. Dann existiert p/q, und es ist p/q = id/q ∘ p. Außerdem erhält p/q Suprema.

Beweis: Da p stabil ist, ist id/q ∘ p eine Projektion. Es ist

id/q ∘ p ∨ q = id/q ∘ p ∨ q ∘ p = (id/q ∨ q) ∘ p = id ∘ p = p.

Sei t ∈ Q_{D}, so daß t ∨ q = p. Sei x ∈ D. Es ist p(x) = t(x) ∨ q(x) = t(x) ∨ q ∘ p(x). Andererseits ist t(x) = t(x) ∨ q ∘ t(x). Also ist (p(x), t(x)) ∈ Θ_{q}, und es ist t(x) ≥ Min[p(x)]Θ_{q} = Min[p(x)]ker(id/q) = (id/q) ∘ p(x). id/q ∘ p ist also die kleinste Projektion, deren Supremum mit q gleich p ist. p erhält Suprema, nach Proposition 6.3. ker(id/q) = Θ_{q} ist sup-verträglich, nach Proposition 6.7. Also erhält id/q Suprema. Insgesamt erhält dann p/q = id/q ∘ p Suprema.

Lemma 6.2 Sei D ein dI-Bereich, und seien A, B, C stabile Projektionen von D, so daß B, C ⊆ A. Sei weiterhin x ein Element von D, so daß ↓ x ∩ B =↓ x ∩ C. Dann ist p_{A}/p_{B}(x) = p_{A}/p_{C}(x).

Beweis: Für y ∈↓ x ist p_{B}(y) = p_{B∩↓x}(y). Man überlegt sich leicht, daß dann Θ_{B} ∩ (↓ x)^{2} = Θ_{B∩↓x} ∩ (↓ x)^{2}. Es ist p_{A}/p_{B}(x) = id/p_{B} ∘ p_{A}(x) = Min[p_{A}(x)]Θ_{B} = Min[p_{A}(x)]Θ_{B∩↓x}. Genauso ist p_{A}/p_{C}(x) = Min[p_{A}(x)]Θ_{C∩↓x}

Lemma 6.3 Sei D ein dI-Bereich und sei B eine endliche Menge von Halfaktorprojektionen von D. Für p ∈ B sei p^{↓_{B}} definiert durch

p^{↓_{B}} := ⋁ {q ∈ B | q echt kleiner als p}

Dann:

• ⋁ B = ⋁_{p∈B} p/p^{↓_{B}}

• Ist (x_{p})_{p∈B} ∈ ∏_{p∈B} im(p/p^{↓_{B}}), so daß p/p^{↓_{B}}(x_{q}) ≤ x_{p} für alle p, q ∈ B, so existiert ⋁_{p∈B} x_{p}.

Beweis: Wir zeigen per Induktion, daß die beiden Aussagen für jedes Anfangsstück von B gelten, Nehmen wir also an, wir hätten für jedes Anfangsstück A von B mit weniger als n Elementen bereits bewiesen, daß ⋁ A = ⋁_{p∈A} p/p^{↓_{B}}. Sei nun A ein Anfangsstück mit n Elementen. Sei p ein maximales Element von A. Es ist

⋁ A = ⋁(A \ {p}) ∨ p
= ⋁(A \ {p}) ∨ (p/p^{↓_{B}} ∨ p^{↓_{B}})
= ⋁(A \ {p}) ∨ p/p^{↓_{B}}
= ⋁_{q∈A} q/q^{↓_{B}}

Die vorletzte Gleichung gilt, weil p^{↓_{B}} ≤ (⋁ A \ {p}), und die letzte Gleichung gilt nach Induktionsannahme. Sei nun (x_{p})_{p∈B} ∈ ∏_{p∈B} im(p/p^{↓_{B}}), so daß p/p^{↓_{B}}(x_{q}) ≤ x_{p} für alle p, q ∈ B. Nehmen wir an, für alle Anfangsstücke A von B mit weniger als n Elementen wüßten wir bereits, daß ⋁_{p∈A} x_{p} existiert. Sei nun A ein Anfangsstück mit n Elementen, und sei p ein maximales Element von A. Nach Induktionsannahme existiert ⋁_{q∈A\{p}} x_{q}. Es ist

⋁(A \ {p})(x_{p}) = ⋁_{q∈A\{p}} q/q^{↓_{B}}(x_{p}) ≤ ⋁_{q∈A\{p}} x_{q}

Da ⋁(A \ {p}) die Slide-Bedingung erfüllt, existiert dann auch ⋁_{q∈A} x_{q}.

Satz 6.3 Sei D ein dI-Bereich, und sei M = {p/p^{↓} | p ∈ J(H_{D})}. Dann definiert M eine zykelfreie Darstellung von D, d.h M definiert eine Darstellung und die ∗ − P räordnung auf M ist eine Ordnung.

Beweis: Wir müssen zeigen, daß M die drei Eigenschaften aus Proposition 3.4 hat, und daß die ∗-Präordnung auf M antisymmetrisch ist.

(iii) Nach Lemma 6.1 erhält p/p^{↓} Suprema für alle p ∈ J(H_{D}).

(i) Es ist zu zeigen, daß das punktweise Supremum von {p/p^{↓} | p ∈ J(H_{D})} gleich der Identität ist. Wir bemerken zunächst, daß die vollständig verbundirreduziblen Elemente von D eine Sup-Basis bilden, und daß jedes solche Element einen endlichen Hauptanfang erzeugt. Eine Bezeichnung: Für x ∈ D sei J_{x} :=↓ x ∩ J(D). Wir zeigen nun per Induktion, daß x = ⋁_{p∈J(H_{D})} p/p^{↓}(x) für alle vollständig verbundirreduziblen Elemente x von D. Sei also x ∈ J(D). Angenommen für alle y ∈ J_{x} \ {x} hätten wir bereits gezeigt, daß y = ⋁_{p∈J(H_{D})} p/p^{↓}(y). Bezeichne < x > die H̃_{D}-Hülle von {x}, und bezeichne q die Projektion auf < x >. Nach Satz 6.2 b) ist q ∈ J(H_{D}). Da x vollständig verbundirreduzibel in D ist und da Suprema in H̃_{D} elementweise gebildet werden, ist x nicht in < x >^{↓} enthalten. Also ist q^{↓}(x) echt kleiner als x. Es ist

x = q(x) = q^{↓}(x) ∨ q/q^{↓}(x)
= ⋁ J_{q^{↓}(x)} ∨ q/q^{↓}(x)
= ⋁ {{⋁ p/p^{↓}(y) | p ∈ J(H_{D})} | y ∈ J_{q^{↓}(x)}} ∨ q/q^{↓}(x)
≤ ⋁_{p∈J(H_{D})} p/p^{↓}(x) ≤ x

Die vierte Gleichung gilt nach Induktionsannahme. Sei nun x ein beliebiges Element von D. Dann ist

x = ⋁ J_{x} = ⋁_{y∈J_{x}} ⋁_{p∈J(H_{D})} p/p^{↓}(y) ≤ ⋁_{p∈J(H_{D})} p/p^{↓}(x) ≤ x

(ii) Sei (x_{p})_{p∈J(H_{D})} ∈ ∏_{p∈J(H_{D})} im(p/p^{↓}), so daß p/p^{↓}(x_{q}) ≤ x_{p} für alle p, q ∈ J(H_{D}). Zu zeigen ist, daß {x_{p} | p ∈ J(H_{D})} ein Supremum hat. Wir zeigen zunächst, daß für jede endliche Teilmenge F von J(H_{D}) und jede Familie (k_{p})_{p∈F} ∈ ∏_{p∈F} K_{x_{p}} ∩ im(p/p^{↓}) das Supremum von {k_{p} | p ∈ F } existiert. Wir werden dazu Lemma 6.3 verwenden. Wir betrachten eine endliche Teilmenge B von H_{D}, nämlich

B̃ := {< x > | x ∈ J(D) ∩ ⋃_{p∈F} ↓ k_{p}}
B := {p_{A} | A ∈ B̃}

Weiterhin bezeichne für A ∈ B̃ und für p ∈ B:

A^{↓B̃} := ⋁ {C ∈ B̃ | C echt kleiner als A}
p^{↓_{B}} := ⋁ {q ∈ B | q echt kleiner als p}

Wir behaupten zunächst folgendes: ‘F ür < x >∈ B̃ und p ∈ F ist < x >^{↓B̃}∩ ↓ k_{p} = < x >^{↓}∩ ↓ k_{p}’ Beweis dieser Behauptung: Es sind

< x >^{↓B̃} = ⋁ {A ∈ B̃ | A echte T eilmenge von < x >}
< x >^{↓} = ⋁ {A ∈ H̃_{D} | A echte T eilmenge von < x >}

Da B̃ eine Teilmenge von H̃_{D} ist, ist sicher < x >^{↓B̃}∩ ↓ k_{p} ⊆ < x >^{↓}∩ ↓ k_{p}. Sei nun umgekehrt z ∈ < x >^{↓}∩ ↓ k_{p}. Es ist z = ⋁ J_{z}, also z ∈ ⋁ {< y > | y ∈ J_{z}}. Da < x >^{↓} ein Anfangsstück ist, ist y ∈ < x >^{↓} für jedes y ∈ J_{z}. Also ist < y > eine Teilmenge von < x >^{↓}, das wiederum eine echte Teilmenge von < x > ist. Da y ≤ z ≤ k_{p} ist < y > auch ein Element von B̃. Somit haben wir

z ∈ ⋁ {< y > | y ∈ J_{z}}
⊆ ⋁ {A ∈ B̃ | A echte T eilmenge von < x >} = < x >^{↓B̃}

Mit der eben bewiesenen Behauptung und mit Lemma 6.2 erhalten wir nun, daß

q/q^{↓_{B}}(k_{p}) = q/q^{↓_{(}}k_{p}) für alle p ∈ F und alle q ∈ B.

Wir definieren nun ein Element (z_{q})_{q∈B} von ∏_{q∈B} im(q/q^{↓_{B}}) durch

z_{q} := ⋁_{p∈F} q/q^{↓}(k_{p}).

Diese Suprema existieren, weil x_{q} eine obere Schranke von {q/q^{↓}(k_{p}) | p ∈ F } ist. Für jedes q ∈ B ist z_{q} ein Element von im(q/q^{↓_{B}}), weil q/q^{↓_{B}}(k_{p}) = q/q^{↓}(k_{p}) für alle p ∈ F und weil Bilder von Projektionen abgeschlossen sind gegen Suprema. Seien nun r, q ∈ B. Es ist

r/r^{↓_{B}}(z_{q}) = r/r^{↓_{B}}( ⋁_{p∈F} q/q^{↓}(k_{p}))
= ⋁_{p∈F} r/r^{↓_{B}} ∘ q/q^{↓}(k_{p})
≤ ⋁_{p∈F} r/r^{↓_{B}}(k_{p})
= ⋁_{p∈F} r/r^{↓}(k_{p})
= z_{r}

Die zweite Gleichung gilt, weil r/r^{↓_{B}} Suprema erhält, nach Lemma 6.1. Nach Lemma 6.3 existiert nun ⋁_{q∈B} z_{q}. Außerdem ist für jedes p ∈ F

⋁_{q∈B} z_{q} ≥ ⋁_{q∈B} q/q^{↓}(k_{p}) = (⋁ B)(k_{p}) = k_{p}

Das erste Gleichheitszeichen steht wegen Lemma 6.3. Das zweite Gleichheitszeichen steht, weil k_{p} ∈ ⋁ B̃. Es ist also ⋁_{q∈B} z_{q} = ⋁_{p∈F} k_{p}.

Bezeichne nun

M := {⋁_{p∈F} k_{p} | F ∈ P^{fin}(J(H_{D})), ∀p ∈ F. k_{p} ∈ K_{x_{p}} ∩ im(p/p^{↓})}

Da K_{x_{p}} ∩ im(p/p^{↓}) gerichtet ist für jedes p ∈ J(H_{D}), ist auch M gerichtet.

Da D ein Bereich ist, existiert dann das Supremum von M.

Für jedes p ∈ J(H_{D}) ist x_{p} = p/p^{↓}(x_{p}) = p/p^{↓}(⋁ ^{↑}K_{x_{p}}) = ⋁ ^{↑}p/p^{↓}(K_{x_{p}}). Da D endlich algebraisch ist, ist p/p^{↓_{(}}K_{x_{p}}) ⊆ K_{x_{p}}. Es ist also x_{p} ≤ ⋁ ^{↑}M für alle p ∈ J(H_{D}). Also ist ⋁ ^{↑}M = ⋁_{p∈J(H_{D})} x_{p}.

Wir haben damit gezeigt, daß M eine Darstellung von D definiert. Bleibt zu zeigen, daß die ∗-Präordnung auf M antisymmetrisch ist: Seien zunächst p, r ∈ J(H_{D}), so daß r echt kleiner ist als p. Dann ist

p/p^{↓} ∘ r = id/p^{↓} ∘ p ∘ r = id/p^{↓} ∘ r ≤ id/p^{↓} ∘ p^{↓} = ⊥

Die erste Gleichung der Gleichungskette gilt nach Lemma 6.1, die zweite gilt, weil r kleiner ist als p, die Ungleichung gilt, weil r kleiner ist als p^{↓},und die letzte Gleichung gilt, weil p^{↓} eine Halbfaktorprojektion ist. Seien nun p, q ∈ J(H_{D}), so daß p ≰ q. Dann ist

p/p^{↓} ∘ q/q^{↓} ≤ p/p^{↓} ∘ q = p/p^{↓} ∘ p ∘ q
= p/p^{↓} ∘ (p ∧ q)
= p/p^{↓} ∘ (⋁ {r ∈ J(H_{D}) | r ≤ p ∧ q})
= ⋁ {p/p^{↓} ∘ r | r ≤ p ∧ q}
= ⊥

Die zweite Gleichung der Gleichungskette gilt, weil p und q stabil sind. Die vierte Gleichung gilt, weil J(H_{D}) eine Basis von H_{D} ist, nach Satz 6.2 c). Die letzte Gleichung gilt, weil r ≤ p ∧ q < r, und somit p/p^{↓} ∘ r = ⊥, wie wir gerade festgestellt haben. Wir haben damit gezeigt, daß für p, q ∈ J(H_{D}) die folgende Implikation gilt:

p ≰ q ⇒ p/p^{↓} ∘ q/q^{↓} = ⊥

Diese Implikation ist aber äquivalent zu

{(q/q^{↓}, p/p^{↓}) | p/p^{↓} ∘ q/q^{↓} ≠ ⊥} ⊆ {(q/q^{↓}, p/p^{↓}) | p ≤ q}

Die rechte Seite dieser Ungleichung ist eine Ordnung. Die ∗-Präordnung ist die reflexive und transitive Hülle der linken Seite, ist also in der rechten Seite enthalten, ist also eine Ordnung.

6.5 Die Faktoren der dI-Bereichs-Zerlegung sind irreduzibel

Definition 6.9 Eine Darstellung (P, p) in einer Unterkategorie C von P OSET heiße Zerlegung von P, falls keine Projektion injektiv ist. Ein Objekt P von C heiße irreduzibel in C, falls es keine Zerlegung von P in C gibt. P heiße zykelfrei irreduzibel in C, falls es keine Zerlegung über einem zykelfreien Diagramm in C gibt. P heiße einfach irreduzibel, falls es keine Zerlegung über einem einfachen Diagramm in C gibt.

Proposition 6.11 Sei P ein geordnete Menge mit kleinstem Element, (P, p) eine zykelfreie Darstellung über dem Diagramm D : I → P OSET, und i ein Objekt der Indexkategorie. Dann sind äquivalent:

(1) p_{i} ist injektiv.

(2) Für alle von i verschiedenen Objekte j der Indexkategorie ist D(j) einelementig.

Beweis: Die Implikation von (2) nach (1) ist offensichtlich. Zur Implikation von (1) nach (2): Sei j ∈ Ob(I) \ {i} und x ∈ D(i). Falls [i → j] leer ist: Da p_{j} surjektiv ist, gibt es ein y ∈ P, so daß p_{j}(y) = x. Wir definieren ein weiteres Element z von P durch

p_{k}(z) := \{ \begin{matrix}p_{k}(y) & falls [i → k] ≠ ∅ \\ ⊥ & sonst \end{matrix}

Es ist p_{i}(y) = p_{i}(z). Weil p_{i} injektiv ist, ist also y = z. Insbesondere ist also x = p_{j}(y) = p_{j}(z) = ⊥. Falls [i → j] nichtleer ist: Da p_{j} surjektiv ist, gibt es ein y ∈ P, so daß p_{j}(y) = x. Wir definieren ein weiteres Element von P durch

p_{k}(z) := \{ \begin{matrix}p_{k}(y) & falls [j → k] ≠ ∅ \\ ⊥ & sonst \end{matrix}

Da I zykelfrei ist, ist [j → i] leer. Also ist p_{i}(z) = ⊥ = p_{i}(⊥). Da p_{i} injektiv ist, ist dann z = ⊥, also insbesondere x = p_{j}(y) = p_{j}(z) = p_{j}(⊥) = ⊥.

Proposition 6.12 Sei P eine beschränkt vollständige geordnete Menge. Dann sind äquivalent:

(1) P ist zykelfrei, einfach irreduzibel in P OSET.

(2) P ist zykelfrei irreduzibel in BC.

(3) Die Identität und die konstante Abbildung auf das kleinste Element sind die einzigen Halbfaktorprojektionen von P.

Setzen wir zusätzlich voraus, daß P endlich algebraisch ist, so ist auch noch die folgende Eigenschaft äquivalent zu (1) bis (3):

(4) P ist zykelfrei irreduzibel in DCP O.

Beweis:

‘(1) ⇒ (2)’: Sei (P, p) eine zykelfreie Darstellung über D : I → BC. Nach Proposition 3.8 sind die Hyperlimesprojektionen obere Adjungierte. (P, p) ist also ein Hyperlimeskegel über dem zykelfreien, einfachen Diagramm D̃_{||I|} aus Proposition 3.2 a). Da P als zykelfrei, einfach irreduzibel in P OSET vorausgesetzt ist, gibt es ein Objekt i der Indexkategorie, so daß p_{i} injektiv ist.

‘(2) ⇒ (1)’: Sei (P, p) eine zykelfreie, einfache Darstellung über D : I → P OSET. Nach Proposition 5.4 haben sämtlich Objekte von D ein kleinstes Element, und sämtliche verbindenden Morphismen erhalten das kleinste Element. Nach Folgerung 3.4 sind die Hyperlimesprojektionen also obere Adjungierte. Die Objekte von D sind dann Bilder einer beschränkt vollständigen geordneten Menge unter einer oberen Adjungierten, sind also beschränkt vollständig. Da P als zykelfrei irreduzibel in BC vorausgesetzt ist, gibt es dann ein Objekt i der Indexkategorie, so daß p_{i} injektiv ist.

‘(2) ⇒ (3)’: Sei (p, q) ein Halbfaktor-Kohalbfaktorprojektionspaar von P. Da P zykelfrei irreduzibel in BC ist, ist entweder p injektiv oder q. Falls p injektiv ist, folgt mit der Idempotenz von p, daß p die Identität ist. Falls q injektiv ist, so ist das Bild von p, nach Proposition 6.11, einelementig. Also ist p = ⊥.

‘(3) ⇒ (2)’: Sei (P, p) eine zykelfreie Darstellung über D : I → BC. Nach Proposition 3.8 hat jede Hyperlimesprojektion p_{i} eine untere Adjungierte e_{i}. Bezeichne M die Menge {e_{i} ∘ p_{i} | i ∈ Ob(I)}. Weil das Diagramm D zykelfrei ist, ist die ∗-Präordnung auf M eine Ordnung, nach Proposition 3.6 . Angenommen (P, p) sei eine Zerlegung. Wegen Proposition 6.11 gäbe es dann zwei verschiedene Objekte i und j von I, so daß sowohl D(i) wie auch D(j) mindestens zwei Elemente haben. Bezeichne p die Projektion e_{i} ∘ p_{i} und q die Projektion e_{j} ∘ p_{j}. Da p_{i} und p_{j} surjektiv sind, ist das Bild von p isomorph zu D(i) und das Bild von q isomorph zu D(j). Sowohl das Bild von p als auch das Bild von q haben also mindestens zwei Elemente. Also sind p ≠ ⊥ und q ≠ ⊥. Da die ∗-Präordnung auf M eine Ordnung ist, gibt es ein ∗-Endstück U von M, welches p und q trennt, sagen wir p ∈ U und q ∉ U. Nach Satz 6.1 ist (⋁ U, ⋁(M \ U)) ein Halbfaktor-Kohalbfaktorprojektionspaar. Da p ≠ ⊥ und ⋁ U ≥ p, ist ⋁ U ≠ ⊥. Wir haben vorausgesetzt, daß H_{P} = {id, ⊥}. Also ist ⋁ U = id. Dann ist q ≤ ⋁(M \ U) = id/ ⋁ U = id/id = ⊥. Wir hatten aber q so gewählt, daß q ≠ ⊥. Ein Widerspruch.

Sei nun P zusätzlich endlich algebraisch.

‘(1) ⇒ (4)’: Sei (P, p) eine zykelfreie Darstellung über D : I → DCP O. Da P endlich algebraisch ist, hat jede Hyperlimesprojektion über D eine untere Adjungierte, nach Proposition 5.6. (P, p) ist also eine zykelfreie, einfache Darstellung über dem Diagramm aus Proposition 3.2 a). Da wir P als zykelfrei, einfach irreduzibel in P OSET vorausgesetzt haben, gibt es dann ein Objekt i von I, so daß p_{i} injektiv ist.

‘(4) ⇒ (1)’: Sei (P, p) eine zykelfreie, einfache Darstellung über D : I → P OSET. Nach Folgerung 5.1 c) ist jedes Objekt von D ein Bereich, und nach Folgerung 5.2 a) ist jeder verbindende Morphismus von D stetig. Da wir P als zykelfrei, einfach irreduzibel in DCP O vorausgesetzt haben, gibt es dann ein Objekt i von I, so daß p_{i} injektiv ist.

Wir haben die Halbfaktoren eines dI-Bereiches charakterisiert als Bilder von stabilen Projektionen, welche die Slide-Bedingung erfüllen. Mit Hilfe dieser Charakterisierung und mit Proposition 6.12 überlegt man sich nun leicht, daß jeder flache Bereich zykelfrei irreduzibel in DCP O ist. Hier ein weiteres Beispiel für einen zykelfrei irreduziblen Bereich:

P hat keine nichttrivialen Halbfaktoren. Ein von {⊥} verschiedener Halbfaktor A von P muß nämlich ein Atom von P enthalten, da er ein Anfangsstück ist. Dann muß er aber alle Atome enthalten, da sonst die Slide-Bedingung verletzt wäre. Da die Atome aber eine Basis von P bilden und da ein Halbfaktor abgeschlossen ist gegen Suprema, ist dann A = P. Nach Proposition 6.12 ist P also zykelfrei irreduzibel in DCP O. Insbesondere ist P also kein OHF - Objekt. P ist jedoch ein HF -Objekt, nämlich über folgendem Diagramm:

Proposition 6.13 Sei A ein distributiver, stetiger beschränkt vollständiger Bereich, und sei (A, p) eine zykelfreie, einfache Darstellung über D : I → P OSET. Für jedes i ∈ Ob(I) bezeichne e_{i} die untere Adjungierte zu p_{i}. Bezeichne weiterhin:

M := {e_{i} ∘ p_{i} | i ∈ Ob(I)}
L_{M} := {⋁ U | U ist ∗ −Endstück von M}

Wir setzen voraus, daß L_{M} = H_{A}. Dann ist jedes Objekt von D zykelfrei, einfach irreduzibel in P OSET.

Beweis: Sei j ∈ Ob(I). Wir zeigen, daß die Identität und die konstante ⊥-Abbildung die einzigen Halbfaktorprojektionen von D(j) sind. Sei also (r, s) ein Halbfaktor-Kohalbfaktorprojektionspaar von D(j). Das Diagramm der dadurch gegebebenen Darstellung von D(j) bezeichnen wir mit E_{j} : K_{j} → P OSET. Also:

K_{j} = 1_{j} ⟶ 2_{j}, E_{j}(1_{j}) = im(s), E_{j}(2_{j}) = im(r), E_{j}(1_{j} ← 2_{j}) = ′r′

Für i ∈ Ob(I) \ {j} bezeichne E_{i} : K_{i} → P OSET das ‘Singleton-Diagramm’ mit dem Objekt D(i). Also:

K_{i} = 1_{i}, E_{i}(1_{i}) = D(i)

Wir betrachten das Diagramm ⨄_{D}E_{i}.

... D(i)  \overline{\overline{>}} D(j)  \overline{\overline{>}} D(k) ...

... D(i)  D(k) ...

[figure]

im(s)  im(r)

Die verbindenden Morphismen von D erhalten Suprema, nach Folgerung 5.2 c). Nach Teil a) und Teil b) derselben Folgerung ist D(j) distributiv und stetig. Wiederum nach Teil c) der Folgerung erhält dann auch der verbindende Morphismus von E_{j} Suprema. Bezeichne nun

t_{1_{j}} die Korestriktion von s aufs Bild von s
t_{2_{j}} die Korestriktion von r aufs Bild von r
F ür alle i ∈ Ob(I) \ {j} : t_{1_{i}} die Identität auf D(i)

Nach Proposition 4.2 ist (A, (t_{k_{i}} ∘p_{i})_{i∈ObI,k_{i}∈ObK_{i}}) ein Hyperlimeskegel über ⨄_{D}E_{i}. Setzen wir nun:

r̃ := e_{j} ∘ r ∘ p_{j}
s̃ := e_{j} ∘ s ∘ p_{j}
M̃ := M ∪ {r̃, s̃}
U := {e_{i} ∘ p_{i} | i ∈↑_{I} j \ {j}}
V := {e_{i} ∘ p_{i} | i ∈↑_{I} j}
W := {e_{i} ∘ p_{i} | i ∈↑_{I} j \ {j}} ∪ {r̃}

Mit Proposition 3.6 erhält man, daß U und V ∗-Endstücke von M sind. Man überlegt sich leicht, daß ↑_{I} j \ {j} ∪ {2_{j}} ein ∗-Endstück von ⨄_{I}K_{i} ist. Wiederum mit Proposition 3.6 erhält man dann, daß W ein ∗-Endstück von M̃ ist. Nach Satz 6.1 ist dann ⋁ W ∈ H_{A}. Da wir vorausgesetzt haben, daß L_{M} = H_{A}, ist also ⋁ W ∈ L_{M}. ⋁ U und ⋁ V sind Nachbarn in L_{M}. Andererseits ist aber ⋁ U ≤ ⋁ W ≤ ⋁ V. Also ist entweder ⋁ U = ⋁ W oder ⋁ V = ⋁ W. Im ersten Fall ist r̃ ≤ ⋁ U, also r̃ = r̃ ∘ ⋁ U. Andererseits ist aber r̃ = e_{j} ∘ r ∘ p_{j} ≤ e_{j} ∘ p_{j} ≤ ⋁(M \ U). Also: r̃ = r̃ ∘ ⋁ U ≤ ⋁(M \ U) ∘ ⋁ U = ⊥. Nun ist e_{j} ∘ r ∘ p_{j} = r̃ = ⊥. Wegen der Surjektivität von p_{j} ist dann auch e_{j} ∘ r = ⊥. Weil r das kleinste Element auf sich selbet abbildet und weil e_{j} injektiv ist, ist dann auch r = ⊥. Im zweiten Fall, falls also ⋁ W gleich ⋁ V ist, ist r̃ ≥ ⋁ V/ ⋁ U = e_{j} ∘ p_{j}. Dabei steht das Ungleichheitszeichen nach Definition von /, und das Gleichheitszeichen wegen Satz 6.1 d). Es ist also e_{j} ∘ r ∘ p_{j} = r̃ = e_{j} ∘ p_{j} = e_{j} ∘ id_{D(j)} ∘ p_{j}. Mit der Injektivität von e_{j} und der Surjektivität von p_{j} folgt, daß r = id_{D(j)}.

Satz 6.4 Sei A ein dI-Bereich. M sei definiert wie im Zerlegungssatz 6.3. Sei p ∈ M. Dann:

a) D_{M}(p) ist zykelfrei, einfach irreduzibel in P OSET.

b) D_{M}(p) ist zykelfrei irreduzibel in BC.

c) D_{M}(p) ist zykelfrei irreduzibel in DCP O.

Beweis:

a) Wir wollen Proposition 6.13 anwenden, müssen also zeigen, daß L_{M} = H_{A}. Nach Satz 6.1 ist L_{M} eine Teilmenge von H_{A}. Sei umgekehrt p ein Element von H_{A}. Bezeichne U := {q/q^{↓} | q ∈ H_{A} und q ≤ p}. Dann ist p = ⋁ U. Das beweist man wie die Eigenschaft (i) im Beweis des Zerlegungssatzes: Man zeigt zunächst per Induktion, daß jedes vollständig verbundirreduzible Element x des Bildes von p Supremum von {p(x) | p ∈ U} ist. Dann benutzt man, daß die vollständig verbundirreduziblen Elemente eine Basis des Bildes von p bilden. Wir haben im Beweis des Zerlegungssatzes gesehen, daß

≤^{∗}⊆ {(p/p^{↓}, q/q^{↓}) | p, q ∈ J(H_{A}) und q ≤ p}.

U ist ein Endstück von M bezüglich der Ordnung auf der rechten Ungleichungsseite, also erst recht ein Endstück in der ∗-Ordnung. Nach Definition von L_{M} ist also ⋁ U ∈ L_{M}.

b) folgt mit Propositon 6.12.

c) Nach Folgerung 5.2 e) ist D_{M}(p) endlich algebraisch. Nach Proposition 6.12 ist D_{M}(p) dann zykelfrei irreduzibel in DCP O.

Wir beenden, das Kapitel mit zwei Beispielen. Zunächst ein Beispiel dafür, daß die Zerlegung eines dI-Bereiches in zykelfrei irreduzible Faktoren nicht eindeutig ist:

Das nächste Beispiel ist ein distributiver Scott-Bereich, der sich nicht als zykelfreier Hyperlimes von in BC zykelfrei irreduziblen Mengen darstellen läßt:

Es ist H̃_{A} = {↓ n′ | n ∈ N} ∪ {{⊥}}. Ein Halbfaktor ist nämlich Bild einer stabilen Projektion. Die stabilen Projektionen in einem vollständigen Verband sind gerade die Projektionen auf Hauptanfänge. Ist p eine Projektion auf einen Hauptanfang ↓ n für ein n ∈ N, so ist A/Θ_{p} = {↓ n, {n′ | n ∈ N}}. Da {n′ | n ∈ N} kein kleinstes Element hat, ist Θ_{p} kein Projektionskern. Nach Proposition 6.6 ist ↓ n also kein Halbfaktor. Ist p eine Projektion auf einen Hauptanfang ↓ n′ für ein n ∈ N, so ist A/Θ_{p} = {↓ n′} ∪ {{m, m′} | 1 ≤ m < n}. Man sieht leicht, daß Θ_{p} dann ein Projektionskern ist. Die Slide-Bedingung wird in einem Verband von jeder Projektion erfüllt. Da stabile Projektionen eines stetigen, distributiven Bereiches Suprema erhalten, erfüllt p auch die dritte Bedingung aus Proposition 6.6. Also ist ↓ n′ ein Halbfaktor. A hat nichttriviale Halbfaktoren und ist somit nicht zykelfrei irreduzibel in BC. Jede zykelfreie Darstellung von A in BC definiert eine Menge M von Projektionen, die die drei Eigenschaften aus Proposition 3.4 hat, und deren ∗-Präordnung antisymmetrisch ist. Nach Satz 6.1 gibt es einen Unterverband L von H_{A}, so daß M = {p/p^{↓_{L}} | p ist verbundirreduzibel in L}. H_{A} ist eine Kette, also auch L. Ist L endlich, so ist das Element von M, welches durch das kleinste Element von L definiert wird, isomorph zu A, ist also nicht zykelfrei irreduzibel in BC. Ist L unendlich, so ist das punktweise Supremum von M nicht gleich der Identität.

7 Eine Charakterisierung der Zustandsmengen von stabilen konkreten Datenstrukturen

In [Cur] werden konkrete Datenstrukturen eingeführt:

Definition 7.1 Eine konkrete Datenstruktur ist gegeben durch ein 4-Tupel (C, V, E, ⊢). C und V sind Mengen. Die Elemente von C heißen Zellen, die Elemente von V heißen Werte. E ist eine Teilmenge von C × V, so daß es für jede Zelle c eine Wert v gibt, so daß (c, v) ∈ E. Die Elemente von E heißen Ereignisse. Ist A eine Teilmenge von E, so schreiben wir F (A) für die Menge {c ∈ C | ∃v ∈ V.(c, v) ∈ A}. Ist c ein Element von F (A), so sagen wir c sei in A belegt. ⊢ ist eine Teilmenge von P^{fin}(E) × C und heißt Belegbarkeitsrelation. Ist X ⊢ c, so nennen wir X eine Belegbarkeitsvoraussetzung (oder kürzer: Voraussetzung) von c. Beweise einer Zelle c sind folgendermaßen definiert:

(i) Ist ∅ ⊢ c, so ist ∅ ein Beweis von c.

(ii) Ist {(c_{1}, v_{1}), .., (c_{n}, v_{n})} ⊢ c, und ist P_{i} ein Beweis von c_{i} für jedes i ∈ {1, .., n}, so ist P := {(c_{1}, v_{1}), .., (c_{n}, v_{n})} ∪ ⋃_{i=1}^{n} P_{i} ein Beweis von c, falls zusätzlich gilt:

(a) (d, v), (d, w) ∈ P ⇒ v = w (‘keine Zelle ist doppelt belegt’)

(b) c ∉ F (P) (‘c ist in P noch nicht belegt’)

Für die Menge aller Beweise einer Zelle c schreiben wir P roof(c). Ein Zustand Z von (C, V, E, ⊢) sei eine Teilmenge von E, so daß

(i) (c, v), (c, w) ∈ Z ⇒ v = w

(ii) ∀(c, v) ∈ Z. ∃P ∈ P roof(c). P ⊆ Z

Wir schreiben A(C, V, E, ⊢) für die Menge aller Zustände von (C, V, E, ⊢) und betrachten diese Menge als geordnete Menge mit der Inklusionsordnung.

In [Cur] sind Beweise etwas anders definiert als hier. Dort braucht ein Beweis nämlich nicht die Bedingungen (a) und (b) zu erfüllen. Diese beiden Bedingungen versichern uns, daß P ∪ (c, v) ein Zustand ist, falls P ein Beweis von c und (c, v) ein Ereigniss ist. Außerdem definiert Curien konkrete Datenstrukturen mit Hilfe von Deduktionen (Herleitungsfolgen), und nicht wie wir mit Hilfe von Beweisen (Herleitungsbäumen). Unsere Definition ist jedoch äquivalent zu der von Curien.

Proposition 7.1 Sei M = (C, V, E, ⊢) eine konkrete Datenstruktur.

a) A(M) ist ein Bereich.

b) A(M) ist beschränkt vollständig.

c) A(M) ist endlich algebraisch.

Beweis:

a) Beliebige Vereinigungen von Zuständen haben Eigenschaft (ii). Sei Z eine gerichtete Menge von Zuständen. Seien (c, v), (c, w) ∈ ⋃ Z. Dann gibt es Z_{1}, Z_{2} ∈ Z, so daß (c, v) ∈ Z_{1} und (c, w) ∈ Z_{2}. Da Z gerichtet ist, gibt es ein Y ∈ Z, so daß Z_{1}, Z_{2} ⊆ Y Da Y Bedingung (i) erfüllt, ist v = w.

b) Sei Z eine beschränkte Teilmenge von A(M). Als Teilmenge eines Zustandes hat ⋃ Z die Eigenschaft (i).

c) Sei Z ∈ A(M). Für jedes Element (c, v) von Z bezeichne P_{c} irgendeinen Beweis von c, der in Z enthalten ist. P_{c} ∪ {(c, v)} ist endlich, also kompakt, und es ist Z = ⋃_{(c,v)∈Z} P_{c} ∪ {(c, v)}. Also ist A(M) algebraisch. Ein unendlicher Zustand kann nicht kompakt sein, denn er ist, wie wir gerade gesehen haben, Vereinigung von endlichen Zuständen.

Betrachten wir eine konkrete Datenstruktur M, und einen endlichen Zustand Z von M. Man überlegt sich leicht, daß jeder obere Nachbar von Z in A(M) eine Menge ist, die gerade ein Element mehr hat als Z. Auf Grund dessen kann die Menge K(A(M)) aller endlichen Zustände von M keine konvexen Teilmengen haben, die isomorph zu einem der typischen nicht-distributiven Verbände M_{3} oder N_{3} sind. (Trotzdem braucht K(A(M)) nicht distributiv zu sein.) Curien benutzt Eigenschaften dieser Art, um Zustandsmengen von konkreten Datenstrukturen ordnungstheoretisch zu charakterisieren. Er nennt die Zustandsmenge einer konkreten Datenstruktur einen konkreten Bereich.

Definition 7.2 Eine konkrete Datenstruktur heißt stabil, falls jeder Zustand für jede Zelle höchstens eine Voraussetzung enthält. Eine konkrete Datenstruktur heißt wohlfundiert, falls es keine Folge (X_{n}, c_{n}) ∈ (P^{fin}(E) × C)^{N} gibt, so daß X_{n} ⊢ c_{n} und c_{n+1} ∈ F (X_{n}) für alle n ∈ N. Eine wohlfundierte und stabile konkrete Datenstruktur heißt deterministisch.

In [Cur] wird gezeigt, daß die Zustandsmengen der stabilen konkreten Datenstrukturen, wie auch die Zustandsmengen der deterministischen konkreten Datenstrukturen, gerade die distributiven konkreten Bereiche sind. Wir werden in diesem Kapitel die Zustandsmengen der stabilen konkreten Datenstrukturen anders charakterisieren, nämlich als Hyperlimites von flachen Bereichen über zykelfreien, einfachen Diagrammen, deren Indexkategorien die Eigenschaft haben, daß jedes Hauptende endlich ist, und deren verbindende Morphismen konstant sind auf der Menge der maximalen Elemente des jeweiligen Definitionsbereiches.

Definition 7.3 Sei M = (C, V, E, ⊢) eine konkrete Datenstruktur. Es bezeichne

P roof := {(P, c) ∈ ⋃_{c∈C} P roof(c) × C | P ist Beweis von c}

Um Klammern zu sparen, schreiben wir P_{c} anstatt (P, c).

Beweis, daß dadurch eine Ordnung auf P roof gegeben ist: Die Transitivität von ‘<’ ist offensichtlich. Zur Antisymmetrie: Angenommen es gäbe P_{c}, Q_{d} ∈ P roof, so daß sowohl P_{c} < Q_{d} als auch Q_{d} < P_{c}. Da dann sowohl P eine Teilmenge von Q wäre als auch Q eine Teilmenge von P, wäre P = Q. Außerdem wäre c ∈ F (Q). Da P gleich Q ist, wäre also c ∈ F (P). Wir haben aber per Definition verboten, daß eine Zelle c in einem Beweis von c bereits belegt ist. Ein Widerspruch.

Proposition 7.2 Jeder Zustand einer stabilen konkreten Datenstruktur enthält für jede Zelle höchstens einen Beweis.

Beweis: Sei M eine stabile konkrete Datenstruktur. Sei Z ein Zustand von M, c eine Zelle und P und P′ Beweise von c, die in Z enthalten sind. Falls sowohl P als auch P′ leer sind, so ist nichts zu zeigen. Sei nun X = {(c_{1}, v_{1}), .., (c_{n}, v_{n})} ⊆ E und P = X ∪ ⋃_{i=1}^{n} P_{i}, so daß X ⊢ c und P_{i} ∈ P roof(c_{i}) für jedes i ∈ {1, .., n}. Genauso sei X′ = {(c′_{1}, v′_{1}), .., (c′_{m}, v′_{m})} und P′ = X′ ∪ ⋃_{i=1}^{m} P′_{i}, so daß X′ ⊢ c und P′_{i} ∈ P roof(c′_{i}) für alle i ∈ {1, .., m}. Da M stabil ist, ist X = X′. Nach Induktionsannahme ist P_{i} = P′_{i} für alle i ∈ {1, .., n}. Also ist P = P′.

Definition 7.4 Ist Z ein Zustand einer stabilen konkreten Datenstruktur und c eine in Z belegte Zelle, so bezeichne pr(c, Z) den in Z enthaltenen Beweis von c und val(c, Z) bezeichne den Wert, mit dem c in Z belegt ist.

Wir stellen fest: Sind Y und Z Zustände einer stabilen konkreten Datenstruktur, so daß Y in Z enthalten ist, und ist c ∈ F (Y), so ist pr(c, Y) = pr(c, Z) und val(c, Y) = val(c, Z). Das nächste Lemma ist entscheidend:

Lemma 7.1 Sei c eine Zelle einer stabilen konkreten Datenstruktur, und seien P und P′ zwei verschiedene Beweise von c. Dann gibt es einen gemeinsamen echten Unterbeweis Q_{d} von P_{c} und P′_{c}, so daß val(d, P) ≠ val(d, P′).

Beweis: Sei M eine stabile konkrete Datenstruktur. Zu zeigen ist die folgende Aussage:

∀(P_{c}, P′_{c}) ∈ (P roof)^{2}. [(P ≠ P′) ⇒ (∃Q_{d} < P_{c}, P′_{c}. val(d, P) ≠ val(d, P′))]

In (P roof)^{2} ist jeder Hauptanfang endlich. Wir können die Aussage also per Induktion über die Mächtigkeit des erzeugten Hauptanfanges zeigen. Sei zunächst (P_{c}, P′_{c}) ein minimales Element von (P roof)^{2}. Da P und P′ Zustände sind, sind dann sowohl P als auch P′ leer. Dann ist die Aussage P ≠ P′ falsch, die Implikation also wahr. Seien nun P_{c}, P′_{c} ∈ P roof, so daß P ≠ P′. Angenommen die Implikation sei bereits bewiesen für (R_{d}, R′_{d}) ∈ (P roof)^{2} mit (R_{d}, R′_{d}) < (P_{c}, P′_{c}). Wegen Proposition 7.2 ist P ∪ P′ kein Zustand. Es gibt also ein a ∈ F (P) ∩ F (P′), so daß val(a, P) ≠ val(a, P′). Es ist (pr(a, P)_{a}, pr(a, P′)_{a}) < (P_{c}, P′_{c}). Nach Induktionsannahme ist also entweder pr(a, P) = pr(a, P′), oder es gibt ein Q_{d} < pr(a, P)_{a}, pr(a, P′)_{a}, so daß val(d, pr(a, P)) ≠ val(d, pr(a, P′)).

Satz 7.1 Sei M = (C, V, E, ⊢) eine stabile konkrete Datenstruktur. Das Diagramm D : P roof^{op} → DCP O sei definiert durch:

D(P_{c}) := {v ∈ V | (c, v) ∈ E}_{⊥}
D(P_{c} ← Q_{d})(x) := \{ \begin{matrix}val(c, Q) & falls x ≠ ⊥ \\ ⊥ & falls x = ⊥ \end{matrix}

Dann ist die Zustandsmenge A(M) ordnungsisomorph zu hypD.

Beweis:

‘D ist ein Diagramm’: Seien P_{c}, Q_{d}, R_{e} ∈ P roof, so daß P_{c} < Q_{d} < R_{e}. Sei x ∈ D(R_{e}).

D(P_{c} ← Q_{d}) ∘ D(Q_{d} ← R_{e})(x) = \{ \begin{matrix}D(P_{c} ← Q_{d})(val(d, R)) & falls x ≠ ⊥ \\ D(P_{c} ← Q_{d})(⊥) & falls x = ⊥ \end{matrix}
= \{ \begin{matrix}val(c, Q) & falls x ≠ ⊥ \\ ⊥ & falls x = ⊥ \end{matrix}
= \{ \begin{matrix}val(c, R) & falls x ≠ ⊥ \\ ⊥ & falls x = ⊥ \end{matrix}
= D(P_{c} ← R_{e})(x)

Wir definieren nun die Isomorphismen zwischen A(M) und hypD.

φ : A(M) → hypD sei gegeben durch:

p_{P_{c}} ∘ φ(Z) = \{ \begin{matrix}val(c, Z) & falls c ∈ F (Z) und P ⊆ Z \\ ⊥ & sonst \end{matrix}

ψ : hypD → A(M) sei gegeben durch:

ψ((x_{P_{c}})_{P_{c}∈P roof}) = {(c, x_{P_{c}}) | x_{P_{c}} ≠ ⊥}

‘φ ist wohldefiniert’: Seien (P_{c}, Q_{d}) ∈< und Z ∈ A(M).

Falls d in Z belegt ist und Q eine Teilmenge von Z ist, so ist

D(P_{c} ← Q_{d}) ∘ p_{Q_{d}} ∘ φ(Z) = D(P_{c} ← Q_{d})(val(d, Z)) = val(c, Q) = val(c, Z).

Weil P_{c} ein echter Unterbeweis von Q_{d} ist, ist c in Q belegt, und Q ist eine Teilmenge von P. Also ist auch p_{P_{c}} ∘ φ(Z) = val(c, Z). Falls nun d in Z nicht belegt ist oder Q keine Teilmenge von P ist, so ist

D(P_{c} ← Q_{d}) ∘ p_{Q_{d}} ∘ φ(Z) = D(P_{c} ← Q_{d})(⊥) = ⊥ ≤ p_{P_{c}} ∘ φ(Z)

‘ψ ist wohldefiniert’: Sei x = (x_{P_{c}})_{P_{c}∈P roof} ∈ hypD.

‘ψ(x) erfüllt (i)’: Seien (c, x_{P_{c}}), (c, x_{P′_{c}}) ∈ ψ(x), das heißt x_{P_{c}}, x_{P′_{c}} ≠ ⊥. Angenommen es sei P_{c} ≠ P′_{c}. Nach Lemma 7.1 gibt es einen gemeinsamen echten Unterbeweis Q_{d} von P_{c} und P′_{c}, so daß val(d, P) ≠ val(d, P′). Es ist x_{Q_{d}} ≥ D(Q_{d} ← P_{c})(x_{P_{c}}) = val(d, P). Genauso ist x_{Q_{d}} ≥ val(d, P′). Andererseits sind val(d, P) und val(d, P′) aber maximale Elemente von D(Q_{d}), haben also keine gemeinsame obere Schranke. Ein Widerspruch.

‘ψ(x) erfüllt (ii)’: Sei (c, x_{P_{c}}) ∈ ψ(x), das heißt x_{P_{c}} ≠ ⊥. Wir zeigen, daß P eine Teilmenge von ψ(x) ist. Sei also (d, v) ∈ P. Da P ein Zustand ist, gibt es einen Beweis Q von d, der in P enthalten ist. Es ist x_{Q_{d}} ≥ D(Q_{d} ← P_{c})(x_{P_{c}}) = val(d, P) = v. Da v maximal in D(Q_{d}) ist, ist dann x_{Q_{d}} = v. Nach Definition von ψ ist also (d, v) ∈ ψ(x).

‘φ ∘ ψ = id_{hypD}’: Sei x = (x_{P_{c}})_{P_{c}∈P roof} ∈ hypD, und sei P_{c} ∈ P roof. Es ist zu zeigen, daß p_{P_{c}} ∘ φ ∘ ψ(x) = x_{P_{c}}. Falls x_{P_{c}} ≠ ⊥, so ist (c, x_{P_{c}}) ∈ ψ(x). Wie wir bereits gezeigt haben, ist dann P eine Teilmenge von ψ(x). Also ist p_{P_{c}} ∘ φ ∘ ψ(x) = val(c, ψ(x)) = x_{P_{c}}. Falls x_{Q_{c}} = ⊥ für alle Q ∈ P roof(c), so ist c ∉ F (ψ(x)), also p_{P_{c}} ∘ φ ∘ ψ(x) = ⊥. Falls x_{P_{c}} gleich ⊥ ist, es jedoch eine Beweis P′ von c gibt, so daß x_{P′_{c}} ≠ ⊥, so gibt es nach Lemma 7.1 einen gemeinsamen echten Unterbeweis Q_{d} von P_{c} und P′_{c}, so daß val(d, P) ≠ val(d, P′). Es ist p_{Q_{d}} ∘ φ ∘ ψ(x) ≥ D(Q_{d} ← P′_{c}) ∘ p_{P′_{c}} ∘ φ ∘ ψ(x) = D(Q_{d} ← P′_{c})(x_{P′_{c}}) = val(d, P′). Wäre p_{P_{c}} ∘ φ ∘ ψ(x) ≠ ⊥, so wäre p_{Q_{d}} ∘ φ ∘ ψ(x) ≥ D(Q_{d} ← P_{c}) ∘ p_{P_{c}} ∘ φ ∘ ψ(x) = val(d, P). Das steht im Widerspruch dazu, daß {val(d, P′), val(d, P)} unbeschränkt ist. Es ist also p_{P_{c}} ∘ φ ∘ ψ(x) = ⊥.

‘ψ ∘ φ = id_{A(M)}’: Sei Z ∈ A(M). Wir müssen die Mengengleichheit ψ ∘ φ(Z) = Z zeigen.

‘⊆’: Sei (c, v) ∈ ψ∘φ(Z). Nach Definition von ψ gibt es ein P_{c} ∈ P roof, so daß v = p_{P_{c}} ∘φ(Z). Wegen v ≠ ⊥ ist dann c ∈ F (Z) und p_{P_{c}} ∘ φ(Z) = val(c, Z), nach Definition von φ. Also

ist (c, v) ∈ Z.

‘⊇’: Sei (c, v) ∈ Z. Da Z ein Zustand ist, gibt es einen Beweis P von c, der in Z enthalten ist. Nach Definition von φ ist p_{P_{c}} ∘ φ(Z) = v, und nach Definition von ψ ist dann (c, v) ∈ ψ ∘ φ(Z).

Die Diagramme die man, wie in Satz 7.1 beschrieben, aus stabilen konkreten Datenstrukturen erhält, haben sehr spezielle Eigenschaften. So sind sämtliche Hauptenden ihrer Indexkategorie endlich, und die verbindenden Morphismen sind konstant auf der Menge der maximalen Elemente des jeweiligen Definitionsbereiches. Wir werden zeigen, daß diese beiden Eigenschaften die zykelfreien, einfachen Diagramme von flachen Bereichen charakterisieren, deren Hyperlimesobjekte isomorph zur Zustandsmenge einer stabilen konkreten Datenstruktur ist.

Definition 7.5 Ein zykelfreies, einfaches Diagramm von flachen Bereichen heiße Baumdiagramm, falls es die beiden folgenden Eigenschaften hat:

(1) Jedes Hauptende der Indexkategorie ist endlich.

(2) Für jeden Pfeil a : i → j der Indexkategorie ist

D(a)(x) = \{ \begin{matrix}⊥ & falls x = ⊥ \\ c & sonst, \end{matrix}

wobei c ein von ⊥ verschiedenes Element von D(j) ist.

Eine stabile, konkrete Datenstruktur (C, V, E, ⊢) heiße normal, falls sie die folgenden Eigenschaften hat:

(1′) Für jede Zelle gibt es genau eine Voraussetzung.

(2′) Jede Voraussetzung einer Zelle c ist auch ein Beweis von c.

(3′) V = ⋃_{c∈C} {v | (c, v) ∈ E}

Bezeichne:

\begin{matrix}SCDS & die Klasse aller stabilen konkreten Datenstrukturen \\ BAUMDIAGRAMM & die Klasse aller Baumdiagramme \end{matrix}

Außerdem bezeichne D : SCDS → BAUMDIAGRAMM die Abbildung, die jeder stabilen konkreten Datenstruktur das in Satz 7.1 beschriebene Diagramm zuordnet.

Satz 7.2 Es gibt eine Abbildung M : BAUMDIAGRAMM → SCDS, so daß:

a) Für alle Baumdiagramme D ist M(D) normal.

b) Für alle normalen stabilen konkreten Datenstrukturen M ist M(D(M)) = M, bis auf Umbenennung der Zellen.

c) Für alle Baumdiagramme D ist D(M(D)) = D, bis auf Isomorphie der Indexkategorie.

Beweis: Sei D : I → DCP O ein Baumdiagramm. Wir definieren M(D) = (C, V, E, ⊢) durch

C = Ob(I)
V = ⋃_{i∈Ob(I)} D(i) \ {⊥}
E = ⋃_{i∈I}({i} × D(i) \ {⊥})
X ⊢ i , falls X = {(j, D(j ← i)(y)) | j > i}, wobei y ∈ D(i) \ {⊥}

M(D) ist stabil, denn jede Zelle hat nur eine Belegbarkeitsvoraussetzung.

a) Es ist offensichtlich, daß M(D) die Eigenschaften (1′) und (3′) hat. Bleibt zu zeigen, daß jede Voraussetzung einer Zelle von M(D) auch ein Beweis derselben ist. Sei also i ein Objekt von I. Bezeichne X_{i} die Menge {(j, D(j ← I)(y) | j > i}, wobei y ein von ⊥ verschiedenes Element von D(i) ist. Nach Definition von M(D) ist X_{i} die einzige Voraussetzung von i. Zu zeigen ist also, daß X_{i} ein Beweis von i ist: Falls i ein maximales Objekt von I ist, so ist X_{i} leer. Da X_{i} außerdem eine Voraussetzung von I ist, ist also X_{i} ein Beweis von i. Sei nun i ein beliebiges Objekt von I. Nehmen wir an, für alle Objekte j, die echt größer sind als i, sei X_{j} ein Beweis von j. Es ist

X_{i} = {(j, D(j ← i)(y)) | j > i}
= {(j, D(j ← i)(y)) | j > i} ∪ ⋃_{j>i} {(k, D(k ← j) ∘ D(j ← i)(y)) | k > j}
= X_{i} ∪ ⋃_{j>i} X_{j}
∈ P roof(i)

b) Sei M eine normale stabile konkrete Datenstruktur. Für jede Zelle c von M gibt es wegen (1′) genau eine Belegbarkeitsvoraussetzung, nennen wir sie X_{c}. Wegen (2′) ist X_{c} ein Beweis von c. Aus (1′) wiederum folgt, daß X_{c} der einzige Beweis von c ist. Durch c ↦ X_{c} wird also eine Bijektion φ_{M} von C_{M} nach P roof_{M} definiert. Nun brauchen wir nur noch Definitionen einzusetzen:

C_{MDM} = I_{DM} = P roof_{M} ≃ C_{M}

V_{MDM} = ⋃_{i∈I_{DM}}(DM)(i) \ {⊥}
= ⋃_{P_{c}∈P roof_{M}} {v ∈ V_{M} | (c, v) ∈ E_{M}}_{⊥} \ {⊥}
= ⋃_{c∈C_{M}} {v ∈ V_{M} | (c, v) ∈ E_{M}}

=^{(3′)} V_{M}
E_{MDM} = ⋃_{i∈I_{DM}}({i} × (DM)(i) \ {⊥})
= ⋃_{P_{c}∈P roof_{M}}({P_{c}} × {v ∈ V_{M} | (c, v) ∈ E_{M}})
≃ ⋃_{c∈C}({c} × {v ∈ V_{M} | (c, v) ∈ E_{M}})
= E_{M}

Sei c eine Zelle von M, und bezeichne P den Beweis von c in M. Es ist

Y ⊢_{MDM} P_{c} ⇔ Y = {(d, (DM)(Q_{d} ← P_{c})(y)) | Q_{d} < P_{c}}
⇔ Y = {(d, val(d, P) | Q_{d} < P_{c}}
⇔ Y = P

P ist aber auch die einzige Voraussetzung von c in M. Es ist also Y ⊢_{MDM} P_{c}, genau dann wenn Y ⊢ c.

c) Es ist C_{MD} = Ob(I_{D}). Wir zeigen, daß die im Beweis von b) definierte Bijektion φ_{MD} sogar ein Ordnungsisomorphismus von I_{D} nach P roof_{MD}^{op} ist. Seien i und j Objekte von I_{D}. Es ist zu zeigen, daß i echt kleiner ist als j, genau dann wenn j in φ_{MD}(i) belegt ist und φ_{MD}(j) eine Teilmenge von φ_{MD}(i) ist. Man sieht sofort, daß i echt kleiner ist als j, genau dann wenn j in φ_{MD}(i) = {(k, D(k ← i)(y)) | k > i} belegt ist. Sei nun i echt kleiner als j. Bezeichne y ein Element von D(i) \ {⊥}. Dann ist D(j ← i)(y) ∈ D(j) \ {⊥}, und es ist

φ_{MD}(j) = {(k, D(k ← j) ∘ D(j ← i)(y)) | k > j}
= {(k, D(k ← i)(y)) | k > j}
⊆ φ_{MD}(i)

Nachdem wir nun festgestellt haben, daß durch die Vorschrift i ↦ X_{i} ein Ordnungsisomorphismus von I_{D} nach P roof_{MD}^{op} gegeben ist, brauchen wir nur noch Definitionen einzusetzen:

I_{DMD} = P roof_{MD}^{op} ≃ I_{D}
(DMD)(X_{i}) = {v | (i, v) ∈ E_{MD}}_{⊥} = {v | v ∈ D(i) \ {⊥}}_{⊥} = D(i)

(DMD)(X_{j} ← X_{i})(x) = \{ \begin{matrix}⊥ & falls x = ⊥ \\ val(j, X_{i}) & sonst \end{matrix}
= \{ \begin{matrix}⊥ & falls x = ⊥ \\ D(j ← i)(x) & sonst \end{matrix}
= D(j ← i)(x)

Korollar 7.1 Ein Bereich ist Zustandsmenge einer stabilen, konktreten Datenstruktur, genau dann wenn er Hyperlimesobjekt über einem Baumdiagramm ist.

Beweis: Sei M eine stabile konkrete Datenstruktur. Das Diagramm D(M) ist ein Baumdiagramm, und nach Satz 7.1 ist hyp(DM) isomorph zu A(M). Sei umgekehrt D ein Baumdiagramm. Nach Satz 7.2 c) ist DMD = D. Nach Satz 7.1 ist A(MD) isomorph zu hyp(DMD). Also ist A(MD) isomorph zu hypD.

Korollar 7.2 Zu jeder stabilen konkreten Datenstruktur gibt es eine normale stabile konkrete Datenstruktur mit isomorpher Zustandsmenge. Insbesondere gibt es also zu jeder stabilen konkreten Datenstruktur eine wohlfundierte stabile konkrete Datenstruktur mit isomorpher Zustandsmenge.

Beweis: Sei M eine stabile konkrete Datenstruktur. Nach Satz 7.2 a) ist MDM normal. Es ist

A(MDM) ≃^{7.1} hyp(DMDM) ≃^{7.2c)} hyp(DM) ≃^{7.1} A(M).

‘Jede normale stabile konkrete Datenstruktur ist wohlfundiert’: Sei (C, V, E, ⊢) eine normale stabile konkrete Datenstruktur. Angenommen es gäbe eine Folge (X_{n}, c_{n}) ∈ (P^{fin}(E) × C)^{N}, so daß X_{n} ⊢ c_{n} und c_{n+1} ∈ F (X_{n}) für alle n ∈ N. Wegen (2′) wäre X_{n} ein Beweis von c_{n} für jedes n ∈ N. Da X_{n} eine Voraussetzung von c_{n+1} enthält, und es wegen (1′) nur eine solche gibt, wäre X_{n+1} ⊆ X_{n} für jedes n ∈ N. Also wäre X_{n+1} ein echter Unterbeweis von X_{n} für jedes n ∈ N. In P roof gibt es aber keine unendlichen absteigenden Ketten. Ist nämlich P_{c} ein echter Unterbeweis von Q_{d}, so ist einerseits c in Q belegt (nach Definition eines Unterbeweises), und andererseits ist c in P nicht belegt (nach Definition eines Beweises von c). Also ist P eine echte Teilmenge von Q. Da Beweise endliche Mengen sind, kann es also in P roof keine unendlichen absteigenden Ketten geben.

Literatur

[BJO] P.Buneman,A.Jung,A.Ohori: Using Powerdomains to Generalize Relational Databases, Theotetical Computer Science 1990

[COMP] G.Gierz,K.H.Hofmann,K.Keimel,J.D.Lawson,M.Mislove,D.Scott: A Compendium of Continuous Lattices, Springer Verlag 1980

[Cur] P.-L. Curien: Categorical Combinators, Sequential Algorhithms and Functional Programming, Pitman 1986

[JLP] A.Jung,L.Libkin,H.Puhlmann: Decomposition of Domains, In: Proceedings of the Conference on Mathematical Foundations of Programming Semantics 1991

[Jun] A.Jung: Cartesian Closed Categories of Domains, Dissertation, Technische Hochschule Darmstadt 1988

[ML] S.MacLane: Categories for the Working Mathematician, Springer Verlag 1971

[Puh90] H.Puhlmann: Verallgemeinerung Relationaler Schemata in Datenbanken mit Informationsordnung, Diplomarbeit, Technische Hochschule Darmstadt 1990

[Puh91] H.Puhlmann: A Semantics for Generalized Database Relations, MSc Thesis, Imperial College London 1991

Danksagung

Zum Schluß möchte ich mich bedanken bei meinen Betreuern Dr.Achim Jung und Prof.Klaus Keimel. Bei Achim bedanke ich mich vor allem für das schöne und ergiebige Thema und die vielen Anregungen, die er mir zu meiner Arbeit gegeben hat. Bei Herrn Keimel bedanke ich mich für die Verbesserungsvorschläge zu meinem Skript und für die Zeit, die er sich für meine Betreuung zu den Domains-Seminaren genommen hat. Außerdem bedanke ich mich bei meinem Kommilitonen Olaf Kirch, mit dem ich mich gemeinsam in die Bereichstheorie eingearbeitet habe, für die gute Zusammenarbeit und für seine Hilfe beim Erlernen von TEX.

Hiermit erkläre ich eidesstattlich, daß ich diese Arbeit eigenständig und nur unter Verwendung der angegebenen Hilfsmittel angefertigt habe.

Darmstadt, 13.August 1993