%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{GGrund} \section{Naive Mengenlehre und Kombinatorik} \nichtfinal{Es w"are vielleicht eine zus"atzliche Motivation durch Anwendungen in der elementaren Wahrscheinlichkeitstheorie sinnvoll.} \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. 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{WHK}. 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 \ref{AuZ} finden. \end{Beispiele} %\nichtfinal{\begin{Bemerkungl}[\textbf{Mehrdeutigkeiten mit dem Komma als Trenner}] % Die Verwendung des Kommas als Trenner zwischen den Elementen einer Menge %ist %insofern problematisch, als $\{1,2\}$ nun einerseits als %die Menge mit den beiden Elementen $1$ und $2$ verstanden werden kann, %andererseits aber auch als %die Menge mit dem Dezimalbruch $1,\!2$ als einzigem Element. %Was im Einzelfall gemeint ist, gilt es durch genaues Pr"ufen des Freiraums %%nach dem Komma zu erschlie"sen, % oder noch besser aus dem %Kontext. In diesem Text %werden Dezimalbr"uche nur selten vorkommen. %Es wird dahingegen oft vorkommen, da"s sich %die Bedeutung einer Formel erst aus dem Kontext erschlie"st. %\end{Bemerkungl}} \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{Kard} 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 \eref{QR}{AN1} und f"ur eine genauere Diskussion des Begriffs der Kardinalit"at vergleiche \eref{KaZa}{AL}. \end{Bemerkungl} \subsection{Teilmengen} \label{Tm} \begin{Definition} Eine Menge $Y$ hei"st {\bf Teilmenge}\index{Menge!Teilmenge}\index{Teilmenge} einer Menge $X$, wenn jedes Element 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{geho} 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 eine zus"atzlich noch 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{Bemerkungl} % Bereits an dieser Stelle ist unsere Notation nicht % eindeutig: Ich wollte mit $\{0,1\}$ die zweielementige Menge mit % den beiden Elementen Null und Eins andeuten, % das k"onnte jedoch auch als die Menge mit % der Dezimalzahl $0,\!1$ als einzigem Element interpretiert % werden. Es wird noch oft vorkommen, da"s sich % die Bedeutung einer Formel erst aus dem Kontext erschlie"st. % Im folgenden werden Kommas fast % nie als Kommas einer Dezimalzahl zu verstehen sein. % Beim genauen Hinsehen kann man am Abstand hinter dem Komma % erkennen, wann doch eine Dezimalzahl gemeint ist. % \end{Bemerkungl} \begin{Definition}\label{MeKo} 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[BiKoe]{Binomialkoeffizient} ${n\choose k}$ die Zahl der $k$-elementigen Teilmengen einer $n$-ele\-men\-tigen Menge an.\label{BK} 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{MGKK} 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 \eref{BBK}{EIN} 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 \eref{BiFoA}{EIN}. Wir rechnen dazu\label{PFB} $$(a+b)^n=\sum_{Y\subset\{1,2,\ldots,n\}} a^{|Y|} b^{n-|Y|}$$ Die rechte Seite soll hier in Verallgemeinerung der in \eref{Summ}{EIN} 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{BK} 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{Mop} \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{MGKK} \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\}$; \begin{figure}[h] \centering \includegraphics[height=0.25\textheight]{SkriptenBilder/BildMop} \\ \noindent Van-de-Ven-Diagramme f"ur Vereinigung, Schnitt und Differenz \end{figure} \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} \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} \begin{figure}[htb] \begin{minipage}{0.45\textwidth} \includegraphics[width=\textwidth]{SkriptenBilder/BildPe} \end{minipage}\hfill \begin{minipage}{0.45\textwidth}\centering 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\in X$ und neben $y\in Y$ liegt. \end{minipage} \end{figure} \begin{figure}[htb] \begin{minipage}{0.45\textwidth} \includegraphics[width=\textwidth]{SkriptenBilder/BildKar} \end{minipage}\hfill \begin{minipage}{0.45\textwidth}\centering Dies Bild mu"s anders interpretiert werden als das vorherige. 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{minipage} \end{figure} \end{Definition} \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 nebenstehenden 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{MGKK} 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{fBild}[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{fBild} \begin{fBild}[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{fBild} \begin{Bemerkungl}\label{VMR} 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 nebenstehenden 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{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{WHK} 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{SVMF}{AN1} 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 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 von neuem 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{EFGl} \end{Ubung} \subsection{Abbildungen} \label{AnB} \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{fBild}[p] \centering \includegraphics[height=0.4\textheight]{SkriptenBilder/Bild0002} \\ \noindent Eine Abbildung einer Menge mit f"unf in eine mit drei Elementen \end{fBild} \begin{fBild}[p] \centering \includegraphics[height=0.4\textheight]{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{fBild} \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{DFA} $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{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{EnSS} $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{Definition} Sei $f:X \ra Y$ eine Abbildung.\label{BiMeA}\begin{enumerate} \item Gegeben eine Teilmenge $A \subset X$ erkl"aren wir das {\bf Bild von $A$ unter $f$},\index{Bild!einer Teilmenge} eine Teilmenge $f(A)\subset Y$, durch $$f(A) \pdef \{y\in Y \mid \text{Es gibt }x \in A\text{ mit }f(x)=y\}$$ \item Gegeben eine Teilmenge $B \subset Y$ erkl"aren wir das {\bf Urbild von $B$ unter $f$}\index{Urbild!von Menge}, eine Teilmenge von $ f^{-1}(B)\subset X$, durch $$f^{-1} (B) \pdef \{ x \in X \mid f(x) \in B\}$$ \end{enumerate} \end{Definition} \begin{Bemerkungl} Das Bild von ganz $X$ nennen wir das {\bf Bild von $f$} und notieren es $\op{im}(f)\pdef f(X)$. Das K"urzel $\op{im}$ steht f"ur franz"osisch und\index{im@$\op{im}$!Bild von Abbildung} englisch {\bf image}. \end{Bemerkungl} \begin{Beispiel} F"ur unsere Abbildung $q:\DZ\ra\DZ$, $n\mapsto n^2$ des Quadrierens von eben k"onnten wir die Menge aller Quadratzahlen schreiben als\label{Bq} $$q (\DZ) = \{a^{2} \mid a \in \DZ\}$$%\subset \DN Ebenso w"are $\{ 2a \mid a \in \DN\}$ eine m"ogliche formelm"a"sige Darstellung der Menge aller geraden nat"urlichen Zahlen, und $\{ab \mid a,b \in \DN , a \geq 2, b \geq 2\}$ w"are eine formelm"a"sige Darstellung der Menge aller nat"urlichen Zahlen, die nicht prim und auch nicht Null oder Eins sind. \end{Beispiel} \begin{Bemerkungl} Eine Abbildung, deren Bild aus h"ochstens einem Element besteht, nennen wir eine {\bf konstante Abbildung}.\index{konstant!Abbildung}\index{Abbildung!konstante} Eine Abbildung, deren Bild aus genau einem Element besteht, nennen wir eine\label{einw} \defind{einwertige Abbildung}.\index{Abbildung!einwertige} Eine einwertige Abbildung ist also eine konstante Abbildung mit nichtleerem Definitionsbereich. \end{Bemerkungl} \begin{Bemerkungl}[\textbf{Konstanten und konstante Abbildungen}] Gegeben ein festes $c\in Y$ schreiben wir oft auch kurz $c$ f"ur die 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{Bemerkungl} Gegeben eine Abbildung $f:X\ra Y$ ist formal $f^{-1}$ eine Abbildung $f^{-1}:\mathcal P(Y)\ra \mathcal P(X)$ in der Gegenrichtung auf den Potenzmengen. Besteht $B$ nur aus einem Element $x$, so schreiben wir auch $f^{-1} (x)$ statt $f^{-1}(\{x\})$ und nennen diese Menge die {\bf Faser}\index{Faser!einer Abbildung}\index{)6aa@$f^{-1}$ Urbild von Menge} {\bf von $f$ \"{u}ber} $x$ oder {\bf bei} $x$. Das Quadrieren $q$ aus \ref{Bq} hat etwa die Faser $q^{-1}(1)=\{1,-1\}$ bei $1$ und die Faser $q^{-1}(-1)=\emptyset$\label{Faser} bei $-1$. \end{Bemerkungl} \begin{Bemerkungl}[\textbf{Diskussion der Notation}] Die Notation $f^{-1}(B)$ f"ur das Urbild einer Menge unter einer Abbildung f"uhrt leicht zu Verwirrung, da man $a^{-1}$ aus der Schule als alternative Notation f"ur den Bruch $a^{-1}=1/a$ gewohnt ist. Diese beiden Notationen sind nur entfernt verwandt und werden beide in der Mathematik durchgehend verwendet. Was im Einzelfall gemeint ist, gilt es aus dem Kontext zu erschlie"sen. \end{Bemerkungl} \subsection{Verkn"upfung von Abbildungen} \label{VerAA} \begin{Definition}\label{KkA} 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{Ubunge}\label{BiuB} % Sei $X$ eine Menge und $f:X\ra X$ eine Abbildung. % Bezeichne $f^n=f\circ f\circ \ldots\circ f:X\ra X$ das % \glqq $n$-malige Ausf"uhren von $f$\grqq. % Im Extremfall $n=0$ verstehen wir $f^0=\op{id}$. % Sei nun $C\subset X$ eine Teilmenge. % Man zeige: % Stimmen f"ur ein $n\in\DN$ die Bildmengen $f^n(C)$ und $f^{n+1}(C)$ % "uberein, % so gilt bereits $f^n(C)=f^{n+1}(C)=f^{n+2}(C)\ldots $ % Stimmen f"ur ein $n\in\DN$ die Urbildmengen $(f^n)^{-1}(C)$ und % $(f^{n+1})^{-1}(C)$ % "uberein, % so gilt bereits $(f^n)^{-1}(C)=(f^{n+1})^{-1}(C)=(f^{n+2})^{-1}(C)\ldots $ % \end{Ubunge} \begin{fBild}[p]\centering \includegraphics[height=0.2\textheight]{SkriptenBilder/BildSurv}\\[4mm] \noindent Eine Surjektion \end{fBild} \begin{fBild}[p]\centering \includegraphics[height=0.2\textheight]{SkriptenBilder/BildInjv}\\[4mm] \noindent Eine Injektion \end{fBild} \begin{fBild}[p]\centering \includegraphics[height=0.2\textheight]{SkriptenBilder/BildBij}\\[4mm] \noindent Eine Bijektion \end{fBild} \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} \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} \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} \end{enumerate} \end{Definition} \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 zu einer Abbildung $q : \DN \ra \DZ$ ist aber durchaus injektiv. \end{Bemerkungl} \begin{Bemerkungl}[\textbf{Surjektion auf das Bild}] Ist\label{VStea} $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. "Uberhaupt ignorieren wir, gegeben Mengen $X,Y$ und eine Teilmenge $Z\subset Y$, im folgenden meist den Unterschied zwischen einer \glqq Abbildung von $X$ nach $Y$, deren Bild in $Z$ enthalten ist\grqq\ und einer \glqq Abbildung von $X$ nach $Z$\grqq. \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{InSu} 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$; \item Genau dann ist $g$ injektiv, wenn f"ur beliebige Abbildungen $f_1,f_2:X \ra Y$ aus $g\circ f_1 = g\circ f_{2}$ schon folgt $f_1 = f_{2}$. \end{enumerate} \end{Satz} \begin{proof}[Beweis] "Ubung. Besonders elegant ist es, zun"achst die letzte Aussage zu zeigen, und dann die vorderen Aussagen ohne weitere Betrachtung von Elementen zu folgern. \end{proof} \begin{Bemerkungl}[\textbf{Universelle Eigenschaft von Injektionen}] Sei $i:Y\hra X$ eine injektive Abbildung und $\varphi:Z\ra X$ eine beliebige Abbildung. Genau dann gibt es eine Abbildung $\tilde\varphi:Z\ra Y$ mit $i\circ \tilde\varphi=\varphi$, wenn gilt $\op{im}(\varphi)\subset \op{im}(i)$.\label{UEI} Nach dem Vorhergehenden ist diese Abbildung $\tilde\varphi$ dann sogar eindeutig bestimmt. \end{Bemerkungl} \begin{Satz}\label{InSun}%\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$; \item Genau dann ist $f$ surjektiv, wenn f"ur beliebige Abbildungen $g_1,g_2:Y\ra Z$ aus $g_1\circ f = g_{2}\circ f$ schon folgt $g_1=g_{2}$. \end{enumerate} \end{Satz} \begin{proof}[Beweis] "Ubung. Besonders elegant ist es, zun"achst die letzte Aussage zu zeigen, und dann die vorderen Aussagen ohne weitere Betrachtung von Elementen zu folgern. \end{proof} \begin{Bemerkungl}[\textbf{Universelle Eigenschaft von Surjektionen}] Sei $s:X\sra Y$ eine surjektive Abbildung und $\varphi:X\ra Z$ eine beliebige Abbildung. Offensichtlich gibt es genau dann eine Abbildung $\bar\varphi:Y\ra Z$ mit $\bar\varphi\circ s=\varphi$, wenn $\varphi$ auf den \hyperref[Faser]{Fasern} von $s$ konstant ist.\label{UES} Nach dem Vorhergehenden ist diese Abbildung $\bar\varphi$ dann sogar eindeutig bestimmt. Diese Erkenntnis ist insbesondere f"ur die Algebra relevant. \end{Bemerkungl} \begin{figure}[htb] \begin{minipage}{0.45\textwidth} \includegraphics[width=\textwidth]{SkriptenBilder/Usu} \end{minipage}\hfill \begin{minipage}{0.45\textwidth}\centering Universelle Eigenschaft von Surjektionen in einem Beispiel \end{minipage} \end{figure} \begin{Bemerkungl} 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{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} 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{BdF} \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{Ubung} Sind Abbildungen $f : X \ra Y$ und $g:Y \ra Z$ gegeben, so haben wir $(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{Ubung} \begin{Ubunge}\label{MnMK} 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{MnMK} 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{zyA} 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. Die Terminologie \glqq zyklische Anordnung\grqq\ ist etwas ungl"ucklich, da unsere Struktur nun beim besten Willen keine Anordnung im Sinne von \eref{OM}{AN1} ist. Andererseits ist aber das Angeben einer Anordnung auf einer endlichen Menge $M$ schon auch etwas "Ahnliches. \end{Ubunge} \begin{fBild}[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{fBild} \begin{fBild}[p]\centering \includegraphics[height=0.25\textheight]{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{fBild} \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} \subsection{Erg"anzungen zur Mengenlehre*} \begin{Bemerkungl}[\textbf{Kommutativit"at kartesischer Produkte}] Ich insistiere darauf, da"s gegeben Mengen $X,Y$ die kartesischen Produkte $X\times Y$ und $Y\times X$ f"ur uns verschiedene Mengen sind. Es gibt zwischen diesen kartesischen Produkten zwar die ausgezeichneten Bijektionen $\tau_{X,Y}:X\times Y\sira Y\times X$ mit $(x,y)\mapsto (y,x)$ und $\tau_{Y,X}$ ist stets die Umkehrabbildung zu $\tau_{X,Y}$, aber $\tau_{X,X}$ mu"s keineswegs die Identit"at auf $X^2$ sein, das gilt vielmehr nur f"ur $|X|\leq 1$. \end{Bemerkungl} \begin{Bemerkungw} In \eref{SchB}{AL} zeigen wir den Satz von Schr"oder-Bernstein: Sind $X$ und $Y$ Mengen und gibt es sowohl eine Injektion $f:X\hra Y$ als auch eine Injektion $g:Y\hra X$, so gibt es sogar eine Bijektion $b:X\sira Y$. \end{Bemerkungw} \begin{Definition} Die Menge aller Abbildungen von $X$ nach $Y$ bezeichne ich mit\index{Ens@$\op{Ens}(X,Y)$ Abbildungen $X\ra Y$} $$\op{Ens}(X,Y)$$ nach der franz"osischen "Ubersetzung \defind{ensemble} des deutschen Begriffs \glqq Menge\grqq. \end{Definition} \begin{Bemerkungl}[\textbf{Diskussion der Terminologie}] "Ublicher ist statt unserem $\op{Ens}(X,Y)$ die Notation $Y^X$\index{)8bb@$Y^X$!statt $\op{Ens}(X,Y)$}. Noch gebr"auchlicher ist in der deutschen Literatur die Bezeichnung $\op{Abb}(X,Y)$\index{Abb@$\op{Abb}$} f"ur die Menge aller Abbildungen von $X$ nach $Y$. Ich will jedoch in \eref{UEns}{LA2} die \glqq Kategorie aller Mengen\grqq\ wie Gabriel \cite{Gabriel} 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)$. Das erkl"art die hier gew"ahlte Bezeichnung f"ur Mengen von Abbildungen. \end{Bemerkungl} \begin{Bemerkungl}[\textbf{Exponentialgesetz}] Gegeben drei Mengen $X,Y,Z$ erhalten wir eine\label{ABBK} Bijektion $$\op{Ens}(X\times Y,Z)\sira \op{Ens}(X,\op{Ens}( Y,Z))$$ durch die Vorschrift $f\mapsto f(x,\;)$ mit der Notation $f(x,\;)$ f"ur die Abbildung $y\mapsto f(x,y)$. Etwas vage formuliert ist also eine Abbildung $X\times Y\ra Z$ von einem kartesischen Produkt $X\times Y$ in eine weitere Menge $Z$ dasselbe wie eine Abbildung, die jedem $x\in X$ eine Abbildung $Y\ra Z$ zuordnet, und umgekehrt nat"urlich auch dasselbe wie eine Abbildung, die jedem $y\in Y$ eine Abbildung $X\ra Z$ zuordnet. In der exponentiellen Notation liest sich das besonders suggestiv als kanonische Bijektion $Z^{(X\times Y)}\sira (Z^X)^Y$. Wegen dieser Notation zitiert man diese Aussage auch als das {\bf Exponentialgesetz}.\index{Exponentialgesetz!f"ur Mengen} In wieder anderen Worten sind also die in der Schule derzeit so beliebten \glqq Funktionen mit Parameter\grqq\ nichts anderes als \glqq Funktionen von zwei Variablen, bei denen eine der beiden Variablen als Parameter bezeichnet wird\grqq. \end{Bemerkungl} \begin{Bemerkungw} Sp"ater bezeichnen wir eine Abbildung $X\times Y\ra Z$ auch als eine {\bf $2$-Multiabbildung}\index{Multiabbildung!$2$-Multiabbildung} und notieren sie $X\curlyvee Y\ra Z$ mit dem als reinem Trenner zu verstehenden Symbol $\curlyvee$\index{)8a@$\curlyvee$ Trenner!bei Multiabbildungen} und erkl"aren allgemeiner \glqq $r$-Mul\-ti\-ab\-bil\-dun\-gen\grqq\ f"ur beliebiges $r\in \DN$\label{Muabb} sowie deren \glqq Multiverkn"upfung\grqq, aber alles zu seiner Zeit. \end{Bemerkungw} \begin{Bemerkunge}[\textbf{Unm"ogliche Surjektionen}] Eine Abbildung $f : X \rightarrow \mathcal P (X)$ von einer Menge in ihre Potenzmenge kann nie surjektiv sein. In der Tat, betrachten wir in $X$ die Teilmenge\label{KaPo} $A =\{ x \in X \mid x \not\in f (x) \}$, so kann es kein $y \in X$ geben mit $f (y) = A$, denn f"ur solch ein $y$ h"atten wir entweder $y \in A$ oder $y \not\in A$, und aus $y \in A$ alias $y \in f (y)$ folgte $y \not\in A$, wohingegen aus $y \not\in A$ alias $y \not\in f(y)$ folgte $y\in A$. Ordnen wir etwa jedem Menschen die Menge aller der Menschen zu, die er liebt, und betrachten die Menge aller Menschen, die sich nicht selbst lieben, so wird diese Menge f"ur keinen Menschen genau aus all den Menschen bestehen, die er liebt. \end{Bemerkunge} \begin{Bemerkunge}\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 nennen wir eine Abbildung $X\ra \DN$ auch eine \defind{Multimenge} von Elementen von $X$. Unter der {\bf Kardinalit"at einer Multimenge}\index{Kardinalit"at!einer Multimenge} verstehen wir die Summe "uber die Werte der entsprechenden Abbildung an allen Stellen $x\in X$, aufgefa"st als ein Element von $\DN\amalg\{\infty\}$. Ich notiere Multimengen durch Mengenklammern mit einem vorgestellten unteren Index $\mu$. So w"are etwa $_\mu\{5,5,5,7,7,1\}$\index{)5@$_\mu\{\;\}$ Multimenge} eine\index{m@$_\mu\{\;\}$ Multimenge} Multimenge von nat"urlichen Zahlen der Kardinalit"at $6$. Diese Notation ist aber nicht gebr"auchlich. Die Gesamtheit aller endlichen Multimengen von Elementen einer Menge $X$ notiere ich auch $\mathbb N X$. %oder $\op{Kmon}^\frei X$ f"ur \glqq freies kommutatives Monoid "uber $X$\grqq. Eine Multimenge der Kardinalit"at Zwei von Elementen einer Menge $X$ nenne ich ein {\bf ungeordnetes Paar}\index{Paar!ungeordnetes} von Elementen von $X$. \end{Bemerkunge} \begin{Bemerkungl} Gegeben $S\supset T$ eine Menge mit einer Teilmenge und $f:S\ra S$ eine Selbstabbildung von $S$ sagen wir, $T$ sei {\bf stabil unter $f$} und {\bf $f$ stabilisiert $T$},\index{stabil!Teilmenge unter Selbstabbildung} wenn\index{stabilisiert} gilt $f(T)\subset T$. Gilt sogar $f(T)=T$, so sagen wir, $T$ {\bf werde von $f$ festgehalten}.\index{festgehalten!Teilmenge unter Selbstabbildung} Gilt noch st"arker $f(t)=t\;\forall t\in T$, so sagen wir, $T$ {\bf werde von $f$ punktweise festgehalten}.\index{festgehalten!Teilmenge unter Selbstabbildung!punktweise} \end{Bemerkungl} \begin{Beispiel} F"ur jede Menge $X$ mag man die {\bf Mengenabbildung}\index{Mengenabbildung} $X\hra \mathcal P(X)$, $x\mapsto \{x\}$ betrachten. Ihr Bild ist die Menge\index{P@$\mathcal P_1(X)$ einelementige Teilmengen von $X$} $$\mathcal P_1(X)\subset \mathcal P(X)$$ aller einelementigen Teilmengen von $X$. Die Umkehrabbildung der so entstehenden Bijektion\label{P1M} $X\sira \mathcal P_1(X)$ notieren wir $\op{elt}:\mathcal P_1(X)\ra X$\index{elt@$\op{elt}$ Elementabbildung} und nennen sie die {\bf Elementabbildung}.\index{Elementabbildung} Sie ordnet jeder einelementigen Teilmenge von $X$ ihr einziges Element zu. \end{Beispiel} \begin{Bemerkungw}[\textbf{Formalisierung des Begriffs der nat"urlichen Zahlen}] Wir werden in \eref{NatZ}{LA1} zeigen, da"s es Paare $(N,s)$ gibt bestehend aus einer\label{DNZZ} Menge $N$ und einer injektiven Abbildung $s:N\ra N$ derart, da"s $N\backslash s(N)$ aus genau einem Element $o$ besteht und da"s jede $s$-stabile Teilmenge von $N$, die $o$ enth"alt, bereits ganz $N$ sein mu"s. Weiter werden wir zeigen, da"s solch ein Paar im Wesentlichen eindeutig bestimmt ist in dem Sinne, da"s es f"ur jedes weitere derartige Paar $(N',s')$ genau eine Bijektion $\varphi:N\sira N'$ gibt mit $s'\varphi=\varphi s$. Im Rahmen der ganz naiven Mengenlehre kann man solch ein Paar unmittelbar angeben als $(\DN, s)$ mit $s:n\mapsto (n+1)$. Bei einem etwas formaleren Aufbau der Mathematik aus der Mengenlehre mag man umgekehrt von derartigen Paaren ausgehen und so zu einer Definition von $\DN$ und der Addition auf $\DN$ gelangen, vergleiche \eref{NatZ}{LA1} folgende. Hier liegt auch der Schl"ussel f"ur eine formale Rechtfertigung des Prinzips der vollst"andigen Induktion. \end{Bemerkungw} \begin{Bemerkungw} Sie sehen bereits an dieser Stelle, wie problematisch der Begriff der Gleichheit im Grunde genommen ist und wie nah er an der Wurzel mathematischen Denkens liegt. Um ein besonders einfaches Beispiel zu bem"uhen, mag man sich fragen, ob je zwei einelementige Mengen gleich sind. Unsere Antwort hier mu"s lauten: Nat"urlich nicht, zwei einelementige Teilmengen einer gegebenen Menge etwa sind genau dann gleich, wenn sie dasselbe Element enthalten. Allerdings gibt es andererseits zwischen je zwei einelementigen Mengen genau eine Bijektion, eine einelementige Menge ist also \glqq eindeutig bis auf eindeutige Bijektion\grqq. \end{Bemerkungw} \subsubsection*{"Ubungen} \begin{Ubunge}\label{EAD} Gegeben eine fest gedachte Menge $Y$ k"onnen wir f"ur jede weitere Menge $A$ eine Abbildung $\op{ev}_A: A\ra \op{Ens}(\op{Ens}(A,Y),Y)$,\index{ev@$\op{ev}$ Auswertungsabbildung} genannt die {\bf Evaluations-}\index{Evaluationsabbildung} oder {\bf Auswertungsabbildung},\index{Auswertungsabbildung} erkl"aren durch die Vorschrift $\op{ev}_A:a\mapsto (f\mapsto f(a))$. Man zeige, da"s f"ur jede Menge $X$ die Komposition $$\op{Ens}(X,Y)\ra \op{Ens}(\op{Ens}(\op{Ens}(X,Y),Y),Y)\ra \op{Ens}(X,Y)$$ von $\op{ev}_{\op{Ens}(X,Y)}$ mit dem Vorschalten $(\circ\op{ev}_X)$ von $\op{ev}_X$ die Identit"at auf $\op{Ens}(X,Y)$ ist. Sp"ater werden Sie diese Aussage m"oglicherweise als die \glqq Dreiecksidentit"at\grqq\ im Kontext \glqq adjungierter Funktoren\grqq\ in \eref{FADJj}{TF} verstehen lernen. \end{Ubunge} \subsection{Logische Symbole und Konventionen} \begin{Bemerkungl} In der mathematischen Fachsprache meint {\bf oder}\index{oder} immer, da"s auch beides erlaubt ist. Wir haben diese Konvention schon benutzt bei der Definition der Vereinigung in \ref{MGKK} durch die Vorschrift $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\}$. In diesem Zusammenhang mu"s ich die sch"one Geschichte erz"ahlen von dem Logiker, der seinem Freund erz"ahlt, er habe ein Kind bekommen. Der Freund fragt: \glqq Ist es ein Junge oder ein M"adchen?\grqq\ worauf der Logiker antwortet: \glqq Ja!\grqq\ \end{Bemerkungl} \begin{Bemerkunge}[\textbf{Herkunft des Vereinigungssymbols}] In den \glqq Arithmetes principia\grqq\ von Guiseppe Peano scheint das Symbol $\cup$ zum ersten Mal vorzukommen, allerdings als Symbol f"ur \glqq oder\grqq. Peano schreibt: \glqq Signum $\cup$ legitur \emph{vel}\grqq\ und \glqq vel\grqq\ hei"st \glqq oder\grqq\ auf lateinisch. Der Kontext legt nahe, da"s $\cup$ an den Buchstaben $v$ erinnern soll. Das Symbol $\vee$ hatte Peano schon als Symbol f"ur \glqq verum\grqq\ verbraucht. In der Bedeutung der Vereinigung zweier Mengen habe ich das Symbol zuerst bei Bourbaki gesehen. \end{Bemerkunge} \begin{Bemerkungl}\label{SPR} Sagt man der mathematischen Fachsprache, 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 mathematischen Fachsprache 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}\label{abk} Die folgenden Abk"urzungen erweisen sich als bequem und werden h"aufig verwendet: \vspace{0,5cm} \noindent \begin{tabular}{c@{\hspace{2cm}}l} $\forall$&\index{)0aex@$\forall$ f"ur alle} f"ur alle (ein umgedrehtes A wie \glqq alle\grqq)\\ $\exists$&\index{)0aex@$\exists$ es existiert ein} es gibt (ein umgedrehtes E wie \glqq existiert\grqq)\\ $\exists!$&\index{)0aex@${\exists\awq}$ es existiert genau ein} es gibt genau ein\\ $\ldots\RA\cdots$&\index{)4@$\Rightarrow$ impliziert} aus $\ldots$ folgt $\cdots$\\ $\ldots\Leftarrow\cdots$&\index{)4@$\Leftarrow$ folgt aus} $\ldots$ folgt aus $\cdots$\\ $\ldots\Leftrightarrow\cdots$&\index{)4@$\Leftrightarrow$ gleichbedeutend} $\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} In den Zeiten des Bleisatzes war es nicht einfach, neue Symbole in Druck zu bringen. Irgendwelche Buchstaben verdreht zu setzen, war jedoch unproblematisch. So entstanden die Symbole $\forall$ und $\exists$. Sie hei"sen {\bf Quantoren}.\index{Quantor} \end{Bemerkungl} \begin{Bemerkungl} Bei den \glqq f"ur alle\grqq\ und \glqq es gibt\grqq\ kommt es in der mathematischen Fachsprache, anders als in der weniger pr"azisen Umgangssprache, entscheidend auf die Reihenfolge an. 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 nicht $n^{2}= 2$\grqq\ \end{quote} \end{Bemerkungl} \begin{Bemerkungl}\label{BWD} Wollen wir zeigen, da"s aus einer Aussage $A$ eine weitere 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. Oder ein Beispiel aus dem t"aglichen Leben: Die Aussage (Wenn ein Mensch ein Kind gebiert, ist er eine Frau) ist gleichbedeutend zur Aussage (Wenn ein Mensch keine Frau ist, gebiert er auch keine Kinder). Nicht folgern kann man dahingegen die Aussage (Wenn ein Mensch kein Kind gebiert, ist er keine Frau). \end{Bemerkungl} \begin{Bemerkungl} In der Literatur findet man oft die Abk"urzung {\bf oBdA} f"ur \glqq ohne Beschr"ankung der Allgemeinheit\grqq. \index{oBdA ohne Beschr"ankung der Allgemeinheit} \end{Bemerkungl} %%% Local Variables: %%% mode: latex %%% TeX-master: "XXGR" %%% End: %makeindex -g -s german.ist XXGR.idx %pdflatex "\PassOptionsToPackage{final}{showkeys}\PassOptionsToPackage{final}{ifdraft}\input{XXGR}" %scp /home/soergel/Dokumente/Skripten/Skripten/XXGR.pdf soergel@tux00.mathematik.uni-freiburg.de:/webserver/home/soergel/Skripten/XXGR.pdf