Faktorisierungssysteme auf Bereichen

Diplomarbeit

von Mathias Kegelmann

Betreuer: Dr. Achim Jung Fachbereich Mathematik

•^{⨆↑} y_{i}
[figure]
⨆↑ x^{i} •  •y_{i}

[figure: R′][figure]

xi •
[figure: .......................]
• l

[figure: R]

• k

�

Technische Hochschule Darmstadt September 1995

Inhaltsverzeichnis

Einleitung 3

1 Grundlagen 5 1.1 Bereichstheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Faktorisierungssysteme . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Faktorisierungssysteme auf Bereichen 19 2.1 Faktorisierungssysteme auf geordneten Mengen . . . . . . . . . . 19 2.2 Erzeugung von Faktorisierungssystemen . . . . . . . . . . . . . . 23 2.3 Stetige Faktorisierungen . . . . . . . . . . . . . . . . . . . . . . . 26

3 Abbildungen zwischen faktorisierten Bereichen 33 3.1 Eine Kategorie faktorisierter Bereiche . . . . . . . . . . . . . . . . 33 3.2 Der Ansatz von Lamarche . . . . . . . . . . . . . . . . . . . . . 40

4 Kartesisch abgeschlossene Kategorien 53 4.1 Produkte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.2 Exponentiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

Literaturverzeichnis 63 2

Einleitung

In der Bereichstheorie betrachtet man vor allem zwei Arten von Funktionen, Scott-stetige und stabile. Die stabilen Abbildungen wurden von Berry ursprünglich für Untersuchungen zur Sequenzialität des λ-Kalküls eingeführt [Ber78]. Sie spielen ferner eine große Rolle für Modelle kommunizierender Prozesse [Win88] und bei den coherent spaces, die für die denotationelle Semantik von polymorphen Programmiersprachen [Gir86] und Linearer Logik [Gir87] verwendet werden.

Für stabile Funktionen fordert man, daß sie gerichtete Suprema und zusätzlich beschränkte binäre Infima erhalten. Es gibt also weniger stabile Funktionen als stetige. Das ändert sich aber, wenn man auch Funktionen höheren Typs betrachtet. Sei z.B. ι ein Grundtyp und [ι → ι] der stetige bzw. [ι ⇒ ι] der stabile Funktionenraum, dann sind bereits [[ι → ι] → ι] und [[ι ⇒ ι] ⇒ ι] unvergleichbar, da im zweiten Fall die Funktionen zwar zusätzlich stabil sein müssen, man dafür aber weniger Elemente im Urbildbereich hat. Also sind nicht einfach die stabilen Modelle in den entsprechenden stetigen enthalten.

François Lamarche konstruiert in [Lam95] eine Kategorie, die sowohl stetige als auch stabile Morphismen enthält; seine Ergebnisse bilden die Grundlage für diese Arbeit. Die Idee ist dabei die folgende: Man hat nicht verschiedene Sorten von Abbildungen sondern zusätzliche Struktur auf den dcpo’s, indem man die Ordnung auf diesen in zwei Teilordnungen zerlegt. Man definiert dann Morphismen als stetige Abbildungen, die nur durch die zweite Teilordnung beschränkte Infima erhalten müssen. So erhält man durch eine geeignete Wahl der Zerlegung die stetigen bzw. die stabilen Funktionen als Spezialfälle, wenn man die ursprüngliche Ordnung ganz der ersten bzw. der zweiten Teilordnung zuschlägt.

Im ersten Kapitel werden grundlegende Ergebnisse aus der Bereichstheorie und der Theorie der Faktorisierungssysteme zur Verfügung gestellt. Die eben angesprochene ‘Aufspaltung’ der Ordnung einer dcpo in zwei Teilordnungen ist technisch gesehen ein Faktorisierungssystem, wenn man die dcpo als Kategorie auffaßt. Eine Reihe von Eigenschaften, die wir später brauchen, sind Spezialfälle von Sätzen, die für Faktorisierungssysteme auf beliebigen Kategorien gelten. Da sich die Beweise für geordnete Mengen nicht besonders vereinfachen lassen, zeigen wir sie an dieser Stelle in größerer Allgemeinheit als wir sie später verwenden.

Diese Ergebnisse übertragen wir im zweiten Kapitel auf dcpo’s und untersuchen, wie man solche Faktorisierungssysteme erzeugen kann. Für die weitere Theorie kann man aber nicht beliebige Faktorisierungssysteme verwenden. Wir werden deshalb eine Reihe von äquivalenten Eigenschaften formulieren, die sicherstellen, daß ein Faktorisierungssystem ‘gut’ mit der zusätzlichen Struktur einer dcpo zusammenpaßt.

Damit können wir im dritten Kapitel zwei Ansätze angeben, um eine Kategorie zu konstruieren, die sowohl stetige als auch stabile Abbildungen enthält. Die Morphismen lassen sich dabei in beiden Fällen algebraisch und mit Hilfe verallgemeinerter topologischer Begriffe beschreiben. Wir werden die Äquivalenz dieser Beschreibungen zeigen und dann untersuchen, wie die beiden Ansätze zusammenhängen.

Im letzten Kapitel werden wir sehen, daß diese Kategorien Produkte haben. Also sind die Exponentiale das Problem beim Finden einer kartesisch abgeschlossenen Kategorie. Zur Zeit ist nur die von Lamarche in seinem Artikel angegebene bekannt. Wir können aber die Ordnung auf dem Exponential und den einen Teil des zugehörigen Faktorisierungssystems für kartesisch abgeschlossene volle Unterkategorien der Kategorien aus dem dritten Kapitel a priori angeben.

An dieser Stelle möchte ich mich bei allen bedanken, die mich bei der Erstellung dieser Arbeit unterstützt haben. Besonders danken möchte ich Prof. Dr. Klaus Keimel, dessen Vorlesungen und Engagement mich während meines ganzen Studiums beeinflußt haben. Thomas Erker und Micha Marz danke ich für das äußerst gründliche Korrekturlesen der Arbeit. Schließlich möchte ich mich bei Dr. Achim Jung für die Betreuung der Arbeit bedanken, bei der er jederzeit bereit war, auftauchende Fragen ausführlich zu diskutieren und mir durch seine Ideen neue Anregungen zu geben.

1 Grundlagen

Friends, Romans, countrymen, lend me your ears;

W. Shakespeare, Julius Cæsar

In diesem Kapitel werden die benötigten Definitionen und Fakten aus der Theorie der Bereiche und der Faktorisierungssysteme angegeben. Die Darstellung orientiert sich dabei weitgehend an [AJ95] und [BW84].

1.1 Bereichstheorie

Die grundlegenden Begriffe und Bezeichnungen der Bereichstheorie übernehmen wir aus [AJ95, Section 2].

Um Unklarheiten zu vermeiden, sind hier einige weniger geläufige Notationen aufgelistet: Für Teilmengen A ⊆ B einer geordneten Menge sagen wir, A sei kofinal in B, wenn es zu jedem x ∈ B ein x′ ∈ A mit x′ ⊒ x gibt. Wir benutzen den Begriff Bereich ausschließlich für stetige bzw. algebraische dcpo’s. Ist B die Basis eines stetigen Bereichs, schreiben wir B_{x} für die Elemente aus der Basis, die weit unter x liegen. Insbesondere benutzen wir diese Schreibweise bei algebraischen Bereichen; bei diesen bezeichne K immer die kompakten Elemente, und K_{x} sind damit die kompakten Elemente unter x. Ist D eine dcpo, dann bezeichnen wir mit ⊑_{D} die Teilmenge von D^{2}, die aus den geordneten Paaren (x, y) mit x ⊑ y besteht. Der Übersichtlichkeit wegen schreiben wir für solche Paare auch (x ⊑ y). Bezüglich der von D^{2} induzierten Ordnung ist ⊑_{D} selbst wieder eine dcpo.

Zuerst wollen wir nun die Ordnung und die Scott-offenen Mengen einer dcpo mit Hilfe von Funktionenräumen beschreiben, da wir diese Charakterisierungen später auf faktorisierte dcpo’s übertragen wollen. Im folgenden bezeichne 2 den zweielementigen Bereich 2 := {0, 1} mit 0 ⊑ 1.

Proposition 1.1. Die stetigen Abbildungen von 2 in eine dcpo D stehen in Bijektion zu den Paaren (x, y) ∈ D^{2} mit x ⊑ y, in Zeichen [2 → D] ≅ ⊑_{D}.

Beweis. Ist f: 2 → D stetig, dann gilt f(0) ⊑ f(1).

Ist umgekehrt x ⊑ y, dann definiert (0 ↦ x, 1 ↦ y) eine monotone Abbildung. Diese ist automatisch stetig, da es in 2 nur triviale gerichtete Mengen gibt.

Proposition 1.2. Die offenen Mengen einer dcpo D stehen in Bijektion zu den stetigen Abbildungen von D nach 2, d.h. σ(D) ≅ [D → 2], wobei σ(D) die Scott-Topologie auf D bezeichne.

Betrachtet man auf dem Funktionenraum die elementweise Ordnung und auf den offenen Teilmengen die Enthaltenseinsrelation, so ist die Bijektion ein Ordnungsisomorphismus.

Beweis. Da {1} eine offene Teilmenge von 2 ist, ist für jede stetige Abbildung D → 2 auch f^{−1}[{1}] offen.

Sei umgekehrt U ⊆ D offen. Die charakteristische Funktion

χ_{U}: x ↦ \begin{cases}1 & x ∈ U \\ 0 & sonst \end{cases}

ist stetig, was man unmittelbar durch Betrachten der Urbilder der drei offenen Mengen von 2 sieht.

Die charakteristischen Funktionen zweier Mengen sind genau dann in der punktweisen Ordnung vergleichbar, wenn die eine Menge in der anderen liegt.

Für einige Betrachtungen haben dcpo’s noch nicht genug Struktur. Deshalb wollen wir einige mögliche Zusatzeigenschaften aufzählen, mit deren Hilfe wir unsere Untersuchungen später auf spezielle dcpo’s einschränken können.

Definition 1.3. Sei D eine dcpo. Man sagt, D hat die Eigenschaft

• S, wenn je zwei beschränkte Elemente ein Infimum haben,

• L, wenn zwei Elemente x_{1}, x_{2} ∈ D, die durch y ∈ D beschränkt sind, ein Supremum x_{1} ⊔^{y} x_{2} in ↓y haben und D ein kleinstes Element hat,

• BC (bounded completeness), wenn je zwei beschränkte Elemente ein Supremum in D haben und D ein kleinstes Element hat,

• I, wenn D algebraisch ist und für jedes kompakte Element k das Anfangsstück ↓k endlich ist,

• I_{1}, wenn D algebraisch ist und es keine unendliche absteigende Kette kompakter Elemente gibt,

• d, wenn D die Eigenschaft BC hat und für alle x, y, z ∈ D, wobei y und z beschränkt sind, das Distributivgesetz x ⊓ (y ⊔ z) = (x ⊓ y) ⊔ (x ⊓ z) gilt.

Hat eine dcpo z.B. die Eigenschaft L, sprechen wir von einer L-dcpo etc.

Bemerkung. Da man mit binären und gerichteten Suprema alle Suprema von nichtleeren Teilmengen konstruieren kann, sind L-dcpo’s genau die dcpo’s, bei denen alle Hauptideale vollständige Verbände sind. Dabei sind die Infima in den Hauptidealen auch Infima in der ganzen dcpo, für die Suprema stimmt dies im allgemeinen nicht. Dementsprechend sind die BC-dcpo’s die dcpo’s, bei denen auch die Suprema in den Hauptidealen stets Suprema in der ganzen dcpo sind.

Die Bedingung BC ist echt stärker als L (siehe [AJ95, Fig. 11]). Für dcpo’s mit kleinstem Element ist L echt stärker als S. Ein Beispiel dafür ist ℕ mit der umgekehrten natürlichen Ordnung, worunter man zusätzlich zwei miteinander unvergleichbare Elemente und ⊥ setzt.

Eine dcpo hat die Eigenschaft L genau dann, wenn alle Infima für beschränkte, nichtleere Teilmengen existieren. Zur Eigenschaft BC korrespondiert die Existenz von Infima aller nichtleeren Teilmengen.

Die Bedingung d ist gleichwertig dazu, daß alle Hauptideale distributive, vollständige Verbände sind, in denen die Suprema mit denen in der ganzen dcpo übereinstimmen.

Definition 1.4. Ein ω-algebraischer BC-Bereich heißt Scott-Bereich.

Proposition 1.5. Werden in einer L-dcpo D zwei Elemente x_{1}, x_{2} von y und z beschränkt, und gilt y ⊑ z, dann stimmen die Suprema x_{1} ⊔^{y} x_{2} in ↓y und x_{1} ⊔^{z} x_{2} in ↓z überein.

Beweis. Wegen ↓y ⊆ ↓z gilt allemal x_{1} ⊔^{y} x_{2} ⊒ x_{1} ⊔^{z} x_{2}. Somit liegt x_{1} ⊔^{z} x_{2} unter

y, und es folgt x_{1} ⊔^{y} x_{2} ⊑ x_{1} ⊔^{z} x_{2}.

Korollar 1.6. Sei D eine L-dcpo und x_{1} ⊔^{y} x_{2} ⊑ z, z′. Dann gilt x_{1} ⊔^{z} x_{2} =

x_{1} ⊔^{y} x_{2} = x_{1} ⊔^{z′} x_{2}.

Proposition 1.7. Seien x_{1} und x_{2} kompakte Elemente eines stetigen L-Bereichs D und y eine obere Schranke für x_{1} und x_{2}. Dann ist x_{1} ⊔^{y} x_{2} kompakt.

Beweis. Sei G ⊆ D eine gerichtete Menge mit ^{⨆↑} G = x_{1} ⊔^{y} x_{2} ⊒ x_{1}, x_{2} — da D stetig ist, können wir uns auf solche gerichteten Mengen beschränken, um die Kompaktheit von x_{1} ⊔^{y} x_{2} zu zeigen (siehe [AJ95, Proposition 2.2.17.1]). Da x_{1} und x_{2} kompakt sind, gibt es Elemente g_{1}, g_{2} ∈ G mit g_{1} ⊒ x_{1} und g_{2} ⊒ x_{2}. Wegen der Gerichtetheit von G gibt es ein Element g ∈ G mit g ⊒ g_{1}, g_{2}. Also ist g eine obere Schranke von x_{1} und x_{2}. Da g in ↓y liegt, folgt g ⊒ x_{1} ⊔^{y} x_{2}, und x_{1} ⊔^{y} x_{2} ist kompakt.

Bei stetigen Bereichen ist die Schnittoperation ⊓ im folgenden Sinn stetig:

Proposition 1.8. Sei I eine gerichtete Menge und sowohl (x_{i})_{i∈I} als auch (y_{i})_{i∈I} monotone Netze in einem stetigen Bereich, so daß für alle i ∈ I das Infimum x_{i} ⊓ y_{i} existiert. Dann ist ^{⨆↑}(x_{i} ⊓ y_{i}) das Infimum von ^{⨆↑} x_{i} und ^{⨆↑} y_{i}.

Beweis. Aufgrund der Monotonie von ⊓ ist die Menge {x_{i} ⊓ y_{i} | i ∈ I} gerichtet und das Supremum ^{⨆↑}(x_{i} ⊓y_{i}) existiert. Sei nun z eine untere Schranke von ^{⨆↑} x_{i} und ^{⨆↑} y_{i} und z′ ≪ z ⊑ ^{⨆↑} x_{i},^{⨆↑} y_{i}. Dann gibt es Indizes i und j mit z′ ⊑ x_{i}, y_{j}. Wegen der Gerichtetheit der beiden Ausgangsmengen muß es auch ein k ∈ I mit z′ ⊑ x_{k}, y_{k} geben. Also gilt z′ ⊑ x_{k} ⊓ y_{k} ⊑ ^{⨆↑}(x_{i} ⊓ y_{i}). Da der Bereich als stetig vorausgesetzt ist, folgt damit schon z ⊑ ^{⨆↑}(x_{i} ⊓ y_{i}).

Korollar 1.9. Sei D ein stetiger S-Bereich und x ∈ D. Dann ist die Abbildung ⊓: ↓x × ↓x → D stetig.

Beweis. Eine Abbildung aus einem Produkt von dcpo’s ist genau dann stetig, wenn sie in jeder Komponente stetig ist (siehe [AJ95, Lemma 3.2.6]). Sei deshalb G ⊆ ↓x gerichtet und y ⊑ x. Dann folgt aus dem vorangegangenen Satz (^{⨆↑} G) ⊓ y = ^{⨆↑}{g ⊓ y | g ∈ G}.

Wie in der Einleitung erwähnt, betrachtet man faktorisierte Bereiche, um die Theorie der Scott-stetigen und der stabilen Funktionen in einem gemeinsamen Rahmen behandeln zu können. Da die stabilen Funktionen etwas weniger gebräuchlich sind als die Scott-stetigen, wollen wir hier die grundlegenden Definitionen und Ergebnisse angeben.

Definition 1.10. Eine Funktion zwischen S-dcpo’s heißt stabil, wenn sie stetig ist und beschränkte binäre Infima erhält, d.h. für x_{1}, x_{2} ⊑ y gilt f(x_{1}⊓x_{2}) = f(x_{1}) ⊓ f(x_{2}).

Proposition 1.11. Sei D ein algebraischer SI_{1}-Bereich. Dann ist eine stetige Abbildung f: D → E genau dann stabil, wenn es zu jedem x ∈ D und jedem y ∈ K_{f(x)} ein kleinstes x′ ⊑ x mit f(x′) ⊒ y gibt.

Dieses kleinste Element x′ ist automatisch kompakt.

Beweis. Angenommen es gebe zu jedem x und y ∈ K_{f(x)} ein solches kleinstes Element. Seien x_{1} und x_{2} von x beschränkt. Wegen der Monotonie von f gilt f(x_{1}⊓x_{2}) ⊑ f(x_{1}) ⊓ f(x_{2}). Zu jedem kompakten k ⊑ f(x_{1}) ⊓ f(x_{2}) gibt es unter x nach Voraussetzung ein kleinstes Element x′ mit f(x′) ⊒ k. Dieses Element muß unter x_{1} und x_{2} liegen, also liegt es auch unter x_{1} ⊓ x_{2}. Daraus folgt mit der Monotonie f(x_{1}⊓x_{2}) ⊒ f(x′) ⊒ k. Da dies für jedes k ∈ K_{f(x_{1})⊓f(x_{2})} erfüllt ist, gilt f(x_{1}⊓x_{2}) ⊒ f(x_{1}) ⊓ f(x_{2}).

Sei nun umgekehrt f stabil, x ∈ D beliebig und y ∈ K_{f(x)}. Da D algebraisch und f stetig ist, gibt es kompakte Elemente unter x, deren Bilder über y liegen. Sei x_{1} ein solches Element. Ist es noch nicht das kleinste solche, dann gibt es noch ein weiteres Element x̃_{1} ∈ K_{x} mit x_{1} ⋢ x̃_{1} und f(x̃_{1}) ⊒ y. Da x aber die beiden Elemente beschränkt und stabile Funktionen beschränkte Infima erhalten, folgt f(x_{1} ⊓ x̃_{1}) = f(x_{1}) ⊓ f(x̃_{1}) ⊒ y ⊓ y = y. Wieder aufgrund der Algebraizität von D gibt es dann ein kompaktes Element x_{2} unter x_{1} ⊓ x̃_{1} mit f(x_{2}) ⊒ y. Wegen x_{1} ⋢ x̃_{1} gilt x_{2} ⊏ x_{1}. Also kann man mit diesem Argument iterativ eine absteigende Kette von kompakten Elementen erzeugen. Da D ein I_{1}-Bereich ist, gibt es ein kleinstes Element.

Um die letzte Behauptung zu zeigen, überlegen wir, daß jedes minimale x, dessen Bild über einem kompakten Element y liegt, bereits kompakt sein muß. Es gilt y ⊑ f(x) = f(^{⨆↑} K_{x}) = ^{⨆↑} f[K_{x}]. Da y kompakt ist, gilt bereits für ein kompaktes x′ ⊑ x die Beziehung f(x′) ⊒ y. Aus der Minimalität von x schließen wir x = x′.

Bemerkung. Im vorangegangenen Beweis wurde die absteigende Kettenbedingung nur für die Rückrichtung benötigt.

Definition 1.12. Zwei stabile Funktionen f, g: D → E zwischen S-dcpo’s heißen vergleichbar in der Berry-Ordnung f ≤_{b} g genau dann, wenn f punktweise kleiner als g ist und für alle x ⊑ y die Gleichung f(x) = f(y) ⊓ g(x) gilt.

Proposition 1.13. Die Kategorie der dI-Bereiche mit den stabilen Funktionen als Morphismen ist kartesisch abgeschlossen. Die Ordnung auf dem Exponential ist die Berry-Ordnung.

Beweis. Siehe z.B. [Gun92, 5.2].

Zum Schluß wollen wir noch einige weitergehende topologische Eigenschaften betrachten, um diese für die Beschreibung von faktorisierten Bereichen im nächsten Kapitel zur Verfügung zu haben.

Definition 1.14. Die Lawson-Topologie ist die gemeinsame Verfeinerung der Scott-Topologie und der oberen (von Komplementen der Mengen ↑x erzeugten) Topologie.

Eine Basis der Lawson-Topologie sind die Mengen der Form U \ ⋃_{i=1}^{n} ↑x_{i}, wobei U eine Scott-offene Menge ist.

Proposition 1.15. Jede Lawson-abgeschlossene Teilmenge einer dcpo D ist ⨆↑-abgeschlossen (admissable).

Für eine L-dcpo sind die Lawson-abgeschlossenen Teilmengen zusätzlich gegen gefilterte Infima abgeschlossen.

Beweis. Die Scott-abgeschlossenen Mengen und die der Form ↑x bilden eine Subbasis für die Lawson-abgeschlossenen Mengen und sind zusätzlich gegen gerichtete Suprema abgeschlossen. Daß der Schnitt von^{⨆↑}-abgeschlossenen Mengen wieder ^{⨆↑}-abgeschlossen ist, ist klar. Wir werden nun zeigen, daß dies auch für die Vereinigung zweier ^{⨆↑}-abgeschlossenen Mengen gilt. Seien dazu A_{1} und A_{2} solche Mengen und G ⊆ A_{1} ∪ A_{2} gerichtet. Angenommen es gibt ein x ∈ G, so daß ↑x ∩ G ⊆ A_{1}, dann gilt ^{⨆↑} G ∈ A_{1}. Andernfalls ist G ∩ A_{2} kofinal in G und es folgt ^{⨆↑} G ∈ A_{2}. In beiden Fällen liegt das Supremum also wieder in A_{1} ∪ A_{2}.

In einem L-Bereich existieren alle gefilterten Infima. Wegen des Dualitätsprinzips für geordnete Mengen sind beliebige Schnitte und Vereinigungen zweier gegen gefilterte Schnitte abgeschlossener Mengen wieder solche. Scott-abgeschlossene Mengen sind als untere Mengen gegen gefilterte Infima abgeschlossen, Hauptfilter ↑x ebenfalls. Also folgt wie oben, daß Lawson-abgeschlossene Mengen gegen gefilterte Infima abgeschlossen sind.

Korollar 1.16. Eine Lawson-abgeschlossene untere Teilmenge einer dcpo ist Scott-abgeschlossen, eine Lawson-offenen obere Teilmenge Scott-offen.

Beweis. Sei U eine Lawson-abgeschlossene untere Menge. Nach Proposition 1.15 ist U gegen gerichtete Suprema abgeschlossen und somit Scottabgeschlossen. Eine Lawson-offenen obere Menge ist das Komplement einer Lawson-abgeschlossenen unteren, also einer Scott-abgeschlossenen Menge und damit selbst Scott-offen.

Proposition 1.17. Sei f: L → L′ eine Abbildung zwischen vollständigen Verbänden, die binäre Infima erhält. Dann ist f genau dann Lawson-stetig, wenn f beliebige nichtleere Infima und gerichtete Suprema erhält.

Beweis. Angenommen f erhält gerichtete Suprema und nichtleere Infima. Dann ist f Scott-stetig, also sind Urbilder Scott-abgeschlossener Mengen Scottund somit Lawson-abgeschlossen. Sei x ∈ L_{2} und f^{−1}[↑x] ≠ ∅. Nach Voraussetzung gilt f(⨅ f^{−1}[↑x]) = ⨅ f[f^{−1}[↑x]] ⊒ x. Also hat f^{−1}[↑x] ein kleinstes Element ⨅ f^{−1}[↑x] und ist somit Lawson-abgeschlossen. Das zeigt, daß f Lawson-stetig ist.

Sei umgekehrt f Lawson-stetig. Die Abbildung f erhält nach Voraussetzung binäre Infima und ist somit monoton. Sei G ⊆ L gerichtet. Wegen der Monotonie gilt f(^{⨆↑} G) ⊒ ^{⨆↑} f[G]. Die Menge ↓ {^{⨆↑} f[G]} ist Scott-abgeschlossen. Da f Lawson-stetig und monoton ist, ist f^{−1}[↓ {^{⨆↑} f[G]}] eine Lawsonabgeschlossene untere Menge, die G enthält. Nach Proposition 1.15 gilt deshalb ⨆↑ G ∈ f^{−1}[↓{^{⨆↑} f[G]}] und somit f(^{⨆↑} G) ⊑ ^{⨆↑} f[G]. Also erhält f gerichtete Suprema.

Da Hauptfilter Lawson-abgeschlossen und Lawson-abgeschlossene Mengen nach Proposition 1.15 gegen gefilterte Infima abgeschlossen sind, kann man dieses Argument dualisieren und sieht, daß f gefilterte Infima erhält.

Jedes nichtleere Infimum kann man umschreiben als gefiltertes Infimum der endlichen Teilinfima. Da die Funktion f binäre und gefilterte Infima erhält, muß sie deshalb auch beliebige nichtleere Infima erhalten.

Bei endlichen Produkten von stetigen Bereichen ist die Approximationsordnung ≪ komponentenweise gegeben. Für die Teil-dcpo ⊑ der geordneten Paare ist dies auch der Fall, wie wir im folgenden sehen werden:

Lemma 1.18. Sei D ein stetiger Bereich mit Basis B. Jedes Paar (x ⊑ y) ist gerichtetes Supremum von Paaren (x′ ⊑ y′) mit x′ ∈ B_{x} und y′ ∈ B_{y}.

Beweis. Sei G := (B_{x} × B_{y}) ∩ ⊑_{D}. Wir überlegen zuerst, daß G gerichtet ist. Seien (x′ ⊑ y′) und (x′′ ⊑ y′′) aus G. Da B_{x} gerichtet ist, gibt es ein x̃ mit x′, x′′ ⊑ x̃ ∈ B_{x}. Wegen ^{⨆↑} B_{y} = y ⊒ x gibt es ein ỹ ∈ B_{y} mit x̃, y′, y′′ ⊑ ỹ.

Somit ist noch ^{⨆↑} G = (x ⊑ y) zu zeigen. Dazu betrachten wir die Elemente aus G komponentenweise. Für jedes x′ ∈ B_{x} gilt auch x′ ∈ B_{y}, d.h. (x′ ⊑ x′) ∈ G. Also erhält man als Supremum in der ersten Komponente x. Zu einem Element y′ ≪ y betrachtet man man ein beliebiges x′ ∈ B_{x} und schließt wie oben, daß es ein y′′ ∈ B_{y} mit y′′ ⊒ y′, x′ gibt. Also liegen die zweiten Komponenten von Elementen aus G kofinal in ↓ ↓y, und wir erhalten als Supremum in der zweiten Komponente y.

Lemma 1.19. Sei D ein stetiger Bereich. In ⊑_{D} gilt (x_{1} ⊑ y_{1}) ≪ (x_{2} ⊑ y_{2}) genau dann, wenn x_{1} ≪ x_{2} und y_{1} ≪ y_{2} gelten, d.h. die Approximationsordnung ist komponentenweise gegeben.

Beweis. Ist x_{1} ≪ x_{2} und y_{1} ≪ y_{2} mit x_{1} ⊑ y_{1} und x_{2} ⊑ y_{2}, dann gilt sicherlich (x_{1} ⊑ y_{1}) ≪ (x_{2} ⊑ y_{2}).

Sei deshalb umgekehrt (x_{1} ⊑ y_{1}) ≪ (x_{2} ⊑ y_{2}) und G eine gerichtete Menge in D mit ^{⨆↑} G = x_{2} — da D stetig ist, können wir uns zum Nachweis von x_{1} ≪ x_{2} auf solche gerichteten Mengen beschränken (siehe [AJ95, Proposition 2.2.17.1]). Die Menge G′ := {(x′ ⊑ y_{2}) | x′ ∈ G} ist gerichtet, und es gilt ⨆↑ G′ = (x_{2} ⊑ y_{2}). Also gibt es ein x′ ∈ G mit x′ ⊒ x_{1}. Für die zweite Komponente sei ^{⨆↑} G = y_{2}. Wir betrachten G′ := (↓ ↓x_{2} × G) ∩ ⊑_{D}. Daß diese Menge gerichtet ist und^{⨆↑} G′ = (x_{2} ⊑ y_{2}) gilt, sieht man genau wie im vorangegangenen Lemma. Also gibt es wieder ein Element y′ ∈ G mit y′ ⊒ y_{1}.

Korollar 1.20. Ist D ein stetiger bzw. algebraischer Bereich, dann ist auch ⊑_{D} stetig bzw. algebraisch.

Beweis. Die Behauptung folgt unmittelbar aus den Lemmata 1.18 und 1.19.

Proposition 1.21. Für einen stetigen Bereich D ist die Menge ⊑_{D} als Teilmenge des Bereichs D^{2} Lawson-abgeschlossen.

Beweis. Seien x ⋢ y beliebig. Wir werden nun eine Lawson-offene Umgebung von (x, y) bestimmen, die ⊑_{D} nicht trifft. Da D stetig ist, gibt es Elemente x′ ≪ x und y′ ≪ y mit x′ ⋢ y. Wir betrachten nun U := ↑ ↑(x′, y′) \ ↑(x′, x′). Da y ⋣ x′ aber (x′, y′) ≪ (x, y) gelten, ist (x, y) ∈ U. Angenommen es gäbe vergleichbare Elemente (x̃ ⊑ ỹ) ∈ U. Dann folgt aus x′ ≪ x̃ ⊑ ỹ auch ỹ ⊒ x′ im Widerspruch zur Definition von U. Also ist U eine offene Umgebung von (x, y), die ⊑_{D} nicht schneidet und ⊑_{D} somit Lawson-abgeschlossen.

1.2 Faktorisierungssysteme

Aus der Kategorie der Mengen, der Gruppen und vieler anderer konkreter Kategorien kennt man den Homomorphiesatz, der in dem folgenden Diagramm^{1} dargestellt ist:

1Dieses, wie alle folgenden Diagramme, sind mit Paul Taylor’s commutative diagrams, version 3.83 erstellt.

A  \overline{f  ^{}}B
[figure: ♮; ∀e; f̄; ∀m]
B/ ker(f)

C ^{∃!i^{}. . . . . . . . .} ; ≅

Die kanonische Zerlegung eines Homomorphismus f: A → B, nach dem Kern, faktorisiert ihn in einen Epi- und einen Monomorphismus f = f̄ ∘ ♮. Diese Faktorisierung ist insofern eindeutig, als es zu jeder anderen Zerlegung f = m ∘ e in einen Mono- und einen Epimorphismus einen eindeutigen Isomorphismus i mit i ∘ ♮ = e und m ∘ i = f̄ gibt.

Das gibt Anlaß zu der folgenden Definition für beliebige Kategorien:

Definition 1.22. Ein Faktorisierungssystem (E, M) auf einer Kategorie C besteht aus zwei Klassen von Morphismen E und M, so daß die folgenden Bedingungen erfüllt sind:

1. E und M enthalten alle Isomorphismen von C und sind gegen Komposition mit Isomorphismen abgeschlossen,

2. M ∘ E = Mor(C), d.h. jeder Morphismus läßt sich in einen aus E gefolgt von einem aus M zerlegen,

3. (diagonal fill-in property) Für alle kommutativen Quadrate der Form

C \overline{∀m ∈ M_{}}D
.............. ∃!d
[figure: A; ∀; ∀e ∈ E; B; ∀]

gibt es einen eindeutigen Morphismus d: B → C, so daß die beiden Dreiecke kommutieren.

Im nächsten Kapitel werden wir den Sonderfall betrachten, in dem die Kategorien nur geordnete Mengen sind, wobei ein Morphismus von x nach y für x ⊑ y steht. Die Eigenschaften, die wir dort dauernd benutzen wollen, sind zum überwiegenden Teil Spezialfälle von Sätzen, die ganz allgemein für Faktorisierungssysteme gelten. Deshalb werden wir diese Eigenschaften nun für den allgemeinen Fall beweisen und später dann auf diese Resultate verweisen:

Proposition 1.23. Sei (E, M) ein Faktorisierungssystem auf einer Kategorie. Enthält M nur Monomorphismen oder E nur Epimorphismen und sind beide Klassen gegen Komposition abgeschlossen (d.h. E ∘ E = E und M ∘ M = M), dann ist die diagonal fill-in property äquivalent dazu, daß die Faktorisierung — wie oben beim Homomorphiesatz — ‘bis auf Isomorphie’ eindeutig ist.

Beweis. Enthalte E nur Epimorphismen. Hat man nun zwei Faktorisierungen m_{1} ∘ e_{1} = m_{2} ∘ e_{2}, so gibt es aufgrund der diagonal fill-in property Morphismen d

•  \overline{m_{1} ^{}}•
[figure: ..............; d; ..............; d′]
[figure: •; e_{1}; e_{2}; •; m_{2}]

und d′, die die Dreiecke kommutieren lassen. Man hat damit d∘d′∘e_{2} = d∘e_{1} = e_{2}. Da e_{2} ∈ E ein Epimorphismus ist, folgt d ∘ d′ = 1. Analog erhält man d′ ∘ d = 1, also sind d und d′ Isomorphismen.

Enthält M nur Monomorphismen, so folgt die gewünschte Implikation aufgrund des Dualitätprinzips, da (M, E) ein Faktorisierungssystem der dualen Kategorie ist.

Lasse sich nun umgekehrt jeder Morphismus eindeutig faktorisieren. Wir müssen nun für die entsprechenden Quadrate die diagonal fill-in property überprüfen. Dabei können wir die Seiten gleich als faktorisiert voraussetzen.

•  \overline{m ^{}}•

[figure: •; m_{2}; .; .; .; .; .; .; .; .; .; .; .; d ; ≅; •; m_{1}]

[figure: •; e_{2}; e; •; e_{1}]

Es gilt e_{1} ∘ e, e_{2} ∈ E und m ∘ m_{2}, m_{1} ∈ M. Wegen der Eindeutigkeit der Faktorisierung gibt es einen Isomorphismus d, so daß das untere und das obere Quadrat kommutieren. Damit gilt m_{2}∘d∘e_{1}∘e = m_{2}∘e_{2} und m∘m_{2}∘d∘e_{1} = m_{1}∘e_{1}. Ist e ein Epi- oder m eine Monomorphismus, so ist der diagonal fill-in m_{2} ∘ d ∘ e_{1} automatisch eindeutig.

Bemerkung. Diese Proposition zeigt, daß die aus der Algebra bekannten Beispiele, die man von den jeweiligen Homomorphiesätzen kennt, tatsächlich Faktorisierungssysteme im Sinne der allgemeinen Definition sind.

In Korollar 1.27 werden wir sehen, daß für beliebige Faktorisierungssysteme (E, M) die Klassen E und M immer gegen Komposition abgeschlossen sind. Diese Voraussetzung der Proposition 1.23 ist somit keine Einschränkung.

Auf jeder Kategorie gibt es immer die beiden trivialen Faktorisierungssysteme, bei denen man alle Morphismen entweder in E oder in M aufnimmt und in die jeweils andere Klasse nur die Isomorphismen. Diese spielen, wie wir später sehen werden, eine wichtige Rolle bei den Faktorisierungssystemen auf als Kategorie aufgefaßten Bereichen.

Eine der zentralen Eigenschaften von Faktorisierungssystemen ist, daß die eine Hälfte die andere bereits völlig bestimmt:

Proposition 1.24. Sei (E, M) ein Faktorisierungssystem auf einer Kategorie. Es gilt genau dann f ∈ E, wenn es für jedes kommutative Quadrat

• \overline{∀m ∈ M_{}}•
.............. ∃!d
[figure: •; ∀; f; •; ∀]

genau einen diagonal fill-in-Morphismus d gibt.

Beweis. Daß es zu jedem f ∈ E genau ein solches d gibt ist klar. Es bleibt also zu zeigen, daß jedes f, das die diagonal fill-in property erfüllt, bereits in M liegen muß. Dazu betrachten wir das folgende Diagramm:

•  \overline{m ^{}}•
.............. d
[figure: •; e; f; •; ‖ ; 1]

Dabei ist f = m∘e die Faktorisierung von f. Nach Voraussetzung gibt es einen Morphismus d mit m ∘ d = 1 und d ∘ f = e. Also gilt auch m ∘ d ∘ m = 1 ∘ m = m und d ∘ m ∘ e = d ∘ f = e. Somit hat man das kommutative Diagramm

•  \overline{m ^{}}•
[figure: d ∘ m]
[figure: •; e; e; •; m]

Aufgrund der Eindeutigkeit des diagonal fill-in-Morphismus, folgt d ∘ m = 1. Also ist m ein Isomorphismus. Da E gegen Komposition mit Isomorphismen abgeschlossen ist, liegt f = m ∘ e in E.

Aufgrund des Dualitätsprinzips für Kategorien erhält man sofort die duale Aussage:

Proposition 1.25. Sei (E, M) ein Faktorisierungssystem auf einer Kategorie. Es gilt genau dann f ∈ M, wenn es für jedes kommutative Quadrat

•  \overline{f ^{}}•
.............. ∃!d
[figure: •; ∀; ∀e ∈ E; •; ∀]

genau einen diagonal fill-in-Morphismus d gibt.

Aus diesen beiden Propositionen erhalten wir eine Reihe wichtiger Konsequenzen:

Korollar 1.26. Sei (E, M) ein Faktorisierungssystem. Dann enthält der Schnitt von E und M genau die Isomorphismen.

Beweis. Jeder Isomorphismus liegt nach Definition in E und in M. Sei deshalb umgekehrt f ∈ E ∩ M. Man betrachtet das folgende Diagramm:

•  \overline{f ^{}}•
.............. g
•^{1‖}  \overline{f ^{}}• ‖ ; 1

Da f ∈ E ∩ M liegt, gibt es einen diagonal fill-in-Morphismus g, der somit f ∘ g = 1 und g ∘ f = 1 erfüllt. Also ist f ein Isomorphismus.

Korollar 1.27. Für ein Faktorisierungssystem (E, M) sind die Klassen E und M gegen Komposition abgeschlossen.

Beweis. Seien f, g ∈ M. Wir werden nun zeigen, daß für beliebige Morphismen p, q und e mit e ∈ E sowie g ∘ f ∘ p = q ∘ e die diagonal fill-in property erfüllt ist.

[figure: •; f; •; g; •]
.................................. d′ ^{}.............. d
[figure: •; p; e ∈ E; •; q]

Da g ∈ M, gibt es ein eindeutiges d, und da auch f ∈ M, gibt es ein eindeutiges d′, so daß die entsprechenden Dreiecke kommutieren. Es gilt dann d′ ∘ e = p und g ∘ f ∘ d′ = g ∘ d = q. Somit ist nur noch die Eindeutigkeit von d′ zu zeigen. Sei dazu d̃ein weiterer Pfeil mit d̃∘ e = p und g ∘ f ∘ d̃= q. Aus der Eindeutigkeit von d folgt d = f ∘ d̃ und damit auch d′ = d̃.

Nach Proposition 1.25 ist somit g ∘ f ∈ M. Aus Dualitätsgründen folgt, daß auch E gegen Komposition abgeschlossen ist.

Wenn man Kategorien einsortig auffaßt, kann man mit Hilfe dieses Korollars die Definition von Faktorisierungssystemen etwas eleganter schreiben, indem man die erste Bedingung (scheinbar) verschärft: Ein Faktorisierungssystem besteht aus zwei Unterkategorien E und M. Diese enthalten alle Isomorphismen, jeder Morphismus aus der ursprünglichen Kategorie wird faktorisiert, d.h. er kann als Komposition von einem aus M nach einem von E dargestellt werden, und die diagonal fill-in property gilt.

Im folgenden werden wir Pushouts und dual dazu Pullbacks von Morphismen benötigen. Ist f ein Morphismus, so versteht man unter einem Pushout von f folgendes: Sei g mit dom(f) = dom(g) beliebig. Ist (f̄, ḡ) der Co-Limeskegel dieses

[figure: •; f̄; •; •; g; f; •; ḡ]

Pushout-Diagramms, so nennt man f̄ den Pushout von f.

Da Pushouts Co-Limites sind, folgt für beliebige, passende Morphismen h und h′ mit h ∘ f̄ = h′ ∘ f̄ und h ∘ ḡ = h′ ∘ ḡ die Gleichheit h = h′. Diese Eigenschaft von Co-Limites nennt man die jointly-epi-Eigenschaft.

Korollar 1.28. Sei (E, M) ein Faktorisierungssystem. Dann sind Pushouts von Morphismen aus E wieder in E — verkürzt sagt man auch Pushouts von E’s sind E’s.

Beweis. Zum Beweis betrachten wir folgendes Diagramm:

•  \overline{m ∈ M  ^{}}•
[figure: ..............; d; ..................................; d′]
[figure: •; p_{2}; f̄; •; q_{2}]
..............
[figure: •; p_{1}; f; •; q_{1}]

Wegen f ∈ E gibt es ein d mit m ∘ d = q_{2} ∘ q_{1} und d ∘ f = p_{2} ∘ p_{1}. Da das untere Quadrat ein Pushout ist, gibt es ein d′ mit d′ ∘ q_{1} = d und d′ ∘ f̄ = p_{2}. Daraus folgt m ∘ d′ ∘ f̄ = m ∘ p_{2} = q_{2} ∘ f̄ und m ∘ d′ ∘ q_{1} = m ∘ d = q_{2} ∘ q_{1}. Wegen der jointly-epi-Eigenschaft ist somit m ∘ d′ = q_{2}. Es verbleibt somit nur noch die Eindeutigkeit von d′ zu zeigen: Für jeden weiteren Morphismus d̃mit m ∘ d̃= q_{2} und d̃∘ f̄ = p_{2} folgt auch m ∘ d̃∘ q_{1} = q_{2} ∘ q_{1} und d̃∘ q_{1} ∘ f = d̃∘ f̄∘ p_{1} = p_{2} ∘ p_{1}. Aufgrund der Eindeutigkeit des diagonal fill-in ist damit d = d̃∘ q_{1}, und mit der jointly-epi-Eigenschaft hat man d′ = d̃.

Mit diesem Satz hat man auch gleich die duale Aussage:

Korollar 1.29. Für ein Faktorisierungssystem (E, M) sind die Pullbacks von M’s wieder M’s.

18

2 Faktorisierungssysteme auf Bereichen

Divide et impera.

nach Ludwig XI

Die Begriffe und Ergebnisse über Faktorisierungssysteme aus dem vorangegangenen Kapitel lassen sich auf geordnete Mengen übertragen, indem man diese als Kategorien auffaßt. Da geordnete Menge sehr spezielle Kategorien sind, vereinfacht sich dabei einiges.

Wir werden untersuchen, wie man Faktorisierungssysteme erzeugen kann, und sehen, daß es für L-dcpo’s immer eine Vielzahl an Faktorisierungssystemen gibt.

Betrachtet man dcpo’s, so stellt man fest, daß Faktorisierungssysteme eine Reihe von wünschenswerten Eigenschaften im allgemeinen nicht haben, z.B. ist die Faktorisierungsabbildung nicht Scott-stetig. Kann man ein Faktorisierungssystem von einer Basis auf den ganzen Bereich fortsetzen, so ist diese Fortsetzung nicht eindeutig.

Deshalb werden wir mehrere äquivalente Bedingungen dafür formulieren, daß die zusätzliche Struktur der dcpo mit dem Faktorisierungssystem zusammenpaßt. In den folgenden Kapiteln werden wir dann nur noch in dieser Weise faktorisierte dcpo’s betrachten.

2.1 Faktorisierungssysteme auf geordneten Mengen

Jede geordnete Menge (P, ⊑) kann man unmittelbar als Kategorie auffassen: Dazu nimmt man als Objekte die Elemente aus P und als Morphismen x → y vergleichbare Elemente (x ⊑ y). Damit kann man die Ergebnisse aus dem Abschnitt 1.2 direkt auf geordnete Mengen übertragen. Für die Definition verwenden wir gleich die vereinfachte Fassung, die sich aus Proposition 1.23 ergibt:

Definition 2.1. Sei (P, ⊑_{P}) eine geordnete Menge. Ein Faktorisierungssystem (E, M) auf P besteht aus zwei Teilordnungen M und E von ⊑_{P}, so daß es für alle x ⊑ y genau ein a mit (x, a) ∈ E und (a, y) ∈ M gibt — d.h. ⊑_{P} = E ∘ M —, und diese Faktorisierung ist eindeutig.

Wir schreiben als Abkürzung x ≤^{E} y für (x, y) ∈ E, analog für M, und benutzen auch die entsprechenden ‘größer-gleich’-Zeichen.

Den Punkt a, der bei der Faktorisierung von x ⊑ y auftritt, bezeichnen wir mit x\y. Es gilt also x ≤^{E} x\y ≤^{M} y. Gelegentlich werden wir die Faktorisierung auch als Abbildung (·\·): ⊑_{P} → P von den in der Ordnungsrelation stehenden Paaren nach P auffassen.

Nach Proposition 1.23 gilt für alle a, b, c, d mit a ≤^{E} b ⊑ d und a ⊑ c ≤^{M} d

[figure: • d; M; c •; ..........; • b; E; a •]  (♢)

wegen der Eindeutigkeit der Faktorisierung die ‘diagonal-fill-in-Beziehung’ b ⊑ c.

Aus dieser Bedingung, die wir im folgenden mit “♢” bezeichnen wollen, kann man eine Galois-Verbindung gewinnen:

Definition 2.2. Sei (P, ⊑_{P}) eine geordnete Menge und R eine beliebige Teilrelation von ⊑_{P}. Wir setzen

R^{↑}:={(x ⊑ y) | (∀(a, b) ∈ R) a ⊑ x, b ⊑ y ⇒ b ⊑ x}

und

R^{↓}:={(x ⊑ y) | (∀(a, b) ∈ R) x ⊑ a, y ⊑ b ⇒ y ⊑ a}.

[figure: • y  • ∀b; R^{↑}; R; x •  ∀a •; ..........  ..........; • ∀b  • y; R; R^{↓}; ∀a •  x•]

Wenn die Bedeutung aus dem Kontext hervorgeht, benutzen wir R′ anstelle von R^{↑} und R^{↓}.

Bemerkung 2.3. Es gelten R ⊆ S ⇒ S′ ⊆ R′ und R ⊆ R^{↑↓} bzw. R ⊆ R^{↓↑}. Somit ist (·^{↑}, ·^{↓}) eine Galois-Verbindung auf den Teilrelationen von ⊑_{P}.

Bei den Beweisen der Korollare 1.27, 1.28 und 1.29 haben wir die Voraussetzung, daß (E, M) ein Faktorisierungssystem ist, nicht voll ausgenutzt. Eigentlich haben wir gezeigt, daß E′ bzw. M′ gegen Komposition und Pushouts bzw. Pullbacks abgeschlossen sind.

Somit ist R′ für jede Teilrelation R der Ordnung ⊑_{P} transitiv. Wie man durch unmittelbares Nachprüfen der Definition sieht, ist R′ auch reflexiv, also eine Teilordnung von ⊑_{P}.

Mit dieser neuen Notation können wir für ein Faktorisierungssystem (E, M) die Propositionen 1.24 und 1.25 als M^{↓} = E und E^{↑} = M formulieren. Korollar 1.26 übersetzt sich in x ≤^{E} y, x ≤^{M} y ⇒ x = y. Zusammen mit den beiden äquivalenten Bedingungen für die Eindeutigkeit der Faktorisierung sind diese Beziehungen die zentralen Beweisprinzipien für Faktorisierungssysteme auf geordneten Mengen.

Den Pullbacks entsprechen bei den geordneten Mengen beschränkte binäre Schnitte, den Pushouts nach unten beschränkte binäre Suprema. Die Voraussetzung, daß die Elemente nach unten beschränkt sein müssen, ist trivialerweise erfüllt, wenn die geordnete Menge ein kleinstes Element hat.

Aus den Korollaren 1.28 und 1.29 wissen wir, daß Pushouts von E’s (oder

• x ⊔ y  •
[figure: ⇒ E; M]
x •  • y  x •  • y
[figure: E; M ⇐]
•  x ⊓ y •

allgemeiner von R^{↓}’s) wieder E’s (R^{↓}’s) und Pullbacks von M’s (R^{↑}’s) wieder M’s (R^{↑}’s) sind. Für den Fall, daß x und y vergleichbar sind, erhalten wir die beiden wichtigen Spezialfälle z ⊑ x ⊑ y und z ≤^{E} y impliziert x ≤^{E} y bzw. x ⊑ y ⊑ z und x ≤^{M} z impliziert x ≤^{M} y:

• y  z •
[figure: ⇒ E]
x •  • y
[figure: M ⇐]
• z E  x • M

Jetzt wollen wir einige fundamentale Eigenschaften von Faktorisierungssystemen auf geordneten Mengen und dcpo’s untersuchen:

Satz 2.4. Sei (P, ⊑_{P}) eine geordnete Menge mit einem Faktorisierungssystem (E, M). Dann ist die Faktorisierungsabbildung (·\·) in beiden Komponenten monoton und idempotent. In der ersten Komponente ist sie zusätzlich inflationär und in der zweiten deflationär, d.h. x ⊑ x\y bzw. x\y ⊑ y.

Beweis. Sei y beliebig und x ⊑ x′ ⊑ y.

y •  • y′
[figure: M]
• x′\y  y •  • x\y′ M
[figure: ..........; E; M; ..........]
x\y • M  • x′  x\y •
[figure: E]
x • E  • x E

Dann gilt x ≤^{E} x\y ⊑ y und x ⊑ x′ ⊑ x′\y ≤^{M} y. Wegen der Bedingung ♢ gilt somit x\y ⊑ x′\y. Die Monotonie von (·\·) in der zweiten Komponente erhält man durch Dualisieren.

Für alle x ⊑ y gilt x ≤^{E} x\y ≤^{M} y. Also hat man bereits eine Faktorisierung von x ⊑ x\y und x\y ⊑ y. Da die Faktorisierung aber eindeutig ist, folgt (x\y)\y = x\y und x\(x\y) = x\y. Damit ist die Faktorisierungsabbildung in beiden Komponenten idempotent.

Die letzte Behauptung folgt, da für alle x ⊑ y sogar die Beziehung x ≤^{E} x\y ≤^{M} y gilt.

Die folgende Beobachtung ist zwar elementar, aber später für einige Beweise sehr nützlich:

Lemma 2.5. Sei (P, ⊑_{P}) eine geordnete Menge mit einem Faktorisierungssystem (E, M). Dann gilt

x ≤^{E} y ⇔ x\y = y
x ≤^{M} y ⇔ x\y = x.

Bemerkung. Aus jeder Abbildung (· ⑊ ·): ⊑_{P} → P, die monoton, in beiden Komponenten idempotent, in der ersten inflationär und in der zweiten deflationär ist, kann man ein Faktorisierungssystem machen. Dazu verwendet man die beiden Äquivalenzen aus dem vorangegangenen Satz als Definition. Die zugehörige Faktorisierungsabbildung ist dann gerade (· ⑊ ·).

Satz 2.6. Sei D eine dcpo mit Faktorisierungssystem (E, M). Dann ist E ⊆ D^{2} gegen gerichtete Suprema abgeschlossen.

Beweis. Sei G:={(x_{i}, y_{i}) | i ∈ I} eine gerichtete Teilmenge von E. Wir betrachten nun a ≤^{M} b mit^{⨆↑} x_{i} ⊑ a und^{⨆↑} y_{i} ⊑ b. Wegen ♢ gilt y_{i} ⊑ a für alle i ∈ I. Damit

• b

[figure: M]

a •

.......... . . . . . . . . . . . . . . . . . . . .

•^{⨆↑} y_{i}
[figure]
⨆↑ x^{i} •  • y_{i}

[figure: E]

xi •

haben wir auch ^{⨆↑} y_{i} ⊑ a, und (^{⨆↑} x_{i},^{⨆↑} y_{i}) ∈ E folgt nach Bemerkung 2.3.

2.2 Erzeugung von Faktorisierungssystemen

Aus dem Abschnitt 1.2 wissen wir, daß es auf jeder geordneten Menge immer die beiden trivialen Faktorisierungssysteme (⊑, =) und (=, ⊑) gibt. Es stellt sich nun die Frage, wie man weitere erhalten kann.

Dazu wird sich die Galois-Verbindung aus Definition 2.2 als sehr nützlich erweisen. Aus den Propositionen 1.24 und 1.25 ist bereits klar, daß man diese dazu benutzen kann, um den einen Teil eines Faktorisierungssystems aus dem anderen zurückzugewinnen. Für L-dcpo’s werden wir sehen, daß man mit dieser Galois-Verbindung zwei kanonische Methoden hat, aus einer beliebig gegebenen Unterrelation der Ordnung ein Faktorisierungssystem zu konstruieren.

Zunächst brauchen wir eine Verallgemeinerung von Korollar 1.29 auf unendliche Schnitte:

Lemma 2.7. Sei (P, ⊑_{P}) eine geordnete Menge, R eine Teilrelation von ⊑_{P}, y ∈ P und X eine nichtleere Teilmenge von P, so daß alle Elemente aus X in R^{↑}-Relation zu y stehen — in Zeichen X ≤^{R′} y. Hat X ein Infimum, dann gilt ⨅ X ≤^{R′} y.

Beweis. Wir betrachten a ≤^{R} b mit a ⊑ ⨅ X und b ⊑ y. Da für jedes x ∈ X die

• y
[figure: R′]
X ∋ x′ • … • x R′
[figure: ....................]
⨅ X •  • b
[figure: R]
a •

Beziehung x ≤^{R′} y gilt, folgt b ⊑ x und somit b ⊑ ⨅ X, was ⨅ X ≤^{R′} y zeigt.

Korollar 2.8. Sei D eine L-dcpo und ∅ ≠ X ≤^{M} y. Dann ist ⨅ X ≤^{M} y.

Satz 2.9. Sei D eine L-dcpo und R eine beliebige Teilrelation von ⊑_{D}. Dann ist (R^{↑↓}, R^{↑}) ein Faktorisierungssystem.

Beweis. Wie wir schon in Bemerkung 2.3 gesehen haben, sind R′ und R′′ Teilordnungen von ⊑_{D}. Da (·^{↑}, ·^{↓}) eine Galois-Verbindung ist, erfüllt (R′′, R′) die Bedingung ♢. Es bleibt also nur zu zeigen, daß ⊑_{D} = R′′ ∘ R′ ist:

Sei daher x ⊑ y beliebig und z das Infimum aller Elemente z′ mit x ⊑ z′ ≤^{R′} y. Nach Lemma 2.7 gilt dann auch x ⊑ z ≤^{R′} y. Somit ist z das kleinste Element R′-unter y, das noch über x liegt. Wir behaupten nun x ≤^{R′′} z. Um das zu zeigen, wählen wir a ≤^{R′} b beliebig mit x ⊑ a und z ⊑ b. Da Pullbacks von R′’s wieder

• b
[figure: R′]
a •  • y
[figure: ....................; R′]
• z
[figure: R′]
• a ⊓ z
[figure]
x •

in R′ sind (vgl. Bemerkung 2.3), gilt x ⊑ (a ⊓ z) ≤^{R′} z ≤^{R′} y. Die Ordnung R′ ist transitiv, und z ist das kleinste Element zwischen x und y, das R′-unter y liegt. Also gilt z = (a ⊓ z) und mithin z ⊑ a, was x ≤^{R′′} z zeigt.

Wenn für jede Teilrelation R der Ordnung (R′′, R′) ein Faktorisierungssystem ist, liegt es nahe (R′, R′′) zu betrachten. Das Analogon zu Satz 2.9 läßt sich tatsächlich zeigen; da in L-dcpo’s aber nur lokale beschränkte Suprema existieren, ist der Beweis technisch etwas komplizierter, obwohl die Beweisidee dieselbe ist. Wir beginnen mit einigen Vorüberlegungen:

Lemma 2.10. Sei D eine L-dcpo und R eine beliebige Teilrelation von ⊑_{D}. Ist

x ⊑ y_{1} ⊑ z und x ≤^{R^{↓}} y_{2} ⊑ z, dann gilt y_{1} ≤^{R^{↓}} (y_{1} ⊔^{z} y_{2}).

b •  • z
[figure: R]
a •

[figure: ^{.........................}]• y_{1} ⊔^{z} y_{2}

[figure]
y^{1} •  • y_{2}
[figure: R′]
x •

Beweis. Seien a ≤^{R} b mit y_{1} ⊑ a und (y_{1} ⊔^{z} y_{2}) ⊑ b. Die beiden beschränkten

Suprema (y_{1}⊔^{z}y_{2}) und (y_{1}⊔^{b}y_{2}) stimmen nach Korollar 1.6 überein. Wegen x ≤^{R′} y_{2}

gilt y_{2} ⊑ a. Daraus erhält man nun sofort (y_{1} ⊔^{b}y_{2}) ⊑ a und somit y_{1} ≤^{R′} (y_{1} ⊔^{z} y_{2}).

Dieses Lemma hat auch eine Fassung für unendliche Suprema:

Lemma 2.11. Sei D eine L-dcpo, R eine beliebige Teilrelation von ⊑_{D}. Ferner seien x, z ∈ D und Y eine nichtleere Menge mit x ≤^{R^{↓}} Y ⊑ z. Dann gilt

x ≤^{R^{↓}} ⨆^{z}Y.

Beweis. Sei wieder a ≤^{R} b mit x ⊑ a und ⨆^{z}Y ⊑ b. Wie im vorangegangenen

Lemma sieht man ⨆^{z}Y = ⨆^{b}Y. Da alle y ∈ Y die Bedingung x ≤^{R′} y ⊑ ⨆^{z}Y ⊑ b

erfüllen, liegen sie alle unter a. Also folgt ⨆^{z}Y ⊑ a.

Satz 2.12. Sei D eine L-dcpo und R eine beliebige Teilrelation von ⊑_{D}. Dann ist (R^{↓}, R^{↓↑}) ein Faktorisierungssystem.

Beweis. Wie im Beweis von Satz 2.9 müssen wir nur ⊑ = R′ ∘ R′′ zeigen.

Sei daher x ⊑ y beliebig und z das Supremum aller Elemente z′ mit x ≤^{R′} z′ ⊑ y. Nach Lemma 2.11 ist x ≤^{R′} z ⊑ y. Es bleibt z ≤^{R′′} y zu zeigen. Sei deshalb a ≤^{R′} b mit a ⊑ z und b ⊑ y beliebig. Nach Lemma 2.10 ist

• y
[figure]
z ⊔^{y} b •
[figure: R′]
z •
[figure: R′; ....................]
x •  • b
[figure: R′]
• a

x ≤^{R′} z ≤^{R′} z ⊔^{y} b und somit z ⊔^{y} b = z, da z bereits das größte solche Element ist. Also ist z ⊒ b, was z ≤^{R′′} y zeigt.

Jetzt wollen wir noch untersuchen, wie man die Sätze 2.9 und 2.12 verwenden kann, um Fortsetzungen von Faktorisierungssystemen zu konstruieren:

Korollar 2.13. Sei D eine L-dcpo, Q ⊆ D und (E, M) ein Faktorisierungssystem auf Q bezüglich der induzierten Ordnung. Dann sind (E^{↑↓}, E^{↑}) und (M^{↓}, M^{↓↑}) Faktorisierungssysteme auf D, die (E, M) fortsetzen, d.h. es gilt für alle x, y ∈ Q die Äquivalenz x ≤^{E^{↑↓}} y ⇔ x ≤^{M^{↓}} y ⇔ x ≤^{E} y und x ≤^{M^{↓↑}} y ⇔ x ≤^{E^{↑}} y ⇔ x ≤^{M} y.

Beweis. Daß (E′′, E′) und (M′, M′′) Faktorisierungssysteme sind, folgt aus den Sätzen 2.9 und 2.12.

Für beliebige Teilrelationen R gilt R ⊆ R′′, und da (E, M) ein Faktorisierungssystem auf Q ist, gilt zusätzlich M ⊆ E′ und E ⊆ M′.

Ist (x ≤^{E′′} y) ∈ Q^{2}, dann erfüllt es mit allen (a ≤^{E′} b) ∈ Q^{2} die Bedingung ♢. Aus M ⊆ E′ folgt x ≤^{E} y, da (E, M) ein Faktorisierungssystem auf Q ist.

Ebenso erfüllen alle Paare (x, y) aus Q^{2}, die E′-vergleichbar sind, mit allen E′′-vergleichbaren die Bedingung ♢. Darunter sind im besonderen die E-vergleichbaren aus Q^{2}, also folgt x ≤^{M} y. Somit ist die gewünschte Fortsetzungseigenschaft für (E′′, E′) gezeigt.

Den Fall (M′, M′′) beweist man analog.

Im nächsten Abschnitt werden wir ein Beispiel dafür sehen, daß die beiden Fortsetzungen aus dem vorangegangenen Korollar im allgemeinen nicht übereinstimmen.

2.3 Stetige Faktorisierungen

Da ein stetiger Bereich keine kanonische Basis hat, kann man nicht erwarten, daß die Einschränkung eines Faktorisierungssystems des Bereichs auf eine Basis B wieder ein Faktorisierungssystem ist. Liegen nämlich x und y in B, nicht aber x\y, so kann man x ⊑ y nicht mit Basiselementen faktorisieren. Auch im algebraischen Fall wird die Situation nicht besser, wie das folgende Beispiel zeigt:

\begin{matrix}• & ω + 1 \\ • ω & M \\ • 2 & E \\ • 1 & E \\ • 0 & E \end{matrix}

Wir betrachten das durch x ≤^{E} y :⇔ x ⊑ y ⊑ ω und ω ≤^{M} ω + 1 gegebene Faktorisierungssystem. Alle Elemente außer ω sind kompakt. Wegen 0 ≤^{E} ω ≤^{M} ω + 1 läßt sich aber 0 ⊑ ω + 1 in den kompakten Elementen nicht faktorisieren.

Aus Korollar 2.13 wissen wir, daß man wenigstens für L-Bereiche Faktorisierungssysteme fortsetzen kann. Da wir zu einem gegebenen Faktorisierungssystem (E, M) immer (E′′, E′) und (M′, M′′) als Fortsetzung wählen können, liegt die Vermutung nahe, daß die Fortsetzung im allgemeinen nicht eindeutig ist. Um diese Vermutung zu verifizieren, verwenden wir wieder den Bereich von oben:

• ω + 1  • ω + 1
• ω M  • ω E

• 2 M  • 2 M
• 1 M  • 1 M
• 0 M  • 0 M

Wir betrachten die beiden folgenden Faktorisierungssysteme: Zum einen das triviale mit x ≤^{E} y :⇔ x = y und x ≤^{M} y :⇔ x ⊑ y. Das zweite geht aus diesem hervor, indem man ω ≰^{M} ω + 1 und ω ≤^{E} ω + 1 setzt. Eingeschränkt auf die kompakten Elemente erhält man in beiden Fällen das triviale Faktorisierungssystem (=, ⊑). Aus diesem kann man die beiden als (=′′, =′) und (⊑′, ⊑′′) zurückgewinnen.

Das erste dieser beiden Faktorisierungssysteme hat eine Reihe guter Eigenschaften, die das zweite nicht hat: Die Menge M ist ^{⨆↑}-abgeschlossen; im zweiten Fall gilt das nicht, da ^{⨆↑}_{n∈N}(n, ω + 1) = (ω, ω + 1) ∉ M. Dieses gerichtete Supremum zeigt auch, daß in diesem Fall die Faktorisierungsabbildung nicht stetig ist. Für das erste Faktorisierungssystem ist dies gewährleistet, da es sich gerade um die Projektion auf die erste Komponente handelt. Ferner sind im ersten im Gegensatz zum zweiten Faktorisierungssystem alle E-vergleichbaren Elemente Supremum von solchen weit darunter.

Im folgenden werden wir nun untersuchen, wie diese Eigenschaften zusammenhängen:

Satz 2.14. Sei D eine dcpo mit Faktorisierungssystem (E, M). Genau dann ist die Faktorisierungsabbildung (·\·) stetig, wenn M als Teilmenge von D^{2} gegen gerichtete Suprema abgeschlossen ist.

Beweis. Sei (·\·) stetig und G = {(x_{i} ≤^{M} y_{i}) | i ∈ I} ⊆ M gerichtet. Nach Lemma 2.5 gilt x_{i}\y_{i} = x_{i} für alle i ∈ I. Aus der Stetigkeit von (·\·) folgt ⨆↑ x_{i} = ^{⨆↑}(x_{i}\y_{i}) = (^{⨆↑} x_{i})\(^{⨆↑} y_{i}) und somit ^{⨆↑} x_{i} ≤^{M} ^{⨆↑} y_{i}.

Sei umgekehrt M gegen gerichtete Suprema abgeschlossen. Aus Satz 2.4 wissen wir, daß (·\·) monoton ist. Sei {(x_{i} ⊑ y_{i}) | i ∈ I} eine gerichtete Menge in ⊑_{D}.

•^{⨆↑} y_{i}
[figure: M]
⨆↑(x^{i}\y^{i}) •
[figure: E]
⨆↑ x^{i} •  • y_{i}
[figure: M]
• x_{i}\y_{i}
[figure: E]
• x_{i}

Nach Voraussetzung ist M gegen gerichtete Suprema abgeschlossen, für E gilt das nach Satz 2.6 immer. Also haben wir ^{⨆↑} x_{i} ≤^{E} ^{⨆↑}(x_{i}\y_{i}) ≤^{M} ^{⨆↑} y_{i}, und wegen der Eindeutigkeit der Faktorisierung ist (^{⨆↑} x_{i})\(^{⨆↑} y_{i}) = ^{⨆↑}(x_{i}\y_{i}).

Für stetige Bereiche kommen zwei weitere äquivalente Bedingungen dazu: Satz 2.15. Für einen stetigen Bereich D mit Faktorisierungssystem (E, M) sind die folgenden Bedingungen äquivalent:

(i) Die Faktorisierungsabbildung (·\·) ist stetig, (ii) M ist ^{⨆↑}-abgeschlossen, (iii) Alle Paare (x ≤^{E} y) sind das gerichtete Supremum von Elementen

(x′ ≤^{E} y′) mit x′ ≪ x und y′ ≪ y, (iv) M ist Lawson-abgeschlossen. Beweis. Nach Satz 2.14 sind (i) und (ii) äquivalent.

Gelte (i) und sei x ≤^{E} y. Wir wollen (iii) zeigen. Setze G := ↓ ↓(x, y) ∩ ⊑_{D} = {(x_{i} ⊑ y_{i}) | i ∈ I}. Wegen Lemma 1.18 gilt ^{⨆↑} G = (x ⊑ y). Wir be-

y•
[figure: E]
x •  • y_{i} ‖

[figure: M]

• x_{i}\y_{i}
[figure: E]
•x_{i} ‖

trachten nun {(x_{i}, x_{i}\y_{i}) | i ∈ I}. Diese Menge ist gerichtet, da (·\·) monoton ist. Wegen der Stetigkeit der Faktorisierungsabbildung folgt ^{⨆↑}(x_{i}, x_{i}\y_{i}) = (^{⨆↑} x_{i},^{⨆↑}(x_{i}\y_{i})) = (x, (^{⨆↑} x_{i})\(^{⨆↑} y_{i})) = (x, x\y) = (x, y). Das zeigt (i)⇒(iii).

Wir zeigen nun, daß aus (iii) die Lawson-Abgeschlossenheit von M folgt: Sei dazu (x, y) ∉ M. Ist x ⋢ y, gibt es nach Proposition 1.21 eine Lawson-offene Menge, die (x, y) enthält und ⊑_{D} ⊆ M nicht schneidet. Wir können deshalb o.B.d.A. x ⊑ y annehmen. Wegen x ≰^{M} y erfüllt (x ⊑ y) nicht mit allen ‘passenden’ Paaren die Bedingung ♢. Es gibt deshalb Elemente x′ ≤^{E} y′ mit x′ ⊑ x,

• y
[figure]
x •  • y′
[figure: E]
x′ •  • y′′ ‖
[figure: E]
x′′ • ‖

y′ ⊑ y und y′ ⋢ x. Nach Voraussetzung ist (x′ ≤^{E} y′) das gerichtete Supremum von Elementen (x′′_{i} ≤^{E} y′′_{i}) weit darunter. Wegen y′ ⋢ x muß es dabei solche mit y′′_{i} ⋢ x geben. Für ein solches Element (x′′ ≤^{E} y′′) betrachten wir die Lawson-offene Menge U := ↑ ↑(x′′, y′′) \ ↑(y′′, y′′). Offenbar ist (x, y) ∈ U. Aus (x̃, ỹ) ∈ U ∩ M folgt mit der Bedingung ♢ die Beziehung y′′ ⊑ x̃, im Widerspruch zu (x̃, ỹ) ∈ U. Also gilt U ∩ M = ∅, was die Lawson-Abgeschlossenheit von M zeigt.

Nach Proposition 1.15 ist jede Lawson-abgeschlossene Menge gegen gerichtete Suprema abgeschlossen; aus (iv) folgt also (ii).

Die Bedingungen des vorangegangenen Satzes sagen aus, daß das Faktorisierungssystem mit der zusätzlichen Struktur einer dcpo zusammenpaßt. Deshalb werden wir im folgenden nur noch solche untersuchen.

Definition 2.16. Eine dcpo D mit Faktorisierungssystem (E, M) heißt faktorisierte dcpo, wenn die äquivalenten Bedingungen aus Satz 2.14 gelten.

Analog benutzen wir abgeleitete Begriffe wie faktorisierter Bereich, faktorisierter S-Bereich etc.

Ist das Faktorisierungssystem nicht explizit angegeben, so bezeichnen wir es im folgenden immer mit (E, M).

Aus Bemerkung 2.3 wissen wir, daß M = E′ gilt. Mit Hilfe von Satz 2.15 können wir ein besseres Kriterium dafür angeben, daß ein Paar (x ⊑ y) in M liegt:

Korollar 2.17. Sei D ein faktorisierter stetiger Bereich. Ein Paar (x ⊑ y) liegt genau dann in M, wenn für alle x′ ≤^{E} y′ mit x′ ≪ x und y′ ≪ y die Ungleichung y′ ⊑ x gilt.

Beweis. Ein Paar (x ≤^{M} y) erfüllt mit allen (x′ ≤^{E} y′) die Bedingung ♢, insbesondere also mit solchen, die weit darunter liegen.

Gelte umgekehrt für alle x′ ≤^{E} y′ mit x′ ≪ x und y′ ≪ y die Beziehung y′ ⊑ x. Wir zeigen nun (x ⊑ y) ∈ E′ = M (vgl. Bemerkung 2.3). Sei x̃ ≤^{E} ỹ mit x̃ ⊑ x und ỹ ⊑ y beliebig. Wegen der Bedingung (iii) aus Satz 2.15 ist (x̃ ≤^{E} ỹ)

• y
[figure]
x •

.......... . . . . . . . . . . . . . . . . . . . .

• ỹ

[figure: E]

x̃ •  • y′ ‖

[figure: E]

x′ • ‖

das gerichtete Supremum von Elementen (x′ ≤^{E} y′) mit x′ ≪ x̃ und y′ ≪ ỹ. Für jedes solche Element gilt nach Voraussetzung y′ ⊑ x. Da ỹ das Supremum dieser y′ ist, folgt ỹ ⊑ x und somit x ≤^{M} y.

Es stellt sich die Frage, ob man sich beim Überprüfen von x ≤^{M} y nach dem vorangegangenen Korollar auf Basiselemente weit darunter beschränken kann. Insbesondere für algebraische Bereiche ist dies interessant, da es für die von Lamarche betrachteten Bereichen gilt, und er davon in seiner Theorie auch Gebrauch macht. Es ist im Moment aber nicht bekannt, ob eine solche Verallgemeinerung von Korollar 2.17 im allgemeinen gilt.

Vermutung 2.18. Sei D ein faktorisierter algebraischer Bereich. Dann sind alle Paare (x ≤^{E} y) das gerichtete Supremum von Elementen (x′ ≤^{E} y′) mit kompaktem x′ und y′.

Definition 2.19. Einen faktorisierten algebraischen Bereich, der die Bedingung aus Vermutung 2.18 erfüllt, nennen wir einen kompakt faktorisierten Bereich.

Korollar 2.20. Sei D ein kompakt faktorisierter Bereich. Ein Paar (x ⊑ y) liegt genau dann in M, wenn für alle x′ ≤^{E} y′ mit kompaktem x′ ⊑ x und kompaktem y′ ⊑ y die Ungleichung y′ ⊑ x gilt.

Es stellt sich nun die Frage, wie man faktorisierte Bereiche konstruieren kann. Dazu können wir die Ergebnisse aus Abschnitt 2.2 benutzen.

Satz 2.21. Sei D ein algebraischer L-Bereich und R ⊆ (⊑_{D} ∩ K(D)^{2}) eine Teilordnung von ⊑_{D}, die nur kompakte Elemente vergleichbar macht. Dann ist (R^{↑↓}, R^{↑}) ein Faktorisierungssystem, das die äquivalenten Bedingungen aus Satz 2.15 erfüllt, d.h. das D zu einem faktorisierten Bereich macht.

Beweis. Nach Satz 2.9 ist (R′′, R′) ein Faktorisierungssystem. Wir zeigen, daß R′ gegen gerichtete Suprema abgeschlossen ist und das Faktorisierungssystem somit die Bedingung (ii) aus Satz 2.15 erfüllt:

Sei G = {(x_{i} ⊑ y_{i}) | i ∈ I} ⊆ R′ gerichtet und k ≤^{R} l mit k ⊑ ^{⨆↑} x_{i} und

•^{⨆↑} y_{i}
[figure]
⨆↑ x^{i} •  •y_{i}
[figure: R′][figure]
xi •
[figure: ....................]
• l
[figure: R]
• k

l ⊑ ^{⨆↑} y_{i}. Wegen der Kompaktheit von k und l gibt es einen Index i mit x_{i} ⊒ k und y_{i} ⊒ l. Da k ≤^{R} l und x_{i} ≤^{R′} y_{i} folgt l ⊑ x_{i} ⊑ ^{⨆↑} x_{i} aus der Bedingung ♢. Also gilt ^{⨆↑} G = (^{⨆↑} x_{i},^{⨆↑} y_{i}) ∈ R′.

Startet man mit einen Faktorisierungssystem auf den kompakten Elementen, so konstruiert man im vorangegangenen Satz eine Fortsetzung, wie wir aus Korollar 2.13 wissen. Deshalb können wir zeigen, daß dieses so erzeugte Faktorisierungssystem die Eigenschaft aus Vermutung 2.18 hat:

Korollar 2.22. Sei D ein algebraischer L-Bereich und (E, M) ein Faktorisierungssystem auf der Teilmenge der kompakten Elemente mit der induzierten Ordnung. Dann ist D mit (E^{↑↓}, E^{↑}) ein kompakt faktorisierter Bereich.

Beweis. Nach Korollar 2.13 ist (E′′, E′) eine Fortsetzung von (E, M). Wegen Satz 2.21 ist D damit ein faktorisierter Bereich und nach Satz 2.15 sind alle E-vergleichbaren Elemente somit das gerichtete Supremum von solchen weit darunter.

Wir können den Beweis von (i) ⇒ (iii) aus Satz 2.15 etwas verfeinern: Sei x ≤^{E} y. Dann ist (x ≤^{E} y) nach Lemma 1.18 das gerichtete Supremum der Menge G := {(x_{i}, y_{i}) | i ∈ I} = ⊑_{D} ∩ K^{2} ∩ ↓(x, y). Da (E, M) ein Faktorisierungssystem auf den kompakten Elementen ist, ist für kompakte Elemente x′ und y′ auch x′\y′ kompakt. Also enthält die Menge {(x_{i}, x_{i}\y_{i}) | i ∈ I} nur Paare E-vergleichbarer kompakter Elemente. Wie der Beweis von Satz 2.15 zeigt, ist (x ≤^{E} y) das gerichtete Supremum dieser Menge.

Satz 2.21 kann man leicht auf den stetigen Fall verallgemeinern:

Satz 2.23. Sei D ein stetiger L-Bereich und R eine Teilordnung von ⊑_{D}, so daß jedes (x, y) ∈ R das Supremum von (x′, y′) ∈ R mit x′ ≪ x und y′ ≪ y ist. Dann ist (R^{↑↓}, R^{↑}) ein Faktorisierungssystem, das D zu einem faktorisierten Bereich macht.

Beweis. Wie im Satz zuvor reicht es zu zeigen, daß R′ gegen gerichtete Suprema abgeschlossen ist. Sei deshalb G = {(x_{i} ⊑ y_{i}) | i ∈ I} ⊆ R′ gerichtet und a ≤^{R} b mit a ⊑ ^{⨆↑} x_{i} und b ⊑ ^{⨆↑} y_{i} beliebig. Jetzt ist (a ≤^{R} b) das Supremum von Elementen (a′ ≤^{R} b′) mit a′ ≪ a ⊑ ^{⨆↑} x_{i} und b′ ≪ b ⊑ ^{⨆↑} y_{i}. Also gibt es ein i ∈ I mit x_{i} ⊒ a′ und y_{i} ⊒ b′. Aus ♢ folgt damit b′ ⊑ ^{⨆↑} x_{i}, und da b das Supremum solcher b′ ist, erhält man b ⊑ ^{⨆↑} x_{i}. Somit ist (^{⨆↑} x_{i},^{⨆↑} y_{i}) ∈ R′.

Aus Korollar 1.20 wissen wir, daß ⊑_{D} für stetige faktorisierte Bereiche D immer stetig ist. Wegen den Sätzen 2.6 und 2.15 sind E und M dcpo’s, und die Suprema werden wie in ⊑_{D}, d.h. wie in D^{2} berechnet. Für faktorisierte Bereiche können wir mit Hilfe der Stetigkeit der Faktorisierungsabbildung weitere Aussagen über die Struktur von E und M machen:

Satz 2.24. Für einen faktorisierten stetigen Bereich sind sowohl E als auch M stetige Bereiche. Die Approximationsordnung auf E ist dabei von ⊑_{D} und somit von D^{2} induziert.

Ist D algebraisch, so ist auch M algebraisch.

Beweis. Da die Faktorisierungsabbildung (·\·) für faktorisierte Bereiche stetig ist, sind auch die beiden Abbildungen ⟨p_{1}, \⟩: ⊑_{D}→ E und ⟨\, p_{2}⟩: ⊑_{D}→ M stetig. Zusammen mit den Inklusionen E ↪ ⊑_{D} bzw. M ↪ ⊑_{D} ergeben sich stetige Schnitt-Retraktionspaare; als Retrakte des stetigen Bereichs ⊑_{D} sind E und M damit stetig (vgl. [AJ95, Theorem 3.1.4]).

Die Abbildung ⟨p_{1}, \⟩ ist eine Projektion. Wegen [AJ95, Proposition 3.1.17] ist die Approximationsordnung auf E somit die von ⊑_{D} induzierte. Nach Lemma 1.19 ist diese selbst von D^{2} induziert.

Ist D algebraisch, dann ist nach Korollar 1.20 auch ⊑_{D} algebraisch. Die Abbildung ⟨\, p_{2}⟩ ist ein Hüllenoperator. Nach [AJ95, Proposition 3.1.18] ist das Bild eines algebraischen Bereichs unter einem stetigen Hüllenoperator genau dann algebraisch, wenn das Bild gegen gerichtete Suprema abgeschlossen ist. Nach Satz 2.15 ist das für M der Fall.

Bemerkung. Im allgemeinen ist die Approximationsordnung auf M nicht von D^{2} induziert. Für faktorisierte algebraische Bereiche haben die kompakten Elemente in M die Form (x\y, y) für kompakte Elemente x ⊑ y.

3 Abbildungen zwischen faktorisierten Bereichen

Δεδóμενα λέγεται κατηγoϱία,
η̃ς oιστoὶ δέδoνται.

frei nach Euklid, Dedomena

Es stellt sich die Frage, welche Abbildungen zwischen faktorisierten Bereichen man auswählen soll, um eine interessante Kategorie zu erhalten. Diese soll die Kategorie der Scott-stetigen und die der stabilen Funktionen als volle Unterkategorien beinhalten.

Wir untersuchen zuerst einen Morphismusbegriff, den man für S-dcpo’s definieren kann. Die Morphismen kann man dabei algebraisch oder mit verallgemeinerten topologischen Begriffen beschreiben. Dann studieren wir die von Lamarche in [Lam95] vorgeschlagenen Morphismen. Auch hier gibt es wieder eine algebraische und eine ‘topologische’ Fassung. Zum Schluß des Kapitels werden wir sehen, daß die beiden Morphismenbegriffe für LI-Bereiche zusammenfallen.

3.1 Eine Kategorie faktorisierter Bereiche

Die Idee, wie man die Scott-stetige und stabile Funktionen gleichzeitig in einer Kategorie zusammenfassen kann, ist es, verschiedene Faktorisierungssysteme auf Bereichen zu betrachten, insbesondere die beiden trivialen (⊑, =) und (=, ⊑). Für eine stabile Funktion verlangt man, daß alle beschränkten Infima erhalten werden. Bei Funktionen zwischen faktorisierten dcpo’s beschränkt man sich auf Infima, für die eines der Elemente und die obere Schranke M-vergleichbar sind. Beim Faktorisierungssystem (⊑, =) wird diese Bedingung trivial, für (=, ⊑) sind alle vergleichbaren Elemente M-vergleichbar, d.h. man erhält die volle Stabilitätsbedingung. Aus technischen Gründen muß man zusätzlich verlangen, daß die Abbildungen M-Vergleichbarkeit erhalten.

Definition 3.1. Eine Abbildung f: D → D′ zwischen faktorisierten S-dcpo’s heißt para-stetig, wenn sie die folgenden Bedingungen erfüllt:

1. f ist Scott-stetig,

2. für alle x ≤^{M} y ∈ D gilt f(x) ≤^{M} f(y) (M-Monotonie),

3. Für alle x, y, z ∈ D mit x ≤^{M} z und y ⊑ z gilt f(x ⊓ y) = f(x) ⊓ f(y) (f erhält Pullbacks von M’s).

Die S-dcpo’s mit den para-stetigen Funktionen bilden eine Kategorie:

Lemma 3.2. Seien D_{1}, D_{2} und D_{3} faktorisierte S-dcpo’s. Dann sind die Identität auf D_{1}, alle konstanten Funktionen von D_{1} nach D_{2} und für alle parastetigen Funktionen f: D_{1} → D_{2} und g: D_{2} → D_{2} die Hintereinanderausführung g ∘ f para-stetig.

Beweis. Die Para-Stetigkeit der Identität und der konstanten Funktionen folgt unmittelbar aus der Definition.

Mit f und g ist auch g ∘f Scott-stetig und M-monoton. Es ist also nur noch zu zeigen, daß g ∘ f Pullbacks von M’s erhält: Sei x ≤^{M} z ⊒ y ∈ D_{1}. Wegen der Para-Stetigkeit von f gilt f(x) ≤^{M} f(z) ⊒ f(y) und f(x ⊓ y) = f(x) ⊓ f(y). Da g para-stetig ist, erhalten wir g(f(x ⊓ y)) = g(f(x) ⊓ f(y)) = g(f(x)) ⊓ g(f(y)).

Definition 3.3. Die Kategorie der faktorisierten S-dcpo’s mit den para-stetigen Abbildungen bezeichnen wir mit FDCPO und die der entsprechenden stetigen bzw. algebraischen S-Bereiche mit FCONT bzw. FALG.

Für eine dcpo D bezeichnet man (⊑_{D}, =) als topologisches und (=, ⊑_{D}) als stabiles Faktorisierungssystem auf D. Wir sagen auch eine dcpo sei topologisch bzw. stabil faktorisiert.

Die nächsten beiden Sätze zeigen, daß FDCPO die Kategorie der S-dcpo’s mit den Scott-stetigen sowie die mit den stabilen Abbildungen als volle Unterkategorien enthält:

Satz 3.4. Eine Abbildung f: D → D′ von einer topologisch faktorisierten S-dcpo D in eine beliebige faktorisierte S-dcpo D′ ist genau dann para-stetig, wenn sie Scott-stetig ist.

Beweis. Nach Definition ist jede para-stetige Abbildung Scott-stetig. Die dcpo D trägt das topologische Faktorisierungssystem, d.h. jedes Element ist nur mit sich selbst M-vergleichbar. Also ist die M-Monotonie trivial. Aus x ≤^{M} z ⊒ y folgt z = x ⊒ y und somit x ⊓ y = y. Da jede Scott-stetige Abbildung monoton ist, wird auch die letzte Bedingung trivialerweise erfüllt.

Satz 3.5. Eine Abbildung zwischen zwei stabil faktorisierten S-dcpo’s ist genau dann para-stetig, wenn sie stabil ist.

Beweis. Bei der stabilen Faktorisierung sind alle vergleichbaren Elemente M-ver-gleichbar. Also muß eine para-stetige Abbildung alle beschränkten Infima erhalten und ist somit stabil.

Umgekehrt erhält jede stabile Funktion alle beschränkten Infima und ist Scott-stetig, also allemal monoton. Für Abbildungen zwischen stabil faktorisierten dcpo’s fallen Monotonie und M-Monotonie zusammen, und somit jede stabile Abbildung zwischen solchen dcpo’s para-stetig.

Um die Propositionen 1.1 und 1.2 auf faktorisierte dcpo’s übertragen zu können, müssen wir zwischen den beiden Möglichkeiten unterscheiden, den zweielementigen Bereich 2 zu faktorisieren.

Definition 3.6. In der Kategorie FDCPO bezeichne 2_{T} den Bereich 2 mit dem topologischen Faktorisierungssystem (0 ≤^{E} 1). Den stabil faktorisierten (0 ≤^{M} 1) bezeichnen wir mit 2_{S}.

Satz 3.7. Die para-stetigen Abbildungen von 2_{T} in eine faktorisierte S-dcpo D stehen in Bijektion zu den Paaren (x ⊑ y) ∈ D^{2}, d.h. FDCPO(2_{T} , D) ≅ ⊑_{D}.

Beweis. Die Behauptung folgt unmittelbar aus Proposition 1.1 und Satz 3.4.

Satz 3.8. Die para-stetigen Abbildungen von 2_{S} in eine faktorisierte S-dcpo D stehen in Bijektion zu den Elementen aus M, d.h. FDCPO(2_{S}, D) ≅ M.

Beweis. Sei f: 2_{S} → D para-stetig. Dann folgt aus der M-Monotonie von f die Beziehung f(0) ≤^{M} f(1).

Sei umgekehrt x ≤^{M} y beliebig und f die Abbildung mit f(0) = x und f(1) = y. Jede monotone Abbildung aus 2_{S} erhält alle Suprema und alle Infima. Da x ≤^{M} y gilt, ist f zusätzlich M-monoton und somit para-stetig.

Im folgenden untersuchen wir, wie man die Morphismen, die bisher über algebraische Eigenschaften definiert sind, mit verallgemeinerten topologisch Begriffen beschreiben kann. Dazu werden wir para-offene Mengen definieren. Zu der üblichen Forderung, daß das Urbild einer offenen Menge offen sein soll, werden wir zusätzlich fordern, daß die Urbildfunktion bezüglich einer noch zu definierenden Ordnung auf den para-offenen Mengen monoton ist.

Aus Proposition 1.2 wissen wir, daß die Scott-offenen Mengen zu den Scott-stetigen Abbildungen [D → 2_{T}] korrespondieren. Wir definieren deshalb die para-offenen Mengen gerade so, daß sie den Morphismen FDCPO(D, 2_{S}) entsprechen. Wie in Proposition 1.2 wird diese Bijektion ein Ordnungsisomorphismus sein; um das formulieren zu können, müssen wir aber zunächst eine Ordnung auf FDCPO(D, D′) erklären.

Die Definition orientiert sich an der Berry-Ordnung (vgl. Definition 1.12) und hat die Eigenschaft, daß sie für die para-stetigen Funktionen zwischen topologisch bzw. stabil faktorisierten dcpo’s gerade die punktweise bzw. die Berry-Ordnung liefert. Im nächsten Kapitel werden wir sehen, daß diese Definition insofern ‘richtig’ gewählt ist, als sie für kartesisch abgeschlossene volle Unterkategorien von FDCPO gerade die Ordnung auf dem Exponential ist.

Definition 3.9. Seien D und D′ zwei faktorisierte S-dcpo’s. Zwei para-stetige Funktionen f, g: D → D′ heißen vergleichbar in der verallgemeinerten Berry-Ordnung f ⊑_{B} g genau dann, wenn f punktweise kleiner als g ist und für alle x ≤^{M} y ∈ D die Gleichung f(x) = f(y) ⊓ g(x) gilt.

Sind D und D′ Objekte in FDCPO, dann schreiben wir [D → D′] für die geordnete Menge (FDCPO(D, D′), ⊑_{B}).

Die Berry-Ordnung ist bisher nur für stabile Funktionen erklärt, sie ist aber für beliebige Morphismen f, g aus FDCPO sinnvoll. Deshalb verwenden wir sie im folgenden auch für solche. Für die Berry-Ordnung schreiben wir immer ≤_{b}, für die verallgemeinerte dagegen ⊑_{B}.

Lemma 3.10. Seien D und D′ zwei S-dcpo’s und f, g: D → D′ para-stetige Funktionen. Trägt D das topologische Faktorisierungssystem, so gilt f ⊑_{B} g genau dann, wenn f punktweise kleiner als g ist. Ist D stabil faktorisiert, dann sind f ⊑_{B} g und f ≤_{b} g äquivalent.

Beweis. Ergibt sich unmittelbar aus der Definition.

Jetzt haben wir den technischen Apparat, um para-offene Mengen definieren und die Korrespondenz zu [D → 2_{S}] zeigen zu können:

Definition 3.11. Sei D eine faktorisierte S-dcpo. Eine Teilmenge U ⊆ D heißt para-offen, wenn sie Scott-offen ist und gegen Pullbacks von M’s abgeschlossen ist, d.h. für alle x, y, z ∈ U mit x ≤^{M} z ⊒ y gilt x ⊓ y ∈ U.

Seien U und V offen. Wir definieren U ⊑ V genau dann, wenn U ⊆ V gilt und aus y ∈ U, x ∈ V und x ≤^{M} y stets x ∈ U folgt. Die folgende Skizze zeigt die Situation, in der zwei Mengen U ⊆ V nicht vergleichbar sind:

U  • y
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..........[figure: M].......... ..............................
. . . . . . .
x •  V
. . . . . . .

Die para-offenen Teilmengen von D mit dieser Ordnung bezeichnen wir mit O(D).

Satz 3.12. Sei D eine faktorisierte S-dcpo. Dann sind O(D) und [D → 2_{S}] ordnungsisomorph.

Dieser Isomorphismus ordnet einer para-stetigen Funktion f die Menge f^{−1}[{1}] und einer para-offenen Menge U ihre charakteristische Funktion χ_{U} zu.

Beweis. Sei f: D → 2_{S} para-stetig. Wir betrachten U_{f} := f^{−1}[{1}]. Wegen der Scott-Stetigkeit von f ist U_{f} Scott-offen. Um U_{f} als para-offen nachzuweisen, müssen wir noch zeigen, daß U_{f} gegen Pullbacks von M’s abgeschlossen ist. Sei deshalb x, y, z ∈ U_{f} mit x ≤^{M} z ⊒ y. Da die Punkte in U_{f} liegen, gilt f(x) = f(y) = f(z) = 1, und da f als para-stetige Abbildung Pullbacks von M’s erhält, folgt f(x ⊓ y) = f(x) ⊓ f(y) = 1 ⊓ 1 = 1. Also liegt x ⊓ y in U_{f}. Somit ist U_{f} para-offen.

Gilt f ⊑_{B} g, so ist f punktweise kleiner als g. Deshalb gilt U_{f} ⊆ U_{g} := g^{−1}[{1}]. Zum Nachweis von U_{f} ⊑ U_{g} müssen wir zeigen, daß es keine M-Vergleichbarkeiten zwischen Elementen aus U_{f} und U_{g} gibt, die nicht bereits in U_{f} liegen. Sei x ∈ U_{g} und y ∈ U_{f} mit x ≤^{M} y. Aus f ⊑_{B} g folgt f(x) = g(x) ⊓ f(y) = 1 ⊓ 1 = 1, d.h. es gilt x ∈ U_{f}. Also ist die Zuordnung f ↦ U_{f} monoton.

Sei nun umgekehrt U eine para-offene Teilmenge von D. Die charakteristische Funktion

χ_{U}: D → 2_{S} mit x ↦ \begin{cases}1 & x ∈ U \\ 0 & sonst \end{cases}

ist Scott-stetig, da U Scott-offen ist. Da in 2_{S} alle Elemente M-vergleichbar sind, ist sie auch M-monoton, und da U gegen Pullbacks von M’s abgeschlossen ist, erhält χ_{U} Pullbacks von M’s.

Für U ⊑ V ist wegen U ⊆ V die Funktion χ_{U} punktweise kleiner als χ_{V}. Wir zeigen nun, daß für alle x ≤^{M} y die Gleichung χ_{U}(x) = χ_{V} (x) ⊓ χ_{U}(y) gilt: Liegt x nicht in V, so folgt χ_{U}(x) = χ_{V} (x) = 0, und die Gleichung ist erfüllt. Andernfalls ist mit x auch y ein Element aus V. Wegen U ⊑ V liegen beide Elemente entweder in U oder in V \ U; in beiden Fällen gilt die Gleichung. Somit ist auch die Zuordnung U ↦ χ_{U} monoton.

Die Funktionen [D → 2_{T}] haben für die weitere Theorie keine besondere Bedeutung: Sie entsprechen den Scott-offenen Teilmengen von D, die M-Anfangsstücke sind, d.h. die ↓_{M} U = U erfüllen. Die verallgemeinerte Berry-Ordnung auf dem Funktionenraum entspricht der Enthaltenseinsrelation auf den Teilmengen.

Mit Hilfe dieser Begriffe können wir die Morphismen zwischen faktorisierten Bereichen nun auf eine neue Art beschreiben. Dazu brauchen wir noch eine Vorüberlegung:

Lemma 3.13. Seien D_{1}, D_{2} und D_{3} faktorisierte S-dcpo’s. Dann ist die Komposition als Abbildung ∘: [D_{2} → D_{3}] × [D_{1} → D_{2}] ⟶ [D_{1} → D_{3}] monoton.

Beweis. Um die Monotonie zu zeigen, reicht es, sie komponentenweise zu überprüfen. Ferner ist klar, daß die Komposition bzgl. der punktweisen Ordnung monoton ist.

Sei f ⊑_{B} f′ ∈ [D_{1} → D_{2}] und g ∈ [D_{2} → D_{3}]. Um g ∘ f ⊑_{B} g ∘ f′ zu zeigen, müssen wir nachweisen, daß für alle x ≤^{M} y die Gleichung g(f(x)) = g(f(y)) ⊓ g(f′(x)) gilt. Wegen x ≤^{M} y und f ⊑_{B} f′ ist f(x) = f(y) ⊓ f′(x). Aus der M-Monotonie von f′ erhalten wir f′(x) ≤^{M} f′(y). Die Funktion g ist para-stetig und erhält Pullbacks von M’s. Also folgt g(f(x)) = g(f(y) ⊓ f′(x)) = g(f(y)) ⊓ g(f′(x)).

Für die Monotonie in der ersten Komponente sei f ∈ [D_{1} → D_{2}] und g ⊑_{B} g′ ∈ [D_{2} → D_{3}]. Wir zeigen nun g ∘ f ⊑_{B} g′ ∘ f. Sei dazu x ≤^{M} y. Aus der M-Monotonie von f folgt f(x) ≤^{M} f(y), und wegen g ⊑_{B} g′ gilt g(f(x)) = g(f(y)) ⊓ g′(f(x)), was die Behauptung zeigt.

Satz 3.14. Sei f: D → D′ eine Abbildung zwischen zwei faktorisierten stetigen S-Bereichen. Dann ist f genau dann para-stetig, wenn die Urbilder aller para-offenen Teilmengen von D′ para-offen sind und die Urbildfunktion f^{−1}[·]: O(D′) → O(D) (bzgl. ⊑) monoton ist.

Beweis. Sei f para-stetig und U ⊆ D′ para-offen. Nach Satz 3.12 entspricht U einer Abbildung χ_{U}: D′ → 2_{S}. Es ist dann χ_{U} ∘ f para-stetig, und es gilt f^{−1}[U] = (χ_{U} ∘ f)^{−1}[{1}]. Nach Satz 3.12 ist f^{−1}[U] somit para-offen.

Für U ⊑ V gilt χ_{U} ⊑_{B} χ_{V}. Aus Lemma 3.13 folgt χ_{U} ∘ f ⊑_{B} χ_{V} ∘ f und mit Satz 3.12 wie eben f^{−1}[U] ⊑ f^{−1}[V].

Habe umgekehrt f die Eigenschaft, daß die Urbilder para-offener Mengen para-offen sind und f^{−1}[·] monoton ist. Wir zeigen, daß dann f para-stetig ist:

(Scott-Stetigkeit): Für stetige Bereiche bilden die Scott-offenen Filter eine Basis der Scott-Topologie (siehe [AJ95, Lemma 2.3.8]). Filter sind gegen binäre Schnitte abgeschlossen, und somit sind diese Basismengen para-offen. Da die Urbilder dieser Mengen nach Voraussetzung para-offen also insbesondere Scottoffen sind, ist f Scott-stetig.

(M-Monotonie): Sei x ≤^{M} y. Wir werden f(x) ≤^{M} f(y) mit Hilfe von Bemerkung 2.3 zeigen, indem wir nachweisen, daß f(x) ⊑ f(y) mit passenden a ≤^{E} b die Bedingung ♢ erfüllt: Sei dazu a ≤^{E} b mit a ⊑ f(x) und b ⊑ f(y). Wegen

• f(y)
[figure]
f(x) •
• b
[figure: E]
a •  • b_{0} ‖
[figure: E]
a0 • ‖  • b′ ‖
[figure: E]
a′ • ‖

Satz 2.15 ist (a ≤^{E} b) das Supremum von E-vergleichbaren Elementen weit darunter. Sei (a′ ≤^{E} b′) mit a′ ≪ a und b′ ≪ b ein beliebiges solches Element. Aus Satz 2.24 wissen wir, daß E als Retrakt von ⊑_{D} stetig ist und die von D^{2} induzierte Approximationsordnung trägt. Aufgrund der Interpolationseigenschaft für stetige Bereiche (siehe [AJ95, Lemma 2.2.15]) gibt es ein interpolierendes Element (a_{0} ≤^{E} b_{0}) mit a ≫ a_{0} ≫ a′ und b ≫ b_{0} ≫ b′. Ebenso erhält man ein Paar (a_{1} ≤^{E} b_{1}) mit a_{0} ≫ a_{1} ≫ a′ und b_{0} ≫ b_{1} ≫ b′. So konstruiert man eine Folge (a_{i} ≤^{E} b_{i})_{i∈ℕ} mit a ≫ a_{0} ≫ a_{1} ≫ ⋯ ≫ a′ und b ≫ b_{0} ≫ b_{1} ≫ ⋯ ≫ b′.

Die Mengen A := ⋃_{i} ↑ ↑a_{i} und B := ⋃_{i} ↑ ↑b_{i} sind Scott-offene Filter und damit para-offen. Sie werden von a′ bzw. b′ nach unten beschränkt. Aufgrund der Konstruktion gilt B ⊆ A. Wir behaupten, es gilt sogar B ⊑ A. Sei c ≤^{M} d mit c ∈ A und d ∈ B, dann gibt es einen Index i ∈ ℕ mit a_{i} ≪ c und b_{i} ≪ d. Aus a_{i} ≤^{E} b_{i}

• d B
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . [figure: M] .............................. ...................................
c •
• b_{i} ‖
[figure: E]
ai • ‖
........... A

folgt mit der Bedingung ♢ die Beziehung b_{i} ⊑ c und daher b_{i+1} ≪ c. Somit liegt c in B, und B ⊑ A ist gezeigt.

Es gilt x ∈ f^{−1}[A] und y ∈ f^{−1}[B]. Aus der Monotonie der Urbildfunktion folgt f^{−1}[B] ⊑ f^{−1}[A]. Wegen x ≤^{M} y muß deshalb x ∈ f^{−1}[B] gelten. Also haben wir f(x) ∈ B und wegen B ⊆ ↑b′ damit auch f(x) ⊒ b′. Da b das Supremum von solchen b′ ist, folgt f(x) ⊒ b. Wegen Bemerkung 2.3 ist damit f(x) ≤^{M} f(y) gezeigt.

(Pullbacks von M’s): Sei x ≤^{M} z ⊒ y. Aufgrund der Monotonie von f gilt f(x ⊓ y) ⊑ f(x) ⊓ f(y). Für die umgekehrte Vergleichbarkeit betrachten wir ein beliebiges a ≪ f(x) ⊓ f(y). Wie beim Nachweis der M-Monotonie konstruieren

f^{−1}[A]  z •  f(z) •
[figure: . . . . . . . . . . . . . . . . . . . . . . . . . .; M; ..........]
x • • y \overline{f^{}}f(x) • • f(y)
[figure: M; ..............................]
• x ⊓ y  • f(x) ⊓ f(y)
[figure]
f(x ⊓ y) •
..........• a ‖

wir eine Folge f(x) ⊓ f(y) ≫ a_{0} ≫ a_{1} ≫ a_{2} ≫ ⋯ ≫ a. Die Menge A := ⋃_{i} ↑ ↑a_{i} ist als Scott-offener Filter para-offen, und es gilt f(x) ⊓ f(y) ∈ A. Damit liegen auch f(x), f(y) und f(z) in A, es folgt x, y, z ∈ f^{−1}[A]. Da f^{−1}[A] para-offen und somit gegen Pullbacks von M’s abgeschlossen ist, erhalten wir x ⊓ y ∈ f^{−1}[A]. Mit A ⊆ ↑a folgt f(x ⊓ y) ⊒ a. Da dies für jedes a ≪ f(x) ⊓ f(y) gilt, ist damit die Gleichheit f(x) ⊓ f(y) = f(x ⊓ y) gezeigt.

Also ist f para-stetig.

3.2 Der Ansatz von Lamarche

Wir betrachten nun die von Lamarche in [Lam95] untersuchte Kategorie. Man kann die Morphismen wie im vorangegangenen Abschnitt entweder algebraisch oder para-topologisch beschreiben. Die Definition orientiert sich bei Lamarche an der para-topologischen Fassung. Deshalb wollen wir mit dieser beginnen und dann die Äquivalenz zur entsprechenden algebraischen untersuchen.

Die Begriffe sind weitgehend zu denen des vorigen Abschnitts analog. Um Verwechslungen zu vermeiden, benutzen wir die Bezeichnungen para-offen bzw. para-stetig für die Begriffe aus dem vorangegangenen Abschnitt und ℓ-para-offen bzw. ℓ-para-stetig für die neuen Begriffe aus diesem.

Lamarche untersucht Scott-Bereiche, also algebraische BC-Bereiche, die ein wie in Korollar 2.22 konstruiertes Faktorisierungssystem tragen. Diese sind somit kompakt faktorisierte BC-Bereiche.

Für algebraische Bereiche sind die von den kompakten Elementen erzeugten Hauptfilter eine Basis der Scott-Topologie. Man erhält den Begriff der ℓ-para-offenen Mengen, indem man für deren Erzeugung nur bestimmte Familien kompakter Elemente zuläßt.

Definition 3.15. Sei D ein faktorisierter algebraischer L-Bereich. Eine Teilmenge N ⊆ D heißt kollaborierend, wenn für je zwei Elemente x_{1}, x_{2} ∈ N und jede obere Schranke y ∈ D dieser Elemente die Beziehung x_{1}, x_{2} ≤^{E} x_{1} ⊔^{y} x_{2} gilt.

Ist N ⊆ K(D) eine kollaborierende Menge kompakter Elemente, so nennen wir ↑N ℓ-para-offen und N das Erzeugendensystem der ℓ-para-offenen Menge.

Es ist klar, daß alle ℓ-para-offenen Mengen Scott-offen sind. Wir wollen nun die Scott-offenen Mengen charakterisieren, die ℓ-para-offen sind, ohne dabei explizit auf Erzeugendensysteme bezug zu nehmen.

Lemma 3.16. Die ℓ-para-offenen Teilmengen eines faktorisierten algebraischen L-Bereichs D sind para-offen.

Beweis. Sei N ⊆ D eine Erzeugendensystem aus kompakten kollaborierenden Elementen, U = ↑N die davon erzeugte ℓ-para-offene Menge und x, y ∈ U Elemente mit x ≤^{M} z ⊒ y. Dann gibt es Elemente k, l ∈ N mit k ⊑ x und

• z
[figure: M]
x •  • y
..........
• k ⊔^{z} l
[figure: E; E]
k •  • l

l ⊑ y. Die Elemente k und l kollaborieren und sind durch z beschränkt. Also gilt k, l ≤^{E} k ⊔^{z} l. Wegen der Bedingung ♢ folgt k ⊔^{z} l ⊑ x. Damit ist l eine untere Schranke von {x, y}, und es gilt l ⊑ x ⊓ y. Somit liegt das Infimum in U = ↑N ⊇ ↑l.

Lemma 3.17. Sei U eine ℓ-para-offene Teilmenge eines faktorisierten algebraischen L-Bereichs. Dann hat für jedes Element x ∈ U die Menge (↓_{M} x) ∩ U ein kleinstes Element. Ist k ein Element eines Erzeugendensystems von U und k ⊑ x, so ist dieses kleinste Element k\x.

Beweis. Die ℓ-para-offene Menge U hat ein Erzeugendensystem N. Zu jedem Element x ∈ U = ↑N gibt es ein k ∈ N mit k ⊑ x. Wir behaupten, k\x ist das gesuchte kleinste Element in ↓_{M}{x} ∩ U:

Sei y ∈ U ein Element mit y ≤^{M} x. Dann gibt es ein l ∈ N mit l ⊑ y. Die

x •
[figure: M; M]
• y
[figure: M]
k\x • M = = = = =•= = = = =• l\y
• k ⊔^{x} l E
[figure: E; E]
k • E  • l E

beiden Erzeuger k und l sind durch x beschränkt, und da N als Erzeugendensystem kollaboriert folgt k, l ≤^{E} k ⊔^{x} l. Nun faktorisieren wir k ⊔^{x} l ⊑ x und l ⊑ y. Aus der Eindeutigkeit der Faktorisierung erhalten wir k\x = (k ⊔^{x} l)\x = l\y. Also gilt k\x = l\y ⊑ y.

Das zu einem gegebenen Element x ∈ U kleinste Element M-darunter, dessen Existenz uns das vorangegangene Lemma garantiert, bezeichnen wir im folgenden mit U⟨x⟩. Wegen der Transitivität von M ist die Abbildung U⟨·⟩ idempotent. Im folgenden bezeichnen wir die Menge ihrer Fixpunkte mit fix(U⟨·⟩). Da die Abbildung auch deflationär ist, liegt jedes Element x ∈ U über einem Fixpunkt U⟨x⟩.

Korollar 3.18. Sei U eine ℓ-para-offene Teilmenge eines faktorisierten algebraischen L-Bereichs, X ⊆ U eine nichtleere Teilmenge und y ≥^{M} X eine obere Schranke bezüglich M. Dann gilt ⨅ X ∈ U, d.h. U ist gegen nichtleere M-beschränkte Infima abgeschlossen.

Beweis. Nach Lemma 3.17 gibt es zu der oberen Schranke y ein Element U⟨y⟩, das kleinste Element in ↓_{M}{y} ∩ U. Wegen X ⊆ U und da alle Elemente aus X M-unter y liegen, folgt U⟨y⟩ ⊑ X. Also ist U⟨y⟩ ⊑ ⨅ X, und ⨅ X liegt in U.

Satz 3.19. Eine Teilmenge U eines kompakt faktorisierten L-Bereichs ist genau dann ℓ-para-offen, wenn sie die folgenden drei Bedingungen erfüllt:

1. U = ↑(U ∩ K) (d.h. U ist Scott-offen),

2. zu jedem Element x ∈ U gibt es in ↓_{M}{x} ∩ U ein kleinstes Element U⟨x⟩,

3. die Abbildung U⟨·⟩: U → U ist Scott-stetig.

Beweis. Sei N eine kollaborierende Menge kompakter Elemente und U = ↑N die davon erzeugte ℓ-para-offene Menge. Dann ist die erste Bedingung trivialerweise erfüllt. Die zweite Bedingung haben wir in Lemma 3.17 gezeigt. Das Lemma sagt ferner, daß für jedes k ∈ N mit k ⊑ x die Gleichung U⟨x⟩ = k\x gilt. Sei deshalb G ⊆ U eine gerichtete Menge und k ∈ N liege unter einem Element von G. Dann gilt ^{⨆↑} G = ^{⨆↑}(G ∩ ↑k). Die Faktorisierungsabbildung ist nach 2.15 Scott-stetig, und somit folgt die Stetigkeit von U⟨·⟩.

Sei umgekehrt U eine Menge, die die drei Bedingungen des Satzes erfüllt. Wir konstruieren ein Erzeugendensystem, um U als ℓ-para-offen nachzuweisen.

Die Abbildung U⟨·⟩ bildet ein Element x ∈ U auf das kleinste Element M-darunter in U ab. Wir betrachten F := fix(U⟨·⟩), die Menge der Fixpunkte dieser Abbildung. Jedes Element x liegt über einem Fixpunkt U⟨x⟩ ∈ F.

Wir überlegen nun, daß F kollaboriert. Seien x_{1}, x_{2} ∈ F von y beschränkt.

[figure: • y; • z := x_{1} ⊔^{y} x_{2}; x1 • • x_{2}]

Dann gilt x_{1}, x_{2} ⊑ x_{1} ⊔^{y} x_{2} =: z ⊑ y. Die Abbildung U⟨·⟩ ist Scott-stetig und damit monoton. Also gilt U⟨x_{1}⟩ = x_{1} ⊑ U⟨z⟩ ⊒ U⟨x_{2}⟩ = x_{2}. Da z das Supremum von x_{1} und x_{2} ist, folgt U⟨z⟩ = z, d.h. z ist ebenfalls ein Fixpunkt. Das Element z ist somit M-minimal in U, und es folgt x_{1}, x_{2} ≤^{E} z.

Es bietet sich nun an, als Erzeugendensystem F ∩ K zu wählen. Wir wissen bereits, daß unter jedem Element aus U eines aus F liegt und daß F kollaboriert. Um U als ℓ-para-offen nachzuweisen, müssen wir deshalb nur noch zeigen, daß jedes Element aus U über einem kompakten Fixpunkt liegt. Für ein x ∈ U gibt es aufgrund der ersten Bedingung ein kompaktes Element k ∈ U mit k ⊑ U⟨x⟩ ⊑ x. Das Element U⟨x⟩ ist ein Fixpunkt von U⟨·⟩ und somit M-minimal. Deshalb gilt k ≤^{E} U⟨x⟩. Nach Voraussetzung ist (k ≤^{E} U⟨x⟩) das gerichtete Supremum von E-vergleichbaren Paaren (k_{i} ≤^{E} l_{i}) darunter, wobei die k_{i} und die l_{i} kompakt sind. Die Elemente m_{i} := k ⊔^{x} l_{i} sind nach Proposition 1.7 kompakt, und wegen

x •
U⟨x⟩ •M
[figure]
k ⊔^{x} li =: mi •E
[figure]
U⟨m^{i}⟩ •  • l_{i}
..........  [figure: E]
k •E
[figure]
• k_{i}

Lemma 2.10 gilt k ≤^{E} m_{i}, da dies ein Pushout von (k_{i} ≤^{E} l_{i}) ist. Ferner ist l_{i} ⊑ m_{i} ⊑ U⟨x⟩, woraus ^{⨆↑} m_{i} = ^{⨆↑} l_{i} = U⟨x⟩ folgt. Wir betrachten nun die Elemente U⟨m_{i}⟩. Nach Voraussetzung ist die Abbildung U⟨·⟩ stetig, und wir erhalten ⨆↑ U⟨m_{i}⟩ = U⟨^{⨆↑} m_{i}⟩ = U⟨U⟨x⟩⟩ = U⟨x⟩. Da k kompakt ist und k ⊑ U⟨x⟩ gilt, liegt eines der U⟨m_{i}⟩ über k. Aus k ≤^{E} m_{i} folgt mit Bemerkung 2.3 zum einen U⟨m_{i}⟩ ≤^{E} m_{i}, andererseits haben wir U⟨m_{i}⟩ ≤^{M} m_{i} nach der Definition von U⟨·⟩. Also muß U⟨m_{i}⟩ = m_{i} gelten, d.h. m_{i} ist ein kompakter Fixpunkt.

Bemerkung. Der Beweis des Satzes zeigt, daß es zu jeder ℓ-para-offenen Menge U ein größtes Erzeugendensystem, nämlich fix(U⟨·⟩) ∩ K, gibt.

Wir wollen ℓ-para-stetige Abbildungen wieder als solche definieren, deren zugehörige Urbildfunktion ℓ-para-offene Mengen monoton auf ℓ-para-offene Mengen abbildet. Dazu fehlt uns noch eine Ordnung auf den ℓ-para-offenen Mengen. Da jede ℓ-para-offene Menge para-offen ist, benutzen wir die von den para-offenen Mengen induzierte Ordnung (siehe Definition 3.11). Diese kann man in unserem Spezialfall noch anders charakterisieren:

Satz 3.20. Sei D ein kompakt faktorisierter L-Bereich und U und V zwei ℓ-para-offene Teilmengen. Genau dann gilt U ⊑ V, wenn fix(U⟨·⟩) ⊆ fix(V ⟨·⟩) gilt.

Beweis. Angenommen es gelte U ⊑ V. Sei x ∈ U ein Fixpunkt von U⟨·⟩, d.h. ein M-minimales Element in U, und y ein Element aus V mit y ≤^{M} x. Wegen U ⊑ V kann nicht y ∈ V \ U gelten. Da x in U aber M-minimal ist, folgt daraus x = y. Also ist x auch in V ein M-minimales Element und damit ein Fixpunkt von V ⟨·⟩. Damit haben wir fix(U⟨·⟩) ⊆ fix(V ⟨·⟩) gezeigt.

Sei umgekehrt fix(U⟨·⟩) ⊆ fix(V ⟨·⟩). Dann gilt U = ↑fix(U⟨·⟩) ⊆ ↑fix(V ⟨·⟩) = V. Für x ∈ V und y ∈ U mit x ≤^{M} y, gilt V ⟨x⟩ ≤^{M} x ≤^{M} y, und wegen der

• y ∈ U
[figure: M]
V ∋ x •
..........
• U⟨y⟩ ∈ U M
[figure: E]
V ⟨y⟩ = V ⟨x⟩ • M

Monotonie von V ⟨·⟩ folgt V ⟨x⟩ = V ⟨y⟩. Aus U⟨y⟩ ≤^{M} y ergibt sich deshalb V ⟨x⟩ = V ⟨y⟩ ⊑ U⟨y⟩. Das Element U⟨y⟩ ist M-minimal in U und nach Voraussetzung damit M-minimal in V. Also folgt V ⟨x⟩ ≤^{E} U⟨y⟩, und aus Bedingung ♢ erhalten wir U⟨y⟩ ⊑ x. Somit liegt x in U, was U ⊑ V zeigt.

Definition 3.21. Eine Abbildung f: D → D′ zwischen kompakt faktorisierten L-Bereichen heißt ℓ-para-stetig, wenn die Urbilder ℓ-para-offener Teilmengen von D′ ℓ-para-offen sind und die Urbildfunktion f^{−1}[·] bzgl. der von den para-offenen Mengen induzierten Ordnung monoton ist.

Lemma 3.22. Seien D_{1}, D_{2} und D_{3} kompakt faktorisierte S-dcpo’s. Dann sind die Identität auf D_{1}, alle konstanten Funktionen von D_{1} nach D_{2} und für alle ℓ-para-stetigen Funktionen f: D_{1} → D_{2} und g: D_{2} → D_{2} die Hintereinanderausführung g ∘ f ℓ-para-stetig.

Beweis. Die Behauptungen folgen unmittelbar aus der Definition der ℓ-Para-Stetigkeit.

Definition 3.23. Die Kategorie der kompakt faktorisierten L-Bereiche mit den ℓ-para-stetigen Abbildungen als Morphismen bezeichnen wir mit LFALG.

Trägt ein Bereich aus LFALG das topologische bzw. stabile Faktorisierungssystem (vgl. Definition 3.3), so sagen wir auch er sei topologisch bzw. stabil kompakt faktorisiert.

Auch in LFALG sind die Morphismen zwischen topologisch faktorisierten Objekten gerade die Scott-stetigen Abbildungen (vgl. Satz 3.4):

Satz 3.24. Eine Abbildung f: D → D′ von einem topologisch kompakt faktorisierten L-Bereich D in einen kompakt faktorisierten L-Bereich D′ ist genau dann ℓ-para-stetig, wenn sie Scott-stetig ist.

Beweis. Ist D topologisch faktorisiert, so kollaborieren alle Teilmengen von D. Also sind in D alle Scott-offenen Mengen ℓ-para-offen und somit alle Scottstetigen Abbildungen ℓ-para-stetig.

Wie wir am Ende dieses Kapitels (Korollar 3.36) sehen werden, gilt für I-Bereiche die Satz 3.5 entsprechende Aussage, daß die ℓ-para-stetigen Abbildungen zwischen stabil kompakt faktorisierten Bereichen gerade den stabilen Funktionen entsprechen.

Die ℓ-Para-Stetigkeit einer Funktion kann man überprüfen, indem man die Urbilder von ℓ-para-offenen Hauptfiltern betrachtet:

Lemma 3.25. Seien k und l kompakte Elemente eines kompakt faktorisierten L-Bereichs. Dann gilt ↑l ⊑ ↑k genau dann, wenn k ≤^{E} l gilt.

Beweis. Sei ↑l ⊑ ↑k. Daraus folgt unmittelbar ↑l ⊆ ↑k und somit k ⊑ l. Wir zeigen k ≤^{E} l, indem wir nachweisen, daß (k ⊑ l) für passende M-vergleichbare Elemente die Bedingung ♢ erfüllt (siehe Bemerkung 2.3). Sei dazu k ⊑ x ≤^{M} y ⊒ l. Aus ↑l ⊑ ↑k erhalten wir x ∈ ↑l und damit k ≤^{E} l.

Sei umgekehrt k ≤^{E} l. Wegen der Bedingung ♢ gilt für alle x ∈ ↑k und y ∈ ↑l mit x ≤^{M} y die Beziehung l ⊑ x. Daraus folgt ↑l ⊑ ↑k.

Satz 3.26. Seien D und D′ kompakt faktorisierte L-Bereiche. Eine Abbildung f: D → D′ ist genau dann ℓ-para-stetig, wenn für alle kompakten Elemente k ∈ D′ das Urbild f^{−1}[↑k] ℓ-para-offen ist und für kompakte Elemente k, l ∈ D′ mit k ≤^{E} l die Beziehung f^{−1}[↑l] ⊑ f^{−1}[↑k] gilt.

Beweis. Sei f ℓ-para-stetig. Dann sind für kompakte Elemente k ∈ D′ die Urbilder f^{−1}[↑k] nach Definition para-offen. Gilt für kompakte Elemente k und l die Ungleichung k ≤^{E} l, so folgt ↑l ⊑ ↑k aus Lemma 3.25, und wegen der ℓ-Para-Stetigkeit erhalten wir f^{−1}[↑l] ⊑ f^{−1}[↑k].

Sei umgekehrt für alle kompakten Elemente k ∈ D′ das Urbild f^{−1}[↑k] ℓ-para-offen, und aus k ≤^{E} l folge f^{−1}[↑l] ⊑ f^{−1}[↑k]. Bevor wir die ℓ-Para-Stetigkeit von f zeigen, überlegen wir, daß f Scott-stetig und M-monoton ist. Die Menge {↑k | k ∈ K(D′)} ist eine Basis der Scott-Topologie auf D′. Da die Urbilder dieser Hauptfilter nach Voraussetzung ℓ-para-offen und damit Scott-offen sind, ist f Scott-stetig. Zum Nachweis der M-Monotonie von f seien x ≤^{M} y Elemente aus D und k, l ∈ K(D′) mit f(x) ⊒ k ≤^{E} l ⊑ f(y). Nach Lemma 3.25 gilt

• y  • f(y)
[figure: M]
x •  \overline{f  ^{}}f(x) •
..........• l
[figure: E]
k •

↑l ⊑ ↑k, und nach Voraussetzung folgt damit f^{−1}[↑l] ⊑ f^{−1}[↑k]. Da x in f^{−1}[↑k] und y in f^{−1}[↑l] liegt, folgt x ∈ f^{−1}[↑l]. Also gilt l ⊑ f(x), und mit Korollar 2.20 erhalten wir f(x) ≤^{M} f(y).

Jetzt weisen wir die ℓ-Para-Stetigkeit von f nach. Dazu zeigen wir mit Satz 3.19, daß die Urbilder ℓ-para-offener Mengen ℓ-para-offen sind. Für die ℓ-Para-Offenheit einer Menge V müssen wir nachweisen, daß V Scott-offen ist, daß es zu jedem x ∈ V ein kleinstes Element V ⟨x⟩ in der Menge V ∩ ↓_{M}{x} gibt und daß diese Abbildung V ⟨·⟩ Scott-stetig ist.

Sei deshalb U eine ℓ-para-offene Teilmenge von D′. Wegen der Scott-Stetigkeit von f ist f^{−1}[U] Scott-offen. Zu x ∈ f^{−1}[U] gibt es ein kompaktes Element k ⊑ f(x) in fix(U⟨·⟩) ∩ K(D′), dem größten Erzeugendensystem von U. Nach Voraussetzung ist f^{−1}[↑ k] ℓ-para-offen, also enthält diese Menge ein kleinstes Element x′, das M-unter x liegt. Für jedes andere Element y ≤^{M} x aus

x •  f(x) •
[figure: M; M]
• y \overline{f^{}}• f(y)
..........  ..........
x′ • M  k ⊔^{f(x)}l •
[figure: E]
k •  • l

f^{−1}[U] gibt es ein kompaktes l ∈ fix(U) mit l ⊑ f(y). Da U ℓ-para-offen ist und k und l Elemente eines Erzeugendensystems von U sind, müssen sie kollaborieren,

d.h. es gilt k, l ≤^{E} k ⊔^{f(x)} l. Wegen der Bedingung ♢ erhalten wir k ⊔^{f(x)} l ⊑ f(y) und somit y ∈ f^{−1}[↑k]. Da x′ das kleinste Element in f^{−1}[↑k] ∩ ↓_{M}{x} ist, folgt x′ ⊑ y, und x′ ist das gesuchte kleinste Element in f^{−1}[U] ∩ ↓_{M}{x}.

Die Abbildung, die einem Element x aus f^{−1}[↑ k] das kleinste Element (f^{−1}[↑k])⟨x⟩ in f^{−1}[↑k] ∩ ↓_{M}{x} zuordnet, ist wegen der ℓ-Para-Offenheit von f^{−1}[↑ k] Scott-stetig. Wie wir gerade gesehen haben, ist dies aber auch das kleinste Element in f^{−1}[U] ∩ ↓_{M}{x}. Damit ist auch die Abbildung (f^{−1}[U])⟨·⟩ Scott-stetig, was die ℓ-Para-Offenheit von f^{−1}[U] zeigt.

Für die ℓ-Para-Stetigkeit von f bleibt als letztes noch zu zeigen, daß f^{−1}[·] monoton ist. Seien dazu U und V zwei ℓ-para-offene Teilmengen von D′ mit U ⊑ V. Es ist klar, daß f^{−1}[U] ⊆ f^{−1}[V] gilt. Da wir die M-Monotonie von f bereits gezeigt haben, gilt für x ∈ f^{−1}[V] und y ∈ f^{−1}[U] mit x ≤^{M} y die Ungleichung f(x) ≤^{M} f(y). Aus f(x) ∈ V ⊒ U ∋ f(y) erhalten wir deshalb f(x) ∈ U und somit x ∈ f^{−1}[U]. Das zeigt f^{−1}[U] ⊑ f^{−1}[V].

Die ℓ-Para-Stetigkeit einer Abbildung kann man auch algebraisch charakterisieren:

Satz 3.27. Eine Abbildung f: D → D′ zwischen zwei kompakt faktorisierten L-Bereichen ist genau dann ℓ-para-stetig, wenn sie die folgenden vier Eigenschaften erfüllt:

1. f ist Scott-stetig,

2. f ist M-monoton,

3. f erhält Pullbacks von M’s,

4. f erhält beliebige nichtleere M-beschränkte Infima.

Beweis. Sei f ℓ-para-stetig. Dann ist f nach Definition Scott-stetig, und die M-Monotonie von f zeigt man wie im Beweis von Satz 3.26.

Wir zeigen nun, daß f Pullbacks von M’s erhält und betrachten dazu Elemente x ≤^{M} z ⊒ y aus D. Aufgrund der Monotonie von f gilt f(x ⊓ y) ⊑ f(x) ⊓ f(y). Für die umgekehrte Vergleichbarkeit betrachten wir ein beliebiges kompaktes k ⊑ f(x) ⊓ f(y). Nach Voraussetzung ist f^{−1}[↑k] ℓ-para-

f^{−1}[↑k]  z •  f(z) •
[figure: . . . . . . . . . . . . . . . . . . . . . . . . . .; M; ..........]
x • • y \overline{f^{}}f(x) • • f(y)
[figure: M; ..............................]
• x ⊓ y  • f(x) ⊓ f(y)
[figure]
• f(x ⊓ y)
k •^{..........}

offen und wegen Lemma 3.16 somit gegen Pullbacks von M’s abgeschlossen; aus x, y ∈ f^{−1}[↑k] folgt deshalb x ⊓ y ∈ f^{−1}[↑k]. Also gilt f(x ⊓ y) ⊒ k, woraus wir f(x ⊓ y) ⊒ ^{⨆↑} K_{f(x)⊓f(y)} = f(x)⊓f(y) schließen. Damit ist f(x)⊓f(y) = f(x⊓y) gezeigt.

Mit einer analogen Überlegung zeigen wir, daß f beliebige nichtleere M-be-schränkte Infima erhält: Für ∅ ≠ X ≤^{M} y ist wieder f(⨅ X) ⊑ ⨅ f[X] klar, und wir müssen nur die andere Vergleichbarkeit zeigen. Sei k ein kompaktes Element mit k ⊑ ⨅ f[X]. Die Menge f^{−1}[↑ k] ist ℓ-para-offen und nach Korollar 3.18 damit gegen nichtleere M-beschränkte Infima abgeschlossen. Da sie X enthält, gilt ⨅ X ∈ f^{−1}[↑k], was f(⨅ X) ⊒ k zeigt. Da k ∈ K_{⨅ f[X]} beliebig war, haben wir f(⨅ X) = ⨅ f[X] nachgewiesen.

Erfülle nun umgekehrt f die vier Bedingungen des Satzes. Wir zeigen die ℓ-Para-Stetigkeit von f mit Hilfe von Satz 3.26, indem wir überprüfen, daß für kompakte Elemente k ≤^{E} l aus D′ das Urbild f^{−1}[↑k] ℓ-para-offen ist und die Ungleichung f^{−1}[↑l] ⊑ f^{−1}[↑k] gilt.

Sei k ∈ D′ kompakt und U := f^{−1}[↑k]. Nach Satz 3.19 ist U genau dann ℓ-para-offen, wenn U Scott-offen ist, es zu jedem x ∈ U ein kleinstes Element U⟨x⟩ in der Menge U ∩ ↓_{M}{x} gibt und die Abbildung U⟨·⟩ Scott-stetig ist. Die Scott-Offenheit von U ist klar. Für x ∈ U gilt wegen der vierten Bedingung f(⨅ ↓_{M}{x}) = ⨅ f[↓_{M}{x}] ⊒ k, d.h. ⨅ ↓_{M}{x} ∈ U. Wegen Korollar 2.8 haben wir ⨅ ↓_{M}{x} ≤^{M} x, also ist ⨅ ↓_{M}{x} das kleinste Element in U ∩↓_{M}{x}. Um die Scott-Stetigkeit von U⟨·⟩ zu zeigen, überlegen wir zuerst, daß die Abbildung monoton ist. Seien x ⊑ y zwei Elemente aus U. Für jedes y′ ≤^{M} y gilt x ⊓

• y
[figure]
x •  • y′ M
[figure]
x ⊓ y′ • M  • ⨅ ↓_{M}{y} = U⟨y⟩
..........
⨅ ↓^{M}{x} = U⟨x⟩ •

y′ ≤^{M} x nach Bemerkung 2.3, und da f nach Voraussetzung Pullbacks von M’s erhält, folgt f(x ⊓ y′) = f(x) ⊓ f(y′) ⊒ k ⊓ k = k, d.h. x ⊓ y′ liegt in U. Wegen ⨅ ↓_{M}{x} ⊑ x ⊓ y′ ⊑ y′ erhalten wir U⟨x⟩ = ⨅ ↓_{M}{x} ⊑ ⨅ ↓_{M}{y} = U⟨y⟩. Sei nun {x_{i} | i ∈ I} gerichtet. Wegen der Monotonie gilt ^{⨆↑} U⟨x_{i}⟩ ⊑ U⟨^{⨆↑} x_{i}⟩. Da für jedes i ∈ I die Ungleichung U⟨x_{i}⟩ ≤^{M} x_{i} gilt und M nach Satz 2.15 gegen gerichtete Suprema abgeschlossen ist, folgt ^{⨆↑} U⟨x_{i}⟩ ≤^{M} ^{⨆↑} x_{i}. Daraus erhalten wir U⟨^{⨆↑} x_{i}⟩ ⊑ ^{⨆↑} U⟨x_{i}⟩ und damit die Scott-Stetigkeit von U⟨·⟩. Also ist U = f^{−1}[↑k] ℓ-para-offen.

Seien k ≤^{E} l ∈ D′ kompakt. Aus f^{−1}[↑ k] ∋ x ≤^{M} y ∈ f^{−1}[↑ l] folgt f(x) ≤^{M} f(y), da f als M-monoton vorausgesetzt ist. Ferner gilt f(x) ⊒ k und f(y) ⊒ l. Wegen der Bedingung ♢ folgt l ⊑ f(x), was f^{−1}[↑l] ⊑ f^{−1}[↑k] zeigt.

Damit ist die ℓ-Para-Stetigkeit von f bewiesen.

Korollar 3.28. Jede ℓ-para-stetige Abbildung (zwischen kompakt faktorisierten L-Bereichen) ist para-stetig.

Also ist LFALG eine Unterkategorie von FDCPO. Wir können somit auch auf der Menge der ℓ-para-stetigen Funktionen die verallgemeinerte Berry-Ordnung betrachten (siehe Definition 3.9). Für die so geordnete Menge von Funktionen zwischen zwei kompakt faktorisierten L-Bereichen D und D′ schreiben wir [D →^{ℓ} D′].

Für ℓ-para-stetige Abbildungen gilt das Analogon von Lemma 3.10:

Korollar 3.29. Seien D und D′ zwei kompakt faktorisierte L-Bereiche und f, g: D → D′ ℓ-para-stetige Funktionen. Trägt D das topologische Faktorisierungssystem, so gilt f ⊑_{B} g genau dann, wenn f punktweise kleiner als g ist. Ist D stabil faktorisiert, dann sind f ⊑_{B} g und f ≤_{b} g äquivalent.

Satz 3.27 erlaubt es uns, die Sätze 3.7, 3.8 und 3.12 auf ℓ-para-stetige Abbildungen zu übertragen:

Korollar 3.30. Die ℓ-para-stetigen Abbildungen von 2_{T} in einen kompakt faktorisierten L-Bereich D stehen in Bijektion zu den Paaren (x ⊑ y) ∈ D^{2}, d.h. [2_{T} →^{ℓ} D] ≅ ⊑_{D}.

Korollar 3.31. Die para-stetigen Abbildungen von 2_{S} in einen kompakt faktorisierten L-Bereich D stehen in Bijektion zu den Elementen aus M, d.h. [2_{S} →^{ℓ} D] ≅ M.

Korollar 3.32. Für einen kompakt faktorisierten L-Bereich D sind [D →^{ℓ} 2_{S}] und die Menge der ℓ-para-offenen Teilmengen von D ordnungsisomorph.

Dieser Isomorphismus ordnet einer ℓ-para-stetigen Funktion f die Menge f^{−1}[{1}] und einer ℓ-para-offenen Menge U ihre charakteristische Funktion χ_{U} zu.

Beweis. Sei f: D → 2_{S} ℓ-para-stetig und U := f^{−1}[{1}]. Dann ist U als Urbild der ℓ-para-offenen Menge {1} ℓ-para-offen.

Sei umgekehrt U ⊆ D ℓ-para-offen und χ_{U}: D → 2_{S} die zugehörige charakteristische Funktion. Nach Lemma 3.16 ist U para-offen, und wegen Satz 3.12 ist χ_{U} deshalb Scott-stetig, M-monoton und erhält Pullbacks von M’s. Da U nach Korollar 3.18 gegen nichtleere M-beschränkte Infima abgeschlossen ist, erhält χ_{U} solche Infima. Wegen Satz 3.27 ist χ_{U} deshalb ℓ-para-stetig.

Da ℓ-para-offene Mengen para-offen und ℓ-para-stetige Abbildungen parastetig sind, folgt aus Satz 3.12 sofort, daß diese Bijektion ein Ordnungsisomorphismus ist.

Es gibt noch eine weitere Art, ℓ-Para-Stetigkeit zu verstehen. Für jedes Element x ∈ D eines kompakt faktorisierten L-Bereichs D ist nach Korollar 2.8 ↓_{M}{x} ein vollständiger Verband, wobei die Infima wie in D berechnet werden. Im folgenden bezeichnen wir diesen Unterverband mit M^{x}. Wegen Bemerkung 2.3 sind alle in M^{x} vergleichbaren Elemente M-vergleichbar. Nach Satz 2.15 ist M gegen gerichtete Suprema abgeschlossen, also stimmen die gerichteten Suprema in M^{x} mit denen in D überein. Über andere Suprema kann man im allgemeinen keine Aussage machen.

Wir überlegen nun, daß jedes x ∈ D in einem maximalen solchen Unterverband enthalten ist: Nach Satz 2.15 ist für jedes x ∈ L die Menge ↑^{M} {x} gegen gerichtete Suprema abgeschlossen, also induktiv. Mit Hilfe des Zornschen Lemmas finden wir deshalb ein M-maximales Element x̂ ≥^{M} x. Dann ist M x̂ ein maximaler solcher Unterverband, der x enthält.

Satz 3.33. Eine Abbildung f: D → D′ zwischen kompakt faktorisierten L-Be-reichen ist genau dann ℓ-para-stetig, wenn die folgenden drei Bedingungen erfüllt sind:

1. f ist Scott-stetig,

2. f erhält Pullbacks von M’s,

3. für M-maximale Elemente x ∈ D und y ∈ D′ mit f(x) ≤^{M} y gilt f(M^{x}) ⊆ M^{y} und die Einschränkung f_{|M^{x}}: M^{x} → M^{y} ist Lawson-stetig.

Beweis. Sei f ℓ-para-stetig. Nach Satz 3.27 ist dann f Scott-stetig und erhält Pullbacks von M’s. Sei x ein M-maximales Element in D und y eines in D′ mit f(x) ≤^{M} y. Da f nach Satz 3.27 M-monoton ist, gilt f(M^{x}) ⊆ M^{y}. Die Einschränkung von f auf M^{x} erhält nach Satz 3.27 alle nichtleeren Infima und ist deshalb nach Proposition 1.17 Lawson-stetig.

Erfülle f umgekehrt die drei Bedingungen des Satzes. Wegen Satz 3.27 reicht es für die ℓ-Para-Stetigkeit zu zeigen, daß f M-monoton ist und nichtleere M-beschränkte Infima erhält:

Sei x ≤^{M} x̃ ∈ D. Wie wir bei den Vorüberlegungen zu diesem Satz gesehen haben, gibt es M-maximale Elemente x̂ ∈ D und y ∈ D′ mit x ≤^{M} x̃ ≤^{M} x̂ und f(x) ⊑ f(x̃) ⊑ f(x̂) ≤^{M} y. Nach Voraussetzung gilt f[M x̂] ⊆ M^{y} und deshalb f(x) ≤^{M} y; mit Bemerkung 2.3 erhalten wir daraus f(x) ≤^{M} f(x̃).

Seien ∅ ≠ X ≤^{M} x und x̂ ∈ D bzw. y ∈ D′ M-maximale Elemente mit x ≤^{M} x̂ bzw. f(x̂) ≤^{M} y. Binäre Infima in M x̂ sind Pullbacks von M’s und werden deshalb nach Voraussetzung von f erhalten. Da f_{|M x̂}: M x̂ → M^{y} Lawson-stetig ist, erhalten wir f(⨅ X) = ⨅ f[X] aus Proposition 1.17.

Die ℓ-para-stetigen Abbildungen sind also Scott-stetige Funktionen, die (maximale) Unterverbände der Form M^{x} des einen Bereichs Lawson-stetig in solche des anderen abbilden und die Pullbacks von M’s erhalten, und damit die relative Lage dieser Unterverbände respektieren.

Wir vergleichen zum Schluß noch einmal ℓ-Para-Stetigkeit und Para-Stetig-keit. Aus Lemma 3.16 wissen wir bereits, daß ℓ-para-offene Mengen immer paraoffen sind. Für I-Bereiche gilt auch die Umkehrung:

Satz 3.34. Sei D ein kompakt faktorisierter LI-Bereich. Dann ist eine Teilmenge U ⊆ D genau dann ℓ-para-offen, wenn sie para-offen ist.

Beweis. Sei U para-offen. Nach Voraussetzung ist U Scott-offen, also gilt U =↑(U ∩ K). Sei N die Menge der M-minimalen kompakten Elemente aus U und k ∈ U ∩ K ein kompaktes Element. Da D ein I-Bereich ist, ist das Anfangsstück ↓ k und somit auch die Menge ↓k ∩ U endlich. Also liegt unter k ein M-minimales Element aus U und somit aus N. Damit gilt U = ↑(U ∩ K) = ↑N, und es ist nur noch zu zeigen, daß N kollaboriert. Seien k_{1}, k_{2} ∈ N durch x beschränkt. Nach Proposition 1.7 ist k_{1} ⊔^{x} k_{2} kompakt, und für jedes Element y ≤^{M} k_{1} ⊔^{x} k_{2} mit y ∈ U gilt y ⊓ k_{1} ≤^{M} k_{1} nach Bemerkung 2.3. Da U gegen Pullbacks von M’s abgeschlossen ist, liegt y⊓k_{1} in U, und aus der M-Minimalität von k_{1} folgt y ⊓ k_{1} = k_{1} und somit k_{1} ⊑ y. Analog erhalten wir k_{2} ⊑ y und damit k_{1} ⊔^{x} k_{2} ⊑ y. Mithin ist k_{1} ⊔^{x} k_{2} M-minimal in U. Daraus folgt k_{1}, k_{2} ≤^{E} k_{1} ⊔^{x} k_{2}. Damit kollaboriert N, und U = ↑N ist ℓ-para-offen.

Korollar 3.35. Eine Abbildung zwischen kompakt faktorisierten LI-Bereichen ist genau dann ℓ-para-stetig, wenn sie para-stetig ist.

Korollar 3.36. Eine Abbildung f: D → D′ zwischen zwei stabil kompakt faktorisierten LI-Bereichen ist genau dann ℓ-para-stetig, wenn sie stabil ist.

Das ist genau dann der Fall, wenn es zu jedem x ∈ D und jedem y ∈ K_{f(x)} ein kleinstes x′ ⊑ x mit f(x′) ⊒ y gibt.

Beweis. Die erste Behauptung folgt unmittelbar aus Korollar 3.35 und Satz 3.5; die zweite erhalten wir aus Proposition 1.11.

52

4 Kartesisch abgeschlossene Kategorien

No problem is so big or so complicated that it can’t be run away from.

—Linus

Charles M. Schulz, PEANUTS

Es ist leicht, in FDCPO bzw. LFALG Produkte zu konstruieren, indem man komponentenweise faktorisiert.

Für Exponentiale ist die Situation schwieriger. Lamarche gibt in [Lam95] mit Hilfe von event structures eine kartesisch abgeschlossene volle Unterkategorie von LFALG an, die aus dI-Bereichen besteht; andere sind im Moment nicht bekannt. Man kann aber über die Struktur einer kartesisch abgeschlossenen vollen Unterkategorie von FDCPO bzw. LFALG a priori eine Reihe von Aussagen machen; wir werden sehen, daß die Exponentiale die entsprechenden Hom-Mengen mit einer geeigneten Ordnung sein müssen. Unter gewissen Zusatzbedingungen können wir diese Ordnung und den M-Anteil des Faktorisierungssystems bestimmen.

Daraus werden wir schließen, daß solche Kategorien immer eine kartesisch abgeschlossene Kategorie mit Scott-stetigen Funktionen und eine mit stabilen enthalten. Für diese beiden klassischen Fälle sind eine Reihe von Einschränkungen bekannt, die sich auf mögliche kartesisch abgeschlossene Kategorien faktorisierter Bereiche übertragen.

4.1 Produkte

In allen bisher erwähnten Kategorien sind die einelementigen Bereiche terminale Objekte. Diese kann man nur auf eine Weise faktorisieren. Einen dieser Bereiche bezeichnen wir im folgenden mit 1. Da nach den Lemmata 3.2 und 3.22 alle konstanten Abbildungen Morphismen sind, hat jeder Bereich mit mehr als einem Element mindestens zwei Endomorphismen. In allen vollen Unterkategorien von FDCPO und LFALG müssen deshalb die terminalen Objekte einelementig sein.

Damit repräsentiert für jede volle Unterkategorie C einer dieser beiden Kategorien der Funktor FDCPO(1, −) den Vergißfunktor |−|: C → SET. Also ist der Vergißfunktor stetig, und wir erhalten unmittelbar:

Lemma 4.1. Sei ∏ D_{i} ein Produkt in einer vollen Unterkategorie von FDCPO bzw. LFALG mit einem terminalen Objekt. Dann ist die ∏ D_{i} zugrundeliegende Menge das kartesische Produkt der Mengen |D_{i}|.

Die Konstruktion von Produkten geht nun recht einfach:

Satz 4.2. Sei (D_{i})_{i∈I} eine Familie von Objekten aus FDCPO bzw. LFALG. Wenn man das Produkt der zugrundeliegenden dcpo’s durch

(x_{i})_{i∈I} ≤^{E} (y_{i})_{i∈I} :⇔ (∀i ∈ I) x_{i} ≤^{E} y_{i}
(x_{i})_{i∈I} ≤^{M} (y_{i})_{i∈I} :⇔ (∀i ∈ I) x_{i} ≤^{M} y_{i}

faktorisiert, so ist es zusammen mit den Projektionen p_{i} auf die einzelnen Komponenten ein Produkt in der entsprechenden Kategorie.

Ist die Indexmenge I endlich oder sind alle D_{i} punktiert, dann führt das Produkt nicht aus FCONT und FALG heraus.

Beweis. Da die Ordnung komponentenweise erklärt ist, ist für S- bzw. L-dcpo’s das Produkt wieder eine S- bzw. L-dcpo. Das Produkt von stetigen bzw. algebraischen Bereichen ist stetig bzw. algebraisch, wenn entweder die Indexmenge endlich ist oder alle Bereiche punktiert sind.

Wir überprüfen nun, daß die angegebenen Relationen E und M ein Faktorisierungssystem auf ∏ D_{i} bilden, das die äquivalenten Bedingungen aus Satz 2.14 erfüllt. Sei (x_{i})_{i∈I} ⊑ (y_{i})_{i∈I}. Dann gilt für jedes i ∈ I die Ungleichung x_{i} ≤^{E} x_{i}\y_{i} ≤^{M} y_{i}, und die Eindeutigkeit dieser Faktorisierung ist klar. Da M komponentenweise erklärt ist und gerichtete Suprema komponentenweise berechnet werden, ist M gegen gerichtete Suprema abgeschlossen. Mit dieser Faktorisierung ist ∏ D_{i} also eine faktorisierte dcpo. Sind alle D_{i} kompakt faktorisierte Bereiche, dann sind Elemente ((x_{i})_{i∈I} ≤^{E} (y_{i})_{i∈I}) das gerichtete Supremum von solchen der Form ((k_{i})_{i∈I} ≤^{E} (l_{i})_{i∈I}), wobei die k_{i} und l_{i} kompakt und für fast alle i ∈ I gleich ⊥ sind. Somit ist ∏ D_{i} kompakt faktorisiert.

Da die Ordnung und die Faktorisierung komponentenweise definiert sind, ist es klar, daß die Projektionen para-stetig bzw. ℓ-para-stetig sind.

Seien f_{i}: D′ → D_{i} para-stetige bzw. ℓ-para-stetige Abbildungen. Wir betrach-

∏ D_{i}
[figure: ⟨f_{i} | i ∈ I⟩]
[figure: D′; f_{i}; D_{i}; p_{i}]

ten die Abbildung ⟨f_{i} | i ∈ I⟩: D′ → ∏ D_{i} mit x ↦ (f_{i}(x))_{i∈I}. Es ist klar, daß ⟨f_{i} | i ∈ I⟩ Scott-stetig ist. Da die Ordnung und Faktorisierung komponentenweise definiert sind und alle f_{i} Morphismen sind, ist ⟨f_{i} | i ∈ I⟩ M-monoton, erhält Pullbacks von M’s und gegebenenfalls nichtleere M-beschränkte Infima, d.h. ⟨f_{i} | i ∈ I⟩ ist ein Morphismus.

Die Eindeutigkeit von ⟨f_{i} | i ∈ I⟩ ist klar. Also ist ∏ D_{i} ein Produkt in der entsprechenden Kategorie.

Korollar 4.3. Die vollen Unterkategorien der topologisch und der stabil faktorisierten Bereiche von FDCPO bzw. LFALG sind gegen Produkte abgeschlossen.

Wir überlegen nun, was wir generell über die Struktur der Produkte in vollen Unterkategorien von FDCPO bzw. LFALG sagen können.

Satz 4.4. Sei C eine volle Unterkategorie von FDCPO oder LFALG, die ein terminales Objekt und die beiden zweielementigen Bereiche 2_{T} und 2_{S} enthält. Existiert in C ein Produkt ∏ D_{i}, so ist die Ordnung und die Faktorisierung komponentenweise, also wie im Satz 4.2, erklärt.

Beweis. Aus den Sätzen 3.7 und 3.8 bzw. den Korollaren 3.30 und 3.31 wissen wir, daß für jedes Objekt D die Entsprechungen ⊑_{D} ≅ [2_{T} → D] und M ≅ [2_{S} → D] gelten. Wegen der universellen Eigenschaft des Produkts gilt [2_{T} → ∏ D_{i}] ≅ ∏[2_{T} → D_{i}] und [2_{S} → ∏ D_{i}] ≅ ∏[2_{S} → D_{i}]. Wegen Lemma 4.1 ist | ∏ D_{i}| = ∏ |D_{i}|; deshalb ist auf ∏ D_{i} die Ordnung und M wie in Satz 4.2 komponentenweise erklärt. Nach Proposition 1.24 bestimmt M die Relation E bereits eindeutig, und damit ist das Produkt von der in Satz 4.2 beschriebenen Form.

4.2 Exponentiale

Zuerst bemerken wir, daß in kartesisch abgeschlossenen vollen Unterkategorien von FDCPO oder LFALG die Exponentiale [D → D′] als zugrundeliegende Menge gerade die Menge der Morphismen zwischen D und D′ haben:

Lemma 4.5. Seien C eine kartesisch abgeschlossene volle Unterkategorie von FDCPO oder LFALG sowie D und D′ Objekte aus C. Dann gilt |[D → D′]| ≅ C(D, D′).

Beweis. Wir haben am Anfang des vorangegangenen Abschnitts gesehen, daß die terminalen Objekte in C einelementig sind. Eines davon bezeichnen wir wieder mit 1. Der Funktor C(1, −) repräsentiert den Vergißfunktor |−|: C → SET.

[D → D′] [D → D′] × D \overline{ε ^{}}D′
[figure: ∀f]
[figure: 1; ∃!f̄; .; .; .; .; .; .; .; .; .; 1 × D; f̄×1; .; .; .; .; .; .; .; .; .]

Wegen der universellen Eigenschaft des Exponentials erhalten wir deshalb C(D, D′) ≅ C(1 × D, D′) ≅ C(1, [D → D′]) ≅ |[D → D′]|.

Im folgenden identifizieren wir die Elemente eines solchen Exponentials mit den entsprechenden Morphismen.

Für ein Objekt D aus FDCPO oder LFALG können wir wegen [2_{T} → D] ≅ ⊑_{D} und [2_{S} → D] ≅ M die Ordnung und den M-Anteil des Faktorisierungssystems mit Hilfe von Morphismen charakterisieren (siehe Satz 3.7 und 3.8 bzw. Korollar 3.30 und 3.31). Deshalb können wir die Methode aus dem vorangegangenen Lemma verwenden und auf dem Exponential die Ordnung und M a priori bestimmen:

Satz 4.6. Seien C eine kartesisch abgeschlossene volle Unterkategorie von FDCPO oder LFALG, die 2_{T} enthält, sowie D und D′ Objekte aus C. Für Abbildungen f_{0}, f_{1} : D → D′ gilt f_{0} ⊑_{[D→D′]} f_{1} genau dann, wenn f_{0} und f_{1} in der verallgemeinerten Berry-Ordnung f_{0} ⊑_{B} f_{1} vergleichbar sind.

Beweis. Wir nutzen wieder die universelle Eigenschaft des Exponentials aus:

[D → D′] [D → D′] × D \overline{ε ^{}}D′
[figure: ∀f]
[figure: 2_{T}; ∃!f̄; .; .; .; .; .; .; .; .; .; 2_{T} × D; f̄×1; .; .; .; .; .; .; .; .; .]

Es gilt ⊑_{[D→D′]} ≅ C(2_{T} , [D → D′]) ≅ C(2_{T} × D, D′). Wir müssen jetzt diesen Isomorphismus noch etwas genauer betrachten: Sei f ∈ C(2_{T} × D, D′). Wegen der Kommutativität des Dreiecks muß f̄ die folgende Abbildung sein: f̄: 2_{T} → [D → D′] mit 0 ↦ f(0, ·) und 1 ↦ f(1, ·). Also entsprechen in [D → D′] vergleichbare Morphismen f_{0} und f_{1} den Abbildungen f(0, ·) und f(1, ·) für einen Morphismus f: 2_{T} × D → D′, und wegen Satz 4.4 kennen wir die Struktur von 2_{T} × D.

Sei f: 2_{T} ×D → D′ ein Morphismus. Wir zeigen f(0, ·) ⊑_{B} f(1, ·). Wegen der Monotonie von f ist f(0, ·) punktweise kleiner als f(1, ·), und für x ≤^{M} y ∈ D ist das folgende Diagramm ein Pullback:

[figure: (1, y) •; M; (0, y) • • (1, x); M; • (0, x)]

Da f Pullbacks von M’s erhält, gilt f(0, x) = f(0, y) ⊓ f(1, x) und somit f(0, ·) ⊑_{B} f(1, ·).

Seien jetzt f_{0}, f_{1} : D → D′ Morphismen mit f_{0} ⊑_{B} f_{1}. Um f_{0} ⊑_{[D→D′]} f_{1} zu zeigen, reicht es nach der Vorüberlegung nachzuweisen, daß die Abbildung f: 2_{T} × D → D′: (i, x) ↦ f_{i}(x) ein Morphismus ist. Dazu überprüfen wir die Eigenschaften aus Definition 3.1 bzw. Satz 3.27:

Die Scott-Stetigkeit von f folgt unmittelbar aus der von f_{1} und f_{2}. Wegen 0 ≰^{M} 1 sind M-vergleichbare Elemente in 2_{T} ×D von der Form (i, x) ⊑ (i, y) mit x ≤^{M} y. Also gilt f(i, x) = f_{i}(x) ≤^{M} f_{i}(y) = f(i, y). Somit ist f M-monoton.

Um zu zeigen, daß f Pullbacks von M’s erhält, betrachten wir nacheinander die verschiedenen Fälle, die bei solchen Pullbacks auftreten können:

1. (i, x) ⊑ (i, z) ≥^{M} (i, y):

(i, z) •  \overline{f  ^{}}• f_{i}(z)
[figure: M]
(i, x) •  • (i, y)  f^{i}(x) •  • f_{i}(y)
[figure: M]
• (i, x ⊓ y)  f^{i}(x ⊓ y) •

Es gilt f_{i}(x ⊓ y) = f_{i}(x) ⊓ f_{i}(y), da f_{i} Pullbacks von M’s erhält.

2. (0, x) ⊑ (1, x) ≥^{M} (1, y):

(1, x) •  \overline{f  ^{}}• f_{1}(x)
[figure: M]
(0, x) •  • (1, y)  f^{0}(x) •  • f_{1}(y)
[figure: M]
• (0, y)  f^{0}(y) •

Wegen f_{0} ⊑_{B} f_{1} und y ≤^{M} x gilt f_{0}(y) = f_{1}(y) ⊓ f_{0}(x).

3. (0, x) ⊑ (1, z) ≥^{M} (1, y): Diesen Fall können wir auf die beiden vorherigen zurückführen:

(1, z) •  \overline{f  ^{}}f^{1}(z) •
[figure: M]
(0, z) •  • (1, y)  f^{0}(z) •  (2)  • f_{1}(y)
[figure: M]
(0, x) •  • (0, y)  f^{0}(x) •  (1)  • f_{0}(y)
[figure: M]
• (0, x ⊓ y)  • f_{0}(x ⊓ y)

Es gilt f_{0}(x ⊓ y) = f_{0}(x) ⊓ f_{0}(y) = f_{0}(x) ⊓ (f_{0}(z) ⊓ f_{1}(y)) = f_{0}(x) ⊓ f_{1}(y).

Damit haben wir gezeigt, daß f Pullbacks von M’s erhält.

Ist C eine volle Unterkategorie von LFALG, so müssen wir noch zeigen, daß f nichtleere M-beschränkte Infima erhält: Wegen 0 ≰^{M} 1 folgt das daraus, daß f_{0} und f_{1} solche Infima erhalten. Also ist f ein Morphismus.

Satz 4.7. Seien C eine kartesisch abgeschlossene volle Unterkategorie von FDCPO oder LFALG, die 2_{T} und 2_{S} enthält, sowie D und D′ Objekte aus C. Für Abbildungen f_{0}, f_{1} : D → D′ gilt f_{0} ≤^{M} f_{1} genau dann, wenn f_{0} und f_{1} die Berry-Bedingung f_{0} ≤_{b} f_{1} erfüllen und f_{0} punktweise M-kleiner als f_{1} ist, d.h. für alle x ∈ D gilt f_{0}(x) ≤^{M} f_{1}(x).

Beweis. Wie im Beweis des vorigen Satzes sehen wir, daß zwei M-vergleichbare Funktionen f_{0} ≤^{M} f_{1} gerade einem Morphismus f: 2_{S} × D → D′ entsprechen. Die Isomorphie M_{[D→D′]} ≅ [2_{S} → [D → D′]] ≅ [2_{S}×D → D′] ist über den Zusammenhang f(i, x) = f_{i}(x) gegeben.

Sei f: 2_{S} × D → D′ ein Morphismus. Wegen der Monotonie von f ist f(0, ·) punktweise kleiner als f(1, ·). In 2_{S} gilt 0 ≤^{M} 1, also ist für x ⊑ y das folgende Diagramm ein Pullback:

[figure: (1, y) •; M; (1, x) • • (0, y); M; • (0, x)]

Da f Pullbacks von M’s erhält, gilt f(0, x) = f(1, x) ⊓ f(0, y). Das zeigt f(0, ·) ≤_{b} f(1, ·). Wegen 0 ≤^{M} 1 und der M-Monotonie von f gilt für alle x ∈ D die Ungleichung f(0, x) ≤^{M} f(1, x).

Sei umgekehrt f_{0} ≤_{b} f_{1}, und für alle x ∈ D gelte f_{0}(x) ≤^{M} f_{1}(x). Wir zeigen, daß die zugehörige Abbildung f: 2_{S} × D → D′ ein Morphismus ist, indem wir die Bedingungen aus Definition 3.1 bzw. Satz 3.27 überprüfen:

Die Scott-Stetigkeit von f folgt unmittelbar aus der von f_{0} und f_{1}. Sei x ≤^{M} y. Wegen der M-Monotonie der f_{i} gilt f(i, x) = f_{i}(x) ≤^{M} f_{i}(y) = f(i, y) und f(0, x) = f_{0}(x) ≤^{M} f_{1}(x) ≤^{M} f_{1}(y). Also ist f M-monoton. Daß f Pullbacks von M’s erhält, zeigen wir mit einer Fallunterscheidung:

1.–3. Die Fälle (i, x) ⊑ (i, z) ≥^{M} (i, y), (0, x) ⊑ (1, x) ≥^{M} (1, y) und (0, x) ⊑ (1, z) ≥^{M} (1, y) können wir wörtlich aus dem Beweis von Satz 4.6 übernehmen.

4. (1, x) ⊑ (1, y) ≥^{M} (0, y):

(1, y) •  \overline{f  ^{}}• f_{1}(y)
[figure: M]
(1, x) •  • (0, y)  f^{1}(x) •  • f_{0}(y)
[figure: M]
• (0, x)  f^{0}(x) •

Wegen f_{0} ≤_{b} f_{1} gilt f_{0}(x) = f_{1}(x) ⊓ f_{0}(y).

5. (1, x) ⊑ (1, z) ≥^{M} (0, y): Diesen Fall kann man in Fall 1 und 4 zerlegen:

(1, z) •  \overline{f  ^{}}• f_{1}(z)
[figure: M]
(1, x) •  • (0, z)  f^{1}(x) •  (4)  • f_{0}(z)
[figure: M; M]
(0, x) •  • (0, y)  f^{0}(x) •  (1)  • f_{0}(y)
[figure: M]
(0, x ⊓ y) •  f^{0}(x ⊓ y) •

Es gilt f_{0}(x ⊓ y) = f_{0}(x) ⊓ f_{0}(y) = (f_{1}(x) ⊓ f_{0}(z)) ⊓ f_{0}(y) = f_{1}(x) ⊓ f_{0}(y).

Die Fälle (0, x) ⊑ (1, y) ≥^{M} (0, y) bzw. (0, x) ⊑ (1, z) ≥^{M} (0, y) kann man auf (0, x) ⊑ (0, y) ≥^{M} (0, y) bzw. (0, x) ⊑ (0, z) ≥^{M} (0, y) und somit auf den 1. Fall zurückführen. Also erhält f Pullbacks von M’s.

Ist C eine volle Unterkategorie von LFALG, so verbleibt zu zeigen, daß f nichtleere M-beschränkte Infima erhält. Sei ∅ ≠ X ≤^{M} (i, y). Gilt X ⊆ {i} × D für i = 0 oder i = 1, so folgt die Behauptung unmittelbar aus der ℓ-Para-Stetigkeit von f_{i}. Der interessante Fall ist also der, in dem X sowohl Elemente aus {0} × D als auch aus {1} × D enthält. In diesem Fall spalten wir X in X = X_{0} ∪ X_{1} mit ∅ ≠ X_{0} = {0} × X̃_{0} und ∅ ≠ X_{1} = {1} × X̃_{1} auf. Es gilt dann X_{0} ≤^{M} (0, y), X_{1} ≤^{M} (1, y) und ⨅ X = ⨅(X_{0} ∪ X_{1}) = ⨅ X_{0} ⊓ ⨅ X_{1}. Wegen Satz 2.8 haben wir ⨅ X_{0} ≤^{M} (0, y) ≤^{M} (1, y). Wir wissen bereits, daß f Pullbacks von M’s erhält. Da f_{0} und f_{1} nichtleere M-beschränkte Infima erhalten, folgt

f(⨅ X) = f(⨅ X_{0} ⊓ ⨅ X_{1})  = f(⨅ X_{0}) ⊓ f(⨅ X_{1})
= f_{0}(⨅ X̃_{0}) ⊓ f_{1}(⨅ X̃_{1}) = (⨅ f_{0}[X̃_{0}]) ⊓ (⨅ f_{1}[X̃_{1}])
= (⨅ f[X_{0}]) ⊓ (⨅ f[X_{1}]) = ⨅ f[X_{0} ∪ X_{1}]
= ⨅ f[X].

Damit haben wir gezeigt, daß f ein Morphismus ist.

Aus diesen beiden Sätzen erhält man, daß Exponentiale, genauso wie Produkte, nicht aus den vollen Unterkategorien der topologisch bzw. stabil faktorisierten dcpo’s herausführen:

Korollar 4.8. Seien C eine kartesisch abgeschlossene volle Unterkategorie von FDCPO oder LFALG, die 2_{T} und 2_{S} enthält, sowie D und D′ Objekte aus C. Ist D′ topologisch faktorisiert, dann auch [D → D′].

Beweis. Seien f, g ∈ [D → D′] zwei Morphismen mit f ≤^{M} g. Nach Satz 4.7 gilt dann für jedes x ∈ D die Ungleichung f(x) ≤^{M} g(x). Da D′ topologisch faktorisiert ist, folgt f(x) = g(x), und die Relation M ist gerade die Gleichheit. Nach Bemerkung 2.3 gilt E = M′, und somit trägt [D → D′] das topologische Faktorisierungssystem (⊑_{B}, =).

Korollar 4.9. Seien C eine kartesisch abgeschlossene volle Unterkategorie von FDCPO oder LFALG, die 2_{T} und 2_{S} enthält, sowie D und D′ stabil faktorisierte Objekte aus C. Dann ist [D → D′] stabil faktorisiert.

Beweis. Seien f ⊑_{B} g Morphismen aus [D → D′]. Da D′ das stabile Faktorisierungssystem trägt, gilt f(x) ≤^{M} g(x) für alle x ∈ D. Da auch D stabil faktorisiert ist, fallen die verallgemeinerte Berry-Ordnung und die (gewöhnliche) Berry-Ordnung zusammen (vgl. Lemma 3.10). Nach Satz 4.7 gilt deshalb f ≤^{M} g, d.h. die Relationen M und ⊑_{B} sind gleich. Nach Bemerkung 2.3 gilt E = M′, und somit ist [D → D′] durch (=, ⊑_{B}), d.h. stabil, faktorisiert.

Korollar 4.10. Sei C eine kartesisch abgeschlossene volle Unterkategorie von FDCPO oder LFALG, die 2_{T} und 2_{S} enthält. Dann sind die beiden vollen Unterkategorien von C, die die topologisch bzw. die stabil faktorisierten Objekte enthalten, kartesisch abgeschlossen.

Jede solche Kategorie C enthält also eine kartesisch abgeschlossene Kategorie von Bereichen mit Scott-stetigen Funktionen und eine mit stabilen Funktionen.

Beweis. Am Anfang des Kapitels haben wir überlegt, daß terminale Objekte in solchen vollen Unterkategorien einelementig sein müssen. Diese sind trivialerweise topologisch und stabil faktorisiert. Deshalb folgt die Behauptung unmittelbar aus den Korollaren 4.3, 4.8 und 4.9.

Das letzte Korollar schränkt die Suche nach kartesisch abgeschlossenen Kategorien faktorisierter Bereiche ein, da es in der Literatur eine Reihe von Ergebnissen über maximale kartesisch abgeschlossene Kategorien von Bereichen gibt: Für punktierte Bereiche mit Scott-stetigen Funktionen sind die Kategorien der L-Bereiche und der FS-Bereiche bzw. die der aL- und der bifiniten Bereiche die maximalen kartesisch abgeschlossenen vollen Unterkategorien von CONT bzw. ALG (siehe [AJ95, Section 4]). In [Zha95] zeigt Zhang, daß die dI-Bereiche die größte kartesisch abgeschlossene Kategorie von Scott-Bereichen mit stabilen Funktionen bilden. Dieses Ergebnis und Korollar 4.10 widerlegen die Vermutung Lamarches, daß die Kategorie der kompakt faktorisierten Scott-Bereiche kartesisch abgeschlossen sei [Lam95, Conjecture 26].

Das Ergebnis von Zhang zeigt auch, daß man sich nicht auf BC-Bereiche beschränken kann, wenn man eine deutlich größere kartesische abgeschlossene Kategorie als die von Lamarche angegebene konstruieren will. Ein möglicher Ansatz könnte sein, die Ergebnisse von Amadio auf faktorisierte Bereiche zu übertragen; in [Ama91] gibt er eine kartesisch abgeschlossene Kategorie mit bifiniten S-Bereichen und stabilen Funktionen an.

62

Literatur

[AJ95] S. Abramsky and A. Jung. Domain theory. In S. Abramsky, D. M. Gabbay, and T. S. E. Maibaum, editors, Handbook of Logic in Computer Science, volume 3. Clarendon Press, 1995.

[Ama91] R. Amadio. Bifinite domains: Stable case. Technical Report LIENS-91-3, Ecole Normale Supérieure, 1991.

[Ber78] G. Berry. Stable models of typed λ-calculi. In Proceedings of the 5th International Colloquium on Automata, Languages and Programming, volume 62 of Lecture Notes in Computer Science, pages 72–89. Springer Verlag, 1978.

[BW84] M. Barr and C. Wells. Toposes, Triples and Theories. Springer Verlag, 1984.

[GHK^{+}80] G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, and D. S. Scott. A Compendium of Continuous Lattices. Springer Verlag, 1980.

[Gir86] J.-Y. Girard. The system F of variable types: Fifteen years later. Theoretical Computer Science, 45:159–192, 1986.

[Gir87] J.-Y. Girard. Linear logic. Theoretical Computer Science, 50:1–102, 1987.

[Gun92] C. Gunter. Semantics of Programming Languages. Structures and Techniques. Foundations of Computing. MIT Press, 1992.

[Lam95] F. Lamarche. A large cartesian closed category of domains. Submitted to: Information and Computation, 1995.

[Mac71] S. Mac Lane. Categories for the Working Mathematician. Springer Verlag, 1971.

[Win88] G. Winskel. An introduction to event structures. In J. W. de Bakker, editor, Linear Time, Branching Time, and Partial Order in Logics and Models for Concurrency, volume 354 of Lecture Notes in Computer Science, pages 364–399. Springer Verlag, 1988.

[Zha95] G.-Q. Zhang. The largest cartesian closed category of stable domains. draft paper, 1995.

64