Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I/Vorlesung 8/latex

Aus Wikiversity
Zur Navigation springen Zur Suche springen

\setcounter{section}{8}

Wir führen nun die Addition und die Multiplikation von natürlichen Zahlen ein. Dabei müssen wir uns kurz klar machen, um was für ein Objekt es sich überhaupt handelt. Bei der Addition \zusatzklammer {der Multiplikation} {} {} wird zwei\zusatzfussnote {Es ist hier auch erlaubt, dass die beiden Zahlen gleich sind. Dann könnte man sich an dem Wort zwei stören, da ja dann nur eine Zahl vorliegt. In einem solchen Zusammenhang sind die Zahlangaben so zu verstehen, dass sie zählen, wie oft eine Zahl aufgerufen wird} {.} {} natürlichen Zahlen \mathkor {} {a} {und} {b} {} eine neue Zahl, ihre Summe
\mathl{a+b}{} \zusatzklammer {ihr Produkt \mathlk{a\cdot b}{}} {} {} zugeordnet. Weiter ober haben wir schon aus zwei Mengen ihre Vereinigung bzw. ihren Durchschnitt gebildet. Für diese Situationen gibt es das Konzept der Verknüpfung. Um dies angemessen formulieren zu können, benötigen wir die Produktmenge.






\zwischenueberschrift{Produktmengen}




\inputdefinition
{}
{

Es seien zwei Mengen \mathkor {} {L} {und} {M} {} gegeben. Dann nennt man die Menge
\mavergleichskettedisp
{\vergleichskette
{ L \times M }
{ =} { { \left\{ (x,y) \mid x \in L , \, y \in M \right\} } }
{ } { }
{ } { }
{ } { }
} {}{}{} die \definitionswort {Produktmenge}{} der beiden Mengen.

}

Die Elemente der Produktmenge nennt man \stichwort {Paare} {} und schreibt
\mathl{(x,y)}{.} Dabei kommt es wesentlich auf die Reihenfolge an. Die Produktmenge besteht also aus allen Paarkombinationen, wo in der ersten \stichwort {Komponente} {} ein Element der ersten Menge und in der zweiten Komponente ein Element der zweiten Menge steht. Zwei Paare sind genau dann gleich, wenn sie in beiden Komponenten gleich sind. Bei einer Produktmenge können natürlich auch beide Mengen gleich sein. Dann ist es verlockend, die Reihenfolge zu verwechseln, und also besonders wichtig, darauf zu achten, dies nicht zu tun. Wenn eine der beiden Mengen leer ist, so ist auch die Produktmenge leer.




\inputbeispiel{}
{

Es sei $V$ die Menge aller Vornamen \zusatzklammer {sagen wir der Vornamen, die in einer bestimmten Grundmenge an Personen wirklich vorkommen} {} {} und $N$ die Menge aller Nachnamen. Dann ist
\mathdisp {V \times N} { }
die Menge aller Namen. Elemente davon sind in Paarschreibweise beispielsweise
\mathl{(\text{Heinz},\text{Müller})}{,}
\mathl{(\text{Petra}, \text{Müller})}{} und
\mathl{(\text{Lucy},\text{Sonnenschein})}{.} Aus einem Namen lässt sich einfach der Vorname und der Nachname herauslesen, indem man entweder auf die erste oder auf die zweite Komponente des Namens schaut. Auch wenn alle Vornamen und Nachnamen für sich genommen vorkommen, so muss natürlich nicht jeder daraus gebastelte mögliche Name wirklich vorkommen. Bei der Produktmenge werden eben alle Kombinationsmöglichkeiten aus den beiden beteiligten Mengen genommen.


}




\inputbeispiel{}
{






\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Chess board blank.eps} }
\end{center}
\bildtext {} }

\bildlizenz { Chess board blank.svg } {} {Beao} {Commons} {CC-by-sa 3.0} {}

Ein Schachbrett \zusatzklammer {genauer: die Menge der Felder auf einem Schachbrett, auf denen eine Figur stehen kann} {} {} ist die Produktmenge
\mathl{\{a,b,c,d,e,f,g,h\} \times\{1,2,3,4,5,6,7,8\}}{.} Jedes Feld ist ein Paar, beispielsweise
\mathl{(a,1), (d,4), (c,7)}{.} Da die beteiligten Mengen verschieden sind, kann man statt der Paarschreibweise einfach
\mathl{a1,d4,c7}{} schreiben. Diese Notation ist der Ausgangspunkt für die Beschreibung von Stellungen und von ganzen Partien.


}




\inputbeispiel{}
{

Bei zwei reellen Intervallen \mathkor {} {M=[a,b]} {und} {L=[c,d]} {} ist die Produktmenge einfach das Rechteck
\mathdisp {[a,b] \times [c,d]} { . }
Allerdings muss man bei einem Rechteck im Hinterkopf behalten, welche Seite das erste und welche Seite das zweite Intervall ist. Für
\mathl{\R \times \R}{} schreibt man häufig auch $\R^2$.


} Man kann auch mehrfache Produktmengen bilden, wie etwa
\mavergleichskette
{\vergleichskette
{\R^ 3 }
{ = }{\R \times \R \times \R }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.}

Für eine Abbildung \maabbdisp {f} {\R} {\R } {} ist der Graph diejenige Teilmenge von
\mavergleichskette
{\vergleichskette
{\R \times \R }
{ \cong }{ \R^ 2 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} die durch alle Paare der Form
\mathl{(x,f(x))}{} gegeben sind. Diese Definition überträgt sich auf beliebige Abbildungen. Es existiert also stets ein Graph unabhängig von seiner zeichnerischen Realisierbarkeit. Diese hängt davon ab, ob man die Produktmenge aus Definitionsmenge und Wertemenge gut visualisieren kann.


\inputdefinition
{}
{

Es seien \mathkor {} {L} {und} {M} {} Mengen und es sei \maabbdisp {F} {L} {M} {} eine \definitionsverweis {Abbildung}{}{.} Dann nennt man
\mavergleichskettedisp
{\vergleichskette
{\Gamma }
{ =} { \Gamma_F }
{ =} { { \left\{ (x,F(x)) \mid x \in L \right\} } }
{ \subseteq} { L \times M }
{ } { }
} {}{}{} den \definitionswort {Graphen}{} der Abbildung $F$.

}






\zwischenueberschrift{Verknüpfungen}




\inputdefinition
{}
{

Eine \definitionswort {Verknüpfung}{} $\circ$ auf einer Menge $M$ ist eine \definitionsverweis {Abbildung}{}{} \maabbeledisp {\circ} {M\times M} {M } {(x,y)} {\circ(x,y) = x \circ y } {.}

} Statt Verknüpfung sagt man auch \stichwort {Operation} {.} Das Verknüpfungszeichen $\circ$ ist hier einigermaßen willkürlich gewählt, um vorschnelle Assoziationen zu vermeiden. In vielen konkreten Situation steht hier \mathkor {} {+} {oder} {\cdot} {.} Das \anfuehrung{neue}{} Element
\mathl{x \circ y}{} heißt dann auch das \stichwort {Ergebnis} {} der Operation. Da das Ergebnis wieder zur Ausgangsmenge $M$ gehört, kann man es weiter verknüpfen mit weiteren Elementen. Dies erfordert im Allgemeinen Klammerungen, um zu wissen, in welcher Reihenfolge welche Elemente miteinander verknüpft werden sollen. Im Allgemeinen ist
\mavergleichskettedisp
{\vergleichskette
{a \circ (b \circ c) }
{ \neq} { (a \circ b) \circ c }
{ } { }
{ } { }
{ } { }
} {}{}{.}




\inputdefinition
{}
{

Eine \definitionsverweis {Verknüpfung}{}{} \maabbeledisp {\circ} {M \times M} {M } {(x,y)} {x \circ y } {,} auf einer Menge $M$ heißt \definitionswort {assoziativ}{,} wenn für alle
\mavergleichskette
{\vergleichskette
{x,y,z }
{ \in }{M }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{ (x \circ y ) \circ z }
{ =} { x \circ (y \circ z) }
{ } { }
{ } { }
{ } { }
} {}{}{} gilt.

}

Man sagt auch, dass für die Verknüpfung das \stichwort {Assoziativgesetz} {} oder die \stichwort {Klammerregel} {} gilt.




\inputdefinition
{}
{

Eine \definitionsverweis {Verknüpfung}{}{} \maabbeledisp {\circ} {M \times M} {M } {(x,y)} {x \circ y } {,} auf einer Menge $M$ heißt \definitionswort {kommutativ}{,} wenn für alle
\mavergleichskette
{\vergleichskette
{x,y }
{ \in }{M }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{ x \circ y }
{ =} { y \circ x }
{ } { }
{ } { }
{ } { }
} {}{}{} gilt.

}

Man sagt auch, dass für die Verknüpfung das \stichwort {Kommutativgesetz} {} oder das \stichwort {Vertauschungsgesetz} {} gilt. Die Addition und die Multiplikation auf den natürlichen Zahlen sind beide assoziativ und kommutativ.


\inputdefinition
{}
{

Es sei eine Menge $M$ mit einer \definitionsverweis {Verknüpfung}{}{} \maabbeledisp {\circ} {M \times M} {M } {(x,y)} {x \circ y } {,} gegeben. Dann heißt ein Element
\mavergleichskette
{\vergleichskette
{e }
{ \in }{M }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} \definitionswort {neutrales Element}{} der Verknüpfung, wenn für alle
\mavergleichskette
{\vergleichskette
{x }
{ \in }{M }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die Gleichheit
\mavergleichskette
{\vergleichskette
{ x \circ e }
{ = }{ x }
{ = }{ e \circ x }
{ }{ }
{ }{ }
} {}{}{} gilt.

}

Bei der Addition auf den natürlichen Zahlen ist $0$ das neutrale Element und bei der Multiplikation auf den natürlichen Zahlen ist $1$ das neutrale Element. Deshalb ist es in der abstrakten Formulierung sinnvoll, eine unbelastete Bezeichnung zu wählen. Wenn die Verknüpfung kommutativ ist, so muss man die Eigenschaft des neutralen Elementes nur von einer Seite überprüfen.






\zwischenueberschrift{Die Addition auf den natürlichen Zahlen}

Die Addition auf den natürlichen Zahlen ist eine vertraute Operation und es gibt viele Möglichkeiten, sie einzuführen. Je nach Kontext und Absicht sind unterschiedliche Ansätze besser geeignet. Zur rechnerischen Definition der Addition ist etwa das schriftliche Addieren im Dezimalsystem besonders effektiv, während zum Nachweis der Assoziativität die inhaltliche Interpretation als disjunkte Vereinigung von Mengen sinnvoll ist. Um ein klares Fundament zu haben, muss man sich bei einem systematisches Aufbau der Mathematik dafür entscheiden, was man als Definition nimmt, und dann beweisen, dass der gewählte Zugang auch andere Charakterisierungen erlaubt und somit mit anderen Zugängen übereinstimmt.

Wir wollen die Addition auf den natürlichen Zahlen definieren, und zwar allein unter Bezug auf das Nachfolgernehmen, das das Zählen charakterisiert. Das Nachfolgernehmen ist ein Prozess, den man iterieren kann. Sowohl der Startwert des Nachfolgernehmens als auch die Anzahl, wie oft ein Nachfolger genommen werden soll, wird durch natürliche Zahlen beschrieben. Die $k$-fache Durchführung eines Prozesses bedeutet, dass er so oft durchgeführt wird, wie es die Menge
\mathl{\{ 1 , \ldots , k \}}{} vorgibt.






\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Additionnachfolger6.eps} }
\end{center}
\bildtext {} }

\bildlizenz { Additionnachfolger6.png } {} {Bocardodarapti} {Commons} {CC-by-sa 4.0} {}




\inputdefinition
{}
{

Die \definitionswort {Summe}{}
\mathl{n+k}{} zweier \definitionsverweis {natürlicher Zahlen}{}{} \mathkor {} {n} {und} {k} {} ist diejenige natürliche Zahl, die man erhält, wenn man von $n$ ausgehend $k$-fach den Nachfolger nimmt.

}

Die Operation heißt die \stichwort {Addition} {} und die beteiligten Zahlen nennt man die \stichwort {Summanden} {.} Nach dieser Definition wird also ausgehend von $n$ der Nachfolgerprozess $k$-fach durchgeführt. Bei
\mavergleichskette
{\vergleichskette
{k }
{ = }{0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ist dies als der nullte Nachfolger, also als $n$ selbst, zu verstehen. Bei
\mavergleichskette
{\vergleichskette
{k }
{ = }{1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ist dies der erste Nachfolger,
\mathl{n+1}{} ist also die erste Zahl $n^\prime$ nach $n$. Die Summe
\mathl{n+k}{} ist also
\mathl{n^{\prime \prime \ldots \prime}}{} mit $k$ Nachfolgerstrichen. Wenn umgekehrt
\mavergleichskettedisp
{\vergleichskette
{n }
{ =} {0 }
{ } { }
{ } { }
{ } { }
} {}{}{} ist, so ist der $k$-te Nachfolger der $0$ gleich $k$. Man beachte, dass hier die Addition in einer Weise definiert wird, in der die Kommutativität keineswegs offensichtlich ist, das wird sich aber gleich ergeben.






\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Addition Table.eps} }
\end{center}
\bildtext {Das \stichwort {kleine Einsundeins} {.} Das Umlegungsprinzip schlägt sich in der Additionstabelle darin nieder, dass in den Linksunten nach Rechtsoben-Diagonalen konstante Werte stehen.} }

\bildlizenz { Addition Table.svg } {} {Indolences} {Commons} {CC-by-sa 3.0} {}





\inputfaktbeweis
{Natürliche Zahlen/Addition mit n/Nachfolgerzählen/Hilfseigenschaften/Fakt}
{Lemma}
{}
{

\faktsituation {Für die Addition der natürlichen Zahlen \zusatzklammer {mit der in Definition 8.10 festgelegten Addition} {} {}}
\faktuebergang {gelten die folgenden Aussagen.}
\faktfolgerung {\aufzaehlungfuenf{
\mavergleichskettedisp
{\vergleichskette
{n+0 }
{ =} {n }
{ =} {0+n }
{ } { }
{ } { }
} {}{}{} für alle $n$, d.h. $0$ ist das \definitionsverweis {neutrale Element}{}{} der Addition. }{
\mavergleichskettedisp
{\vergleichskette
{n+k' }
{ =} {(n+k)' }
{ =} {n' +k }
{ } { }
{ } { }
} {}{}{} für alle $n,k \in \N$ \zusatzklammer {\stichwort {Umlegungsregel} {}} {} {.} }{Die Addition ist \definitionsverweis {kommutativ}{}{.} }{Die Addition ist \definitionsverweis {assoziativ}{}{.} }{Aus einer Gleichung
\mavergleichskette
{\vergleichskette
{n+k }
{ = }{m+k }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} folgt
\mavergleichskettedisp
{\vergleichskette
{n }
{ =} {m }
{ } { }
{ } { }
{ } { }
} {}{}{} \zusatzklammer {\stichwort {Abziehregel} {}} {} {.} }}
\faktzusatz {}
\faktzusatz {}

}
{

\aufzaehlungfuenf{Die Gleichungen links und rechts sind unmittelbar klar, da der $n$-te Nachfolger der $0$ gleich $n$ ist. }{Die Ausdrücke besagen prozesstheoretisch das gleiche: Links geht man von der Zahl $n$ aus und nimmt einmal öfters als $k$-mal den Nachfolger. In der Mitte bestimmt man $k$-fach den Nachfolger von $n$ und nimmt von diesem Ergebnis den Nachfolger. Rechts nimmt man von $n$ den Nachfolger und davon dann $k$-fach den Nachfolger. }{Es ist
\mavergleichskettedisp
{\vergleichskette
{n+k }
{ =} {k+n }
{ } { }
{ } { }
{ } { }
} {}{}{} für alle $k,n$ zu zeigen. Diese Gleichungen zeigen wir durch Induktion über $k$ für alle $n$. Bei
\mavergleichskette
{\vergleichskette
{k }
{ = }{0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} steht beidseitig $n$ nach Teil (1). Sei die Gleichheit nun für ein $k$ \zusatzklammer {und alle $n$} {} {} schon bewiesen. Dann ist unter Verwendung der Induktionsvoraussetzung und Teil (2)
\mavergleichskettedisp
{\vergleichskette
{n+k^\prime }
{ =} { (n+k)^\prime }
{ =} { (k+n)^\prime }
{ =} { k^\prime + n }
{ } { }
} {}{}{,} die Gleichung gilt also auch für $k^\prime$. }{Wir beweisen die Assoziativität, also die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{(m+n) + k }
{ =} { m+ (n+k) }
{ } { }
{ } { }
{ } { }
} {}{}{,} durch Induktion über $k$ \zusatzklammer {für alle
\mathl{m,n}{} gleichzeitig} {} {.} Mit der Regel aus (2) und der Induktionsvoraussetzung ergibt sich direkt
\mavergleichskettedisp
{\vergleichskette
{(m+n)+k^\prime }
{ =} { (m+n)^\prime +k }
{ =} { (m+n^\prime) + k }
{ =} { m +(n^\prime +k) }
{ =} { m+ (n+k^\prime) }
} {}{}{.} }{Die Abziehregel beweisen wir ebenfalls durch Induktion über $k$. Der Fall
\mavergleichskettedisp
{\vergleichskette
{k }
{ =} {0 }
{ } { }
{ } { }
{ } { }
} {}{}{} ist klar. Sei also die Aussage für ein $k$ schon bewiesen und sei eine Gleichung der Form
\mavergleichskettedisp
{\vergleichskette
{m+k^\prime }
{ =} {n + k^\prime }
{ } { }
{ } { }
{ } { }
} {}{}{} gegeben. Dann ist nach der Umlegungsregel auch
\mavergleichskettedisp
{\vergleichskette
{m^\prime +k }
{ =} {n^\prime +k }
{ } { }
{ } { }
{ } { }
} {}{}{.} Nach der Induktionsvoraussetzung ist somit
\mavergleichskettedisp
{\vergleichskette
{m^\prime }
{ =} {n^\prime }
{ } { }
{ } { }
{ } { }
} {}{}{.} Da die Nachfolgerabbildung \definitionsverweis {injektiv}{}{} ist, ergibt sich
\mavergleichskettedisp
{\vergleichskette
{m }
{ =} {n }
{ } { }
{ } { }
{ } { }
} {}{}{.} }

}


Für einige alternative Begründungen siehe die Aufgaben. Teil (2) kann man auch so verstehen, dass man eine Summe
\mathl{n+k}{} dadurch berechnen kann, dass man sukzessive den ersten Summanden um eins erhöht \zusatzklammer {also den Nachfolger nimmt} {} {} und den zweiten um eins vermindert \zusatzklammer {also den Vorgänger nimmt} {} {,} falls
\mavergleichskette
{\vergleichskette
{k }
{ \neq }{0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ist. Dies macht man so lange, bis der zweite Summand $0$ ist. Der dabei entstandene neue erste Summand ist die Summe. Statt Umlegungsregel sagt man auch \stichwort {Umlegungsprinzip} {} oder man spricht von einer \anfuehrung{gegensinnigen Veränderung}{,} was auch oft bei Rechnungen effektiv eingesetzt wird, wenn man etwa
\mavergleichskette
{\vergleichskette
{19+41 }
{ = }{20+40 }
{ = }{60 }
{ }{ }
{ }{ }
} {}{}{} rechnet. Die folgende Aussage besagt, dass durch das Umlegungsprinzip die Addition bereits festgelegt ist.





\inputfaktbeweis
{Natürliche Zahlen/Eindeutigkeit der Addition/Fakt}
{Satz}
{}
{

\faktsituation {Auf den \definitionsverweis {natürlichen Zahlen}{}{}}
\faktfolgerung {gibt es genau eine \definitionsverweis {Verknüpfung}{}{} \maabbeledisp {} {\N \times \N} {\N } {(x,y)} { x+y } {,} mit
\mathdisp {x+0=x \text { für alle } x \in \N \text{ und } x+y' =(x+y)' \text { für alle } x,y \in \N} { . }
}
\faktzusatz {}
\faktzusatz {}

}
{

Die Addition erfüllt nach Lemma 8.11  (1, 2) diese Eigenschaften.

Es seien zwei Verknüpfungen \mathkor {} {+} {und} {*} {} auf $\N$ gegeben, die beide diese charakteristischen Eigenschaften erfüllen. Es ist zu zeigen, dass dann diese beiden Verknüpfungen überhaupt übereinstimmen. Wir müssen also die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{x +y }
{ =} {x *y }
{ } { }
{ } { }
{ } { }
} {}{}{} für alle
\mathl{x,y \in \N}{} beweisen. Dies machen wir durch Induktion über $y$ \zusatzklammer {für beliebige $x$} {} {.} Bei
\mavergleichskettedisp
{\vergleichskette
{y }
{ =} {0 }
{ } { }
{ } { }
{ } { }
} {}{}{} ist wegen
\mavergleichskettedisp
{\vergleichskette
{x+0 }
{ =} {x }
{ =} {x*0 }
{ } { }
{ } { }
} {}{}{} die Aussage richtig. Sei die Aussage nun für ein bestimmtes $y$ schon bewiesen. Dann ist mit der charakteristischen Eigenschaft und der Induktionsvoraussetzung
\mavergleichskettedisp
{\vergleichskette
{x+y^\prime }
{ =} { (x+y)^\prime }
{ =} { (x*y)^\prime }
{ =} { x * y^\prime }
{ } { }
} {}{}{.}

}






\zwischenueberschrift{Addition und disjunkte Vereinigung}






\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Commutative Addition.eps} }
\end{center}
\bildtext {Das Vereinigungsprinzip und die Kommutativität der Addition} }

\bildlizenz { Commutative Addition.svg } {} {Weston.pace~commonswiki} {Commons} {CC-by-sa 2.5} {}

Die Standardinterpretation der und wichtigste Motivation für die Addition zweier natürlicher Zahlen ist, dass sie die Anzahl der Vereinigung von zwei disjunkten endlichen Mengen angibt. Wenn man zwei Körbe von Äpfeln hat und diese zusammenschüttet, so ist die Gesamtanzahl gerade die Summe der beiden Einzelanzahlen. Es ist möglich, die Addition von natürlichen Zahlen darüber zu definieren. Vorteile sind die unmittelbare Anschauung, Nachteile, dass man eine Zahl durch eine endliche Menge repräsentieren muss, und nicht klar ist, welche man nehmen soll und es nicht selbstverständlich ist, dass unterschiedliche gleichgroße disjunkte Mengen nach Vereinigung gleichgroß sind \zusatzklammer {was heißt das} {?} {.} Der Vorteil bei unserer Definition ist, dass man die Addition auf einen elementareren Prozess, nämlich den Prozess des Zählens bzw. Nachfolgernehmens zurückführt. Dies erlaubt es, Gesetzmäßigkeiten zu beweisen, indem sie per Induktion auf elementare Schritte zurückgeführt werden. Beide Konzepte sind wichtig, und natürlich will man, unabhängig davon, wie man die Addition nun eingeführt hat, schnell wissen, dass die beiden Konzepte übereinstimmen. Dazu ist es hilfreich, im Vereinigungskonzept auch Einzelschritte zu erkennen. Dies ist wieder das Umlegungsprinzip: Die Vereinigung kann man sich so vorstellen, dass schrittweise ein Element \zusatzklammer {ein Apfel} {} {} der zweiten Menge in die erste Menge umgelegt wird, siehe auch Aufgabe 4.13 und Aufgabe *****.

Bei einem solchen Einzelschritt erhöht sich die erste Anzahl um eins \zusatzklammer {Nachfolger} {} {} und die zweite Anzahl verringert sich um eins \zusatzklammer {Vorgänger} {} {.} Das deckt sich mit Lemma 8.11  (2).





\inputfaktbeweis
{Natürliche Zahlen/Nachfolger/Addition und disjunkte Vereinigung/Fakt}
{Satz}
{}
{

\faktsituation {Es seien \mathkor {} {M} {und} {N} {} \definitionsverweis {disjunkte}{}{} \definitionsverweis {endliche Mengen}{}{} mit \mathkor {} {m} {bzw.} {n} {} Elementen.}
\faktfolgerung {Dann besitzt ihre \definitionsverweis {Vereinigung}{}{}
\mathl{M \cup N}{} gerade
\mathl{m+n}{} Elemente.}
\faktzusatz {}
\faktzusatz {}

}
{

Die Voraussetzung besagt, dass es eine \definitionsverweis {bijektive Abbildung}{}{} \maabbdisp {\psi} {\{ 1 , \ldots , m \} } {M } {} und eine bijektive Abbildung \maabbdisp {\varphi} {{ \{ 1 , \ldots , n \} } } {N } {} gibt. Die Abbildung \maabbeledisp {} {{ \{ 1 , \ldots , n \} }} { \{m+1 , \ldots , m+n\} } {i} {m+i } {,} ist nach Aufgabe 8.24 bijektiv, sei $\theta$ die \definitionsverweis {Umkehrabbildung}{}{.} Somit ist nach Lemma 6.4  (3) \maabbdisp {\varphi \circ \theta} { \{m+1 , \ldots , m+n\} } { N } {} ebenfalls bijektiv. Wir definieren nun eine Abbildung \maabbdisp {F} {\{1 , \ldots , m+n\}} { M \cup N } {} durch
\mavergleichskettedisp
{\vergleichskette
{ F(k) }
{ =} { \begin{cases} \psi(k), \text{ falls } k \in \{ 1 , \ldots , m \} \, , \\ \varphi( \theta(k)) , \text{ falls } k \in \{m+1 , \ldots , m+n \} \, . \end{cases} }
{ } { }
{ } { }
{ } { }
} {}{}{} Diese Abbildung ist \definitionsverweis {surjektiv}{}{,} da jedes Element aus $M$ durch den ersten Fall und jedes Element aus $N$ durch den zweiten Fall abgedeckt ist. Die Injektivität sieht man so. Wenn
\mavergleichskettedisp
{\vergleichskette
{k }
{ \neq} { \ell }
{ } { }
{ } { }
{ } { }
} {}{}{} gegeben sind, und das eine Element zu
\mathl{\{ 1 , \ldots , m \}}{} und das andere zu
\mathl{\{m+1 , \ldots , m+n \}}{} gehört, so ist
\mathl{F(k) \in M}{} und
\mathl{F(\ell) \in N}{} \zusatzklammer {oder umgekehrt} {} {} und sie sind verschieden wegen der Disjunktheit von \mathkor {} {M} {und} {N} {.} Wenn hingegen \mathkor {} {k} {und} {\ell} {} aus der gleichen Teilmenge des Definitionsbereiches kommen, so ergibt sich die Verschiedenheit von \mathkor {} {F(k)} {und} {F(\ell)} {} aus der Injektivität von $\psi$ bzw. von $\varphi \circ \theta$. Insgesamt erhalten wir also eine bijektive Abbildung \maabbdisp {} {\{1 , \ldots , m+n\} } { M \cup N } {,} so dass die Anzahl von
\mathl{M \cup N}{} gleich
\mathl{m+n}{} ist.

}

Später werden wir beweisen, dass die Addition mit dem schriftlichen Addieren ausgerechnet werden kann, dass also der Algorithmus des schriftlichen Addierens korrekt ist.



<< | Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)