\section{Zahlen} \subsection{Konstruktion der nat"urlichen Zahlen*}\label{NatZ}\index{nat"urliche Zahlen} \begin{Bemerkungl} Im folgenden diskutiere ich eine Beschreibung der nat"urlichen Zahlen im Rahmen der naiven Mengenlehre. Eine vollst"andig "uberzeugende Diskussion dieser Struktur ist meines Erachtens nur im Rahmen der Logik m"oglich. Mir f"allt es bei diesem Beweis besonders schwer, ihn an der Tafel zu entwickeln, da mir alle darin gezeigten Aussagen eh offensichtlich scheinen und ich nie erinnern kann, was an einer vorgegebenen Stelle des Beweisgangs bereits formal hergeleitet ist. \end{Bemerkungl} \begin{Bemerkungl}\label{eue} F"uhrt man die Mengenlehre axiomatisch ein, so mag man eine Menge als {\bf unendlich} erkl"aren,\index{unendlich!Menge} wenn es eine injektive nicht bijektive Abbildung von unserer Menge in sich selbst gibt. Eine Menge hei"st dann {\bf endlich}\index{endlich!Menge}, wenn sie nicht unendlich ist. Die Existenz einer unendlichen Menge ist ein Axiom der Zermelo-Fraenkel-Mengenlehre, wir nennen es das {\bf Unendlichkeitsaxiom}.\index{Unendlichkeitsaxiom} Bei Zermelo und Fraenkel ist diese Axiomatik noch formaler und pr"aziser, aber so weit gehen wir hier nicht. \end{Bemerkungl} \begin{Satz}[\textbf{Die nat"urlichen Zahlen}] \begin{enumerate} \item Es gibt Paare $(N,s)$ aus einer Menge $N$ und einer injektiven Abbildung $s:N\hra N$ derart, da"s $N\backslash s(N)$ aus einem einzigen Element $o$ besteht und da"s jede $s$-stabile Teilmenge von $N$, die $o$ enth"alt, bereits ganz $N$ sein mu"s; \item Sei $(N,s)$ solch ein Paar. Gegeben $(X,x,f)$ ein Tripel bestehend aus einer Menge $X$, einem Element $x\in X$ und einer Abbildung $f:X\ra X$ gibt es dann genau eine Abbildung $\psi : N \ra X$ mit $\psi (o)=x$ und $\psi s=f\psi$; \item Ein Paar $(N,s)$ wie im ersten Teil ist im wesentlichen eindeutig bestimmt. Ist genauer $(N',s')$ ein weiteres derartiges Paar und $\{o'\}=N'\backslash s'(N')$, so ist die eindeutig bestimmte Abbildung $\psi:N\ra N'$ aus dem zweiten Teil mit $s'\psi=\psi s$ und $\psi(o)=o'$ eine Bijektion. \end{enumerate}\label{EDNC} %\label{NatZz} \end{Satz} \begin{figure}[htb] \begin{minipage}{0.45\textwidth} \includegraphics[width=\textwidth]{SkriptenBilder/Bildins} \end{minipage}\hfill \begin{minipage}{0.45\textwidth}\centering Versuch der graphischen Darstellung einer Menge mit einer injektiven aber nicht surjektiven Abbildung zu sich selbst. \end{minipage} \end{figure} \begin{Bemerkungl} Sobald der Satz bewiesen ist, halten wir ein derartiges Paar $(N,s)$ ein f"ur allemal fest, verwenden daf"ur die Notation $(\DN,s)$, erlauben uns aufgrund der Eindeutigkeit den bestimmten Artikel und nennen $\DN$ die Menge der {\bf nat"urlichen Zahlen}.\index{nat"urliche Zahlen} Gegeben $a\in \DN$ hei"st $s(a)$ der {\bf Nachfolger} oder genauer der {\bf unmittelbare Nachfolger}\index{Nachfolger} von $a$.\label{Nhoc} Die Notation $s$ steht f"ur \glqq successor\grqq. Wir vereinbaren f"ur das eindeutig bestimmte Element von $\DN$, das kein Nachfolger ist und das oben $o$ hie"s, die Notation $0\in\DN$\index{)0@$0$ neutrales Element f"ur $+$!nat"urliche Zahl} und die Bezeichnung {\bf Null}.\index{Null} \end{Bemerkungl} \begin{Bemerkungl} Gegeben eine Menge $X$ und zwei Abbildungen $\psi, \phi: \DN \ra X$ mit $\psi(0)=\phi(0)$ und $\big(\psi(b)=\phi(b)\RA \psi(s(b))=\phi(s(b))\big)$ folgt $\psi=\phi$. In der Tat bedeuten unsere Annahmen, da"s die Teilmenge $\{b\in\DN\mid \psi(b)=\phi(b)\}$ das Element $0\in\DN$ enth"alt und stabil ist unter $s$ und mithin aufgrund der charakterisierenden Eigenschaft der nat"urlichen Zahlen ganz $\DN$ sein mu"s. Diese Konsequenz der Definition \ref{Nhoc} hei"st das\index{vollst"andige Induktion} {\bf Prinzip der vollst"andigen Induktion}. Oft wird es verwendet mit $X$ der zweielementigen Menge $X\pdef \{\text{wahr, falsch}\}$ und $\phi$ der konstanten Abbildung \glqq wahr\grqq. \end{Bemerkungl} \begin{Bemerkungl}\label{Nhocc} Die in diesem Satz gegebene Charakterisierung und die im folgenden Beweis durchgef"uhrte Konstruktion der nat"urlichen Zahlen gehen auf einen ber"uhmten Artikel von Richard Dedekind zur"uck mit dem Titel \glqq Was sind und was sollen die Zahlen?\grqq. Eine alternative Charakterisierung besprechen wir in \eref{WOZ}{AL}. \end{Bemerkungl} \begin{Bemerkungw} Im Rahmen der Kategorientheorie k"onnte man $(\DN,s,0)$ erkl"aren als initiales Objekt der Kategorie aller Tripel $(X,f,x)$ wie oben mit den offensichtlichen Morphismen. \end{Bemerkungw} \begin{proof} 1. Nach dem Unendlichkeitsaxiom \ref{eue} finden wir eine Menge $A$ nebst einer injektiven Abbildung $s: A \hra A$ und einem Element $o \in A \backslash s (A)$. Unter allen Teilmengen $M \subset A$ mit $o \in M$ und $s (M) \subset M$ gibt es sicher eine kleinste, n"amlich den Schnitt $N$ aller derartigen Teilmengen. F"ur diese gilt dann notwendig $N\subset \{o\}\cup s(N)$, da die rechte Seite auch eine m"ogliche Teilmenge $M$ mit den geforderten Eigenschaften ist. Die andere Inklusion ist eh klar, also haben wir sogar $N= \{o\}\cup s(N)$. Damit haben wir ein m"ogliches Paar $( N,s)$ gefunden. \\[2mm]\noindent 2. Gegeben $(X,x,f)$ wie oben betrachten wir die Gesamtheit aller Teilmengen $G\subset N \times X$ mit $(o,x)\in G$ und $(n,y)\in G\RA (s(n),f(y))\in G$. Sicher gibt es eine kleinste derartige Teilmenge $G_{\op{min}}=\Gamma$, n"amlich den Schnitt aller Teilmengen $G$ mit diesen Eigenschaften. Wir zeigen nun, da"s $\Gamma$ der Graph einer Funktion ist. Dazu betrachten wir die Teilmenge $M$ aller $m\in N $ derart, da"s es genau ein $y\in X$ gibt mit $(m,y)\in \Gamma$. Sicher gilt $o\in M$, denn g"abe es $y\in X$ mit $x\neq y$ und $(o,y)\in\Gamma$, so k"onnten wir $(o,y)$ ohne Schaden aus $\Gamma$ entfernen im Widerspruch zur Minimalit"at von $\Gamma$. Ist "ahnlich $m\in M$, so zeigen wir in derselben Weise $s(m)\in M$. Also gilt $M= N $ und $\Gamma$ ist der Graph einer Funktion $f: N \ra X$ mit den gew"unschten Eigenschaften. Finden wir eine weitere Funk\-tion mit den gew"unschten Eigenschaften, so ist deren Graph auch ein m"ogliches $G$ und wir folgern erst $G\supset \Gamma$ und dann $G=\Gamma$. \\[2mm]\noindent 3. Nach Teil 2 gibt es genau eine Abbildung $\psi:N\sira N'$ mit $s\psi=\psi s'$ und $\psi:o\mapsto o'$. Nach Teil 2 gibt es auch genau eine Abbildung $\varphi:N'\sira N$ mit $s\varphi=\varphi s'$ und $\varphi:o'\mapsto o$. Nach Teil 2, diesmal der Eindeutigkeitsaussage, gilt dann $\psi \varphi=\op{id}$ und $\varphi\psi=\op{id}$. Also ist unser $\psi$ in der Tat eine Bijektion. \end{proof} \begin{Bemerkungl} In unseren nat"urlichen Zahlen $(\DN,s)$ erkl"aren wir die {\bf Eins}\index{Eins in $\DN$} als den Nachfolger der Null und setzen in Formeln\index{)0@$1$ Nachfolger der Null}\label{eIN} $$1\pdef s(0)$$ \end{Bemerkungl} \begin{Bemerkungl}[\textbf{Potenzen von Abbildungen}] Sei $(X,x,f)$ ein Tripel bestehend aus einer Menge $X$, einem Element $x\in X$ und einer Abbildung $f:X\ra X$. F"ur die Werte der Abbildung $\psi :\DN\ra X$ aus Teil 2 in \ref{EDNC} vereinbaren wir die Notation $$f^n(x)\pdef \psi (n)$$ Unser $f^n(x)$ wird also in Formeln charakterisiert durch $f^0(x)=x$ und $f^{s(n)}(x)=f(f^n(x))$. Indem wir diese Konstruktion f"ur alle $x\in X$ betrachten, erhalten wir f"ur alle $n\in\DN$ eine Abbildung\label{PotI} $$f^n:X\ra X$$ Wir nennen $f^n$ die {\bf $n$-te Potenz von $f$}. Per definitionem gilt $f^0=\op{id}$ und $f^1=f$ und $f^{s(n)}=f\circ f^n$. Vollst"andige Induktion zeigt $\op{id}^n=\op{id}$ f"ur alle $n$. \end{Bemerkungl} \begin{Lemma}[\textbf{Potenzen der Nachfolgerabbildung auf der Null}] F"ur alle nat"urlichen Zahlen $n\in\DN$ gilt $s^n(0)=n$.\label{nEl0} \end{Lemma} \begin{proof} Die Abbildung $\psi:n\mapsto s^n(0)$ ist per definitionem die eindeutig bestimmte Abbildung $\psi:\DN\ra \DN$ mit $\psi(0)=0$ und $\psi s=s\psi$. Die Identit"at hat jedoch bereits diese Eigenschaften, also gilt $\psi=\op{id}$. \end{proof} % \begin{proof} Wir argumentieren mit % vollst"andiger Induktion "uber $n$. F"ur $n=0$ sind beide Seiten $0$ und % die Behauptung stimmt. % Gilt die Formel f"ur ein $n$, so folgt %$s(n)=s(s^n(0))=s^{s(n)}(0)$ mit der ersten Gleichung durch Anwenden von $s$ % und der zweiten nach der definitorischen Gleichung $f(f^n(x))=f^{s(n)}(x)$ % f"ur Potenzen \ref{PotI}. %Damit ist unsere Behauptung bewiesen. % \end{proof} \begin{Lemma}[\textbf{Funktorialit"at von Potenzen}] Gegeben eine Abbildung $h:X\ra Y$ und Abbildungen $f: X\ra X$ sowie $g:Y\ra Y$ mit $h f= g h$ gilt\label{Via} $$h f^n= g^n h\quad\forall n\in \DN $$ \end{Lemma} \begin{proof} Wir argumentieren mit vollst"andiger Induktion "uber $n$. F"ur $n=0$ folgt die Behauptung aus $f^0=g^0=\op{id}$. F"ur den Induktionsschritt m"ussen wir aus der Identit"at $h f^n= g^n h$ die Identit"at $h f^{s(n)}= g^{s(n)} h$ folgern. Das leistet unter Verwendung der Assoziativit"at der Verkn"upfung von Abbildungen die Rechnung $$h f^{s(n)}= h f f^n=g h f^n= g g^n h =g^{s(n)}h \qedhere$$ \end{proof} %\begin{Bemerkungl}[\textbf{Funktorialit"at von Potenzen}] % Gegeben eine Abbildung $h:X\ra Y$ und Abbildungen % $f: X\ra X$ sowie $g:Y\ra Y$ mit $h f= g h$ gilt % $$h f^n= g^n h$$ f"ur alle $n\in \DN$. % In der Tat reicht es, % f"ur alle $x\in X$ die Identit"at $h f^n(x)= g^n h(x)$ % zeigen. Beide Seiten sind aber als Funktionen von $n$ Abbildungen $\psi: \DN\ra Y$ mit demselben % Wert $\psi(0)=h(x)$ f"ur $n=0$ und derselben % charakterisierenden Eigenschaft\label{Via} $$\psi s=g\psi$$ In der Tat, setzen wir $\psi_1(n)\pdef hf^n(x)$ % und $\psi_2(n)\pdef g^nh(x)$, so haben wir $\psi_1s(n)=h f^{s(n)}(x)=h f f^n(x)=ghf^n(x)=g\psi_1(n)$ und $\psi_2s(n)=g^{s(n)}h(x)=gg^{n}h(x)=g\psi_2(n)$ % nach der charakterisierenden Eigenschaft % der Potenzen von Abbildungen. %\end{Bemerkungl} \begin{Bemerkungl}[\textbf{Potenzregeln f"ur kommutierende Selbstabbildungen}] Gegeben Selbstabbildungen $f, h:X\ra X$ einer Menge mit $hf=fh$ folgern wir aus der Funktorialit"at von Potenzen \ref{Via} unmittelbar $h f^a= f^a h$ f"ur alle $a\in\DN$. Das schreiben wir um zu $(f^a)h=h(f^a)$ und durch nochmaliges Anwenden unserer Erkenntnis\label{pkS} erhalten wir f"ur alle $a,b\in\DN$ die Identit"at $$f^a h^b= h^b f^a$$ \end{Bemerkungl} \begin{Definition} F"ur die Menge der nat"urlichen Zahlen mit Nachfolgerabbildung $(\DN,s)$ aus \ref{Nhoc} erkl"aren wir die {\bf Addition}\index{Addition!nat"urlicher Zahlen} $\DN\times\DN\ra\DN$, $(a,b)\mapsto a+b$ durch die Vorschrift $$a+b\pdef s^a(b)$$ \end{Definition} \begin{Bemerkungl}\label{1ps} Wir finden $0+b=s^{0}(b)=\op{id}(b)=b$ und $1+b=s^{1}(b)=s(b)$ f"ur alle $b\in \DN$. Andererseits finden wir $b+0=s^b(0)=b$ nach Lemma \ref{nEl0} zu dem Wert von Potenzen der Nachfolgerabbildung auf der Null. \end{Bemerkungl} \begin{Lemma} Die Addition von nat"urlichen Zahlen ist eine kommutative Ver\-kn"up\-fung mit der Null als neutralem Element.\label{nEl} \end{Lemma} \begin{proof} Aus der Potenzregel \ref{pkS} folgt $s^as^b =s^bs^a$ f"ur alle $a,b\in\DN$. Werten wir beide Seiten auf $0$ aus, so erhalten wir mit Lemma \ref{nEl0} zum Wert von Potenzen der Nachfolgerabbildung auf der Null die Kommtativit"at $s^a(b)=s^b(a)$. Die Identit"aten $0+b=b=b+0$ kennen wir bereits aus \ref{1ps}. \end{proof} \begin{Lemma}[\textbf{Produkt von Potenzen und Addition}] Gegeben eine Menge $X$ und eine Abbildung $f:X\ra X$ sowie $a,b\in\DN$ gilt $f^{a+b}=f^a f^b$.\label{ppA} \end{Lemma} \begin{proof} Wir zeigen das durch vollst"andige Induktion "uber $a$. Im Fall $a=0$ ist es klar. F"ur den Induktionsschritt wenden wir $f$ an und finden von der Mitte ausgehend $$f^{s(a)+b}= f^{s(a+b)}=f f^{a+b}=f (f^a f^b)=(f f^a)f^b=f^{s(a)}f^b$$ Hier nutzen wir nach rechts die Assoziativit"at der Verkn"upfung von Abbildungen und nach links die Identit"at $s(a)+b=s^{s(a)}(b)=s (s^a(b))=s(a+b)$. \end{proof} \begin{Bemerkungl}[\textbf{Assoziativit"at der Addition nat"urlicher Zahlen}] Die Addition nat"urlicher Zahlen ist assoziativ, denn gegeben $a,b,c\in\DN$ finden wir\label{nAs} durch Anwenden unserer Identit"at $f^{a+b}=f^a f^b$ aus \ref{ppA} unter Verwendung der Assoziativit"at der Verkn"upfung von Abbildungen %$(a+b)+c=s^{a+b}(c)=s^{a}(s^{b}(c))=a+(b+c)$. $$ s^{(a+b)+c}= (s^a s^b) s^c=s^a s^b s^c=s^a (s^b s^c)=s^{a+(b+c)}$$ Auswerten bei $0$ liefert dann die Behauptung. \end{Bemerkungl} \begin{Satz}[\textbf{Eigenschaften der Addition nat"urlicher Zahlen}] Die Menge der nat"urlichen Zahlen\label{KurZ} wird mit der Verkn"upfung $+$ ein kommutatives Monoid, in dem die \emph{\bf K"urzungsregel} $(a+b=c+b)\RA(a=c)$ gilt sowie die Regel $(a+b=0)\RA (a=b=0)$. \end{Satz} \begin{proof} Kommutativit"at, neutrales Element und Assoziativit"at haben wir bereits in \ref{nEl} und \ref{nAs} erledigt. Was unsere K"urzungsregel angeht, enth"alt f"ur $a\neq c$ die Menge aller $b$ mit $a+b\neq c+b$ sicher $b=0$ und ist stabil unter $s$, enth"alt also alle $b\in\DN$. Aus $a+b=0$ folgt zu guter Letzt $a=0$, weil ja sonst die Null gar nicht im Bild der Abbildung $(a+)=s^a:\DN\ra\DN$ liegt, und $0+b=0$ impliziert $b=0$, weil $0$ neutral ist f"ur die Addition. \end{proof} \begin{Satz}[\textbf{Anordnung auf den nat"urlichen Zahlen}] Sei $(\DN, s)$ die Menge der nat"urlichen Zahlen mit Nachfolgerabbildung aus \ref{Nhoc}\label{ONZ} und Addition aus \ref{KurZ}. Die Relation $\leq$ auf $\DN$ gegeben durch die Vorschrift $$(a\leq b)\IFF (\exists c\in\DN\text{ mit }a+c=b)$$ ist eine Anordnung auf $\DN$. F"ur diese Anordnung ist $0\in\DN$ das kleinste Element und jede nichtleere Teilmenge von $\DN$ besitzt ein kleinstes Element. \end{Satz} \begin{proof} Bis auf die allerletzte Aussage folgt das leicht aus den in \ref{KurZ} gezeigten Eigenschaften der Addition. Ist nun $A\subset \DN$ eine Teilmenge ohne kleinstes Element, so ist $\{n\in \DN\mid n\leq a\;\forall a\in A\}$ stabil unter $s$ und enth"alt die Null, ist also ganz $\DN$ und es folgt $A=\emptyset$. \end{proof} \begin{Satz}[\textbf{Z"ahlen endlicher Mengen}] Eine Menge $X$ ist genau dann endlich, wenn es ein $n\in \DN$ und eine Bijektion $\DN_{ 0\RA a_r\neq 0$, was wieder dem Leser zur "Ubung "uberlassen sei. \end{Bemerkungl} \begin{Bemerkungl}[\textbf{Zahldarstellungen}] Gegeben eine beliebige nat"urliche Zahl $b>1$ hat jede nat"urliche Zahl $n$ genau eine Darstellung der Form $$n=a_rb^r+\ldots +a_1b^1+a_0b^0$$ mit $a_0, a_1,\ldots, a_r\in \{0,1,\ldots, b-1\}$ und $r> 0\RA a_r\neq 0$. Wenn wir Symbole alias Ziffern f"ur die Elemente dieser Menge vereinbaren, so k"onnen wir die Sequenz von Ziffern $a_r\ldots a_0$ als Darstellung der Zahl $n$ interpretieren. Wir sagen dann auch, sie {\bf stelle $n$ im $b$-adischen System dar} \index{Zahldarstellungen} und schreiben $$a_r\ldots a_0=[a_r,\ldots, a_0]_b=n$$ Wenn aber ganz links nicht eine Darstellung zur Basis zehn gemeint sein sollte, mu"s man das deutlich dazusagen. Das zehnadische Sytem hei"st das {\bf Dezimalsystem}\index{Dezimalsystem} und man spricht dann auch von der {\bf Dezimaldarstellung}\index{Dezimaldarstellung} einer nat"urlichen Zahl und wir haben etwa $$[2,5,5]_{10}=255$$ Bei $b\leq 10$ w"ahlt man als Ziffern meist die ersten $b$ "ublichen Ziffern des Dezimalsystems. Das $2$-adische Sytem hei"st das {\bf Dualsystem}\index{Dualsystem} und man spricht dann auch von der {\bf Bin"ardarstellung}\index{Bin"ardarstellung} einer nat"urlichen Zahl. So w"are $$1010=[1,0,1,0]_2=2^3+2^1=10$$ die Darstellung der Zahl Zehn im Dualsystem, wo ganz links dazugesagt werden mu"s, da"s $1010$ als Bin"ardarstellung gemeint ist. Gebr"auchlich sind auch Darstellungen im $16$-adischen Sytem alias {\bf Hexadezimalsystem}\index{Hexadezimalsystem} mit den "ublicherweise verwendten Ziffern $0,1,2,3,4,5,6,7,8,9,\mathrm A, \mathrm B,\mathrm C,\mathrm D,\mathrm E,\mathrm F$. So h"atten wir zum Beispiel $$\mathrm F\mathrm F=[\mathrm F,\mathrm F]_{16}=15\cdot 16+15= 255$$ und m"ussen ganz links dazusagen, da"s $\mathrm F\mathrm F$ als Hexadesimaldarstellung gemeint ist. Wenn aber in so einer Ziffernfolge die ersten sechs Buchstaben des Alphabets als Gro"sbuchstaben auftauchen, liegt der Verdacht einer Zahl in Hexadesimaldarstellung nahe. \end{Bemerkungl} \begin{Bemerkungl} Hier zeige ich noch zwei Aussagen f"ur endliche Mengen, die wir bereits als offensichtlich deklariert und verwendet haben, aber vor der Formalisierung des Begriffs einer endlichen Menge \ref{eue}. \end{Bemerkungl} \begin{Lemma}[\textbf{Eigenschaften endlicher Mengen}] Jede Teilmenge einer endlichen Menge ist endlich. Die Vereinigung einer endlichen Menge mit einer einelementigen Menge ist endlich.\label{EeM} \end{Lemma} \begin{Bemerkungl} Diese Erkenntnisse haben wir bereits mehrfach als intuitiv klar verwendet, aber das war noch vor dem Verlust der Unschuld durch die Formalisierung des Begriffs einer endlichen Menge. Da"s man umgekehrt auch jede endliche Menge als endliche Vereinigung einelementiger Mengen schreiben kann, wird im wesentlichen in \ref{ZeMM} bewiesen. \end{Bemerkungl} \begin{proof} Es ist klar, da"s jede Menge mit einer unendlichen Teilmenge auch selbst unendlich sein mu"s. Das zeigt die erste Aussage. Es ist klar, da"s eine unendliche Menge unendlich bleibt, wenn wir ihr ein Element wegnehmen: Wir k"onnen n"amlich unsere injektive aber nicht bijektive Abbildung leicht so ab"andern, da"s ein vorgegebenes Element auf sich selber abgebildet wird. Das zeigt die zweite Aussage. \end{proof} \begin{Lemma}[\textbf{Maximale Elemente endlicher teilgeordneter Mengen}] Jede nichtleere endliche teilgeordnete Menge $(E,\leq)$ besitzt mindestens ein maximales Element.\label{NEEN} \end{Lemma} \begin{Bemerkungl} Diese Erkenntnis haben wir bereits mehrfach als intuitiv klar verwendet, etwa im Beweis \eref{Kop}{AN1} der Tatsache, da"s zwischen je zwei verschiedenen reellen Zahlen immer noch eine rationale Zahl liegt, oder beim Beweis des Ba\-sis\-exis\-tenz\-sat\-zes f"ur endlich erzeugte Vektorr"aume \ref{EEBa}. Das aber war noch vor der Formalisierung des Begriffs einer endlichen Menge. \end{Bemerkungl} \begin{proof} Wir argumentieren durch Widerspruch. Andernfalls k"onnten wir eine Abbildung $f:E\ra E$ finden, die jedem Element ein echt gr"o"seres Element zuordnet. Da wir $E\neq \emptyset$ angenommen hatten, gibt es andererseits $a\in E$ und wir erhielten eine injektive aber nicht surjektive Abbildung von $\{x\in E\mid x\geq a\}$ zu sich selbst im Widerspruch zu Lemma \ref{EeM}, nach dem jede Teilmenge einer endlichen Menge endlich sein mu"s. \end{proof} \subsubsection*{"Ubungen} \begin{Ubung} Man zeige, da"s gilt $s(a)\neq a$ f"ur alle $a\in \DN$. \end{Ubung} \begin{Ubung} Man f"uhre den Beweis f"ur das Teilen mit Rest \ref{TMR} aus. \end{Ubung} \begin{Ubung} Man zeige, da"s die Vereinigung einer endlichen Menge mit einer einelementigen Menge wieder endlich ist. Man zeige durch vollst"andige Induktion "uber $a$,\label{Uze} da"s f"ur alle $a\in\DN$ die Menge $\DN_{ 0}$ und diese ist nach \ref{disZ} distributiv "uber der Addition. Aus \eref{TLl}{AN1} folgt dann schlie"slich, da"s sich unsere Multiplikation auf $\DZ_{> 0}$ aus \ref{MnaZ} auf eine und nur eine Weise zu einer kommutativen und "uber $+$ distributiven Multiplikation auf $\DZ$ fortsetzen l"a"st. Von dieser Multiplikation ist a posteriori dann auch klar, da"s sie unsere Multiplikation auf $\DN\supset \DZ_{>0}$ fortsetzt. Wenn wir in \ref{Ring} lernen, was ein \glqq Ring\grqq\ ist, werden sich unsere ganzen Zahlen mit dieser Addition und Multiplikation als eines der ersten Beispiele f"ur einen Ring erweisen. \end{Bemerkungl} \begin{Bemerkunge} Gegeben Relationen $R\subset X\times X$ und $S\subset Y\times Y$ ist auch das Bild von $(R\times S)\subset (X\times X)\times (Y\times Y)$ unter der durch Vertauschen der mittleren Eintr"age gegebenen Identifikation $(X\times X)\times (Y\times Y)\sira (X\times Y)\times (X\times Y)$ eine Relation. Wir notieren diese Relation auf dem Produkt kurz $R\times S$. Sind $R$ und $S$ "Aquivalenrelationen, so auch $R\times S$. \end{Bemerkunge} \subsubsection*{"Ubungen} \begin{Ubunge} Ist $G$ eine Gruppe und $H\subset G \times G$ eine Untergruppe, die die Diagonale umfa"st, so ist $H$ eine "Aquivalenzrelation. \end{Ubunge} \subsection{Untergruppen der Gruppe der ganzen Zahlen} \label{UgrZ} \begin{Definition} Eine Teilmenge einer Gruppe hei"st eine {\bf Untergruppe},\index{Untergruppe} wenn sie abgeschlossen ist unter der Verkn"upfung und der Inversenbildung und zus"atzlich das neutrale Element enth"alt. Ist $G$ eine multiplikativ geschriebene Gruppe, so ist eine Teilmenge $U \subset G$ also eine Untergruppe, wenn in Formeln gilt: $a,b \in U \Rightarrow a b \in U$, $a \in U \Rightarrow a^{-1} \in U$ sowie $1\in U$. \end{Definition} \begin{Bemerkunge} Nach der reinen Lehre sollte eine Teilmenge einer Gruppe eine \glqq Untergruppe\grqq\ hei"sen, wenn sie so mit der Struktur einer Gruppe versehen werden kann, da"s die Einbettung ein Gruppenhomomorphismus wird. Da diese Definition jedoch f"ur Anwendungen erst aufgeschl"usselt werden mu"s, haben wir gleich die aufgeschl"usselte Fassung als Definition genommen. Den Nachweis der "Aquivalenz zur Definition nach der reinen Lehre "uberlassen wir dem Leser zur "Ubung. \end{Bemerkunge} \begin{Beispiele} In jeder Gruppe ist die einelementige Teilmenge, die nur aus dem neutralen Element besteht, eine Untergruppe. Wir nennen sie die \defnoind{triviale Untergruppe}.\index{Untergruppe!triviale} Ebenso ist nat"urlich die ganze Gruppe stets eine Untergruppe von sich selber. Gegeben ein Vektorraum $V$ ist die Menge aller Automorphismen eine Untergruppe $\op{Aut}(V)\subset \op{Ens}^\times(V)$ der Gruppe aller Permutationen der zugrundeliegenden Menge. \end{Beispiele} \begin{Satz}[\textbf{Untergruppen der additiven Gruppe $\DZ$ der ganzen Zahlen}] Jede Untergruppe $H \subset \DZ$ ist von der Form $H=m \DZ$ f"ur genau ein $m \in \DN$.\label{UGZ} Die Abbildungsvorschrift $m\mapsto m \DZ$ liefert mithin eine Bijektion $$\begin{array}{ccc} \DN & \sira & \{H\subset \DZ\mid H \text{ ist Untergruppe von }\DZ\} \end{array}$$ Die Umkehrabbildung ordnet jeder Untergruppe $H\subset \DZ$ ihr kleinstes positives Element zu, wenn $H$ "uberhaupt positive Elemente hat, und sonst die Null. \end{Satz} \begin{Bemerkungl} Eine Teilmenge $H\subset \DZ$ ist per definitionem eine Untergruppe genau dann, wenn sie die Null enth"alt, mit jedem Element auch sein Negatives und mit je zwei Elementen auch ihre Summe. \end{Bemerkungl} \begin{proof}[Beweis] Im Fall $H=\{0\}$ ist $m=0$ die einzige nat"urliche Zahl mit $H= m\DZ$. Gilt $H \neq \{0\}$, so enth"alt $H$ echt positive Elemente. Sei dann $m \in H$ das kleinste echt positive Element von $H$. Wir behaupten $H = m\DZ$. Die Inklusion $H \supset m \DZ$ ist hier offensichtlich. Aber g"abe es $n \in H \setminus m\DZ$, so k"onnten wir $n$ \hyperref[TMR]{mit Rest teilen} durch $m$ und also schreiben $n = ms + r$ f"ur geeignete $s,r\in\DZ$ mit $0< r < m$. Es folgte $r = n-ms\in H$ im Widerspruch zur Minimalit"at von $m$. Das zeigt $H=m\DZ$. Die restlichen Behauptungen sind nun offensichtlich. \end{proof} \begin{Bemerkungl}\label{EUG} Der Schnitt "uber eine beliebige Familie von Untergruppen einer gegebenen Gruppe ist selbst wieder eine Untergruppe. F"ur eine Teilmenge $T$ einer Gruppe $G$ erkl"aren wir die {\bf von $T$ erzeugte Untergruppe}\index{Untergruppe!erzeugt von Teilmenge} $$\langle T\rangle \subset G$$ als die\index{erzeugt!Untergruppe} kleinste Untergruppe von $G$, die $T$ umfa"st. Nat"urlich gibt es so eine kleinste Untergruppe, n"amlich den Schnitt "uber alle Untergruppen von $G$, die $T$ umfassen. F"ur $T \neq \emptyset$ k"onnen wir $\langle T\rangle$ konkret beschreiben als die Menge aller endlichen Produkte von Elementen aus $T$ und deren Inversen. F"ur $T =\emptyset$ besteht $\langle T\rangle$ dahingegen nur aus dem neutralen Element. Ist $T$ durch einen Ausdruck in Mengenklammern gegeben, so lassen wir diese meist weg und schreiben also zum Beispiel k"urzer $\langle a_1,\ldots,a_n\rangle$ statt $\langle \{ a_1,\ldots,a_n\}\rangle$. Ob der Ausdruck $\langle T\rangle$ in einem speziellen Fall die von einer Menge $T$ erzeugte Untergruppe oder vielmehr die von der einelementigen Menge mit einzigem Element $T$ erzeugte Untergruppe meint, mu"s der Leser meist aus dem Kontext erschlie"sen. Schreiben wir jedoch $\langle_! T\rangle$, so ist stets zu verstehen, da"s $T$ eine Menge von Erzeugern und nicht einen einzelnen Erzeuger meint. \end{Bemerkungl} \begin{Bemerkungl} Ist $V$ ein $k$-Vektorraum und $T\subset V$ eine Teilmenge, so mu"s der Leser aus dem Kontext erschlie"sen, ob mit $\langle T\rangle$ die von $T$ erzeugte Untergruppe oder der von $T$ erzeugte Untervektorraum gemeint ist. Zur Unterscheidung schreiben wir manchmal $\langle T\rangle_\DZ$ f"ur die von $T$ erzeugte Untergruppe und $\langle T\rangle_k$ f"ur den von $T$ erzeugten Untervektorraum. \end{Bemerkungl} \subsubsection*{"Ubungen} \begin{Ubunge}\label{ETUG} Eine endliche nichtleere Teilmenge einer Gruppe, die mit je zwei Elementen auch die Verkn"upfung der beiden enth"alt, ist notwendig bereits eine Untergruppe. \end{Ubunge} \begin{Ubung}\label{SM} Sind $H,K \subset G$ zwei Untergruppen einer Gruppe mit $H\cap K =1$, so induziert die Verkn"upfung eine Injektion $H \times K \hookrightarrow G$. \end{Ubung} \begin{Ubung} Wieviele Untergruppen hat die additive Gruppe eines zweidimensionalen Vektorraums "uber dem K"orper mit zwei Elementen? Wieviele Untergruppen hat die additive Gruppe eines $n$-dimensionalen Vektorraums "uber dem K"orper mit zwei Elementen? \end{Ubung} \begin{Ubunge}\label{StaKe} Sei $G$ eine Gruppe und $\varphi:G\ra G$ ein Gruppenhomomorphismus. Man zeige: Gilt f"ur ein $n\in\DN$ die Geichheit $\op{ker}\varphi^n=\op{ker}\varphi^{n+1}$, so folgt $\op{ker}\varphi^n=\op{ker}\varphi^{n+1}=\op{ker}\varphi^{n+2}=\ldots$ %Hinweis: Man mag \eref{BiuB}{GR} erinnern. \end{Ubunge} \begin{Ubung}\label{KKGr} F"ur jeden Gruppenhomomorphismus $\varphi:G\ra H$ gilt die Formel $|G|=|\op{im}\varphi|\cdot |\op{ker}\varphi|$. Man bemerke, da"s diese Formel im Fall linearer Abbildungen von Vektorr"aumen "uber endlichen K"orpern "aquivalent ist zur Dimensionsformel. \end{Ubung} \subsection{Primfaktorzerlegung}\label{pfz} \begin{Definition} Eine \defind{Primzahl} ist eine nat"urliche Zahl $\geq 2$, die sich nicht als das Produkt von zwei echt kleineren nat"urlichen Zahlen erhalten l"a"st. \end{Definition} \begin{Beispiel} Die Primzahlen unterhalb von $50$ sind $2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$, $47$. \end{Beispiel} \begin{Bemerkungl} Eine M"oglichkeit, alle Primzahlen zu finden, ist das sogenannte \defind{Sieb des Eratosthenes}: Man beginnt mit der kleinsten Primzahl, der Zwei. Streicht man alle Vielfachen der Zwei, als da hei"st, alle geraden Zahlen, so ist die erste Zahl unter den "Ubrigen die n"achste Primzahl, die Drei. Streicht man nun auch noch alle Vielfachen der Drei, so ist die erste Zahl unter den "Ubrigen die n"achste Primzahl, die F"unf, und so weiter. \glqq Der Erste\grqq\ hei"st auf lateinisch \glqq Primus\grqq\ und auf griechisch "ahnlich und es k"onnte sein, da"s die Bezeichnung \glqq Primzahl\grqq\ daher r"uhrt. \end{Bemerkungl} \begin{Satz}[\textbf{Existenz einer Primfaktorzerlegung}]\label{EPF} Jede nat"urliche Zahl\index{Primfaktorzerlegung!Existenz} $n \geq 2$ kann als ein Produkt von Primzahlen $n = p_{1} p_{2} \ldots p_{r}$ mit $r\geq 1$ dargestellt werden. \end{Satz} \begin{Bemerkungl} Jede nat"urliche Zahl\index{Primfaktorzerlegung!Existenz} $n \geq 1$ kann auch als ein Produkt von Primzahlen $n = p_{1} p_{2} \ldots p_{r}$ mit $r\geq 0$ dargestellt werden, wenn wir unsere Konvention \eref{VLSP}{GR} erinnern, nach der die Eins durch das \glqq leere Produkt\grqq\ mit $r=0$ dargestellt wird. \end{Bemerkungl} \begin{proof}[Beweis] Das ist klar mit vollst"andiger Induktion: Ist eine Zahl nicht bereits selbst prim, so kann sie als Produkt von zwei echt kleineren Faktoren geschrieben werden, von denen nach Induktionsannahme bereits bekannt ist, da"s sie Primfaktorzerlegungen besitzen. \end{proof} \begin{Satz}\label{UEPi} Es gibt unendlich viele Primzahlen. \end{Satz} \begin{proof} Durch Widerspruch. G"abe es nur endlich viele Primzahlen, so k"onnten wir deren Produkt betrachten und dazu Eins hinzuz"ahlen. Die so neu entstehende Zahl m"u"ste dann wie jede nat"urliche Zahl $\geq 2$ nach \ref{EPF} eine Primfaktorzerlegung mit mindestens einem Primfaktor besitzen, aber keine unserer endlich vielen Primzahlen k"ame als Primfaktor in Frage. \end{proof} \begin{Bemerkunge} Noch offen (2019) ist die Frage, ob es auch unendlich viele \defind{Primzahlzwillinge} gibt, als da hei"st, Paare von Primzahlen mit der Differenz Zwei, wie zum Beispiel $5,7$ oder $11,13$ oder $17,19$. Ebenso offen ist die Frage, ob jede gerade Zahl $n>2$ die Summe von zwei Primzahlen ist. Die Vermutung, da"s das richtig sein sollte, ist bekannt als \defind{Goldbach-Vermutung}. Bekannt ist, da"s es unendlich viele Paare von Primzahlen mit einem Abstand $\leq 246$ gibt. \end{Bemerkunge} \begin{Satz}[\textbf{Eindeutigkeit der Primfaktorzerlegung}] Die Darstellung einer nat"urlichen Zahl $n \geq 1$ als ein Produkt von Primzahlen $n = p_{1} p_{2} \ldots p_{r}$ ist eindeutig bis auf die Reihenfolge der Faktoren. Nehmen wir zus"atzlich\label{EPFE} $ p_{1}\leq p_{2}\leq \ldots \leq p_{r}$ an, so ist unsere Darstellung mithin eindeutig. \end{Satz} \begin{Bemerkungl} In anderen Worten liefert das Aufmultiplizieren eine Bijektion $$\{\text{Endliche Multimengen von Primzahlen}\} \sira\{\text{Positive nat"urliche Zahlen} \} $$ \end{Bemerkungl} \begin{Bemerkungl} Dieser Satz ist einer von vielen Gr"unden, aus denen man bei der Definition des Begriffs einer Primzahl die Eins ausschlie"st. Die Eins auf der rechten Seite erh"alt man aus der leeren Multimenge auf der linken Seite. \end{Bemerkungl} \begin{proof} Der Beweis dieses Satzes braucht einige Vorbereitungen. Ich bitte Sie, gut aufzupassen, da"s wir bei diesen Vorbereitungen den Satz "uber die Eindeutigkeit der Primfaktorzerlegung nirgends verwenden, bis er dann im Anschlu"s an Lemma \ref{EPf} endlich bewiesen werden kann. \end{proof} \begin{Definition} Seien $a,b \in \DZ$ ganze Zahlen. Wir sagen {\bf $a$ teilt $b$}\index{teilt} oder {\bf $a$ ist ein Teiler von $b$}\index{Teiler} oder {\bf $b$ ist ein Vielfaches von $a$}\index{Vielfaches} und schreiben $a|b$, wenn es $c \in \DZ$ gibt mit $ac=b$. \end{Definition} \begin{Definition} Sind ganze Zahlen $a,b\in\DZ$ nicht beide Null, so gibt es eine gr"o"ste ganze Zahl $c\in\DZ$, die sie beide teilt. Diese Zahl hei"st der {\bf gr"o"ste gemeinsame Teiler}\index{gr"o"ster gemeinsamer Teiler} von $a$ und $b$ und man notiert sie $\op{ggT}(a,b)$.\index{ggT@$\op{ggT}$ gr"o"ster gemeinsamer Teiler} Ganze Zahlen $a$ und $b$ hei"sen {\bf teilerfremd},\index{teilerfremd!ganze Zahlen} wenn sie au"ser $\pm 1$ keine gemeinsamen Teiler besitzen. \end{Definition} \begin{Beispiel} Insbesondere sind also $a=0$ und $b=0$ nicht teilerfremd und $0$ und $5$ sind auch nicht teilerfremd. \end{Beispiel} \begin{Satz}[\textbf{"uber den gr"o"sten gemeinsamen Teiler}] Gegeben zwei ganze Zahlen $a,b\in \DZ$, die nicht beide Null sind,\label{ggT} kann ihr gr"o"ster gemeinsamer Teiler $\op{ggT}(a,b)$ als eine ganzzahlige Linearkombination unserer beiden Zahlen dargestellt werden. Es gibt also in Formeln $r, s \in \DZ$ mit $$\op{ggT}(a,b) = r a+sb$$ Teilt weiter $d \in \DZ$ sowohl $a$ als auch $b$, so teilt $d$ auch den gr"o"sten gemeinsamen Teiler von $a$ und $b$. \end{Satz} \begin{Bemerkungl} Der letzte Teil dieses Satzes ist einigerma"sen offensichtlich, wenn man die Eindeutigkeit der Primfaktorzerlegung als bekannt voraussetzt. Da wir besagte Eindeutigkeit der Primfaktorzerlegung jedoch erst aus besagtem zweiten Teil ableiten werden, ist es wichtig, auch f"ur den zweiten Teil dieses Satzes einen eigenst"andigen Beweis zu geben. \end{Bemerkungl} \begin{proof}[Beweis] Man betrachte die Teilmenge $a \DZ + b\DZ= \{ ar+bs\mid r, s \in \DZ\}\subset\DZ$. Sie ist offensichtlich eine von Null verschiedene Untergruppe von $\DZ$. Also ist sie nach unserer Klassifikation \ref{UGZ} der Untergruppen von $\DZ$ von der Form $a \DZ + b\DZ = m\DZ$ f"ur genau ein $m > 0$ und es gilt: \begin{enumerate} \item $m$ teilt $a$ und $b$. In der Tat haben wir ja $a,b\in m\DZ$; \item $m = r a +sb$ f"ur geeignete $r,s \in \DZ$. In der Tat haben wir ja $m\in a \DZ + b\DZ$; \item $(d$ teilt $a$ und $b) \Rightarrow (d$ teilt $m)$. \end{enumerate} Daraus folgt sofort, da"s $m$ der gr"o"ste gemeinsame Teiler von $a$ und $b$ ist, und damit folgt dann der Satz. \end{proof} \begin{Bemerkungl}[\textbf{Notation f"ur gr"o"ste gemeinsame Teiler}] Gegeben $a_1,\ldots, a_n\in\DZ$ k"on\-nen wir mit der Notation \ref{EUG} k"urzer schreiben $$a_1\DZ+\ldots+a_n\DZ=\langle a_1,\ldots,a_n\rangle$$ "Ublich ist hier auch die Notation $(a_1,\ldots,a_n)$, die jedoch oft auch $n$-Tupel von ganzen Zahlen bezeichnet, also Elemente von $\Bbb{Z}^{n}$, und in der Analysis im Fall $n=2$ meist ein offenes Intervall. Es gilt dann aus dem Kontext zu erschlie"sen, was jeweils gemeint ist. Sind $a$ und $b$ nicht beide Null und ist $c$ ihr gr"o"ster gemeinsamer Teiler, so haben wir nach dem Vorhergehenden $\langle a,b\rangle=\langle c\rangle$. Wir benutzen von nun an oft diese Notation. "Uber die Tintenersparnis hinaus hat sie den Vorteil, auch im Fall $a=b=0$ sinnvoll zu bleiben. \end{Bemerkungl} \begin{Lemma}[\textbf{von Euklid}] Teilt eine Primzahl ein Produkt von zwei ganzen Zahlen, so teilt sie einen der\label{EPf} Faktoren.\index{Euklid!Lemma von} \end{Lemma} \begin{Bemerkungl}[\textbf{Diskussion der Terminologie}] Dies Lemma findet sich in Euklid's Elementen in Buch VII als Proposition 30. \end{Bemerkungl} \begin{Bemerkungl} Wenn wir die Eindeutigkeit der Primfaktorzerlegung als bekannt voraussetzen, so ist dies Lemma offensichtlich. Das hilft aber hier nicht weiter, da wir bei dieser Argumentation voraussetzen, was wir gerade erst beweisen wollen. Sicher ist Ihnen die Eindeutigkeit der Primfaktorzerlegung aus der Schule und ihrer Rechenerfahrung wohlvertraut. Um die Schwierigkeit zu sehen, sollten Sie vielleicht selbst einmal versuchen, einen Beweis f"ur diese allzu vertraute Erkenntnis anzugeben. Im "ubrigen werden wir in \eref{GBGG}{AL} sehen, da"s etwa im Ring $\DZ[\sqrt{-5}]$ das Analogon zur Eindeutigkeit der Primfaktorzerlegung nicht mehr richtig ist. \end{Bemerkungl} \begin{proof}[Beweis] Sei $p$ unsere Primzahl und seien $a,b\in\DZ$ gegeben mit $p|ab$. Teilt $p$ nicht $a$, so folgt f"ur den gr"o"sten gemeinsamen Teiler $\op{ggT}(p,a)=1$, denn die Primzahl $p$ hat nur die Teiler $\pm 1$ und $\pm p$. Der gr"o"ste gemeinsame Teiler von $p$ und $a$ kann aber nicht $p$ sein und mu"s folglich $1$ sein. Nach Satz \ref{ggT} "uber den gr"o"sten gemeinsamen Teiler gibt es also $r, s \in \DZ$ mit $1=rp +sa$. Es folgt $b = rpb + sab$ und damit $p|b$, denn $p$ teilt $rpb$ und teilt nach Annahme auch $sab$. \end{proof} \begin{proof}[Beweis der Eindeutigkeit der Primfaktorzerlegung \ref{EPFE}] Zun"achst bemerken wir, da"s aus dem Lemma von Euklid \ref{EPf} per Induktion dieselbe Aussage auch f"ur Produkte beliebiger L"ange folgt: Teilt eine Primzahl ein Produkt, so teilt sie einen der Faktoren. Seien nun $n=p_1p_2\ldots p_r=q_1q_2\ldots q_s$ zwei Primfaktorzerlegungen derselben Zahl $n\geq 1$. Da $p_1$ unser $n$ teilt, mu"s es damit eines der $q_i$ teilen. Da auch dies $q_i$ prim ist, folgt $p_1=q_i$. Wir k"urzen den gemeinsamen Primfaktor und sind fertig per Induktion. \end{proof} % \begin{Bemerkungl} % Aus der Existenz der Primfaktorzerlegung folgt insbesondere, % da"s es unendlich viele Primzahlen geben mu"s: F"ur jede endliche % Menge von % Primzahlen k"onnen wir n"amlich ihr Produkt % bilden. Z"ahlen wir zu diesem Produkt noch 1 hinzu, so kann % keine Primzahl aus unserer endlichen % Menge ein Primfaktor der neu entstandenen Zahl sein. % Also ist jeder Primfaktor der neu entstandenen Zahl eine Primzahl au"serhalb % unserer vorgegebenen endlichen Menge von Primzahlen. % \end{Bemerkungl} \begin{Bemerkungl}\label{EukA} Ich erkl"are am Beispiel $a=160$, $b= 625$ den sogenannten {\bf euklidischen Algorithmus}, mit dem man den gr"o"sten gemeinsamen Teiler zweier positiver nat"urlicher Zahlen $a,b$ bestimmen kann nebst einer Darstellung $\op{ggT}(a,b)=ra+rb$. In unseren Gleichungen wird jeweils geteilt mit Rest. $$\begin{array}{rrrrrrrrrrrrrr} 625 = 3 \cdot&\! 160 &+& 145 \\ %\swarrow&&\swarrow\\ 160 = 1 \cdot&\! 145 &+& 15 \\ %\swarrow&&\swarrow\\ 145 = 9 \cdot &\! 15 &+& 10 \\ %\swarrow&&\swarrow\\ 15 = 1 \cdot&\! 10 &+& 5 \\ %\swarrow&&\swarrow\\ 10 = 2 \cdot &\! 5 &+&0 & \end{array}$$ Daraus folgt %$\langle 625,160\rangle =\langle 160,145\rangle =\langle 145,15\rangle %=\langle 15,10\rangle =\langle 10,5\rangle =\langle 5,0\rangle =\langle %5\rangle $. $\op{ggT} (625,160) =\op{ggT} (160,145) =\op{ggT} (145,15) =\op{ggT} (15,10) =\op{ggT} (10,5) =\op{ggT} (5,0) = 5 $. Die vorletzte Zeile liefert nun umgekehrt eine Darstellung $5= -10 + 15$ unseres gr"o"sten gemeinsamen Teilers $5=\op{ggT}(10,15)$ als ganzzahlige Linearkombination von $10$ und $15$. Die vorvorletzte Zeile liefert durch Umstellen $10=-9\cdot 15 + 145$ und durch Einsetzen in die vorherige Gleichung eine Darstellung $$5=-(-9\cdot 15 + 145)+ 15=10\cdot 15 - 145$$ unseres gr"o"sten gemeinsamen Teilers $5=\op{ggT}(15,145)$ als ganzzahlige Linearkombination von $15$ und $145$. Indem wir so induktiv hochsteigen, erhalten wir schlie"slich f"ur den gr"o"sten gemeinsamen Teiler die Darstellung $5=-11 \cdot 625 + 43 \cdot 160 $. \end{Bemerkungl} \begin{Bemerkunge} Gegeben eine positive nat"urliche Zahl $n$ bezeichne $\op{rad}(n)$ das Produkt ohne Vielfachheiten aller Primzahlen, die $n$ teilen. Die {\bf ABC-Ver\-mu\-tung}\index{ABC-Vermutung} besagt, da"s es f"ur jedes $\varepsilon >0$ nur endlich viele Tripel von paarweise teilerfremden positiven nat"urlichen Zahlen $a,b,c$ geben soll mit $a+b=c$ und $$c > (\op{rad}(abc))^{1+\varepsilon}$$ Es soll also salopp gesprochen sehr selten sein, da"s f"ur teilerfremde positive nat"urliche Zahlen $a,b$ mit vergleichsweise kleinen Primfaktoren ihre Summe auch nur kleine Primfaktoren hat. Der Status der Vermutung ist zur Zeit (2019) noch ungekl"art. Man kann zeigen, da"s es unendlich viele Tripel von paarweise teilerfremden positiven nat"urlichen Zahlen $a0$ zur"uck. In diesem Fall beginnt man mit der Erkenntnis $\varphi(1\cdot 1)=\varphi(1)=1_R=1_R\cdot 1_R=\varphi(1)\varphi(1)$ und argumentiert von da aus mit vollst"andiger Induktion und dem Distributivgesetz. \end{proof} \begin{Bemerkungl}[\textbf{Ganze Zahlen und allgemeine Ringe}] Gegeben ein Ring $R$ notieren wir den Ringhomomorphismus $\DZ\ra R$ aus \ref{UEZz} manchmal $n\mapsto n_R$ und meist $n\mapsto n$. Ich will kurz diskutieren, warum das ungef"ahrlich ist.\label{GZAR} Gegeben $r\in R$ und $n\in\DZ$ gilt n"amlich stets $nr=n_R r=r n_R$, wobei $nr$ in Bezug auf die Struktur von $R$ als additive abelsche Gruppe verstehen, also $nr=n^+ r= r+r\ldots +r$ mit $n$ Summanden falls $n\geq 1$ und so weiter, wie in der Tabelle \eref{KFt}{GR} und in \eref{naa}{GR} ausgef"uhrt wird. Unsere Gleichung $nr=n_R r=r n_R$ bedeutet dann hinwiederum, da"s es auf den Unterschied zwischen $n_R$ und $n$ meist gar nicht ankommt. Deshalb f"uhrt es auch selten zu Mi"svert"andnissen, wenn wir statt $n_R$ nur kurz $n$ schreiben. \end{Bemerkungl} \begin{Bemerkungl} Eine Teilmenge eines Rings hei"st ein {\bf Teilring},\index{Teilring} wenn sie eine additive Untergruppe und ein multiplikatives Untermonoid ist. Ist also $R$ unser Ring, so ist eine Teilmenge $T\subset R$ genau dann ein Teilring, wenn gilt $0_R, 1_R\in T$, $a\in T\RA (-a)\in T$ sowie $a,b\in T\RA a+b, ab\in T$. Wir diskutieren diesen Begriff hier nur im Vorbeigehen, da er in dieser Vorlesung nur eine Nebenrolle spielt. \end{Bemerkungl} \subsubsection*{"Ubungen} \begin{Ubung}[\textbf{Quotientenring}] Gegeben ein Ring $R$ und eine Surjektion $R\sra Q$ von $R$ auf eine Menge $Q$, die an die Multiplikation und Addition von $R$ angepa"st ist im Sinne von \eref{koindV}{GR}, ist $Q$ mit der koinduzierten Addition und Multiplikation auch wieder ein Ring.\label{QuoRi} \end{Ubung} \begin{Ubunge}\label{MSRR} Auf der abelschen Gruppe $\DZ$ gibt es genau zwei Verkn"upfungen, die als Multiplikation die Addition zu einer Ringstruktur erg"anzen. \end{Ubunge} \begin{Ubung}\label{Riff} Man zeige, da"s in jedem Ring $R$ gilt $0a =0 \; \forall a \in R$; $-a = (-1) a \; \forall a \in R$; $(-1) (-1) =1$; $(-a)(-b)=ab\;\forall a,b\in R$. \end{Ubung} \newpage \begin{Ubung} Gegeben eine "Uberdeckung einer endlichen Menge $X$ durch Teilmengen $X=X_1\cup\ldots\cup X_n$ zeige man die {\bf Einschlu"s-Ausschlu"s-Formel}\index{Einschlu"s-Ausschlu"s-Formel} $$0=\sum_{I\subset \{1,\ldots,n\}}(-1)^{|I|}\left|{\textstyle \bigcup_{i\in I}X_i}\right|$$ %mit der Interpretation des leeren Schnitts als $X$. Im Fall $n=3$ etwa k"onnen wir das ausschreiben zu $$|X\cup Y\cup Z|=|X|+|Y|+|Z|-|X\cup Y| -|X\cup Z| -|Y\cup Z| +|X\cup Y\cup Z|$$ Hinweis: Sogar im Fall einer beliebigen Menge $X$ mit beliebigen Teilmengen $X_i$ mag man deren charakteristische Funktionen mit $\chi_i$ bezeichnen und im Ring der $\DZ$-wertigen Funktionen auf $X$ das Produkt $(1-\chi_1)\ldots(1-\chi_n)$ ausmultiplizieren. Danach mach man im endlichen Fall die Summe der Funktionswerte vergleichen. \end{Ubung} \begin{Ubung}\label{UeZz} F"ur jeden Ring $R$ gibt es h"ochstens einen Ringhomomorphismus $\DQ\ra R$, in Formeln $|\op{Ring}(\DQ, R)|\leq 1$. \end{Ubung} \subsection{Restklassenringe des Rings der ganzen Zahlen} \begin{Definition} Gegeben $G\supset H$ eine Gruppe mit einer Untergruppe definieren wir den {\bf Quotienten} $G/H$,\index{)1@$/$ Quotient}\index{Quotient} eine Teilmenge $G/H\subset \mathcal P(G)$, durch die Vorschrift $$G/H\pdef\{ L\subset G\mid \exists g\in G\text{ mit }L=gH\}$$ Die Teilmenge $gH\subset G$ hei"st die {\bf $H$-Linksnebenklasse von $g$ in $G$}.\index{Linksnebenklasse} Unser Quotient ist also die Menge aller $H$-Linksnebenklassen in $G$. Jedes Element einer Linksnebenklasse hei"st auch ein {\bf Repr"asentant}\index{Repr"asentant} besagter Linksnebenklasse. Eine Teilmenge $R\subset G$ derart, da"s die Vorschrift $g\mapsto gH$ eine Bijektion $R\sira G/H$ induziert, hei"st ein {\bf Repr"asentantensystem}\index{Repr"asentantensystem} f"ur die Menge der Linksnebenklassen. \end{Definition} \begin{Bemerkungw} Diese Konstruktion wird in \eref{NebK}{LA2} noch sehr viel ausf"uhrlicher diskutiert werden. \end{Bemerkungw} \begin{Beispiel} Im Fall der additiven Gruppe $\DZ$ mit der Untergruppe $m\DZ$ haben wir speziell $\DZ/m\DZ=\{L\subset \DZ\mid \exists a\in \DZ\text{ mit }L=a+m\DZ\}$. Die Linksnebenklasse von $a$ hei"st in diesem Fall auch die {\bf Restklasse von $a$ modulo $m$},\index{Restklasse} da zumindest im Fall $a \geq 0$ und $m>0$ ihre nichtnegativen Elemente genau alle nat"urlichen Zahlen sind, die beim Teilen durch $m$ denselben Rest lassen wie $a$. Wir notieren diese Restklasse auch $\bar{a}$.\label{Rkr} Nat"urlich ist $\bar{a} = \bar{b}$ gleichbedeutend zu $a -b \in m \mathbb Z$. Geh"oren $a$ und $b$ zur selben Restklasse, in Formeln $a + m\DZ = b + m\DZ$, so nennen wir sie \defnoind{kongruent modulo $m$}\index{kongruent modulo} und schreiben $$a \equiv b \pmod{m}$$ Offensichtlich gibt es f"ur $m>0 $ genau $m$ Restklassen modulo $m$, in Formeln $|\Bbb{Z} / m \Bbb{Z}| = m$, und wir haben genauer $$\Bbb{Z} / m \Bbb{Z}=\{\bar{0},\bar{1},\ldots,\overline{m-1}\}$$ Da in dieser Aufz"ahlung keine Nebenklassen mehrfach genannt werden, ist die Teilmenge $\{0,1,\ldots,m-1\}$ also ein Repr"asentantensystem f"ur die Menge von Nebenklassen $\Bbb{Z} / m \Bbb{Z}$. Ein anderes Repr"asentantensystem w"are $\{1,\ldots,m\}$, ein Drittes $\{1,\ldots,m-1,7m\}$. \end{Beispiel} \begin{Satz}[\textbf{Restklassenring}] F"ur alle $m\in\DZ$ gibt es auf der Menge $\Bbb{Z} / m \Bbb{Z}$ genau eine Struktur als Ring derart, da"s die Abbildung $\Bbb{Z}\sra \Bbb{Z} / m \Bbb{Z}$ mit $a\mapsto \bar a$ ein Ringhomomorphismus ist.\label{Rkr} \end{Satz} \begin{Bemerkungl} Das ist dann nat"urlich die Struktur als Quotientenring im Sinne unserer "Ubung \ref{QuoRi}. \end{Bemerkungl} \begin{proof} Da"s es h"ochstens eine derartige Ringstruktur gibt, es eh klar. Zu zeigen bleibt nur deren Existenz. Nach \eref{Verk}{GR} induziert jede Verkn"upfung auf einer Menge $A$ eine Verkn"upfung auf ihrer Potenzmenge $\mathcal P(A)$. F"ur die so von der Verkn"upfung $+$ auf $\DZ$ induzierte Verkn"upfung $+$ auf $\mathcal P (\mathbb Z)$ gilt offensichtlich $$\bar{a} + \bar{b} = (a+m\DZ)+ (b+m\DZ)= (a+b)+m\DZ=\overline{a+b} \quad \forall a,b \in \mathbb Z$$ Insbesondere induziert unsere Verkn"upfung $+$ auf $\mathcal P (\mathbb Z)$ eine Verkn"upfung $+$ auf $\mathbb Z / m \mathbb Z$ und $a\mapsto \bar a$ ist f"ur diese Verkn"upfungen ein Morphismus von Magmas alias Mengen mit Verkn"upfung. Ebenso k"onnen wir auf $\mathcal P (\mathbb Z)$ eine Verkn"upfung $\odot=\odot_m$ einf"uhren durch die Vorschrift \begin{equation*} T \odot S \pdef T \cdot S + m \mathbb Z \pdef \{ ab + mr \mid a \in T, b \in S, r \in \mathbb Z \} \end{equation*} Wieder pr"uft man f"ur die so erkl"arte Multiplikation m"uhelos die Formel \begin{equation*} \bar{a} \odot \bar{b} = \overline{ab} \end{equation*} Da"s $\mathbb Z / m \mathbb Z$ mit unseren beiden Verkn"upfungen ein Ring wird und $a\mapsto\bar a$ ein Ringhomomorphismus, folgt ohne weitere Schwierigkeiten aus der Surjektivit"at der nat"urlichen Abbildung $\DZ\sra \DZ/m\DZ$ alias "Ubung \ref{QuoRi}. \end{proof} \begin{Bemerkungl} Wir geben wir die komische Notation $\odot$ nun auch gleich wieder auf und schreiben stattdessen $\bar{a}\cdot \bar{b}$ oder noch k"urzer $\bar{a}\bar{b}$. Auch die Notation $\bar a$ werden wir meist zu $a$ vereinfachen, wie wir es ja in \ref{GZAR} eh schon vereinbart hatten. \end{Bemerkungl} \begin{Beispiel} Modulo $m=2$ gibt es genau zwei Restklassen: Die Elemente der Restklasse von $0$ bezeichnet man "ublicherweise als {\bf gerade Zahlen},\index{gerade!Zahl}\index{Zahl!gerade} die Elemente der Restklasse von $1$ als {\bf ungerade Zahlen}.\index{ungerade!Zahl}\index{Zahl!ungerade} Der Ring $\DZ/2\DZ$ mit diesen beiden Elementen $\bar{0}$ und $\bar{1}$ ist offensichtlich sogar ein K"orper. \end{Beispiel} \begin{Beispiel}[\textbf{Der Ring $\mathbb Z / 12 \mathbb Z$ der Uhrzeiten}] Den Ring $\mathbb Z / 12 \mathbb Z$ k"onnte man als \glqq Ring von Uhrzeiten\grqq\ ansehen. Er hat die zw"olf Elemente $\{\bar{0}, \bar{1}, \ldots, \overline{11}\}$ und wir haben $\overline{11} + \bar{5} = \overline{16} = \bar{4}$ alias \glqq $5$ Stunden nach $11$ Uhr ist es $4$ Uhr\grqq. Weiter haben wir in $\DZ/12\DZ$ etwa auch $\bar{3} \cdot \bar{8} = \overline{24} = \bar{0}$. In einem Ring kann es also durchaus passieren, da"s ein Produkt von zwei von Null verschiedenen Faktoren Null ist. \end{Beispiel} \begin{Bemerkungw} Sei $m\geq 1$ eine nat"urliche Zahl. Eine Restklasse modulo $m$ hei"st eine {\bf prime Restklasse},\index{prim!Restklasse}\index{Restklasse!prime} wenn sie aus zu $m$ teilerfremden Zahlen besteht. Wir zeigen in \eref{PZRc}{FT1}, da"s es in jeder primen Restklasse unendlich viele Primzahlen gibt. Im Fall $m=10$ bedeutet das zum Beispiel, da"s es jeweils unendlich viele Primzahlen gibt, deren Dezimaldarstellung mit einer der Ziffern $1,3,7$ und $9$ endet. \end{Bemerkungw} \begin{Proposition}[\textbf{Teilbarkeitskriterien "uber Quersummen}\index{Quersumme}] Eine nat"urliche Zahl ist genau dann durch Drei beziehungsweise durch Neun teilbar, wenn ihre Quersumme durch Drei beziehungsweise durch Neun teilbar ist. \end{Proposition} \begin{proof}[Beweis] Wir erkl"aren das Argument nur an einem Beispiel. Das ist nat"urlich im Sinne der Logik kein Beweis. Dies Vorgehen schien mir aber in diesem Fall besonders gut geeignet, dem Leser den Grund daf"ur klarzumachen, aus dem unsere Aussage im Allgemeinen gilt. Und das ist es ja genau, was ein Beweis in unserem mehr umgangssprachlichen Sinne leisten soll! Also frisch ans Werk. Per definitionem gilt $$1258 =1 \cdot 10^{3} + 2\cdot 10^{2} + 5\cdot 10 +8$$ Offensichtlich folgt $$\;\;\;\;\;\;\;\;\;\;\;\;\;1258 \equiv 1 \cdot 10^{3} + 2\cdot 10^{2} + 5\cdot 10 +8\pmod 3$$ Da $10$ kongruent ist zu $1$ modulo $3$ erhalten wir daraus $$1258 \equiv 1 + 2+ 5 +8 \pmod 3$$ Insbesondere ist die rechte Seite durch Drei teilbar genau dann, wenn die linke Seite durch Drei teilbar ist. Das Argument f"ur Neun statt Drei geht genauso. \end{proof} \begin{Bemerkungl} In $\DZ/12\DZ$ gilt zum Beispiel $\bar{3} \cdot \bar{5} = \bar{3}\cdot\bar{1}$. In allgemeinen Ringen d"urfen wir also nicht k"urzen. Dies Ph"anomen werden wir nun begrifflich fassen. Dazu vereinbaren wir, da"s bei Ringen unsere allgemeinen Konventionen \eref{kzb}{GR} zu K"urzbarkeit und Teilen stets in Bezug auf die Multiplikation zu verstehen sein sollen. Wir schreiben das auch noch aus. \end{Bemerkungl} \begin{Definition}\label{TeiR} \begin{enumerate} \item Gegeben ein Ring $R$ und Elemente $a,b\in R$ sagen wir, $a$ \defind{teilt} $b$ oder auch $a$ ist ein {\bf Teiler\index{Teiler} von $b$} und schreiben $a| b$,\index{)0a@$\mid$ ist Teiler von} wenn es $d\in R$ gibt mit $ad=b$. Ist unser Ring nicht kommutativ, so nennen wir $a$ genauer einen {\bf Linksteiler}\index{Linksteiler} von $b$ und erkl"aren analog {\bf Rechtsteiler};\index{Rechtsteiler} \item Ein Element $a\in R$ eines Rings hei"st {\bf linksk"urzbar},\index{linksk"urzbar} wenn die Multiplikation mit $a$ eine Injektion $(a\cdot):R\hra R$ liefert. Analog erkl"aren wir die Eigenschaft {\bf rechtsk"urzbar}.\index{rechtsk"urzbar} Ein Element, das linksk"urzbar und rechtsk"urzbar ist, nennen wir {\bf k"urzbar}.\index{k"urzbar} Ein nicht k"urzbares Element nennen wir {\bf nichtk"urzbar}\index{nichtk"urzbar}; \item Ein Ring hei"st ein {\bf Integrit"atsring}\index{Integrit"atsring} oder {\bf Integrit"atsbereich}\index{Integrit"atsbereich}, wenn er nicht der Nullring ist und das Produkt von je zwei von Null verschiedenen Elementen von Null verschieden ist. Einen kommutativen Integrit"atsring nennen wir auch einen {\bf Integrit"atskring}.\index{Integrit"atskring} \end{enumerate} \end{Definition} \begin{Beispiel} Die nichtk"urzbaren Elemente in $\DZ/12\DZ$ sind $0,2,3,4,6,8,9,10$. \end{Beispiel} \begin{Bemerkungl}[\textbf{Alternative Definition eines Integrit"atsrings}] Ein Ring ist ein Integrit"atsring genau dann, wenn er genau ein nichtk"urzbares Element hat. Im Nullring ist das einzige Element k"urzbar, deshalb ist er auch in dieser Fassung der Definition kein Integrit"atsring. In allen anderen Ringen ist die Null nicht k"urzbar. In einem Integrit"atsring ist folglich die Null das einzige nichtk"urzbare Element. \end{Bemerkungl} \begin{Bemerkungl}[\textbf{Diskussion der Terminologie}] In der Literatur hei"sen die nichtk"urzbaren Elemente eines Rings meist die \glqq Nullteiler\grqq.\index{{\it Nullteiler}} Mir gefiel diese Terminologie nicht, da ja nach unseren sonstigen Definitionen alle Elemente eines Rings Teiler der Null sind. \end{Bemerkungl} \begin{Bemerkungl}[\textbf{K"urzen in Ringen}]\index{K"urzen in Ringen} Sei $R$ ein Ring und $a\in R$. Genau dann ist der Gruppenhomomorphismus $(a\cdot):R\ra R$\label{KiRi} injektiv, wenn sein Kern Null ist, wenn also gilt $ax=0\RA x=0$. Per definitionem ist das also gleichbedeutend zu $a$ linksk"urzbar. \end{Bemerkungl} %\subsection{Endliche Primk"orper} \begin{Definition}\label{DeEi} Ein Element $a$ eines Rings $R$ hei"st {\bf invertierbar}\index{invertierbar!in Ring} oder genauer {\bf invertierbar in $R$} oder auch eine {\bf Einheit von $R$}\index{Einheit!von Ring}, wenn es bez"uglich der Multiplikation invertierbar ist im Sinne von \eref{DeGr}{GR}, wenn es also $b\in R$ gibt mit $ab=ba=1$. Die Menge der invertierbaren Elemente eines Rings bildet unter der Multiplikation eine Gruppe, die man die \defnoind{Gruppe der Einheiten von $R$}\index{Gruppe der Einheiten} nennt und gem"a"s unserer allgemeinen Konventionen \eref{NEM}{GR} mit $R^\times$ bezeichnet. \end{Definition} \begin{Beispiel} Der Ring $\DZ$ der ganzen Zahlen hat genau zwei Einheiten, n"amlich $1$ und $(-1)$. In Formeln haben wir also $\DZ^\times=\{1, -1\}$. Dahingegen sind die Einheiten im Ring $\DQ$ der rationalen Zahlen genau alle von Null verschiedenen Elemente, in Formeln $\DQ^\times=\DQ\backslash 0$. \end{Beispiel} \begin{Bemerkungl} Eine Einheit eines Krings teilt alle Elemente unseres Krings und ist sogar dasselbe\label{EniN} wie ein Teiler der Eins. \end{Bemerkungl} \begin{Bemerkungl} Jede Einheit eines Krings ist k"urzbar, aber k"urzbare Elemente m"ussen keine Einheiten sein. Zum Beispiel sind alle von Null verschiedenen ganzen Zahlen k"urzbar in $\DZ$, aber nur $\pm 1$ sind Einheiten. \end{Bemerkungl} \begin{Definition} Zwei Elemente eines Krings hei"sen {\bf teilerfremd}\index{teilerfremd!Elemente eines Krings}, wenn sie au"ser Einheiten\label{teif} keine gemeinsamen Teiler haben. \end{Definition} \begin{Bemerkungl} Allgemeiner mag man eine Teilmenge eines Krings {\bf teilerfremd} nennen, wenn es keine Nichteinheit unseres Krings gibt, die alle Elemente unserer Teilmenge teilt. \end{Bemerkungl} \begin{Bemerkungl}[\textbf{K"urzbare Elemente endlicher Ringe}] In einem endlichen Ring $R$ sind die Einheiten genau die k"urzbaren Elemente. In der Tat ist in diesem Fall die Multiplikation $(a\cdot):R\ra R$ genau dann injektiv,\label{Nnnn} wenn sie bijektiv ist. \end{Bemerkungl} \begin{Beispiel} Die Einheiten von $\DZ/12\DZ$ sind mithin genau $1,5,7,11$. Man pr"uft unschwer, da"s sogar jedes dieser Elemente sein eigenes Inverses ist. Mithin ist die Einheitengruppe $(\DZ/12\DZ)^\times$ des Uhrzeitenrings gerade unsere Klein'sche Vierergruppe. Im allgemeinen ein Inverses zu $a$ in $\DZ/m\DZ$ zu finden, l"auft auf die L"osung der Gleichung $ax=1+my$ hinaus. Wir hatten bereits gesehen, da"s der euklidische Algorithmus das leisten kann. \end{Beispiel} \begin{Bemerkungl}[\textbf{Ursprung der Terminologie}] A priori meint eine Einheit in der Physik das, was ein Mathematiker eine \glqq Basis eines eindimensionalen Vektorraums\grqq\ nennen w"urde. So w"are etwa die Sekunde $s$ eine Basis des schmutzigen reellen Vektorraums $\vec{\mathbb T}$ aller Zeitspannen. In Formeln ausgedr"uckt bedeutet das gerade, da"s das Daranmultiplizieren von $s$ eine Bijektion $\DR\sira \vec{\mathbb T}$ liefert. Mit den Einheiten eines Krings $R$ verh"alt es sich nun genauso: Genau dann ist $u\in R$ eine Einheit, wenn das Daranmultiplizieren von $u$ eine Bijektion $R\sira R$ liefert. Daher r"uhrt vermutlich die Terminologie. \end{Bemerkungl} \begin{Bemerkunge} In der Chemie rechnet man oft mit {\bf mol}\index{mol} und versteht darunter seit 2019 genau $6,\!02214076 \cdot 10^{23}$ und verwendet das als eine Einheit. Mathematisch gesehen sollte man das eigentlich eine Zahl nennen, aber nat"urlich ist $\DR$ auch ein eindimensionaler reeller Vektorraum und in diesem Sinne mag man auch alle von Null verschiedenen Elemente von $\DR$ Einheiten nennen. Diese Konvention des Mol war fr"uher noch sinnvoller, als man ein Mol als die Zahl der Kohlenstoffatome in einem Gramm des Standardisotops von Kohlenstoff erkl"arte und gar nicht so genau sagen konnte, wie viele Atome das nun genau sind. \end{Bemerkunge} \begin{Bemerkungl}\label{DK} Ein K"orper kann in der hier eingef"uhrten Begrifflichkeit definiert werden als Integrit"atskring, in dem jedes von Null verschiedene Element eine Einheit ist. \end{Bemerkungl} \begin{Proposition}[\textbf{Endliche Primk"orper}\index{endliche Primk"orper}]\label{EPK} Sei $m \in \DN$. Genau dann ist der Restklassenring $\DZ/m\DZ$ ein K"orper, wenn $m$ eine Primzahl ist. \end{Proposition} \begin{proof} Sei ohne Beschr"ankung der Allgemeinheit $m\geq 2$. Ist $m$ keine Primzahl, so gibt es $a,b\in \DN$ mit $a1$ keine Primzahl faktorisieren wir $m = ab$ mit $10$ mit nat"urlichen Zahlen $a0$ in der zweiten Faktorisierung. Wir haben also $P(\mu_1)=0$. Da wir $K$ als Integrit"atskring angenommen hatten, mu"s ein ein $i$ geben mit $\mu_1=\lambda_i$. Da mit $K$ auch $K[X]$ ein Integrit"atskring ist, d"urfen wir $(X-\mu_1)=(X-\lambda_i)$ k"urzen und kommen mit Induktion zum Ziel. \end{proof} \begin{Bemerkungl} Ist $K$ ein K"orper oder allgemeiner ein Integrit"atskring, $P \in K [X]$ ein Polynom und $\lambda\in K$ eine Nullstelle von $P$, so nennen wir das Supremum "uber alle $n\in\DN $ mit $(X-\lambda)^n|P$ die \defnoind{Vielfachheit der Nullstelle $\lambda$}\index{Vielfachheit!einer Nullstelle} oder auch ihre {\bf Ordnung}.\index{Ordnung!einer Nullstelle} Das Nullpolynom hat insbesondere an jeder Stelle eine Nullstelle der Vielfachheit $\infty$ und gar keine Nullstelle bei $\lambda$ ist dasselbe wie eine\label{Nsto} \glqq Nullstelle der Vielfachheit Null\grqq. Insbesondere ist im Fall eines K"orpers oder allgemeiner eines Integrit"atskrings auch die Zahl der mit ihren Vielfachheiten gez"ahlten Nullstellen eines von Null verschiedenen Polynoms beschr"ankt durch seinen Grad. \end{Bemerkungl} \begin{Definition} Ein K"orper $K$ hei"st \defnoind{algebraisch abgeschlossen}\index{algebraisch!abgeschlossen, K"orper}\index{abgeschlossen!algebraisch},\label{AlAb} wenn jedes nichtkonstante Polynom $P \in K [X]\backslash K$ mit Koeffizienten in unserem K"orper $K$ eine Nullstelle in unserem K"orper $K$ hat. \end{Definition} \begin{Beispiel} Der K"orper $K=\DR$ ist nicht algebraisch abgeschlossen, denn das Polynom $X^2+1$ hat keine reelle Nullstelle. \end{Beispiel} \begin{Bemerkungw}\label{KCAA} Der K"orper $\DC$ der komplexen Zahlen ist algebraisch abgeschlossen. Das ist die Aussage des sogenannten {\bf Fundamentalsatzes der Algebra}, f"ur\index{Fundamentalsatz der Algebra} den wir mehrere Beweise geben werden: Einen besonders elementaren Beweis nach Argand in der Analysis in \eref{FA}{AN1}, einen sehr eleganten mit den Methoden der Funktionentheorie in \eref{FSAF}{FT1}, und einen mehr algebraischen Beweis, bei dem die Analysis nur "uber den Zwischenwertsatz eingeht, in \eref{FSAA}{AL}. Mir selbst gef"allt der noch wieder andere Beweis mit den Mitteln der Topologie \eref{FSAT}{TF} am besten, da er meine Anschauung am meisten anspricht. Er wird in analytischer Verkleidung bereits in \eref{FAWI}{AN2} vorgef"uhrt. Eine heuristische Begr"undung wird in nebenstehendem Bild gegeben. \end{Bemerkungw} \begin{figure}[htb] \begin{minipage}{0.45\textwidth} \includegraphics[width=\textwidth]{SkriptenBilder/BildFdAl} \end{minipage}\hfill \begin{minipage}{0.45\textwidth}\centering Heuristische Begr"undung f"ur den Fundamentalsatz der Algebra. Eine mehrfach um einen am Ursprung aufgestellten Pfahl gelegte Seilschlinge kann nicht auf einen Punkt zusammengezogen werden, ohne da"s wir sie irgendwann "uber den Pfahl heben. \end{minipage} \end{figure} \begin{Bemerkungl}[\textbf{Heuristische Begr"undung f"ur den Fundamentalsatz der Algebra}] Ein Polynom $n$-ten Grades wird eine sehr gro"se Kreislinie in der komplexen Zahlenebene mit Zentrum im Ursprung abbilden auf einen Weg in der komplexen Zahlenebene, der \glqq den Ursprung $n$-mal uml"auft\grqq. Angedeutet ist etwa das Bild einer sehr gro"sen Kreislinie unter einem Polynom vom Grad Zwei. Schrumpfen wir nun unsere sehr gro"se Kreislinie zu immer kleineren Kreislinien bis auf einen Punkt, so schrumpfen auch diese Wege zu einem konstanten Weg zusammen. Unsere $n$-fach um einen etwa am Ursprung aufgestellten Pfahl laufende Seilschlinge kann jedoch offensichtlich nicht auf einen Punkt zusammengezogen werden, ohne da"s wir sie "uber den Pfahl heben, anders gesagt: Mindestens eines der Bilder dieser kleineren Kreislinien mu"s durch den Ursprung laufen, als da hei"st, unser Polynom mu"s auf mindestens einer dieser kleineren Kreislinien eine Nullstelle haben. In \eref{FDAT}{AN2} oder besser \eref{FSAT}{TF} werden wir diese Heuristik zu einem formalen Beweis ausbauen. \end{Bemerkungl} \begin{Korollar}\label{zl} Ist $K$ ein algebraisch abgeschlossener K"orper, so hat jedes von Null verschiedene Polynom $P\in K[X]\backslash 0$ eine {\em\bf Zerlegung in Linearfaktoren}\index{Linearfaktoren!Zerlegung in} der Gestalt $$P = c (X-\lambda_{1}) \ldots (X-\lambda_{n})$$ mit $n\geq 0$, $c\in K^\times$ und $\lambda_1,\ldots,\lambda_n\in K$. Dar"uber hinaus ist diese Zerlegung eindeutig bis auf die Reihenfolge der Faktoren. \end{Korollar} \begin{proof}[Beweis] In diesem Fall haben eben nur konstante von Null verschiedene Polynome keine Nullstellen. \end{proof} \begin{Bemerkungl} In anderen Worten liefert f"ur einen algebraisch abgeschlossenen K"orper $K$ das Aufmultiplizieren eine Bijektion\label{AMBk} $$\begin{array}{ccc}\left\{\begin{array}{c}\text{Endliche Multimengen}\\ \text{von Elementen von $K$} \end{array}\right\}&\sira &\left\{\begin{array}{c}\text{Polynome in $K[X]$}\\ \text{mit Leitkoeffizient Eins} \end{array}\right\}\\[4mm] _\mu\{\lambda_1,\ldots,\lambda_r\}&\mapsto&(X-\lambda_1)\ldots(X-\lambda_r) \end{array} $$ liefert. Das vorgestellte $\mu$ aus der linken Seite ist ein \glqq Multimengenanzeiger\grqq, mit dem wir es uns erlauben, Elemente mit Vielfachheiten zu betrachten und anzugeben. \end{Bemerkungl} \begin{Korollar}[\defnoind{Faktorisierung reeller Polynome}] Jedes von Null verschiedene Polynom $P$ mit reellen Koeffizienten besitzt\label{FRP} eine Zerlegung in Faktoren der Gestalt $$P = c (X-\lambda_{1}) \ldots (X-\lambda_{r}) (X^2+\mu_1 X+\nu_1) \ldots (X^2+\mu_sX+\nu_s)$$ mit $c,\lambda_1,\ldots,\lambda_r,\mu_1,\ldots, \mu_s,\nu_1,\ldots,\nu_s \in\DR$ derart, da"s die quadratischen Faktoren keine reellen Nullstellen haben. Diese Zerlegung ist eindeutig bis auf die Reihenfolge der Faktoren. \end{Korollar} \begin{proof}[Beweis] Da unser Polynom invariant ist unter der komplexen Konjugation, m"us\-sen sich seine mit ihren Vielfachheiten genommenen komplexen Nullstellen so durchnummerieren lassen, da"s $\lambda_1,\ldots,\lambda_r$ reell sind und da"s eine gerade Zahl nicht reeller Nullstellen "ubrigbleibt mit $\lambda_{r+2t-1}=\bar{\lambda}_{r+2t}$ f"ur $1\leq t\leq s$ und $r,s\geq 0$. Die Produkte $(X-\lambda_{r+2t-1})(X-\lambda_{r+2t})$ haben dann reelle Koeffizienten, da sie ja invariant sind unter der komplexen Konjugation, haben jedoch keine reellen Nullstellen. \end{proof} \begin{Bemerkungw} In der Algebra \eref{FarF}{AL} k"onnen Sie lernen, inwiefern sowohl die vorhergehenden Aussagen "uber die Faktorisierung von Polynomen als auch die Primfaktorzerlegung nat"urlicher Zahlen Spezialf"alle eines allgemeinen Satzes "uber die \glqq Faktorialit"at euklidischer Ringe\grqq\ sind. \end{Bemerkungw} \begin{Bemerkungl}[\textbf{Polynomringe in mehreren Variablen}] "Ahnlich wie den Polynomring in einer Variablen \ref{PoRi} konstruiert man auch Polynomringe in mehr Variablen "uber einem gegebenen Grundring $R$. Ist die Zahl der Variablen endlich, so kann man induktiv definieren\label{PoRiMV} $$R[X_{1}, \ldots , X_{n}]=(R[X_{1}, \ldots , X_{n-1}])[X_n]$$ Man kann aber auch f"ur eine beliebige Menge $I$ den Polynomring\index{)5]@$R[X_{1}, \ldots , X_{n}]$ Polynomring} $R[X_i]_{i\in I}$ bilden als die Menge aller \glqq endlichen formalen Linearkombinationen mit Koeffizienten aus $R$ von endlichen Monomen in den $X_i$\grqq. Ich verzichte an dieser Stelle auf eine formale Definition. \end{Bemerkungl} \begin{Bemerkunge} Bei Hochster kann man ein Beispiel f"ur nichtisomorphe kommutative Ringe $A\not\cong B$ finden, deren Polynomringe in einer Variablen doch isomorph sind, $A[T]\cong B[T]$. Die Konstruktion eines derartigen Beispiels ist aber bereits h"ohere Mathematik und f"ur uns an dieser Stelle nicht relevant. \end{Bemerkunge} \subsubsection*{"Ubungen} \begin{Ubung} Welche Matrix entsteht beim Einsetzen der quadratischen Matrix ${(^{\;\;0}_{-1}}\; {^{1}_{0})}$ in das Polynom $X^2+1$ ? \end{Ubung} \begin{Ubunge}\label{AbNs} Man zeige, da"s jede Nullstelle $\alpha\in\DC$ eines normierten Polynoms mit komplexen Koeffizienten $X^n+a_{n-1}X^{n-1}+\ldots +a_0$ die Absch"atzung $|\alpha|\leq 1+|a_{n-1}|+\ldots +|a_0|$ erf"ullt. Hinweis: Sonst gilt erst $|\alpha|>1$ und dann $|\alpha|^n>|a_{n-1}\alpha^{n-1}|+\ldots +|a_0|$. Umgekehrt zeige man auch, da"s aus der Absch"atzung $|\alpha|\leq C$ f"ur alle komplexen Wurzeln die Absch"atzung $|a_k|\leq {n\choose k} C^{n-k}$ f"ur die Koeffizienten folgt. \end{Ubunge} \begin{Ubung}\label{NKN} Ist $P\in\DR[X]$ ein Polynom mit reellen Koeffizienten und $\mu\in\DC$ eine komplexe Zahl, so gilt $P(\mu)=0\RA P(\bar{\mu})=0$. Ist also eine komplexe Zahl Nullstelle eines Polynoms mit reellen Koeffizienten, so ist auch die konjugiert komplexe Zahl eine Nullstelle desselben Polynoms. \end{Ubung} \begin{figure}[htb] \begin{minipage}{0.45\textwidth} \includegraphics[width=\textwidth]{SkriptenBilder/BildNKP} \end{minipage}\hfill \begin{minipage}{0.45\textwidth}\centering Die komplexen Nullstellen eines Polynoms mit reellen Koeffizienten, die nicht reell sind, tauchen immer in Paaren aus einer Wurzel und ihrer komplex Konjugierten auf, vergleiche auch "Ubung \ref{NKN}. \end{minipage} \end{figure} \begin{Ubunge} Seien $k, K$ kommutative Ringe, $i: k\ra K$ ein Ringhomomorphismus und $i: k[X]\ra K[X]$ der induzierten Ringhomomorphismus zwischen den zugeh"origen Polynomringen. Man zeige: Ist $\lambda\in k$ eine Nullstelle eines Polynoms $P \in k[X]$, so ist $i(\lambda)\in K$ eine Nullstelle des Polynoms $i(P)$. \end{Ubunge} \begin{Ubunge} Man zeige: In jedem endlichen K"orper ist das Produkt aller von Null verschiedenen Elemente $(-1)$. Hinweis: Man zeige zun"achst, da"s nur die Elemente $\pm 1$ ihre eigenen Inversen sind. Als Spezialfall erh"alt man die Kongruenz $(p-1)!\equiv -1\pmod p$ f"ur jede Primzahl $p$. Diese Aussage wird manchmal auch als {\bf Satz von Wilson} zitiert.\index{Wilson!Satz von} Ist $n\in \DN_{\geq 1}$ keine Primzahl, so zeigt man im "ubrigen leicht $(n-1)!\equiv 0\pmod n$. \end{Ubunge} \begin{Ubunge} Ist $K$ ein Integrit"atsbereich, so induziert die kanonische Einbettung $K\hra K[X]$ auf den Einheitengruppen eine Bijektion $K^\times \sira K[X]^\times$. Im Ring $(\DZ/4\DZ)[X]$ aber ist etwa auch $\bar{1}+\bar{2}X$ eine Einheit. \end{Ubunge} \begin{Ubung}\label{QuDr} Man zeige, da"s es in einem endlichen K"orper $\mathbb F$ einer von $2$ verschiedenen Charakteristik genau $(|\mathbb F|+1)/2$ Quadrate gibt, wohingegen in einem endlichen K"orper der Charakteristik $2$ jedes Element das Quadrat eines weiteren Elements ist. \end{Ubung} \begin{Ubung} Man zerlege das Polynom $X^4+2$ in $\DR[X]$ in der in \ref{FRP} beschriebenen Weise in ein Produkt quadratischer Faktoren ohne Nullstelle. \end{Ubung} \begin{Ubunge}\label{MFNr} Ein reelles Polynom hat bei $\lambda\in \DR$ eine mehrfache Nullstelle genau dann, wenn auch seine Ableitung bei $\lambda$ verschwindet. \end{Ubunge} \begin{Ubunge} Gegeben ein reelles Polynom, dessen komplexe Nullstellen bereits s"amtlich reell sind, ist jede Nullstelle seiner Ableitung reell und wenn sie keine Nullstelle der Funktion selbst ist, eine einfache Nullstelle der Ableitung. Hinweis: Zwischen je zwei Nullstellen unserer Funktion mu"s mindestens eine Nullstelle ihrer Ableitung liegen. \end{Ubunge} \begin{Ubunge} Man zeige: Die rationalen Nullstellen eines normierten Polynoms mit ganzzahligen Koeffizienten $P\in \DZ[X]$ sind bereits alle ganz. In Formeln folgt aus\label{NUQ} $P(\lambda)=0$ f"ur $\lambda\in \DQ$ also bereits $\lambda\in\DZ$. \end{Ubunge} \begin{Ubunge} Gegeben ein Ring $R$ bilden auch die {\bf formalen Potenzreihen mit Koeffizienten in $R$}\index{Potenzreihe!formale} der Gestalt $\sum_{n\geq 0}a_n X^n$ mit $a_n\in R$\label{FPR} einen Ring, der meist $R\llbracket X\rrbracket$ notiert\index{)5]]@$k\llbracket T\rrbracket$ formale Potenzreihen} wird. Man gebe eine exakte Definition dieses Rings und zeige, da"s seine Einheiten genau diejenigen Potenzreihen sind, deren konstanter Term eine Einheit in $R$ ist, in Formeln $$R\llbracket X\rrbracket^\times=R^\times+XR\llbracket X\rrbracket$$ Man verallgemeinere die Definition und Beschreibung der Einheiten auf Potenzreihenringe $R\llbracket X_1,\ldots,X_n\rrbracket$ in mehreren Variablen und konstruiere einen Ring\-isomorphismus $$(R\llbracket X_1,\ldots,X_n\rrbracket)\llbracket X_{n+1}\rrbracket\sira R\llbracket X_1,\ldots,X_n,X_{n+1} \rrbracket$$ \end{Ubunge} %\begin{Ubunge} % Seien $R$ ein Ring und %$f=\sum_{n\geq 0}a_n X^n\in R\llbracket X\rrbracket$ eine formale Potenzreihe, %f"ur die mindestens ein Koeffizient eine Einheit ist. %Man zeige, da"s es dann genau eine Einheit $u\in R\llbracket %X\rrbracket^\times$ %gibt derart,\label{WVS} %da"s $fu$ ein normiertes Polynom ist. %Man zeige genauer: %Ist $m$ minimal mit $a_m\in R^\times$, so gibt es % $u\in R\llbracket X\rrbracket^\times$ mit $fu\in R[X]$ normiert vom Grad $m$. %Diese Aussage ist ein formales Analogon des %{\bf Weierstra"s'schen Vorbereitungssatzes}\index{Weierstra"s!Vorbereitungssatz} % insbesondere im Fall, da"s %$R$ selbst ein formaler Potenzreihenring in mehreren Variablen % ist. %\end{Ubunge} \begin{Ubunge}\label{FRL} Gegeben ein Ring $R$ bilden auch die {\bf formalen Laurentreihen mit Koeffizienten in $R$}\index{Laurentreihe!formale} der Gestalt $\sum_{n\geq -N}a_n X^n$ mit $a_n\in R$ und $N\in\DN$ einen Ring, der meist $R(\!(X)\!)$\index{)5))@$R(\hspace{-0.8mm}(X)\hspace{-0.8mm})$ formale Laurentreihen} notiert wird. Man gebe eine exakte Definition dieses Rings und zeige, da"s im Fall $R\neq 0$ seine Einheiten genau diejenigen von Null verschiedenen Reihen sind, bei denen der Koeffizient der kleinsten mit von Null verschiedenem Koeffizienten auftauchenden Potenz von $X$ eine Einheit in $R$ ist, in Formeln $$R(\!(X)\!)^\times=\bigcup_{n\in \DZ} X^nR\llbracket X\rrbracket^\times$$ Insbesondere ist im Fall eines K"orpers $K$ auch $K(\!(X)\!)$ ein K"orper. \end{Ubunge} \begin{Bemerkunge} Wir verwenden hier die Terminologie, nach der bei {\bf formalen Laurentreihen}\index{Laurentreihe!formale} im Gegensatz zu den Laurentreihen der Funktionentheorie nur endlich viele Terme mit negativen Exponenten erlaubt sind. \end{Bemerkunge} %\begin{Ubunge}QUATSCH![\textbf{Formale Laurentreihen in mehreren Variablen}] % Man erkl"are zu einem beliebig vorgegebenen Ring $R$ den % Ring $R\llbracket X_1,\ldots, X_n\rrbracket$ der %{\bf formalen % Laurentreihen "uber $R$ in den Variablen $X_i$}\label{fLmV} %als die Menge aller %formalen Summen $s$ von Monomen in den $X_i$ mit Koeffizienten in $R$ derart, %da"s es eine untere Schranke $N(s)\in \DZ$ gibt, so da"s kein $X_i$ in einem Monom mit Koeffizient ungleich Null in $s$ in noch kleinerer Potenz als $N(s)$ auftritt. Man zeige, da"s dieser Ring im Fall eines K"orpers $R$ auch %selber wieder ein K"orper ist. %\end{Ubunge} \subsection{Polynome als Funktionen*} \begin{figure}[htb] \begin{minipage}{0.45\textwidth} \includegraphics[width=\textwidth]{SkriptenBilder/BildInterpN} \end{minipage}\hfill \begin{minipage}{0.45\textwidth}\centering Das Polynom $P(X)=2X^2-2X-1$ mit reellen Koeffizienten vom Grad $\leq 2$, das die an den St"utzstellen $-1,1,2$ vorgegebenen Werte $3,-1,3$ interpoliert. \end{minipage} \end{figure} \begin{Lemma}[\textbf{Interpolation durch Polynome}] Seien $K$ ein K"orper\label{InPo} und $x_0,$ $\ldots, x_n \in K$ paarweise verschiedene \emph{\bf St"utzstellen} und $y_0, \ldots, y_n\in K$ beliebig vorgegebene Werte. So gibt es genau ein Polynom $P \in K [X]$ vom Grad $\leq n$ mit $P (x_0) = y_0, \ldots, P(x_n) = y_n$. \end{Lemma} \begin{proof} Zun"achst ist sicher $(X - x_1) \ldots (X - x_n)\defp A_0 (X)$ ein Polynom vom Grad $n$, das bei $x_1, \ldots, x_n$ verschwindet und an allen anderen Stellen von Null verschieden ist, insbesondere auch bei $x_0$. Dann ist $L_0(X) \pdef A_0 (X) / A_0 (x_0)$ ein Polynom vom Grad $n$, das bei $x_0$ den Wert Eins annimmt und bei $x_1, \ldots, x_n$ verschwindet. In derselben Weise konstruieren wir auch Polynome $L_1 (X), \ldots, L_n (X)$ und erhalten ein m"ogliches Interpolationspolynom als \begin{equation*} P(X) = y_0 L_0 (X) + \ldots + y_n L_n (X) = \sum^n_{i=0} y_i \frac{\prod_{j\neq i} (X-x_j)} {\prod_{j\neq i} (x_i -x_j)} \end{equation*} Das zeigt die Existenz. Ist $Q$ eine weitere L"osung derselben Interpolationsaufgabe vom Grad $\leq n$, so ist $P-Q$ ein Polynom vom Grad $\leq n$ mit $n+1$ Nullstellen, eben bei den St"utzstellen $x_0, \ldots, x_n$. Wegen \ref{ZNPn} mu"s dann aber $P-Q$ das Nullpolynom sein, und das zeigt die Eindeutigkeit. \end{proof} \begin{Bemerkungl}\label{PMV} Um die bisher eingef"uhrten algebraischen Konzepte anschaulicher zu machen, will ich sie in Bezug setzen zu geometrischen Konzepten. Ist $K$ ein Kring, so k"onnen wir jedem Polynom $f \in K[X_{1}, \ldots , X_{n}]$ die Funktion $\tilde{f} : K^{n} \ra K$, $(x_{1}, \ldots, x_{n}) \mapsto f(x_{1}, \ldots, x_{n})$ zuordnen. Wir erhalten so einen Ringhomomorphismus $$K[X_{1}, \ldots, X_{n}] \ra \op{Ens} (K^{n},K)$$ Dieser Homomorphismus ist im allgemeinen weder injektiv noch surjektiv. Schon f"ur $n =1$, $K= \DR$ l"a"st sich ja keineswegs jede Abbildung $\DR \ra\DR$ durch ein Polynom beschreiben, also ist sie in diesem Fall nicht surjektiv. Im Fall eines endlichen K"orpers $K$ kann weiter f"ur $n\geq 1$ unsere $K$-lineare Auswertungsabbildung vom unendlichdimensionalen $K$-Vektorraum $K[X_{1}, \ldots , X_{n}]$ in den endlichdimensionalen $K$-Vektorraum $\op{Ens} (K^{n},K)$ unm"oglich injektiv sein. Wir haben jedoch den folgenden Satz. \end{Bemerkungl} \begin{Satz}[\textbf{Polynome als Funktionen}] \begin{enumerate} \item Ist $K$ ein unendlicher K"orper, ja allgemeiner ein unendlicher Integrit"atskring, so ist f"ur alle $n\in\DN$ die Auswertungsabbildung eine Injektion $K[X_{1}, \ldots , X_{n}] \hra \op{Ens} (K^{n},K)$; \item Ist $K$ ein endlicher K"orper, so ist f"ur alle $n\in\DN$ die Auswertungsabbildung eine Surjektion $K[X_{1}, \ldots, X_{n}] \sra \op{Ens} (K^{n},K)$. Ihren Kern beschreibt "Ubung \eref{KSuR}{LA2}. \end{enumerate}%\label{PAFu} \label{PoFu} \end{Satz} \begin{proof}[Beweis] 1. Durch Induktion "uber $n$. Der Fall $n=0$ ist eh klar. F"ur $n =1$ folgt die Behauptung aus der Erkenntnis, das jedes von Null verschiedene Polynom in $K[X]$ nur endlich viele Nullstellen in $K$ haben kann. Der Kern der Abbildung $$K[X] \ra \op{Ens} (K,K)$$ besteht also nur aus dem Nullpolynom. F"ur den Induktionsschritt setzen wir $X_{n} = Y$ und schreiben unser Polynom in der Gestalt $$P = a_{d} Y^{d} + \ldots + a_{1}Y + a_{0}$$ mit $a_{i} \in K [X_{1}, \ldots , X_{n-1}]$. Halten wir $(x_{1}, \ldots , x_{n-1}) = x \in K^{n-1}$ fest, so ist $a_{d} (x) Y^{d} + \ldots + a_{1}(x) Y + a_{0}(x) \in K[Y]$ das Nullpolynom nach dem Fall $n=1$. Also verschwinden $a_{d}(x), \ldots , a_{1} (x),a_{0}(x)$ f"ur alle $x \in K^{n-1}$, mit Induktion sind somit alle $a_{i}$ schon das Nullpolynom und wir haben $P =0$. \\[2mm]\noindent 2. Das bleibt dem Leser "uberlassen. Man mag sich beim Beweis an \ref{InPo} orientieren. Wir folgern in \eref{IP}{AL} eine allgemeinere Aussage aus dem abstrakten chinesischen Restsatz. \end{proof} \subsubsection*{"Ubungen} \begin{Ubunge} Man zeige, da"s jeder algebraisch abgeschlossene K"or\-per unendlich ist. Hinweis: Im Fall $1\neq -1$ reicht es, Quadratwurzeln zu suchen.\label{uev} Man zeige, da"s jedes nichtkonstante Polynom $P\in K[X,Y]$ in zwei Ver"anderlichen "uber einem algebraisch abgeschlossenen K"orper unendlich viele Nullstellen in $K^2$ hat. \end{Ubunge} \begin{Ubunge}[\textbf{Nullstellensatz f"ur Hyperebenen}] Sei $K$ ein unendlicher K"orper.\label{HYT} Verschwindet ein Polynom im Polynomring in $d$ Variablen "uber $K$ auf einer affinen Hyperebene in $K^{d}$, so wird es von jeder linearen Gleichung besagter Hyperebene geteilt. Hinweis: Ohne Beschr"ankung der Allgemeinheit mag man unsere Hyperebene als eine der Koordinatenhyperebenen annehmen. Man zeige auch allgemeiner: Verschwindet ein Polynom in $d$ Ver"anderlichen "uber einem unendlichen K"orper auf der Vereinigung der paarweise verschiedenen affinen Hyperebenen $H_1, \ldots, H_n\subset K^d$, so wird es vom Produkt der linearen Gleichungen unserer Hyperebenen geteilt. \end{Ubunge} \begin{Bemerkungw} Allgemeinere Aussagen in dieser Richtung macht der Hilbert'sche Nullstellensatz \eref{HN}{KAG}. \end{Bemerkungw} \begin{Ubunge}[\textbf{Pythagoreische Zahlen}] Man zeige: Stellen wir eine Lampe oben auf den Einheitskreis und bilden jeden von $(0,1)$ verschiedenen Punkt des Einheitskreises ab auf denjenigen Punkt der Parallelen zur $x$-Achse durch $(0,-1)$, auf den sein Schatten f"allt, so entsprechen die Punkte mit rationalen Koordinaten auf dem Einheitskreis genau den Punkten mit rationalen Koordinaten auf unserer Parallelen. Hinweis: Hat ein Polynom in $\DQ[X]$ vom Grad drei zwei rationale Nullstellen, so ist auch seine dritte Nullstelle rational.\label{PyS} Geben wir das Bild vom Schattenwurf auf und nehmen den Schnitt des Lichtstrahls mit der $x$-Achse, so steht eine explizite Formel f"ur die Umkehrabbildung in \eref{PRr}{AN1}. \end{Ubunge} \begin{figure}[htb] \begin{minipage}{0.45\textwidth} \includegraphics[width=\textwidth]{SkriptenBilder/BildPyT} \end{minipage}\hfill \begin{minipage}{0.45\textwidth}\centering Nach "Ubung \ref{PyS} entsprechen die Punkte mit rationalen Koordinaten auf dem Einheitskreis genau den Punkten mit rationalen Koordinaten auf einer Geraden. \end{minipage} \end{figure} \begin{Bemerkunge} Unter einem {\bf pythagoreischen Zahlentripel} versteht man ein Tripel $(a,b,c)$ von positiven nat"urlichen Zahlen mit $a^2+b^2=c^2$, die also als Seitenl"angen eines rechtwinkligen Dreiecks auftreten k"onnen. Die pythagoreischen Zahlentripel mit gr"o"stem gemeinsamen Teiler $\langle a,b,c\rangle =\langle 1\rangle$ und $c>0$ entsprechen nun offensichtlich eineindeutig den Punkten mit rationalen Koordinaten auf dem Einheitskreis vermittels der Vorschrift $(a,b,c)\mapsto (a/c,b/c)$. In dieser Weise liefert unser Bild also einen geometrischen Zugang zur Klassifikation der pythagoreischen Zahlentripel. \end{Bemerkunge} \begin{Ubung} Man zeige, da"s die Menge der Polynome in $\DQ[X]$, die an allen Punkten aus $\DN$ ganzzahlige Werte annehmen, "ubereinstimmt mit der Menge\label{numPO} aller Linearkombinationen mit ganzzahligen Koeffizienten der mithilfe der Binomialkoeffizienten gebildeten Polynome $${X \choose k} \pdef \frac{X (X-1) \ldots (X - k+1)} {k(k-1) \ldots 1}\quad\text{ falls $k\geq 1$ und } {X \choose 0} \pdef 1.$$ Hinweis: Man berechne die Werte unserer Polynome bei $X=0,1,2,\ldots$ Die "Ubung zeigt, da"s diejenigen Polynome in $\DQ[X]$, die an allen Punkten aus $\DN$ ganzzahlige Werte annehmen, sogar an allen Punkten aus $\DZ$ ganzzahlige Werte annehmen m"ussen. Sie hei"sen {\bf ganzwertige} oder {\bf numerische Polynome}. \index{numerisch!Polynom}\index{ganzwertig!Polynom}\index{Polynom!numerisches}\index{Polynom!ganzwertiges} Man zeige weiter f"ur jedes Polynom in $\DQ[X]$ vom Grad $d\geq 0$, das an fast allen Punkten aus $\DN$ ganzzahlige Werte annimmt, da"s es ein ganzwertiges Polynom sein mu"s und da"s das $(d!)$-fache seines Leitkoeffizienten mithin eine ganze Zahl sein mu"s. \end{Ubung} \begin{Ubunge} Man zeige, da"s die Menge aller Polynome mit rationalen Koeffizienten in $\DQ[X_1,\ldots,X_r]$, die an allen Punkten aus $\DN^r$ ganzzahlige Werte annehmen, "ubereinstimmt mit der Menge\label{numPOm} aller Linearkombinationen mit ganzzahligen Koeffizienten von Produkten der Gestalt $${X_1 \choose k_1}\ldots {X_r \choose k_r} $$ mit $k_1,\ldots, k_r\geq 0$. Hinweis: Man argumentiere wie in \ref{numPO}. \end{Ubunge} \begin{Ubung} Ein Polynom "uber einem K"orper $k$ der Charakteristik $\op{char}k=0$, das eine injektive Abbildung $k\hra k$ liefert, hat den Grad Eins.\label{pikl} \end{Ubung} \subsection{Bruchk"orper und Partialbruchzerlegung}\label{QoK} \begin{Bemerkungl} Die Konstruktion des K"orpers $\DQ$ der Bruchzahlen aus dem Integrit"atsbereich $\DZ$ der ganzen Zahlen hatten wir bisher noch nicht formal besprochen. Hier holen wir das gleich in gr"o"serer Allgemeinheit nach und zeigen, wie man zu jedem Integrit"atsbereich seinen \glqq Bruchk"orper\grqq\ konstruieren kann. \end{Bemerkungl} \begin{Definition}\label{DQok} Gegeben ein kommutativer Integrit"atsbereich $R$ konstruieren wir seinen {\bf Bruchk"orper}\index{Frac@$\op{Frac}$ Bruchk"orper} \index{Bruchk"orper} $$\op{Frac}(R)$$ wie folgt: Wir betrachten die Menge $R\times (R\backslash 0)$ und erkl"aren darauf eine Relation $\sim$ durch die Vorschrift $$(a,s) \sim (b,t)\text{ genau dann, wenn gilt $at= bs$.}$$ Diese Relation ist eine "Aquivalenzrelation, wie man leicht pr"uft. Wir bezeichnen die Menge der "Aquivalenzklassen mit $\op{Frac}(R)$ und die "Aquivalenzklasse von $(a,s)$ mit $\frac{a}{s}$ oder $a/s$. Dann erkl"aren wir auf $\op{Frac}(R)$ Verkn"upfungen $+$ und $\cdot$ durch die Regeln $$\frac{a}{s} + \frac{b}{t} = \frac{at + bs}{st}\;\;\;\text{und}\;\;\; \frac{a}{s}\cdot \frac{b}{t} = \frac{ab}{st}$$ und "uberlassen dem Leser den Nachweis, da"s diese Verkn"upfungen wohldefiniert sind und $\op{Frac}(R)$ zu einem K"orper machen und da"s die Abbildung $\op{can} : R \ra \op{Frac}(R)$, $r \mapsto r/1$ ein injektiver Ringhomomorphismus ist. Er hei"st die {\bf kanonische Einbettung} unseres Integrit"atsbereichs in seinen Bruchk"orper. \end{Definition} \begin{Bemerkunge} Auf Englisch bezeichnet man den Bruchk"orper als {\bf fraction field}\index{fraction field} und auf Franz"osisch als {\bf corps de fractions}. Auf Deutsch nennt man ihn auch oft \glqq Quotientenk"orper\grqq, aber\index{Quotientenk"orper@{\it Quotientenk"orper}} das kann leicht zum Mi"sverst"andnis f"uhren, es handle sich dabei um eine Quotientenkonstruktion wie bei Quotientenvektorr"aumen oder Nebenklassengruppen. Die noch allgemeinere Konstruktion der \glqq Lokalisierung\grqq\ lernen wir erst in \eref{LokR}{KAG} kennen. \end{Bemerkunge} \begin{Beispiel} Der K"orper der rationalen Zahlen $\DQ$ wird formal definiert als der Quotientenk"orper des Rings der ganzen Zahlen, in Formeln $$\DQ\pdef\op{Frac}\DZ$$ Sicher w"are es unter formalen Aspekten betrachtet eigentlich richtig gewesen, diese Definition schon viel fr"uher zu geben. Es schien mir jedoch didaktisch ungeschickt, gleich am Anfang derart viel Zeit und Formeln auf die exakte Konstruktion einer Struktur zu verwenden, die Ihnen bereits zu Beginn ihres Studiums hinreichend vertraut sein sollte. Wie bereits bei rationalen Zahlen nennt man auch im allgemeinen bei einem Bruch $g/h$ das Element $g$ den {\bf Z"ahler}\index{Z"ahler} und das Element $h$ den {\bf Nenner}\index{Nenner} des Bruchs. \end{Beispiel} \begin{Satz}[\textbf{Universelle Eigenschaft des Bruchk"orpers}] Sei $R$ ein kommutativer Integrit"atsbereich.\label{UEQ} Ist $\varphi : R \ra A$ ein Ringhomomorphismus, unter dem jedes von Null verschiedene Element von $R$ auf eine Einheit von $A$ abgebildet wird, so faktorisiert $\varphi$ eindeutig "uber $\op{Frac}R$, es gibt also in Formeln genau einen Ringhomomorphismus $\tilde{\varphi} : \op{Frac}R \ra A$ mit $\varphi(r) = \tilde{\varphi}(r/1)\;\forall r\in R$. \end{Satz} \begin{proof}[Beweis] F"ur jedes m"ogliche $\tilde{\varphi}$ mu"s gelten $\tilde{\varphi} (r/s)= \varphi (r) \varphi(s)^{-1}$. Das zeigt bereits die Eindeutigkeit von $\tilde{\varphi}$. Um auch seine Existenz zu zeigen, betrachten wir die Abbildung $\hat{\varphi}: R\times(R\backslash 0)\ra A$ gegeben durch $\hat{\varphi} (r,s)= \varphi (r) \varphi(s)^{-1}$ und pr"ufen, da"s sie konstant ist auf "Aquivalenzklassen. Dann mu"s sie nach \ref{UEAQ} eine wohlbestimmte Abbildung $\op{Frac}R \ra A$ induzieren, von der der Leser leicht selbst pr"ufen wird, da"s sie ein Ringhomomorphismus ist. \end{proof} \begin{Bemerkungl}[\textbf{Br"uche mit kontrollierten Nennern}] Gegeben ein kommutativer Integrit"atsbereich $R$ und eine Teilmenge $S\subset R\backslash 0$ betrachten wir im Bruchk"orper von $R$ den Teilring\index{)6aa@$S^{-1}$ Lokalisierung!$S^{-1}R$ eines Integrit"atsbereichs} $$S^{-1}R\pdef\left\{(r/s)\in \op{Frac}R\mid s\text{ ist ein Produkt von Elementen von }S\right\}$$ Hierbei ist die Eins auch als Produkt von Elementen von $S$ zu verstehen, eben als das leere Produkt. Insbesondere erhalten wir eine Einbettung $R\hra S^{-1}R$ durch $r\mapsto (r/1)$. Ist nun $\varphi : R \ra A$ ein Ringhomomorphismus, unter dem jedes Element von $S$ auf eine Einheit von $A$ abgebildet wird, so faktorisiert $\varphi$ mit demselben Beweis wie zuvor eindeutig "uber $S^{-1}R$, es gibt also in Formeln genau einen\label{KoBr} Ringhomomorphismus $\tilde{\varphi} : S^{-1}R \ra A$ mit $\varphi(r) = \tilde{\varphi}(r/1)\;\forall r\in R$. \end{Bemerkungl} \begin{Beispiel}[\textbf{Auswerten rationaler Funktionen}] Ist $K$ ein K"orper, so bezeichnet man den Bruchk"orper des Polynomrings mit\label{DRF} $ K (X)\pdef \op{Frac} K[X] $\index{)5)@$K(X)$ Funktionenk"orper} und nennt ihn den {\bf Funktionenk"orper\index{Funktionenk"orper} zu $K$} und seine Elemente {\bf rationale Funktionen}.\index{rationale Funktion}\index{Funktion!rationale} Man lasse sich durch die Terminologie nicht verwirren, Elemente dieses K"orpers sind per definitionem formale Ausdr"ucke und eben gerade keine Funktionen. Inwiefern man sie zumindest f"ur unendliches $K$ doch als Funktionen verstehen darf, soll nun ausgef"uhrt werden. Gegeben $\lambda\in K$ betrachten wir dazu die Menge $S_\lambda\pdef\{P\mid P(\lambda)\neq 0\}$ aller Polynome, die bei $\lambda$ keine Nullstelle haben, und bezeichnen mit $$K[X]_\lambda\pdef S_\lambda^{-1} K[X]\subset K(X)$$ der Teilring aller Br"uche von Polynomen, die sich darstellen lassen als ein Bruch, dessen Nenner bei $\lambda$ keine Nullstelle hat. Auf diesem Teilring ist das Auswerten bei $\lambda$ nach \ref{KoBr} ein wohlbestimmter Ringhomomorphismus $K[X]_\lambda\ra K$, den wir notieren als $f\mapsto f(\lambda)$. Er ist der einzige Ringhomomorphismus $K[X]_\lambda\ra K$ mit $X\mapsto\lambda$, der bei Vorschalten der Einbettung von $K$ die Identit"at auf $K$ liefert. Gegeben $f\in K(X)$ hei"sen die Punkte $\lambda\in K$ mit $f\not\in K[X]_\lambda$ die {\bf Polstellen von $f$}\index{Polstelle!von rationaler Funktion} und das kleinste $n$ mit $(X-\lambda)^n f\in K[X]_\lambda$ hei"st die {\bf Polstellenordnung von $f$ bei $\lambda$}.\index{Polstellenordnung} Jedes Element $f\in K(X)$ hat h"ochstens endlich viele Polstellen. F"ur jede rationale Funktion $f \in K (X)$ erkl"art man ihren {\bf Definitionsbereich}\index{Definitionsbereich} \index{D@$D (f)$ Definitionsbereich von $f$} $D (f) \subset K$\label{DRFn} als die Menge aller Punkte $a \in K$, die keine Polstellen von $f$ sind. Durch \glqq K"urzen von Nullstellen\grqq\ "uberzeugt man sich, da"s jede rationale Funktion so als Bruch $f = g/h$ geschrieben werden kann, da"s Z"ahler und Nenner keine gemeinsamen Nullstellen in $K$ haben, und da"s dann die Polstellen gerade die Nullstellen des Nenners sind. Vereinbart man, da"s $f$ diesen Stellen als Wert ein neues Symbol $\infty$ zuweisen soll, so erh"alt man f"ur jeden unendlichen K"orper $K$ sogar eine wohlbestimmte Injektion $K(X)\hra\op{Ens}(K,K\amalg\{\infty\})$. \end{Beispiel} \begin{Bemerkungl}[\textbf{Verschiedene Definitionen f"ur Definitionsbereiche}] In der Schule m"ogen Sie gelernt haben, da"s etwa die Funktion $x/x$ bei $x=0$ nicht definiert sei. Von unserem Standpunkt aus ist das nicht so klar. Es gibt einerseits den Begriff einer Funktion als einer Abbildung, und um eine Abbildung anzugeben m"ussen bei uns im Prinzip Definitionsbereich, Wertebereich und Abbildungsvorschrift gleich mit angegeben werden. Die Abbildungsvorschrift $x\mapsto x/x$ kann in der Tat bei $x=0$ nicht sinnvoll in der Art \glqq setze erst $x=0 $ f"ur die Variable ein und f"uhre dann die vorgeschriebenen Operationen im K"orper $\DR$ durch\grqq\ ausgewertet werden. Im Sinne unserer obigen Definition gilt im Funktionenk"oper $\DR(X)$ dahingegen $1=X/X$ und die Null geh"ort durchaus zum Definitionsbereich dieser rationalen Funktion im in \ref{DRFn} erkl"arten Sinne. \end{Bemerkungl} \begin{Bemerkungw} Es ist sogar richtig, da"s jede rationale Funktion eine eindeutige maximal gek"urzte Darstellung mit normiertem Nenner hat. Um das einzusehen, ben"otigt man ein Analogon der eindeutigen Primfaktorzerlegung f"ur Polynomringe, das wir f"ur einen allgemeinen K"orper $K$ erst in \eref{PReF}{AL} zeigen. \end{Bemerkungw} \begin{Bemerkungl}\label{EGR} Wir erinnern aus \ref{FPR} und \ref{FRL} die Ringe der Potenzreihen und der Laurentreihen. Gegeben ein K"orper $K$ liefert die Verkn"upfung von Einbettungen $K[X]\hra K\llbracket X\rrbracket\hra K(\!(X)\!)$ offensichtlich einen Ringhomomorphismus und nach der universellen Eigenschaft \ref{UEQ} mithin eine Einbettung $K(X)\hra K(\!(X)\!)$. Das Bild von $(1-X)^{-1}$ unter dieser Einbettung ist etwa die \glqq formale geometrische Reihe\grqq\ $1+X+X^2+X^3+\ldots$ \end{Bemerkungl} \begin{Bemerkunge}\label{LauA} Sei $K$ ein K"orper. Ist $p\in K$ fest gew"ahlt und $K(T)\sira K(X)$ der durch $T\mapsto (X+p)$ gegebene Isomorphismus, so bezeichnet man das Bild von $f\in K(T)$ unter der Komposition $K(T)\sira K(X)\hra K(\!(X)\!)$ auch als die {\bf Laurententwicklung von $f$ um den Entwicklungspunkt $p$}.\index{Laurententwicklung!algebraische} Meist schreibt man in einer Laurententwicklung statt $X$ auch $(T-p)$. So w"are die Laurententwicklung von $f=T^2/(T-1)$ um den Entwicklungspunkt $T=1$ etwa die endliche Laurentreihe $(T-1)^{-1}+2+(T-1)$. \end{Bemerkunge} \begin{Satz}[\textbf{Partialbruchzerlegung}] Gegeben ein algebraisch abgeschlossener K"orper $K$ wird eine $K$-Basis des Funktionenk"orpers $K(X)$ gebildet von erstens den Potenzen der Variablen $(X^n)_{n\geq 1}$ mitsamt zweitens den\label{PBZ} Potenzen der Inversen der Linearfaktoren $((X-a)^{-n})_{n\geq 1,\;a\in K }$ zuz"uglich drittens der Eins $1\in K(X)$.\label{pbzx} \end{Satz} \begin{Bemerkungl} Eine Darstellung einer rationalen Funktion als Linearkombination der Elemente dieser Basis nennt man eine {\bf Partialbruchzerlegung}\index{Partialbruchzerlegung} unserer rationalen Funktion. Anschaulich scheint mir zumindest die lineare Unabh"angigkeit der behaupteten Basis recht einsichtig: Polstellen an verschiedenen Punkten k"onnen sich ebensowenig gegenseitig aufheben wie Polstellen verschiedener Ordnung an einem vorgegebenen Punkt. Alle rationalen Funktionen mag man auffassen als Funktionen auf der projektiven Gerade $\DP^1 K$ aus \eref{PrIf}{EL} und die $(X^n)_{n\geq 1}$ als Funktionen, die \glqq eine Polstelle der Ordnung $n$ im Unendlichen haben\grqq. Das ist auch der Grund daf"ur, da"s ich die $1$ im Satz oben extra aufgef"uhrt habe und nicht stattdessen einfach k"urzer $(X^n)_{n\geq 0}$ schreibe. Dennoch spielen sie eine etwas andere Rolle. $X^n$ hat eine $n$-fache Nullstelle bei Null und eine $n$-fache Polstelle bei $\infty$, dahingegen hat $(X-\lambda)^{-n}$ eine $n$-fache Polstelle bei $\lambda$ und eine $n$-fache Nullstelle bei $\infty$. Von allen Funktionen, die an einer Stelle eine $n$-fache Nullstelle und an einer anderen Stelle eine $n$-fache Polstelle haben, nehmen wir also nur eine unkanonische Auswahl, um eine Basis zu erhalten. \end{Bemerkungl} \begin{Bemerkungl} Ist $K$ ein algebraisch abgeschlossener K"orper, so sind die Polstellen eines Elements $f\in K(X)$ im Sinne von \ref{DRF} genau die Elemente $a\in K$ mit der Eigenschaft, da"s f"ur ein $n\geq 1$ der Term $(X-a)^{-n}$ mit von Null verschiedenem Koeffizienten in der Partialbruchzerlegung von $f$ auftritt. \end{Bemerkungl} \begin{Bemerkunge} In B"uchern zur Analysis findet man oft eine Variante dieses Satzes f"ur den K"orper $K=\DR:$ In diesem Fall werden die im Satz beschriebenen Elemente erg"anzt zu einer Basis durch die Elemente $1/((X-\lambda)(X-\bar{\lambda}))^n$ und die Elemente $X/((X-\lambda)(X-\bar{\lambda}))^n$ f"ur $\lambda\in\DC$ mit positivem Imagin"arteil und $n\geq 1$ beliebig, wie der Leser zur "Ubung selbst zeigen mag. Eine Verallgemeinerung auf den Fall eines beliebigen K"orpers $K$ wird in \eref{pbzz}{AL} diskutiert. \end{Bemerkunge} \begin{proof}[Beweis] Wir zeigen zun"achst, da"s unsere Familie den Funktionenk"orper als $K$-Vektorraum erzeugt. Sei also $f\in K(X)$ dargestellt als Bruch von zwei Polynomen $f=P/Q$ mit $Q\neq 0$. Wir argumentieren mit Induktion "uber den Grad von $Q$. Ist $Q$ konstant, so haben wir schon gewonnen. Sonst besitzt $Q$ eine Nullstelle $\mu\in K$ und wir k"onnen schreiben $Q(x)=(X-\mu)^m\tilde{Q}(x)$ mit $m\geq 1$ und $\tilde{Q}(\mu) \neq 0$. Dann nehmen wir $c\pdef P(\mu) / \tilde{Q}(\mu)$ und betrachten die Funktion $$\frac{P}{Q} - \frac{c}{(X-\mu)^{m}} = \frac{P-c \tilde{Q}} {(X-\mu)^{m} \tilde{Q}}$$ Aufgrund unserer Wahl von $c$ hat der Z"ahler auf der rechten Seite eine Nullstelle bei $X = \mu$, wir k"onnen im Bruch also $(X - \mu)$ k"urzen, und eine offensichtliche Induktion "uber dem Grad des Polynoms $Q$ beendet den Beweis. Zum Beweis der linearen Unabh"angigkeit betrachten wir eine Linearkombination unserer Basis in spe, die die Nullfunktion darstellt. Sei $c(X-a)^{-n}$ ein Summand darin mit $n\geq 1$ gr"o"stm"oglich f"ur die gew"ahlte Polstelle $a$. So multiplizieren wir mit $(X-a)^{n}$ und werten aus bei $a$ im Sinne von \ref{KoBr} und finden, da"s schon $c=0$ gegolten haben mu"s. So argumentieren wir alle Polstellen weg. Da"s die nichtnegativen Potenzen von $X$ linear unabh"angig sind, folgt ja schon aus der Definition des Polynomrings. \end{proof} \begin{Bemerkungl}[\textbf{Berechnung einer Partialbruchzerlegung}] Will man konkret eine Partialbruchzerlegung bestimmen, so rate ich dazu, mit einer\label{PBZe} Polynomdivision zu beginnen und $P=AQ+R$ zu schreiben mit Polynomen $A$ und $R$ derart, da"s der Grad von $R$ echt kleiner ist als der Grad von $Q$. Wir erhalten $P/Q=A+R/Q$, und in der Partialbruchzerlegung von $R/Q$ tritt dann kein polynomialer Summand mehr auf. Die Polstellen-Summanden geh"oren dann alle zu Nullstellen von $Q$ und ihr Grad ist beschr"ankt durch die Vielfachheit der entsprechenden Nullstelle von $Q$. Nun setzen wir die Koeffizienten unserer Linearkombination als Unbestimmte an, f"ur die wir dann ein lineares Gleichungssystem erhalten, das wir mit den "ublichen Verfahren l"osen. \end{Bemerkungl} \begin{Beispiel}\label{BPDa} Wir bestimmen von $(X^4 + 2 X^2) / (X^2+2X +1)$ die Partialbruchzerlegung. Die Polynomdivision haben wir bereits in \ref{BPDaa} durchgef"uhrt und $X^4 + 2X^2 = (X^2 - 2 X +5) (X^2 +2X +1) - 8X -5$ erhalten, so da"s sich unser Bruch vereinfacht zu \begin{displaymath} \frac{X^4 + 2X^2}{X^2+2X+1} = X^2 -2X +5 -\frac{8X +5}{X^2+2X+1} \end{displaymath} Jetzt zerlegen wir den Nenner in Linearfaktoren $X^2 +2X +1 = (X+1)^2$ und d"urfen nach unserem Satz "uber die Partialbruchzerlegung \begin{displaymath} \frac{8X +5}{(X+1)^2} = \frac{a}{X+1} + \frac{b}{(X+1)^2} \end{displaymath} ansetzen, woraus sich ergibt $8X +5 = aX + a + b$ und damit $a =8$ und $b =-3$. Die Partialbruchzerlegung unserer urspr"unglichen Funktion hat also die Gestalt \begin{displaymath} \frac{X^4+2X^2}{X^2 +2X +1} = X^2 -2X +5 - \frac{8}{X+1} + \frac{3}{(X+1)^2} \end{displaymath} \end{Beispiel} \begin{Bemerkungl}[\textbf{Geschlossene Darstellung der Fibonacci-Zahlen}] Wir bilden die sogenannte {\bf erzeugende Funktion}\index{erzeugende Funktion!der Fibonacci-Folge} der Fibonacci-Folge alias die\label{FiAl} formale Potenzreihe $f (x) =\sum_{n \geq 0} f_n x^n$ mit den Fibonacci-Zahlen aus \eref{FiFo}{EIN} als Koeffizienten. Die Rekursionsformel f"ur Fibonacci-Zahlen $f_{n+2}=f_{n+1}+ f_n$ liefert unmittelbar $x f (x) + x^2 f(x) = f(x) -x$. Wir folgern $(1-x-x^2) f (x) = x$. Umgekehrt hat jede formale Potenzreihe, die diese Identit"at erf"ullt, die Fibonacci-Zahlen als Koeffizienten. Es gilt also, die Funktion $x/(1-x-x^2)$ in eine Potenzreihe zu entwickeln. Dazu erinnern wir Satz \ref{PBZ} "uber die Partialbruchzerlegung, schreiben $x^2 + x -1 = (x +\alpha) (x+ \beta)$ mit $\alpha = \frac{1}{2} + \frac{1}{2} \sqrt{5}$ und $\beta= \frac{1}{2} - \frac{1}{2} \sqrt{5}$ und d"urfen $x/(1-x-x^2) =a/(x + \alpha) + b/(x+\beta)$ ansetzen. Zur Vereinfachung der weiteren Rechnungen erinnern wir $\alpha \beta =-1$ und variieren unseren Ansatz zu $x/(1-x-x^2) = c/(1-x\alpha ) + d/(1-x\beta )$. Das f"uhrt zu $c + d =0$ alias $c = -d$ und $\alpha c + \beta d =-1$ alias $c = 1 /(\beta - \alpha) = 1/\sqrt{5}$. Die Entwicklung unserer Br"uche in eine geometrische Reihe nach \ref{EGR} liefert damit im Ring der formalen Potenzreihen die Identit"at \begin{equation*} \frac{x}{1-x-x^2} = \sum_{i \geq 0} \frac{( x\alpha)^i}{\sqrt{5}} - \frac{(x\beta )^i}{\sqrt{5}} \end{equation*} und f"ur den Koeffizienten von $x^i$ alias die $i$-te Fibonacci-Zahl $f_i$ ergibt sich wie in \eref{FiFo}{EIN} die Darstellung \begin{equation*} f_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{equation*} \end{Bemerkungl} \subsubsection*{"Ubungen} \begin{Ubung}\label{AOQ} Man zeige: Besitzt ein kommutativer Integrit"atsbereich $R$ eine Anordnung $\leq$, unter der er im Sinne von \eref{ARI}{AN1} ein angeordneter Ring wird, so besitzt sein Bruchk"orper $\op{Frac}R$ genau eine Struktur als angeordneter K"orper, f"ur die die kanonische Einbettung $R\hra\op{Frac}R$ mit der Anordnung vertr"aglich alias monoton wachsend ist. Speziell erhalten wir so die "ubliche Anordnung auf $\DQ=\op{Frac}\DZ$. \end{Ubung} \begin{Ubunge}\label{PN} Gegeben ein unendlicher K"orper $K$ und eine von Null verschiedene rationale Funktion $f\in K(X)^\times$ sind die Polstellen von $f$ genau die Nullstellen von $(1/f)$, als da hei"st, die Stellen aus dem Definitionsbereich von $(1/f)$, an denen diese Funktion den Wert Null annimmt. Fassen wir genauer $f$ als Abbildung $f:K\ra K\amalg\{\infty\}$ auf, so entspricht $(1/f)$ der Abbildung $a\mapsto f(a)^{-1}$, wenn wir $0^{-1}=\infty$ und $\infty^{-1}=0$ vereinbaren. \end{Ubunge} \begin{Ubung} Sei $P\in \DQ(X)$ gegeben. Man zeige: Gibt es eine Folge ganzer Zahlen aus dem Definitionsbereich unserer rationalen Funktion\label{WGP} $a_n\in\DZ\cap D(P)$ mit $a_n\ra\infty$ und $P(a_n)\in\DZ$ f"ur alle $n$, so ist $P$ bereits ein Polynom $P\in \DQ[X]$. \end{Ubung} \begin{Ubung} Sei $K$ ein K"oper und seien $f,g\in K(X)$ gegeben. Man zeige: Gibt es unendlich viele Punkte aus dem gemeinsamen Definitionsbereich $D(f)\cap D(g)$, an denen $f$ und $g$ denselben Wert annehmen, so gilt bereits $f=g$ in $K(X)$. \end{Ubung} \begin{Ubunge} Man zeige, da"s im K"orper $\DQ(\!(X)\!)$ jede formale Potenzreihe mit konstantem Koeffizienten Eins eine Quadratwurzel besitzt. Die Quadratwurzel von $(1+X)$ kann sogar durch die binomische Reihe \eref{BiRe}{AN1} explizit angegeben werden, aber das sieht man leichter mit den Methoden der Analysis. \end{Ubunge} \begin{Ubung} Man bestimme die Partialbruchzerlegung von $1/(1+X^4)$ in $\DC(X)$. \end{Ubung} \begin{Ubung} Man zeige, da"s bei einem Bruch $P(T)/(T^n(T-1)^m)$ mit Z"ahler $P(T)\in\DZ[T]$\label{PBZG} auch alle Koeffizienten bei der Partialbruchzerlegung ganze Zahlen sind. \end{Ubung} \begin{Ubung} Man bearbeite nocheinmal die "Ubungen \eref{ZSFF}{EIN} und \eref{ZSFFv}{EIN}. \end{Ubung} \begin{Ubung}[\textbf{Verkn"upfung rationaler Funktionen}] Ist $K$ ein K"orper und $P\in K[X]$ ein von Null verschiedenes Polynom, so liegt jede Nullstelle von $P$ im gr"o"seren K"orper $K(Y) \supset K$\label{VRfu} bereits im Teilk"orper $K$. Gegeben $f\in K(X)$ geh"ort mithin jedes $g\in K(Y)\backslash K$ zum Definitionsbereich von $f$ und wir k"onnen mithin setzen $$f\circ g\pdef f(g)\in K(Y)$$ Man zeige, da"s die $K$-linearen K"orperhomomorphismen $\varphi:K(X)\ra K(Y)$ alle die Gestalt $\varphi:f\mapsto f\circ g$ haben f"ur $g=\varphi(X)\in K(Y)\backslash K$. Sind $f$ und $g$ beide nicht konstant, so ist auch $f\circ g$ nicht konstant. Gegeben $f,g,h\in K(X)\backslash K$ zeige man die Assoziativit"at $(f\circ g)\circ h=f\circ( g\circ h)$. Unsere Abbildung $K(X)\ra \op{Ens}(K,K\sqcup\{\infty\})$ kann zu einer Abbildung $K(X)\ra \op{Ens}(K\sqcup\{\infty\})$ fortgesetzt werden, indem wir f"ur $f=P/Q$ den Wert $f(\infty)$ erkl"aren als den Bruch $a_n/b_n$ der Leitkoeffizienten, falls $P$ und $Q$ denselben Grad $n$ haben, und $\infty$ falls der Grad von $P$ gr"o"ser ist als der von $Q$, und $0$ falls er kleiner ist. So erhalten wir einen Monoidhomomorphismus $(K(X),\circ)\ra (\op{Ens}(K\sqcup\{\infty\}),\circ)$, der im Fall eines unendlichen K"orpers $K$ injektiv ist. \end{Ubung} \begin{Ubung}[\textbf{Bruchk"orper von Ringen formaler Potenzreihen}] Gegeben ein kommutativer Integrit"atsbereich $R$ zeige man, da"s die universelle Eigenschaft des Bruchk"orpers einen K"orperisomorphismus $$\op{Frac}(R\llbracket X\rrbracket)\sira (\op{Frac}R)(\!( X)\!)$$ induziert. Induktiv erhalten wir so etwa f"ur jeden K"orper $K$ einen K"orperisomorphismus $$\big(K(\!( X)\!)\big)(\!( Y)\!)\sira \big(K(\!( Y)\!)\big)(\!( X)\!)$$ Zum Beispiel ist $(X-Y)^{-1}=X^{-1}(1-Y/X)^{-1}=\sum_{n\geq 0} X^{-n-1}Y^n$ die Darstellung eines Elements auf der linken Seite, das auf der rechten Seite auf den Ausdruck $\sum_{n\geq 0} -Y^{-n-1}X^n$ abgebildet wird. \end{Ubung} \subsection{Quaternionen*} \begin{Bemerkungl} Dieser Abschnitt ist f"ur den Rest der Vorlesung unerheblich. Allerdings geh"oren die Quaternionen zur mathematischen Allgemeinbildung. \end{Bemerkungl} \begin{Definition}\label{DsKn} Ein \defind{Schiefk"orper} ist ein Ring $R$, der nicht der Nullring ist und in dem alle von Null verschiedenen Elemente Einheiten sind. Auf englisch sagt man \defind{skew field}, auf franz"osisch \defind{corps gauche}. Gleichbedeutend spricht man auch von einem \defind{Divisionsring}. \end{Definition} \begin{Satz}[\textbf{Quaternionen}] Es gibt F"unftupel $(\mathbb{H},\op{i},\op{j},\op{k},\kappa)$ bestehend aus einem Ring\index{Quaternionen} $\mathbb{H}$, Elementen $\op{i},\op{j},\op{k}\in \mathbb{H}$ und einem Ringhomomorphismus $\kappa : \mathbb{R} \rightarrow \mathbb{H}$ derart,\label{DQuaR} da"s gilt $$\op{i}^2=\op{j}^2=\op{k}^2=\op{i}\op{j}\op{k}=-1$$ und $\kappa(a)q=q\kappa(a)\;\forall a\in \DR$, $q\in \mathbb H$ und da"s $1, \op{i},\op{j},\op{k}$ eine Basis von $\mathbb{H}$ bilden f"ur die durch die Vorschrift $\DR\times\mathbb H\ra\mathbb H$, $(a,q)\mapsto \kappa(a)q$ auf $\mathbb{H}$ gegebene Struktur als $\mathbb{R}$-Vektorraum. Des weiteren ist in einem derartigem F"unftupel der Ring $\mathbb H$ ein Schiefk"orper. \end{Satz} \begin{Bemerkungl} Ein derartiges F"unftupel ist im wesentlichen eindeutig bestimmt in der offensichtlichen Weise. Um das zu sehen beachten wir, da"s durch Multiplikation der letzten Gleichung von rechts mit $\op{k}$ folgt $\op{i}\op{j}=\op{k}$ und durch Invertieren beider Seiten weiter $\op{j}\op{i}=-\op{k}$. Von da ausgehend erhalten wir unmittelbar die Formeln $$\op{i}\op{j}=\op{k}=-\op{j}\op{i},\quad \op{j}\op{k}=\op{i}=-\op{k}\op{j},\quad \op{k}\op{i}=\op{j}=-\op{i}\op{k},$$ und so die Eindeutigkeit.\label{DQua} Wegen dieser Eindeutigkeit erlauben wir uns den bestimmten Artikel und nennen $\mathbb{H}$ den Schiefk"orper der {\bf Quaternionen}\index{Quaternionen}, da er als Vektorraum "uber den reellen Zahlen die Dimension Vier hat. Weiter k"urzen wir f"ur reelle Zahlen $a\in \DR$ meist $\kappa(a)=a$ ab. Jedes Element $q\in\mathbb H$ hat also die Gestalt $$q=a+b\op{i}+c\op{j}+d\op{k}$$ mit wohlbestimmten $a,b,c,d\in\DR$. Die Abbildung $\DC\hra \mathbb H$ mit $a+b{\op{i}}_\DC\mapsto a+b{\op{i}}$ ist ein Ringhomomorphismus und wir machen auch f"ur komplexe Zahlen meist in der Notation keinen Unterschied zwischen unserer Zahl und ihrem Bild in $\mathbb H$ unter obiger Einbettung. In \eref{Quat}{AL} diskutieren wir, warum und in welcher Weise $\DR,\DC$ und $\mathbb{H}$ bis auf Isomorphismus die einzigen Schiefk"orper endlicher Dimension \glqq "uber dem K"orper $\DR$\grqq\ sind. Die Notation $\mathbb H$ geht auf Hamilton zur"uck, einem der Entdecker dieser Struktur, der sich sehr f"ur ihre Verwendung in der Physik stark machte. \end{Bemerkungl} \begin{Bemerkungl} Auch die Abbildungen $\DC\ra\mathbb H$ mit $a+b{\op{i}}_\DC\mapsto a+b{\op{j}}$ oder mit $a+b{\op{i}}_\DC\mapsto a+b{\op{k}}$ sind Ringhomomorphismen, und wir werden bald sehen, da"s es sogar unendlich viele $\DR$-lineare Ringhomomorphismen, ja eine ganze $3$-Sph"are von $\DR$-linearen Ringhomomorphismen $\DC\ra\mathbb H$ gibt. \end{Bemerkungl} \begin{proof} Bezeichne $\Bbb{H}$ die Menge aller komplexen $(2\times 2) $-Matrizen der Gestalt $$\Bbb{H} =\left.\left\{ \left({z\atop \bar{y}} \;{ -y\atop \;\; \bar{z} }\right) \right| z,y \in \Bbb{C} \right\} \subset \op{Mat}(2; \Bbb{C}) $$ Die Addition und Multiplikation von Matrizen induziert offensichtlich eine Addition und Multiplikation auf $\Bbb{H}$ und wir erhalten eine Einbettung $\DC\hra \Bbb{H}$ vermittels $z\mapsto \op{diag}(z,\bar{z})$. Das Bilden der konjugierten transponierten Matrix definiert einen Antiautomorphismus $q\mapsto \bar{q}$ von $\Bbb{H}$, in Formeln $\overline{qw} =\bar{w} \bar{q}$, und $q\bar{q} $ ist f"ur $q\neq 0$ stets positiv und reell. Folglich ist $\Bbb{H}$ ein Schiefk"orper. Wir fassen $\DC$ meist als Teilmenge von $\Bbb{H}$ auf vermittels der eben erkl"arten Einbettung, aber vorerst unterscheiden wir noch zwischen den komplexen Zahlen $1_\DC$, $\op{i}_\DC$ und den Matrizen $1=\op{diag}(1_\DC,1_\DC)$, $\op{i}=\op{diag}(\op{i}_\DC,-\op{i}_\DC)$. Unser $\Bbb{H}$ hat dann "uber $\DR$ die Basis $1,\op{i}, \op{j},\op{k}$ mit $\op{i}\pdef\op{diag}(\op{i}_\DC,-\op{i}_\DC)$ und $$\op{j}\pdef \left({\;\;0\atop -1} {\;\;1\atop \;\;0}\right)\text{ und }\op{k}\pdef \left({0\;\atop \op{i}_\DC} {\op{i}_\DC\atop 0}\right)$$ und es gilt \begin{equation*} \op{i}^{2} = \op{j}^{2} = \op{k}^{2}= \op{i}\op{j}\op{k} = -1 \qedhere\end{equation*} \end{proof} \begin{Bemerkungl}\label{KQua} Jede zyklische Vertauschung von $\op{i},\op{j},\op{k}$ liefert einen Automorphismus der Quaternionen. Die Konjugation $q \mapsto \bar{q}$ aus der im Beweis gegebenen Konstruktion hat in der Basis $1, \op{i},\op{j},\op{k}$ die Gestalt $$\overline{a+b\op{i}+c\op{j}+d\op{k}} = a - b\op{i}-c\op{j}-d\op{k}$$ und hat wie bereits erw"ahnt die Eigenschaft $\overline{qw} =\bar{w} \bar{q}$. Gegeben ein Quaternion $q = a+b \op{i} +c\op{j}+d\op{k}$ nennt man $a=(q+\bar{q})/2$ seinen {\bf Realteil}\index{Realteil!bei Quaternionen} und schreibt $a=\op{Re}(q)$. F"ur $q = a+b \op{i} +c\op{j}+d\op{k}$ ist $q \bar{q} = \bar{q}q = a^{2}+b^{2}+c^{2}+d^{2}$ und man setzt $| q| = \sqrt{q \bar{q}}$ und nennt diese reelle Zahl den {\bf Betrag}\index{Betrag!bei Quaternionen} unseres Quaternions. Offensichtlich kann f"ur $q\neq 0$ sein Inverses durch die Formel $q^{-1}=\bar{q}/|q|^2$ angegeben werden. Offensichtlich gilt dann $| qw| =| q| | w|$ f"ur alle $q,w\in\Bbb{H}$ und die Gruppe aller Quaternionen der L"ange Eins besteht genau aus allen unit"aren $(2\times 2)$-Matrizen mit Determinante Eins. Darin enthalten ist die Untergruppe der acht Quaternionen $\{\pm 1,\pm \op{i},\pm \op{j},\pm \op{k}\}$, die sogenannte {\bf Quaternionengruppe},\index{Quaternionengruppe} von deren Multiplikationstabelle Hamilton bei seiner Konstruktion ausgegangen war. \end{Bemerkungl} \begin{Bemerkungw} Gegeben ein Kring $R$ mitsamt einem selbstinversen Ringhomomorphismus $R\ra R$, $r\mapsto\bar{r}$ und einem Element $v\in R$ mit $\bar{v}=v$ bildet allgemeiner die Menge aller $(2\times 2) $-Matrizen der Gestalt $$\Bbb{H} =\left.\left\{ \left({z\atop \bar{y}} \;{ vy\atop \;\; \bar{z} }\right) \right| z,y \in R \right\} \subset \op{Mat}(2; R) $$ einen Teilring des Matrizenrings. Derartige Ringe hei"sen {\bf Quaternionenringe}.\index{Quaternionenring} \end{Bemerkungw} \begin{Bemerkungl} Es gibt au"ser der Identit"at nur einen $\DR$-linearen K"orperhomomorphismus $\DC\ra\DC$, n"amlich die komplexe Konjugation. Im Fall der Quaternionen liefert dahingegen jede von Null verschiedene Quaternion $q\in\mathbb H^\times$ einen $\DR$-linearen Ringhomomorphismus $\op{int}q:\mathbb H\ra\mathbb H$, $w\mapsto qwq^{-1}$, und $\op{int}q=\op{int}q'$ impliziert bereits $\DR q=\DR q'$. \end{Bemerkungl} \subsubsection*{"Ubungen} \begin{Ubung} Man zeige, da"s es f"ur jedes Quaternion $q$ mit Realteil $\op{Re}q=0$ und Betrag $|q|=1$ einen $\DR$-linearen Ringhomomorphismus $\DC\ra\mathbb H$ gibt mit $\op{i}_\DC\mapsto q$. \end{Ubung} \begin{Ubunge} Man zeige: Sind zwei nat"urliche Zahlen jeweils eine Summe von vier Quadraten, so auch ihr Produkt. Diese Erkenntnis ist ein wichtiger Schritt bei einem Beweis des sogenannten {\bf Vier-Quadrate-Satzes} von Lagrange, nach dem jede nat"urliche Zahl eine Summe von vier Quadratzahlen ist, etwa $3=1^2+1^2+1^2+0^2$ oder $23=3^2+3^2+2^2+1^2$. \end{Ubunge} %%% Local Variables: %%% mode: latex %%% TeX-master: "XXLA1" %%% End: