Eine weitere besondere Klasse von Relationen sind die Ordnungsrelationen. Das sind Relationen, die gewisse Eigenschaften erfüllen. Für Relationen kann man einen Haufen Begriffe definieren. Diese werden hier anhand von Beispielen erläutert.
Eine Ordnung $R$ einer Menge $A$ ist eine binäre Relation $R\subseteq A \times A$. Man unterscheidet zwischen starken und schwachen Ordnungen. Die Eigenschaften Transitivität, Reflexivität und (Anti-)Symmetrie wurden in diesem Skript besprochen.
Schwache Ordnungen sind binäre Relationen, die
sind. Starke (manchmal auch strikte) Odnungen sind Relationen, die
sind.
Gegeben die Relation $R_{N1} \subseteq \mathbb{N} \times \mathbb{N}$. $R_{N1}=\{(x,y)| x \leq y\}$.
$R_{N1}$ enthält also z.B. die Tupel $(1,1),(1,2),(1,3),\dots,(2,2),(2,3),\dots$. Damit ist $R_{N1}$ eine schwache Ordnung, denn die Relation ist
Die Relation $R_{N2} \subseteq \mathbb{N} \times \mathbb{N}$ mit $R_{N2}=\{(x,y)| x < y\}$ ist eine echte Teilmenge von $R_{N1}$. $R_{N2}$ enthält nämlich alle Tupel aus $R_{N1}$ außer die Tupel mit zwei gleichen Zahlen. Also:
$R_{N2}=R_{N1}\setminus \{(n,n) \in R_{N1} | n \in \mathbb{N}\}$
Damit ist $R_{N2}$ genau wie $R_{N1}$ transitiv, aber irreflexiv und asymmetrisch: Es enthält keine Tupel der Form $(1,1),(2,2),\dots$ mehr und ist deshalb irreflexiv. Und: Da es keine zwei Zahlen $a,b$ gibt, für die gilt: $a<b$ und $b<a$, ist $R_{N2}$ auch asymmetrisch.
Also ist $R_{N2}$ eine starke Ordnung. Und zwar nicht irgendeine starke Ordnung, sondern die zur schwachen Relation $R_{N1}$ korrespondierende starke Ordnung.
Eine schwache und eine starke Ordnung korrespondieren genau dann, wenn sie beide auf der Menge A definiert sind und die schwache Ordnung eine Vereinigung aus der starken Ordnung und allen Paaren $(a,a)$ mit $a\in A$ ist.
Eine geordnete Menge $(M,R)$ ist ein Paar aus einer Menge $M$ und einer Ordnung $R$ von $M$. Es gilt dann: Die Relation $R \subseteq M \times M$ ist eine (starke oder schwache) Ordnungsrelation auf $M$, also eine Relation, die die oben genannten Eigenschaften erfüllt.
Hier ein Beispiel aus dem Foliensatz:
$T=(\{\{1,2,3,4,5\},\{1,2,3,5\},\{1,3,4\},\{2,4,5\},\{1,2,3\},\{1,3\},\{2,4\},\{1,5\},\{1\},\{3\},\{4\},\{5\},\{\}\},\subseteq)$
Es gilt dann zum Beispiel: $\{1,3,4\}\subseteq \{1,2,3,4,5\}$ usw.
Um all diese Beziehungen darzustellen, verwenden wir Hassediagramme. Um Hassediagramme zeichnen zu können, müssen wir verstehen, was die (unmittelbaren) Vorgänger und Nachfolger in einer Ordnungsrelation sind.
Im Video wird das Erstellens eines Hassediagramms am Beispiel der bereits erwähnten geordneten Menge $T=(\{\{1,2,3,4,5\},\{1,2,3,5\},\{1,3,4\},\{2,4,5\},\{1,2,3\},\{1,3\},\{2,4\},\{1,5\},\{1\},\{3\},\{4\},\{5\},\{\}\},\subseteq)$ gezeigt.
Um diese Definition zu verstehen, macht es Sinn, sich an totale und partielle Funktionen zu erinnern. Eine Funktion ist total, wenn sie allen Elementen des Definitionsbereichs etwas zuordnet.
Bei Ordnungen ist die Definition nur ein wenig anders. Eine Ordnungsrelation $R$ auf eine Menge $M$ ist nämlich dann total, wenn sie alle Elemente von $M$ zueinander in Relation setzt:
Diese Eigenschaft nennt man konnex oder linear: Eine Relation $R: M \times M$ ist konnex genau dann, wenn für alle $x,y$ mit $x,y \in M$ gilt: $\langle x,y \rangle \in M$ oder $\langle y,x \rangle \in M$
Ordnungen, die die Eigenschaft "konnex" erfüllen, nennt man total oder linear. Anders gesagt: Bei totalen Relationen gibt es keine zwei verschiedenen Elemente $x,y$, sodass $x$ nicht in Relation zu $y$ steht. Um sich zu merken, warum so eine Ordnung "lineare Ordnung" genannt wird, sehe man sich das Hassediagramm zu so einer Ordnung an. Das ist nämlich, salopp gesagt, eine Linie. Warum das so ist, erkläre ich im Video. Ordnungen, die nicht total/konnex/linear sind, nennt man partielle Ordnungen oder posets (partially ordered sets).
Bei einer Ordnungsrelation können wir minimale und maximale Elemente, Minima und Maxima bestimmen. Besonders sollte man hier auf den Unterschied zwischen minimalem Element und Minimum bzw. maximalem Element und Maximum achten!
Gegeben sei eine beliebige Ordnungsrelation Relation $R\subseteq A \times A$.
Der wichtigste Unterschied zwischen minimalen/maximalen Elementen und Minimum/Maximum ist der, dass es nur höchstens 1 Minimum und 1 Maximum geben kann, aber mehrere minimale und maximale Elemente. Das wird an einem Hassediagramm deutlich. Hier ein Beispiel aus der Hausaufgabe. Die dargestellte Relation ist $\subseteq$ auf den abgebildeten Elementen. Am besten erst versuchen, die Definitionen oben anzuwenden, und dann erst weiterlesen!
Die minimalen Elemente sind alle Elemente ohne Vorgänger, in diesem Fall nur $\emptyset$. Das ist zugleich das Minimum, da $\emptyset$ auch Vorgänger aller anderen Elemente ist.
Die maximalen Elemente sind alle Elemente ohne Nachfolger: $\{\epsilon\}, \{a,b,c,d,e\},\{b,d,e,f\}$. Da es mehrere Elemente ohne Nachfolger gibt, gibt es auch kein Element, das Nachfolger aller anderen Elemente ist. Es gibt also kein Maximum. Diesen Zusammenhang sollte man sich merken: Das Minimum/Maximum ist immer genau das einzige minimale/maximale Element.
In einer Ordnungsrelation R heißen zwei Elemente $a,b$ vergleichbar, wenn gilt: $R(a,b)$ oder $R(b,a)$. Dementsprechend sind zwei Elemente von $R$ unvergleichbar, wenn sie nicht in Relation zueinander stehen.
Beispiel aus dem Hassediagramm zur Hausaufgabe (oben): $\{a\}$ und $\{a,b,c,d,e\}$ sind vergleichbar, da $\{a\}\subseteq\{a,b,c,d,e\}$. $\{a\}$ und $\{b,d,e\}$ sind unvergleichbar, da $\{a\}\nsubseteq \{b,d,e\}$.
Eine Kette ist eine Menge von Elementen der Relation, die alle miteinander vergleichbar sind. Formal: Gegeben eine geordnete Menge $(M,R)$. Eine Teilmenge $K \subseteq M$ ist eine Kette gdw. für alle verschiedenen Elemente $a,b \in K$ gilt: $R(a,b)$ oder $R(b,a)$.
Eine Antikette ist eine Menge von Elementen der Relation R, die alle miteinander unvergleichbar sind. Formal: Eine Teilmenge $K \subseteq M$ ist eine Antikette gdw. für alle verschiedenen Elemente $a,b \in K$ gilt: Weder $R(a,b)$ noch $R(b,a)$.
Die Höhe einer endlichen geordneten Menge $(M,R)$ ist die Länge der längsten Kette in $(M,R)$. Die Breite einer endlichen geordneten Menge $(M,R)$ ist die Länge der längsten Antikette in $(M,R)$.
Höhe und Breite für Dummies: Man nehme ein gut gezeichnetes Hassediagramm, bei dem es nur Kanten gibt zwischen Elementen, die über- und untereinander stehen. Die Höhe der geordneten Menge ist die Anzahl der Knoten im längsten Weg von unten nach oben im Hassediagramm. Die Breite der geordneten Menge ist die größte Zahl an Knoten, die nebeneinander stehen.
Dabei handelt es sich um drei besondere Teilmengen der geordneten Mengen.
Für die Definitionen ist immer gegeben eine geordnete Menge $(M,\ltimes)$. Die Beispiele beziehen sich auf die geordnete Menge $(POT(\{Fleisch,Käse,Salat\}),\subset)$. Das zugehörige Hassediagramm:
$\dots$ wird mit eckigen Klammern notiert:
$[a,b] := \{x \in M | a \ltimes x \ltimes b\}$
$[a,b]$ ist also die Menge aller Elemente $x \in M$, die sowohl in der Ordnungsrelation zu $a$ als auch zu $b$ stehen. Anders formuliert: $[a,b]$ ist die Menge aller Elemente, die in einer Kette von $a$ nach $b$ sind.
Beispiel: $[\emptyset, \{Fleisch, Salat\}]=\{\emptyset, \{Fleisch\},\{Salat\},\{Fleisch,Salat\}\}$. Die Ketten von $\emptyset$ nach $\{Fleisch, Salat\}$ sind
und $K_1 \cup K_2=[\emptyset, \{Fleisch, Salat\}]$
Das Hauptideal $(b]:=\{x \in M | x \ltimes b\}$ bezeichnet einfach die Menge der Vorgänger von $b$ und $b$ selbst.
Beispiel: $(\{Käse\}]=\{\emptyset, \{Käse\}\}$
Immer diese Zusammenhänge: Das Intervall $[a,b]$ ist gleich dem Ideal $(b]$ genau dann, wenn $a$ das Minimum ist. Oben haben wir zum Beispiel $[\emptyset, \{Fleisch, Salat\}]=(\{Fleisch, Salat\}]$ bestimmt
Der Hauptfilter $[a):=\{x \in M | a \ltimes x\}$ bezeichnet die Menge der Nachfolger von $a$ und $a$ selbst.
Beispiel: $[\{Fleisch,Käse\})=\{\{Fleisch,Käse\},\{Fleisch,Käse,Salat\}\}$
Auch hier gilt, ähnlich wie beim Hauptideal: $[a,b]=[a]$, wenn $b$ das Maximum ist. Am besten selbst an einem Beispiel vor Augen führen :)
Nebenbemerkung: Intervalle kennt man vielleicht schon aus der Schule. Hier seien 2 Formen von Intervallen erwähnt: Geschlossene und offene Intervalle. Solche wie die Intervalle oben nennt man geschlossene Intervalle. Beispiel: Bezogen auf die reellen Zahlen $\mathbb{R}$ ist $[0,1] =\{x \in \mathbb{R} | 0 \leq x \leq 1\} $. Die Menge wird von $0$ und $1$ abgeschlossen, und $0$ und $1$ sind Elemente der Menge. Im Gegensatz dazu ist das offene Intervall $]0,1[=\{x \in \mathbb{R} | 0 < x < 1\}$. Das Intervall ist an den Seiten offen, $0$ und $1$ sind nicht Elemente der Menge. Je nach Notationsvorlieben sieht man auch $]0,1[=(0,1)$. Frage: Was ist jetzt wohl $[0,1[$?
Quasiordnungen erfüllen also, im Gegensatz zu schwachen Ordnungen, nicht die Eigenschaft der Antisymmetrie. In einer Quasiordnung $(M,\unlhd)$ kann es also zwei Elemente $x,y$ geben, sodass $x\unlhd y$ und $y \unlhd x$, aber $x \neq y$. Merke: Alle schwachen Ordnungen sind Quasiordnungen, da alle schwachen Ordnungen (unter anderem) reflexiv und transitiv sind.
Wir hatten bereits häufiger die Relation $\leq$ auf $\mathbb{N}$ betrachtet. Betrachten wir nun $\leq_{abr}$ auf $\mathbb{R}$. Diese Relation nimmt zwei reelle Zahlen, rundet sie zur nächstkleineren ganzen Zahl ab und vergleicht sie dann. Beispiel: $3.59\leq_{abr}7,98$, da $3\leq7$. Oder $\pi \leq_{abr} 3.010101$, da $3 \leq 3$. Es gilt aber auch $3.010101 \leq_{abr} \pi$, da $3 \leq 3$. Da also gilt $\pi \leq_{abr} 3.010101$ und $3.010101 \leq_{abr} \pi$, aber $\pi \neq 3.010101$, ist diese Relation nicht antisymmetrisch.