Kurs:Grundkurs Mathematik (Osnabrück 2018-2019)/Teil I/Vorlesung 10/latex
\setcounter{section}{10}
\zwischenueberschrift{Die Ordnungsrelation}
Wir wollen auf den natürlichen Zahlen die Größer- bzw. genauer die Größergleich-Ordnung einführen.
\inputdefinition
{}
{
Eine \definitionswort {Relation}{} $R$ auf einer Menge $M$ ist eine Teilmenge der Produktmenge
\mathl{M \times M}{,} also
\mavergleichskette
{\vergleichskette
{R
}
{ \subseteq }{M \times M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
\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
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
} Diese Eigenschaften heißen der Reihe nach \stichwort {Reflexivität} {,} \stichwort {Transitivität} {} und \stichwort {Antisymmetrie} {.}
\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.
}
\zwischenueberschrift{Die Ordnung auf den natürlichen Zahlen}
\inputdefinition
{}
{
Man sagt, dass eine natürliche Zahl $n$
\definitionswort {größergleich}{}
einer natürlichen Zahl $k$ ist, geschrieben
\mavergleichskettedisp
{\vergleichskette
{n
}
{ \geq} {k
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wenn man von $k$ aus durch endlichfaches Nachfolgernehmen zu $n$ gelangt.
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Natural numbers.svg} }
\end{center}
\bildtext {Auf dem nach rechts verlaufenden Zahlenstrahl bedeutet
\mathl{n \geq k}{,} dass sich $n$ weiter rechts als $k$ befindet. Diese Intepretation gilt für alle reellen Zahlen.} }
\bildlizenz { Natural numbers.svg } {} {Junaidpv} {Commons} {gemeinfrei} {}
Statt
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{ k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
schreibt man auch
\mavergleichskette
{\vergleichskette
{k
}
{ \leq }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {gesprochen kleinergleich} {} {.}
Die Schreibweise
\mavergleichskette
{\vergleichskette
{n
}
{ > }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
bedeutet
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{n
}
{ \neq }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
\inputfaktbeweis
{Natürliche Zahlen/Ordnungsrelation/Addition/Fakt}
{Lemma}
{}
{
\faktsituation {Für
\definitionsverweis {natürliche Zahlen}{}{}
\mathl{n,k}{} gilt}
\faktfolgerung {
\mavergleichskettedisp
{\vergleichskette
{n
}
{ \geq} {k
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
genau dann, wenn es ein
\mavergleichskette
{\vergleichskette
{ m
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {k+m
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gibt.}
\faktzusatz {}
\faktzusatz {}
}
{
Die Zahl $m$ gibt an, wie oft man von $k$ aus den Nachfolger nehmen muss, um zu $n$ zu gelangen.
\inputfaktbeweis
{Natürliche Zahlen/Ordnungsrelation/01/Alternative/Fakt}
{Lemma}
{}
{
\faktsituation {Für die Größergleich-Relation in den
\definitionsverweis {natürlichen Zahlen}{}{}
gelten die folgenden Aussagen.}
\faktfolgerung {\aufzaehlungdrei{Es ist
\mavergleichskettedisp
{\vergleichskette
{a
}
{ \geq} {0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{ a
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{a
}
{ =} { 0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
oder
\mavergleichskettedisp
{\vergleichskette
{a
}
{ \geq} {1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Bei
\mavergleichskettedisp
{\vergleichskette
{a
}
{ \geq} {b
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt
\mavergleichskettedisp
{\vergleichskette
{a
}
{ =} {b
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
oder
\mavergleichskettedisp
{\vergleichskette
{a
}
{ \geq} {b+1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir verwenden die Charakterisierung aus
Lemma 10.5.
\aufzaehlungdrei{Ist klar wegen
\mavergleichskette
{\vergleichskette
{a
}
{ = }{ 0+a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Wir zeigen die Aussage
\mavergleichskette
{\vergleichskette
{a
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{ a
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
durch Induktion über $a$. Für
\mavergleichskette
{\vergleichskette
{a
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist die Aussage klar. Es sei also angenommen, dass die Aussage für ein bestimmtes $a$ gelte. Dann ist
\mavergleichskette
{\vergleichskette
{a
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Im ersten Fall ist dann
\mavergleichskette
{\vergleichskette
{1+a
}
{ = }{1+0
}
{ = }{1
}
{ }{
}
{ }{
}
}
{}{}{}
und insbesondere
\mavergleichskette
{\vergleichskette
{1+a
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Im zweiten Fall ist
\mavergleichskette
{\vergleichskette
{a
}
{ = }{b+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit einem
\mavergleichskette
{\vergleichskette
{ b
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und damit
\mavergleichskette
{\vergleichskette
{a+1
}
{ = }{(b+1) +1
}
{ = }{ 1+ (b+1)
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Wird ähnlich wie (2) bewiesen, siehe
Aufgabe 10.6.
}
\inputfaktbeweis
{Natürliche Zahlen/Ordnungsrelation/Total/Fakt}
{Satz}
{}
{
\faktsituation {Auf den
\definitionsverweis {natürlichen Zahlen}{}{}}
\faktfolgerung {ist durch die Größergleich-Relation $\geq$ eine
\definitionsverweis {totale Ordnung}{}{}
definiert.}
\faktzusatz {}
\faktzusatz {}
}
{
Wir verwenden
die Charakterisierung
mit der Addition. Wegen
\mavergleichskette
{\vergleichskette
{n
}
{ = }{n+0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wenn
\mavergleichskette
{\vergleichskette
{k
}
{ \geq }{\ell
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ \ell
}
{ \geq }{m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, so bedeutet dies, dass es natürliche Zahlen
\mathl{a,b}{} mit
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ \ell +a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ \ell
}
{ = }{m+b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt. Dann gilt insgesamt
\mavergleichskettedisp
{\vergleichskette
{ k
}
{ =} { \ell +a
}
{ =} { (m+b)+ a
}
{ =} { m+ (b+a)
}
{ } {
}
}
{}{}{}
und somit ist auch
\mavergleichskette
{\vergleichskette
{k
}
{ \geq }{ m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Aus
\mavergleichskette
{\vergleichskette
{k
}
{ \geq }{ \ell
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{\ell
}
{ \geq }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ergibt sich
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ \ell +a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{\ell
}
{ = }{ k+b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und somit
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ k+(a+b)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dies ist
nach der Abziehregel
nur bei
\mavergleichskette
{\vergleichskette
{a+b
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
möglich, und dies ist wiederum, da $0$ kein Nachfolger ist, nur bei
\mavergleichskette
{\vergleichskette
{a
}
{ = }{b
}
{ = }{ 0
}
{ }{
}
{ }{
}
}
{}{}{}
möglich. Die Aussage
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{b
}
{ \geq }{a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
beweisen wir durch Induktion über $a$
\zusatzklammer {für jedes feste $b$} {} {,}
wobei der Induktionsanfang wegen
\mavergleichskette
{\vergleichskette
{b
}
{ \geq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
klar ist. Die Aussage gelte also für ein bestimmtes $a$. Wenn die erste Möglichkeit gilt, also
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
so gilt wegen
\mavergleichskettedisp
{\vergleichskette
{a+1
}
{ >} {a
}
{ \geq} {b
}
{ } {
}
{ } {
}
}
{}{}{}
erst recht
\mavergleichskette
{\vergleichskette
{a+1
}
{ \geq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wenn die zweite Möglichkeit gilt, also
\mavergleichskette
{\vergleichskette
{a
}
{ \leq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
so gibt es zwei Möglichkeiten. Bei
\mavergleichskette
{\vergleichskette
{a
}
{ = }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{a+1
}
{ \geq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und die Gesamtaussage gilt für
\mathl{a+1}{.} Andernfalls ist
\mavergleichskette
{\vergleichskette
{ a
}
{ < }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und somit ist
nach Lemma 10.6 (3)
\mavergleichskette
{\vergleichskette
{a+1
}
{ \leq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und die Gesamtaussage gilt erneut.
Wir begründen nun, dass die Ordnungsrelation mit der Addition und der Multiplikation verträglich ist.
\inputfaktbeweis
{Natürliche Zahlen/Ordnungsrelation/Verträglichkeit/Fakt}
{Satz}
{}
{
\faktsituation {Es seien
\mathl{a,b,c}{}
\definitionsverweis {natürliche Zahlen}{}{.}}
\faktuebergang {Dann gelten folgende Aussagen.}
\faktfolgerung {\aufzaehlungfuenf{Es ist
\mavergleichskettedisp
{\vergleichskette
{a
}
{ \geq} {b
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
genau dann, wenn
\mavergleichskettedisp
{\vergleichskette
{a+c
}
{ \geq} {b+c
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist.
}{Aus
\mavergleichskettedisp
{\vergleichskette
{a
}
{ \geq} {b
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{c
}
{ \geq} {d
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
folgt
\mavergleichskettedisp
{\vergleichskette
{a+c
}
{ \geq} {b+d
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Aus
\mavergleichskettedisp
{\vergleichskette
{a
}
{ \geq} {b
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
folgt
\mavergleichskettedisp
{\vergleichskette
{ca
}
{ \geq} {cb
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Aus
\mavergleichskettedisp
{\vergleichskette
{a
}
{ \geq} {b
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{c
}
{ \geq} {d
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
folgt
\mavergleichskettedisp
{\vergleichskette
{ac
}
{ \geq} {bd
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Aus
\mavergleichskettedisp
{\vergleichskette
{c
}
{ \geq} {1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{ca
}
{ \geq} {cb
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
folgt
\mavergleichskettedisp
{\vergleichskette
{a
}
{ \geq} {b
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
\aufzaehlungfuenf{Wir beweisen die Aussagen mit
Lemma 10.5.
Nach Voraussetzung gibt es ein
\mavergleichskette
{\vergleichskette
{ m
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ a
}
{ = }{ b+m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist auch
\mavergleichskette
{\vergleichskette
{ a
}
{ = }{ b+m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
\mavergleichskette
{\vergleichskette
{a+c
}
{ = }{ b+m+c
}
{ = }{ b+c+m
}
{ }{
}
{ }{
}
}
{}{}{,}
was
\mavergleichskette
{\vergleichskette
{a+c
}
{ \geq }{ b+c
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
bedeutet.
}{Zweifache Anwendung von Teil (1) liefert
\mavergleichskettedisp
{\vergleichskette
{a+c
}
{ \geq} { b+c
}
{ \geq} { b+d
}
{ } {
}
{ } {
}
}
{}{}{,}
so dass die Transitivität den Schluss ergibt.
}{Die Voraussetzung bedeutet wieder
\mavergleichskette
{\vergleichskette
{a
}
{ = }{ b+m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit einem
\mavergleichskette
{\vergleichskette
{ m
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist mit dem Distributivgesetz
\mavergleichskettedisp
{\vergleichskette
{ ca
}
{ =} { c (b+m)
}
{ =} { cb +cm
}
{ } {
}
{ } {
}
}
{}{}{,}
also
\mavergleichskette
{\vergleichskette
{ ca
}
{ \geq }{ cm
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Aus den Voraussetzungen und Teil (3) ergibt sich
\mavergleichskettedisp
{\vergleichskette
{ac
}
{ \geq} {bc
}
{ \geq} {bd
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Sei
\mavergleichskette
{\vergleichskette
{c
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir beweisen die Kontraposition, dass aus der Größerbeziehung
\mavergleichskette
{\vergleichskette
{ b
}
{ > }{ a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Größerbeziehung
\mavergleichskette
{\vergleichskette
{ bc
}
{ > }{ ac
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt. Sei also
\mavergleichskette
{\vergleichskette
{b
}
{ > }{a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist
\mavergleichskette
{\vergleichskette
{b
}
{ \geq }{a+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und somit ist nach Teil (3) und Teil (2)
\mavergleichskettedisp
{\vergleichskette
{bc
}
{ \geq} {(a+1)c
}
{ =} { ac +c
}
{ \geq} {ac+1
}
{ } {
}
}
{}{}{,}
also
\mavergleichskette
{\vergleichskette
{bc
}
{ > }{ac
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
Die algorithmische Bestimmung der Ordnungsrelation im Dezimalsystem werden wir in Korollar 15.4 beschreiben.
\zwischenueberschrift{Maxima und Minima}
\inputdefinition
{}
{
Zu einer endlichen nichtleeren Teilmenge
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt $a$ das
\definitionswort {Maximum}{}
von $T$, wenn
\mavergleichskette
{\vergleichskette
{ a
}
{ \in }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist und wenn
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
\inputdefinition
{}
{
Zu einer nichtleeren Teilmenge
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt $b$ das
\definitionswort {Minimum}{}
von $T$, wenn
\mavergleichskette
{\vergleichskette
{ b
}
{ \in }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist und wenn
\mavergleichskette
{\vergleichskette
{b
}
{ \leq }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
Die leere Menge besitzt weder ein Maximum noch ein Minimum. Die Gesamtmenge $\N$ besitzt das Minimum $0$ und kein Maximum.
Aus dem Induktionsprinzip folgt die nächste wichtige Eigenschaft, die besagt, dass die natürlichen Zahlen \stichwort {wohlgeordnet} {} sind. Vom intuitiven Standpunkt her ist sie selbstverständlich, wir führen sie aber trotzdem auf das Induktionsprinzip zurück. Es geht in diesem Beweis weniger dadrum, sich über die Satzaussage zu vergewissern, sondern vielmehr Einblicke in mathematisches Argumentieren zu gewinnen. Es ist auch ein Beispiel dafür, wie man eine Aussage über Teilmengen zu einer Aussage über natürliche Zahlen macht, um das Induktionsprinzip anwenden zu können.
\inputfaktbeweis
{Natürliche Zahlen/Nichtleere Teilmengen/Hat Minimum/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktvoraussetzung {Jede nichtleere Teilmenge
\mavergleichskette
{\vergleichskette
{M
}
{ \subseteq }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}}
\faktfolgerung {besitzt ein
\definitionsverweis {Minimum}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir betrachten die Aussage
\einrueckung{ $A(n)$ = Alle Teilmengen von $\N$, die $n$ enthalten, besitzen ein Minimum.}
Da jede nichtleere Teilmenge mindestens ein
\mavergleichskette
{\vergleichskette
{ n
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
besitzt, ist die Aussage des Satzes äquivalent zur Gültigkeit von
\mathl{A(n)}{} für alle $n$. Diese Aussage können wir durch Induktion beweisen. Die Aussage
\mathl{A(0)}{} besagt, dass jede Teilmenge
\mavergleichskette
{\vergleichskette
{M
}
{ \subseteq }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die die $0$ enthält, auch ein Minimum enthält. Dies ist aber klar, da dann eben $0$ das Minimum ist. Es sei die Aussage
\mathl{A(k)}{} nun für alle
\mavergleichskette
{\vergleichskette
{k
}
{ \leq }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
schon bewiesen. Wir müssen
\mathl{A(n+1)}{} beweisen. Es sei also
\mavergleichskette
{\vergleichskette
{M
}
{ \subseteq }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Teilmenge, die
\mathl{n+1}{} enthält.
\fallunterscheidungzwei {Wenn $M$ auch eine Zahl
\mavergleichskette
{\vergleichskette
{k
}
{ < }{n+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
besitzt, so besitzt $M$ nach der Induktionsvoraussetzung ein Minimum.}
{Andernfalls besitzt $M$ keine Zahl, die kleiner als
\mathl{n+1}{} ist. Dann ist aber
\mathl{n+1}{} das Minimum von $M$.}
\zwischenueberschrift{Die Differenz von natürlichen Zahlen}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Subtraction01.svg} }
\end{center}
\bildtext {Aus einer Menge mit $a$ Elementen wird eine Teilmenge mit $b$ Elementen
\zusatzklammer {
\mavergleichskettek
{\vergleichskettek
{ b
}
{ \leq }{ a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {}
herausgenommen. Zurück bleibt eine Menge mit
\mathl{a-b}{} Elementen.} }
\bildlizenz { Subtraction01.svg } {} {Nashev} {Commons} {CC-by-sa 3.0} {}
\inputdefinition
{}
{
Für
\definitionsverweis {natürliche Zahlen}{}{}
\mavergleichskettedisp
{\vergleichskette
{a
}
{ \geq} {b
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist
\mathl{a-b}{} diejenige natürliche Zahl $c$ für die
\mavergleichskettedisp
{\vergleichskette
{a
}
{ =} {b+c
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt. Sie heißt die
\definitionswort {Differenz}{}
zwischen $a$ und $b$.
}
Man mache sich hier die Logik dieser Definition klar: Die Voraussetzung
\mavergleichskettedisp
{\vergleichskette
{a
}
{ \geq} {b
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
bedeutet nach
Lemma 10.5
die Existenz einer natürlichen Zahl $c$ mit
\mavergleichskettedisp
{\vergleichskette
{a
}
{ =} {b+c
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dieses $c$ ist aufgrund der Abziehregel durch diese Eigenschaft eindeutig bestimmt. Die Differenz gibt an, wie oft man von $b$ aus den Nachfolger nehmen muss, um zu $a$ zu gelangen. Die charakteristische Eigenschaft ist die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{b +(a-b)
}
{ =} {a
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dabei ist
\mathl{a-b}{} die einzige Lösung für die Gleichung\zusatzfussnote {Das Gleichungskonzept werden wir später genauer besprechen} {.} {}
\mavergleichskettedisp
{\vergleichskette
{b+x
}
{ =} {a
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Ferner ist
\mavergleichskette
{\vergleichskette
{a-a
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wenn eine Gleichung
\mavergleichskette
{\vergleichskette
{a+b
}
{ = }{c
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gegeben ist, so sagt man beim Übergang zu
\mavergleichskettedisp
{\vergleichskette
{a
}
{ =} {c-b
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
auch, dass $b$
\zusatzklammer {beidseitig} {} {}
abgezogen wird.
Für
\mavergleichskette
{\vergleichskette
{a
}
{ < }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist der Ausdruck
\mathl{a-b}{} innerhalb der natürlichen Zahlen nicht definiert. Da zu
\mavergleichskette
{\vergleichskette
{ a,b
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
stets
\mavergleichskettedisp
{\vergleichskette
{a
}
{ \geq} {b
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
oder
\mavergleichskettedisp
{\vergleichskette
{b
}
{ \geq} {a
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt, ist einer der beiden Ausdrücke
\mathkor {} {a-b} {oder} {b-a} {}
eine wohldefinierte natürliche Zahl. Oft nennt man auch diese Zahl, die sich ergibt, wenn man die beiden Zahlen richtig geordnet hat, die Differenz der beiden Zahlen.
Für die Differenz können wir einfach eine mengentheoretische Interpretation angeben.
\inputfaktbeweis
{Natürliche Zahlen/Differenz/Mengendifferenz/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $M$ eine
\definitionsverweis {endliche Menge}{}{}
mit $m$ Elementen und es sei
\mavergleichskettedisp
{\vergleichskette
{T
}
{ \subseteq} { M
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
eine Teilmenge, die $k$ Elemente besitze.}
\faktfolgerung {Dann besitzt
\mathdisp {M \setminus T} { }
genau
\mathl{m-k}{} Elemente.}
\faktzusatz {}
\faktzusatz {}
}
{
Es ist
\mavergleichskettedisp
{\vergleichskette
{M
}
{ =} { T \uplus (M \setminus T)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
eine disjunkte Zerlegung. Daher gilt
nach Satz 8.14
\mavergleichskettedisp
{\vergleichskette
{m
}
{ =} { { \# \left( M \right) }
}
{ =} { { \# \left( T \right) } + { \# \left( M \setminus T \right) }
}
{ =} { k + { \# \left( M \setminus T \right) }
}
{ } {
}
}
{}{}{.}
Somit erfüllt
\mathl{{ \# \left( M \setminus T \right) }}{} die charakteristische Eigenschaft der Differenz und ist daher gleich
\mathl{m-k}{.}
\inputfaktbeweis
{Natürliche Zahlen/Differenz/Rechengesetze/Fakt}
{Lemma}
{}
{
\faktsituation {\aufzaehlungdrei{Für
\definitionsverweis {natürliche Zahlen}{}{}
\mathl{a,b,c}{} mit
\mavergleichskettedisp
{\vergleichskette
{a
}
{ \geq} {b
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{b+c + (a-b)
}
{ =} { c+a
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Insbesondere ist
\mavergleichskette
{\vergleichskette
{(a+c) - (b+c)
}
{ = }{a-b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ (a+c) - (a-b)
}
{ = }{ b+c
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Für natürliche Zahlen
\mathl{a,b,c,d}{} mit
\mavergleichskettedisp
{\vergleichskette
{a
}
{ \geq} {b
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{c
}
{ \geq} {d
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{ (a+c)- (b+d)
}
{ =} { (a-b) + (c-d)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Insbesondere ist bei
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
stets
\mavergleichskette
{\vergleichskette
{ (a+c)- b
}
{ = }{ (a-b) + c
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Bei
\mavergleichskettedisp
{\vergleichskette
{ b+c
}
{ \geq} {a
}
{ \geq} { b
}
{ } {
}
{ } {
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{ c
}
{ \geq }{ a-b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und es ist
\mavergleichskettedisp
{\vergleichskette
{ c- (a-b)
}
{ =} { (c+b ) -a
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}}
\faktfolgerung {}
\faktzusatz {}
\faktzusatz {}
}
{
\aufzaehlungdrei{Aus
\mavergleichskettedisp
{\vergleichskette
{b +(a-b)
}
{ =} {a
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ergibt sich direkt
\mavergleichskettedisp
{\vergleichskette
{b+c + (a-b)
}
{ =} { c+a
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Die Zusätze ergeben sich aus der Eindeutigkeit der Differenz.
}{Wegen
Satz 10.8 (2)
ist
\mavergleichskettedisp
{\vergleichskette
{a+c
}
{ \geq} {b+d
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
so dass der Ausdruck links einen Sinn ergibt. Die Rechnung
\mavergleichskettedisp
{\vergleichskette
{(b+d) +(a-b)+(c-d)
}
{ =} { d+a +(c-d)
}
{ =} {a+c
}
{ } {
}
{ } {
}
}
{}{}{}
unter Verwendung der ersten Teils zeigt, dass
\mathl{(a-b) + (c-d)}{} die charakteristische Eigenschaft von
\mathl{(a+c) - (b+d)}{} erfüllt, also wegen der Eindeutigkeit damit übereinstimmt.
}{Nach Teil (2) folgt aus
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{b+c
}
{ \geq }{a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Beziehung
\mavergleichskettedisp
{\vergleichskette
{ (a-b) + ((b+c)-a )
}
{ =} { a+b+c- (a+b)
}
{ =} { c
}
{ } {
}
{ } {
}
}
{}{}{}
und insbesondere
\mavergleichskette
{\vergleichskette
{c
}
{ \geq }{a-b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Beidseitiges Abziehen von
\mathl{a-b}{} ergibt
\mavergleichskettedisp
{\vergleichskette
{ (b+c) -a
}
{ =} { c- (a-b)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
Die folgende Aussage ist das Distributivgesetz für die Differenz.
\inputfaktbeweis
{Natürliche Zahlen/Differenz/Distributivgesetz/Fakt}
{Lemma}
{}
{
\faktsituation {Es seien
\mathl{a,b,c}{} natürliche Zahlen mit
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktfolgerung {Dann ist
\mavergleichskettedisp
{\vergleichskette
{c (a-b)
}
{ =} { ca -cb
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Nach
Satz 10.8
ist mit
\mavergleichskette
{\vergleichskette
{ a
}
{ \geq }{ b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
auch
\mavergleichskette
{\vergleichskette
{ca
}
{ \geq }{cb
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
so dass
\mathl{ca -cb}{} wohldefiniert ist. Es ist
\mavergleichskettedisp
{\vergleichskette
{a
}
{ =} {(a-b)+b
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und daher ist
nach dem Distributivgesetz für die Addition und die Multiplikation
\mavergleichskettedisp
{\vergleichskette
{ca
}
{ =} { c ((a-b)+b)
}
{ =} { c (a-b) +cb
}
{ } {
}
{ } {
}
}
{}{}{.}
Also ist
\mavergleichskettedisp
{\vergleichskette
{ c(a-b)
}
{ =} { ca-cb
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}