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 $(x,y)\in G\times G$ können bzgl. der partiellen Ordnung geordnet werden.

Definition[Bearbeiten]

Sei $M\not =\emptyset$ sei eine Grundmenge. Eine partielle Ordnung ist eine Relation $R\subseteq M\times M$ , für die $(x,y)\in R$ als $x\leq y$ notiert wird. Für eine partielle Ordnung ist eine reflexive, antisymmetrische und transitive Relation, bei der also

(Reflexivität) $x\leq x$
(Antisymmetrie) $x\leq y\land y\leq x\;\Rightarrow \;x=y$
(Transitivität) $x\leq y\land y\leq z\;\Rightarrow \;x\leq z$

für alle $x,y,z\in M$ erfüllt sind.

Bemerkung - Umkehrrelation[Bearbeiten]

Die Umkehrrelation einer HalbordnungGegeben sei ein abgeschlossener, spitzer und konvexer Kegel $K$ , der ein nichtleeres Inneres besitzt. Dann definiert

x\preccurlyeq _{K}y{\text{ genau dann, wenn }}y-x\in K

eine Halbordnung auf $\mathbb {R} ^{n}$ . Der Kegel enthält also alle „positiven“ Elemente, also diejenigen, für die $0_{n}\preccurlyeq _{K}y$ gilt. Analog lässt sich durch

x\prec _{K}y{\text{ genau dann, wenn }}y-x\in K^{\circ }

eine strikte Halbordnung auf $\mathbb {R} ^{n}$ definieren. Dabei ist $K^{\circ }$ das Innere des Kegels.

$y\preceq x:\Longleftrightarrow x\leq y$

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 $N1$ und die grün markierten Verbindungen zu größeren Elementen.

$N12$ und $N13$ steht in keiner $\geq$ - bzw. $\leq$ -Beziehung zu $N1$ .

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 $(x_{i})_{i\in I}$ Indexmengen $I$ , die z.B. im Gegensatz zu Folgen mit der Indexmenge $\mathbb {N}$ auf $I$ nur eine partielle Ordnung besitzen und keine vollständige Ordnung mehr.

Teilmengebeziehung als Halbordnung[Bearbeiten]

Jede Teilmengenbeziehung $A\subseteq B$ auf einem System ${\mathfrak {M}}$ von Mengen ist eine Halbordnung, denn sie ist

transitiv, da die Teilmenge einer Teilmenge von $A$ auch Teilmenge von $A$ ist:

{C\subseteq B\subseteq A}\ \Rightarrow \ {C\subseteq A}

für alle

A,B,C\in {\mathfrak {M}};

reflexiv, da jede Menge eine Teilmenge ihrer selbst ist:

{A\subseteq A}

für alle

A\in {\mathfrak {M}};

und antisymmetrisch, da nur $A$ selbst sowohl Teilmenge als auch Obermenge von $A$ ist:

{(A\subseteq B)}\wedge {(B\subseteq A)}\ \Rightarrow \ {A=B}

für alle

A,B\in {\mathfrak {M}}.

Komponentenweise kleiner als Halbordnung[Bearbeiten]

Die Halbordnung komponentenweise-kleiner-oder-gleich, $\leq ^{n}:$ Für eine fest gewählte natürliche Zahl $n$ und zwei Tupel aus einer Menge von $n$ -Tupeln}} gilt:

{\left(a_{1},a_{2},\ldots ,a_{n}\right)}\leq ^{n}{\left(b_{1},b_{2},\ldots ,b_{n}\right)}\ :\Longleftrightarrow \ a_{i}\leq b_{i}

für jedes

i=1,2,\ldots ,n;

Bemerkung - Komponentenweise kleiner[Bearbeiten]

Manchmal wird die Halbordnung komponentenweise-kleiner-oder-gleich $\leq ^{n}:$ auch ohne Exponent $n$ notiert, also $\preceq ,$ $\leq$ oder einfach $\prec$ geschrieben.

Durch einen Kegel induzierte Halbordnung[Bearbeiten]

Gegeben sei ein abgeschlossener, spitzer und konvexer Kegel $K$ , der ein nichtleeres Inneres besitzt. Dann definiert

x\preccurlyeq _{K}y{\text{ genau dann, wenn }}y-x\in K

eine Halbordnung auf $\mathbb {R} ^{n}$ . Der Kegel enthält also alle „positiven“ Elemente, also diejenigen, für die $0_{n}\preccurlyeq _{K}y$ gilt. Analog lässt sich durch

x\prec _{K}y{\text{ genau dann, wenn }}y-x\in K^{\circ }

eine strikte Halbordnung auf $\mathbb {R} ^{n}$ definieren. Dabei ist $K^{\circ }$ 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, $\mid :$ Für zwei natürliche Zahlen gilt:

{a\mid b}\ ({a\ \mathrm {teilt} \ b}):\Longleftrightarrow \ \exists ~n\in \mathbb {N} :n\cdot a=b.

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.