Ordnungen, Verbände und Relationen mit Anwendungen 9783834895325, 3834895326 [PDF]

Zitiervorschau

Rudolf Berghammer Ordnungen, Verbande und Relationen mit Anwendungen

Leitfaden der Informatik Herausgegeben von Prof. Dr. Bernd Becker Prof. Dr. Friedemann Mattern Prof. Dr. Heinrich Muller Prof. Dr. Wilhelm Schafer Prof. Dr. Dorothea Wagner Prof. Dr. Ingo Wegener

Die Leitfaden der Informatik behandein • Themen aus der Theoretischen, Praktischen und Technischen Informatik entsprechend dem aktuellen Stand der Wissenschaft in einer systematischen und fundierten Darstellung des jeweiligen Gebietes • Methoden und Ergebnisse der Informatik, ausgearbeitet und dargestellt aus der Sicht der Anwendung in einer fur Anwender verstandlichen, exakten und prazisen Form. Die Bande der Reihe wenden sich zum einen als Grundlage und Erganzung zu Vorlesungen der Informatik an Studierende und Lehrende in Informatik-Studiengangen an Hochschulen, zum anderen an „Praktiker", die sich einen Uberblick uber die Anwendungen der Informatik (-Methoden) verschaffen wollen; sie dienen aber auch in Wirtschaft, Industrie und Verwaltung tatigen Informatikerinnen und Informatikem zur Fortbildung in praxisrelevanten Fragestellungen ihres Faches.

I

www.viewegteubner.de

Rudolf Berghammer

Ordnungen,Verbande und Relationen mit Anwendungen STUDIUM

VIEWEG+ TEUBNER

Bibliografische Information der Deutschen Nationalbibliothek Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet uber abrufbar.

1.Auflage2008 Alle Rechte vorbehalten © Vieweg+Teubner | GWV Fachverlage GmbH, Wiesbaden 2008 Lektorat: Ulrich Sandten | Kerstin Hoffmann Vieweg+Teubner ist Teil der Fachverlagsgruppe Springer Science+Business Media. www.viewegteubner.de Das Werk einschlieBlich aller seiner Telle ist urheberrechtlich geschutzt. Jede Verwertung auBerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlags unzulassig und strafbar. Das gilt insbesondere fur Vervielfaltigungen, Ubersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten waren und daher von jedermann benutzt werden durften. Umschlaggestaltung: KunkelLopka Medienentwicklung, Heidelberg Druck und buchbinderische Verarbeitung: Strauss Offsetdruck, Morlenbach Gedruckt auf saurefreiem und chlorfrei gebleichtem Papier. Printed in Germany ISBN 978-3-8348-0595-9

Einleitung In dieser Ausarbeitung von Vorlesungen, welche in den letzten Jahren an der ChristianAlbrechts-Universitat zu Kiel abgehalten wurden, wird versucht, eine Einfiihrung in die Ordnungs- und Verbandstheorie und den damit eng verbundenen algebraischen Kalkiil der binaren Relationen zu geben und Anwendungen insbesondere in der Informatik zu demonstrieren. Die eben erwahnten Gebiete spielen heute in vielen Bereichen der reinen und angewandten Mathematik und der Informatik eine groBe Rolle. Etwa haben sehr viele Satze der Mathematik fiber auf- und absteigende Ketten, wie sie etwa bei auflosbaren Gruppen oder Noetherschen Ringen auftreten, einen ordnungstheoretischen Hintergrund. Gleiches gilt fiir die Methoden der Informatik zum Beweis von Terminierungen von Deduktionen und Programmen. Ein weiteres Beispiel ist die Boolesche Algebra, ein spezieller Zweig der Verbandstheorie. Durch sie ist die Algebraisierung der Aussagenlogik gegeben. Ihre Bedeutung fiir insbesondere die Informatik ergibt sich bei den Schaltabbildungen und den logischen Schaltungen. Als letztes Beispiel seien noch Fixpunkte genannt. Sehr viele praktisch bedeutende Probleme lassen sich als Fixpunktprobleme formulieren, etwa die Berechnung der relationalen transitiven und reflexiv-transitiven Hiillen oder das damit eng verbundene Erreichbarkeitsproblem auf Graphen. Algorithmische Losungen dieser Probleme ergeben sich dann oft direkt aus den „konstruktiven" Fixpunktsatzen iiber vollstandigen Verbanden. Fixpunkte spielen auch bei der Semantik von Programmiersprachen eine groBe Rolle. Es gibt wahrscheinlich kein mathematisches Konzept, das so viele Anwendungen findet, wie das einer Ordnung. Diese wurden in der Mathematik schon sehr friih betrachtet. Einzelne der grundlegenden Gedanken gehen sogar sehr weit zuriick, teilweise bis Aristoteles. Eine liberragende Bedeutung kam den Ordnungen insbesondere zu Beginn des 20. Jahrhunderts zu, als die Grundlagen der Mathematik intensiv diskutiert wurden. Untrennbar damit sind die Namen G. Cantor, E. Zermelo und F. Hausdorff verbunden. G. Cantor begriindete die Mengenlehre. Von E. Zermelo stammt die Einsicht, daB das Auswahlaxiom ein wesentliches Beweismittel der Mathematik ist. Seine heutzutage mit Abstand am haufigsten verwendete Konsequenz - man sollte genauer sagen: aquivalente Formulierung - ist das bekannte Lemma von M. Zorn. F. Hausdorff hat wohl als erster die Ordnungsaxiome explizit formuliert. Sein Maximalkettenprinzip ist aquivalent zum Zornschen Lemma. Den Ursprung der Verbandstheorie kann man wohl bei G. Boole sehen, der schon im 19. Jahrhundert eine Algebraisierung der Aussagenlogik untersuchte, sowie bei R. Dedekind, der sich den Verbanden von den Idealen bei algebraischen Zahlen, also von der algebraischen Seite her naherte. Von R. Dedekind stammt auch die heute iibliche algebraische

vi

Einleitung

Verbandsdefinition, von ihm auch als Dualgruppe bezeichnet, wie etwa in der grundlegenden Arbeit „Uber die von drei Moduln erzeugte Dualgruppe" (Mathematische Annalen 53, 371-403, 1900). Die Untersuchungen von G. Boole wurden sehr bald von anderen Wissenschaftlern aufgegriffen, insbesondere um 1880 von C.S. Peirce in seiner „Algebra of Logic" und von E. Schroder, der von 1885 bis 1895 das umfassende Werk „Algebra der Logik" in drei Banden publizierte. Eine Vereinheitlichung zu der Theorie, wie wir sie heutzutage kennen, ist in erster Linie das Werk von G. Birkhoff. Es sind aber noch eine Reihe von weiteren bekannten Mathematikern zu nennen, die zur Grundlegung und Weiterentwicklung der Verbandstheorie als einem Teilgebiet sowohl der modernen Algebra als auch der Ordnungstheorie beigetragen haben. Ohne Vollstandigkeitsanspruch seien genannt R.P. Dilworth, O. Frink, P. Halmos, L. Kantorovik, K. Kuratowski, O. Ore und H.M. Stone. Bei einer Historic der Relationenalgebra kann man ebenfalls bei A. de Morgan, C.S. Peirce und E. Schroder ansetzen. Diese gingen jedoch alle noch komponentenbehaftet vor, verwendeten also die Element beziehung (in verschiedensten Schreibweisen). Wichtige Daten fiir das komponentenfreie, algebraische Vorgehen, bei dem die Elementbeziehung vermieden wird und stattdessen nur mehr Operationen auf Relationen Verwendung finden, sind 1941, als A. Tarski eine Axiomatisierung der abstrakten Relationenalgebra publizierte, und 1955, als er zusammen mit L. Chin die grundlegendsten arithmetischen Gesetze der abstrakten Relationenalgebra veroffentlichtc"^. Nach und nach land der Ansatz Anklang und vielfaltige Anwendungen und im Jahr 1989 erschien, von G. Schmidt und T. Strohlein und in Deutsch, das erste Lehrbuch liber abstrakte Relationenalgebra. Eine erste gemeinsame Konferenz iiber relationale Methoden in der Informatik (Initiative RelMiCS) fand 1994 statt. Bis heute folgten neun weltweite weitere Treffen dieser Art, die bisher letzte RelMiCS-Konferenz im Jahr 2008 fand auf der Insel Frauenchiemsee im Chiemsee (Bayern) statt. Weil Relationenalgebra als Gebiet wesentlich jiinger als Verbandstheorie ist, verzichten wir hier auf die Nennung weiterer Namen von Wissenschaftlern, da eine Bewertung ihres endgiiltigen wissenschaftlichen Einflusses derzeit noch unmoglich erscheint. Der erste Teil des vorliegenden Buchs ist den Ordnungen und Verbanden gewidmet. Hier werden zuerst die Grundlagen der Ordnungs- und Verbandstheorie vorgestellt. Darauf aufbauend werden dann spezielle Klassen von Ordnungen und Verbanden diskutiert, die wichtigsten Fixpunktsatze bewiesen und anhand von einigen exemplarischen Anwendungen vertieft, Vervollstandigungs- und Darstellbarkeitsfragen geklart und transfinite Zahlen mit dem Auswahlaxiom und wichtigen Folgerungen (genauer: dazu aquovalenten Formulierungen, wie etwa das Lemma von M. Zorn) und Anwendungen prasentiert. Ein Abschnitt iiber einige spezielle Anwendungen von Ordnungen und Verbanden in der Informatik schlieJ3t den ersten Teil ab. Der zweite Teil des Buchs ist relativ kurz. Zuerst werden hier die grundlegenden Begriffe von konkreten, also mengentheoretischen, Relationen eingefiihrt und dann im Rahmen von abstrakten Relationenalgebren algebraisiert. Ein Teil der Axiome einer Relationenalgebra ist rein verbandstheoretischer Natur; hierdurch wird die Briicke zum ersten Teil des Buchs hergestellt. Nach dieser Einfiihrung in die Algebra der Relationen ^Man vergleiche hierzu mit A. Tarski, On the calculus of relations, Journal of Symbolic Logic 6, 73-89, 1941. und mit L.H. Chin, A. Tarski, Distributive and modular laws in the arithmetic of relation algebras, University of California Publications in Mathematics (new series) 1, 341-384, 1951.

Einleitung

vii

und das Rechnen in ihr befassen wir uns noch mit den strukturerhaltenden Funktionen zwischen Relationen. Dies ist in unserem Rahmen insbesondere wichtig, um die „Eindeutigkeit" von axiomatisch definierten relationalen Strukturen festzulegen, welche spater bei gewissen Anwendungen eine Rolle spielen. Im dritten Teil des Buchs konzentrieren wir uns auf Anwendungen von Relationen beim Algorithmenentwurf. Dabei werden oftmals auch ordnungs- und verbandstheoretische Eigenschaften wesentlich mitverwendet und auch Fixpunkte spielen bei vielen dieser Anwendungen eine zentrale Rolle. Zuerst zeigen wir, wie man Datenstrukturen - insbesondere Mengen und einige der in der universellen Algebra bzw. der Semantik von Programmiersprachen wichtigen sogenannten Bereichskonstruktionen - mit relationenalgebraischen Mitteln beschreiben kann. Dann demonstrieren wir anhand von vielen Fallstudien, wie man konkrete Probleme durch relationale Programme lost, also durch Programme, die sich im wesentlichen nur auf einen Datentyp fiir Relationen mit all den friiher vorgestellten Operationen stiitzen. Viele der Beispiele sind graphentheoretischer Natur, wie etwa die Bestimmung der erreichbaren Knoten, das Testen von Kreisfreiheit oder die Berechnung von Kernen. Wir betrachten aber auch Probleme aus anderen Bereichen, beispielsweise kombinatorische 2-Personen-Spiele oder die Bestimmung kanonischer Epimorphismen. Durch die relationale Behandlung von ordnungs- und verbandstheoretischen Problemen wird schlieBlich der Bogen wieder zuriick zum ersten Teil des Buchs geschlagen. In dem dritten Teil wird auch ein seit 1993 an der ChristianAlbrechts-Universitat zu Kiel entwickeltes Computersystem zur Manipulation und Visualisierung von konkreten Relationen und zum relationalen Programmieren vorgestellt. Mit Hilfe des Systems, genannt R E L V I E W , wurden insbesondere auch viele Beispiele des Buchs berechnet und entsprechende Bilder erstellt. Zum Schlufi soil noch kurz auf die begleitende Literatur eingegangen werden. Beziiglich der Ordnungs- und Verbandstheorie sei insbesondere auf die folgenden Lehrbiicher verwiesen. - H. Gericke, Theorie der Verbande, 2. Auflage, Bibliographisches Institut, 1967. - H. Hermes, Einfiihrung in die Verbandstheorie, 2. Auflage, Springer Verlag, 1967. - G. Birkhoff, Latice Theory, 3. Auflage, Amer. Math. Soc, 1967. - M. Erne, Einfiihrung in die Ordnungstheorie, Bibliographisches Institut, 1982. - R. Freese, J. Jezek, J.B. Nation, Free Latices, Amer. Math. Soc, 1995. - B.A. Davey, H.A. Priestley, Introduction to Lattices and Orders, 2. Auflage, Cambridge University Press, 2002. Beziiglich der konkreten Relationen und der Relationenalgebra verweisen wir auf das nachfolgende, schon oben erwahnte Lehrbuch. - G. Schmidt, T. Strohlein, Relationen und Graphen, Springer Verlag, 1989. Eine iiberarbeitete englischsprachige Ausgabe dieses Buchs ist 1993 als „ Relations and Graphs" ebenfalls beim Springer Verlag erschienen. AuBer dem Buch von G. Schmidt und T. Strohlein existiert derzeit kein weiteres Lehrbuch (dieser Ausdruck sei betont) iiber die

viii

Einleitung

algebraische, komponentenfreie Behandlung der binaren Relationen. Es gibt jedoch das nachfolgend angegebene Buch, in dem sich einige fiihrende Expert en in Relationenalgebra vor einigen Jahren zusammengetan haben, und eine Reihe von sehr gut lesbaren Artikeln iiber die Anwendung von Relationen in verschiedensten Bereichen der Informatik (wie Semantik, Algorithmik, Datenstrukturen, Datenbanken und Linguistik) produzierten. - C. Brink, W. Kahl, G. Schmidt (Herausgeber): Relational Methods in Computer Science, Springer Verlag, 1997. Fiir Leser, die sich vertieft mit Relationenalgebra beschaftigen wollen, seien noch die beiden nachfolgenden Monographien angegeben. Es muJ3 an dieser Stelle jedoch bemerkt werden, daJ3 es sich dabei um keine Lehrbiicher handelt und das Verstehen dieser Biicher eine gute mathematische Ausbildung und teilweise auch einen betrachtlichen Aufwand erfordert. - G. Birkhoff, S. Givant, A Formalization of Set Theory without Variables, Amer. Math. Soc, 1987. - R. Maddux, Relation Algebras, Elsevier, 2006. Weiterhin sei noch auf den Artikel „The origin of relation algebras in the development and axiomatization of the calculus of relations" von R.D. Maddux (Studia Logica 50. Seite 421455, 1991) verwiesen. In ihm werden, sich orientierend an der geschichtlichen Entwicklung, die Grundlagen der axiomatischen Relationenalgebra dargelegt. Besonders interessant ist der Artikel fiir Leser, die an historischen Fakten interessiert sind, den er enthalt ein umfangreiches Literaturverzeichnis und eine Fiille interessanter wortlicher Zitate aus den friihen Arbeit en von A. de Morgan, C.S. Peirce und anderen. Das Lesen dieses Buchs, welches sich primar an Studierende der Informatik und Mathematik im Diplom-Hauptstudium oder im Master-Studium wendet, erfordert relativ wenig tiefgehende Voraussetzungen. Aus der Mathematik werden nur die Grundbegriffe der Mengenlehre und etwas klassische Algebra, mathematische Logik und Graphentheorie vorausgesetzt und aus der Informatik eine gewisse Vertrautheit mit Algorithmik, imperativen Programmiersprachen und den fundamentalsten Programmentwicklungstechniken (wie beispielsweise der Zusicherungsmethode mit Vorbedingung, Nachbedingung und Schleifeninvarianten von R. Floyd und C.A.R. Hoare). Da dies aber alles nicht iiber das hinausgeht, was man iiblicherweise im Diplom-Grundstudium oder den ersten Semestern eines Bachelor-Studiums Informatik oder Mathematik lernt, verzichten wir hier auf die Angabe von entsprechender Literatur. Viele Studierende, Mitarbeiter, Kollegen und Freunde haben in den letzten Jahren durch zahlreiche Vorschlage und Anregungen, konstruktive Kritik und auch aufwendiges Korrekturlesen an der Entstehung dieses Buchs mitgewirkt. Ihnen, die nicht alle namentlich genannt werden konnen, sei an dieser Stelle sehr herzlich gedankt. Danken mochte ich auch Herrn Ingo Wegener fiir seine Unterstiitzung bei der Publikation des Werkes und dem Teubner Verlag fiir die sehr angenehme Zusammenarbeit. Kiel, im Mai 2008

Rudolf Berghammer

Inhaltsverzeichnis 1

Ordnungen und Verbande

1

1.1

Algebraische Beschreibung von Verbanden

1

1.2

Geordnete Mengen

4

1.3

Verbande als spezielle geordnete Mengen

10

1.4

Das Dualitatsprinzip

14

1.5

Nachbarschaft und Diagramme

17

1.6

Konstruktionsmechanismen

21

2

Spezielle Klassen v o n Verbanden

27

2.1

Modulare Verbande

27

2.2

Distributive Verbande

35

2.3

Boolesche Verbande

40

2.4

Vollstandige Verbande

53

3

Fixpunkttheorie

65

3.1

Fixpunktsatze

65

3.2

Anwendung: Schroder-Bernstein-Theorem

74

3.3

Berechnungsinduktion

76

3.4

Hiillenbildungen und Hiillensysteme

80

3.5

Galois-Verbindungen

89

Inhaltsverzeichnis

4

Vervollstandigung und Darstellung m i t t e l s Vervollstandigung

95

4.1

Vervollstandigung durch Ideale

95

4.2

Schnittvervollstandigung

102

4.3

Vergleich der beiden Methoden

108

4.4

Darstellung durch Schnitte

116

4.5

Darstellung durch Abwartsmengen

123

5

Transfinite Zahlen und das A u s w a h l a x i o m

129

5.1

Wohlordnungen und Transfinite Zahlen

129

5.2

Auswahlaxiom und wichtige Folgerungen

138

5.3

Fixpunkte von Abbildungen auf CPOs

146

5.4

Darstellung: Der unendliche Fall

150

5.5

Fixpunktcharakterisierung von Vollstandigkeit

155

6

Einige Informatik-Anwendungen v o n Ordnungen und Verbanden

165

6.1

Schaltabbildungen und logische Schaltungen

165

6.2

Denotationelle Semantik

171

6.3

Nachweis von Terminierung

181

6.4

Verteilte Systeme

190

7

Relationenalgebraische Grundlagen

199

7.1

Konkrete Relationen

199

7.2

Abstrakte Relationenalgebra

205

7.3

Spezielle homogene Relationen

211

7.4

Spezielle heterogene Relationen

217

7.5

Residuen und symmetrische Quotienten

222

8

Strukturerhaltende Funktionen

231

8.1

Der homogene Fall

231

8.2

Der heterogene Fah

239

Inhaltsverzeichnis

xi

8.3

Modifikationen des Homomorphie-Begriffs

241

9

Relationenalgebraische Beschreibung von Datenstrukturen

247

9.1

Elementare Beschreibung von Mengen

247

9.2

Die Potenzmengen-Konstruktion

256

9.3

Weitere relationale Bereichskonstruktionen

260

9.4

Das Computersystem RELVIEW

264

9.5

Anwendungsbeispiele

268

10

Erreichbarkeits- und Zusammenhangsfragen

281

10.1 Berechnung von Erreichbarkeits-Hiillen

281

10.2 Erreichbarkeitsalgorithmen

290

10.3 Progressiv-endhche Relationen und Kreisfreiheit

297

10.4 Berechnung von transitiven Reduktionen

301

11

Berechnung von Kernen

315

11.1 Grundlegendes zur Kernberechnung

315

11.2 Kerne von ungerichteten Graphen

317

11.3 Kernberechnung als Fixpunktproblem

322

12

333

Aquivalenzklassen und kanonische Epimorphismen

12.1 Ein relationales Modell fiir Sequenzen

333

12.2 Spaltenweises Berechnen von Aquivalenzklassen

337

12.3 Charakterisierung kanonischer Epimorphismen

344

13

349

Ordnungs- und verbandstheoretische Fragestellungen

13.1 Einige grundlegende Algorithmen

349

13.2 Diskretheit und Hasse-Diagramme

355

13.3 Berechnung von linearen Erweiterungen

358

13.4 Bestimmung von Untergruppenverbanden

367

xii

Inhaltsverzeichnis

13.5 Algorithmen zu Vervollstandigungen

374

13.6 Testen von Erfiillbarkeit

383

Index

389

Kapitel 1 Ordnungen und Verbande Es gibt zwei Arten, Verbande zu definieren. Die erste Art ist algebraisch und erklart Verbande als spezielle algebraische Strukturen, die zweite Art ist relational und definiert Verbande als spezielle geordnete Mengen. Ein erstes Ziel dieses Kapitels ist es, beide Definitionsmoglichkeiten fiir Verbande einzufiihren und sie als gleichwertig zu beweisen. Weiterhin studieren wir in beiden Fallen Unterstrukturen und die strukturerhaltenden Abbildungen, die sogenannten Homomorphismen. Als nachstes gehen wir auf Nachbarschaftsbeziehungen und die damit zusammenhangenden Hasse-Diagramme zur zeichnerischen Darstellung von Ordnungen ein. Schliefilich stellen wir noch einige wichtige Konstruktionsmechanismen auf Ordnungen und Verbanden vor.

1.1

Algebraische Beschreibung von Verbanden

Wir behandeln Verbande zuerst als algebraische Strukturen, d.h. als Mengen mit inneren Verkniipfungen (d.h. Abbildungen auf ihnen). Der Hauptgrund dafiir ist, daB ein Verband eine weniger gelaufige algebraische Struktur ist als z.B. die Gruppe, der Ring, der Vektorraum oder der Korper. Weiterhin ware bei einer ordnungstheoretischen Einfiihrung wegen der vielen von der Analysis und der linearen Algebra herriihrenden Begriffe auf der speziellen geordneten Menge (M, g: VxW^VxW

if0g){a,b)

=

{fia),g{b))

und bekommt dadurch eine U-stetige Abbildung f 0 g auf V x W und, daB der InduktionsschluB (2) von der simultanen Berechnungsinduktion genau dann gilt, falls ^{a,b)eVxW:

P{a,b) =^ P{if ® g){a,b))

zutrifft. Verwendet man nun die Originalform von Berechnungsinduktion, also Satz 3.3.2, mit dem Pro dukt-Verband V x W, der obigen Eigenschaft P ( 0 , 0 ) als Induktionsbeginn und dem eben angegebenen „neuen InduktionsschluB", so folgt daraus P{fif(^g). Nun zeigt die recht einfach zu beweisende Gleichung /~if^g = {fif,fig) sofort das Gewiinschte. Den allgemeineren Fall n > 2 behandelt man entsprechend mit einem n-stelligen Funktionsprodukt fi0.--0fn von Abbildungen. • Nachfolgend geben wir ein Beispiel fiir die Anwendung von simultaner Berechnungsinduktion an. 3.3.6 Beispiel (Abbildungskomposition) Es sei f : V ^ V eine U-stetige Abbildung auf einem vollstandigen Verband (1/, U , n ) . Damit existieren die kleinsten Fixpunkte fif und fifof, denn mit / ist auch die Komposition / o / monoton. Die Komposition / o / ist, wie man leicht zeigt, sogar U-stetig. Wir wollen /df = fifof beweisen. Wegen f{f{f^f))

= f^f gilt die Abschatzung fifof E M/-

Fixp unktth eorie

Die verbleibende Eigenscheft fif C yU/o/ beweisen wir durch Berechnungsinduktion unter Verwendung von aQb A aQ f{a) als Pradikat P{a^b). Eine Anwendung von Berechnungsinduktion besteht immer aus drei Schritten: Zuldssigkeitstest: Das Pradikat P ist zulassig, denn wir konnen unter Verwendung der Projektionen pi und p2 den ersten Teil als pi{a,b) Q p2{a,b) schreiben und den zweiten Teil als j9i(a, b) Q {f^P2){ci-, b). Die Behauptung folgt somit aus den syntaktischen Kriterien. Induktionsbeginn:

Trivialerweise gelten 0 C 0 und 0 Q / ( O ) .

Induktionsschlufi: Es seien zwei beliebige Elemente a^b ^V tt E f{ci)i vorgegeben. Dann haben wir a Qb

=^ =^ =^

mit P{a,b)^ also a Q b und

f monoton /monoton f monoton und a Q f{a)

f(a) Q f{b) f{f{a))Qf{f{b)) f{a) E f{f{b))

und auch a C /(a)

=^

f monoton.

f{a) Q f{f{a))

Diese beiden Rechnungen zeigen P{f{a),

( / o f){b)).

Aufgrund der Berechnungsinduktion haben wir somit P ( ^ / , ^ / o / ) , insbesondere also die gewiinschte Abschatzung fif C fifof• Die Vorgehensweise dieses Beispiels ist typisch fiir viele Anwendungen von Berechnungsinduktion. Man hat die eigentlich interessante Eigenschaft, oben a E ^, um eine zusatzliche Eigenschaft zu ver star ken, um die Invar ianz der eigentlich interessanten Eigenschaft beweisen zu konnen. Die zusatzliche Eigenschaft entdeckt man dabei natiirlich in der Regel erst wahrend des Beweisversuchs. Man nimmt sie dann in das Pradikat auf und beginnt den Beweis von vorne. Es ist an dieser Stelle noch eine Bemerkung zur Stetigkeit angebracht. In Satz 3.3.2 wird die Abbildung / als U-stetig vorausgesetzt, da der Beweis den Fixpunktsatz fiir stetige Abbildungen verwendet. Es ist iiberraschend, dafi Satz 3.3.2 aber auch schon gilt, wenn die Abbildung / nur monoton ist. Ein Beweis dieser Verallgemeinerung ist mit den bisherigen Hilfsmitteln aber noch nicht moglich.

3.4

Hiillenbildungen und Hullensysteme

Hiillenbildungen spielen in vielen Bereichen der Mathematik und der Informatik eine ausgezeichnete Rolle. Vom Grundstudium her bekannt sind sicher die transitive Hiille

3.4 HiiUenbildungen

81

und Hiillensysteine

R^ = |J^>-^ R^ und die reflexiv-transitive Hiille R* = IJi>o ^^ einer Relation R. Diese beiden Konstruktionen werden wir spater noch relationenalgebraisch genauer studieren. Die transitive Hiille einer Relation erfiillt die Gleichung R^ = RU RR^ und man kann sogar zeigen, daB R^ die kleinste Losung X von X = RU RX ist, die R enthalt. Dieses Beispiel zeigt, daB Hiillenbildungen und Fixpunkte etwas miteinander zu tun haben. Was, das will dieser Abschnitt klaren. Wir beginnen mit den Hiillenbildungen, deren Axiome auf K. Kuratowski zuriickgefiihrt werden konnen: 3.4.1 Definition Eine Abbildung h : V ^ V auf einem vollstandigen Verband (V,U,n) mit Verbandsordnung (F, C) heiBt Hilllenhildung^ falls fiir alle a, 6 G F gilt: (a)

aQh

(b)

a C h{a)

(c)

h{h{a)) = h{a)

=^

h{a) Q h{b)

Monotonie Expansionseigenschaft Idempotenz

Zu a e V nennt man den Bildpunkt h{a) die Hiille von a. Ist a ein Fixpunkt von /i, so heiBt a auch beziiglich h abgeschlossen. • Statt Hiillenbildung sagt man auch Hiillenoperator. Jeder Bildpunkt einer Hiillenbildung /i, also jede Hiille, ist also ein Fixpunkt von h. Statt Idempotenz hatte es auch geniigt, h{h{a)) Q h{a) zu fordern, da h{a) Q h{h{a)) aus der Expansionseigenschaft folgt. Der folgende Satz zeigt, daB man Hiillenbildungen auch durch eine Aquivalenz beschreiben kann. 3.4.2 Satz Die Abbildung h \V ^V auf einem vollstandigen Verband (F, U, n) ist genau dann eine Hiillenbildung, falls fiir alle a, 6 G F gilt a E h{b) ^ ^

h{a) E h{b)

Beweis: „ ^ ^ " Es seien a^b GV. Gilt a C /i(6), so folgt daraus h{a) C h{h{b)) = h{b) nach der Monotonie in der Idempotenz. Gilt hingegen die rechte Seite h{a) Q h{b) der Aquivalenz, so bekommen wir ihre linke Seite a Q h{b) wegen der Expansionseigenschaft. „o^H^)^ In der Kegel sind die grammatikalischen Bildungsgesetze bei solchen rekursiven Definitionen von Mengen so, daB die entsprechende Kleinste-Fixpunkt-Bildung zu einer Hiillenbildung fiihrt und, neben Monotonie, sogar U-Stetigkeit vorliegt. Die Verwendung von Negationen (auf der Metaebene) fiihrt zu Nichtmonotonie und damit zu sinnlosen rekursiven Definitionen. Deshalb tauchen Klauseln wie ...x^M...

=^

...

bei induktiven bzw. rekursiven Definitionen von Mengen M niemals auf.

3.5

Galois-Verbindungen

Im letzten Abschnitt dieses Kapitels wollen wir nun noch einen Begriff studieren, der in einer engen Beziehung zu Hiillenbildungen und -systemen steht, und damit auch in einer engen Beziehung zu Fixpunkten. Es handelt sich um Galois-Verbindungen, die oft auch Galois-Korrespondenzen genannt werden. Wie Hiillen besitzen sie zahlreiche Anwendungen. Wir beginnen mit der Definition des Begriffs, die auf O. Ore zuriickgeht.

90

Fixpunkttheorie

3.5.1 Definition Es seien (M, Qi) und (A^, C2) zwei Ordnungen. Ein Paar von Abbildungen f :M ^N g:N ^M heifit eine Galois-Verbindung zwischen M und A , falls fiir alle a e M und b G N die folgende Eigenschaft zutrifft: a El g{b)