Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 7/latex
\setcounter{section}{7}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Crystal Clear kdm user female.svg} }
\end{center}
\bildtext {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.} }
\bildlizenz { Crystal Clear kdm user female.svg } {} {Ftiercel} {Commons} {GNU-Lizenz für freie Dokumentatio} {}
\zwischenueberschrift{Ordnungsrelationen}
Eine reflexive, transitive und antisymmetrische Relation nennt man eine Ordnung, wofür man häufig ein Symbol wie
\mathl{\geq, \leq,\preccurlyeq, \subseteq}{} verwendet. Wir geben nochmal die ausführliche Definition.
\inputdefinition
{}
{
Eine
\definitionsverweis {Relation}{}{}
$\preccurlyeq$ auf einer Menge $I$ heißt \definitionswort {Ordnungsrelation}{} oder \definitionswort {Ordnung}{,} wenn folgende drei Bedingungen erfüllt sind.
\aufzaehlungdrei{Es ist
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{i
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Aus
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{j
}
{ \preccurlyeq }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt stets
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Aus
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{j
}
{ \preccurlyeq }{i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\mavergleichskette
{\vergleichskette
{i
}
{ = }{j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
}
Eine Menge mit einer fixierten Ordnung darauf heißt \stichwort {geordnete Menge} {.} Zu jeder geordneten Menge
\mathl{(M, \preccurlyeq)}{} und jede Teilmenge
\mavergleichskette
{\vergleichskette
{N
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist auch $N$ eine geordnete Menge, indem man direkt die Ordnungsbeziehung von $M$ übernimmt. Man spricht von der \stichwort {induzierten Ordnung} {} auf $N$.
\inputdefinition
{}
{
Eine
\definitionsverweis {Ordnungsrelation}{}{}
$\preccurlyeq$ auf einer Menge $I$ heißt \definitionswort {lineare Ordnung}{}
\zusatzklammer {oder \definitionswort {totale Ordnung}{}} {} {,}
wenn zu je zwei Elementen
\mavergleichskette
{\vergleichskette
{x,y
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Beziehung
\mathkor {} {x \preccurlyeq y} {oder} {y \preccurlyeq x} {}
gilt.
}
Man sagt auch, dass bei einer linearen Ordnung je zwei Elementen \stichwort {vergleichbar} {} sind.
\inputbeispiel{}
{
Auf den natürlichen Zahlen besteht zwischen
\mathkor {} {n} {und} {k} {}
die
\definitionsverweis {Ordnungsrelation}{}{}
\mavergleichskette
{\vergleichskette
{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
\definitionsverweis {totale Ordnung}{}{.}
Mit der Addition kann man dies folgendermaßen ausdrücken: Es ist
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
genau dann, wenn es eine natürliche Zahl $m$ mit
\mavergleichskette
{\vergleichskette
{n
}
{ = }{k+m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt.
}
\inputbemerkung
{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Totale orde.svg} }
\end{center}
\bildtext {Eine totale Ordnung auf einer endlichen Menge ist durch ein Angangselement
\zusatzklammer {kleinstes Element} {} {}
und dadurch gegeben, dass jedem Element
\zusatzklammer {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.} }
\bildlizenz { Totale orde.svg } {} {Rinke 80} {Commons} {gemeinfrei} {}
Auf einer endlichen Menge $M$ mit $n$ Elementen sind die
\definitionsverweis {totalen Ordnungen}{}{}
einfach zu überschauen. Eine totale Ordnung auf $M$ ist das gleiche wie eine
\definitionsverweis {bijektive Abbildung}{}{}
\maabb {\varphi} { { \{ 1 , \ldots , n \} } } {M
} {,}
also eine Nummerierung von $M$. Eine solche Nummerierung legt über
\mavergleichskette
{\vergleichskette
{ \varphi(i)
}
{ \geq }{ \varphi(j)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
falls
\mavergleichskette
{\vergleichskette
{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
\zusatzklammer {auch die nicht totalen} {} {}
Ordnungen in einer endlichen Menge zu verschaffen.
}
\inputbeispiel{}
{
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
\definitionsverweis {totale Ordnung}{}{}
gegeben. Dann definiert man auf $W$ die sogenannte \stichwort {lexikographische Ordnung} {,} indem für Wörter $w,z$ die Beziehung
\mavergleichskettedisp
{\vergleichskette
{w
}
{ \preccurlyeq_{\text{lex} }} {z
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {$w$ kommt im Lexikon vor $z$} {} {}
genau dann gilt, wenn sie gleich sind oder wenn an der ersten Stelle von vorne gelesen, wo sich
\mathkor {} {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
\zusatzklammer {\anfuehrung{Vers}{} kommt vor \anfuehrung{Verstand}{}} {} {.}
Die lexikographische Ordnung ist eine totale Ordnung.
}
\inputbeispiel{}
{
Auf jeder Menge $M$ ist die identische Relation, also die \definitionsverweis {Relation}{}{,} bei der jedes Element nur mit sich selbst in Relation steht, eine \definitionsverweis {Ordnungsrelation}{}{.}
}
\inputdefinition
{}
{
Ein
\definitionsverweis {kommutativer Ring}{}{}
heißt \definitionswort {angeordnet}{,} wenn es eine
\definitionsverweis {totale Ordnung}{}{}
$\geq$ auf $R$ gibt, die die beiden Eigenschaften
\aufzaehlungzwei {Aus
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\mavergleichskette
{\vergleichskette
{a+c
}
{ \geq }{b+c
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für beliebige
\mavergleichskette
{\vergleichskette
{a,b,c
}
{ \in }{R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
} {Aus
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{b
}
{ \geq }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\mavergleichskette
{\vergleichskette
{ab
}
{ \geq }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für beliebige
\mavergleichskette
{\vergleichskette
{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 \stichwort {angeordneter Körper} {.} Die ganzen Zahlen $\Z$, die rationalen Zahlen $\Q$ und die reellen Zahlen $\R$ sind angeordnete Ringe bzw. Körper. Der Körper der komplexen Zahlen ${\mathbb C}$ ist nicht angeordnet \zusatzklammer {und lässt sich auch nicht anordnen} {} {.}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Verband_Teiler30.png} }
\end{center}
\bildtext {} }
\bildlizenz { Verband_Teiler30.png } {} {SirJective} {Commons} {CC-by-sa 3.0} {}
\inputdefinition
{}
{
Man sagt, dass die
\definitionsverweis {natürliche Zahl}{}{}
$a$ die natürliche Zahl $b$ \definitionswort {teilt}{}
\zusatzklammer {oder dass $b$ von $a$ \definitionswort {geteilt}{} wird, oder dass $b$ ein \definitionswort {Vielfaches}{} von $a$ ist} {} {,}
wenn es eine natürliche Zahl $c$ derart gibt, dass
\mavergleichskette
{\vergleichskette
{b
}
{ = }{c \cdot a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Man schreibt dafür auch $a {{|}} b$.
}
Achtung! Die Teilbarkeitsbeziehung in $\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
\mathl{{ \frac{ b }{ a } }}{} ganzzahlig ist. Solche Charakterisierungen mit deutlich komplizierteren Strukturen verdunkeln den einfachen Sachverhalt.
{Teilbarkeitstheorie (N)/Verschiedene Eigenschaften/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktvoraussetzung {In $\N$ gelten folgende Teilbarkeitsbeziehungen.}
\faktfolgerung {\aufzaehlungsechs{Für jede natürliche Zahl $a$ gilt
\mathkor {} {1 \, {{|}}\, a} {und} {a \,{{|}}\, a} {.}
}{Für jede natürliche Zahl $a$ gilt
\mathl{a \,{{|}}\, 0}{.}
}{Gilt
\mathkor {} {a \,{{|}}\, b} {und} {b \,{{|}}\, c} {,}
so gilt auch
\mathl{a \,{{|}}\, c}{.}
}{Gilt
\mathkor {} {a \,{{|}}\, b} {und} {c \,{{|}}\, d} {,}
so gilt auch
\mathl{ac \,{{|}}\, bd}{.}
}{Gilt
\mathl{a \,{{|}}\, b}{,} so gilt auch
\mathl{ac \,{{|}}\, bc}{} für jede natürliche Zahl $c$.
}{Gilt
\mathkor {} {a \,{{|}}\, b} {und} {a \,{{|}}\, c} {,}
so gilt auch
\mathl{a \,{{|}}\, { \left( rb+sc \right) }}{} für beliebige natürliche Zahlen $r,s$.
}}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 7.18. }
\inputbeispiel{}
{
Wir betrachten die positiven natürlichen Zahlen $\N_+$ zusammen mit der Teilbarkeitsbeziehung. Dies ergibt eine
\definitionsverweis {Ordnung}{}{}
auf $\N_+$. Die Teilbarkeitsrelation ist in der Tat reflexiv, da stets
\mathl{n{{|}}n}{} ist, wie
\mavergleichskette
{\vergleichskette
{m
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
zeigt. Die Transitivität wurde in
Lemma 7.9 (3)
gezeigt. Die Antisymmetrie folgt so: Aus
\mathkor {} {n=ak} {und} {k=bn} {}
folgt
\mavergleichskette
{\vergleichskette
{n
}
{ = }{(ab)n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Da wir uns auf positive natürliche Zahlen beschränken, folgt
mit der Kürzungsregel
\mavergleichskette
{\vergleichskette
{ab
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und daraus wegen
\mavergleichskette
{\vergleichskette
{a,b
}
{ \leq }{ ab
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
auch
\mavergleichskette
{\vergleichskette
{a
}
{ = }{b
}
{ = }{1
}
{ }{
}
{ }{
}
}
{}{}{.}
Also ist
\mavergleichskette
{\vergleichskette
{k
}
{ = }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Einfache Beispiele wie \mathkon { 2 } { und } { 3 }{ } zeigen, dass hier keine
\definitionsverweis {totale Ordnung}{}{}
vorliegt, da weder $2$ von $3$ noch umgekehrt geteilt wird.
}
\inputbeispiel{}
{
Es sei $M$ eine beliebige Menge und
\mavergleichskette
{\vergleichskette
{ R
}
{ = }{ \mathfrak {P} \, (M )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die
\definitionsverweis {Potenzmenge}{}{}
davon. Dann sind die Elemente aus
\mavergleichskette
{\vergleichskette
{ R
}
{ = }{ \mathfrak {P} \, ( M )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzgs {also die Teilmengen von $M$} {}
durch die Inklusionsbeziehung $\subseteq$
\definitionsverweis {geordnet}{}{.}
Die Reflexivität bedeutet einfach, dass eine jede Menge in sich selbst enthalten ist und die Transitivität bedeutet, dass aus
\mavergleichskette
{\vergleichskette
{T_1
}
{ \subseteq }{T_2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{T_2
}
{ \subseteq }{T_3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Inklusion
\mavergleichskette
{\vergleichskette
{T_1
}
{ \subseteq }{T_3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt. Die Antisymmetrie ist dabei ein wichtiges Beweisprinzip für die Gleichheit von Mengen: Zwei Mengen
\mathl{T_1, T_2}{} sind genau dann gleich, wenn
\mathkor {} {T_1 \subseteq T_2} {und umgekehrt} {T_2 \subseteq T_1} {}
gilt.
}
\inputbeispiel{}
{
Es sei $X$ eine Menge
\zusatzklammer {beispielsweise ein reelles Intervall, oder ein topologischer Raum} {} {,}
so ist die Menge der
\zusatzklammer {stetigen} {} {}
Funktionen
\maabb {f} {X} { \R
} {}
geordnet, indem man
\mavergleichskette
{\vergleichskette
{f
}
{ \geq }{g
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
dadurch definiert, dass
\mavergleichskette
{\vergleichskette
{f(x)
}
{ \geq }{g(x)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für jeden Punkt
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{X
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sein muss. Dies ist offensichtlich keine totale Ordnung.
}
\inputdefinition
{}
{
Es sei
\mathbed {(M_i, \leq_i)} {}
{i \in I} {}
{} {} {} {,}
eine Familie von
\definitionsverweis {geordneten Mengen}{}{.}
Dann nennt man die auf der
\definitionsverweis {Produktmenge}{}{}
\mavergleichskette
{\vergleichskette
{M
}
{ = }{ \prod_{i \in I} M_i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
durch
\mavergleichskettedisp
{\vergleichskette
{ (x_i)_{i \in I}
}
{ \leq} { (y_i)_{i \in I}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
falls
\mavergleichskettedisp
{\vergleichskette
{x_i
}
{ \leq_i} {y_i
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{i
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt, die
\definitionswort {Produktordnung}{.}
}
In Beispiel 7.12 werden die reellen Zahlen so oft genommen, wie es $X$ vorgibt. Dort liegt also eine Produktordnung vor,
\zwischenueberschrift{Ordnungstreue Abbildungen}
\inputdefinition
{}
{
Es seien
\mathkor {} {(M_1, \leq_1)} {und} {(M_2, \leq_2)} {}
zwei Mengen, auf denen jeweils eine
\definitionsverweis {Ordnung}{}{}
definiert ist. Eine
\definitionsverweis {Abbildung}{}{}
\maabbeledisp {F} {M_1} {M_2
} {x} {F(x)
} {,}
heißt \definitionswort {ordnungstreu}{}
\zusatzklammer {oder \definitionswort {monoton}{}} {} {,}
wenn für alle
\mavergleichskette
{\vergleichskette
{x,x'
}
{ \in }{M_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{x
}
{ \leq_1 }{x'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
stets auch
\mavergleichskette
{\vergleichskette
{F(x)
}
{ \leq_2 }{F(x')
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Monotonicity example1.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Monotonicity example1.svg } {} {Oleg Alexandrov} {Commons} {gemeinfrei} {}
Monotone Abbildungen zwischen \mathkor {} {\R} {und} {\R} {} sind aus den Anfängervorlesungen bekannt. Ordnungstreue Abbildungen sind einfach die \definitionsverweis {relationstreuen Abbildungen}{}{,} wenn die beteiligten Relationen Ordnungen sind.
\inputdefinition
{}
{
Es seien
\mathkor {} {(M_1, \leq_1)} {und} {(M_2, \leq_2)} {}
zwei Mengen, auf denen jeweils eine
\definitionsverweis {Ordnung}{}{}
definiert ist. Eine
\definitionsverweis {Abbildung}{}{}
\maabbeledisp {F} {M_1} {M_2
} {x} {F(x)
} {,}
heißt \definitionswort {ordnungsvolltreu}{,} wenn für alle
\mavergleichskette
{\vergleichskette
{x,x'
}
{ \in }{M_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
genau dann
\mavergleichskette
{\vergleichskette
{x
}
{ \leq_1 }{x'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt, wenn
\mavergleichskette
{\vergleichskette
{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.
{Ordnung/Ordnungsvolltreu in Potenzmenge/Injektiv/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mathl{(M, \leq)}{} eine
\definitionsverweis {geordnete Menge}{}{}
und
\mathl{\mathfrak {P} \, (M )}{} die
\definitionsverweis {Potenzmenge}{}{}
von $M$.}
\faktfolgerung {Dann ist die Abbildung
\maabbeledisp {} {M} {\mathfrak {P} \, (M )
} {x} {{ \left\{ y \in M \mid y \leq x \right\} }
} {,}
\definitionsverweis {ordnungsvolltreu}{}{}
und
\definitionsverweis {injektiv}{}{}
ist, wobei die Potenzmenge mit der
\definitionsverweis {Inklusion}{}{}
versehen ist.}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 7.28. }
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
\mavergleichskette
{\vergleichskette
{t
}
{ \leq }{s
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
genau dann, wenn
\mavergleichskettedisp
{\vergleichskette
{ [- \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
\zusatzklammer {siehe die nächste Vorlesung} {} {,}
oder
Satz 9.22,
oder die Definition einer
\definitionsverweis {Äquivalenzklasse}{}{}
für ähnliche Konstruktionen.
Wir erwähnen noch die folgende Variante einer ordnungstreuen Abbildung.
\inputdefinition
{}
{
Es seien
\mathkor {} {(M_1, \leq_1)} {und} {(M_2, \leq_2)} {}
zwei Mengen, auf denen jeweils eine
\definitionsverweis {Ordnung}{}{}
definiert ist. Eine
\definitionsverweis {Abbildung}{}{}
\maabbeledisp {F} {M_1} {M_2
} {x} {F(x)
} {,}
heißt \definitionswort {monoton fallend}{,} wenn für alle
\mavergleichskette
{\vergleichskette
{x,x'
}
{ \in }{M_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{x
}
{ \leq_1 }{x'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
stets
\mavergleichskette
{\vergleichskette
{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.
\zwischenueberschrift{Extremaleigenschaften}
\inputdefinition
{}
{
Es sei
\mathl{(I,\preccurlyeq)}{} eine
\definitionsverweis {geordnete Menge}{}{.}
Ein Element
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt \definitionswort {größtes Element}{} von $I$, wenn
\mavergleichskette
{\vergleichskette
{y
}
{ \preccurlyeq }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für jedes
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
\inputdefinition
{}
{
Es sei
\mathl{(I,\preccurlyeq)}{} eine
\definitionsverweis {geordnete Menge}{}{.}
Ein Element
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt \definitionswort {kleinstes Element}{} von $I$, wenn
\mavergleichskette
{\vergleichskette
{x
}
{ \preccurlyeq }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für jedes
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
\inputdefinition
{}
{
Es sei
\mathl{(I,\preccurlyeq)}{} eine
\definitionsverweis {geordnete Menge}{}{.}
Ein Element
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt \definitionswort {maximal}{}
\zusatzklammer {in $I$} {} {}
oder ein \definitionswort {maximales Element}{}
\zusatzklammer {von $I$} {} {,}
wenn es kein Element
\mathbed {y \in I} {}
{y \neq x} {}
{} {} {} {,}
mit
\mavergleichskette
{\vergleichskette
{x
}
{ \preccurlyeq }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt.
}
\inputdefinition
{}
{
Es sei
\mathl{(I,\preccurlyeq)}{} eine
\definitionsverweis {geordnete Menge}{}{.}
Ein Element
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt \definitionswort {minimal}{}
\zusatzklammer {in $I$} {} {}
oder ein \definitionswort {minimales Element}{}
\zusatzklammer {von $I$} {} {,}
wenn es kein Element
\mathbed {y \in I} {}
{y \neq x} {}
{} {} {} {,}
mit
\mavergleichskette
{\vergleichskette
{ 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
\mathl{[0,1]}{} besitzt die $0$ als kleinstes und die $1$ als größtes Element, das offene Intervall
\mathl{]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 $\N_{\geq 2}$ mit der Teilbarkeitsrelation sind genau die \definitionsverweis {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 \zusatzklammer {diese nennt man auch \stichwort {Atome} {}} {} {.}
\inputdefinition
{}
{
Es sei
\mathl{(I,\preccurlyeq)}{} eine
\definitionsverweis {geordnete Menge}{}{}
und
\mavergleichskette
{\vergleichskette
{J
}
{ \subseteq }{ I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Teilmenge. Ein Element
\mavergleichskette
{\vergleichskette
{s
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt \definitionswort {obere Schranke}{} für $J$, wenn
\mavergleichskette
{\vergleichskette
{ y
}
{ \preccurlyeq }{s
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für jedes
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{J
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
\inputdefinition
{}
{
Es sei
\mathl{(I,\preccurlyeq)}{} eine
\definitionsverweis {geordnete Menge}{}{}
und
\mavergleichskette
{\vergleichskette
{J
}
{ \subseteq }{ I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Teilmenge. Ein Element
\mavergleichskette
{\vergleichskette
{s
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt \definitionswort {untere Schranke}{} für $J$, wenn
\mavergleichskette
{\vergleichskette
{ s
}
{ \preccurlyeq }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für jedes
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{J
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
\inputdefinition
{}
{
Es sei
\mathl{(I,\preccurlyeq)}{} eine
\definitionsverweis {geordnete Menge}{}{}
und
\mavergleichskette
{\vergleichskette
{J
}
{ \subseteq }{ I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Teilmenge. Ein Element
\mavergleichskette
{\vergleichskette
{s
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt \definitionswort {Supremum}{} von $J$, wenn $s$ die
\definitionsverweis {kleinste}{}{}
\definitionsverweis {obere Schranke}{}{}
von $J$ ist.
}
\inputdefinition
{}
{
Es sei
\mathl{(I,\preccurlyeq)}{} eine
\definitionsverweis {geordnete Menge}{}{}
und
\mavergleichskette
{\vergleichskette
{J
}
{ \subseteq }{ I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Teilmenge. Ein Element
\mavergleichskette
{\vergleichskette
{s
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt \definitionswort {Infimum}{} von $J$, wenn $s$ die
\definitionsverweis {größte}{}{}
\definitionsverweis {untere Schranke}{}{}
von $J$ ist.
}
Für das offene Intervall
\mathl{]0,1[}{} ist jede reelle Zahl
\mavergleichskette
{\vergleichskette
{s
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine obere Schranke und $1$ ist das Supremum.
Wir besprechen einige weitere Teilbarkeitsbegriffe und erfassen sie mit unserem ordnungstheoretischen Vokabular.
\inputdefinition
{}
{
Es seien
\mathl{a_1 , \ldots , a_k}{}
\definitionsverweis {natürliche Zahlen}{}{.}
Dann heißt eine natürliche Zahl $t$ \definitionswort {gemeinsamer Teiler}{} der
\mathl{a_1 , \ldots , a_k}{,} wenn $t$ jedes $a_i$
\definitionsverweis {teilt}{}{}
\zusatzklammer {
\mavergleichskettek
{\vergleichskettek
{i
}
{ = }{1 , \ldots , k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {.}
Eine natürliche Zahl $g$ heißt \definitionswort {größter gemeinsamer Teiler}{} der
\mathl{a_1 , \ldots , a_k}{,} wenn $g$ ein gemeinsamer Teiler ist und wenn jeder gemeinsame Teiler $t$ dieses $g$ teilt.
Die Elemente
\mathl{a_1 , \ldots , a_k}{} heißen \definitionswort {teilerfremd}{,} wenn $1$ ihr größter gemeinsamer Teiler ist.
}
Ein gemeinsamer Teiler ist eine untere Schranke von
\mathl{\{a_1 , \ldots , a_k\}}{} bezüglich der Teilbarkeitsrelation und der größte gemeinsame Teiler ist das Infimum davon.
\inputdefinition
{}
{
Zu einer Menge von
\definitionsverweis {natürlichen Zahlen}{}{}
\mathdisp {a_1 , \ldots , a_n} { }
heißt eine natürliche Zahl $b$ ein \definitionswort {gemeinsames Vielfaches}{,} wenn $b$ ein
\definitionsverweis {Vielfaches}{}{}
von jedem $a_i$ ist, also von jedem $a_i$
\definitionsverweis {geteilt}{}{}
wird.
Die Zahl $b$ heißt ein \definitionswort {kleinstes gemeinsames Vielfaches}{} der
\mathl{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
\mathl{\{a_1 , \ldots , a_k\}}{} und das kleinste gemeinsame Vielfache ist das Supremum davon.
\inputbeispiel{}
{
Zu natürlichen Zahlen
\mathl{a_1 , \ldots , a_k}{} bildet die Menge $G$ aller
\definitionsverweis {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
\definitionsverweis {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
\mathl{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.
}