{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## Begriffe, die in diesem Skript erklärt werden\n", "\n", "- stark und schwach\n", " - korrespondierend\n", "- geordnete Mengen\n", "- (unmittelbarer) Vorgänger/Nachfolger\n", "- Hassediagramme + Beispiel\n", "- totale/partielle Ordnung\n", "- minimal, maximal\n", "- Vergleichbarkeit/Kette/Antikette/Höhe/Breite\n", "- Intervall/Ideal/Filter\n", "- Quasiordnung" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Ordnungen" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Eine weitere besondere Klasse von Relationen sind die *Ordnungsrelationen*. \n", "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." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## zwei Arten von Ordnungen: stark und schwach" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Eine Ordnung $R$ einer Menge $A$ ist eine binäre Relation $R\\subseteq A \\times A$.\n", "Man unterscheidet zwischen starken und schwachen Ordnungen. Die Eigenschaften Transitivität, Reflexivität und (Anti-)Symmetrie wurden in [diesem Skript](./02_Relationen.ipynb#Eigenschaften-bin%C3%A4rer-Relationen) besprochen.\n", "\n", "Schwache Ordnungen sind binäre Relationen, die \n", "- transitiv,\n", "- reflexiv und\n", "- antisymmetrisch\n", "\n", "sind. \n", "Starke (manchmal auch strikte) Odnungen sind Relationen, die\n", "- transitiv,\n", "- irreflexiv und\n", "- asymmetrisch\n", "\n", "sind." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Beispiel\n", "\n", "Gegeben die Relation $R_{N1} \\subseteq \\mathbb{N} \\times \\mathbb{N}$.\n", "$R_{N1}=\\{(x,y)| x \\leq y\\}$. \n", "\n", "$R_{N1}$ enthält also z.B. die Tupel $(1,1),(1,2),(1,3),\\dots,(2,2),(2,3),\\dots$.\n", "Damit ist $R_{N1}$ eine schwache Ordnung, denn die Relation ist\n", "- transitiv: da z.B. $2\\le 3$ und $3\\le 19$, gilt auch $2\\le 19$\n", "- reflexiv: $(n,n) \\in R_{N1}$ für alle $n \\in \\mathbb{N}$\n", "- antisymmetrisch: wenn $(a,b) \\in R_{N1}$ und $(b,a) \\in R_{N1}$, ist niemals $a\\neq b$\n", "\n", "\n", "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:\n", "\n", "$R_{N2}=R_{N1}\\setminus \\{(n,n) \\in R_{N1} | n \\in \\mathbb{N}\\}$\n", "\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" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Video zum Zeichnen von Hasse-Diagrammen" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## totale und partielle Ordnungen" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Um diese Definition zu verstehen, macht es Sinn, sich an [totale und partielle Funktionen](02_Funktionen.ipynb#Video-zum-Funktionsbegriff-und-zu-partiellen-und-totalen-Funktionen) zu erinnern. Eine Funktion ist total, wenn sie allen Elementen des Definitionsbereichs etwas zuordnet. \n", "\n", "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:\n", "\n", "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$\n", "\n", "Ordnungen, die die Eigenschaft \"konnex\" erfüllen, nennt man *total* oder *linear*.\n", "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.\n", "Ordnungen, die nicht total/konnex/linear sind, nennt man *partielle* Ordnungen oder *posets* (**p**artially **o**rdered **sets**)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## minimale und maximale Elemente" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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! \n", "\n", "Gegeben sei eine beliebige Ordnungsrelation Relation $R\\subseteq A \\times A$. \n", "\n", "- Ein Element $a \\in A$ ist *minimal*, wenn es kein $b \\in A$ mit $a \\neq B$ gibt und $R(b,a)$. Minimale Elemente sind also alle Elemente, die keinen Vorgänger haben. \n", "- Ein Element $a \\in A$ ist *maximal*, wenn es kein $b \\in A$ mit $a \\neq B$ gibt und $R(a,b)$. Maximale Elemente sind also alle Elemente, die keinen Nachfolger haben. \n", "- Ein Element $a \\in A$ ist das *Minimum* von $A$, wenn für alle $b \\neq a$ mit $b \\in A$ gilt: $R(a,b)$. Anders gesagt: $a$ ist das Minimum von $A$, wenn es Vorgänger aller anderen Elemente in $A$ ist.\n", "- Ein Element $a \\in A$ ist das *Maximum* von $A$, wenn für alle $b \\neq a$ mit $b \\in A$ gilt: $R(b,a)$. Anders gesagt: $a$ ist das Maximum von $A$, wenn es Nachfolger aller anderen Elemente in $A$ ist. \n", "\n", "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!\n", "\n", "![Hassediagramm](pic/04_Hassediagramm_minmax.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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.\n", "\n", "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: \n", "**Das Minimum/Maximum ist immer genau das einzige minimale/maximale Element.**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Vergleichbarkeit/Kette/Antikette/Höhe/Breite" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Vergleichbarkeit\n", "\n", "In einer Ordnungsrelation R heißen zwei Elemente $a,b$ *vergleichbar*, wenn gilt: $R(a,b)$ oder $R(b,a)$.\n", "Dementsprechend sind zwei Elemente von $R$ *unvergleichbar*, wenn sie nicht in Relation zueinander stehen. \n", "\n", "Beispiel aus dem Hassediagramm zur Hausaufgabe (oben): $\\{a\\}$ und $\\{a,b,c,d,e\\}$ sind vergleichbar, da $\\{a\\}\\subseteq\\{a,b,c,d,e\\}$.\n", "$\\{a\\}$ und $\\{b,d,e\\}$ sind unvergleichbar, da $\\{a\\}\\nsubseteq \\{b,d,e\\}$.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Kette und Antikette\n", "\n", "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)$. \n", "\n", "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)$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Höhe und Breite" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Die *Höhe* einer endlichen geordneten Menge $(M,R)$ ist die Länge der längsten Kette in $(M,R)$. \n", "Die *Breite* einer endlichen geordneten Menge $(M,R)$ ist die Länge der längsten Antikette in $(M,R)$.\n", "\n", "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.\n", "Die Höhe der geordneten Menge ist die Anzahl der Knoten im längsten Weg von unten nach oben im Hassediagramm. \n", "Die Breite der geordneten Menge ist die größte Zahl an Knoten, die nebeneinander stehen." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Video Kette und Antikette" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Intervall / Ideal / Filter\n", "\n", "Dabei handelt es sich um drei besondere Teilmengen der geordneten Mengen. \n", "\n", "Für die Definitionen ist immer gegeben eine geordnete Menge $(M,\\ltimes)$. \n", "Die Beispiele beziehen sich auf die geordnete Menge $(POT(\\{Fleisch,Käse,Salat\\}),\\subset)$. Das zugehörige Hassediagramm:\n", "\n", "![FleischKäseSalat](pic/04_FleischKaeseSalat.png)\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Das Intervall\n", "\n", "$\\dots$ wird mit eckigen Klammern notiert: \n", "\n", "$[a,b] := \\{x \\in M | a \\ltimes x \\ltimes b\\}$ \n", "\n", "\n", "$[a,b]$ ist also die Menge aller Elemente $x \\in M$, die sowohl in der Ordnungsrelation zu $a$ als auch zu $b$ stehen.\n", "Anders formuliert: $[a,b]$ ist die Menge aller Elemente, die in einer Kette von $a$ nach $b$ sind.\n", "\n", "Beispiel: $[\\emptyset, \\{Fleisch, Salat\\}]=\\{\\emptyset, \\{Fleisch\\},\\{Salat\\},\\{Fleisch,Salat\\}\\}$. Die Ketten von $\\emptyset$ nach $\\{Fleisch, Salat\\}$ sind \n", "\n", "- $K_1 = \\{\\emptyset, \\{Fleisch\\}, \\{Fleisch, Salat\\}\\}$\n", "- $K_2 = \\{\\emptyset, \\{Salat\\}, \\{Fleisch, Salat\\}\\}$ \n", "\n", "und $K_1 \\cup K_2=[\\emptyset, \\{Fleisch, Salat\\}]$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Das Hauptideal\n", "\n", "Das Hauptideal $(b]:=\\{x \\in M | x \\ltimes b\\}$ bezeichnet einfach die Menge der Vorgänger von $b$ und $b$ selbst.\n", "\n", "Beispiel: $(\\{Käse\\}]=\\{\\emptyset, \\{Käse\\}\\}$\n", "\n", "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" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Der Hauptfilter\n", "\n", "Der Hauptfilter $[a):=\\{x \\in M | a \\ltimes x\\}$ bezeichnet die Menge der Nachfolger von $a$ und $a$ selbst.\n", "\n", "Beispiel: $[\\{Fleisch,Käse\\})=\\{\\{Fleisch,Käse\\},\\{Fleisch,Käse,Salat\\}\\}$\n", "\n", "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 :)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "**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. \n", "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.\n", "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[$?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Quasiordnung" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![Folie 28](Folien/04/slide-28.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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. \n", "\n", "### Ein weiteres Beispiel\n", "\n", "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.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Zusammenfassende Folien" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![Folie 29](Folien/04/slide-29.png)\n", "![Folie 30](Folien/04/slide-30.png)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.4" } }, "nbformat": 4, "nbformat_minor": 2 }