\message{ !name(AATOTAL.tex)}%Ein Bild: width=\textwidth %Zwei Bilder: height=0.4\textheight ohne Text, 9-8cm mit Text %\begin{figure}[p]\centering\includegraphics[height=0.4\textheight oder width=\textwidth]{SkriptenBilder/BildGibtsnet}\\[4mm] %\noindent BlahBlah\end{figure} %Index Machen: makeindex -g -s german.ist AATOTAL %BILDER VORBEREITEN %B.bb von B.ps Kriegen: for i in *.ps; do grep ^%%BoundingBox $i >$i.bb; done %BILDER EIN BISSEL VERPACKEN %gzip *.ps %Alt-x server-start (f"ur Quelltextsuche bei emacs) %AATOTAL INTERN VER"OFFENTLICHEN: %in /Documents/Skripten/Skripten/SkriptenBilder machen: %for i in *.ps; do grep ^%%BoundingBox $i >$i.bb; done %gzip *.ps %in /Documents/Skripten/Skripten machen: %scp AATOTALd.dvi soergel@tux00:/webserver/home/intern/soergel/AATOTALd.dvi %tar cf SkriptenBilder.tar SkriptenBilder/*.*ps* %scp SkriptenBilder.tar soergel@tux00:/webserver/home/intern/soergel/ %BILDER IN UNI VERPACKEN: %soergel@soerdell:~/Documents/Skripten/Skripten> tar cfz SkriptenBilder.tar SkriptenBilder/* %BILDER F"UR DAS HEIMHOLEN AUF DEN WEBSERVER LEGEN: %scp SkriptenBilder.tar %soergel@tux00:/webserver/home/soergel/Skripten/SkriptenBilder.tar %BILDER ZUHAUSE VOM SERVER HOLEN: %scp soergel@tux00.mathematik.uni-freiburg.de:/webserver/home/soergel/Skripten/SkriptenBilder.tar SkriptenBilder.tar %BILDER ZUHAUSE AUSPACKEN: %soergel@linux:~/Documents/Skripten/Skripten> tar xf SkriptenBilder.tar %soergel@linux:~/Documents/Skripten/Skripten> tar cfz SkriptenBilder.tar SkriptenBilder/BildA.ps.bb %scp SkriptenBilder.tar soergel@tux00.mathematik.uni-freiburg.de:/webserver/home/soergel/Skripten/SkriptenBilder.tar %Anleitung xypic %http://www.uni-koblenz.de/~texadmin/texmf/doc/html/latex/contrib/xypic/xyguide-html/index.html \documentclass[12pt,a4paper]{book} \renewcommand{\thepart}{\Alph{part}} \setcounter{tocdepth}{0} \usepackage{minitoc} \renewcommand{\mtctitle}{Inhalt} \usepackage[active]{srcltx}%Alt-X server-start \usepackage{showkeys} \usepackage{young} \usepackage{makeidx} \usepackage{newlfont} \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsxtra} \usepackage{amsfonts} \usepackage{amscd} \usepackage[ngerman]{babel} \usepackage[hypertex]{hyperref} \usepackage{verbatim} \usepackage{changebar} \usepackage{ae} \usepackage{xr} \changebarsep85pt \usepackage{graphicx} \renewcommand{\floatpagefraction}{0.2} \renewcommand{\figurename}{ } \input{xy} \xyoption{all} \input{Querverweisekurz} \frenchspacing \usepackage{amsthm} \usepackage{epsfig} \usepackage{alltt} \input{newtheorems} \input{newcommands} \renewenvironment{comment}{\begin{changebar}}{\end{changebar}} \makeindex \begin{document} \message{ !name(An01Grundlagen.tex) !offset(-83) } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{GGrund} \section{Einstimmung}\label{Grund} \subsection{Vollst"andige Induktion und binomische Formel}\label{Ein} \begin{Satz}\label{ErF} F"ur jede nat"urliche Zahl $n\geq 1$ gilt $1+2+\ldots +n = \frac{n(n+1)}{2}.$ \end{Satz} \begin{proof}[Beweis] Bei diesem Beweis sollen Sie gleichzeitig das Beweisprinzip der {\bf voll\-st"andigen Induktion}\index{Induktion} 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} Die Aussage $A(1)$ ist richtig. In der Tat gilt die Formel $1= \frac{1(1+1)}{2}.$ \item[Induktionsschritt:]\index{Induktion} Aus $A(n)$ folgt $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!} oder {\bf Induktionsvoraussetzung}\index{Induktion}, 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,\ldots .$ \end{proof} \begin{Bemerkungl} Dieser 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 m"ogen Sie in der Logik lernen. \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{Bemerkung} 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{Meng} einf"uhren werden, mu"s man die leere Menge endlich nennen, damit jede Teilmenge einer endlichen Menge wieder endlich ist. Will man dann 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{Bemerkung} \begin{figure}[p] \centering \includegraphics[width=12cm]{SkriptenBilder/Bild0003} \\[4mm] \noindent Die Gesamtfl"ache dieses Treppenquerschnitts ist offensichtlich $4^2/2+4/2=4\cdot 5/2$ \end{figure} \begin{Bemerkung}\label{SSF} Man kann sich den Satz anschaulich klar machen als eine Formel f"ur die Fl"ache eines Querschnitts f"ur 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 $1.$ Ein weiterer Beweis geht so: $$\begin{array}{rcrlcc} 1 + 2 + \ldots +n&=&1/2 &+ \;\;\;\; 2/2 &+ \ldots &+\; n/2 \\ &&+ \; n/2 &+ (n-1)/2& + \ldots &+\; 1/2\\[2mm] &=& \frac{n+1}{2} &+ \;\;\;\; \frac{n+1}{2}& + \ldots &+\; \frac{n+1}{2}\\[2mm] & = & n(n+1)/2 \hspace{-1cm}&& & \end{array}$$ Ich will diesen Beweis benutzen, um eine neue Notation einzuf"uhren. \end{Bemerkung} \begin{Definition} Gegeben $a_{1},a_{2},\ldots , a_{n}$ schreiben wir $$\sum^{n}_{i=1} a_{i} = a_{1}+a_{2}+ \ldots + a_{n}$$ Das Symbol $\sum$ ist ein gro"ses griechisches S und steht f"ur \glqq Summe\grqq. In diesem und "ahnlichen Zusammenh"angen hei"sen $a_1,\ldots, a_n$ die \defind{Summanden} und $i$ hei"st der \defind{Laufindex}, weil er eben etwa in unserem Fall von $1$ bis $n$ l"auft. \end{Definition} \begin{Bemerkung} Das Wort \glqq Definition\grqq\ \index{Definition} kommt aus dem Lateinischen und bedeutet \glqq Abgrenzung\grqq. In Definitionen versuchen wir, die Bedeutungen von Symbolen und Begriffen so klar wie m"oglich festzulegen. \end{Bemerkung} \begin{Beispiel} In der $\sum$-Notation liest sich der in \ref{SSF} 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{Definition} In einer "ahnlichen Bedeutung wie $\sum$ verwendet man auch das Symbol $\prod,$ ein gro"ses griechisches $P,$ f"ur \glqq Produkt\grqq\ und schreibt $$\prod^{n}_{i=1} a_{i}=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} durch die Formel $$n! = 1\cdot 2 \cdot\ldots \cdot n = \prod^{n}_{i=1} i$$ Wir treffen zus"atzlich die Vereinbarung $0! =1$ und haben also $0! =1,$ $1!=1,$ $2!=2,$ $3! = 6,$ $4!=24$ und so weiter. \end{Definition} \begin{Bemerkungl}\label{LPS} Wir werden in Zukunft noch "ofter Produkte mit "uberhaupt keinem Faktor zu betrachten haben und vereinbaren deshalb gleich hier schon, da"s Produkten, bei denen die obere Grenze des Laufindex um eins kleiner ist als seine untere Grenze, der Wert 1 zugewiesen werden soll. 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. \end{Bemerkungl} \begin{Satz}[\textbf{Bedeutung der Fakult"at}]\label{BFa} 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 werden, 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 in der Tat wie behauptet $n!$ m"ogliche Reihenfolgen. \end{proof} \begin{Definition} Wir definieren f"ur beliebiges $n$ und jede nat"urliche Zahl $k$ die {\bf Binomialkoeffizienten}\index{Binomialkoeffizienten} ${n \choose k}$ (sprich: $n$ {\bf "uber} $k$) durch die Regeln $${n \choose k} = \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}=1.$$ Der Sonderfall $k=0$ wird im "Ubrigen auch durch unsere allgemeine Formel gedeckt, wenn wir unsere Konvention \ref{LPS} 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{Satz}[\textbf{Bedeutung der Binomialkoeffizienten}] Gegeben na\-t"urliche Zahlen\label{BBK} $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 also nach \ref{BFa} 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=\prod_{i=1}^{k} a$ und verstehen im Lichte von \ref{LPS} also insbesondere $a^0=1.$ \end{Definition} \begin{Satz} F"ur jede nat"urliche Zahl $n$ gilt 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{Bemerkung} Man beachte, wie wichtig unsere Konvention $a^0=1$ und insbesondere auch $0^0=1$ f"ur die G"ultigkeit dieser Formel ist. \end{Bemerkung} \begin{proof}[Erster Beweis] Beim Ausmultiplizieren erhalten wir so oft $a^k b^{n-k},$ wie es M"oglichkeiten gibt, aus unseren $n$ Faktoren die $k$ Faktoren $(a+b)$ auszusuchen, \glqq in denen wir beim Ausmultiplizieren das $b$ nehmen\grqq. Dieses Argument werden wir in \ref{PFB} 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 undurchsichtig. 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{Bemerkung} 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 $$(a+b)^4=a^4 + 4a^3b + 6 a^2b^2+ 4 ab^3+b^4\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$$ \end{Bemerkung} \subsection{Fibonacci-Folge und Vektorraumbegriff} \begin{Beispiel} Die \defind{Fibonacci-Folge} $$0,1,1,2,3,5,8,13,21,\ldots $$ entsteht, indem man mit $x_0=0$ und $x_1=1$ beginnt und dann jedes weitere Folgenglied als die Summe seiner beiden Vorg"anger bildet. Wir suchen nun f"ur die Glieder dieser Folge eine geschlossene Darstellung. Dazu vereinbaren wir, da"s wir Folgen $x_0, x_1, x_2, \ldots$ mit der Eigenschaft $x_n =x_{n-1}+x_{n-2}$ f"ur $n = 2,3,4 , \ldots $ {\bf Folgen vom Fibonacci-Typ} nennen wollen. Kennen wir die beiden ersten Glieder einer Folge vom Fibonacci-Typ, so liegt nat"urlich bereits die gesamte Folge fest. Nun bemerken wir, da"s f"ur jede Folge $x_0,x_1, x_2, \ldots $ vom Fibonacci-Typ und jedes $\alpha$ auch die Folge $\alpha x_0, \alpha x_1, \alpha x_2, \ldots$ vom Fibonacci-Typ ist, und da"s f"ur jede weitere Folge $y_0,y_1,y_2, \ldots $ vom Fibonacci-Typ auch die gliedweise Summe $(x_0 + y_0), (x_1 + y_1) , (x_2 + y_2), \ldots $ eine Folge vom Fibonacci-Typ ist. Der Trick ist dann, danach zu fragen, f"ur welche $\beta$ die Folge $x_i =\beta^i$ vom Fibonacci-Typ ist. Das ist ja offensichtlich genau dann der Fall, wenn gilt $1 + \beta = \beta^2,$ als da hei"st f"ur $\beta_{\pm} = \frac{1}{2} (1 \pm \sqrt{5}).$ F"ur beliebige $c,d$ ist mithin die Folge \begin{displaymath} x_i = c\beta_+^i + d\beta_-^i \end{displaymath} vom Fibonacci-Typ, und wenn wir $c $ und $d$ bestimmen mit $x_0 = 0$ und $x_1 =1,$ so ergibt sich eine explizite Darstellung unserer Fibonacci-Folge. Wir suchen also $c$ und $d$ mit \begin{displaymath} \begin{array}{lll} 0 &=& c + d\\ 1 & =& c \left( \frac{1}{2}(1+\sqrt{5})\right) + d \left( \frac{1}{2} (1-\sqrt{5})\right) \end{array} \end{displaymath} und folgern leicht $c = -d$ und $1 = c\sqrt{5} $ alias $c = 1/\sqrt{5}=-d.$ Damit ergibt sich schlie"slich f"ur unsere urspr"ungliche Fibonacci-Folge die explizite Darstellung \begin{displaymath} x_i = \frac{1}{\sqrt{5}} \left( \frac{1+ \sqrt{5}}{2}\right)^i - \frac{1}{\sqrt{5}} \left( \frac{1-\sqrt{5}}{2}\right)^{i} \end{displaymath} \end{Beispiel} \begin{Ubung} Kann man f"ur jede Folge $x_0,x_1,\ldots$ vom Fibonacci-Typ Zahlen $c,d$ finden mit $x_i = c\beta_+^i + d\beta_-^i$ f"ur alle $i$? Finden Sie eine geschlossene Darstellung f"ur die Glieder der Folge, die mit $0,0,1$ beginnt und dem Bildungsgesetz $x_n=2x_{n-1}+x_{n-2}-2x_{n-3}$ gehorcht. \end{Ubung} \begin{Beispiel} Wir betrachten ein lineares Gleichungssytem der Gestalt \begin{displaymath} \begin{array}{lllll} \alpha_{11} x_1 + \alpha_{12}x_2 + &\ldots &+\alpha_{1m} x_m &=&0\\ \alpha_{21} x_1 + \alpha_{22} x_2 + & \ldots & + \alpha_{2m} x_m &=&0\\ & \vdots & & & \\ \alpha_{n1} x_1 + \alpha_{n2} x_2 + & \ldots & +\alpha_{nm}x_m &=&0 \end{array} \end{displaymath} Wie man zu vorgegebenen $\alpha_{i,j}$ f"ur $1\leq i\leq n$ und $1\leq j\leq m$ die Menge $L$ aller L"osungen $(x_1, \ldots , x_m)$ ermittelt, sollen sie sp"ater in dieser Vorlesung lernen. Zwei Dinge aber sind a priori klar: \begin{enumerate} \item Sind $(x_1, \ldots, x_m) $ und $(x'_1, \ldots , x'_m)$ L"osungen, so ist auch ihre komponentenweise Summe $(x_1 + x'_1, \ldots , x_m + x'_{m})$ eine L"osung; \item Ist $(x_1, \ldots, x_m)$ eine L"osung und $\alpha$ eine reelle Zahl, so ist auch das komponentenweise Produkt $(\alpha x_1, \ldots , \alpha x_m)$ eine L"osung. \end{enumerate} \end{Beispiel} \begin{Beispiel} Wir betrachten die Menge aller Funktionen $f: \Bbb{R} \ra \Bbb{R}$, die zweimal differenzierbar sind und der Differentialgleichung \begin{displaymath} f\grqq\ = - f \end{displaymath} gen"ugen. L"osungen sind zum Beispiel die Funktionen $\sin, \cos,$ die Nullfunktion oder auch die Funktionen $f(x) = \sin (x+a)$ f"ur konstantes $a.$ Wie man die Menge $L$ aller L"osungen beschreiben kann, sollen Sie nicht hier lernen. Zwei Dinge aber sind a priori klar: \begin{enumerate} \item Mit $f$ und $g$ ist auch die Funktion $f+g$ eine L"osung; \item Ist $f$ eine L"osung und $\alpha$ eine reelle Zahl, so ist auch $\alpha f$ eine L"osung. \end{enumerate} \end{Beispiel} \begin{Beispiel} Wir betrachten die Gesamtheit aller Parallelverschiebungen der Tafelebene. Graphisch stellen wir solch eine Parallelverschiebung dar durch einen Pfeil von irgendeinem Punkt zu seinem Bild unter der Verschiebung. Im nebenstehenden Bild stellen etwa alle gepunktelten Pfeile dieselbe Parallelverschiebung dar. Was f"ur ein Ding diese Gesamtheit $P$ aller Parallelverschiebungen eigentlich ist, scheint mir recht undurchsichtig, aber einige Dinge sind a priori klar: \begin{enumerate} \item Sind $p$ und $q$ Parallelverschiebungen, so ist auch ihre \glqq Hintereinanderausf"uhrung\grqq\ $p \circ q$, sprich \glqq $p$ nach $q$\grqq\ eine Parallelverschiebung. \begin{figure}[p] \centering \includegraphics[width=12cm]{SkriptenBilder/BildPar}\\[4mm] \noindent Die Hintereinanderausf"uhrung der beiden Parallelverschiebungen der Tafel- oder hier vielmehr der Papierebene, die durch die durchgezogenen Pfeile dargestellt werden, wird die durch die gepunktelten Feile dargestellt. \end{figure} \item Ist $\alpha$ eine reelle Zahl und $p$ eine Parallelverschiebung, so k"onnen wir eine neue Parallelverschiebung $\alpha p$ bilden, das \glqq $\alpha$-fache von $p$\grqq. Bei negativen Vielfachen vereinbaren wir hierzu, da"s eine entsprechende Verschiebung in die Gegenrichtung gemeint ist. \item F"uhren wir eine neue Notation ein und schreiben f"ur die Hintereinanderausf"uhrung $p\circ q=p\dotplus q,$ so gelten f"ur beliebige Parallelverschiebungen $p,q,r$ der Tafelebene und beliebige reelle Zahlen $\alpha, \beta$ die Formeln \begin{displaymath} \begin{array}{ccc} (p \dotplus q) \dotplus r & =& p \dotplus (q \dotplus r)\\ p\dotplus q & = & q \dotplus p\\ \alpha (\beta p) & =& (\alpha \beta )p\\ (\alpha + \beta) p & =& (\alpha p)\dotplus (\beta p)\\ \alpha (p \dotplus q) & =& (\alpha p) \dotplus (\alpha q) \end{array} \end{displaymath} \end{enumerate} Will man sich die Gesamtheit aller Parallelverschiebungen der Tafelebene anschaulich machen, so tut man im "Ubrigen gut daran, einen Punkt als \glqq Ursprung\grqq\ auszuzeichnen und jede Parallelverschiebung mit dem Punkt der Tafelebene zu identifizieren, auf den unsere Parallelverschiebung diesen Ursprung abbildet. \end{Beispiel} \begin{Beispiel}\label{ZSV} Analoges gilt f"ur die Gesamtheit der Parallelverschiebung des Raums und auch f"ur die Gesamtheit aller Verschiebungen einer Geraden und, mit noch mehr Mut, f"ur die Gesamtheit aller Zeitspannen. \end{Beispiel} \begin{Bemerkung} Die Formeln unserer kleinen Formelsammlung von eben gelten ganz genauso auch f"ur die L"osungsmenge unserer Differentialgleichung $f\grqq\ = -f$, wenn wir $f\dotplus g = f + g$ verstehen, f"ur die L"osungsmenge unseres linearen Gleichungssystems, wenn wir $$(x_1, \ldots, x_m ) \dotplus (x'_{1}, \ldots , x'_{m}) = (x_1 + x'_{1}, \ldots , x_m + x'_{m})$$ verstehen, und f"ur die Menge aller Folgen vom Fibonacci-Typ, wenn wir "ahnlich die Summe $\dotplus$ zweier Folgen erkl"aren. Das erste Ziel der folgenden Vorlesungen "uber lineare Algebra ist es, einen abstrakten Formalismus aufzubauen, dem sich alle diese Beispiele unterordnen. Wir verfolgen damit gleichzeitig zwei Ziele: \\[2mm]\noindent 1. Unser abstrakter Formalismus soll uns dazu verhelfen, die uns als Augentieren und Nachkommen von "Asteh"upfern angeborene r"aumliche Anschauung nutzbar zu machen zum Verst"andnis der bis jetzt gegebenen Beispiele und der vielen weiteren Beispiele von Vektorr"aumen, denen Sie im Verlauf Ihres Studiums noch begegnen werden. So werden sie etwa lernen, da"s man sich die Menge aller Folgen vom Fibonacci-Typ durchaus als Ebene vorstellen darf und die Menge aller Folgen mit vorgegebenem Folgenglied an einer vorgegebenen Stelle als eine Gerade in dieser Ebene. Suchen wir also alle Folgen vom Fibonacci-Typ mit zwei vorgegebenen Folgengliedern, so werden wir im allgemeinen genau eine derartige L"osung finden, da sich eben zwei Geraden in der Ebene im allgemeinen in genau einem Punkt schneiden. In diesem Licht betrachtet soll der abstrakte Formalismus uns also helfen, formale Fragestellungen der Anschauung zug"anglich zu machen. Ich denke, diese N"ahe zur Anschauung ist auch der Grund daf"ur, da"s die lineare Algebra meist an den Anfang des Studiums gestellt wird: Von der Schwierigkeit des Formalismus her gesehen geh"ort sie n"amlich keineswegs zu den einfachsten Gebieten der Mathematik, hier w"urde ich eher an Gruppentheorie oder Graphentheorie oder dergleichen denken. \\[2mm]\noindent 2. Unser abstrakter Formalismus soll so unmi"sverst"andlich sein und seine Spielregeln so klar, da"s Sie in die Lage versetzt werden, alles nachzuvollziehen und mir im Prinzip und vermutlich auch in der Realit"at Fehler nachzuweisen. Schwammige Begriffe wie \glqq Tafelebene\grqq\ oder \glqq Parallelverschiebung des Raums\grqq\ haben in einem solchen Formalismus keinen Platz mehr. In diesem Licht betrachtet verfolgen wir mit dem Aufbau des abstrakten Formalismus auch das Ziel einer gro"sen Vereinfachung durch die Reduktion auf die Beschreibung einiger weniger Aspekte der uns umgebenden in ihrer Komplexit"at kaum pr"azise fa"sbaren Wirklichkeit. \\[2mm]\noindent Als Motivation f"ur den weiteren Fortgang der Vorlesungen "uber lineare Algebra formuliere ich nun ohne R"ucksicht auf noch unbekannte Begriffe und Notationen die abstrakte Definition eines reellen Vektorraums. \end{Bemerkung} \begin{Definition}\label{DERv} Ein \defind{reeller Vektorraum} ist ein Tripel bestehend aus den folgenden drei Dingen: \begin{enumerate} \item Einer Menge $V$; \item Einer Verkn"upfung $V \times V \ra V,$ $ (v, w) \mapsto v \dotplus w,$ die $V$ zu einer abelschen Gruppe macht; \item Einer Abbildung $\Bbb{R} \times V \ra V,$ $ (\alpha , v) \mapsto \alpha v$, \end{enumerate} derart, da"s f"ur alle $\alpha, \beta \in \Bbb{R}$ und alle $v,w \in V$ gilt: \begin{displaymath} \begin{array}{ccc} \alpha (\beta v) &=& (\alpha \beta) v\\ (\alpha + \beta) v &=& (\alpha v) \dotplus (\beta v)\\ \alpha (v\dotplus w) &=& (\alpha v) \dotplus (\alpha w)\\ 1v &=& v \end{array} \end{displaymath} Hier ist nun viel zu kl"aren: Was ist eine Menge? Eine Verkn"upfung? Eine abelsche Gruppe? Eine Abbildung? Was bedeuten die Symbole $\times ,$ $\ra,$ $\mapsto ,$ $\in ,$ $\Bbb{R}$? Wir beginnen in der n"achsten Vorlesung mit der Kl"arung dieser Begriffe und Notationen. \end{Definition} \newpage \section{Naive Mengenlehre} \subsection{Mengen}\label{Meng} \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. \emph{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. \end{Bemerkungl} \begin{Bemerkungl} Nach dem Begr"under der Mengenlehre Georg Cantor ist eine {\bf Menge}\index{Menge} eine \begin{quote} Zusammenfassung $M$ von bestimmten, wohlunterschiedenen Objekten $m,$ $m',$ $m\grqq,\ldots$ unseres Denkens oder unserer Anschauung zu einem Ganzen. \end{quote} Diese Objekte nennen wir die {\bf Elemente}\index{Element} der Menge. 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, aber das Ziel dieser Vorlesung ist auch nicht die formale Begr"undung der Mengenlehre, die Sie sp"ater 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{Beispiele} Endliche Mengen gibt man oft durch eine vollst"andige Liste ihrer Elemente in geschweiften Klammern an, zum Beispiel in der Form $X = \{x_{1},x_{2}, \ldots, x_{n} \}.$ Die Elemente d"urfen mehrfach genannt werden und es kommt nicht auf die Reihenfolge an, in der sie genannt werden. So haben wir also $\{1,1,2\} = \{2,1\}.$\index{e@$\in, \not\in$} 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.$ Es gibt auch die sogenannte {\bf leere Menge}\index{Menge!leere Menge} $\emptyset=\{\;\},$ die gar kein Element enth"alt. Andere Beispiele sind die Menge der {\bf nat"urlichen Zahlen}\index{Zahlen!nat"urliche}\index{nat"urliche Zahlen} $\DN = \{0,1,2,\ldots \},$ die Menge der {\bf ganzen Zahlen}\index{Zahlen!ganze}\index{ganze Zahlen} $\DZ = \{0,1,-1,2,-2, \ldots\}$ und die Menge der {\bf rationalen Zahlen}\index{Zahlen!rationale}\index{rationale Zahlen} $\DQ = \{p/q \mid p,q \in \DZ, q \neq 0\}.$ Deren Name kommt von lateinisch \glqq ratio\grqq\ f"ur \glqq Verh"altnis\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 manchmal auch als \defind{Bruchzahlen}. \end{Beispiele} \begin{Bemerkung} 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$ 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{Bemerkung} \begin{Definition} Eine Menge $Y$ hei"st {\bf Teilmenge}\index{Menge!Teilmenge} \index{Teilmenge} einer Menge $X$ genau dann, wenn jedes Element von $Y$ auch ein Element von $X$ ist. Man schreibt daf"ur $Y\subset X$ oder $X \supset Y.$ Zum Beispiel gilt stets $\emptyset \subset X$ und $\{x\} \subset X $ ist gleichbedeutend zu $ x \in X.$ Zwei Teilmengen einer gegebenen Menge, die kein gemeinsames Element haben, hei"sen {\bf disjunkt}\index{disjunkt}.\index{c@$\subset$}\index{$\subset$} \end{Definition}\begin{Bemerkung} Diese Notation weicht ab von der internationalen Norm ISO 31-11, die statt unserem $\subset$ das Symbol $\subseteq$\index{c@$\subseteq$}\index{$\subseteq$} vorschl"agt. In den Konventionen von ISO 31-11 hat das Symbol $\subset$ abweichend die Bedeutung einer {\bf echten}\index{Teilmenge!echte},\index{echt!Teilmenge} d.h.\ von der ganzen Menge verschiedenen Teilmenge, f"ur die wir die Bezeichnung $\subsetneqq$\index{c@$\subsetneqq$}\index{$\subsetneqq$} verwenden werden. Meine Motivation f"ur diese Abweichung ist, da"s das Symbol f"ur beliebige Teilmengen sehr h"aufig und das f"ur echte Teilmengen nur sehr selten vorkommt. \end{Bemerkung} \begin{Definition}\label{Kard} Wir vereinbaren, da"s wir auch die leere Menge endlich nennen wollen, damit jede Teilmenge einer endlichen Menge auch wieder endlich ist. Die Zahl der Elemente einer endlichen Menge $X$ nennen wir ihre {\bf Kardinalit"at}\index{Kardinalit"at} oder {\bf M"achtigkeit}\index{M"achtigkeit} und notieren sie $|X|$ oder $\op{card}(X).$ Ist $X$ unendlich, so schreiben wir kurz $|X|=\infty$ und ignorieren in unserer Notation, da"s auch unendliche Mengen \glqq verschieden gro"s\grqq\ sein k"onnen, f"ur ein Beispiel siehe \ref{QR} und f"ur eine genauere Diskussion des Begriffs der Kardinalit"at \ref{KaZa}. 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.$ \end{Definition} \begin{Definition} Oft bildet man neue Mengen als Teilmengen bestehender Mengen und schreibt $Y= \{x\in X \mid x \text{ hat eine gewisse Eigenschaft}\}.$ Zum Beispiel gilt $\DN = \{a \in \DZ \mid a \geq 0\}$ oder $\{0,1\} = \{a \in \DN \mid a^{2}=a\}.$ Eine Variante dieser Notation soll hier nur mit zwei Beispielen erkl"art werden: $\{ 2a \mid a \in \DN\}$ bezeichnet die Menge aller geraden nat"urlichen Zahlen, $\{ab \mid a,b \in \DN , a \geq 2, b \geq 2\}$ die Menge aller nat"urlichen Zahlen, die nicht prim und auch nicht Null oder Eins sind. \end{Definition} \begin{Definition} 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} \index{Potenzmenge} von $X$ und wird mit $\cal{P}(X)$ bezeichnet. \end{Definition} \begin{Bemerkung}Ist $X$ eine endliche Menge, so ist auch ihre Potenzmenge endlich und es gilt $|\cal{P}(X)|=2^{|X|}.$ F"ur $X=\{1,2\}$ besteht zum Beispiel $\cal{P}(X)$ aus vier Elementen und genauer gilt $\cal{P}(X)=\{\emptyset,\{1\},\{2\},\{1,2\}\}.$ \end{Bemerkung} \begin{Definition} Gegeben zwei Mengen $X,Y$ k"onnen wir auf verschiedene Arten neue Mengen bilden: \begin{enumerate} \item Die {\bf Vereinigung}\index{Vereinigung} $X\cup Y =\{z \mid z \in X \text{ oder } z \in Y\},$ zum Beispiel ist $\{1,2\} \cup \{2,3\} = \{1,2,3\}.$ \item Den {\bf Schnitt}\index{Schnitt!zweier Mengen} $X\cap Y =\{z \mid z \in X \text{ und } z \in Y\},$ zum Beispiel ist $\{1,2\}\cap \{2,3\} = \{2\}.$ Zwei Mengen sind also disjunkt genau dann, wenn ihr Schnitt die leere Menge ist. \begin{figure}[p] \centering \includegraphics[width=12cm]{SkriptenBilder/BildMop} \\ \noindent Eine gute Anschauung f"ur die ersten drei Operationen liefern die sogenannten \defind{van-de-Ven-Diagramme} wie sie die obenstehenden 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 sehr fraglich. Wenn man jedoch jedes der schraffierten Gebiete im Bild auffasst als die Menge aller darin liegenden Kreuzungspunkte auf einem dazugedachten Millimeterpapier und keine dieser Kreuzungspunkte auf den Begrenzungslinien liegen, so k"onnen sie wohl schon als eine Menge im Cantor'schen Sinne angesehen werden. \end{figure} \item Die {\bf Differenz}\index{Differenz!von Mengen} $X \backslash Y = \{z \in X \mid z \not\in Y\},$ zum Beispiel haben wir $\{1,2\}\backslash \{2,3\} = \{1\}.$ Man schreibt statt $X \backslash Y$ auch $X-Y.$ Ist $Y$ eine Teilmenge von $X,$ so hei"st $X \backslash Y$ das {\bf Komplement}\index{Komplement} von $Y$ in $X.$ \item Das {\bf kartesische Produkt}\index{kartesisches Produkt} $X \times Y =\{(x,y)\mid x \in X,\; y\in Y\},$\index{x@$\times$} als da hei"st die Menge aller geordneten Paare. 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 kartesische Produkt $X\times X$ einer Menge $X$ mit sich selbst die Abk"urzung $X\times X = X^2.$ \begin{figure}[p] \centering \includegraphics[width=12cm]{SkriptenBilder/BildPe}\\ \noindent Anschauliche Darstellung des Produkts einer Menge mit f"unf und einer Menge mit drei Elementen. Hier wird ein Paar $(x,y)$ dargestellt durch einen fetten Punkt, der "uber $x$ und neben $y$ liegt. \end{figure} \end{enumerate} \end{Definition} \begin{Bemerkung} Wir werden in unserer naiven Mengenlehre die ersten drei Operationen 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 zum Beispiel 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 definieren, d.h.\ als Elemente von $\cal{P}(T),$ und das Konzept \glqq ist Kind von\grqq\ als eine Teilmenge des kartesischen Produkts dieser Menge $T$ mit sich selbst, also als ein Element von $\cal{P}(T\times T).$ \end{Bemerkung} \begin{Bemerkungl}\label{VMR} F"ur das Rechnen mit Mengen "uberlegt man sich die folgenden Regeln: $$\begin{array}{rcl} X \cap (Y\cap Z)&=& (X\cap Y)\cap Z\\ X \cup (Y\cup Z)&=& (X\cup Y) \cup Z\\[2mm] 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] 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] X \backslash (X\backslash Y)&=& X \cap Y \end{array}$$ Eine gute Anschauung f"ur diese Regeln liefern die van-de-Ven-Diagramme, wie sie die nebenstehenden Bilder zeigen. \begin{figure}[p] \centering \includegraphics[height=0.3\textheight]{SkriptenBilder/Bild0001}\\[4mm] %\includegraphics[height=0.3\textheight]{SkriptenBilder/Bild0001}\\[4mm] $X \cap (Y\cup Z)= (X\cap Y)\cup (X \cap Z)$ \end{figure} \begin{figure}[p] \centering \includegraphics[height=0.3\textheight]{SkriptenBilder/Bild0007}\\[4mm] %\includegraphics[height=0.3\textheight]{SkriptenBilder/Bild0007}\\[4mm] $X \setminus (Y\cap Z)= (X\setminus Y)\cup (X \setminus Z)$ \end{figure} \end{Bemerkungl} \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\backslash Y|+|X\cap Y|+|Y\backslash X|.$ \end{Ubung} \begin{Satz}[\textbf{Bedeutung der Binomialkoeffizienten}]\label{BK} Gegeben $n,k\in \DN$ gibt der Binomialkoeffizient ${n\choose k}$ die Zahl der $k$-elementigen Teilmengen einer $n$-elementigen Menge an, in Formeln $$|X|=n\;\; \text{ impliziert } \;\; |\{ 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\},$ 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}$ $k$-elementige Teilmengen. \end{proof} \begin{Bemerkung} Wieder scheint mir dieser Beweis in der f"ur vollst"andige Induktion typischen Weise undurchsichtig. Ich ziehe deshalb den in \ref{BBK} gegebenen weniger formellen Beweis vor. Man kann auch diesen Beweis formalisieren und verstehen als Spezialfall der sogenannten \glqq Bahnformel\grqq\ \ref{BF}, vergleiche \ref{BIKON}. \end{Bemerkung} \begin{Bemerkung} \label{PFB} Wir geben nun die versprochene pr"azise Formulierung unseres ersten Beweises der binomischen Formel. Wir rechnen dazu $$(a+b)^n=\sum_{Y\subset\{1,2,\ldots,n\}} a^{|Y|} b^{n-|Y|}$$ wo die rechte Seite in Verallgemeinerung der in Abschnitt \ref{Ein} eingef"uhrten Notation bedeuten soll, 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{BK} die binomische Formel. \end{Bemerkung} \begin{Ubung} Es gilt $\sum_k{n\choose k}=2^n.$ \end{Ubung} \begin{Bemerkung}\label{WHK} Ich will nicht verschweigen, da"s der in diesem Abschnitt dargestellte naive Zugang zur Mengenlehre durchaus begriffliche Schwierigkeiten mit sich 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 $\ldots$ 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 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 in ihren Grenzbereichen zur Informatik. \end{Bemerkung} \begin{figure}[p] \centering \includegraphics[width=12cm]{SkriptenBilder/BildKar} \\ \noindent Dies Bild mu"s anders interpretiert werden als die Vorherigen. Die Mengen $X$ und $Y$ sind nun zu verstehen als die Mengen der Punkte der vertikalen und horizontalen Geradensegmente und ein Punkt des Quadrats meint das Element $(x,y)\in X\times Y,$ das in derselben H"ohe wie $y\in Y$ senkrecht "uber $x\in X$ liegt. \end{figure} \begin{figure}[p] \centering \includegraphics[width=12cm]{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{figure} \begin{Bemerkung} Um mich nicht dem Vorwurf auszusetzen, w"ahrend des Spiels die Spielregeln "andern zu wollen, sei bereits hier erw"ahnt, da"s in \ref{ErMe} noch weitere wichtige Konstruktionen der Mengenlehre eingef"uhrt werden, und da"s wir in \ref{ZoLe} einige weniger offensichtliche Folgerungen erl"autern, die meines Erachtens bereits an den Rand dessen gehen, was man in unserem informellen Rahmen als Argumentation noch vertreten kann. \end{Bemerkung} \subsection{Abbildungen} \begin{Definition} Seien $X,Y$ Mengen. Eine {\bf Abbildung}\index{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.$ \end{Definition} \begin{figure}[p] \centering \includegraphics[height=0.3\textheight]{SkriptenBilder/Bild0002} \\ \noindent Eine Abbildung einer Menge mit f"unf in eine mit drei Elementen \end{figure} \begin{figure}[p] \centering \includegraphics[width=12cm]{SkriptenBilder/Bildgr}\\ \noindent Der Graph der oben angegebenen Abbildung, wobei das $X$ oben mit dem $X$ hier identifiziert wurde durch \glqq Umkippen nach Rechts\grqq\ \end{figure} \begin{Bemerkungl}\label{DFA} Wem das zu vage ist, der mag die alternative Definition vorziehen, nach der eine {\bf Abbildung}\index{Abbildung} $f:X \ra Y$ eine Teilmenge $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 am selben Punkt angelangt. In unseren Konventionen nennen wir besagte Teilmenge den \defind{Graphen} {\bf von} $f$ und notieren sie mit dem Symbol $\Gamma$ (sprich: Gamma), einem gro"sen griechischen G, und schreiben also $$\Gamma(f)=\{(x,f(x))\mid x\in X\}\subset X\times Y$$ \end{Bemerkungl} \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 genau dann, wenn sie denselben Definitionsbereich $X,$ denselben Wertebereich $Y$ und dieselbe Abbildungsvorschrift $f\subset X \times Y$ haben. Die Menge aller Abbildungen von $X$ nach $Y$ bezeichnen wir mit $\op{Ens}(X,Y)$\index{Ens} nach der franz"osischen "Ubersetzung \defind{ensemble} des deutschen Begriffs \glqq Menge\grqq. \end{Definition} \begin{Bemerkung} Noch gebr"auchlicher ist die Bezeichnung $\op{Abb}(X,Y)$\index{Abb} f"ur die Menge aller Abbildungen von $X$ nach $Y.$ Ich will jedoch sehr viel sp"ater die \glqq Kategorie aller Mengen\grqq\ mit $\op{Ens}$ bezeichnen und f"ur je zwei Objekte $X,Y$ einer Kategorie $\cal{C}$ die Menge aller \glqq Morphismen\grqq\ von $X$ nach $Y$ mit $\cal{C}(X,Y),$ und das motiviert dann auch erst eigentlich die hier gew"ahlte Bezeichnung f"ur Mengen von Abbildungen. \end{Bemerkung} \begin{Bemerkungl}\index{$\mapsto$} Wir notieren Abbildungen oft in der Form $$\begin{array}{rccl} f:&X & \ra & Y\\ &x & \mapsto & f(x) \end{array}$$ und verschiedenen Verk"urzungen. Zum Beispiel sprechen wir von \glqq einer Abbildung $X\ra Y$\grqq\ oder \glqq der Abbildung $n\mapsto n^3$ von der Menge der nat"urlichen Zahlen in sich selber\grqq. Wir benutzen diese zwei Arten von Pfeilen auch im allgemeinen in derselben Weise. \end{Bemerkungl} \begin{Beispiele} F"ur jede Menge $X$ haben wir die {\bf identische Abbildung}\index{Abbildung!identische Abbildung} 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{Beispiele} \begin{Definition}\label{BiMe} Ist $f:X \ra Y$ eine Abbildung und $A \subset X$ eine Teilmenge, so definieren wir ihr {\bf Bild}\index{Bild} oder genauer ihre {\bf Bildmenge}\index{Bildmenge} $f(A),$ eine Teilmenge von $Y,$ durch $$f(A) = \{ f(x) \mid x \in A\}$$ Eine Abbildung, deren Bild aus genau einem Element besteht, nennen wir eine \defind{konstante Abbildung}.\index{Abbildung!konstante} %damit \ref{ZK} ok ist, zusammenh"angend gdw %stetige Abbildung in diskreten Raum konstant. %Bei uns leere Menge nicht zusammenh"angend! \end{Definition} \begin{Beispiel}\label{Bq} F"ur unsere Abbildung $q:\DZ\ra\DZ,$ $x\mapsto x^2$ von eben gilt $$q (\DZ) = \{a^{2} \mid a \in \DZ\}\subset \DN$$ \end{Beispiel} \begin{Bemerkungl} Gegeben ein festes $c\in Y$ schreiben wir oft auch kurz $c$ f"ur die Abbildung $X\ra Y,$ $x\mapsto c$ f"ur alle $ x\in X$ in der Hoffnung, da"s aus dem Kontext klar wird, ob die Abbildung $c:X\ra Y$ oder das Element $c\in Y$ gemeint sind. Die konstanten Abbildungen sind nat"urlich genau alle Abbildungen dieser Gestalt mit nichtleerem Definitionsbereich $X.$ \end{Bemerkungl} \begin{Definition} Ist $f:X \ra Y$ eine Abbildung und $B \subset Y$ eine Teilmenge, so definieren wir ihr {\bf Urbild}\index{Urbild!von Menge} $f^{-1}(B),$ eine Teilmenge von $X,$ durch $$f^{-1} (B) = \{ x \in X \mid f(x) \in B\}$$ Besteht $B$ nur aus einem Element, so schreiben wir auch $f^{-1} (x)$ statt $f^{-1}(\{x\}).$ F"ur die Abbildung $q$ aus \ref{Bq} gilt zum Beispiel $q^{-1}(1)=\{1,-1\}$ und $q^{-1}(-1)=\emptyset.$ \end{Definition} \begin{Definition} Sind schlie"slich drei Mengen $X,Y,Z$ gegeben und Abbildungen $f : X \ra Y$ und $g:Y \ra Z,$ so definieren wir eine Abbildung $g\circ f:X \ra Z,$ die {\bf Verkn"upfung}\index{Verkn"upfung!von Abbildungen} der Abbildungen $f$ und $g,$ durch die Vorschrift $$\begin{array}{rccl} g \circ f:& X & \ra & Z\\ &x & \mapsto & g(f(x)) \end{array}$$ \end{Definition} \begin{Bemerkungl} 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 Formel $(g \circ f) (x) = g(f(x)).$ Betrachten wir zum Beispiel 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.$ Nat"urlich gilt $(g \circ f)(A) = g(f(A))$ f"ur jede Teilmenge $A\subset X$ und umgekehrt auch $(g\circ f)^{-1}(C) = f^{-1}(g^{-1}(C))$ f"ur jede Teilmenge $C \subset Z.$ \end{Bemerkungl} \begin{figure}[p]\centering \includegraphics[height=5cm]{SkriptenBilder/BildInj}\\[4mm] \noindent Eine Injektion \end{figure} \begin{figure}[p]\centering \includegraphics[height=5cm]{SkriptenBilder/BildSur}\\[4mm] \noindent Eine Surjektion \end{figure} \begin{figure}[p]\centering \includegraphics[height=5cm]{SkriptenBilder/BildBij}\\[4mm] \noindent Eine Bijektion \end{figure} \begin{Definition}\label{ISB} Sei $f:X\ra Y$ eine Abbildung. \begin{enumerate} \item $f$ hei"st {\bf injektiv}\index{injektiv} oder eine {\bf Injektion}\index{Injektion} genau dann, 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.$ \item $f$ hei"st {\bf surjektiv} oder eine {\bf Surjektion}\index{Surjektion} genau dann, wenn es f"ur jedes $y\in Y$ mindestens ein $x \in X$ gibt mit $f(x) =y.$ Surjektionen schreibt man manchmal $\sra.$ \item $f$ hei"st {\bf bijektiv}\index{bijektiv} oder eine {\bf Bijektion}\index{Bijektion} genau dann, 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.$ \end{enumerate} \end{Definition} \begin{Bemerkungl} Ist $X \subset Y$ eine Teilmenge, so ist die {\bf Einbettung}\index{Einbettung} 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=g|X=g|_X:X\ra Z.$ Oft 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. \end{Bemerkungl} \begin{Bemerkungl} Ist $f:X \ra Y$ eine Abbildung, so ist die Abbildung $f:X \ra f(X),$ $x\mapsto f(x)$ stets surjektiv. Der Leser m"oge entschuldigen, da"s wir hier zwei verschiedene Abbildungen mit demselben Symbol $f$ bezeichnet haben. Das wird noch "ofter vorkommen. \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} Seien $f,f_{1}:X \ra Y$ und $g, g_{1} :Y \ra Z$ Abbildungen. \begin{enumerate} \item Ist $g\circ f$ surjektiv, so ist $g$ surjektiv. \item Ist $g\circ f$ injektiv, so ist $f$ injektiv. \item Sind $g$ und $f$ injektiv, so auch $g \circ f.$ \item Sind $g$ und $f$ surjektiv, so auch $g\circ f.$ \item Ist $f$ surjektiv, so folgt aus $g\circ f = g_{1}\circ f$ schon $g=g_{1}.$ \item Ist $g$ injektiv, so folgt aus $g\circ f = g\circ f_{1}$ schon $f = f_{1}.$ \end{enumerate} \end{Satz} \begin{proof}[Beweis] "Ubung. \end{proof} \begin{Bemerkungl} Ist $f: X \ra Y$ eine bijektive Abbildung, so ist die Menge $\{(f(x),x)\in Y\times X\mid x\in X\}$ im Sinne von \ref{DFA} 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} auch die {\bf inverse Abbildung}\index{Abbildung!inverse Abbildung} zu $f$ und wird mit $f^{-1} : Y \ra X$ bezeichnet. Offensichtlich ist mit $f$ auch $f^{-1}$ eine Bijektion. \end{Bemerkungl} \begin{Beispiel} Die Umkehrabbildung unserer Bijektion $t:\DZ\ra\DZ,$ $x\mapsto x+1$ ist die Abbildung $\DZ\ra\DZ,$ $x\mapsto x-1.$ \end{Beispiel} \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{Bemerkungl}\label{ABBK} Gegeben drei Mengen $X,Y,Z$ haben wir eine offensichtliche Bijektion $\op{Ens}(X\times Y,Z)\sira \op{Ens}(X,\op{Ens}( Y,Z)).$ Etwas vage formuliert ist also eine Abbildung $X\times Y\ra Z$ dasselbe wie eine Abbildung, die jedem $x\in X$ eine Abbildung $Y\ra Z$ zuordnet, und symmetrisch nat"urlich auch dasselbe wie eine Abbildung, die jedem $y\in Y$ eine Abbildung $X\ra Z$ zuordnet. \end{Bemerkungl} \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 \ra Y.$ \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$ gesetzt hatten, stimmt unser Satz auch f"ur $n=0.$ \end{proof} \begin{Ubung} Seien $X,Y$ endliche Mengen. So gibt es genau $|Y|^{|X|}$ Abbildungen von $X$ nach $Y,$ und darunter sind genau $|Y|(|Y|-1)(|Y|-2)\ldots(|Y|-|X|+1)$ Injektionen. \end{Ubung} \begin{Ubung} Sei $X$ eine Menge mit $n$ Elementen, und seien $\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{Ubung} \begin{Bemerkung} Manche Autoren bezeichnen diese Zahlen auch als \defnoind{Multinomialkoeffizienten}\index{Multinomialkoeffizient} und verwenden die Notation $$\frac{n!}{\al_1!\cdots\al_r!}= {n \choose {\al_1;\ldots;\al_r}}$$ Mich "uberzeugt diese Notation nicht, da sie im Gegensatz zu unserer Notation f"ur die Binomialkoeffizienten recht eigentlich nichts k"urzer macht. \end{Bemerkung} \begin{Ubung} 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{Ubung} \begin{Ubung} Eine \defnoind{zyklische Anordnung}\index{zyklisch!Anordnung} einer endlichen Menge $M$ ist eine Abbildung $z: M \rightarrow M$ derart, da"s wir durch mehrmaliges Anwenden von $z$ auf ein beliebiges Element $x\in M$ jedes Element $y\in M$ erhalten k"onnen. Man zeige, da"s es auf einer $n$-elementigen Menge mit $n \geq 1$ genau $(n-1)!$ zyklische Anordnungen gibt. \end{Ubung} \begin{figure}[p]\centering \includegraphics[height=0.3\textheight]{SkriptenBilder/BildZyA}\\[4mm] \noindent Versuch der graphischen Darstellung einer zyklischen Anordnung auf der Menge $\{1,2,\ldots,7\}.$ Die Pfeile $\mapsto$ sollen jeweils den Effekt der Abbildung $z$ veranschaulichen. \end{figure} \begin{Bemerkung} Die Terminologie \glqq zyklische Anordnung\grqq\ scheint mir etwas ungl"ucklich, da unsere Struktur nun beim besten Willen keine Ordnung im Sinne von \ref{OM} ist. Andererseits ist das Angeben einer Anordnung auf einer endlichen Menge $M$ schon auch etwas "ahnliches. \end{Bemerkung} \begin{figure}[p]\centering \includegraphics[width=\textwidth]{SkriptenBilder/BildKoKi}\\[4mm] \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} \begin{Ubung}\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{Ubung} \begin{Bemerkung}\label{MuMe} Gegeben eine Menge $X$ mag man sich eine Abbildung $X\ra \DN$ veranschaulichen als eine \glqq Menge von Elementen von $X,$ in der jedes Element mit einer wohlbestimmten Vielfachheit vorkommt\grqq. Aufgrund dieser Vorstellung nennt man eine Abbildung $X\ra \DN$ auch eine \defind{Multimenge} von Elementen von $X.$ Wir notieren die Gesamtheit aller derartigen Multimengen mit $$\cal{M}(X)=\op{Ens}(X,\DN)$$ in vager Analogie zur Potenzmenge $\cal{P}(X)$ von $X,$ die ja in kanonischer Bijektion zu $\op{Ens}(X,\{0,1\})$ steht. Unter der Kardinalit"at einer Multimenge verstehen wir die Summe "uber alle Werte der entsprechenden Abbildung, aufgefa"st als ein Element von $\DN\amalg\{\infty\}.$ \end{Bemerkung} \subsection{Logische Symbole und Konventionen} \begin{Bemerkungl} In der Mathematik meint {\bf oder} immer, da"s auch beides erlaubt ist. Wir haben diese Konvention schon benutzt bei der Definition der Vereinigung wenn wir schreiben $X\cup Y =\{z \mid z \in X \text{ oder } z \in Y\},$ zum Beispiel haben wir $\{1,2\} \cup \{2,3\} = \{1,2,3\}.$ \end{Bemerkungl} \begin{Bemerkungl}\label{SPR} Sagt man der Mathematik, es gebe ein Objekt mit diesen und jenen Eigenschaften, so ist stets gemeint, da"s es \emph{mindestens ein} derartiges Objekt geben soll. H"atten wir diese Sprachregelung rechtzeitig vereinbart, so h"atten wir zum Beispiel das W"ortchen \glqq mindestens\grqq\ in Teil 2 von \ref{ISB} bereits weglassen k"onnen. Sagt ihnen also ein Mathematiker, er habe einen Bruder, so kann es auch durchaus sein, da"s er noch weitere Br"uder hat! Will man in der Mathematik Existenz und Eindeutigkeit gleichzeitig ausdr"ucken, so sagt man, es gebe {\bf genau ein} Objekt mit diesen und jenen Eigenschaften. Sagt ihnen also ein Mathematiker, er habe genau einen Bruder, so k"onnen sie sicher sein, da"s er nicht noch weitere Br"uder hat. \end{Bemerkungl} \begin{Bemerkungl} Die folgenden Abk"urzungen erweisen sich als bequem und werden recht h"aufig verwendet: \vspace{0,5cm} \noindent \begin{tabular}{c@{\hspace{2cm}}l} $\forall$&\index{$\forall$} f"ur alle\\ $\exists$&\index{E@$\exists$} es gibt\\ $\exists!$&\index{E@${\exists\awq}$} es gibt genau ein\\ $\ldots\RA\cdots$&\index{$\Rightarrow$} aus $\ldots$ folgt $\cdots$\\ $\ldots\Leftarrow\cdots$&\index{$\Leftarrow$} $\ldots$ folgt aus $\cdots$\\ $\ldots\Leftrightarrow\cdots$&\index{$\Leftrightarrow$} $\ldots$ ist gleichbedeutend zu $\cdots$\\ \end{tabular} \vspace{0,5cm}\\ Ist zum Beispiel $f:X\ra Y$ eine Abbildung, so k"onnen wir unsere Definitionen injektiv, surjektiv, und bijektiv etwas formaler so schreiben: \vspace{0,5cm} \noindent \begin{tabular}{lcl} $f$ injektiv& $\Leftrightarrow$ & $(f(x)=f(z)\RA x=z)$\\ $f$ surjektiv& $\Leftrightarrow$ & $\forall y\in Y\exists x\in X \text{ mit } f(x)=y$\\ $f$ bijektiv& $\Leftrightarrow$ & $\forall y\in Y\exists ! x\in X \text{ mit } f(x)=y$\\ \end{tabular} \end{Bemerkungl} \begin{Bemerkungl} Bei den \glqq f"ur alle\grqq\ und \glqq es gibt\grqq\ kommt es in der Mathematik sehr auf die Reihenfolge an, viel mehr als in der weniger pr"azisen Umgangssprache. Man betrachte zum Beispiel die beiden folgenden Aussagen: \begin{quote} \glqq F"ur alle $n\in \DN$ gibt es $m \in \DN$ so da"s gilt $m \geq n$\grqq\ \end{quote} \begin{quote} \glqq Es gibt $m \in \DN$ so da"s f"ur alle $n \in \DN$ gilt $m \geq n$\grqq\ \end{quote} Offensichtlich ist die erste richtig, die zweite aber falsch. Weiter mache man sich klar, da"s die \glqq f"ur alle\grqq\ und \glqq es gibt\grqq\ bei Verneinung vertauscht werden. "Aquivalent sind zum Beispiel die beiden folgenden Aussagen \begin{quote} \glqq Es gibt kein $n \in \DN$ mit $n^{2}=2$\grqq\ \end{quote} \begin{quote} \glqq F"ur alle $n \in \DN$ gilt $n^{2}\neq 2$\grqq\ \end{quote} \end{Bemerkungl} \begin{Bemerkungl} Wollen wir zeigen, da"s aus einer Aussage $A$ eine andere Aussage $B$ folgt, so k"onnen wir ebensogut zeigen: Gilt $B$ nicht, so gilt auch $A$ nicht. In formelhafter Schreibweise haben wir also $$(A\RA B)\Leftrightarrow((\text{nicht } B)\RA (\text{nicht } A))$$ Wollen wir zum Beispiel zeigen $(g\circ f \text{ surjektiv})\RA (g \text{ surjektiv}),$ so reicht es, wenn wir uns "uberlegen: Ist $g$ nicht surjektiv, so ist $g\circ f$ erst recht nicht surjektiv. \end{Bemerkungl} %%% Local Variables: %%% mode: latex %%% TeX-master: "AATOTAL" %%% End: \message{ !name(AATOTAL.tex) !offset(-969) } \end{document}