Zyklische Ordnungen Axiome und einfache Eigenschaften

URN urn:nbn:de:gbv:18-228-7-852
URL
Dokumentart: Diplomarbeit, Magisterarbeit
Sprache: Deutsch
Erstellungsjahr: 1996
Publikationsdatum:
SWD-Schlagwörter: Theoretische Informatik
Freie Schlagwörter (Deutsch): zyklische Axiome
Freie Schlagwörter (Englisch): theory, recurring axiom
DDC-Sachgruppe: Informatik
BK - Klassifikation: 54.99 , 54.10

Kurzfassung auf Deutsch:

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. 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 aufgefait werden. Die Wörter der Ordnung sind dabei als endliche, totale Teilordnungen zu interpretieren, die zusammengefasst die gesamte Ordnung konstituieren. Zyklizität wird durch Rotationsabgeschlossenheit formalisiert. Analog zur Transitivität azyklischer Ordnungen wird ausserdem 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, dass diese im allgemeinen höchstens eine Abstraktion zyklischer Ordnungen darstellen kann. 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, dass die meisten interessanten zyklischen Ordnungen als Mengen von Tripeln aufgefasst werden können. Abschliessend 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, dass die Klasse der global orientierten, zyklischen Ordnungen identisch ist mit der Klasse der aufschneidbaren, zyklischen Ordnungen, wenn wir eine geeignete Schnittdefinition verwenden.

Hinweis zum Urherberrecht

Für Dokumente, die in elektronischer Form über Datenenetze angeboten werden, gilt uneingeschränkt das Urheberrechtsgesetz (UrhG). Insbesondere gilt:

Einzelne Vervielfältigungen, z.B. Kopien und Ausdrucke, dürfen nur zum privaten und sonstigen eigenen Gebrauch angefertigt werden (Paragraph 53 Urheberrecht). Die Herstellung und Verbreitung von weiteren Reproduktionen ist nur mit ausdrücklicher Genehmigung des Urhebers gestattet.

Der Benutzer ist für die Einhaltung der Rechtsvorschriften selbst verantwortlich und kann bei Mißbrauch haftbar gemacht werden.