\section{Grundlegendes}


\subsection{Vollst"andige Induktion und binomische Formel}
\begin{Satz}\label{ErFa} F"ur jede nat"urliche Zahl $n\geq 1$ gilt
$1+2+\ldots +n = \frac{n(n+1)}{2}$.
\end{Satz}
\begin{Beispiel}
Im Fall $n=5$ behauptet unser Satz  $1+2+3+4+5=5\times 6/2$ und in
diesem Fall stimmt das schon mal: Beide Seiten sind $15$. 
Man bemerke, da"s wir beim Rechnen mit Symbolen wie
etwa $ n(n+1)$
die Multiplikationssymbole weggelassen haben, die nur beim Rechnen mit
durch Ziffern dargestellten Zahlen  wichtig sind. 
\end{Beispiel}
\begin{proof}[Beweis]
Bei diesem Beweis sollen Sie gleichzeitig das 
Beweisprinzip der {\bf voll\-st"andigen
Induktion}\index{Induktion, vollst"andige} lernen.
Wir bezeichnen mit $A(n)$ die Aussage, da"s die Formel im Satz 
f"ur ein gegebenes $n$ gilt, und zeigen:
\begin{description}
\item[Induktionsbasis:]\index{Induktion, vollst"andige!Induktionsbasis}
Die Aussage $A(1)$ ist richtig. In der Tat gilt 
 $1= \frac{1(1+1)}{2}$.
\item[Induktionsschritt:]\index{Induktion, vollst"andige!Induktionsschritt}
Aus der Aussage 
$A(n)$ folgt die Aussage 
$A(n+1)$. In der Tat, unter der Annahme, da"s unsere Formel
f"ur ein gegebenes $n$ gilt, der sogenannten 
{\bf Induktionsannahme}\index{Induktion, vollst"andige!Induktionsannahme} oder
{\bf Induktionsvoraussetzung}\index{Induktion, vollst"andige!Induktionsvoraussetzung}, 
rechnen wir
$$\begin{array}{rcl}
1+2+\ldots + n + (n+1) &= &\frac{n(n+1)}{2} + \frac{2(n+1)}{2}\\[2mm]
&=& \frac{(n+2)(n+1)}{2}\\[2mm]
&=& \frac{(n+1)((n+1)+1)}{2}
\end{array}$$
und folgern so, da"s die Formel auch f"ur $n+1$ gilt.
\end{description}
Es ist damit klar, da"s unsere Aussage
$A(n)$ richtig ist alias da"s unsere Formel  
gilt f"ur alle $n = 1,2,3,$ \dots
\end{proof}
\begin{Bemerkungl}
  Das Zeichen $\qedsymbol$\index{)0a@$\qedsymbol$ Beweisende}  
 deutet in diesem Text  das Ende eines Beweises an
und ist in der neueren Literatur weit verbreitet. 
Buchstaben in Formeln
 werden in der
Mathematik "ublicherweise kursiv notiert, so wie etwa 
das $n$ oder auch das $A$ im
vorhergehenden Beweis. Nur Buchstaben oder Buchstabenkombinationen,
die stets dasselbe bedeuten sollen, schreibt man nicht kursiv,
wie etwa $\op{sin}$ f"ur den Sinus oder $\op{log}$
f"ur den Logarithmus. 
\end{Bemerkungl}
\begin{Bemerkungl}
Der vorhergehende
Beweis st"utzt sich auf unser intuitives Verst"andnis der nat"urlichen
Zahlen.
Man kann das Konzept der nat"urlichen Zahlen auch formal einf"uhren
und so die nat"urlichen Zahlen in gewisser Weise \glqq besser\grqq\  verstehen. 
Das wird in \eref{DNZZ}{GR} und ausf"uhrlicher in 
\eref{Nhoc}{LA1} diskutiert. 
Das Wort \glqq Induktion\grqq\  meint eigentlich \glqq Hervorrufen\grqq,
so wie etwa das Betrachten einer Wurst die Aussch"uttung von Spucke induziert 
alias uns den Mund w"assrig macht. Im Zusammenhang der 
vollst"andigen Induktion ist es dahingehend zu verstehen, da"s die
Richtigkeit unserer Aussage $A(1)$ die Richtigkeit von $A(2)$ 
induziert, die Richtigkeit von $A(2)$ hinwiederum die Richtigkeit 
von $A(3)$, die Richtigkeit von $A(3)$  die Richtigkeit 
von $A(4)$, und immer so weiter. 
\end{Bemerkungl}

\begin{Bemerkungl}
Es herrscht keine Einigkeit in der Frage, ob 
man die Null eine nat"urliche Zahl nennen soll. In diesem Text
ist stets die Null mit gemeint, wenn von nat"urlichen
Zahlen die Rede ist. Wollen wir die Null dennoch ausschlie"sen, 
so sprechen wir wie oben von einer
  \glqq nat"urlichen Zahl $n\geq 1$\grqq.
\end{Bemerkungl}
  

\begin{Bemerkungl}
  Ich will kurz begr"unden, warum es mir nat"urlich scheint, auch die Null 
eine nat"urliche Zahl zu nennen:
  Hat bildlich gesprochen jedes Kind einer Klasse einen Korb mit "Apfeln vor
  sich und soll seine "Apfel z"ahlen, so kann es ja 
durchaus vorkommen, da"s in
  seinem Korb gar kein Apfel liegt, weil es zum Beispiel alle seine "Apfel
  bereits gegessen hat.  In der Begrifflichkeit der Mengenlehre ausgedr"uckt,
  die wir in \ref{Menga} einf"uhren werden, mu"s man die leere Menge endlich
  nennen, wenn man erreichen will, da"s 
jede Teilmenge einer endlichen Menge wieder endlich ist.  Will
  man dann zus"atzlich 
erreichen, da"s die Kardinalit"at jeder endlichen Menge eine
  nat"urliche Zahl ist, so darf man die Null nicht aus den nat"urlichen Zahlen
  herauslassen.
\end{Bemerkungl}
\begin{figure}[htb]
\begin{minipage}{0.45\textwidth}
  \includegraphics[width=\textwidth]{SkriptenBilder/Bild0003}
\end{minipage}\hfill
 \begin{minipage}{0.45\textwidth}\centering
Die Gesamtfl"ache dieses Treppenquerschnitts ist offensichtlich
$$4^2/2+4/2=4\cdot 5/2=10$$
\end{minipage}
\end{figure}
\begin{Bemerkungl}\label{SSFa}
Man kann sich den Satz  wie im Bild angedeutet anschaulich   
klar machen als eine Formel f"ur die Fl"ache des Querschnitts
durch eine Treppe der L"ange $n$ mit Stufenabstand und Stufenh"ohe Eins.
In der Tat bedeckt 
ein derartiger Querschnitt 
ja offensichtlich ein halbes Quadrat der Kantenl"ange $n$ nebst
$n$ halben Quadraten der Kantenl"ange Eins.
Ein weiterer Beweis geht so:
$$\begin{array}{rcrlccc}
1 + 2 + 3+\ldots +n&=&1/2 &+ \;\;\;\; 2/2 &+\;\;\;\; 3/2 &+ \ldots &+\; n/2 \\
&&+ \; n/2 &+ (n-1)/2& + (n-2)/2& + \ldots &+\; 1/2\\[2mm]
&=& \frac{n+1}{2} &+ \;\;\;\; \frac{n+1}{2}&+ \;\;\;\; \frac{n+1}{2}& + \ldots &+\; \frac{n+1}{2}\\[2mm]
& = & n(n+1)/2 \hspace{-1cm}&& &  &
\end{array}$$
Ich will letzteren Beweis benutzen, um eine neue Notation einzuf"uhren.
\end{Bemerkungl}
\begin{Definition}
Gegeben $a_{1},a_{2},\ldots , a_{n}$ schreiben wir
$$\sum^{n}_{i=1} a_{i} \pdef a_{1}+a_{2}+ \ldots + a_{n}$$
Das Symbol $\sum$ ist ein gro"ses griechisches S und steht f"ur \glqq Summe\grqq.
Das Symbol 
$\pdef$\index{)8@$\pdef$ ist definiert durch}\index{)8@$\defp$ wird definiert als} 
deutet an, da"s die Bedeutung der\label{Summa}  
Symbole auf der doppelpunktbehafteten  Seite des Gleichheitszeichens
 durch den Ausdruck auf der  anderen Seite unseres Gleichheitszeichens
definiert ist.
Im obigen und "ahnlichen\index{S@$\sum$ Summe!von Zahlen}\index{)9@$\sum$ Summe!von Zahlen}
Zusammenh"angen hei"sen
$a_1,\ldots, a_n$   die \defind{Summanden} und $i$  der
\defind{Laufindex}, da er eben etwa in unserem Fall von $1$ bis $n$
l"auft und anzeigt alias \glqq indiziert\grqq, welcher Summand gemeint ist. 
\end{Definition}
\begin{Bemerkungl}[\textbf{Zur Sprache in der Mathematik}]
Das Wort \glqq Definition\grqq\   kommt\index{Definition}  aus dem
Lateinischen und bedeutet  \glqq Abgrenzung\grqq. In 
Definitionen versuchen wir, die Bedeutung von  Symbolen und Begriffen
so klar wie m"oglich festzulegen. Sie werden merken, da"s 
man in der Mathematik die Angwohnheit hat, in Definitionen
Worte der Umgangssprache wie Menge, Gruppe, K"orper,
Unterk"orper, Abbildung etcetera \glqq umzuwidmen\grqq\  und ihnen ganz spezielle und
meist nur noch entfernt mit der umgangssprachlichen Bedeutung verwandte
neue Bedeutungen zu geben. In mathematischen Texten sind dann 
"uberwiegend diese umgewidmeten Bedeutungen gemeint. In dieser Weise
baut die Mathematik also wirklich ihre eigene Sprache auf, bei der
jedoch die Grammatik und auch nicht ganz wenige W"orter 
doch wieder von den uns gel"aufigen
Sprachen "ubernommen werden. 
Das mu"s insbesondere f"ur den Anf"anger verwirrend sein, der sich auch
bei ganz harmlos daherkommenden W"ortern stets wird fragen 
m"ussen, ob sie denn nun 
umgangssprachlich gemeint sind oder vielmehr bereits durch eine 
Definition auf eine mehr oder weniger andere
und viel genauere Bedeutung festgelegt wurden.
Um hier zu helfen, habe ich mir
gro"se M"uhe mit dem Index gegeben, den Sie ganz am Schlu"s dieses Skriptums
finden
und in dem alle  
an verschiedenen Stellen eingef"uhrten oder umgewidmeten 
und dort fett gedruckten 
Begriffe verzeichnet sein sollten.
Und an dieser Stelle  mu"s ich Sie schon bitten, das Wort \glqq Index\grqq\ 
 nicht als Laufindex mi"szuverstehen!
\end{Bemerkungl}
\begin{Beispiel}
In der $\sum$-Notation liest sich der in \ref{SSFa} gegebene Beweis so:
$$\begin{array}{lcl}
\sum^{n}_{i=1} i
& =& \sum^{n}_{i=1} \frac{i}{2} + \sum^{n}_{i=1} \frac{i}{2}\\[2mm]
&&\text{und nach Indexwechsel $i=n+1-k$ hinten}\\
& =& \sum^{n}_{i=1} \frac{i}{2} + \sum^{n}_{k=1} \frac{n+1-k}{2}\\[2mm]
&&\text{dann mache  $k$ zu $i$ in der zweiten Summe}\\
& =& \sum^{n}_{i=1} \frac{i}{2} + \sum^{n}_{i=1} \frac{n+1-i}{2}\\[2mm]
&&\text{und nach  Zusammenfassen beider Summen}\\
& =& \sum^{n}_{i=1} \frac{n+1}{2}\\[2mm]
&&\text{ergibt sich offensichtlich}\\
&=& n(\frac{n+1}{2})
\end{array}$$
\end{Beispiel}

 \begin{Beispiel}
 Einen anderen Beweis derselben Formel liefert
die  Gleichungskette:
$$(n+1)^2=\sum_{i=0}^{n}(i+1)^2-i^2=\sum_{i=0}^{n}2i +1
=2\sum_{i=0}^{n}i +\sum_{i=0}^{n}1=n+1+2\sum_{i=0}^{n}i $$
 \end{Beispiel}
\begin{Definition}
  In einer "ahnlichen Bedeutung wie das Symbol
  $\sum$ verwendet man auch 
das Symbol $\prod$,\index{P@$\prod$ Produkt!von Zahlen} ein gro"ses\index{)9@$\prod$ Produkt!von Zahlen}
griechisches $P$, f"ur \glqq Produkt\grqq\  und
schreibt $$\prod^{n}_{i=1} a_{i}\pdef a_{1}a_{2}\ldots a_{n}$$  
Die  $a_1,\ldots, a_n$ hei"sen in diesem und "ahnlichen
Zusammenh"angen die \defind{Faktoren} des Produkts.
\end{Definition}


\begin{Definition}
F"ur jede nat"urliche Zahl $n\geq 1$ definieren wir die Zahl
$n!$ (sprich: $n$ {\bf Fakult"at})\index{Fakult"at}  
\index{)0b@$n~!$ Fakult"at} durch 
die Formel
$$n! \pdef 1\cdot 2 \cdot\ldots \cdot n  = \prod^{n}_{i=1} i$$
Wir treffen zus"atzlich
die Vereinbarung
$0! \pdef 1$ und haben also 
$0! =1$, $1!=1$, $2!=2$, $3! = 6$, $4!=24$ und so weiter.
\end{Definition}
\begin{Bemerkungl}[\textbf{Allgemeinere Summen und Produkte}] 
Wir vereinbaren, da"s Produkten,\label{LPSa} 
bei denen die obere Grenze des Laufindex 
um Eins kleiner ist als seine untere Grenze, 
der Wert $1$ zugewiesen werden soll,
also etwa  $1=\prod^{0}_{i=1} i=0!$.
Ebenso vereinbaren wir auch, da"s 
Summen, bei denen die obere Grenze des Laufindex 
um Eins kleiner ist als seine untere Grenze, 
der Wert $0$ zugewiesen werden soll, so da"s wir in Erweiterung unserer Formel
\ref{ErFa} etwa schreiben k"onnten
$0=\sum^{0}_{i=1} i$. Der Sinn dieser Erweiterungen zeigt sich darin,
da"s damit Formeln wie $\sum_{i=k}^la_i=\sum_{i=k}^ma_i+\sum_{i=m+1}^la_i$
auch f"ur $m=k-1$ richtig bleiben. Man mag sogar noch weiter gehen 
und die Definition von Summen und Produkten
auf beliebige untere und obere Grenzen
so erweitern, da"s  diese Formeln richtig bleiben, zumindest wenn alle
Summanden ein Negatives beziehungsweise alle Faktoren einen Kehrwert haben. In dieser Allgemeinheit
ist die fragliche Notation jedoch nur beim kontinuierlichen Analogon
$\int$ des Summenzeichens "ublich, wie in \ref{IGV} ausgef"uhrt
werden wird.
\end{Bemerkungl}
\begin{Satz}[\textbf{Bedeutung der Fakult"at}]\label{BFaa}
Es gibt
genau 
$n!$  M"oglichkeiten, $n$  
voneinander verschiedene Objekte in eine Reihenfolge zu
bringen.  
\end{Satz}
\begin{Beispiel}
Es gibt genau $3! = 6$ M"oglichkeiten, die drei
Buchstaben $a,b$ und $c$ in eine Reihenfolge zu bringen, n"amlich
$$\begin{array}{ccc}
abc & bac & cab \\
acb & bca & cba
\end{array}$$  In gewisser Weise stimmt unser Satz sogar f"ur $n=0$:
In der Terminologie, die wir in \ref{OM} einf"uhren, gibt es 
 genau
eine Anordnung der leeren Menge.  
\end{Beispiel}
\begin{proof}
Hat man  $n$ voneinander verschiedene Objekte, so hat man $n$ M"oglichkeiten,
ein Erstes auszusuchen, dann $(n-1)$ M"oglichkeiten, ein Zweites
auszusuchen und so weiter, bis schlie"slich nur noch eine
M"oglichkeit bleibt, ein Letztes auszusuchen.
Insgesamt haben wir also wie behauptet $n!$ m"ogliche
Reihenfolgen. 
\end{proof}
\begin{Definition}\label{BiKoea}
Wir definieren  f"ur beliebiges $n$ und jede nat"urliche Zahl $k$
den {\bf Binomialkoeffizienten}\index{Binomialkoeffizienten} ${n \choose k}$
(sprich: $n$ {\bf "uber} $k$)\index{)5)@${n \choose k}$ Binomialkoeffizient}
 durch die Regeln
$${n \choose k} \pdef \prod^{k-1}_{j=0} \frac{n-j}{k-j} =
\begin{array}{rc}
n (n-1) \ldots &(n-k+1)\\
\hline
k(k-1)\ldots& 1\end{array}\;
\text{ f"ur $k\geq 1$ und } {n \choose 0}\pdef 1.$$  
Der Sonderfall $k=0$ wird im "Ubrigen auch durch unsere 
allgemeine Formel gedeckt, wenn wir unsere Konvention \ref{LPSa} 
beherzigen.
Im Lichte des folgenden Satzes schlage ich vor, die Binomialkoeffizienten
${n\choose k}$ statt \glqq $n$ "uber $k$\grqq\  inhaltsreicher \glqq $k$ aus $n$\grqq\ 
zu sprechen.
\end{Definition}
\begin{Bemerkungl}
  Die  Bezeichnung als Binomialkoeffizienten
leitet sich von dem Auftreten 
dieser Zahlen als Koeffizienten in der
 \glqq binomischen Formel\grqq\  \ref{BiFoAa} ab.
\end{Bemerkungl}

\begin{Satz}[\textbf{Bedeutung der Binomialkoeffizienten}]
Gegeben  na\-t"urliche Zahlen\label{BBKa} $n$ und $k$ 
gibt es genau ${n \choose k}$ M"oglichkeiten, aus 
$n$ voneinander verschiedenen Objekten  $k$ Objekte  auszuw"ahlen.
\end{Satz}
\begin{Beispiel}
Es gibt genau ${4 \choose 2} = \frac{4\cdot 3}{2\cdot 1} =6 $
M"oglichkeiten, aus den vier Buchstaben $a,b,c,d$ zwei auszuw"ahlen,
n"amlich
$$\begin{array}{lll}
a,b \;& b,c \;& c,d \\
a,c & b,d &  \\
a,d & &
\end{array}$$
\end{Beispiel}


\begin{proof}[Beweis]
Wir haben $n$ M"oglichkeiten, ein erstes Objekt auszuw"ahlen, dann
$n-1$ M"oglichkeiten, ein zweites Objekt auszuw"ahlen, und so weiter, 
also insgesamt $n(n-1)
\ldots (n-k+1)$ M"oglichkeiten, $k$ Objekte {\em der Reihe nach}
auszuw"ahlen. Auf die Reihenfolge, in der wir
ausgew"ahlt haben, kommt es uns aber gar nicht an, 
jeweils genau $k!$ von
unseren $n(n-1) \ldots (n-k+1)$ M"oglichkeiten f"uhren 
nach \ref{BFaa}  also zur Auswahl
derselben $k$ Objekte.
Man bemerke, da"s unser Satz auch im Extremfall $k=0$ noch stimmt, wenn wir
ihn geeignet interpretieren: In der Terminologie, die wir gleich einf"uhren
werden, besitzt in der Tat jede Menge genau eine
nullelementige Teilmenge, n"amlich die leere Menge. 
\end{proof} 
\begin{Bemerkungl}
Offensichtlich gilt f"ur alle nat"urlichen 
Zahlen $n$ mit $n\geq k$ die Formel
$${n\choose k} = \frac{n!}{k!(n-k)!} = {n\choose n-k}$$
Das folgt einerseits sofort aus der formalen Definition
und ist andererseits auch klar nach der oben erkl"arten Bedeutung der
Binomialkoeffizienten: Wenn wir aus $n$ Objekten $k$ Objekte 
ausw"ahlen, so bleiben $n-k$ Objekte "ubrig. Es gibt demnach gleichviele 
M"oglichkeiten, $k$ Objekte 
auszuw"ahlen, wie es M"oglichkeiten gibt, $n-k$ Objekte auszuw"ahlen.
Wir haben weiter ${n\choose n} = {n\choose 0} =1$ f"ur jede 
nat"urliche Zahl $n\geq 0$
sowie
${n \choose 1}= {n\choose n-1} = n$ f"ur jede nat"urliche Zahl $n\geq 1$. 
\end{Bemerkungl}
\begin{Definition}
  Wie in der Schule setzen wir $a^k\pdef\prod_{i=1}^{k} a$\index{)8bb@$a^k$ Potenz} und sprechen diesen
  usdruck \glqq $a$ hoch $k$\grqq. In Worten 
ist also gemeint \glqq das Produkt von $k$-mal dem Faktor $a$\grqq.  
Im Lichte von \ref{LPSa} verstehen wir insbesondere $a^0\pdef 1$.  
\end{Definition}

\begin{Satz} F"ur jede nat"urliche Zahl $n$ gilt\label{BiFoAa}
die {\bf\em binomische Formel}\index{binomische Formel}
$$(a+b)^{n} = \sum^{n}_{k=0} {n\choose k} a^{k}b^{n-k}$$
\end{Satz}
\begin{Bemerkungl}
Man beachte, wie wichtig unsere Konvention
$a^0=1$ und insbesondere auch ihr Spezialfall $0^0=1$ f"ur die
G"ultigkeit dieser Formel ist. 
\end{Bemerkungl}
\begin{Bemerkungl}
Die Bezeichung 
\glqq binomische Formel\grqq\ 
leitet sich ab von der Vorsilbe \glqq bi\grqq\  f"ur Zwei,
wie etwa in englisch \glqq bicycle\grqq\  f"ur \glqq Zweirad\grqq\  alias \glqq Fahrrad\grqq,
und dem lateinischen Wort 
\glqq nomen\grqq\  f"ur \glqq Namen\grqq. Mit den beiden \glqq Namen\grqq\  sind hier  $a$ und
$b$ gemeint. Mehr dazu wird in \ref{WBPb} erkl"art.
\end{Bemerkungl}
\begin{proof}[Erster Beweis]
Beim Ausmultiplizieren
erhalten wir das Monom $a^k b^{n-k}$ so oft, wie es M"oglichkeiten gibt,
aus unseren $n$ Faktoren $(a+b)$ die $k$ Faktoren  auszusuchen,
\glqq in denen wir beim Ausmultiplizieren das $a$ nehmen\grqq. 
Dieses Argument werden wir in  \ref{PFBa}  
noch besser formulieren.
\end{proof}
\begin{proof}[Zweiter Beweis]
Dieser Beweis ist eine ausgezeichnete "Ubung im Umgang mit unseren Symbolen
und mit der vollst"andigen Induktion. 
Er scheint mir jedoch auch in einer f"ur Beweise durch 
vollst"andige Induktion typischen Weise wenig durchsichtig.
Zun"achst pr"ufen wir f"ur beliebiges $n$ und jede nat"urliche Zahl
$k\geq 1$ die Formel
$${n\choose k-1} + {n\choose k} = {n+1\choose k}$$
durch explizites Nachrechnen.
Dann geben wir unserer Formel im Satz den Namen $A(n)$ und pr"ufen
die Formel
$A(0)$ und zur Sicherheit auch noch $A(1)$ durch Hinsehen.
Schlie"slich gilt es, den Induktionsschritt durchzuf"uhren,
als da hei"st, $A(n+1)$ aus $A(n)$
zu folgern.
Dazu rechnen wir
$$\begin{array}{ccl}
(a+b)^{n+1} & =& (a+b) (a+b)^{n}\\[2mm]
&&\text{und mit der Induktionsvoraussetzung}\\
& =& (a+b) \sum^{n}_{k=0}{n\choose k} a^{k}b^{n-k}\\[2mm]
&&\text{und durch Ausmultiplizieren}\\
&=&\sum^{n}_{k=0}{n\choose k} a^{k+1}b^{n-k}+ \sum^{n}_{k=0} {n\choose k}
a^{k}b^{n-k+1}\\[2mm]
&&\text{und Indexwechsel $k=i-1$ in der ersten Summe}\\
&=&\sum^{n+1}_{i=1} {n\choose i-1}a^{i}b^{n-i+1}+ \sum^{n}_{k=0}
{n\choose k} a^{k}b^{n-k+1}\\[2mm]
&&\text{dann mit  $k$ statt $i$ 
und Absondern von Summanden}\\
&=& a^{n+1}b^{0} + \sum^{n}_{k=1}{n\choose k-1} a^{k}b^{n-k+1} +\\[2mm]
&&\hspace{13mm}+\sum^{n}_{k=1} \;{n\choose k}\; 
a^{k}b^{n-k+1} + a^{0}b^{n+1}\\[2mm]
&&\text{und nach Zusammenfassen der mittleren Summen}\\
&=& a^{n+1}b^{0} + \sum^{n}_{k=1} {n+1\choose k} a^{k}b^{n-k+1}+a^{0}
b^{n+1}\\[2mm]
&&\text{und Einbeziehen der abgesonderten Summanden}\\
&=& \sum^{n+1}_{k=0} {n+1\choose k} a^{k}b^{n+1-k}
\end{array}$$
und folgern so tats"achlich $A(n+1)$ aus $A(n)$.
\end{proof}
\begin{Bemerkungl}
Die Formel ${n\choose k-1} + {n\choose k} = {n+1\choose k}$ f"ur
$k \geq 1$ kann man zur effektiven Berechnung der Binomialkoeffizienten
mit dem sogenannten 
{\bf Pascal'schen Dreieck}\index{Pascal'sches Dreieck} benutzen:
Im Schema
$$\begin{array}{ccccccccc}
 & & & &1& & & &\\
 & & &1& &1& & &\\
 & &1& &2& &1& &\\
 &1& &3& &3& &1& \\
1& &4& &6& &4& &1
\end{array}$$
seien die Einsen an den R"andern vorgegeben und eine Zahl in der Mitte
berechne sich als die Summe ihrer beiden oberen \glqq Nachbarn\grqq. Dann stehen
in der $(n+1)$-ten Zeile der Reihe nach die Binomialkoeffizienten
${n\choose 0}=1, {n\choose 1}=n,  \ldots$, bis 
${n\choose n-1}=n, {n\choose n} =1$. Wir haben also zum Beispiel nach der untersten Zeile in obigem Ausschnitt des Pascal'schen Dreiecks 
$$(a+b)^4=a^4 + 4a^3b + 6 a^2b^2+ 4 ab^3+b^4\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$$
\end{Bemerkungl}
\subsubsection*{"Ubungen}

\begin{Ubung}
Man finde und beweise eine Formel f"ur $\sum^n_{i=1}i^2$.
Hinweis: Man suche zun"achst eine Formel f"ur $\sum^n_{i=1}i^3-(i-1)^3$
und beachte $i^3-(i-1)^3=3i^2-3i+1$.\label{SuQua}
\end{Ubung}

\begin{Ubunge}\label{SNUPOa} 
  Man zeige, da"s  f"ur jedes $k\in\DN$ eine Formel der Gestalt
$\sum^n_{i=1}i^k= \frac{1}{k+1}n^{k+1} +a_{k}n^k+\ldots + a_1 n + a_0$ gilt
mit $a_\kappa\in\DQ$.
\end{Ubunge}

\subsection{Mengen und Teilmengen}\label{Menga}
\begin{Bemerkungl}
  Beim Arbeiten mit reellen Zahlen oder r"aumlichen
Gebilden reicht auf der Schule ein intuitives
  Verst"andnis meist aus, und wenn die Intuition in die Irre f"uhrt, ist ein
  Lehrer zur Stelle.  Wenn Sie jedoch selbst unterrichten oder etwas beweisen
  wollen, reicht dieses intuitive Verst"andnis nicht mehr aus.  Im
    folgenden werden deshalb zun"achst der Begriff der reellen Zahlen
und der Begriff des Raums
    zur"uckgef"uhrt auf Grundbegriffe der Mengenlehre, den Begriff der
    rationalen Zahlen und elementare Logik.  Bei der Arbeit mit diesen
  Begriffen f"uhrt uns die Intuition nicht so leicht in die Irre, wir geben uns
  deshalb mit einem intuitiven Verst"andnis zufrieden und verweisen jeden, der
  es noch genauer wissen will, auf eine Vorlesung "uber Logik.  
Wir beginnen mit
  etwas naiver Mengenlehre, wie sie von Georg Cantor in den Jahren
1874 bis 1897 begr"undet wurde und von der der ber"uhmte Mathematiker 
David Hilbert einmal sagte:
\glqq Aus dem Paradies, das Cantor uns geschaffen, 
soll uns niemand vertreiben k"onnen\grqq. Nat"urlich gab es auch vor der 
Mengenlehre schon hoch entwickelte Mathematik: Beim Tod 
von Carl Friedrich Gau"s im Jahre 1855 gab es diese Theorie noch gar 
nicht und Fourier fand
seine \glqq Fourierentwicklung\grqq\  sogar bereits zu Beginn des 19.-ten Jahrhunderts. 
Er behauptete auch gleich in seiner \glqq Th\'{e}orie analytique de la chaleur\grqq,
da"s sich jede beliebige periodische Funktion durch eine  
Fouriereihe darstellen lasse, aber diese Behauptung stie"s
bei anderen ber"uhmten Mathematikern seiner Zeit auf Ablehnung
und es entstand dar"uber ein heftiger Disput. Erst in besagtem \glqq Paradies der
Mengenlehre\grqq\  konnten die Fourier's Behauptung 
zugrundeliegenden Begriffe soweit
 gekl"art werden, da"s dieser Disput nun  endg"ultig beigelegt ist.
"Ahnlich verh"alt es sich auch mit vielen anderen Fragestellungen.
Da die Mengenlehre dar"uber hinaus auch 
vom didaktischen Standpunkt aus eine "au"serst klare 
und durchsichtige Darstellung mathematischer Sachverhalte erm"oglicht,
hat sie sich als Grundlage der h"oheren Mathematik und der 
Ausbildung von Mathematikern an Universit"aten 
schnell durchgesetzt
und ist nun weltweit das \glqq Alphabet
der Sprache der Mathematik\grqq.
Man wird  an Universit"aten sogar 
geradezu dazu erzogen, alle Mathematik in der Sprache der
Mengenlehre zu fassen und geometrischen Argumenten
keine Beweiskraft zuzugestehen. Ich halte das bei der Ausbildung von
Mathematikern auch f"ur angemessen.
Bei der Mathematik-Ausbildung  im allgemeinen scheint mir 
dieses Vorgehen dahingegen nicht zielf"uhrend: 
In diesem Kontext
 sollte man
meines Erachtens nicht mit demselben Ma"s messen,
auch ohne alle Mengenlehre geometrisch erkl"arte Begriffe
wie Gerade und Kreis, Ebene und Raum,
als wohldefinierte Objekte der Mathematik zulassen und
geometrischen Argumenten
Beweiskraft zugestehen. 
\end{Bemerkungl}
\begin{Bemerkungl}
  Im Wortlaut der ersten Zeilen des Artikels 
\glqq Beitr"age zur Begr"undung der transfiniten Mengenlehre (Erster Aufsatz)\grqq\ 
von Georg Cantor, erschienen im Jahre 1895, h"ort sich 
die Definition einer Menge so an:
\begin{quote} Unter einer {\bf Menge}\index{Menge} verstehen wir jede
  Zusammenfassung $M$ von bestimmten wohlunterschiedenen Objekten $m$  
unserer Anschauung oder  unseres Denkens 
(welche die {\bf Elemente}\index{Element} von $M$
genannt werden) zu einem Ganzen.
\end{quote} 
Verbinden
wir mit einer Menge eine geometrische Vorstellung, so nennen wir ihre Elemente
auch {\bf Punkte}\index{Punkt} und die Menge selbst einen
\defind{Raum}.  Ein derartiges Herumgerede ist nat"urlich keine formale
Definition und birgt durchaus verschiedene Fallstricke, vergleiche \ref{WHKa}. 
Das Ziel dieser Vorlesung ist aber auch nicht eine formale
Begr"undung der Mengenlehre, wie  Sie sie 
in der Logik kennenlernen k"onnen.
Sie sollen vielmehr die Bedeutung dieser Worte intuitiv erfassen wie ein
Kleinkind, das Sprechen lernt: Indem sie mir und anderen 
Mathematikern zuh"oren,
wie wir mit diesen Worten sinnvolle S"atze bilden, uns nachahmen, und
beobachten, welchen Effekt Sie damit hervorrufen.  Unter anderem dazu sind die
"Ubungsgruppen da. 
\end{Bemerkungl}

\begin{Bemerkunge}
Bei der Entwicklung der Mathematik aus der Umgangssprache durch
fortgesetztes Zuspitzen und Umwidmen des Wortschatzes mu"s ich 
an den Baron von M"unchhausen denken, wie er sich an seinen eigenen
Haaren aus dem Sumpf zieht. Schon verbl"uffend, da"s es klappt.
Aber bei Kleinkindern, die Sprechen lernen, ist es ja noch viel 
verbl"uffender, wie sie die Bedeutung von Worten erfassen,
ohne da"s man sie ihnen  in Worten erkl"aren kann.
\end{Bemerkunge}

\begin{Beispiele}
Endliche Mengen kann man  durch eine vollst"andige Liste ihrer Elemente
in geschweiften Klammern angeben, zum Beispiel in der Form\index{)5@$\{\;\}$ Mengenklammern}  
$$X = \{x_{1},x_{2}, \ldots, x_{n} \}$$
Diese geschweiften Klammern hei"sen 
auch {\bf Mengenklammern}.\index{Mengenklammern}
Die Elemente d"urfen mehrfach
genannt werden und es kommt nicht auf die Reihenfolge an,
in der sie genannt werden.
Wir haben also $\{1,1,2\} = \{2,1\}$.\index{)0lm@$\in$  Element von}\index{)0lm@$\not\in$ nicht Element von} 
Die Aussage \glqq $x$ ist Element von $X$\grqq\  wird mit $x\in X$ abgek"urzt, ihre
Verneinung \glqq $x$ ist nicht Element von $X$\grqq\  mit $x \not\in X$.
Zum Beispiel gilt $1\in \{2,1\}$ und $3\not\in \{2,1\}$.  
Es gibt auch die sogenannte 
{\bf leere Menge}\index{Menge!leere Menge}\index{leer!Menge} $\emptyset=\{\;\}$,
die gar kein\index{)0lm@$\emptyset$ leere Menge}
Element enth"alt.
Andere Beispiele sind die Mengen
\begin{description}
\item[$\DN$]$\pdef \{0,1,2,\ldots \}$\index{N@$\DN$ nat"urliche
  Zahlen} der {\bf nat"urlichen
Zahlen},\index{Zahl!nat"urliche}\index{nat"urliche Zahlen} 
\index{N@$\DN$ nat"urliche
  Zahlen} 
\item[$\DZ$]$\pdef\{0,1,-1,2,-2, \ldots\}$ 
 der {\bf ganzen Zahlen} und\index{Zahl!ganze}\index{ganze Zahlen} 
\index{Z@$\DZ$ ganze Zahlen}
\item[$\DQ$]$\pdef\{p/q \mid p,q \in \DZ,\; q \neq 0\}$
der {\bf rationalen 
Zahlen}.\index{Zahl!rationale}\index{rationale Zahlen}\index{Q@$\DQ$ rationale Zahlen}
\end{description}      
Der Name letzterer Menge kommt von lateinisch 
\glqq ratio\grqq\  f"ur
\glqq Verh"altnis\grqq, der Buchstabe $\DQ$ steht f"ur \glqq Quotient\grqq. 
Man beachte, da"s wir auch hier Elemente mehrfach genannt haben,
es gilt ja $p/q = p^{\prime}/q^{\prime}$ genau dann,
wenn $pq^{\prime} = p^{\prime}q$.  Auf Deutsch bezeichnet man die 
rationalen Zahlen
 auch als
\defind{Bruchzahlen}, da man sich etwa ein Viertel eines Kekses 
 als den Anteil denken kann,
der entsteht, wenn man besagten Keks in vier gleiche Teile zerbricht.
Einen Leitfaden zu einem formaleren Aufbau des Zahlensystems k"onnen Sie
in \eref{AuZ}{GR} finden.
\end{Beispiele}

\begin{Bemerkunge}[\textbf{Herkunft des Gleichheitszeichens}] 
  Das Gleichheitszeichen\index{)8@$=$ Gleichheitszeichen} $=$ 
scheint auf ein 1557 von Robert Recorde
  publiziertes Buch zur"uckzugehen und soll andeuten, da"s das, was auf der
  linken und rechten Seite dieses Zeichens steht, so gleich ist wie die beiden
  Strichlein, die das uns heute so selbstverst"andliche Gleichheitszeichen
  bilden. Davor schrieb man statt einem Gleichheitszeichen meist $a\!\!\;e$
  f"ur \glqq "aquivalent\grqq.
\end{Bemerkunge}

\begin{Bemerkunge}[\textbf{Diskussion der Notation}]
In  Texten, in deren Konventionen die Null
keine nat"urliche Zahl ist, verwendet man meist die
abweichenden Notationen $\DN$ f"ur die Menge  $\{1,2,\ldots \}$
und $\DN_0$\index{N@$\DN_0$} f"ur die Menge $\{0,1,2,\ldots \}$. 
Die in diesem Text verwendete Notation $\DN=\{0,1,2,\ldots \}$
stimmt mit 
der internationalen Norm ISO 31-11 "uberein. 
\end{Bemerkunge}

\begin{Bemerkungl}
  Die Bedeutung der Symbole $\DZ$ und $\DQ$ 
ist in der Mathematik weitgehend einheitlich. Man verwendet diesen
Schrifttypus auch sonst 
gerne f"ur  Symbole, die 
in ihrer Bedeutung "uber gro"se Teile der Mathematik
hinweg einheitlich verwendet werden. Bei der Bedeutung von $\DN$ ist man
allerdings nie ganz sicher, ob die Null mitgemeint ist. In den Konventionen dieses Textes gilt $0\in\DN$. 
\end{Bemerkungl}



  \begin{Bemerkungl}\label{Karda}
    Eine Menge, die nur endlich viele Elemente hat, nennen wir eine {\bf
      endliche Menge}.\index{endlich!Menge} Eine pr"azisere Definition dieses
    Konzepts wird in \eref{eue}{LA1} gegeben.  Wir vereinbaren
bereits hier, da"s wir
  auch  die leere Menge 
    endlich nennen. 
 Die Zahl der Elemente einer endlichen Menge $X$
    nennen wir ihre {\bf Kardinalit"at}\index{Kardinalit"at} oder {\bf
      M"achtigkeit}\index{M"achtigkeit}\index{card@$\op{card}$} und notieren
    sie $$|X|$$ oder $\op{card}(X)$.\index{)5@${\mid}\;{\mid}$ Kardinalit"at} In
    der Literatur findet man auch die Notation $\sharp X$.\index{)0a@$\sharp$
      Kardinalit"at} F"ur endliche Mengen 
$X$ ist demnach ihre Kardinalit"at stets eine
    nat"urliche Zahl $|X|\in\DN$ und $|X|=0$ ist gleichbedeutend zu $
    X=\emptyset$.
Ist $X$ unendlich, so schreiben wir bis auf weiteres
kurzerhand $|X|=\infty$ und
    ignorieren in unserer Notation, da"s auch unendliche Mengen \glqq verschieden
    gro"s\grqq\  sein k"onnen. F"ur ein Beispiel f"ur
    \glqq verschieden gro"se unendliche Mengen\grqq\ siehe \ref{QR} und f"ur
    eine genauere Diskussion des Begriffs der Kardinalit"at vergleiche  \eref{KaZa}{AL}.
      \end{Bemerkungl}







\begin{Definition}
  Eine Menge $Y$ hei"st
  {\bf Teilmenge}\index{Menge!Teilmenge}\index{Teilmenge}
  einer Menge $X$, wenn jedes Element\label{Tma} 
von $Y$ auch ein Element von $X$ ist. Man schreibt daf"ur $Y\subset  X$
oder $X \supset Y$.
\end{Definition}
\begin{Beispiel} Die leere Menge Teilmenge jeder Menge,
in Formeln  $\emptyset \subset X$. 
$\{x\} \subset X $ ist gleichbedeutend zu $ x \in X$.
 Es gilt $\emptyset\subset \{2,1\}\subset\DZ\subset\DQ$.
\end{Beispiel}


\begin{Bemerkungl}[\textbf{Elemente und Teilmengen}]
  Es ist im Kontext der Mengenlehre wichtig, bei einer Menge $X$ sorgf"altig zu unterscheiden zwischen ihren Elementen und ihren Teilmengen. Gegeben ein Element $x\in X$ ist f"ur uns das Element $x\in X$ etwas anderes als
  die Teilmenge $\{x\}\subset X$, die nur aus dem einzigen Element $x$ besteht.
 Gegeben eine Menge $X$ mit einer 
Teilmenge $Y\subset X$ sage ich 
auch, $X$ {\bf umfa"st} $Y$. Gegeben ein Element $x\in X$ sage ich,
$x$ {\bf geh"ort zu} $X$.\label{gehoa}  
Andere Sprechweisen m"ochte ich ungern auf eine so pr"azise Bedeutung festlegen.
Gegeben eine Teilmenge $Y\subset X$ kann man sagen, \glqq $Y$ sei enthalten in
$X$\grqq\  oder \glqq $Y$ liege in $X$\grqq, 
und gegeben ein Element $x\in X$ kann man auch sagen,
\glqq $x$ sei enthalten in
$X$\grqq\  oder \glqq $x$ liege in $X$\grqq. 
Was genau gemeint ist, gilt es dann aus dem Kontext zu erschlie"sen.
\end{Bemerkungl}


\begin{Bemerkungl}[\textbf{Diskussion der Notation}]
  Gegeben eine Menge $X$ verwenden wir die Schreibweise $Y\subsetneq X$
  als Abk"urzung f"ur $(Y\subset X$ und $Y\neq X)$. Eine von der ganzen
  Menge verschiedene Teilmenge $Y$ einer Menge $X$ nennen wir auch eine
  {\bf echte\index{Teilmenge!echte}\index{echt!Teilmenge}
    Teilmenge von $X$}. Bei diesen Notationen folgen wir Cantor und Bourbaki,
  die sehr viel sp"ater festgelegte  internationalen Norm ISO 31-11 weicht jedoch davon ab. In der
  folgenden Tabelle stellen wir diese beiden Konventionen einander
  gegen"uber.
 \begin{center} \begin{tabular}{c|c|c}
Cantor und Bourbaki &  Norm ISO 31-11&  Bedeutung\\[1mm] \hline
&\\
$\subset$ & $\subseteq$ & ist Teilmenge von\\[1mm]
$\subsetneq$ & $\subset$ & ist echte Teilmenge von\\[1mm]
\end{tabular}
 \end{center}
Ich ziehe die Konvention von Cantor und Bourbaki vor,
weil ich sie gewohnt bin und weil man sehr oft
Teilmengen zu betrachten hat und nur vergleichsweise selten echte Teilmengen.
Ich  mu"s jedoch zugeben, da"s die in diesem Text gew"ahlte Notation
$\subset, \subsetneq$ mit den "ublichen  Notationen $\leq,<$ f"ur Ungleichungen 
 weniger gut zusammenpa"st als die Konvention nach ISO 31-11.
\end{Bemerkungl}






  \begin{Bemerkungl}
    Oft bildet man neue  Mengen als Teilmengen bestehender Mengen.
    Gebr"auchlich ist dazu eine Notation\index{)0a@$\mid$ Notation bei
      Teilmengen}, bei der man zwischen den
    Mengenklammern hinter einem senkrechten
    Strich dazuschreibt, welche zus"atzliche Eigenschaft die Elemente einer
    Teilmenge haben sollte, so da"s man Teilmengen $Y$ einer Menge
    $X$ angeben kann in der Form 
    $$Y= \{x\in X \mid x \text{ hat zus"atzlich noch eine gewisse Eigenschaft}\}$$
  Zum Beispiel
    gilt $\DN = \{a \in \DZ \mid a \geq 0\}$, lies \glqq die Menge der nat"urlichen Zahlen ist die Teilmenge der Menge der ganzen Zahlen bestehend aus allen ganzen Zahlen, die $\geq 0$ sind\grqq, und $\{0,1\} = \{a \in \DN \mid
    a^{2}=a\}$.
  \end{Bemerkungl}



\begin{Definition}\label{MeKoa}
Es ist auch erlaubt, die \glqq Menge aller Teilmengen\grqq\  einer gegebenen Menge
$X$ zu bilden. Sie hei"st die {\bf Potenzmenge\index{Menge!Potenzmenge}
 von}\index{Potenzmenge}\index{P@$\cal{P}(X)$ Potenzmenge} $X$ und wird 
$\cal{P}(X)$ oder $\op{Pot}(X)$ 
notiert.\index{Pot@$\op{Pot}(X)$ Potenzmenge} 
\end{Definition}

\begin{Beispiel} Die Potenzmenge $\cal{P}(\{1,2,3\})$ kann man als die Menge
  aller m"oglichen Ausg"ange einer Versuchsanordnung interpretieren, bei der
  man dreimal eine M"unze wirft. Dazu mag man etwa jedem
  Ausgang die Menge der Wurfnummern zuordnet, bei denen
  Wappen herauskam. So w"urde  etwa
  dem Ausgang WZW die Teilmenge $\{1,3\}$ zugeordnet.
\end{Beispiel}

\begin{Bemerkungl}[\textbf{Kardinalit"at der Potenzmenge}] 
Ist $X$ eine endliche Menge, so ist auch ihre
Potenzmenge endlich und es gilt die Formel  $|\cal{P}(X)|=2^{|X|}$. F"ur
die drei-ele\-men\-ti\-ge Menge 
$X=\{1,2,3\}$ besteht ihre Potenzmenge $\cal{P}(X)$  zum Beispiel 
aus $8=2^3$  Elementen und wir haben genauer
$$\cal{P}(X)=\big\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},
\{1,3\},\{2,3\},\{1,2,3\}\big\}$$
Die Teilmenge $\{1\}\subset \{1,2,3\}$, die nur aus dem Element $1$ besteht, ist also
ein Element der Potenzmenge $\{1\}\in \cal{P}(\{1,2,3\})$.
Das Element $1$ ist dahingegen kein Element der Potenzmenge, sondern
ein Element der ursprünglichen Menge $1\in \{1,2,3\}$.
\end{Bemerkungl}



\begin{Satz}[\textbf{Bedeutung der Binomialkoeffizienten}]
Gegeben nat"urliche Zahlen 
$n,k\in \DN$ gibt der 
\hyperref[BiKoea]{Binomialkoeffizient} ${n\choose k}$ 
die Zahl der $k$-elementigen Teilmengen 
einer $n$-ele\-men\-tigen Menge an.\label{BKa}  
In Formeln ausgedr"uckt haben wir unter der Annahme $|X|=n$ also
$$ |\{ Y\subset X\mid |Y|=k\}|=\textstyle{{n\choose k}}$$
\end{Satz}


\begin{proof}[Beweis]
Vollst"andige Induktion "uber $n$. F"ur $n=0$ gilt die Aussage, denn eine
nullelementige Menge hat genau eine $k$-elementige Teilmenge falls
$k=0$ und keine $k$-elementige Teilmenge falls $k\geq 1$.
Nehmen wir nun an, die Aussage sei f"ur ein $n$ schon bewiesen.
Eine $(n+1)$-elementige Menge $X$ schreiben wir als $X=M\cup \{x\}$ mit dem
gleich in \ref{MGKKa} formal eingef"uhrten Vereingungszeichen $\cup$, wo
$M$ eine $n$-elementige Menge ist und $x \not\in M$.
Ist $k=0$, so gibt es genau eine $k$-elementige Teilmenge von $M\cup \{x\}$,
n"amlich die leere Menge.
Ist $k\geq 1$, so gibt es in $M \cup \{x\}$ nach 
Induktionsannahme genau ${n\choose k} $
$k$-elementige Teilmengen, die $x$ nicht enthalten.
Die $k$-elementigen Teilmengen dahingegen, die $x$ enthalten,
ergeben sich durch Hinzunehmen von $x$ aus den
$(k-1)$-elementigen Teilmengen von $M$, von denen es gerade ${n\choose k-1}$
gibt. Insgesamt hat $M \cup \{x\}$ damit  also genau
${n\choose k} + {n\choose k-1} ={n+1\choose k}$ 
Teilmengen mit genau $k$ Elementen.
\end{proof}

\begin{Bemerkungl}
Wieder scheint mir dieser Beweis in der f"ur vollst"andige
Induktion typischen Weise undurchsichtig. Ich ziehe deshalb den
in \ref{BBKa} gegebenen weniger formellen 
Beweis vor. Man kann auch diesen Beweis  formalisieren und
verstehen als Spezialfall der sogenannten 
\glqq\hyperref[BF]{Bahnformel}\grqq, 
vergleiche \eref{BIKON}{LA2}.
\end{Bemerkungl}

\begin{Bemerkungl}[\textbf{Variante zum Beweis der binomischen Formel}] 
Wir geben nun die versprochene pr"azise 
Formulierung unseres ersten Beweises der binomischen Formel \ref{BiFoAa}.
Wir rechnen dazu\label{PFBa}
$$(a+b)^n=\sum_{Y\subset\{1,2,\ldots,n\}} a^{|Y|} b^{n-|Y|}$$
Die rechte Seite  soll hier in Verallgemeinerung der in 
 \ref{Summa} eingef"uhrten
Notation bedeuten, da"s wir f"ur jede Teilmenge
$Y$ von $\{1,2,\ldots,n\}$ den angegebenen Ausdruck $a^{|Y|} b^{n-|Y|}$
nehmen und alle diese Ausdr"ucke aufsummieren.
Dann fassen wir gleiche Summanden
zusammen und erhalten mit \ref{BKa} die binomische Formel.
\end{Bemerkungl}
\subsubsection*{"Ubungen}

\begin{Ubung}
Es gilt $\sum_k{n\choose k}=2^n$.
\end{Ubung}
\begin{Ubung}
Man zeige $(a+b+c)^n=\sum_{i+j+k=n}\frac{n!}{i!j!k!} a^{i} b^{j}c^k$.
\end{Ubung}
\subsection{Mengenoperationen}
\label{Mopa} 
\begin{Definition}
Wir erinnern, da"s wir $\pdef$ als Abk"urzung f"ur \glqq ist definiert als\grqq\ verwenden und da"s \glqq oder\grqq\ in der Mathematik stets das \glqq nichtausschlie"sende oder\grqq\ meint. Gegeben zwei Mengen $X,Y$ k"onnen  wir 
unter anderem auf folgende  Weisen neue Mengen
bilden:\label{MGKKa} 
\begin{enumerate}
\item
Die {\bf Vereinigung}\index{Vereinigung} 
$X\cup Y \pdef \{z \mid z \in X \text{ oder } 
z \in Y\}$,\index{)ucup@$\cup$ Vereinigung}
zum Beispiel ist $\{1,2\} \cup \{2,3\} = \{1,2,3\}$;
\item
Den {\bf Schnitt}\index{Schnitt!zweier Mengen} oder 
auch {\bf Durchschnitt}\index{Durchschnitt!zweier Mengen} 
$X\cap Y \pdef \{z \mid z \in X \text{ und } z \in Y\}$, 
zum\index{)9cap@$\cap$ Schnitt} Beispiel ist
$\{1,2\}\cap \{2,3\} = \{2\}$;
\item
Die {\bf Differenz}\index{Differenz!von Mengen}
$X \backslash Y \pdef \{z \in X \mid z \not\in Y\}$, 
zum\index{)2@$X \backslash Y$ Differenz von Mengen} 
Beispiel haben wir
$\{1,2\}\backslash \{2,3\} = \{1\}$. Man schreibt statt $X \backslash Y$
auch $X{-}Y$.\index{)8a@${-}$ Differenz von Mengen} 
Ist $Y$ eine Teilmenge von $X$, so hei"st $X \backslash Y$
das {\bf Komplement}\index{Komplement} von $Y$ in $X$
oder ausf"uhrlicher die {\bf Komplementmenge};\index{Komplementmenge}
\begin{figure}[htb]
    \includegraphics[width=0.8\textwidth]{SkriptenBilder/BildMop}
\\
\noindent\centering
Van-de-Ven-Diagramme f"ur Vereinigung, Schnitt und Differenz
\end{figure}
\item
Das {\bf Produkt}\index{kartesisch!Produkt!von zwei Mengen} 
$X \times Y \pdef\{(x,y)\mid x \in X,\; y\in Y\}$
oder ausf"uhrlicher  {\bf kartesische Produkt}.\index{)x@$\times$!kartesisches Produkt}
Es gilt also $(x,y)= (x^{\prime},
y^{\prime})$ genau dann, wenn gilt $x=x^{\prime}$ und $y=y^{\prime}$.
Zum Beispiel haben wir
$$\{1,2\} \times \{1,2,3\} = \{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)\}$$
Oft benutzt man f"ur das Produkt $X\times X$ 
einer Menge $X$ mit sich
selbst die Abk"urzung 
$X^2 \pdef X\times X$\index{)6\2@$X^2 =X\times X$} und nennt das
die Menge aller
{\bf angeordneten Paare}\index{Paar!angeordnetes} von
Elementen von $X$.
\end{enumerate} \end{Definition}

\begin{figure}[htb]
\begin{minipage}{0.45\textwidth}
  \includegraphics[width=\textwidth]{SkriptenBilder/BildPe}
\end{minipage}\hfill\begin{minipage}{0.45\textwidth}
  \includegraphics[width=\textwidth]{SkriptenBilder/BildKar}
\end{minipage}
\\
\centering
Zwei anschauliche Darstellungen des Produkts von zwei Mengen.
Links das Produkt einer Menge mit f"unf und einer
Menge mit drei Elementen. Rechts das Produkt zweier Geradensegmente,
aufgefa"st als unndliche Mengen.
In beiden F"allen wird ein Paar $(x,y)\in X\times Y$ dargestellt durch einen
Punkt, der "uber $x$ und neben $y$ liegt.
\end{figure}







\begin{Bemerkungl}
  Eine gute Anschauung f"ur die ersten drei Operationen liefern
die sogenannten {\bf van-de-Ven-Dia\-gram\-me},\index{van-de-Ven-Dia\-gramm} wie sie die
 Bilder
zeigen.
Sie sind allerdings nicht zu genau zu hinterfragen,
denn ob die Punkte auf einem Blatt Papier 
im Sinne von Cantor \glqq bestimmte wohlunterschiedene
Objekte unserer Anschauung\grqq\  
sind, scheint mir nicht ohne weiteres so klar.
Wenn man jedoch jedes der schraffierten Gebiete im Bild
als die Menge aller darin liegenden 
Kreuzungspunkte auf einem dazugedachten
Millimeterpapier auffa"st und keine dieser Kreuzungspunkte auf
den Begrenzungslinien liegen, 
so k"onnen sie wohl schon als eine Menge im Cantor'schen
Sinne angesehen werden. 
\end{Bemerkungl}



\begin{Bemerkungl}
  Zwei Teilmengen einer gegebenen Menge, 
die kein gemeinsames Element haben, hei"sen 
{\bf disjunkt}\index{disjunkt}.\index{)c@$\subset$ 
  Teilmenge} "Aquivalent dazu ist die Bedingung, da"s ihr Schnitt
die leere Menge ist.
\end{Bemerkungl}

\begin{Bemerkungl}[\textbf{Mehrdeutigkeiten mit dem Komma als Trenner}] 
  Die Verwendung des Kommas als Trenner ist hier
problematisch, da $(1,2)$ nun 
zweierlei bedeuten kann: Zum einen
ein Element des kartesischen Produkts $\DN\times\DN$,
zum anderen aber auch den eingeklammerten Dezimalbruch  $1,\!2$.
Was im Einzelfall gemeint ist, gilt es aus dem
Kontext zu erschlie"sen. In diesem Text
werden Dezimalbr"uche nur selten vorkommen.
In deutschen Schulb"uchern verwendet man f"ur angeordnete Paare meist
die abweichende Notation $(x|y)$, um auch Paare von Dezimalbr"uchen
unmi"sverst"andlich notieren zu k"onnen.\index{\mid@$(x{\mid} y)$ Notation f"ur Paare}\index{)5)@$(x{\mid} y)$ Notation f"ur Paare}
\end{Bemerkungl}
\begin{Bemerkungl}[\textbf{Diskussion der Terminologie}]
  Die Bezeichnung als \glqq Schnitt\grqq\ kommt wohl
  her von der Vorstellung des Schnitts zweier Geraden, wenn
  man sie als Teilmengen der Ebene denkt und diese
  hinwiederum als ein Blatt Papier, das man l"angs der einen
  Gerade entzweischneiden kann. Der Punkt, an dem die
  andere Gerade entzweigeschnitten wird, ist dann der Schnittpunkt
  und der Schnitt unserer beiden Geraden besteht genau aus diesem
  einen Punkt.
\end{Bemerkungl}

\begin{Bemerkungl}[\textbf{Mengenlehre und das Bilden von Begriffen}] 
  Wir werden in unserer naiven Mengenlehre die ersten 
drei Operationen \glqq Vereinigung\grqq, \glqq Schnitt\grqq\
und \glqq Differenz\grqq\
aus \ref{MGKKa} nur
 auf Teilmengen einer gemeinsamen 
Obermenge anwenden, die uns in der einen oder anderen
  Weise bereits zur Verf"ugung steht.
Die Potenzmenge und das kartesische Produkt dahingegen 
benutzen wir, um dar"uber hinaus neue Mengen zu erschaffen. 
Diese Konstruktionen erlauben es, im Rahmen  der Mengenlehre 
so etwas wie Abstraktionen zu bilden: Wenn wir uns etwa
die Menge $T$ aller an mindestens einem Tag der Weltgeschichte lebenden
oder gelebt habenden
Tiere als eine Menge im Cantor'schen Sinne denken, 
so w"urden wir Konzepte wie
\glqq m"annlich\grqq\  oder \glqq Hund\grqq\  oder \glqq Fleischfresser\grqq\  
formal als Teilmengen dieser Menge
 alias als Elemente
von $\cal{P}(T)$ formalisieren.
Das Konzept \glqq ist Kind von\grqq\  w"urde dahingegen formalisiert
als eine Teilmenge $K\subset T\times T$ des kartesischen Produkts 
unserer Menge $T$ mit sich selbst alias
als ein Element  $K\in \cal{P}(T\times T)$, n"amlich als die Teilmenge
$K\pdef \{(x,y)\in T\times T\mid x\text{ ist Kind von }y\}$.
\end{Bemerkungl}



\begin{Bemerkungl}\label{VMRa}
F"ur das Rechnen mit Mengen "uberlegt man sich die folgenden
Regeln, die ich gleich mit ihren "ublichen Bezeichnungen angebe:
$$\begin{array}{lrcl}
\text{\bf Assoziativgesetze:}&X \cap (Y\cap Z)&=& (X\cap Y)\cap  Z\\
&X \cup (Y\cup Z)&=& (X\cup Y) \cup  Z\\[2mm]
\text{\bf Distributivgesetze:}&X \cup (Y\cap Z)&=& (X\cup Y)\cap (X \cup Z)\\
&X \cap (Y\cup Z)&=& (X\cap Y) \cup (X \cap Z)\\[2mm]
\text{\bf de Morgan'sche Regeln:\index{de Morgan'sche Regeln}}&X\backslash (Y\cup Z) & = & (X \backslash Y) \cap (X\backslash Z)\\
&X \backslash(Y\cap Z)&=& (X\backslash Y) \cup (X \backslash Z)\\[2mm]
\text{\bf Komplement der Differenzmenge:}&X \backslash (X\backslash Y)&=& X \cap Y
\end{array}$$
Eine gute Anschauung f"ur diese Regeln liefern
die van-de-Ven-Dia\-gramme, wie  die
 Bilder
zeigen. Das liegt daran, da"s alle acht m"oglichen Lagen
in Bezug auf unsere drei Mengen in diesen Diagrammen als
Fl"achen zu sehen sind.
\end{Bemerkungl}
\begin{figure}[htb]
 \begin{minipage}{0.4\textwidth}
  \includegraphics[width=\textwidth]{SkriptenBilder/Bild0001}
\end{minipage}\hfill\begin{minipage}{0.4\textwidth}
  \includegraphics[width=\textwidth]{SkriptenBilder/Bild0007}
\end{minipage}
\\[2mm]
\noindent\centering
$X \cap (Y\cup Z)= (X\cap Y)\cup (X \cap Z)\quad\quad\quad X \setminus (Y\cap Z)= (X\setminus Y)\cup (X \setminus Z)$
\end{figure}

\begin{Bemerkungl}
  Ich zeige beispielhaft die Regel $X \cup (Y\cap Z)= (X\cup Y)\cap (X \cup Z)$.
Es reicht, statt der Gleichheit die beiden Inklusionen $\subset$ und
$\supset$ zu zeigen.
\\[2mm]\noindent
Ich beginne mit $\subset$.
Sicher gilt $(Y\cap Z)\subset Y$, also auch $X\cup (Y\cap Z)\subset X\cup Y$.
Ebenso zeigt man  $X\cup (Y\cap Z)\subset X\cup Z$ und damit folgt
schon mal $\subset $.
\\[2mm]\noindent
Bleibt noch $\supset$ zu zeigen. Das will mir nur durch 
Betrachtung von Elementen gelingen. Gegeben $a\in (X\cup Y)\cap (X \cup Z)$
gilt entweder $a\in X$ oder $a\not\in X$. Falls $a\in X$ haben wir eh
$a\in X\cup (Y\cap Z)$. Falls $a\not\in X$  folgt aus 
$a\in(X\cup Y)\cap (X \cup Z)$ erst  $a\in(X\cup Y)$ und
dann $a\in Y$ und weiter erst  $a\in(X\cup Z)$ und dann $a\in  Z$, 
also $a\in Y\cap Z\subset X \cup (Y\cap Z)$.
Wir haben somit gezeigt, da"s jedes Element $a$ von $(X\cup Y)\cap (X \cup Z)$
auch zu $X \cup (Y\cap Z)$ geh"ort. Damit folgt die behauptete Inklusion $\supset $.
\end{Bemerkungl}


\begin{fBild}[p]
  \centering
  \includegraphics[width=\textwidth]{SkriptenBilder/BildPro}\\
\noindent
Aus $X=X_1\cup X_2$ und $Y=Y_1\cup Y_2$ folgt noch lange nicht
$X\times Y=(X_1\times Y_1)\cup (X_2\times Y_2)$
\end{fBild}
\begin{Bemerkunge}[\textbf{Das Russell'sche Paradoxon}] 
Ich will nicht verschweigen, da"s der 
in diesem Abschnitt dargestellte
naive Zugang zur Mengenlehre\label{WHKa} 
durchaus begriffliche Schwierigkeiten  mit 
sich\index{Russell'sches Paradoxon} 
bringt: Zum Beispiel darf die Gesamtheit $\cal{M}$ 
aller Mengen nicht als Menge angesehen werden, da wir sonst die 
\glqq Menge aller Mengen, die sich nicht selbst als Element enthalten\grqq,
 gegeben durch die formelhafte Beschreibung
$\cal{N}=\{A\in \cal{M}\mid A\not\in A\}$, 
bilden k"onnten. F"ur diese Menge kann aber weder $\cal{N}\in\cal{N}$
noch $\cal{N}\not\in\cal{N}$ gelten.
Diese Art von Schwierigkeiten kann erst ein formalerer
Zugang kl"aren und aufl"osen, bei dem man unsere naiven Vorstellungen
durch Ketten von Zeichen aus einem wohlbestimmten endlichen
Alphabet ersetzt und unsere Vorstellung von
Wahrheit durch die Verifizierbarkeit 
vermittels rein algebraischer \glqq erlaubter Manipulationen\grqq\  
solcher Zeichenketten, die in \glqq Axiomen\grqq\  festgelegt werden.
Diese Verifikationen kann
man dann durchaus 
auch einer Rechenmaschine "uberlassen, so da"s 
wirklich auf \glqq objektivem\grqq\  Wege entschieden werden kann, 
ob ein \glqq Beweis\grqq\  f"ur die \glqq Richtigkeit\grqq\  
einer unserer Zeichenketten in einem
vorgegebenen axiomatischen Rahmen stichhaltig ist.
Allerdings kann in derartigen Systemen von einer  
Zeichenkette algorithmisch nur entschieden werden, 
ob sie eine \glqq sinnvolle Aussage\grqq\ 
ist, nicht aber, ob sie \glqq bewiesen\grqq\  werden kann. 
Noch viel st"arker zeigt der Unvollst"andigkeitssatz von G"odel, 
da"s es in einem derartigen axiomatischen Rahmen, sobald er 
reichhaltig genug ist f"ur eine 
Beschreibung des Rechnens mit nat"urlichen Zahlen,
stets sinnvolle
Aussagen gibt derart, 
da"s entweder sowohl die Aussage als auch  ihre Verneinung oder aber
weder die Aussage noch ihre Verneinung bewiesen werden k"onnen.
Mit diesen und "ahnlichen Fragestellungen  
besch"aftigt sich die Logik. 
\end{Bemerkunge}

\begin{Bemerkungw}[\textbf{Weitere Konstruktionen der Mengenlehre}]
Um mich nicht dem Vorwurf auszusetzen, w"ahrend des Spiels die 
Spielregeln "andern zu wollen, sei bereits hier erw"ahnt, 
was noch hinzukommen soll.
Die einzigen grundlegenden Konstruktionen, die
noch fehlen, sind das Bilden der \glqq disjunkten Vereinigung\grqq\ 
und des \glqq kartesischen Produkts\grqq\  
zu einer \glqq beliebigen  Mengenfamilie\grqq\  in \eref{SPVb}{LA2} und \eref{SPVn}{LA2}. 
In  \eref{SSSVMF}{AN2} besprechen wir weiter Schnitt und Vereinigung 
einer \glqq beliebigen  Familie von Teilmengen einer gegebenen Menge\grqq. 
In \eref{ZoLe}{LA1} werden einige weniger offensichtliche
Argumentationen im Zusammenhang mit dem
sogenannten \glqq Zorn'schen Lemma\grqq\  erl"autert, die 
meines Erachtens bereits an den Rand dessen gehen,
was man in unserem informellen Rahmen 
der naiven Mengenlehre als Argumentation noch vertreten kann.
In \eref{NatZ}{LA1}  wird
die Konstruktion der nat"urlichen Zahlen im
Rahmen der Mengenlehre diskutiert, insbesondere geben wir erst dort
eine formale Definition des Begriffs einer endlichen Menge. 
 Sicher  ist es 
in gewisser Weise unbefriedigend, 
das Fundament des Hauses der Mathematik erst fertigzustellen, 
wenn  bereits  erste Stockwerke stehen und bewohnt sind.
Andererseits will ich aber auch vermeiden, da"s Sie mir  auf einem
gewaltigen Fundament, das die ganze Mathematik tragen kann,
 im ersten Winter(semester) j"ammerlich erfrieren. 
\end{Bemerkungw}

\begin{Bemerkungl}[\textbf{Der Sinn von Genauigkeit und sorgf"altiger Sprache}]
 Ich k"onnte mir gut vorstellen, da"s verschiedene meiner Leser denken,
diese ganze Pedanterie sei doch eigentlich "uberfl"ussig 
und jetzt sollten
wir doch einfach mal fr"ohlich losrechnen wie das in der 
Schule ja auch sehr gut ging. Ich will hier 
erkl"aren, warum  Pedanterie\label{GsSs}  
in diesem Zusammenhang  wichtig ist. Viele von Ihnen werden wissen,
wie man mit einem einfachen Blatt Papier zum Mond kommt: $42$-mal
Falten und draufsteigen, das war's schon. So "ahnlich ist es in der
Mathematik: Etwas v"ollig Banales wie die naive Mengenlehre wird
in den etwa drei"sig Vorlesungsdoppelstunden des Wintersemesters 
jedes Mal auf's neue gefaltet und wenn Sie dann am Ende des
Wintersemesters zur"uckblicken, kann Ihnen
schon leicht schwindlig werden. Das funktioniert mit wirklichem Papier 
nur eingeschr"ankt, aber wenn man sehr festes und glattes 
\glqq Gedankenpapier\grqq\ nimmt, und solches
Gedankenpapier ist eben gerade die Mengenlehre,
dann klappt es verbl"uffend gut.
 Man mu"s dazu aber mit der Herstellung dieses 
Gedankenpapiers ebenso wie beim Falten  sorgf"altig sein
bis zur Pedanterie, denn 
auch die kleinste Ungeschicklichkeit 
 vervielfacht sich bei diesem Vorgehen 
mit derselben Schnelligkeit wie die gedankliche H"ohe 
 und bringt, eh man sich's versieht, alles zum
Einsturz. 
\end{Bemerkungl}
\subsubsection*{"Ubungen}
\begin{Ubung}
Sind $X$ und $Y$ endliche Mengen, so gilt f"ur die Kardinalit"aten
$|X\times Y|=|X|\cdot|Y|$ und $|X\cup Y|
=|X|+|Y|-|X\cap Y|$.\label{EFGla}
\end{Ubung}



\subsection{Abbildungen}
\label{AnBa} 
\begin{Definition}
Seien $X,Y$ Mengen. Eine {\bf Abbildung}\index{Abbildung}
\index{)4@$\ra$ Abbildung}
$f: X \ra Y$ ist eine Zuordnung, die
jedem Element $x\in X$ genau ein Element $f(x)\in Y$ zuordnet, 
das {\bf Bild}\index{Bild}
von $x$ unter $f$, auch genannt der {\bf Wert}\index{Wert} 
von $f$ an der Stelle $x$. Man spricht dann auch vom
{\bf Auswerten}\index{Auswerten} der Funktion $f$ an der Stelle $x$
oder vom {\bf Einsetzen}\index{Einsetzen} von $x$ in $f$ und schreibt
manchmal abk"urzend $f(x)=fx$.
\end{Definition}
\begin{figure}[htb]
\begin{minipage}{0.45\textwidth}
  \includegraphics[width=\textwidth]{SkriptenBilder/Bild0002}
\end{minipage}\hfill
 \begin{minipage}{0.45\textwidth}\centering
Eine  Abbildung einer Menge mit
f"unf in eine mit drei Elementen
\end{minipage}
\end{figure}


\begin{Bemerkungl}
 Wem das zu vage ist, der mag die alternative Definition vorziehen,
nach der
eine {\bf Abbildung}\index{Abbildung} 
$f:X \ra Y$  eine Teilmenge\label{DFAa} 
$f\subset X \times Y$ ist derart, da"s es f"ur jedes $x \in X$ genau ein
$y \in Y$ gibt mit $(x,y) \in f$.
Dies eindeutig bestimmte $y$ schreiben wir dann $f(x)$ und sind
auf einem etwas formaleren Weg wieder
an demselben Punkt angelangt. 
In unseren Konventionen nennen wir besagte Teilmenge 
den {\bf Graphen von} $f$\index{Graph!einer Abbildung}
 und notieren sie mit 
dem Symbol
$\Gamma$ (sprich: Gamma),\index{G@$\Gamma(f)$ Graph von $f$}
einem gro"sen griechischen G, und schreiben
$$\Gamma(f)\pdef \{(x,f(x))\mid x\in X\}\subset X\times Y$$
\end{Bemerkungl}
\begin{figure}[htb]
\begin{minipage}{0.45\textwidth}
  \includegraphics[width=\textwidth]{SkriptenBilder/Bildgr}
\end{minipage}\hfill
 \begin{minipage}{0.45\textwidth}\centering
Der Graph der oben angegebenen Abbildung, wobei das $X$ oben mit dem
$X$ hier identifiziert wurde durch \glqq Umkippen nach Rechts\grqq\ 
\end{minipage}
\end{figure}

\begin{Definition}
Ist $f:X \ra Y$ eine Abbildung, so nennen wir $X$ ihren {\bf
Definitionsbereich}\index{Definitionsbereich}
und $Y$ ihren {\bf Wertebereich}\index{Wertebereich}.
Zwei Abbildungen nennen wir gleich, wenn sie denselben
Definitionsbereich\label{EnSSa} 
$X$, denselben Wertebereich $Y$ und dieselbe 
Abbildungsvorschrift $f\subset X \times
Y$ haben.
\end{Definition}

\begin{Bemerkungl}[\textbf{Die Notationen $\ra$ und $\mapsto$}]
Wir notieren Abbildungen oft in der Form\index{)4@$\mapsto$ wird abgebildet auf}
$$\begin{array}{rccl}
f:&X & \ra & Y\\
&x & \mapsto & f(x)
\end{array}$$  
und in verschiedenen Verk"urzungen dieser Notation. Zum Beispiel sprechen wir
von \glqq einer Abbildung $\DN\ra \DN$ von
der Menge der nat"urlichen Zahlen in sich selber\grqq\  
oder \glqq der Abbildung $n\mapsto n^3$ von
der Menge der nat"urlichen Zahlen in sich selber\grqq.
Wir benutzen unsere zwei Arten von Pfeilen 
$\ra$ und $\mapsto$ auch 
im allgemeinen in derselben Weise.
\end{Bemerkungl}
\begin{Beispiel}
F"ur jede Menge $X$ haben wir 
die {\bf identische Abbildung}\index{Abbildung!identische} oder
{\bf Identit"at}\index{Identit"at}\index{id}
$$\begin{array}{rccc}
\op{id}=\op{id}_X :& X &\ra &X\\
&x & \mapsto& x
\end{array}\hspace{15mm}$$
Ein konkreteres Beispiel f"ur eine Abbildung ist das Quadrieren
$$\begin{array}{rccl}
q :& \DZ &  \ra & \DZ \\
&n& \mapsto & n^{2}
\end{array}$$  
\end{Beispiel}
\begin{Beispiel}
Gegeben zwei Mengen $X,Y$ erkl"art man die 
{\bf Projektionsabbildungen}
oder {\bf Projektionen}\index{Projektion!bei zwei Mengen}
$\op{pr}_X:X\times Y\ra X$ beziehungsweise $\op{pr}_Y:X\times Y\ra Y$
durch\index{pr@$\op{pr}_X$!Projektion}
die Vorschrift $(x,y)\mapsto x$ beziehungsweise $(x,y)\mapsto y$.
In manchen Zusammenh"angen notiert man sie auch abweichend
$\op{pr}_1$ und $\op{pr}_2$ f"ur die \glqq Projektion
auf die erste beziehungsweise zweite
Komponente\grqq.
\end{Beispiel}

\begin{Bemerkungl}[\textbf{Konstanten und konstante Abbildungen}] 
 Gegeben 
ein festes $c\in Y$
schreiben wir oft auch  kurz 
$c$ f"ur die {\bf konstante Abbildung}\index{konstante Abbildung}
$X\ra Y$ gegeben durch $x\mapsto c$ f"ur alle $ x\in X$. 
Damit verbunden ist die Hoffnung, da"s aus dem Kontext klar wird, ob 
im Einzelfall die
Abbildung $c:X\ra Y$ oder das Element $c\in Y$ gemeint sind.
\end{Bemerkungl}




\begin{Definition}\label{ISB}
Sei $f:X\ra Y$ eine Abbildung.
\begin{enumerate}
\item
$f$ hei"st {\bf injektiv}\index{injektiv!Abbildung} 
oder eine {\bf Injektion}\index{Injektion}, wenn
aus $x \neq x^{\prime}$ folgt $f(x)\neq f(x^{\prime})$. 
Gleichbedeutend ist die Forderung, da"s es f"ur jedes $y\in Y$
h"ochstens ein $x\in X$ gibt mit $f(x)=y$. 
Injektionen
schreibt man oft $\hra$.\index{)4@$\hra$ Injektion}
\begin{figure}[htpb]
\begin{minipage}{0.45\textwidth}
  \includegraphics[width=\textwidth]{SkriptenBilder/BildInjv}
\end{minipage}\hfill
 \begin{minipage}{0.45\textwidth}\centering
Eine  Injektion
\end{minipage}
\end{figure}
\item
$f$ hei"st {\bf surjektiv}\index{surjektiv!Abbildung} oder 
eine {\bf Surjektion}\index{Surjektion}, wenn
es f"ur jedes $y\in Y$ mindestens 
ein $x \in X$ gibt mit $f(x) =y$. Surjektionen
schreibt man manchmal $\sra$.\index{)4@$\sra$ Surjektion}
\begin{figure}[htpb]
\begin{minipage}{0.45\textwidth}
  \includegraphics[width=\textwidth]{SkriptenBilder/BildSurv}
\end{minipage}\hfill
 \begin{minipage}{0.45\textwidth}\centering
Eine  Surjektion
\end{minipage}
\end{figure}
\item
$f$ hei"st {\bf bijektiv}\index{bijektiv!Abbildung} 
oder eine {\bf Bijektion}\index{Bijektion}, wenn
$f$ injektiv und surjektiv ist. Gleichbedeutend ist die Forderung, 
da"s es f"ur jedes $y\in Y$
genau ein $x\in X$ gibt mit $f(x)=y$. 
Bijektionen schreibt man oft $\sira$.\index{)4@$\sira$ Bijektion}
\begin{figure}[htpb]
\begin{minipage}{0.45\textwidth}
  \includegraphics[width=\textwidth]{SkriptenBilder/BildBij}
\end{minipage}\hfill
 \begin{minipage}{0.45\textwidth}\centering
Eine  Bijektion
\end{minipage}
\end{figure}
\end{enumerate}
\end{Definition}

\begin{Definition}\label{KkAa}
Sind drei Mengen $X,Y,Z$ gegeben und dazwischen Abbildungen $f : X \ra Y$
und $g:Y \ra Z$, so definieren wir die 
{\bf Verkn"upfung}\index{Verkn"upfung!von Abbildungen}
unserer\index{)8a@$\circ$ Verkn"upfung!von Abbildungen}  
Abbildungen $f$ und $g$, eine Abbildung $g\circ f:X \ra Z$,
durch
die Vorschrift
$$\begin{array}{rccl}
g \circ f:& X & \ra & Z\\
&x & \mapsto & g(f(x))
\end{array}$$
\end{Definition}
\begin{Bemerkungl}[\textbf{Diskussion der Notation}] 
Die Notation $g\circ f$, sprich \glqq $g$ nach $f$\grqq, 
f"ur \glqq erst $f$, dann $g$\grqq\ 
ist gew"ohnungsbed"urftig, erkl"art sich aber durch die offensichtliche Formel
$(g \circ f) (x) = g(f(x))$. Ich sage, $g\circ f$ entstehe aus $g$ durch
{\bf Vorschalten von $f$}\index{Vorschalten von Abbildung} und
 aus $f$ durch
{\bf Nachschalten von $g$}.\index{Nachschalten von Abbildung}
Oft k"urzt man auch $g\circ f$ mit $gf$ ab. Mit dieser Abk"urzung
mu"s man jedoch sorgsam umgehen, da  im Fall von zwei Abbildungen
$f,g$ von derselben Menge in einen Zahlbereich, etwa $f,g:X\ra \DQ$,  
der Ausdruck $fg$ vielmehr 
f"ur die Abbildung $x\mapsto f(x)g(x)$ reserviert ist,
das sogenannte \glqq punktweise Produkt\grqq\ unserer beiden Funktionen. 
\end{Bemerkungl}

\begin{Beispiel}
  Betrachten wir zus"atzlich zum Quadrieren $q:\DZ \ra \DZ$ die
  Abbildung $t: \DZ \ra \DZ$, $x \mapsto x +1$, so gilt $(q\circ t) (x) =
  (x+1)^{2}$ aber $(t\circ q)(x) = x^{2}+1$. 
\end{Beispiel}








\begin{Bemerkungl}
Ist $X \subset Y$ eine Teilmenge, 
so ist die {\bf Einbettung}\index{Einbettung!einer Teilmenge} oder
{\bf Inklusion}\index{Inklusion} $i:X \ra Y$, $x\mapsto x$ stets injektiv.
Ist $g:Y\ra Z$ eine Abbildung und $X\subset Y$ eine Teilmenge,
so nennen wir
die Verkn"upfung $g\circ i$ von $g$ mit der Inklusion
auch die {\bf Einschr"ankung}\index{Einschr"ankung} von
$g$ auf $X$ und notieren sie $$g\circ i\defp g|X=g|_X:X\ra Z$$
Oft\index{\mid@$f{\mid}X$ Einschr"ankung auf $X$}\index{\mid@$f{\mid}_X$ Einschr"ankung auf $X$}
bezeichnen wir eine Einschr"ankung aber auch einfach mit 
demselben Buchstaben $g$ in der
Hoffnung, da"s der Leser aus dem Kontext erschlie"sen kann, 
welche Abbildung genau gemeint ist.  Das ist  nicht ganz unproblematisch:
So ist etwa unsere Abbildung $q : \DZ \ra \DZ$, $n\mapsto n^{2}$
nicht injektiv, ihre Restriktion $q|_\DN$ zu einer Abbildung $q : \DN \ra \DZ$
ist aber durchaus injektiv.
\end{Bemerkungl}


\begin{Beispiele}
Unsere Abbildung $q : \DZ \ra \DZ$, $n\mapsto n^{2}$ ist weder injektiv
noch surjektiv. Die Identit"at $\op{id} : X \ra X$ ist stets bijektiv.
Sind $X$ und $Y$ endliche Mengen, so gibt es genau dann eine
Bijektion von $X$ nach $Y$, wenn $X$ und $Y$ dieselbe 
Kardinalit"at haben, in Formeln $|X|=|Y|$.  
\end{Beispiele}


\begin{Satz}\label{InSua}
Seien $f:X \ra Y$ und $g :Y \ra Z$ Abbildungen.
\begin{enumerate}
\item
Ist $g\circ f$ injektiv, so ist $f$ injektiv;
\item
Sind $g$ und $f$ injektiv, so auch $g \circ f$.
\end{enumerate}
\end{Satz}
\begin{proof}[Beweis]
"Ubung.
\end{proof}


\begin{Satz}\label{InSuna}%\label{InSu}
Seien $f:X \ra Y$ und $g :Y \ra Z$ Abbildungen.
\begin{enumerate}
\item
Ist $g\circ f$ surjektiv, so ist $g$ surjektiv;
\item
Sind $g$ und $f$ surjektiv, so auch $g\circ f$.
\end{enumerate}
\end{Satz}
\begin{proof}[Beweis]
"Ubung.
\end{proof}


\begin{Bemerkungl}[\textbf{Umkehrabbildung}] 
Ist $f: X \sira Y$ eine bijektive Abbildung,
so ist offensichtlich die Menge  $\{(f(x),x)\in Y\times X\mid x\in X\}$ 
im Sinne von \ref{DFAa} 
eine Abbildung oder, vielleicht klarer, der Graph einer
Abbildung $Y\ra X$.
Diese Abbildung in die Gegenrichtung  hei"st die
{\bf Umkehrabbildung}\index{Abbildung!Umkehrabbildung} oder 
\defind{Umkehrfunktion}\index{Funktion!Umkehrfunktion} oder
auch die 
{\bf inverse Abbildung}\index{Abbildung!inverse} zu $f$
und wird mit $f^{-1} : Y \ra X$ bezeichnet. Offensichtlich ist
mit $f$ auch $f^{-1}$ eine Bijektion.\index{)6aa@$f^{-1}$ Umkehrabbildung} 
\end{Bemerkungl}
\begin{Bemerkungl}[\textbf{Diskussion der Notation}]
Mit dem vorhergehenden haben wir schon eine dritte
m"ogliche Bedeutung f"ur das Symbol $f^{-1}$ kennengelernt. Was im Einzelfall 
 gemeint ist, gilt es aus dem Kontext zu erschlie"sen.
\end{Bemerkungl}
\begin{Beispiel}
Die Umkehrabbildung unserer Bijektion
$t:\DZ\ra\DZ$, $x\mapsto x+1$ ist die Abbildung 
$t^{-1}:\DZ\ra\DZ$, $x\mapsto x-1$.
\end{Beispiel}

\begin{Satz}[\textbf{Bedeutung der Fakult"at}]
Sind $X$ und $Y$ zwei Mengen mit je $n$ Elementen, so gibt es genau $n!$
bijektive Abbildungen $f:X \sira Y$.\label{BdFa}
\end{Satz}
\begin{proof}[Beweis]
Sei $X =\{x_{1},\ldots , x_{n}\}$.
Wir haben $n$ M"oglichkeiten, ein Bild f"ur $x_{1}$ auszusuchen, dann
noch $(n-1)$ M"oglichkeiten, ein Bild f"ur $x_{2}$ auszusuchen, und so
weiter, bis schlie"slich nur noch $1$ Element von $Y$ als m"ogliches
Bild von $x_{n}$ in Frage kommt. Insgesamt gibt es also $n(n-1) \cdots
1 = n!$ M"oglichkeiten f"ur $f$. Da wir $0!=1$ vereinbart hatten, stimmt unser
Satz auch f"ur $n=0$.
\end{proof}




\subsubsection*{"Ubungen} 
\begin{Ubung}
Gegeben eine Bijektion $f:X\ra Y$ ist $g=f^{-1}$ die einzige
Abbildung $g : Y \ra X$ mit $f\circ g = \op{id}_{Y}$.
Ebenso ist auch  $h=f^{-1}$ die einzige
Abbildung $h : Y \ra X$ mit $h\circ f = \op{id}_{X}$.
\end{Ubung}

\begin{Ubunge}
Gegeben endliche Mengen $X,Y$  gibt es genau $|Y|^{|X|}$ Abbildungen von $X$ nach $Y$ und unter
diesen Abbildungen
sind genau $|Y|(|Y|-1)(|Y|-2)\ldots(|Y|-|X|+1)$ Injektionen.
\end{Ubunge}




\begin{Ubunge}\label{MnMKa}
Sei $X$ eine Menge mit $n$ Elementen und seien 
nat"urliche Zahlen 
$\al_1,\ldots,\al_r\in\DN$
gegeben mit $n=\al_1+\ldots+\al_r$. Man zeige: Es gibt genau
$n!/(\al_1!\cdots\al_r!)$ Abbildungen $f:X\ra\{1,\ldots,r\}$, die  
jedes $i$ genau
$\al_i$-mal als Wert annehmen, in Formeln
$$\frac{n!}{\al_1!\cdots\al_r!}=\op{card} \{f\mid
|f^{-1}(i)|=\al_i\text{ f"ur }i=1,\ldots r\}$$
\end{Ubunge}
\begin{Bemerkunge}
Manche Autoren bezeichnen die Zahlen aus der vorherigen "Ubung 
\ref{MnMKa} als
\defnoind{Multinomial\-koeffizienten}\index{Multinomialkoeffizient}
und verwenden die Notation 
$${n \choose {\al_1;\ldots;\al_r}}\pdef \frac{n!}{\al_1!\cdots\al_r!}$$
Mich "uberzeugt diese Notation nicht, da sie im Gegensatz zur
Notation f"ur Binomialkoeffizienten  nichts
k"urzer macht.
\end{Bemerkunge}

\begin{Ubunge}
Man zeige die Formel
$$(x_1+\ldots +x_r)^n=
\sum_{\al_1+\ldots+\al_r=n}\frac{n!}{\al_1!\cdots\al_r!}
x_1^{\al_1}\cdots x_r^{\al_r}$$
Hier ist zu verstehen, da"s wir f"ur alle $\al_1,\ldots,\al_r\in\DN$
mit $\al_1+\ldots+\al_r=n$ den angegebenen Ausdruck nehmen und alle diese
Ausdr"ucke aufsummieren.
\end{Ubunge}


\begin{Ubunge}\label{MuMi}
Sei $X$ eine Menge mit $n\geq 1$ Elementen und  sei $m$ eine nat"urliche Zahl.
Man zeige, da"s es genau ${n+m-1 \choose n-1}$ 
Abbildungen $f:X\ra \DN$ gibt mit 
$\sum_{x\in X}f(x)=m$. Hinweis: Man denke sich $X=\{1,2,\ldots,n\}$
und veranschauliche sich dann $f$ als eine Folge auf $f(1)$ Punkten gefolgt von
einem Strich gefolgt von $f(2)$ Punkten gefolgt von
einem Strich und so weiter, insgesamt also 
eine Folge aus $n+m-1$ Symbolen, davon $m$ Punkten und 
$n-1$ Strichen. 
\end{Ubunge}
\begin{figure}[htpb]\centering
\includegraphics[height=0.25\textheight]{SkriptenBilder/BildKoKi}\\[2mm]
\noindent
Eine Abbildung $f:\{1,2,\ldots,n\}\ra \DN$ im Fall $n=6$ mit 
Wertesumme $m=10$ und die Veranschaulichung nach der Vorschrift aus "Ubung
\ref{MuMi} als Folge bestehend aus $m$ Punkten und $n-1$ Strichen.
\end{figure}
\subsection{Mengen mit Verkn"upfung}\label{MVka}



\begin{Definition}
Eine {\bf Verkn"upfung $\top$ auf einer 
Menge $X$}\index{Verkn"upfung!auf einer Menge}
ist eine Abbildung
$$\begin{array}{ccc}
 X \times X&\ra& X\\
 (x,y) &\mapsto& x \top y
\end{array}$$
Jedem angeordneten Paar $(x,y)$ mit $x,y\in X$ wird also ein 
Element $(x\top y)\in X$ zugeordnet. Eine Menge mit Verkn"upfung hei"st ein
{\bf Magma}.\index{Magma}
\end{Definition}
\begin{figure}[htpb]
\begin{minipage}{0.45\textwidth}
  \includegraphics[width=\textwidth]{SkriptenBilder/BildVT}
\end{minipage}\hfill
 \begin{minipage}{0.45\textwidth}\centering
Man kann Verkn"upfungen auf endlichen Mengen darstellen durch ihre 
\defind{Verkn"upfungstafel}. Hier  die Verkn"upfungstafel
der Verkn"upfung $\op{min}$ auf der Menge  $\{0,1,2,3,4\}$.
Man mu"s  sich dazu einigen, ob im K"astchen aus der Spalte  $m$ und 
der Zeile  $n$ nun $m\top n$ oder vielmehr $n\top m$ stehen soll. Bei einer kommutativen Verkn"upfung wie $\op{min}$ macht das aber kinen Unterschied.
\end{minipage}
\end{figure}

\begin{Bemerkungl}
  Das unverf"angliche Symbol $\top$ benutze ich, um
mich an dieser Stelle noch nicht  
implizit auf
einen der Standardf"alle Addition oder Multiplikation festlegen zu m"ussen.
\end{Bemerkungl}
\begin{Beispiele}
\begin{enumerate}
\item
Die Addition von ganzen Zahlen ist eine Verkn"upfung
$$\begin{array}{cccc}
\DZ \times \DZ&\ra&  \DZ\\
 (m,n) &\mapsto& m + n
\end{array}$$
\item
Die Multiplikation von ganzen Zahlen ist eine Verkn"upfung
$$\begin{array}{ccc}
\DZ \times \DZ&\ra&  \DZ\\
 (m,n) &\mapsto& m \cdot n
\end{array}$$
\item\label{Verkma}
Die Zuordnung $\min$,\index{min} 
die jedem Paar von nat"urlichen Zahlen die kleinere
zuordnet, wenn sie verschieden sind, und eben diese Zahl $\min(n,n)=n$, 
wenn sie gleich sind, ist eine
Verkn"upfung
$$\begin{array}{cccc}
\min :& \DN \times \DN&\ra& \DN\\
 &(m,n) &\mapsto& \min(m , n)
\end{array}$$
\item
Die Subtraktion von ganzen Zahlen ist eine Verkn"upfung
$$\begin{array}{ccc}
\DZ \times \DZ&\ra&  \DZ\\
 (m,n) &\mapsto& m - n
\end{array}$$
\item
Logische Operationen  wie \glqq und\grqq, \glqq oder\grqq,  \glqq impliziert\grqq\ 
k"onnen   als Verkn"upfungen auf der zweielementigen Menge
$\{\op{Wahr},\op{Falsch}\}$ aufgefa"st werden. Die 
 zugeh"origen Verkn"upfungstabellen hei"sen 
{\bf Wahrheitstafeln}.\index{Wahrheitstafel}
Bei einem formalen Zugang werden diese Tafeln, wie sie f"ur \glqq und\grqq\  und
\glqq oder\grqq\  
auf der vorhergehenden Seite zu finden sind, zur 
Definition der jeweiligen Begriffe.
\end{enumerate}
\label{Verka}
\end{Beispiele}
\begin{figure}[htpb]
    \includegraphics[width=0.4\textwidth]{SkriptenBilder/Bildund}\hfill
\includegraphics[width=0.4\textwidth]{SkriptenBilder/Bildoder}
\\[2mm]
\centering
Die Wahrheitstafeln
f"ur \glqq und\grqq\  und \glqq oder\grqq.
Gemeint ist hier wie stets in der 
Mathematik das \glqq nichtausschlie"sende oder\grqq.
Sagen wir, es gelte  $A$ oder $B$,
 so ist insbesondere
auch erlaubt, da"s beides gilt. Bei der Wahrheitstafel f"ur
das \glqq ausschlie"sende oder\grqq\  m"u"ste oben links als 
Verkn"upfung von \glqq Wahr\grqq\  mit \glqq Wahr\grqq\  ein \glqq Falsch\grqq\  stehen. 
\end{figure}



\begin{Bemerkungl}
Eine Verkn"upfung $\top$ auf einer Menge $X$ hei"st
{\bf assoziativ},\index{assoziativ} wenn gilt
$$x \top (y\top z) = (x \top y) \top z \quad \forall x,y,z \in X$$
Im Fall einer assoziativen Verkn"upfung  liefern auch ungeklammerte 
Ausdr"ucke der
Form $x_1\top x_2\top \ldots \top x_n$  wohlbestimmte Elemente von
$X$, und zwar ist genauer das Resultat unabh"angig davon, wie wir
die Klammern setzen. Wir f"uhren das hier nicht weiter aus
und verweisen stattdessen auf \eref{VHHO}{GR}. 
\end{Bemerkungl}

\begin{Bemerkungl}
Eine Verkn"upfung $\top$ auf einer Menge $X$ hei"st {\bf kommutativ}\index{kommutativ!Verkn"upfung} oder
 {\bf abelsch}\index{abelsch!Verkn"upfung}, wenn gilt
 $$x \top y = y \top x \quad \forall x,y\in X$$
  Die Bezeichnung \glqq abelsch\grqq\ ehrt den norwegischen Mathematiker
  Nils Henrik Abel.
\end{Bemerkungl}


\begin{Beispiele}
  Die Addition und Multiplikation auf $\DZ$ sind assoziativ und kommutativ.
  F"ur das Minimum in $\DN$ gilt dasselbe. Die Subtraktion auf $\DZ$ ist
  weder kommutativ noch assoziativ. 
\end{Beispiele}
\begin{Definition}
Gegeben eine Menge mit Verkn"upfung $(X,\top)$ 
 hei"st ein Element $e\in X$ ein \defind{neutrales Element} von $(X,\top)$,
wenn gilt $$e \top x=x \top e = x \quad
\forall x \in X$$
\end{Definition}
\begin{Bemerkungl}[\textbf{Eindeutigkeit neutraler Elemente}] 
Gegeben eine Menge mit Ver\-kn"up\-fung $(X,\top)$ kann
es h"och\-stens ein neutrales Element $e$ geben, denn f"ur jedes weitere
Element $e'$ mit $e' \top x=x \top e' = x \quad \forall x \in X$
haben wir $e'=e'\top e=e$. Wir d"urfen also den bestimmten Artikel verwenden
und in einer Menge mit Verkn"upfung\label{eBNa}
von \emph{dem} neutralen Element reden und es mit $e_X$ bezeichnen.  
\end{Bemerkungl}

\begin{Beispiele} Das neutrale Element von $(\DZ,+)$ ist die Null
  $0\in\DZ$.  Das neutrale Element von $(\DZ,\cdot)$ ist die Eins
  $1\in\DZ$. 
\end{Beispiele}

\begin{Definition}
Ein \defind{Monoid}
ist eine Menge mit einer assoziativen Ver\-kn"up\-fung,
in der es ein neutrales Element gibt.\label{KNeua}
\end{Definition}


\begin{Bemerkungl}
  Das Wort \glqq Monoid\grqq\  ist wohl 
von griechisch \glqq $\mu o\nu o\varsigma$\grqq\  f"ur \glqq allein\grqq\ 
abgeleitet: Ein Monoid besitzt nur eine einzige Verkn"upfung.
\end{Bemerkungl}
\begin{Bemerkungl}[\textbf{Gebr"auchliche Notationsschemata f"ur Monoide}]  
(1) Notiert man in einem Monoid $M$ die Verkn"upfung mit dem Symbol $+$,
so notiert man das neutrale Element meist  
$0_M$ oder abk"urzend $0$\index{)0@$0$ neutrales Element f"ur $+$}\index{)0@$0$ neutrales Element f"ur $+$!$0_M$ im Fall von $(M,+)$}  
und nennt es das {\bf Null-Element}
oder abk"urzend die {\bf Null}\index{Null-Element} und spricht von einem
{\bf additiv notierten Monoid}.\index{Monoid!additiv notiertes} 
Nur kommutative Monoide werden additiv notiert.

(2) Notiert man in einem Monoid $M$ die Verkn"upfung mit einem eher
runden Symbol wie
$\cdot$ oder $\circ$ oder $\ast$ oder
auch einfach durch Hintereinanderschreiben,
so notiert man das neutrale Element oft $1_M$\index{)0@$1$ neutrales Element f"ur $\cdot$!$1_M$  im Fall von $(M,\cdot)$} 
oder abk"urzend 
$1$\index{)0@$1$ neutrales Element f"ur $\cdot$} und nennt es das {\bf Eins-Element}
oder abk"urzend die {\bf Eins}\index{Eins-Element} und spricht von einem
{\bf multiplikativ notierten Monoid}.\index{Monoid!multiplikativ notiertes} 
\end{Bemerkungl}


\begin{Beispiele}
Die nat"urlichen Zahlen
bilden mit der Addition ein Monoid $(\DN,+)$
mit neutralem Element $0$\index{)0@$0$ neutrales Element f"ur $+$!nat"urliche Zahl}. Sie bilden\label{Moina} 
 mit der Multiplikation ein Monoid $(\DN,\cdot)$ 
mit neutralem Element $1$.\index{)0@$1$ neutrales Element f"ur $\cdot$!nat"urliche Zahl}
\end{Beispiele}




\begin{Bemerkungl}[\textbf{Iterierte Verkn"upfungen}] 
Sei $(A,\top)$ ein Monoid.\label{nada} 
Ist $n \in \DN$ eine  nat"urliche Zahl
und $a\in A$,
so schreiben wir
$$ n^{\top}a\pdef
\underset{\text{$n$-mal}}{\underbrace{a\top a\top \ldots\top a}} 
$$ f"ur $n\geq 1$  und setzen erg"anzend $0^{\top}a\pdef e_A$.
Dann gelten offensichtlich f"ur alle $m,n\in\DN$ und $a,b\in A$ mit $a\top b=b\top a$ die Regeln
\begin{enumerate}
  \item
    $(n+m)^{\top}a = (n^{\top} a) \top (m^{\top}a)$
  \item
    $(nm)^{\top}a = n^{\top}(m^{\top}a)$
  \item
     $n^\top(a\top b)=(n^\top a)\top(n^\top b)$
\end{enumerate}
\end{Bemerkungl}
\begin{Beispiel}[\textbf{Iterieren in additiv notierten Monoiden}]
  Im Fall additiv notierter Monoide schreibt man statt $n^\top a$ meist $na$.
  Unsere drei Regeln werden dann $(n+m)a=(na)+(ma)$, $(nm)a=n(ma)$ und
  $n(a+b)=(na)+(nb)$ und unsere Konvention $0^\top a=e_M$ nimmt die
  Gestalt $0a=0_M$ an.\label{ima}  Wenn ich es genau nehmen will, schreibe ich in diesem Fall $n^+a$ statt $na$. 
\end{Beispiel}
\begin{Beispiel}[\textbf{Iterieren in multiplikativ notierten Monoiden}]
  Im Fall multiplikativ notierter
  Monoide schreibt man statt $n^\top a$ meist $a^n$.
  Unsere drei Regeln werden dann $a^{n+m}=(a^n)(a^m)$, $a^{nm}=(a^n)^m$ und
  $(ab)^n=(a^n)(b^n)$ falls $ab=ba$
  und unsere Konvention $0^\top a=e_M$ nimmt die
  Gestalt $a^0=1_M$ an.\label{imn}  
\end{Beispiel}

\begin{Bemerkungl} Die  nat"urlichen, ja die ganzen
  Zahlen, ja sogar die rationalen Zahlen mit Multiplikation und Addition nehmen wir hier als gegeben hin
  ebenso wie die Tatsache, da"s in diesem Fall die $n$-fach iterierte Addition gerade die Multiplikation ist.  Den Aufbau dieser Strukturen aus der
  Mengenlehre diskutieren wir erst in \eref{NatZ}{LA1}.
\end{Bemerkungl}

   
\begin{Definition}
\begin{enumerate}
\item
Ist $(M,\top)$ ein Monoid und $a\in M$ ein Element,
so nennen wir ein weiteres Element $\bar{a} \in M$ 
{\bf invers}\index{invers!in Monoid} 
{\bf zu} $a$, wenn gilt 
$a \top \bar{a}=e=\bar{a} \top a$ f"ur $e\in M$ das neutrale Element
unseres Monoids. Ein Element eines Monoids, das ein Inverses besitzt, hei"st
{\bf invertierbar};\index{invertierbar}
\item
Eine {\bf Gruppe}\index{Gruppe}
ist ein Monoid, in dem jedes Element 
ein Inverses besitzt;
\item
Eine {\bf kommutative Gruppe} oder  
{\bf abelsche Gruppe}\index{abelsch!Gruppe} ist eine Gruppe,
deren Verkn"upfung kommutativ ist. 
\end{enumerate}
\label{DeGra}
\end{Definition}
\begin{Beispiele}
Von unseren Beispielen \ref{Verka} f"ur Mengen mit  Verkn"upfung
 oben ist nur
$(\DZ,+)$ eine Gruppe, und diese Gruppe ist kommutativ.
Ein anderes Beispiel f"ur eine kommutative 
Gruppe ist die Menge 
 $\DQ$ der rationalen Zahlen mit der Addition als
Verkn"upfung, ein weiteres die Menge
$\DQ\backslash \{0\}$ der
von Null verschiedenen rationalen Zahlen mit der Multiplikation als
Verkn"upfung. Auch jedes einelementige Monoid ist eine Gruppe. 
\end{Beispiele}
\begin{Bemerkungl}
Der Begriff einer \glqq Gruppe\grqq\  wurde von \'{E}variste Galois (1811-1832) in die
Mathematik eingef"uhrt.
Er verwendet den Begriff \glqq Gruppe von Transformationen\grqq\ 
sowohl in der Bedeutung einer
\glqq Menge von bijektiven Selbstabbildungen einer gegebenen Menge\grqq\  als auch
in der Bedeutung einer
\glqq Menge von bijektiven Selbstabbildungen einer gegebenen Menge,
die abgeschlossen ist unter Verkn"upfung und Inversenbildung\grqq,  und
die damit in der Tat ein Beispiel f"ur eine 
Gruppe im Sinne der obigen Definition bildet.
Unsere 
obige Definition \ref{DeGra} 
geht auf eine Arbeit von Arthur Cayley aus dem Jahre 1854 mit dem Titel
\glqq On the theory of groups as depending on the symbolic equation $\theta^n=1$\grqq\ 
zur"uck und wurde damit formuliert, bevor Cantor die
Sprache der Mengenlehre entwickelte.
Die Terminologie \glqq abelsche Gruppe\grqq\  wurde zu 
Ehren des norwegischen Mathematikers
Niels Hendrik Abel eingef"uhrt.
\end{Bemerkungl}

\begin{Lemma}
Jedes Element eines Monoids besitzt h"ochstens ein Inverses.  
\end{Lemma}
\begin{proof}
Aus $a \top \bar{a}=e$
und $b \top a=e$  folgt durch Anwenden von $b\top$ auf die
erste Gleichung mit dem Assoziativgesetz sofort $\bar{a}=b$.
\end{proof}
\begin{Bemerkungl}
Wir d"urfen also den bestimmten Artikel benutzen und von 
nun an von \emph{dem} Inversen eines Elements eines Monoids und insbesondere
auch
einer Gruppe reden.  
\end{Bemerkungl}
\begin{Beispiel}[\textbf{Invertieren in additiv notierten Monoiden}]
  Im Fall additiv notierter Monoide schreibt man statt $\bar{a}$ meist $-a$
  und nennt dieses \glqq additive Inverse\grqq\ das {\bf Negative von $a$}.
  \index{Negatives} "Ublich ist in diesem Kontext auch die Abk"urzung
  $a-b\pdef a+(-b)$. 
\end{Beispiel}
\begin{Beispiel}[\textbf{Invertieren in multiplikativ notierten Monoiden}]
  Im Fall multiplikativ notierter
  Monoide bleiben wir vorerst bei unserer Notation  $\bar{a}$.
 \end{Beispiel}
\begin{Bemerkungl}[\textbf{Zweimaliges Invertieren}]
  Gegeben ein invertierbares Element ist offensichtlich
auch sein Inverses invertierbar und  das Inverse des Inversen ist wieder das
urspr"ungliche Element, in Formeln $\bar{\bar{a}}=a$. In additiver Notation
liest sich das $-(-a)=a$.\label{ZwI} 
\end{Bemerkungl}

\begin{Lemma}
Sind $a$ und $b$  invertierbare
Elemente eines Monoids, so ist auch $a\top b$ invertierbar 
mit  Inversem $\overline{(a\top b)}=\bar{b}\top\bar{a}$. 
\end{Lemma}
\begin{proof}
In der Tat rechnen wir
schnell
$(a\top b)\top(\bar{b}\top\bar{a})=e=(\bar{b}\top\bar{a})\top(a\top b)$. 
Diese Formel ist auch aus dem t"aglichen
Leben vertraut:
Wenn man sich morgends zuerst die Str"umpfe anzieht und dann die Schuhe,
so mu"s man abends zuerst die Schuhe ausziehen und dann die Str"umpfe.
\end{proof}
\begin{Bemerkungl} In additiver Notation liest sich das
  $-(a+b)=(-b)+(-a)$ oder, da additiv notierte Monoide stets als abelsch
  angenommen werden, gleichbedeutend $-(a+b)=(-a)+(-b)$.
\end{Bemerkungl}


\begin{Bemerkungl}[\textbf{Gruppe der invertierbaren Elemente eines Monoids}]
  Die invertierbaren Elemente eines Monoids bilden offensichtlich stets
  eine Gruppe.
  F"ur die Gruppe der invertierbaren Elemente eines multiplikativ
  notierten Monoids $M$ verwenden wir die Notation $M^\times$.
\end{Bemerkungl}


\begin{Bemerkungl}[\textbf{Negativ iterierte Verkn"upfung invertierbarer Elemente}]
Ist $(A,\top)$ ein Monoid und $a\in A$ 
invertierbar, so erweitern wir unsere\label{naaa} 
Notation $n^\top a$ aus \ref{nada} weiter auf alle ganzen Zahlen $n \in \DZ$,
indem wir  f"ur $n$  negativ setzen 
$ n^{\top} a \pdef (-n)^{\top} \bar{a}$.
Dann gelten offensichtlich sogar f"ur alle $m,n\in\DZ$ und $a,b\in A^\times$ mit $a\top b=b\top a$ 
die f"ur $m,n\in\DN$ bereits aus \ref{nada} bekannten Regeln
\begin{enumerate}
  \item
    $(n+m)^{\top}a = (n^{\top} a) \top (m^{\top}a)$
  \item
    $(nm)^{\top}a = n^{\top}(m^{\top}a)$
  \item
     $n^\top(a\top b)=(n^\top a)\top(n^\top b)$
\end{enumerate}
\end{Bemerkungl}

\begin{Bemerkungl}[\textbf{Negativ iterierte Verkn"upfung in additiver Notation}]
  Im Fall additiv notierter Monoide erweitern wir unsere Notation $na\pdef n^\top a$ f"ur Elemente $a$ mit Negativem auf alle $n\in \DZ$ und finden f"ur jedes Element $a$ mit Negativem insbesondere $(-1)a=-a$ sowie  die
  Regeln  $(n+m)a=(na)+(ma)$, $(nm)a=n(ma)$ und
  $n(a+b)=(na)+(nb)$ 
  f"ur alle $n,m\in\DZ$ und alle Elemente $a,b$ mit Negativem. Wenn ich es
  genau nehmen will, schreibe ich auch hier $n^+a$. 
\end{Bemerkungl}
\begin{Bemerkungl}[\textbf{Negativ iterierte Verkn"upfung in multiplikativer Notation}]
  Im Fall multiplikativ notierter Monoide erweitern wir unsere Notation $a^n\pdef n^\top a$ f"ur invertierbare Elemente $a$  auf alle $n\in \DZ$
und finden f"ur jedes
  invertierbare Element $a$  insbesondere $a^{-1}=\bar{a}$. Das nehmen wir
  hinfort als unsere "ubliche
  Notation f"ur multiplikative Inverse. Unsere drei Regeln erhalten dann die
  Gestalt $a^{n+m}=(a^n)(a^m)$, $a^{nm}=(a^n)^m$ und
  $(ab)^n=(a^n)(b^n)$  f"ur alle $n,m\in\DZ$  und $a,b$  invertierbar
  mit $ab=ba$. 
\end{Bemerkungl}

\begin{Definition}
  Seien $(A,\top)$ und $(B,\perp)$ Magmas. Ein {\bf Homomorphismus
  von Magmas}\index{Magmahommorphismus} ist eine Abbildung
  $\varphi:A\ra B$ mit
  $$\varphi(x\top y)=\varphi(x)\perp \varphi(y)\quad \forall x,y\in A$$
\end{Definition}
\begin{Definition}
  Seien $(A,\top)$ und $(B,\perp)$ Monoide. Ein {\bf Homomorphismus
    von Monoiden}\index{Monoidhommorphismus} ist ein Magmahomomorphismus
  $\varphi:A\ra B$, der das neutrale Element auf das neutrale Element abbildet.
\end{Definition}
\begin{Definition}  Seien $(A,\top)$ und $(B,\perp)$ Gruppen. Ein {\bf Homomorphismus
    von Gruppen}\index{Gruppenhommorphismus} ist ein Monoidhomomorphismus
  $\varphi:A\ra B$.
\end{Definition}
\begin{Beispiele}\label{ItMok} 
  \begin{enumerate}
  \item
  Die Multiplikation mit einer festen Zahl $a\in \DZ$ ist ein
  Gruppenhomomorphismus $(a\cdot):(\DZ,+)\ra (\DZ,+)$.
\item
  Das Potenzieren
  $n\mapsto q^n$ 
  ist f"ur alle $q\in \DQ$ ein Monoidhomomorphismus $(\DN,+)\ra (\DQ,\cdot)$
  und f"ur $q\neq 0$ sogar ein Gruppenhomomorphismus $(\DZ,+)\ra (\DQ,\cdot)$.
  \item 
  Allgemeiner ist f"ur jedes Element $q$ eines Monoids $(M,\top)$ das
  Iterieren $n\mapsto n^\top q$ ein Monoidhomomorphismus
  $(\DN,+)\ra (M,\top)$, ja der einige  Monoidhomomorphismus mit $1\mapsto q$, und f"ur invertierbares $q$ sogar ein Monoidhomomorphismus $(\DZ,+)\ra (M,\top)$, wieder der einzige mit $1\mapsto q$.
  \end{enumerate}
\end{Beispiele}
\begin{Bemerkungl} Ein {\bf Isomorphismus} bezeichnet einen bijektiven Homomorphismus, dessen Umkehrabbildung auch ein Homomorphismus f"ur die
  jeweiligen Strukturen ist. Im Fall von Magmas oder
  Monoiden ist jeder bijektive Homomorphismus ein Isomorphismus. Ein erstes Beispiel f"ur einen bijektiven Homomorphismus, der kein Isomorphismus ist,
  lernen wir in \ref{htM} im Zusammenhang mit teilgeordneten Mengen kennen.
\end{Bemerkungl}

\subsubsection*{"Ubungen}
\begin{Ubung}
  In einer Gruppe $(G,\top)$ ist das neutrale Element $e\in G$ das
  einzige Element $x\in G$ mit $x\top x=x$. Jeder Magmahomomorpismus von
  einem Monoid in eine Gruppe ist bereits ein Monoidhomomorphismus.\label{MaMoh} 
\end{Ubung}
 \begin{Ubung}
    Sei $Z$ eine Menge. Das Schneiden von Teilmengen ist eine Verkn"upfung
$$\begin{array}{cccc}
  \cap :& \cal{P}(Z) \times \cal{P}(Z)&\ra& \cal{P}(Z)\\
  &(A,B) &\mapsto& A\cap B
\end{array}$$
auf der Potenzmenge. Dasselbe gilt f"ur die Vereinigung und das Bilden
der Differenzmenge. Welche dieser Verkn"upfungen sind kommutativ oder 
assoziativ? Welche besitzen neutrale Elemente?
\end{Ubung}
\begin{Ubunge}
  Man gebe die Wahrheitstafeln f"ur $\RA$ und $\IFF$ an. 
Bezeichne weiter $\neg: \{\op{Wahr},\op{Falsch}\}\ra 
\{\op{Wahr},\op{Falsch}\}$ die \glqq Verneinung\grqq.
 Man\index{)0a@$\neg$ Verneinung} zeige, da"s
die Formel
$$(A\RA B)\IFF((\neg B)\RA (\neg A)) $$
beim Einsetzen beliebiger Wahrheitswerte aus $\{\op{Wahr},\op{Falsch}\}$
f"ur $A$ und $B$ stets
den Wert $\op{Wahr}$ ausgibt.
\end{Ubunge}

\begin{Ubung}\label{EIGa}
Ein Element $a$ eines Monoids $M$ ist invertierbar genau dann,
wenn es $b,c\in M$ gibt mit $b\top a=e=a\top c$ f"ur $e$ das neutrale
Element.
\end{Ubung}
\begin{Ubung}[\textbf{K"urzen}]
Sind $a,b,c$ Elemente eines Monoids und ist $a$ invertierbar, so folgt aus
$a\top b=a\top c$ bereits $b=c$. Ebenso folgt  aus 
$b\top a=c\top a$ bereits $b=c$.\label{KGra} 
\end{Ubung}


\begin{Ubung}
  Gegeben eine Menge $Z$ ist das Bilden des Komplements ein
Monoidhomomorphismus $(\mathcal P(Z),\cap)\ra (\mathcal P(Z),\cup)$.
\end{Ubung}


\begin{Ubung}
  Jeder Monoidhomomorphismus $M\ra N$ bildet invertierbare Elemente auf invertierbare Elemente ab und induziert so einen
  Gruppenhomomorphismus $M^\times\ra N^\times$.\label{muga} 
\end{Ubung}

\begin{Ubung}
  Jeder Monoidhomomorphismus $\varphi:(M,\top)\ra (N,\perp)$ kommutiert mit
  dem Iterieren, in Formeln $\varphi(n^\top x)=n^\perp(\varphi(x))$ f"ur alle $n\in\DN, x\in M$\label{mugv}  und ebenso f"ur alle $n\in\DZ, x\in M^\times$.
\end{Ubung}

\subsection[K"orper im Sinne der Algebra]{K"orper im Sinne der Algebra}
\label{kloia}\begin{Bemerkungl}
  Die algebraische Struktur eines K"orpers wird den Hauptbestandteil
unseres Axiomensystems f"ur die reellen Zahlen in \ref{ReZ}
bilden. Gleichzeitig ist sie die Grundlage f"ur die Modellierung des 
Raums unserer Anschauung in der linearen Algebra.  
\end{Bemerkungl}
\begin{Definition} 
Ein {\bf Ring}\index{Ring} $(R,+, \cdot)$  ist eine 
Menge $R$ mit zwei
Verkn"upfungen, 
 genannt die {\bf Addition}  $+$ und die {\bf Multiplikation} $\cdot $
des Rings, derart da"s die folgenden drei Bedingungen erf"ullt sind:\label{KAxa}
\begin{enumerate}
\item
$(R,+)$ ist eine abelsche Gruppe;
\item
  $(R,\cdot)$ ist ein
  Monoid;
\item
Es gelten die beiden {\bf Distributivgesetze}\index{Distributivgesetz!bei Ring}
$$\begin{array}{lll}
  a\cdot (b+c)&=&(a\cdot b) + (a\cdot c) \quad \forall
  a,b,c \in R\\
  (b+c)\cdot a&=&( b\cdot a) + ( c\cdot a) \quad \forall
a,b,c \in R
\end{array}
$$
\end{enumerate}
Ein Ring, dessen Multiplikation kommutativ ist, hei"st ein
{\bf kommutativer Ring} und bei uns k"urzer auch {\bf Kring}.  
  Die Gruppe $(R,+)$ hei"st die {\bf additive Gruppe} des Rings.
\end{Definition}
\begin{Beispiel} Die ganzen Zahlen $(\DZ,+,\cdot)$ bilden einen
  kommutativen Ring. Die einelementige Menge ist mit der einzig
  m"oglichen Verkn"upfung als Addition und Multiplikation ein Ring, der
  {\bf Nullring}. 
\end{Beispiel}

\begin{Definition}
  Ein {\bf K"orper}\index{K"orper} $(K,+, \cdot)$  ist ein
  kommutativer Ring, dessen multiplikativ invertierbare Elemente genau alle
  vom neutralen Element $0_K$ von $(K,+)$ verschiedenen Elemente sind, in Formeln\label{defK}  $$(K,\cdot)^\times=K\backslash\{0_K\}$$
\end{Definition}
\begin{Bemerkungl}
  Das neutrale Element jedes Monoids ist invertierbar,
  folglich mu"s nach unseren Annahmen in einem K"orper $K$ 
  das neutrale Element $1_K$  des multiplikativen Monoids $(K,\cdot)$ von $0_K$
  verschieden sein, in Formeln $$1_K\neq 0_K$$
Die Gruppe invertierbaren Elemente von
$K^\times=(K,\cdot)^\times$ eines K"orpers $K$ hei"st
die {\bf multiplikative Gruppe} des K"orpers.
\end{Bemerkungl}



\begin{Beispiele}
Ein erstes Beispiel  ist der K"orper der
rationalen Zahlen $(\DQ,+,\cdot)$.
Ein anderes Beispiel ist der zweielementige K"orper mit den
durch die Axiome erzwungenen Rechenregeln, der fundamental ist in
der Informatik.
Die ganzen Zahlen $(\DZ,+,\cdot)$ bilden keinen K"orper, da
$(\DZ\backslash\{ 0\},\cdot)$  keine Gruppe ist, da es 
n"amlich in $\DZ\backslash\{ 0\}$ 
nur f"ur $1$ und $-1$ ein multiplikatives Inverses gibt.  
\end{Beispiele}




\begin{Bemerkunge}[\textbf{Ursprung der Terminologie}] 
  Der Begriff \glqq K"orper\grqq\  ist in diesem Zusammenhang wohl zu verstehen als
  \glqq besonders gut unter den verschiedensten Rechenoperationen abgeschlossener
  Zahlbereich\grqq, in Analogie zu geometrischen K"orpern wie Kugeln oder
  Zylindern, die man entsprechend als \glqq besonders gut in sich
  geschlossene Bereiche des Raums\grqq\  ansehen k"onnte.
Die Bezeichnung als \glqq Distributivgesetz\grqq\  r"uhrt daher, da"s 
uns dieses Gesetz erlaubt, 
beim Multiplizieren eines Elements mit einer Summe den
\glqq Faktor auf die Summanden zu verteilen\grqq. Das Wort
\glqq distribution\grqq\  f"ur Verteilung von Nahrungsmitteln und dergleichen 
auf Franz"osisch und Englisch kommt von demselben lateinischen Wortstamm,
auf die auch unsere 
Bezeichnung \glqq Distributivgesetz\grqq\  zur"uckgeht.
\end{Bemerkunge}

\begin{Bemerkungl}[\textbf{Weglassen von Multiplikationssymbolen}] 
Beim Rechnen
mit Buchstaben werden wir meist $ab\pdef a\cdot b $ abk"urzen. 
Das w"are beim Rechnen mit durch Ziffernfolgen dargestellten Zahlen
wenig sinnvoll, da man dann nicht wissen k"onnte, ob $72$ nun als
\glqq Zweiundsiebzig\grqq\  oder vielmehr 
als \glqq Sieben mal Zwei\grqq\  zu verstehen sein soll. Beim Einsetzen von Zahlen f"ur
die Buchstaben m"ussen also wieder Multiplikationssymbole eingef"ugt werden.
\end{Bemerkungl}

\begin{Bemerkunge}[\textbf{Weglassen von Additionssymbolen}] 
  In der Schule und au"serhalb der Mathematik ist es "ublich,
$1+\frac{1}{2}$ mit $1\frac{1}{2}$ abzuk"urzen und \glqq Anderthalb Stunden\grqq\  zu
sagen oder \glqq Dreieinviertel Pfund\grqq. In diesem Fall
wird also ein Additionssymbol weggelassen. Das ist
jedoch in der
h"oheren Mathematik nicht "ublich.   
In der gesprochenen
 Sprache ist es noch viel merkw"urdiger. Neunzehnhundertvierundachzig
versteht jeder, in Symbolen geschrieben sieht
  $9$ $10$ $100$ $4+80$
dahingegen  ziemlich sinnlos aus, 
und statt der "ublichen Interpretation $((9+10)100) +4+80$ w"aren
durchaus  auch andere 
Interpretationen denkbar. 
In der gesprochenen Sprache scheint eher eine Konvention 
befolgt zu werden, nach der die Operationen der Reihe nach auszuf"uhren
sind wie bei einem Taschenrechner, wobei eine Multiplikation gemeint ist,
wenn die zuerst genannte Zahl die Kleinere ist,
und eine Addition, wenn sie die Gr"o"sere ist. 
Nur die Zahlen von $13$ bis $19$ scheinen dieser Regel nicht zu gehorchen.
Kein Wunder, da"s es Erstkl"asslern schwer f"allt, sich den Zahlenraum zu
erschlie"sen, wenn sie zuvor
dieses Dickicht von Konventionen  durchdringen m"ussen.
\end{Bemerkunge}

\begin{Bemerkungl}[\textbf{Punkt vor Strich}] 
Wir vereinbaren
zur Vermeidung von Klammern die Regel
\glqq Punkt vor Strich\grqq, so da"s also zum Beispiel 
unter zus"atzlicher Beachtung unserer Konvention des
Weglassens von Multiplikationssymbolen, in diesem Fall 
das Weglassen des Punktes, das Distributivgesetz
k"urzer in der Form $a(b+c)=ab + ac$ geschrieben werden kann.
\end{Bemerkungl}
\begin{Bemerkungl}[\textbf{Br"uche}] 
  Gegeben ein K"orper $K$ und  Elemente $a,b\in K$ mit $b\neq 0_K$ vereinbaren wir die Notation
  $$\frac{a}{b}\pdef ab^{-1}$$
  Sie werden zur "Ubung zeigen, da"s die "ublichen Regeln der Bruchrechnung
  auch in dieser Allgemeinheit gelten. 
\end{Bemerkungl}

\begin{Lemma}[\textbf{Folgerungen aus den Ringaxiomen}]
  In jedem Ring $R$ gelten die folgenden Aussagen und Formeln:\label{FaR}  
  \begin{enumerate}
  \item
    $a\cdot 0_R=0_R=0_R\cdot a \quad \forall a \in R$   
\item
$ (-1_R)\cdot  a =-a=   a\cdot (-1_R)\quad \forall a \in R$
\item
$(-1_R)  (-1_R) =1_R$
\item
$(-a)(-b)=ab\quad\forall a,b\in R$
\item
$m^+(ab)=(m^+a)b\;$ f"ur alle 
$m\in\DZ$ und $ a,b\in R$.
  \end{enumerate}
\end{Lemma}
\begin{proof}
  \begin{enumerate}
  \item
    $0_R+0_R=0_R\RA (0_R+0_R)\cdot a=0_R\cdot a \RA (0_R\cdot a)+(0_R\cdot a)=0_R\cdot a\RA 0_R\cdot a=0_R$ durch Addieren von $-(0_R\cdot a)$ auf beiden Seiten.
  \item
$a + (-1_R) a = 1_R  a + (-1_R) a = (1_R+(-1_R)) a = 0_R
a =0_R$
und $-a$ ist ja gerade definiert als das eindeutig bestimmte
Element von $R$ mit der Eigenschaft $a+ (-a) =0_R$.
\item
  $(-1_R)(-1_R)=-(-1_R)= 1_R$ als Negatives des Negativen nach \ref{ZwI}.
\item  Um das nachzuweisen ersetzen wir $-a =   a(-1_R)$ und
$-b = (-1_R) b$ und verwenden $(-1_R) (-1_R) =1_R$.
\item
  Das folgt durch wiederholtes Anwenden des Distributivgesetzes. Die
  F"alle $m>0$, $m=0$ und $m<0$ behandelt man am einfachsten separat.
  Alternativ mag man bemerken, da"s nach dem Distributivgsetz f"ur festes $a$ die Abbildung
  $(\cdot b):a\mapsto a b$ ein Monoidhomomorphismus $(R,+)\ra (R,+)$ ist
  und folglich nach "Ubung \ref{mugv} gilt
  \begin{displaymath} n^+(ab)=n^+((\cdot b)(a))=(\cdot b)(n^+a)=(n^+a)b
   \qedhere
  \end{displaymath}
 \end{enumerate}
\end{proof}
   





\begin{Bemerkungl}[\textbf{Binomische Formel}]
F"ur alle $a,b$ in 
einem Ring $R$ mit $ab=ba$ und alle $n\in\DN$ gilt
die binomische Formel\label{BiFoa} 
$$(a+b)^{n} = \sum^{n}_{\nu =0} {n\choose \nu} a^{\nu} b^{n-\nu}$$ %\\
Um das einzusehen pr"uft man, da"s wir bei der Herleitung nach
\ref{BiFoAa}
nur Ring\-axiome und die Eigenschaft $ab=ba$ verwandt haben. Man beachte hierbei unsere Konvention 
$0_R^0=1_R$ aus \ref{imn}, angewandt auf das Monoid $(R,\cdot)$. 
Die Multiplikation mit den Binomialkoeffizienten in dieser Formel
ist zu verstehen als
wiederholte Addition im Sinne der  
Bezeichnungskonvention $na=n^+a$ aus \ref{ima}, 
angewandt auf den Spezialfall der additiven
Gruppe unseres Rings. 
\end{Bemerkungl}
\begin{Bemerkungl}[\textbf{Minus mal Minus gibt Plus}] 
Die Frage, wie das Produkt zweier negativer Zahlen zu bilden sei,
war lange umstritten. Mir scheint der vorhergehende Beweis das
"uberzeugendste Argument f"ur \glqq Minus mal Minus gibt Plus\grqq\ :
Es sagt salopp gesprochen, da"s man diese Regel vereinbaren mu"s,
 wenn man beim Rechnen das Ausklammern  ohne alle Einschr"ankungen 
erlauben will.
\end{Bemerkungl}

  \begin{Bemerkungl}
Den Begriff eines Homomorphismus 
 verwendet man bei Mengen mit mehr als
einer Verkn"upfung analog. Zum Beispiel ist ein 
{\bf Ringhomomorphismus}\index{Ringhomomorphismus}
$\varphi$  von einem Ring $R$ in einen Ring $S$\label{KoIsa}  
definiert als eine Abbildung  $\varphi:R\ra S$  derart, da"s gilt 
$\varphi(a+b)=\varphi(a)+\varphi(b)$ und $\varphi(ab)=\varphi(a)\varphi(b)$
f"ur alle $a,b\in R$ sowie  $\varphi(0_R)=0_S$ und  $\varphi(1_R)=1_S$.
Die Bedingung  $\varphi(0_R)=0_S$ ist nach \ref{MaMoh} an dieser
Stelle sogar "uberfl"ussig.
 In anderen Worten mag man einen Ringhomomorphismus auch
definieren als eine Abbildung, die sowohl f"ur die Addition als auch
f"ur die Multiplikation ein Monoidhomomorphismus ist. Einen Ringhomomorphismus zwischen K"orpern nennt man einen {\bf K"orperhomomorphismus}.
  \end{Bemerkungl}
\begin{Bemerkungl}
  Gegeben ein bijektiver Ringhomomorphismus ist auch seine Umkehrabbildung ein 
Ringhommorphismus und wir d"urfen einen bijektiven Ringhomomorpismus deshalb
einen {\bf Ringisomorphismus} und im Fall von K"orpern einen
{\bf K"orperisomorphismus}
nennen. 
  \end{Bemerkungl}


  
\begin{Satz}[\textbf{Ganze Zahlen und allgemeine Ringe}]
  F"ur jeden Ring $R$ gibt es genau einen Ringhomomorphismus\label{GZAKa}
  $\varphi:\DZ\ra R$. Er wird gegeben durch die Vorschrift $\varphi(n)=n^+1_R$.
\end{Satz}
\begin{proof}
  Um den "Uberblick zu behalten, verwende ich hier die Notation $n^+a$
  statt $na$ f"ur die iterierte Verkn"upfung im Sinne von \ref{naaa}, also
   $n^+a=a+a+\ldots+a$ mit $n$ Summanden im Fall $n\geq 1$. 
  Wir wissen aus \ref{ItMok}, da"s $n\mapsto n^+a$
  f"ur alle $a\in R$ der einzige
  Gruppenhomomorphismus $(\DZ,+)\ra(R,+)$ ist mit $1\mapsto a$.
  F"ur einen Ringhomomorphismus mu"s aber gelten $\varphi(1)=1_R$, also
  mu"s er durch die Formel $\varphi(n)=n^+1_R$ gegeben sein. Es bleibt zu
  zeigen, da"s diese Abbildung $\varphi$
  mit der Multiplikation vertr"aglich ist,
  in Formeln $\varphi(nm)=\varphi(n)\varphi(m)$. Dazu rechnen wir
  $$\begin{array}[b]{llll}
    \varphi(nm)&=&(nm)^+1_R&\text{per definitionem,}\\
    &=&n^+(m^+1_R)&\text{nach der zweiten Iterationsregel \ref{naaa},}\\
    &=&n^+(1_R(m^+1_R))&\text{weil $1_R$ neutral ist in $(R,\cdot)$,}\\
    &=&(n^+1_R)(m^+1_R)&\text{nach der letzten Regel in \ref{FaR},}\\
    &=&\varphi(n)\varphi(m)&\text{per definitionem.}
  \end{array}\qedhere
$$
  \end{proof}
\begin{Bemerkungl} 
  Gegeben ein Ring $R$ und $n\in\DZ$ verwenden wir oft die Abk"urzungen $n^+1_R=n_R=n$. Unser Satz zeigt, da"s es meist nicht so genau darauf ankommt,
  ob $n$ nun eine ganze Zahl oder das Element $n_R$ eines abstrakten Rings bedeutet. Insbesondere k"urzt man eigentlich immer  $0_{R}$ ab durch $0$ und $1_{R}$ durch $1$.  
Man beachte jedoch, da"s f"ur verschiedene ganze Zahlen $n\neq m$ durchaus
$n_R=m_R$ gelten kann: Ist etwa $R=K$ ein K"orper mit zwei Elementen,
so gilt $n_K=0_K$ f"ur gerades $n$ und  $n_K=1_K$ f"ur ungerades $n$.
Vom h"oheren Standpunkt wird das alles  
in \eref{GZAR}{LA1} nocheinmal ausf"uhrlich diskutiert werden. 
\end{Bemerkungl}
\begin{Lemma}[\textbf{Folgerungen aus den K"orperaxiomen}]
  In jedem K"orper $K$ gelten zus"atzlich zu den bereits f"ur
  Ringe bewiesenen Aussagen die folgenden Aussagen und Formeln:
 \begin{enumerate}
\item
$a  b =0_K \;\;\Rightarrow \;\;( a = 0_K \text{ oder } b=0_K)$
\item
$\frac{a}{b}  \frac{c}{d} = \frac{ac}{bd}\;$ f"ur alle 
$a,c\in K$ und $ b,d\in K^\times$
\item
$\frac{ac}{bc} = \frac{a}{b}\;$ f"ur alle 
$ a\in K$ und $ b,c\in K^\times$
\item
$\frac{a}{b} + \frac{c}{d} = 
\frac{ad + bc}{bd}\;$ f"ur alle 
$ a,c \in K$ und $ b,d\in K^\times$
  \end{enumerate}
\label{FKAa}\end{Lemma}

\begin{proof}[Beweis]
\begin{enumerate}
\item
In der Tat folgt aus
$(a \neq 0_K \text{ und } b \neq 0_K)$ schon $(a  b \neq 0_K)$ nach den
K"orperaxiomen.
\item
Das ist klar.
\item
Das ist klar.
\item
Das wird bewiesen, indem man die Br"uche auf einen Hauptnenner bringt
und das Distributivgesetz anwendet.\qedhere
\end{enumerate}
\end{proof}

 
 


\subsubsection*{"Ubungen} 
\begin{Ubung}
Jeder Ring $R$ mit $0_R=1_R$ hat nur ein einziges Element.
\end{Ubung}
  \begin{Ubung}\label{KK2a}
Ist $K$ ein K"orper derart, da"s es kein $x \in K$ gibt mit
$x^{2} = -1$, so kann man die Menge $K\times K=K^{2}$ 
zu einem K"orper machen, indem man
die Addition und Multiplikation definiert durch
$$\begin{array}{ccc}
(a,b) + (c,d) & \pdef& (a+c, b+d)\\
(a,b) \cdot (c,d) &\pdef& (ac -bd, ad + bc)
\end{array}$$
Die Abbildung $K \ra K^{2}$, $a \mapsto (a,0)$ ist dann 
ein K"orperhomomorphismus.
K"urzen wir $(a,0)$ mit $a$ ab und setzen $(0,1)=\op{i}$, so gilt
$\op{i}^{2} = -1$ und $(a,b) = a + b\op{i}$ und die Abbildung
$a + b\op{i}\mapsto a - b\op{i}$ ist ein K"orperisomorphismus
$K^2\sira K^2$.
\end{Ubung} 
\begin{Bemerkungl}\label{KRCCa}
  Auf die in der vorhergehenden
"Ubung \ref{KK2a} erkl"arte 
Weise k"onnen wir etwa aus dem K"orper $K=\DR$ der \glqq reellen Zahlen\grqq,
  sobald wir ihn kennengelernt haben, direkt den K"orper $\DC$ der 
{\bf komplexen
  Zahlen}\index{komplexe Zahlen} konstruieren. 
Unser K"or\-per\-iso\-mor\-phis\-mus gegeben durch die Vorschrift 
$a + b\op{i}\mapsto a - b\op{i}$ hei"st in diesem Fall die
{\bf komplexe Konjugation}\index{komplexe Konjugation} 
und wird auch $z\mapsto \bar{z}$\index{)6a@$\bar{z}$ komplexe Konjugation}
notiert.
 Man beachte, wie m"uhelos das alles in der Sprache der
  Mengenlehre zu machen ist.  Als die komplexen Zahlen erfunden wurden, gab es
  noch keine Mengenlehre und beim Rechnen beschr"ankte man sich auf das
  Rechnen mit \glqq reellen\grqq\  Zahlen, ja selbst das Multiplizieren zweier
  negativer Zahlen wurde als eine fragw"urdige Operation angesehen, und das
  Ziehen einer Quadratwurzel aus einer negativen Zahl als eine rein imagin"are
  Operation. In gewisser Weise ist es das ja auch geblieben, aber die
  Mengenlehre liefert eben unserer Imagination eine wunderbar
pr"azise Sprache, in der
  wir uns auch "uber imaginierte Dinge unmi"sverst"andlich austauschen
  k"onnen.  Man kann dieselbe Konstruktion auch allgemeiner durchf"uhren, wenn
  man statt $-1$ irgendein anderes Element eines K"orpers $K$ betrachtet, das
  kein Quadrat ist.  Noch allgemeinere Konstruktionen zur \glqq Adjunktion
  h"oherer Wurzeln\grqq\  oder sogar der \glqq Adjunktion von Nullstellen polynomialer
  Gleichungen\grqq\  k"onnen Sie in der Algebra kennenlernen, 
vergleiche etwa \eref{AdNs}{AL}.
In \eref{KoZa}{LA1}  diskutieren wir die komplexen Zahlen  ausf"uhrlicher.
\end{Bemerkungl}
 \begin{Ubunge}\label{BNEa}
Ein K"orperhomomorphismus ist stets injektiv.
\end{Ubunge} 






%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "XXAN1"
%%% End: