Partielle Ordnung
Einleitung Bearbeiten
Eine partielle Ordnung wird auch "Halbordnung", Partialordnung oder auch Teilordnung genannt[1]. Eine partielle Ordnung verliert gegenüber einer totalen Ordnung die Eigenschaft der Totalität. Das bedeutet, dass zwei beliebige Element nicht notwendiger geordnet werden können - d.h., dass man mit der Relation nicht entscheiden kann welches größer ist. Nur bestimmte Paare können bzgl. der partiellen Ordnung geordnet werden.
Definition Bearbeiten
Sei sei eine Grundmenge. Eine partielle Ordnung ist eine Relation , für die als notiert wird. Für eine partielle Ordnung ist eine reflexive, antisymmetrische und transitive Relation, bei der also
- (Reflexivität)
- (Antisymmetrie)
- (Transitivität)
für alle erfüllt sind.
Bemerkung - Umkehrrelation Bearbeiten
Die Umkehrrelation einer HalbordnungGegeben sei ein abgeschlossener, spitzer und konvexer Kegel , der ein nichtleeres Inneres besitzt. Dann definiert
eine Halbordnung auf . Der Kegel enthält also alle „positiven“ Elemente, also diejenigen, für die gilt. Analog lässt sich durch
eine strikte Halbordnung auf definieren. Dabei ist das Innere des Kegels.
ist wiederum eine Halbordnung.
Visualisierung Bearbeiten
Halbordnungen können in Hasse-Diagrammen visualisiert werden. Der rot markierte Bereich der Verbindungen im Netz markiert die Verbindung zu kleineren Elementen zu und die grün markierten Verbindungen zu größeren Elementen.
und steht in keiner - bzw. -Beziehung zu .
Oberhalbmenge Bearbeiten
Eine Teilmenge einer halbgeordneten Menge heißt Oberhalbmenge, wenn sie zu jedem ihrer Elemente auch alle nachfolgenden Elemente (also alle, die rechts vom Relationssymbol stehen könnten) enthält.
Auswahlaxiom Bearbeiten
Mit Hilfe des Auswahlaxioms kann man beweisen, dass jede Halbordnung in eine Totalordnung eingebettet werden kann. Für endliche Mengen muss man das Auswahlaxiom nicht voraussetzen, und in diesem Fall gibt es zur Konstruktion einer solchen Totalordnung auch explizite Algorithmen (siehe Topologische Sortierung).
Beispiele Bearbeiten
In der Topologie benötigt man für Netze Indexmengen , die z.B. im Gegensatz zu Folgen mit der Indexmenge auf nur eine partielle Ordnung besitzen und keine vollständige Ordnung mehr.
Teilmengebeziehung als Halbordnung Bearbeiten
Jede Teilmengenbeziehung auf einem System von Mengen ist eine Halbordnung, denn sie ist
- transitiv, da die Teilmenge einer Teilmenge von auch Teilmenge von ist:
- für alle
- reflexiv, da jede Menge eine Teilmenge ihrer selbst ist:
- für alle
- und antisymmetrisch, da nur selbst sowohl Teilmenge als auch Obermenge von ist:
- für alle
Komponentenweise kleiner als Halbordnung Bearbeiten
Die Halbordnung komponentenweise-kleiner-oder-gleich, Für eine fest gewählte natürliche Zahl und zwei Tupel aus einer Menge von -Tupeln}} gilt:
- für jedes
Bemerkung - Komponentenweise kleiner Bearbeiten
Manchmal wird die Halbordnung komponentenweise-kleiner-oder-gleich auch ohne Exponent notiert, also oder einfach geschrieben.
Durch einen Kegel induzierte Halbordnung Bearbeiten
Gegeben sei ein abgeschlossener, spitzer und konvexer Kegel , der ein nichtleeres Inneres besitzt. Dann definiert
eine Halbordnung auf . Der Kegel enthält also alle „positiven“ Elemente, also diejenigen, für die gilt. Analog lässt sich durch
- Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikiversity.org/v1/“:): {\displaystyle x \prec_K y \text{ genau dann, wenn } y-x \in K^\circ }
eine strikte Halbordnung auf definieren. Dabei ist das Innere des Kegels. Dies ist ein Spezialfall einer von einem Kegel induzierten Halbordnung, die zu dem Begriff der sogenannten verallgemeinerten Ungleichungen führt, die eine wichtige Rolle in der Optimierung spielen.
Teilerbeziehungen und Teilermengen Bearbeiten
Teilerbeziehung, Für zwei natürliche Zahlen gilt:
Strenge Halbordnung Bearbeiten
So wie sich die strenge Totalordnung von der Totalordnung dadurch unterscheidet, dass Reflexivität und Antisymmetrie durch Irreflexivität ersetzt werden, so wird eine strenge Halbordnung durch Irreflexivität und Transitivität bestimmt. Wie bei der strengen Totalordnung fällt bei der strengen Halbordnung der Gleichheitsstrich in der Notation weg oder wird gar durch ein Ungleichzeichen ersetzt. Ein Beispiel ist die Relation „echte Teilmenge“ bei den Mengen.
Weblinks Bearbeiten
Wikibooks: Mathe für Nicht-Freaks: Ordnungsrelation – Lern- und Lehrmaterialien
Einzelnachweise Bearbeiten
- ↑ Marcel Erné: Einführung in die Ordnungstheorie. Bibliographisches Institut, Mannheim u. a. 1982, lSBN 3-411-01638-8.
Siehe auch Bearbeiten
Seiten-Information Bearbeiten
Diese Seite wurde auf Basis der folgenden Wikipedia-Quelle erstellt: