Zur Hauptnavigation Zum Inhaltsbereich Zur Suche Zum Seitenfu├č


Mark-Oliver Stehr

Zyklische Ordnungen - Axiome und einfache Eigenschaften

Mark-Oliver Stehr

Diplomarbeit am Fachbereich Informatik, Universität Hamburg, Juni 1996

Kurzfassung:

Das Ziel dieser Arbeit ist es auf systematische Weise, ausgehend von einer Axiomatisierung azyklischer Ordnungen, schrittweise zu Axiomen für zyklische Ordnungen zu gelangen. Es wurde dabei angestrebt, eine möglichst allgemeine mathematische Theorie zu entwickeln, ebenso wie es die Theorie azyklischer Ordnungen ist.

Den Ausgangspunkt für die Formalisierung bildet eine recht allgemeine Repräsentation mit Hilfe von Wortmengen, die wir auch als verallgemeinerte Relationen bezeichnen und die sich als Verallgemeinerungen von formalen Sprachen auffassen lassen.

Wir definieren die zentralen Begriffe der Einfachheit (Wiederholungsfreiheit innerhalb von Wörtern), Teilwort- und Rotationsabgeschlossenheit sowie Konsistenz (Widerspruchsfreiheit), Vollständigkeit, Totalität (für totale Ordnungen) und Transitivität in verschiedenen Varianten. Sowohl azyklische wie auch zyklische Ordnungen können mit Hilfe dieser Axiome als spezielle verallgemeinerte Relationen aufgefaßt werden. Die Wörter der Ordnung sind dabei als endliche, totale Teilordnungen zu interpretieren, die zusammengefaßt die gesamte Ordnung konstituieren. Zyklizität wird durch Rotationsabgeschlossenheit formalisiert. Analog zur Transitivität azyklischer Ordnungen wird außerdem einer Form zyklischer Transitivität gefordert.

Parallel zu Axiomatisierung werden viele einfache und intuitive Eigenschaften zyklischer Ordnungen abgeleitet. Insbesondere wird die unmittelbare Nachfolgerrelation untersucht und aufgezeigt, daß diese im allgemeinen höchstens eine Abstraktion zyklischer Ordnungen darstellen kann, da es verschiedene zyklische Ordnungen mit identischer Nachfolgerrelation gibt.

Das Hauptresultat dieser Arbeit ist die Darstellbarkeit von zyklischen Ordnungen durch verallgemeinerte Relationen (hier als Basen bezeichnet), deren Wortlänge auf drei beschränkt ist. Dies bedeutet, daß die meisten interessanten zyklischen Ordnungen als Mengen von Tripeln aufgefaßt werden können.

Abschließend definieren wir die Eigenschaft der globalen Orientiertheit als Erweiterbarkeit zu einer totalen Ordnung. Interessanterweise besitzen nicht alle zyklischen Ordnungen diese anschauliche Eigenschaft. Wir können jedoch zeigen, daß die Klasse der global orientierten, zyklischen Ordnungen identisch ist mit der Klasse der aufschneidbaren, zyklischen Ordnungen, wenn wir eine geeignete Schnittdefinition verwenden.

Ressourcen:
Postscript-Version dieser Arbeit in gzip-Format (907 kByte)
Achtung! Die erste Seite enthält ein Bild einer zyklischen Ordnung, das beim Ausdruck reichlich Zeit braucht.

Letzte Änderung: 17:40 19.05.2011
Impressum