Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 7

Dies ist Dr. Ines Eisenbeis. Sie ist für die wissenschaftliche Begleitung des Projektes Vorlesungshund verantwortlich. Ihre Arbeitshypothesen sind: 1) Studierende gehen lieber zur Vorlesung, 2) Außenseiter werden aus ihrer Isolation geholt, 3) Auffälligkeiten reduzieren sich, 4) Positive Sozialkontakte werden gefördert, 5) Profs werden mehr beachtet.

Ordnungsrelationen

Eine reflexive, transitive und antisymmetrische Relation nennt man eine Ordnung, wofür man häufig ein Symbol wie ${}\geq ,\leq ,\preccurlyeq ,\subseteq$ verwendet. Wir geben nochmal die ausführliche Definition.

Definition

Eine Relation ${}\preccurlyeq$ auf einer Menge ${}I$ heißt Ordnungsrelation oder Ordnung, wenn folgende drei Bedingungen erfüllt sind.

1. Es ist ${}i\preccurlyeq i$ für alle ${}i\in I$.
2. Aus ${}i\preccurlyeq j$ und ${}j\preccurlyeq k$ folgt stets ${}i\preccurlyeq k$.
3. Aus ${}i\preccurlyeq j$ und ${}j\preccurlyeq i$ folgt ${}i=j$.

Eine Menge mit einer fixierten Ordnung darauf heißt geordnete Menge. Zu jeder geordneten Menge ${}(M,\preccurlyeq )$ und jede Teilmenge ${}N\subseteq M$ ist auch ${}N$ eine geordnete Menge, indem man direkt die Ordnungsbeziehung von ${}M$ übernimmt. Man spricht von der induzierten Ordnung auf ${}N$.

Definition

Eine Ordnungsrelation ${}\preccurlyeq$ auf einer Menge ${}I$ heißt lineare Ordnung (oder totale Ordnung), wenn zu je zwei Elementen ${}x,y\in I$ die Beziehung ${}x\preccurlyeq y$ oder ${}y\preccurlyeq x$ gilt.

Man sagt auch, dass bei einer linearen Ordnung je zwei Elementen vergleichbar sind.

Beispiel

Auf den natürlichen Zahlen besteht zwischen ${}n$ und ${}k$ die Ordnungsrelation ${}n\geq k$, also ${}n$ ist größergleich ${}k$, wenn man von ${}k$ aus durch endlichfaches Nachfolgernehmen zu ${}n$ gelangt, wobei nullfaches Nachfolgernehmen die Zahl selbst ergibt. Dies ist eine totale Ordnung. Mit der Addition kann man dies folgendermaßen ausdrücken: Es ist ${}n\geq k$ genau dann, wenn es eine natürliche Zahl ${}m$ mit ${}n=k+m$ gibt.

Bemerkung  

Eine totale Ordnung auf einer endlichen Menge ist durch ein Angangselement (kleinstes Element) und dadurch gegeben, dass jedem Element (außer dem größten Element) das nächstkleinste Element zugeordnet wird. In der Skizze wird nur diese Zuordnung dargestellt, die gesamte Ordnung ergibt sich, wenn man sich Selbstpfeile und transitive Pfeile dazudenkt.

Auf einer endlichen Menge ${}M$ mit ${}n$ Elementen sind die totalen Ordnungen einfach zu überschauen. Eine totale Ordnung auf ${}M$ ist das gleiche wie eine bijektive Abbildung ${}\varphi \colon {\{1,\ldots ,n\}}\rightarrow M$, also eine Nummerierung von ${}M$. Eine solche Nummerierung legt über ${}\varphi (i)\geq \varphi (j)$, falls ${}i\geq j$, eine totale Ordnung fest, und eine totale Ordnung legt eine Nummerierung fest, indem ${}1$ auf das kleinste Element von ${}M$ abgebildet wird, ${}2$ auf das zweitkleinste Element u.s.w. Insbesondere gibt es wegen Satz 2.4 ${}n!$ totale Ordnungen auf ${}M$. Es ist ziemlich schwierig, sich eine systematische Übersicht über alle (auch die nicht totalen) Ordnungen in einer endlichen Menge zu verschaffen.

Beispiel

Es sei ${}A$ ein Alphabet und ${}W$ die Menge der Wörter über diesem Alphabet, also die Menge alle endlichen Ketten über ${}A$ oder eine Teilmenge davon, etwa die Menge der real existierenden Wörter. Auf ${}A$ sei eine totale Ordnung gegeben. Dann definiert man auf ${}W$ die sogenannte lexikographische Ordnung, indem für Wörter ${}w,z$ die Beziehung

${}w\preccurlyeq _{\text{lex}}z\,$

(${}w$ kommt im Lexikon vor ${}z$) genau dann gilt, wenn sie gleich sind oder wenn an der ersten Stelle von vorne gelesen, wo sich ${}w$ und ${}z$ unterscheiden, der Buchstabe von ${}w$ an dieser Stelle im Alphabet vor dem Buchstaben von ${}z$ an dieser Stelle kommt, was den Fall einschließen mag, dass an dieser Stelle ${}w$ keinen Buchstaben mehr hat („Vers“ kommt vor „Verstand“). Die lexikographische Ordnung ist eine totale Ordnung.

Beispiel

Auf jeder Menge ${}M$ ist die identische Relation, also die Relation, bei der jedes Element nur mit sich selbst in Relation steht, eine Ordnungsrelation.

Definition

Ein kommutativer Ring heißt angeordnet, wenn es eine totale Ordnung ${}\geq$ auf ${}R$ gibt, die die beiden Eigenschaften

1. Aus ${}a\geq b$ folgt ${}a+c\geq b+c$ für beliebige ${}a,b,c\in R$,
2. Aus ${}a\geq 0$ und ${}b\geq 0$ folgt ${}ab\geq 0$ für beliebige ${}a,b\in R$,

erfüllt.

Ein angeordneter Ring ist also nicht nur ein Ring, auf dem es zusätzlich noch eine totale Ordnung gibt, sondern die Ordnung muss auch mit den algebraischen Verknüpfungen in der beschriebenen Weise verbunden sein. Ein angeordneter Ring, der ein Körper ist, heißt angeordneter Körper. Die ganzen Zahlen ${}\mathbb {Z}$, die rationalen Zahlen ${}\mathbb {Q}$ und die reellen Zahlen ${}\mathbb {R}$ sind angeordnete Ringe bzw. Körper. Der Körper der komplexen Zahlen ${}{\mathbb {C} }$ ist nicht angeordnet (und lässt sich auch nicht anordnen).

Definition

Man sagt, dass die natürliche Zahl ${}a$ die natürliche Zahl ${}b$ teilt (oder dass ${}b$ von ${}a$ geteilt wird, oder dass ${}b$ ein Vielfaches von ${}a$ ist), wenn es eine natürliche Zahl ${}c$ derart gibt, dass ${}b=c\cdot a$ ist. Man schreibt dafür auch ${}a{|}b$.

Achtung! Die Teilbarkeitsbeziehung in ${}\mathbb {N}$ sollte man allein innerhalb der natürlichen Zahlen behandeln. Man vermeide Formulierungen wie, dass ${}a$ die Zahl ${}b$ teilt, wenn bei der Division von ${}b$ durch ${}a$ kein Rest bleibt oder dass der Bruch ${}{\frac {b}{a}}$ ganzzahlig ist. Solche Charakterisierungen mit deutlich komplizierteren Strukturen verdunkeln den einfachen Sachverhalt.

Lemma

In ${}\mathbb {N}$ gelten folgende Teilbarkeitsbeziehungen.

1. Für jede natürliche Zahl ${}a$ gilt ${}1\,{|}\,a$ und ${}a\,{|}\,a$.
2. Für jede natürliche Zahl ${}a$ gilt ${}a\,{|}\,0$.
3. Gilt ${}a\,{|}\,b$ und ${}b\,{|}\,c$, so gilt auch ${}a\,{|}\,c$.
4. Gilt ${}a\,{|}\,b$ und ${}c\,{|}\,d$, so gilt auch ${}ac\,{|}\,bd$.
5. Gilt ${}a\,{|}\,b$, so gilt auch ${}ac\,{|}\,bc$ für jede natürliche Zahl ${}c$.
6. Gilt ${}a\,{|}\,b$ und ${}a\,{|}\,c$, so gilt auch ${}a\,{|}\,{\left(rb+sc\right)}$ für beliebige natürliche Zahlen ${}r,s$.

Beweis

Siehe Aufgabe 7.18.

$\Box$

Beispiel

Wir betrachten die positiven natürlichen Zahlen ${}\mathbb {N} _{+}$ zusammen mit der Teilbarkeitsbeziehung. Dies ergibt eine Ordnung auf ${}\mathbb {N} _{+}$. Die Teilbarkeitsrelation ist in der Tat reflexiv, da stets ${}n{|}n$ ist, wie ${}m=1$ zeigt. Die Transitivität wurde in Lemma 7.9  (3) gezeigt. Die Antisymmetrie folgt so: Aus ${}n=ak$ und ${}k=bn$ folgt ${}n=(ab)n$. Da wir uns auf positive natürliche Zahlen beschränken, folgt mit der Kürzungsregel ${}ab=1$ und daraus wegen ${}a,b\leq ab$ auch ${}a=b=1$. Also ist ${}k=n$. Einfache Beispiele wie $2$ und $3$ zeigen, dass hier keine totale Ordnung vorliegt, da weder ${}2$ von ${}3$ noch umgekehrt geteilt wird.

Beispiel

Es sei ${}M$ eine beliebige Menge und ${}R={\mathfrak {P}}\,(M)$ die Potenzmenge davon. Dann sind die Elemente aus ${}R={\mathfrak {P}}\,(M)$ - also die Teilmengen von ${}M$ - durch die Inklusionsbeziehung ${}\subseteq$ geordnet. Die Reflexivität bedeutet einfach, dass eine jede Menge in sich selbst enthalten ist und die Transitivität bedeutet, dass aus ${}T_{1}\subseteq T_{2}$ und ${}T_{2}\subseteq T_{3}$ die Inklusion ${}T_{1}\subseteq T_{3}$ folgt. Die Antisymmetrie ist dabei ein wichtiges Beweisprinzip für die Gleichheit von Mengen: Zwei Mengen ${}T_{1},T_{2}$ sind genau dann gleich, wenn ${}T_{1}\subseteq T_{2}$ und umgekehrt ${}T_{2}\subseteq T_{1}$ gilt.

Beispiel

Es sei ${}X$ eine Menge (beispielsweise ein reelles Intervall, oder ein topologischer Raum), so ist die Menge der (stetigen) Funktionen ${}f\colon X\rightarrow \mathbb {R}$ geordnet, indem man ${}f\geq g$ dadurch definiert, dass ${}f(x)\geq g(x)$ für jeden Punkt ${}x\in X$ sein muss. Dies ist offensichtlich keine totale Ordnung.

Definition

Es sei ${}(M_{i},\leq _{i})$, ${}i\in I$, eine Familie von geordneten Mengen. Dann nennt man die auf der Produktmenge ${}M=\prod _{i\in I}M_{i}$ durch

${}(x_{i})_{i\in I}\leq (y_{i})_{i\in I}\,,$

falls

${}x_{i}\leq _{i}y_{i}\,$

für alle ${}i\in I$ gilt, die Produktordnung.

In Beispiel 7.12 werden die reellen Zahlen so oft genommen, wie es ${}X$ vorgibt. Dort liegt also eine Produktordnung vor,

Ordnungstreue Abbildungen

Definition

Es seien ${}(M_{1},\leq _{1})$ und ${}(M_{2},\leq _{2})$ zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung

$F\colon M_{1}\longrightarrow M_{2},\,x\longmapsto F(x),$

heißt ordnungstreu (oder monoton), wenn für alle ${}x,x'\in M_{1}$ mit ${}x\leq _{1}x'$ stets auch ${}F(x)\leq _{2}F(x')$ gilt.

Monotone Abbildungen zwischen ${}\mathbb {R}$ und ${}\mathbb {R}$ sind aus den Anfängervorlesungen bekannt. Ordnungstreue Abbildungen sind einfach die relationstreuen Abbildungen, wenn die beteiligten Relationen Ordnungen sind.

Definition

Es seien ${}(M_{1},\leq _{1})$ und ${}(M_{2},\leq _{2})$ zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung

$F\colon M_{1}\longrightarrow M_{2},\,x\longmapsto F(x),$

heißt ordnungsvolltreu, wenn für alle ${}x,x'\in M_{1}$ genau dann ${}x\leq _{1}x'$ gilt, wenn ${}F(x)\leq _{2}F(x')$ gilt.

Wenn ${}M_{1}$ total geordnet und die Abbildung injektiv ist, so muss man nicht zwischen ordnungstreu und ordnungsvolltreu unterscheiden, sonst aber schon. Zu eine Teilmenge einer geordneten Menge mit der induzierten Ordnung ist die Inklusion ordnungsvolltreu. Wenn man dagegen eine Teilmenge mit einer schwächeren Ordnung, beispielsweise der identischen Ordnung versieht, so ist die Inklusion zwar ordnungstreu, aber nicht ordnungsvolltreu. Eine ordnungsvolltreue Abbildung ist stets injektiv.

Lemma

Es sei ${}(M,\leq )$ eine geordnete Menge und ${}{\mathfrak {P}}\,(M)$ die Potenzmenge von ${}M$.

Dann ist die Abbildung

$M\longrightarrow {\mathfrak {P}}\,(M),\,x\longmapsto {\left\{y\in M\mid y\leq x\right\}},$

ordnungsvolltreu und injektiv ist, wobei die Potenzmenge mit der Inklusion versehen ist.

Beweis

Siehe Aufgabe 7.28.

$\Box$

Diese Aussage besagt, dass die Inklusionsbeziehung zwischen Teilmengen in einem gewissen Sinne die universelle Ordnungsbeziehung ist, da sich jede geordnete Menge als Unterobjekt davon realisieren lässt. Beispielsweise gilt für reelle Zahlen die Beziehung ${}t\leq s$ genau dann, wenn

${}[-\infty ,t]\subseteq [-\infty ,s]\,$

gilt. Allerdings muss man dafür auch einen hohen Preis bezahlen, nämlich, dass man einfache Elemente mit großen Mengen identifizieren und dann unnötigen Ballast mitschleppen muss, und dass man total geordnete Mengen in nicht total geordnete Mengen einbettet. Dennoch sind solche und ähnliche universelle Überlegungen für theoretische Überlegungen wichtig, siehe Aufgabe 4.13, oder das Konzept der durch eine ganze Zahl erzeugten Untergruppe (siehe die nächste Vorlesung), oder Satz 9.22, oder die Definition einer Äquivalenzklasse für ähnliche Konstruktionen.

Wir erwähnen noch die folgende Variante einer ordnungstreuen Abbildung.

Definition

Es seien ${}(M_{1},\leq _{1})$ und ${}(M_{2},\leq _{2})$ zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung

$F\colon M_{1}\longrightarrow M_{2},\,x\longmapsto F(x),$

heißt monoton fallend, wenn für alle ${}x,x'\in M_{1}$ mit ${}x\leq _{1}x'$ stets ${}F(x)\geq _{2}F(x')$ gilt.

Statt monoton fallend sagt man manchmal auch antimonoton. Dies ist nicht ein wirklich eigenständiger Begriff, da man ja eine Ordnungsrelation wie jede Relation auf einer Menge umkehren kann, also die Rolle der beiden Elemente vertauschen kann.

Extremaleigenschaften

Definition

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge. Ein Element ${}x\in I$ heißt größtes Element von ${}I$, wenn ${}y\preccurlyeq x$ für jedes ${}y\in I$ gilt.

Definition

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge. Ein Element ${}x\in I$ heißt kleinstes Element von ${}I$, wenn ${}x\preccurlyeq y$ für jedes ${}y\in I$ gilt.

Definition

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge. Ein Element ${}x\in I$ heißt maximal (in ${}I$) oder ein maximales Element (von ${}I$), wenn es kein Element ${}y\in I$, ${}y\neq x$, mit ${}x\preccurlyeq y$ gibt.

Definition

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge. Ein Element ${}x\in I$ heißt minimal (in ${}I$) oder ein minimales Element (von ${}I$), wenn es kein Element ${}y\in I$, ${}y\neq x$, mit ${}y\preccurlyeq x$ gibt.

Bei einer total geordneten Menge fallen die Konzepte größtes Element und maximales Element zusammen, im Allgemeinen muss man sie aber sorgfätig unterscheiden. Ein größtes Element ist, wenn es existiert, eindeutig bestimmt und dann auch das einzige maximale Element.

In einer endlichen geordneten Menge gibt es stets maximale und minimale Elemente.

Das abgeschlossene Intervall ${}[0,1]$ besitzt die ${}0$ als kleinstes und die ${}1$ als größtes Element, das offene Intervall ${}]0,1[$ besitzt weder minimale noch maximale Elemente.

In der Menge der natürlichen Zahlen mit der durch die Teilbarkeitrelation gegebenen Ordnung ist ${}1$ das kleinste Element, da die ${}1$ jede Zahl teilt, und die ${}0$ ist das größte Element, da die ${}0$ von jeder Zahl geteilt wird. Auf ${}\mathbb {N} _{\geq 2}$ mit der Teilbarkeitsrelation sind genau die Primzahlen die minimalen Elemente, es gibt keine maximalen Elemente. Bei einer Potenzmenge mit der durch die Inkusion gegebenen Ordnung ist die leere Menge das kleinste Element und die Gesamtmenge das größte Element. Wenn man die leere Menge aus der Potenzmenge herausnimmt, so sind die einelementigen Teilmengen die minimalen Elemente (diese nennt man auch Atome).

Definition

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge und ${}J\subseteq I$ eine Teilmenge. Ein Element ${}s\in I$ heißt obere Schranke für ${}J$, wenn ${}y\preccurlyeq s$ für jedes ${}y\in J$ gilt.

Definition

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge und ${}J\subseteq I$ eine Teilmenge. Ein Element ${}s\in I$ heißt untere Schranke für ${}J$, wenn ${}s\preccurlyeq x$ für jedes ${}x\in J$ gilt.

Definition

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge und ${}J\subseteq I$ eine Teilmenge. Ein Element ${}s\in I$ heißt Supremum von ${}J$, wenn ${}s$ die kleinste obere Schranke von ${}J$ ist.

Definition

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge und ${}J\subseteq I$ eine Teilmenge. Ein Element ${}s\in I$ heißt Infimum von ${}J$, wenn ${}s$ die größte untere Schranke von ${}J$ ist.

Für das offene Intervall ${}]0,1[$ ist jede reelle Zahl ${}s\geq 1$ eine obere Schranke und ${}1$ ist das Supremum.

Wir besprechen einige weitere Teilbarkeitsbegriffe und erfassen sie mit unserem ordnungstheoretischen Vokabular.

Definition

Es seien ${}a_{1},\ldots ,a_{k}$ natürliche Zahlen. Dann heißt eine natürliche Zahl ${}t$ gemeinsamer Teiler der ${}a_{1},\ldots ,a_{k}$, wenn ${}t$ jedes ${}a_{i}$ teilt (${}i=1,\ldots ,k$).

Eine natürliche Zahl ${}g$ heißt größter gemeinsamer Teiler der ${}a_{1},\ldots ,a_{k}$, wenn ${}g$ ein gemeinsamer Teiler ist und wenn jeder gemeinsame Teiler ${}t$ dieses ${}g$ teilt.

Die Elemente ${}a_{1},\ldots ,a_{k}$ heißen teilerfremd, wenn ${}1$ ihr größter gemeinsamer Teiler ist.

Ein gemeinsamer Teiler ist eine untere Schranke von ${}\{a_{1},\ldots ,a_{k}\}$ bezüglich der Teilbarkeitsrelation und der größte gemeinsame Teiler ist das Infimum davon.

Definition

Zu einer Menge von natürlichen Zahlen

$a_{1},\ldots ,a_{n}$

heißt eine natürliche Zahl ${}b$ ein gemeinsames Vielfaches, wenn ${}b$ ein Vielfaches von jedem ${}a_{i}$ ist, also von jedem ${}a_{i}$ geteilt wird.

Die Zahl ${}b$ heißt ein kleinstes gemeinsames Vielfaches der ${}a_{1},\ldots ,a_{n}$, wenn ${}b$ ein gemeinsames Vielfaches ist und wenn jedes andere gemeinsame Vielfache ein Vielfaches von ${}b$ ist.

Ein gemeinsames Vielfaches ist eine obere Schranke von ${}\{a_{1},\ldots ,a_{k}\}$ und das kleinste gemeinsame Vielfache ist das Supremum davon.

Beispiel

Zu natürlichen Zahlen ${}a_{1},\ldots ,a_{k}$ bildet die Menge ${}G$ aller gemeinsamer Teiler der ${}a_{i}$ eine endliche Menge, die bezüglich der Teilbarbeit geordnet ist. Dabei ist der größte gemeinsame Teiler in ${}G$ in der Tat das größte Element und ${}1$ ist der kleinste gemeinsame Teiler. Es ist keineswegs selbstverständlich, dass es einen größten gemeinsamen Teiler gibt, das hängt mit der eindeutigen Primfaktorzerlegung zusammen und folgt beispielsweise aus Satz 8.4. Unter der Ordnungsrelation ${}\geq$ gibt es in ${}G$ natürlich ein größtes Element, es ist aber eine zahlentheoretische Besonderheit, dass dieses Element von allen anderen gemeinsamen Teilern geteilt wird.

Die Menge ${}V$ der gemeinsamen Vielfachen von ${}a_{1},\ldots ,a_{k}$ ist unendlich und ist ebenfalls über die Teilbarkeit geordnet. Das kleinste gemeinsame Vielfache ist darunter das kleinste Element, und zwar bezüglich der Teilbarkeitsrelation als auch bezüglich der Größergleichrelation.

<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)