_06-Verknuepfungen.tex

\setchapterpreamble[c][.7\textwidth]{\itshape\color{gray}\small
    Der Begriff der Verknüpfung verallgemeinert die aus der Schule bekannten Rechenoperationen und dieser Vortrag könnte genausogut „Rechnen“ betitelt sein. Es werden grundlegende Eigenschaften von Verknüpfungen untersucht und ein paar Konsequenzen daraus abgeleitet.
\vspace{24pt}}


\chapter{Verknüpfungen} \label{chap:verknuepfungen}


\section{Allgemeines}


\begin{defin}[Verknüpfung] \label{def:verknuepfung} \index{Verknüpfung}
    Sei $X$ eine beliebige Menge. Eine (zweistellige) \textbf{Verknüpfung auf $X$} ist eine Abbildung $X\times X \to X$, d.h. eine Abbildung, die je zwei Elementen von $X$ wiederum ein Element von $X$ zuordnet. Eine zweistellige Verknüpfung wird in der Regel mit einem „Verknüpfungszeichen“ notiert: ist der Name der Verknüpfungsabbildung etwa „$*$“, so schreibt man
        \[ x*y \qquad\text{anstelle von}\qquad *(x,y) \]
    für den Funktionswert des Paares $(x,y)$ unter der Abbildung $*$.
\end{defin}


\begin{bem}[* Verallgemeinerungen]
    Prinzipiell lassen sich auch dreistellige und höherstellige Verknüpfungen definieren. Auch können Verknüpfungen zwischen verschiedenen Mengen existieren, wie es in der LA1 etwa bei der \emph{skalaren Multiplikation} eines Vektorraums der Fall ist. In diesem Kapitel sollen mit „Verknüpfungen“ aber ausschließlich (innere) zweistellige Verknüpfungen gemeint sein, wie sie soeben definiert wurden.
\end{bem}


\begin{bsp}[Grundrechenarten] \label{bsp:verknuepfung}
    Es gilt:
    \begin{enumerate}
        \item Auf $\R$ ist durch die Addition $x,y\mapsto x+y$ eine zweistellige Verknüpfung gegeben. Da die Summe zweier rationaler Zahlen ebenfalls rational ist, liefert „$+$“ auch eine Verknüpfung auf der Menge $\Q$. Ebenso ist auch auf $\N$ und $\Z$ durch die Addition „$+$“ jeweils eine Verknüpfung gegeben.
        \item Auf den Mengen $\N,\Z,\Q,\R,\C$ ist durch die Multiplikation $x,y\mapsto x\cdot y$ jeweils eine zweistellige Verknüpfung gegeben.
        \item Auf den Mengen $\Z,\Q,\R,\C$ ist durch die Subtraktion $x,y\mapsto x-y$ jeweils eine zweistellige Verknüpfung gegeben. Für $\N$ ergäbe der Ausdruck
        \[ \text{„$\N \times \N \to \N \ ,\ (x,y) \mapsto x-y$“} \]
        allerdings keinen Sinn, da z.B. $2-3$ gar kein Element von $\N$ wäre. Auf $\N$ ist die Subtraktion also \emph{keine} zweistellige Verknüpfung. Zwar lassen sich für gewisse Zahlenpaare durchaus Differenzen in $\N$ bilden (z.B. $3-2$); dass $-$ eine Verknüpfung auf $\N$ wäre, scheitert aber daran, dass eben nicht \emph{jedes} Paar natürlicher Zahlen eine Differenz in $\N$ besitzt.\footnote{Als nächstbesten Ersatz für die Subtraktion hat man auf $\N$ die \href{https://en.wikipedia.org/wiki/Monus\#Natural_numbers}{„Monus“-Verknüpfung}.}
        \item Auf den Mengen $\Q\setminus \{0\},\R\setminus \{0\},\C\setminus \{0\}$ ist durch die Division $x,y\mapsto x:y$ jeweils eine zweistellige Verknüpfung gegeben. Beachte, dass die Null ausgelassen werden muss, weil bspw. nicht „$1:0$“ gerechnet werden kann. Zwar könnte man $1:0=\infty$ setzen, aber $\infty$ wäre kein Element von $\Q,\R$ bzw. $\C$, sodass dadurch nachwievor keine Verknüpfung auf $\Q,\R$ bzw. $\C$ zustandekäme.
    \end{enumerate}
\end{bsp}


\begin{bsp}[Operationen mit Mengen]
    Sei $M$ eine beliebige Menge. Auf der Potenzmenge $\calP(M)$ haben wir beispielsweise folgende Verknüpfungen:
    \begin{align*}
        \cap : \calP(M)\times \calP(M) \to \calP(M) \ & ,\ (A,B)\mapsto A\cap B \\
        \cup : \calP(M)\times \calP(M) \to \calP(M) \ &,\ (A,B)\mapsto A\cup B \\
        \setminus : \calP(M)\times \calP(M) \to \calP(M) \ &,\ (A,B)\mapsto A\setminus B
    \end{align*}
    Denn der Durchschnitt / die Vereinigung / die Differenzmenge zweier Teilmengen von $M$ ist ebenfalls eine Teilmenge von $M$.
\end{bsp}


\begin{bsp}[* Kleineres und Größeres zweier Elemente] \label{bsp:minmaxverknuepfung}
    Auf $\R$ gibt es die beiden Verknüpfungen
    \begin{align*}
        \min : \R\times \R\to \R\ &,\ (x,y)\mapsto \min\{x,y\} \\
        \max : \R\times \R\to \R\ &,\ (x,y)\mapsto \max\{x,y\}
    \end{align*}
    die ein Zahlenpaar jeweils auf die kleinere bzw. die größere der beiden Zahlen abbildet. Eine Verallgemeinerung sowohl dieses Beispiels als auch des Beispiels mit $\cap$ und $\cup$ stellen \href{https://de.wikipedia.org/wiki/Verband_(Mathematik)}{Verbände} dar.
\end{bsp}


\begin{bsp}[Verketten von Abbildungen] \label{bsp:selbstabbildungen}
    Sei $M$ eine beliebige Menge. Dann ist auf der Menge $\Abb(M,M)$ der Selbstabbildungen von $M$ eine Verknüpfung gegeben durch die Verkettung von Abbildungen $g,f\mapsto g\circ f$.\footnote{siehe \cref{def:verkettung}}
\end{bsp}


\begin{bem}[*]
    Für verschiedene Mengen $A,B,C$ ist die Abbildung
        \[ \Abb(B,C) \times \Abb(A,B) \to \Abb(A,C) \ ,\ (g,f) \mapsto g\circ f \]
    jedoch keine Verknüpfung im Sinne von \cref{def:verknuepfung}, da die involvierten Mengen $\Abb(B,C)$, $\Abb(A,B)$ und $\Abb(A,C)$ verschieden sind. Aus diesem Grund beschränke ich mich in \cref{bsp:selbstabbildungen} auf Selbstabbildungen einer Menge $M$.

    Nichtsdestotrotz besitzt auch das allgemeine Verketten von Abbildungen die wichtige und häufig auftretende Struktur einer \href{https://ncatlab.org/nlab/show/category}{Kategorie}, vgl. \cref{kategorien}. Mehr darüber wirst du spätestens in fortgeschrittenen Algebra-Vorlesungen erfahren.
\end{bem}


\begin{bem}
    Alle bisher beschriebenen Verknüpfungen besaßen ein spezifisches eigenes Verknüpfungssymbol und waren relativ übersichtlich aufzuschreiben. Allgemeine Verknüpfungen auf einer Menge $X$ dürfen aber beliebig kompliziert sein. Es muss sich ja lediglich um \emph{irgendeine} Abbildung $X\times X\to X$ handeln, die beliebig chaotisch sein darf und keinem Muster gehorchen braucht. Neben Addition und Multiplikation gibt es auf $\N$ unendlich viele weitere Verknüpfungen, von denen die meisten wohl niemals von mathematischem Interesse sein werden.
\end{bem}


\begin{nota}[Verknüpfungssymbole]
    In diesem Text werde ich, wenn ich über eine „allgemeine zweistellige Verknüpfung“ schreibe, die Verknüpfung mit einem „$*$“ notieren. Die vorigen Beispiele zeigen, dass konkrete Verknüpfungen auch mit ganz anderen Zeichen wie etwa $+,-,\cdot,:,\cap,\cup$, usw. notiert werden. Andere Bücher und Vorlesungen verwenden auch andere Symbole, wie etwa „$\odot$“ oder „$\circ$“, um über „die allgemeine Verknüpfung“ zu sprechen.
\end{nota}


\begin{defin}[Eingeschränkte Verknüpfung] \index{abgeschlossene Teilmenge (bzgl. einer Verknüpfung)} \index{Einschränkung einer Verknüpfung}
    Seien $X$ eine Menge und $*$ eine Verknüpfung auf $X$. Eine Teilmenge $U\subseteq X$ heißt \textbf{abgeschlossen unter der Verknüpfung $*$}, wenn für alle $x,y\in U$ auch $x*y\in U$ ist. In diesem Fall ist durch
        \[ *\vert_U : U\times U \to U \ ,\ (u,v) \mapsto u*v \]
    eine Verknüpfung auf $U$ definiert, die \textbf{Einschränkung von $*$ auf $U$} oder auch die \textbf{von $X$ vererbte Verknüpfung}. Die eingeschränkte Verknüpfung $*\vert_U$ tut dasselbe wie $*$, aber mit dem Unterschied, dass sie nur noch auf Elemente von $U$ angewandt wird.
\end{defin}


\begin{bsp} \quad
    \begin{enumerate}
        \item Die Teilmengen $\N,\Z,\Q\subseteq \R$ sind abgeschlossen unter Addition und Multiplikation. Die Verknüpfungen auf $\N,\Z,\Q$ stimmen überein mit den von $\R$ geerbten Verknüpfungen. Ob ich zwei ganze Zahlen nun in $\Z$ oder in $\R$ multipliziere, macht keinen Unterschied. Die Verknüpfungen auf $\R$ ergeben sich wiederum als Einschränkungen derjenigen von $\C$.
        \item $\Z_{\ge 0}$, $\Q_{\ge 0}$ und $\R_{\ge 0}$ sind abgeschlossen unter Addition und Multiplikation, da Summen und Produkte nichtnegativer Zahlen ebenfalls nichtnegativ sind. Dagegen sind $\Z_{\le 0}$, $\Q_{\le 0}$ und $\R_{\le 0}$ zwar abgeschlossen unter Addition, nicht jedoch unter Multiplikation, da Produkte negativer Zahlen ja positiv sind.
    \end{enumerate}
\end{bsp}


\begin{bem}
    Beachte, dass sich Verknüpfungen, im Gegensatz zu Relationen (siehe \cref{def:einschraenkungrelation}), nicht auf beliebige Teilmengen einschränken lassen, sondern nur auf solche, die abgeschlossen unter der Verknüpfung sind.\footnote{vgl. \cref{einschraenkbarkeit}} Beispielsweise ist die Teilmenge $\N\subseteq \Z$ nicht abgeschlossen unter Subtraktion, sodass sich, wie in \cref{bsp:verknuepfung} besprochen, die Subtraktion nicht von $\Z$ auf $\N$ einschränken lässt.
\end{bem}


\begin{vorschau}[* opposite Verknüpfung]
    Sei $X$ eine Menge. Ganz ähnlich zu \cref{def:umkehrrel} lässt sich für eine Verknüpfung $*$ auf $X$ die \emph{opposite Verknüpfung} $*^\op$ auf $X$ definieren, wobei $x*^\op y:=y*x$ für alle $x,y\in X$. Weil dies für den Rest dieses Kapitels und die Vorlesungen im ersten Semester jedoch selten relevant ist, werde ich hier nicht weiter darauf eingehen. Nichtsdestotrotz werden opposite Verknüpfungen in der Algebra wichtig, indem sie eine ähnliche Dualität wie die aus \cref{ordnungsdualitaet} ermöglichen und eine mächtige Verallgemeinerung besitzen in Gestalt des Dualitätsprinzips der Kategorientheorie.
\end{vorschau}




\section{Assoziativ- und Kommutativgesetz}


\begin{defin} \index{assoziative Verknüpfung} \index{kommutative Verknüpfung}
    Seien $X$ eine Menge und $*$ eine Verknüpfung auf $X$.
    \begin{itemize}
        \item Die Verknüpfung $*$ heißt \textbf{assoziativ}, falls für alle $x,y,z\in X$ das \textbf{Assoziativgesetz} gilt:
            \[ (x*y)*z = x*(y*z) \]
        \item Man sagt, zwei Elemente $x,y\in X$ \textbf{kommutieren}, wenn $x*y=y*x$.
        \item Die Verknüpfung $*$ heißt \textbf{kommutativ}, falls für alle $x,y\in X$ das \textbf{Kommutativgesetz} gilt:
            \[ x*y = y*x \]
        Mit anderen Worten: wenn alle Elemente miteinander kommutieren.
    \end{itemize}
\end{defin}


\begin{bsp}
    Es gilt:
    \begin{enumerate}
        \item Auf $\N,\Z,\Q,\R,\C$ sind die Addition $+$ und die Multiplikation $\cdot$ sowohl assoziativ als auch kommutativ. Denn für alle natürlichen/ganzen/rationalen/reellen/komplexen Zahlen $x,y,z$ gilt bekanntlich
            \[ \begin{split}
                    (x+y)+z& = x+(y+z)  \\
                x+y     & = y+x
                \end{split} \qquad \text{sowie}\qquad \begin{split}
                    (x\cdot y)\cdot z & = x\cdot (y\cdot z)  \\
                    x\cdot y & = y\cdot x
                \end{split} \]
        \item Die Subtraktion auf $\Z,\Q,\R,\C$ ist weder assoziativ noch kommutativ. Beispielsweise ist
        \begin{align*}
            (3-2)-1 &\neq  3-(2-1)  \\
            3-2 &\neq 2-3
        \end{align*}
        \item Die Division auf $\Q\setminus \{0\},\R\setminus \{0\},\C\setminus \{0\}$ ist weder assoziativ noch kommutativ. Beispielsweise ist
        \begin{align*}
            (2:3):2 &\neq 2:(3:2) \\
            2 : 3 & \neq 3:2
        \end{align*}
        \item Das Verketten von Abbildungen ist eine assoziative Verknüpfung auf $\Abb(M,M)$ (für irgendeine Menge $M$). Dies wurde in \cref{abbassoziativ} bewiesen. Im Allgemeinen (nämlich sobald $M$ mindestens zwei verschiedene Elemente enthält) ist sie jedoch nicht kommutativ (vgl. \cref{bsp:verkettung}).
        \begin{proof}
            Die Menge $M$ enthalte mindestens zwei verschiedene Elemente $a,b\in M$. Seien $f_a,f_b\in\Abb(M,M)$ die beiden konstanten Abbildungen, die alles auf $a$ bzw. $b$ schicken. Dann ist $f_a\circ f_b=f_a\neq f_b=f_b\circ f_a$.
        \end{proof}
        \item Ist $M$ eine beliebige Menge, so sind die beiden Verknüpfungen $\cap$ und $\cup$ auf $\calP(M)$ sowohl assoziativ als auch kommutativ. Die Operation $\setminus$ ist aber, sofern $M$ nichtleer ist, weder assoziativ noch kommutativ.
    \end{enumerate}
\end{bsp}


\begin{bsp}[* Rechnen mit Rundungsfehlern] \label{bsp:fehlerrech}
    So gut wie alle Verknüpfungen in den ersten Semestern Mathematikstudium sind assoziativ. Ein für die Informatik wichtiges Beispiel für eine nicht-assoziative Verknüpfung ist die Multiplikation von Computern. Da ein Computer eine Gleitkommazahl nicht mit beliebig vielen Nachkommastellen speichern kann, muss er nach solchen Rechenschritten, die die Anzahl der Nachkommastellen übers Maximum erhöhen würde, die letzte verfügbare Nachkommastelle runden. Für ein vereinfachtes Beispiel betrachte die Menge
        \[ \tfrac{1}{10}\Z := \{ x\in \Q \mid 10x\in \Z \} \]
    all derjenigen rationalen Zahlen, die höchstens eine Nachkommastelle im Dezimalsystem besitzen (Computer würden im Binärsystem rechnen und erheblich mehr Nachkommastellen einbeziehen). Auf dieser Menge ist folgendermaßen eine zweistellige Verknüpfung „$*$“ gegeben:
    \begin{quote}
        Für $a,b\in \frac{1}{10}\Z$ bilde zuerst das gewöhnliche Produkt rationaler Zahlen $a\cdot b \in \Q$. Runde dieses Produkt nun auf die erste Nachkommastelle. Diese gerundete Zahl sei $a*b$.
    \end{quote}
    Es gilt dann beispielsweise:
    \begin{align*}
        1{,}5* 0{,}5 = 0{,}8 \qquad 0{,}1* 0{,}1 = 0 \qquad 2*3 = 6 \qquad 1{,}5 * (-0{,}3)= -0{,}5 
    \end{align*}
    Diese „ungenaue Multiplikation“ ist zwar kommutativ, aber nicht assoziativ, da beispielsweise:
    \begin{align*}
        (0{,}1 * 0{,}1) * 10 & = 0*10 = 0 \\
        0{,}1*(0{,}1*10) & = 0{,}1*1 = 0{,}1
    \end{align*}
\end{bsp}


\begin{bem}[Die eigentliche Bedeutung des Assoziativgesetzes] \label{klammerfrei}
    Sei $X$ eine Menge mit einer assoziativen Verknüpfung $*$. Der Grund dafür, dass das Assoziativgesetz so eine wichtige Rolle spielt, ist, dass bei einer assoziativen Verknüpfung keine Klammern gesetzt werden müssen. Das Assoziativgesetz selbst
    \begin{align*}
        (x*y)*z = x*(y*z) && x,y,z\in X
    \end{align*}
    besagt schonmal, dass bei solchen Termen, die nur drei Elemente involvieren, beide Klammerungen auf dasselbe Ergebnis hinauslaufen. Daher schreibt man einfach
        \[ x*y*z \]
    Mit fortgeschrittenen Techniken lässt sich beweisen, dass bei assoziativen Verknüpfungen sogar in Termen mit beliebig vielen Elementen jede Art von Klammerung auf dasselbe Ergebnis hinausläuft. Beispielsweise gilt für $a,b,c,d,e\in X$:
    \begin{align*}
        (a*(b*c))*(d*e) & =((a*b)*c)*(d*e) && (\text{Assoziativität für $a$, $b$ und $c$})\\
        & = (((a*b)*c)*d)*e && (\text{Assoziativität für $(a*b)*c$, $d$ und $e$})  \\
        & = ((a*b)*(c*d))*e && (\text{Assoziativität für $a*b$, $c$ und $d$})\\
        &=\ \text{usw.}
    \end{align*}
    Daher können bei assoziativen Verknüpfungen ganz allgemein überall die Klammern weggelassen werden. Hier schriebe man schlicht
        \[ a*b*c*d*e \]
    Aus der Schule bist du es ja auch gewohnt, einfach
        \[ 1+3+2+4 \qquad\text{anstelle von}\qquad (1+3)+(2+4)\ \text{oder}\ ((1+3)+2)+4 \]
    zu schreiben und daran ändert sich auch an der Uni nichts. Sind beispielsweise $A,B,C,D$ vier Mengen, so schreibt man schlicht
        \[ A\cup B\cup C \cup D \]
    für deren Vereinigung, was unproblematisch ist, da $\cup$ eine assoziative Verknüpfung ist.

    Sind $\begin{tikzcd}[cramped] A\ar[r, "f"] & B\ar[r, "g"] & C \ar[r, "h"] & D \end{tikzcd}$ drei Abbildungen, so schreibt man
        \[ h\circ g\circ f \]
    für deren Verkettung, wobei auch hier wegen der Assoziativität keine Klammern gesetzt werden müssen.\footnote{vgl. \cref{abbklammerfrei}}
\end{bem}


\begin{bem}[* Rechnen mit Aussagen modulo Äquivalenz]
    Sei $\calA$ die Menge aller mathematischen Aussagen und $\calL$ die Lindenbaum-Algebra aus \cref{bsp:lindenbaum}. Die Junktoren $\land,\lor,\to,\leftrightarrow$ liefern jeweils Verknüpfungen auf $\calA$. Auf dieser syntaktischen Seite sind $\land$ und $\lor$ \emph{nicht} assoziativ. Sie können jedoch künstlich assoziativ gemacht werden per Übergang zur Lindenbaum-Algebra $\calL$. Denn für Aussagen $A,B,C\in \calA$ gelten die Äquivalenzen
        \[ (A\land B)\land C\ \leftrightarrow\ A\land (B\land C)\qquad\text{und}\qquad (A\lor B)\lor C\ \leftrightarrow\ A\lor (B\lor C) \]
    und in $\calL$ werden alle Äquivalenzen zu Gleichheiten, weil es sich per Definition genau um die Faktormenge modulo aussagenlogische Äquivalenz handelt. Auf $\calL$ induzieren $\land$ und $\lor$ assoziative Verknüpfungen, sodass man keine Klammern setzen braucht, wenn man lediglich modulo aussagenlogische Äquivalenz, also in $\calL$, arbeitet.
\end{bem}


\begin{satz}[* Stabilität unter Einschränkung] \label{verknuepfeigstabil}
    Seien $X$ eine Menge, $*$ eine Verknüpfung auf $X$ und $U\subseteq X$ eine Teilmenge, die abgeschlossen unter der Verknüpfung ist. Ist dann $*$ eine assoziative oder kommutative Verknüpfung, so ist es auch ihre Einschränkung $*\vert_U$ auf $U$.
\end{satz}
\begin{proof}
    Bei Assoziativgesetz und Kommutativgesetz
    \begin{align*}
        (x*y)*z & = x*(y*z) && \text{für alle}\ x,y,z\in X \\
        x*y & = y*x && \text{für alle}\ x,y\in X
    \end{align*}
    handelt es sich jeweils um Allaussagen, die für alle Elemente von $X$ gelten. Damit gelten sie dann erst recht auch für alle Elemente der Teilmenge $U$.
\end{proof}





\section{Monoide}


\begin{defin}[Neutrales Element] \label{def:neutrales} \index{neutrales Element}
    Seien $X$ eine Menge und $*$ eine zweistellige Verknüpfung auf $X$. Ein Element $e\in X$ heißt \textbf{neutrales Element}, falls für alle $x\in X$ die beiden folgenden Gleichungen gelten:
    \begin{align*}
        e*x & = x && (\text{$e$ ist linksneutral}) \\
        x*e & = x && (\text{$e$ ist rechtsneutral})
    \end{align*}
\end{defin}


\begin{bsp} \label{bsp:neutrales} \quad
    \begin{enumerate}
        \item Die Addition auf $\R$ hat die Zahl Null als neutrales Element. Denn für jede reelle Zahl $x\in \R$ gilt ja
            \[ 0+x=x \qquad\text{und}\qquad x+0=x \]
        Ebenso ist die Null auch neutrales Element zur Addition auf $\N,\Z,\Q$ und $\C$.
        \item Die Multiplikation auf $\R$ hat die Zahl Eins als neutrales Element. Denn für jede reelle Zahl $x\in \R$ ist
            \[ 1\cdot x = x\cdot 1= x \]
        Ebenso ist die Eins auch neutrales Element zur Multiplikation auf $\N,\Z,\Q$ und $\C$.
        \item Das Verketten von Abbildungen aus $\Abb(M,M)$ hat die Identität $\id_M$ als neutrales Element. Denn in \cref{idneutral} wurde bewiesen, dass für jede Abbildung $M\xrightarrow{f} M$ gilt:
            \[ f\circ \id_M = f \qquad\text{und}\qquad \id_M \circ f = f \]
        \item Sei $M$ eine beliebige Menge. Bezüglich der Verknüpfung $\cap$ hat $\calP(M)$ das neutrale Element $M$. Denn es gilt:
        \begin{align*}
            M\cap A & = A\cap M = A && \text{für jede Teilmenge}\ A\subseteq M
        \end{align*}
        \item Bezüglich der Verknüpfung $\cup$ hat $\calP(M)$ das neutrale Element $\emptyset$. Denn es gilt:
        \begin{align*}
            \emptyset\cup A & = A\cup \emptyset = A && \text{für jede Teilmenge}\ A\subseteq M
        \end{align*}
        \item Die fehlerbehaftete Multiplikation aus \cref{bsp:fehlerrech} hat die $1$ als neutrales Element. Denn wenn ich eine rationale Zahl, die höchstens eine Nachkommastelle besitzt, mit $1$ multipliziere, ändert sich nichts, sodass auch das nachfolgende Runden nichts am Zahlenwert ändert.
        \item Hinsichtlich der Subtraktion auf $\Z,\Q,\R$ bzw. $\C$ ist die Null zwar rechtsneutral, da $x-0=x$ für jede Zahl $x$ gilt. Sie ist jedoch kein neutrales Element, denn wegen beispielsweise $0-7\neq 7$ ist sie nicht linksneutral. Zur Subtraktion kann es sogar kein neutrales Element geben: denn wäre $e$ ein neutrales Element, so gälte
            \[ 0-4 = (e-0)-4 = e-4 = 4 \]
        was nicht sein kann.
        \item Hinsichtlich der Division auf $\Q\setminus \{0\},\R\setminus \{0\},\C\setminus \{0\}$ gibt es ebenfalls kein neutrales Element.
    \end{enumerate}
\end{bsp}


\begin{satz}[Eindeutigkeit neutraler Elemente] \label{neutreind}
    Seien $X$ eine Menge und $*$ eine Verknüpfung auf $X$. Sofern $X$ bezüglich $*$ ein neutrales Element enthält, ist dieses eindeutig bestimmt.
\end{satz}
\begin{proof}
    Es seien $d,e\in X$ zwei neutrale Elemente bezüglich der Verknüpfung $*$. Dann gilt:
    \begin{align*}
        d & = d*e && (\text{weil $e$ neutrales Element}) \\
        & = e && (\text{weil $d$ neutrales Element}) && \qedhere
    \end{align*}
\end{proof}


\begin{bem}[\textbf{Das} neutrale Element]
    Der Eindeutigkeitssatz berechtigt uns, beim Vorhandensein eines neutralen Elements statt von „einem neutralen Element“ von \emph{dem} neutralen Element zu reden.\footnote{vgl. \cref{kennzeichnung}}
    
    An diesem Satz wird vielleicht deutlich, wie vorteilhaft die axiomatische Arbeit mit abstrakten Verknüpfungen sein kann. Denn er garantiert uns auf einen Schlag, dass alle neutralen Elemente aus \cref{bsp:neutrales} auch jeweils die einzigen neutralen Elemente sind, ohne dass wir dies in jedem Fall einzeln beweisen müssten.
\end{bem}


\begin{defin}[Monoid] \index{Monoid}
    Ein \textbf{Monoid} ist ein Paar $(M,*)$ bestehend aus einer Menge $M$ und einer Verknüpfung $*$ auf $M$, für das gilt:
    \begin{labeling}[(M1), labelindent=1.5em]
        \item $*$ ist eine assoziative Verknüpfung.
        \item $M$ enthält ein neutrales Element (bezüglich der Verknüpfung $*$).
    \end{labeling}
    In diesem Fall ist das neutrale Element nach \cref{neutreind} automatisch eindeutig bestimmt.
    
    Ist überdies die Verknüpfung $*$ auch noch kommutativ, so heißt $(M,*)$ ein \textbf{kommutatives Monoid}.
\end{defin}


\begin{bsp} Es gilt:
    \begin{enumerate}
        \item $(\N_0,+),(\Z,+),(\Q,+),(\R,+),(\C,+)$ sind jeweils kommutative Monoide. Denn die Addition ist assoziativ und kommutativ und die Zahl $0$ ist ihr neutrales Element.
        \item $(\N,\cdot),(\Z,\cdot),(\Q,\cdot),(\R,\cdot),(\C,\cdot)$ sind jeweils kommutative Monoide. Denn die Multiplikation ist assoziativ und kommutativ und die Zahl $1$ ist ihr neutrales Element.
        \item Die Subtraktion und die Division liefern keine Monoide, weil sie nicht assoziativ sind. Und ein neutrales Element besitzen sie ja auch nicht.
        \item Ist $M$ eine beliebige Menge, so ist $(\Abb(M,M),\circ)$ ein Monoid mit neutralem Element $\id_M$. Sofern $M$ mindestens zwei verschiedene Elemente enthält, ist es aber nicht kommutativ.
        \item Ist $M$ eine beliebige Menge, so sind $(\calP(M),\cup)$ und $(\calP(M),\cap)$ zwei kommutative Monoide mit den jeweiligen neutralen Elementen $\emptyset$ und $M$.
        \item Die „fehlerbehaftete Multiplikation“ aus \cref{bsp:fehlerrech} besitzt zwar ein neutrales Element -- sie liefert aber kein Monoid, weil sie nicht assoziativ ist.
        \item Die Addition „$+$“ ist zwar eine assoziative Verknüpfung auf der Menge $\N_{\ge 1}$, aber $(\N_{\ge 1},+)$ ist kein Monoid, da es kein neutrales Element enthält.
    \end{enumerate}
\end{bsp}


\begin{bem}[Trägermenge]
    Beachte, dass ein Monoid immer ein Paar $(M,*)$ ist, in das sowohl die „Trägermenge“ $M$ als auch die Verknüpfung $*$ hineinkodiert sind. Ein und dieselbe Menge kann durchaus als Trägermenge für verschiedene Monoide herhalten. Beispielsweise sind $(\N_0,+)$ und $(\N_0,\cdot)$ zwei verschiedene Monoide, die dennoch dieselbe Trägermenge $\N_0$ besitzen.
    
    Andererseits gibt es Mengen mit „kanonischen“ Verknüpfungen, wie z.B. $\Abb(X,X)$ (wobei $X$ irgendeine Menge ist). Sprechen Mathematiker von „dem Monoid $\Abb(X,X)$“, so meinen sie damit grundsätzlich das Monoid $(\Abb(X,X),\circ)$, also $\Abb(X,X)$ mit der Verkettung von Abbildungen als Verknüpfung. Solche Konventionen wirst du mit der Zeit durch Erfahrung und Gewohnheit verinnerlichen.
    
    Ist im Kontext klar oder gleichgültig, von welcher Verknüpfung die Rede ist, so spricht man abkürzend meist nur von „dem Monoid $M$“.
\end{bem}


\begin{bem}[Die eigentliche Bedeutung des Kommutativgesetzes] \label{reihenfolgeegal}
    Es sei $(M,*)$ ein kommutatives Monoid. Weil dann $*$ assoziativ ist, brauchen wir nach \cref{klammerfrei} keine Klammern setzen. Sind beispielsweise $a,b,c,d\in M$, so können wir einfach $a*b*c*d$ schreiben. Das Kommutativgesetz
    \begin{align*}
        x*y&=y*x && \text{für alle}\ x,y\in M \\
    \intertext{sagt aus, dass es bei der Verknüpfung zweier Elemente nicht auf die Reihenfolge ankommt. Es lässt sich zeigen, dass es sogar bei der Verknüpfung beliebig vieler Elemente nicht auf die Reihenfolge ankommt. Beispielsweise gilt}
        a*b*c*d & = a*c*b*d && (\text{Kommutativgesetz für $b$ und $c$}) \\
        & = c*a*b*d && (\text{Kommutativgesetz für $a$ und $c$}) \\
        & = b*d*c*a && (\text{Kommutativgesetz für $c*a$ und $b*d$}) \\
        & \text{usw.}
    \end{align*}
    Bei Verknüpfungen, die sowohl assoziativ als auch kommutativ sind, brauchst du weder aufs Klammernsetzen, noch auf die Reihenfolge, in der du die Elemente verknüpfst, achten.
\end{bem}


\begin{defin}[Inverse Elemente] \label{def:inverse} \index{inverses Element} \index{Einheit (bei einer Verknüpfung)}
    Sei $X$ eine Menge mit einer zweistelligen Verknüpfung $*$, die ein (nach \cref{neutreind} automatisch eindeutig bestimmtes) neutrales Element $e$ besitzt und sei $a\in X$. Ein Element $b\in X$ heißt \textbf{invers} zu $a$, falls es die folgenden beiden \emph{Inversengleichungen} erfüllt:
    \begin{align*}
        a*b & = e && (\text{„$b$ ist rechtsinvers zu $a$“}) \\
        b*a & = e && (\text{„$b$ ist linksinvers zu $a$“})
    \end{align*}
    Das Element $a$ heißt \textbf{invertierbar} (oder auch: \textbf{Einheit}\footnote{Die Analogie zum Einheitenbegriff aus der Physik (Meter, Kilogramm, \dots) besteht darin, dass in einem Monoid jedes Element ein „Vielfaches“ einer jeder Einheit ist (im Sinne einer Teilbarkeitsrelation wie in \cref{bsp:relation}), so wie etwa jede Länge als Vielfache der Einheit „Meter“ angegeben werden kann.}), falls es ein zu $a$ inverses Element in $X$ gibt.
\end{defin}


\begin{bem}[Keine Inversen ohne Neutrales]
    Beachte, dass es nur bei Vorhandensein eines neutralen Elements überhaupt Sinn ergibt, von inversen Elementen zu sprechen. 
\end{bem}


\begin{bsp} \label{bsp:inverse}
    Es gilt:
    \begin{enumerate}
        \item In den Monoiden $(\Z,+),(\Q,+),(\R,+),(\C,+)$ ist jedes Element invertierbar. Denn für jede ganze/rationale/reelle/komplexe Zahl $x$ gilt
        \begin{align*}
            x + (-x) & = 0 \\
            (-x) + x & = 0
        \end{align*}
        sodass $-x$ invers zu $x$ ist.
        \item Das einzige invertierbare Element im Monoid $(\N_0,+)$ ist die $0$, da $0+0=0$. Für jede andere Zahl $n\in \N_{\ge 1}$ kann es kein $m\in \N_0$ mit $n+m=0$ geben.
        \item In den Monoiden $(\Q,\cdot),(\R,\cdot),(\C,\cdot)$ ist jedes Element $\neq 0$ invertierbar. Denn für jede rationale/reelle/komplexe Zahl $x\neq 0$ gilt
        \begin{align*}
            x \cdot \frac{1}{x} & = 1 \\
            \frac{1}{x}\cdot x & = 1
        \end{align*}
        sodass $\frac{1}{x}$ invers zu $x$ ist. Die Null ist dagegen nicht invertierbar. Denn für jede beliebige Zahl $x$ ist $0\cdot x = 0\neq 1$, sodass $x$ nicht invers zur $0$ sein kann.
    \end{enumerate}
\end{bsp}


\begin{bsp}[*]
    In \cref{bsp:umkehrabb} wurden Abbildungen $f,g:\N\to \N$ beschrieben, für die zwar $g\circ f=\id_\N$ gilt, jedoch $f\circ g\neq \id_\N$. Beispielsweise:
    \begin{align*}
        f : \N_0 \to \N_0 \ &,\ n \mapsto n+1 & g: \N_0 \to \N_0 \ &,\ n\mapsto \begin{cases} n-1 & n\ge 1 \\ 0 & n=0 \end{cases}
    \end{align*}
    Im Monoid $\Abb(\N_0,\N_0)$ ist dann $g$ linksinvers zu $f$, jedoch nicht rechtsinvers. Tatsächlich kann es zu $f$ gar keine inverse Abbildung geben, da $f$ wegen $0\notin \im(f)$ nicht surjektiv, also erst recht nicht bijektiv, ist.

    Dieses Beispiel zeigt, dass im Allgemeinen nicht aus der Gültigkeit einer der beiden Inversengleichungen schon auf die andere geschlossen werden kann.\footnote{Manche Autoren nennen ein Monoid „\href{https://en.wikipedia.org/wiki/Dedekind-finite_ring}{von-Neumann-endlich}“, wenn jedes linksinverse Element auch bereits rechtsinvers ist (und umgekehrt). Wichtigstes Beispiel dafür in der LA1 werden \emph{Matrizenringe} wie $\R^{n\times n}$ sein.}
\end{bsp}


\begin{satz}[Eindeutigkeit inverser Elemente] \label{inveind}
    Seien $(M,*)$ ein Monoid und $a\in M$ ein invertierbares Element. Dann ist das inverse Element von $a$ eindeutig bestimmt.\footnote{vgl. \cref{umkehreind}}
\end{satz}
\begin{proof}
    Es seien $e\in M$ das neutrale Element von $M$ und $b,c\in M$ zwei beliebige Inverse zu $a$. Dann gilt:
    \begin{align*}
        b & = b*e && (\text{da $e$ neutral ist}) && \\
        & = b* a*c && (\text{da $c$ invers zu $a$ ist}) && \\
        & = e*c && (\text{da $b$ invers zu $a$ ist}) && \\
        & = c && (\text{da $e$ neutral ist}) && \qedhere
    \end{align*}
\end{proof}


\begin{nota}[\textbf{Das} inverse Element] \label{dasinverse}
    Seien $(M,*)$ ein Monoid und $a\in M$ ein invertierbares Element. Da dann $a$ auch nur genau ein Inverses besitzt, ergibt es Sinn, anstelle von „einem Inversen zu $a$“ von \emph{dem} Inversen von $a$ zu sprechen, vgl. \cref{kennzeichnung}. Im Folgenden werde ich das Inverse eines invertierbaren Monoidelements $a$ mit „$a^\inv$“ notieren:
    \begin{align*}
         a^\inv := (\text{Das Inverse von $a$}) && (\text{sofern $a$ invertierbar ist})
    \end{align*}
    Diese Schreibweise ist in der Literatur allerdings unüblich, stattdessen wird meist „$a^{-1}$“ geschrieben, siehe \cref{def:potenz}.
\end{nota}


\begin{bem}[*]
    Beachte, dass ich im Beweis von \cref{inveind} implizit Gebrauch vom Assoziativgesetz gemacht habe (erkennst du, wo?). Bei einer nicht-assoziativen Verknüpfung wie z.B. der fehlerbehafteten Multiplikation aus \cref{bsp:fehlerrech}, die sowohl kommutativ ist als auch ein neutrales Element besitzt, brauchen Inverse nicht eindeutig sein. Beispielsweise gilt dort
    \begin{align*}
        0{,}4 * 2{,}5 & = 1 \\
        0{,}4 * 2{,}6 & = 1
    \end{align*}
    sodass das Element $0{,}4$ mindestens zwei verschiedene Inverse besitzt, nämlich $2{,}5$ und $2{,}6$.
\end{bem}


\begin{satz}[Rechenregeln für inverse Elemente] \label{regelnfuerinv} \index{Involution}
    Sei $(M,*)$ ein Monoid mit neutralem Element $e\in M$. Dann gilt:
    \begin{enumerate}
        \item Das neutrale Element ist invertierbar und es ist $e^\inv = e$.\footnote{Elemente, die invers zu sich selbst sind, heißen \textbf{selbstinvers} oder \textbf{involutorisch}.}
        \item Ist $a\in M$ ein invertierbares Element, so ist auch $a^\inv$ invertierbar und es ist
            \[(a^\inv)^\inv = a \]
        \item(Regel von Hemd und Jacke) Sind $a,b\in M$ zwei invertierbare Elemente, so ist auch $a*b$ invertierbar und es ist
            \[ (a*b)^\inv = b^\inv * a^\inv \]
    \end{enumerate}
\end{satz}
\begin{proof}
    \begin{enumerate}
        \item Da $e$ ein neutrales Element ist, gilt $e*e=e$. Diese Gleichung entspricht beiden Inversengleichungen aus \cref{def:inverse} zugleich.
        \item Da $a^\inv$ invers zu $a$ ist, gelten die beiden Gleichungen
            \[ a*a^\inv = e \qquad\text{und}\qquad a^\inv * a=e \]
        Die erste dieser Gleichungen besagt, dass $a$ linksinvers zu $a^\inv$ ist, und die zweite Gleichung besagt, dass $a$ rechtsinvers zu $a^\inv$ ist. Insgesamt ist also $a$ invers zu $a^\inv$.
        \item Es gilt
        \begin{align*}
            \begin{split}
                a*b* b^\inv *a^\inv  & =  a*e*a^\inv \\
                & = a*a^\inv \\
                & = e
            \end{split} & \text{sowie}\qquad \begin{split}
                b^\inv *a^\inv * a*b  & =  b^\inv * e* b \\
                & = b^\inv * b \\
                & = e
            \end{split}
        \end{align*}
        Insgesamt erfüllt $b^\inv *a^\inv$ somit beide Inversengleichungen. \qedhere
    \end{enumerate}
\end{proof}


\begin{bem} \index{Regel von Hemd und Jacke}
    Die letzte Aussage heißt „Regel von Hemd und Jacke“ aufgrund folgender Analogie: Habe ich mir erst ein Hemd und daraufhin eine Jacke angezogen und möchte ich mich nun wieder entkleiden, so muss ich zuerst die Jacke und dann das Hemd ausziehen. -- Beim Invertieren dreht sich die Reihenfolge um.
\end{bem}





\section{Mehr Notation}


\begin{nota}[additive und multiplikative Notation] \index{Summand} \index{Faktor}
    Zur Notation von Verknüpfungen gibt es zwei Standard-Schemata:
    \begin{itemize}
        \item Eine \textbf{additiv geschriebene Verknüpfung} ist eine Verknüpfung, die mit dem Zeichen „$+$“ notiert wird. Im Ausdruck
            \[ a + b\]
        heißen $a,b$ die \textbf{Summanden} und $a+b$ die \textbf{Summe}.
        
        In der Algebra herrscht die Konvention vor, \emph{ausschließlich kommutative Verknüpfungen additiv zu schreiben}, weshalb du nichtkommutative Verknüpungen mit anderen Zeichen notieren solltest.
        \item Eine \textbf{multiplikativ geschriebene Verknüpfung} ist eine Verknüpfung, die mit dem Malpunkt „$\cdot$“ notiert wird. Im Ausdruck
            \[ a\cdot b \]
        heißen $a,b$ die \textbf{Faktoren} und $a\cdot b$ das \textbf{Produkt}. Oft wird in diesem Fall auch gar kein Verknüpfungssymbol aufgeschrieben: man schreibt dann „$ab$“ anstelle von „$a\cdot b$“, so wie du es aus der Schule von der Multiplikation zweier Zahlvariablen kennst.
    \end{itemize}
    „Additiv geschrieben“ und „multiplikativ geschrieben“ sind keine mathematischen Eigenschaften einer Verknüpfung, sondern nur Eigenarten der Notation. Prinzipiell ließe sich jede Verknüpfung additiv oder multiplikativ schreiben.
\end{nota}


\begin{nota}[Null- und Einselement] \index{Nullelement} \index{Einselement}
    Sei $X$ eine beliebige Menge. Ist $+$ eine additiv geschriebene Verknüpfung auf $X$, die ein neutrales Element enthält, so wird dieses in der Regel mit „$0$“ notiert und das \textbf{Nullelement} von $X$ genannt. Per Definition gilt
    \begin{align*}
        0 + x = x \qquad & \text{und}\qquad x+0= x && \text{für alle}\ x\in X \\
    \intertext{Ist dagegen „$\cdot$“ eine multiplikativ geschriebene Verknüpfung auf $X$, die ein neutrales Element enthält, so wird dieses oft mit „$1$“ notiert und das \textbf{Einselement} von $X$ genannt. Per Definition gilt}
        1 \cdot x = x \qquad & \text{und}\qquad x\cdot 1= x && \text{für alle}\ x\in X
    \end{align*}
    Um zu betonen, dass es sich um das Null- bzw. Einselement von $X$ und nicht etwa um die natürliche Zahl Null bzw. Eins handelt, schreibt man auch
    \[ 0_X \qquad\text{bzw.}\qquad 1_X \]
    Beachte, dass Null- und Einselemente im Allgemeinen nichts mit den herkömmlichen Zahlen Null und Eins zu tun haben müssen! Wir bedienen uns lediglich desselben Zeichens.
\end{nota}


\begin{nota}[Differenzen] \label{differenz}
    Seien $(M,+)$ ein additiv geschriebenes Monoid und $a\in M$ ein invertierbares Element. Das Inverse von $a$ wird dann notiert mit
    \begin{align*}
        -a & := a^\inv && (\text{bei einer additiv geschriebenen Verknüpfung})
    \end{align*}
    Für ein weiteres Element $b\in M$ schreibt man
        \[ b-a \qquad\text{anstelle von}\qquad b + (-a) \]
    und spricht von der \textbf{Differenz} von $b$ und $a$. Die Inversengleichungen nehmen mit dieser Notation die folgende Gestalt an:
        \[ a-a = 0 \qquad\text{und}\qquad -a+a = 0 \]
    wobei die zweite Gleichung redundant ist, wenn $+$ als kommutativ vorausgesetzt wird.
    
    Bei Termen mit Summen und Differenzen mehrerer Elemente $a_1,\dots , a_n\in M$ lässt man die Klammern in der Regel weg unter der stillschweigenden Vereinbarung, die Terme „linksassoziativ“ zu interpretieren:
        \[ a_1 \pm a_2\pm a_3\pm\ldots\pm a_n := (((a_1\pm a_2)\pm a_3) \pm \ldots ) \pm a_n\]
    Beispielsweise ist der Term $8-3-1$ zu lesen als $(8-3)-1$ und nicht etwa als $8-(3-1)$.
\end{nota}


\begin{bem}
    Während in der Schule vielleicht Addition und Subtraktion noch als gleichberechtigte „Grundrechenarten“ nebeneinander stehen, wird in der Uni-Mathematik die Addition als vorrangige Verknüpfung verstanden und die Subtraktion aus ihr abgeleitet. Ebenso verhält es sich mit Multiplikation und Division, vgl. \cref{brueche}.
\end{bem}


\begin{defin}[* Potenzen] \label{def:potenz} \index{Potenz} \index{Exponent}
    Seien $M$ eine Menge mit einer assoziativen Verknüpfung $*$ und $a\in M$ irgendein Element. Für ein $n\in \N_{\ge 1}$ heißt das Element, das durch $n$-faches Verknüpfen von $a$ mit sich selbst entsteht
    \[ a^n := \underbrace{a * \ldots * a}_{n\text{-mal}} \]
    die \textbf{$n$-te Potenz von $a$}. Dabei heißen $a$ die \textbf{Basis} und $n$ der \textbf{Exponent}. Manchmal wird auch das Verknüpfungszeichen mit in den Exponenten geschrieben:
            \[ a^{*n} := \underbrace{a * \ldots * a}_{n\text{-mal}} \]
    Sofern $M$ ein neutrales Element $e$ enthält, setzt man die nullte Potenz auf ebendieses:\footnote{Damit ist vom algebraischen Standpunkt auch die Frage nach „\href{https://en.wikipedia.org/wiki/Zero_to_the_power_of_zero}{Null hoch Null}“ beantwortet. In $\C,\R,\Q,\Z,\N_0$ gilt nach der allgemeinen Definition $0^0=1$, da die Eins das neutrale Element zur Multiplikation ist.}
        \[ a^0 := e \]
    Ist überdies auch noch $a$ ein invertierbares Element, so lassen sich auch negative Potenzen definieren. Für $n\in \Z$ ist dann die $n$-te Potenz von $a$ definiert als:
    \begin{align*}
        a^n := \begin{cases}
            \underbrace{a* \ldots * a}_{n\text{-mal}} & n \ge 1 \\
            e & n= 0 \\
            \underbrace{a^\inv * \ldots * a^\inv}_{(-n)\text{-mal}} & n \le -1
        \end{cases}
    \end{align*}
    Insbesondere ist $a^{-1}=a^\inv$ das Inverse von $a$. In der Literatur werden inverse Elemente in Monoiden standardmäßig mit „$a^{-1}$“ notiert.
\end{defin}

    
\begin{nota}[*]
    Im additiv geschriebenen Fall bedient man sich jedoch einer anderen Schreibweise. Sei $+$ eine additiv geschriebene, assoziative Verknüpfung auf der Menge $M$. Für $a\in M$ und $n\in \N_{\ge 1}$ wird dann die $n$-te Potenz von $a$ notiert mit
        \[ n \cdot a := \underbrace{a + \ldots + a}_{n\text{-mal}} \]
    Man spricht hier auch nicht von einer „$n$-ten Potenz“ von $a$, sondern vom \textbf{$n$-fachen von $a$}. Sofern $M$ ein Nullelement enthält, ist
        \[ 0\cdot a := 0_M \]
    Ist überdies $a$ invertierbar, so sind auch die negativen Vielfachen definiert: für $n\in \Z$ ist
    \begin{align*}
        n \cdot a := \begin{cases}
            \underbrace{a+ \ldots + a}_{n\text{-mal}} & n \ge 1 \\
            0_M & n= 0 \\
            \underbrace{(-a) + \ldots +  (-a)}_{(-n)\text{-mal}} & n \le -1
        \end{cases}
    \end{align*}
    Bei diesen Festlegungen handelt es sich um das Gleiche wie in \cref{def:potenz}, nur in einer anderen Schreibweise.
\end{nota}


\begin{satz}[* Potenzgesetze] \label{potenzgesetze}
    Seien $M$ eine Menge mit einer assoziativen Verknüpfung $*$ und $a,b\in M$ zwei miteinander kommutierende Elemente. Für $m,n\in \N_{\ge 1}$ gelten die folgenden Potenzgesetze:
    \begin{align*}
        a^1 & = a \\
        a^{m+n} & = a^m* a^n \\
        (a^n)^m & = a^{m\cdot n} \\
        (a*b)^n &= a^n*b^n && (\textnormal{sofern $a*b=b*a$})
    \end{align*}
    Sofern $M$ ein neutrales Element enthält, gelten diese Gleichungen auch für $m,n=0$, und sofern überdies $a,b$ invertierbar sind, auch für $m,n\in \Z$.\footnote{Es lässt sich zeigen, dass die Definition negativer Potenzen die einzig mögliche Definition ist, mit der die Potenzgesetze allgemein auch für ganzzahlige Exponenten gültig sind.}
\end{satz}
Beachte, dass für die letzte Gleichung wichtig ist, dass $a,b$ miteinander kommutieren. In nichtkommutativen Monoiden wird im Allgemeinen $(ab)^2=abab\neq a^2b^2$ sein.
\begin{proof}
    Die Potenzgesetze können rigoros mit einem \href{https://de.wikipedia.org/wiki/Vollst\%C3\%A4ndige_Induktion}{Induktionsbeweis} bewiesen werden. Da diese Beweistechnik in diesem Skript nicht behandelt wird, könntest du noch abwarten, bis sie in den ersten beiden Semesterwochen durchgenommen wurde, und daraufhin nochmal hierher zurückkehren.
\end{proof}


\begin{bem}[*] \label{brueche}
    Sei $M$ ein Monoid. In \cref{potenzgesetze} habe ich die Potenzgesetze multiplikativ notiert. Hier ist eine Gegenüberstellung der Regeln aus \cref{regelnfuerinv} und \cref{potenzgesetze} in multiplikativer und additiver Schreibweise:
    \begin{center}
    \begin{tabular}{ccl}
        Multiplikative Notation & Additive Notation & $a,b\in M$,\ $m,n\in \N_0$\\
        \midrule
        $1^{-1} = 1$ & $-0=0$ & \\
        $(a^{-1})^{-1} = a$ & $-(-a)=a$ & (sofern $a$ invertierbar) \\
        $(a\cdot b)^{-1} = b^{-1}\cdot a^{-1}$ & $-(a+b) = -a - b$ & (sofern $a,b$ invertierbar) \\
        $a^0 = 1$ & $0\cdot a = 0$ & \\
        $a^1 = a$ & $1\cdot a=a$ &\\
        $a^{m+n} = a^m\cdot a^n$ & $(m+n)\cdot a = m\cdot a + n\cdot a$ & \\
        $(a^n)^m = a^{m\cdot n}$ & $m\cdot (n\cdot a) = (m\cdot n)\cdot a$ & \\
        $(a\cdot b)^n =a^n\cdot b^n$ & $n\cdot (a+b) = n\cdot a+n\cdot b$ & (sofern $a\cdot b=b\cdot a$)
    \end{tabular}
    \end{center}
    wobei ich im additiven Fall voraussetze, dass $+$ kommutativ ist. In beiden Spalten der Tabelle stehen letztendlich dieselben Regeln, nur anders notiert.
\end{bem}


\begin{nota}[* Bruchschreibweise] \index{Zaehler@Zähler} \index{Nenner}
    Sei $M$ ein multiplikativ geschriebenes \emph{kommutatives} Monoid. Für $a\in M$ und ein invertierbares Element $u\in M$ gibt es die Schreibweise
        \[ \frac{a}{u} := a\cdot u^{-1} = u^{-1} \cdot a\]
    Hierbei heißen $a$ der \textbf{Zähler} und $u$ der \textbf{Nenner}. Für diese Notation ist es essenziell, dass $M$ kommutativ ist. Denn andernfalls könnten die beiden Elemente $au^{-1}$ und $u^{-1}a$ durchaus verschieden sein und man müsste zwischen „Links- und Rechtsbrüchen“ unterscheiden.
    
    Ebenso dürfen erstmal nur invertierbare Elemente in die Nenner geschrieben werden; beispielsweise gibt es in $\Q$ keine Zahl der Gestalt „$\frac{4}{0}$“. In der abstrakten Algebra werden jedoch Methoden entwickelt, mit denen auch vormals nicht invertierbare Elemente künstlich invertierbar gemacht und in Nenner geschrieben werden können, vgl. \cref{gruppenvervollstaendigung}.
\end{nota}


\begin{bem}[* Rechenregeln für Brüche]
    Mit Brüchen in kommutativen Monoiden lässt sich rechnen, wie du es aus der Schule gewohnt bist. Wenn du in Stimmung bist, versuche einmal herzuleiten, dass für alle $n\in \N_0$, $a,b\in M$ und alle invertierbaren Elemente $u,v,w\in M$ die folgenden Rechenregeln gelten:
    \begingroup
    \allowdisplaybreaks
    \begin{align*}
    \frac{a}{u}\cdot \frac{b}{v} & = \frac{ab}{uv} & \frac{a}{u}=\frac{b}{v}\ & \Leftrightarrow\ av=bu & a\cdot \frac{b}{u} & = \frac{ab}{u} = \frac{a}{u}\cdot b \\[0.5em]
    \frac{a}{1} & = a & \frac{1}{u} & = u^{-1} & \frac{u}{u} & = 1 \\[0.5em]
    \frac{au}{vu} & = \frac{a}{v} & \left(\frac{a}{u}\right)^n & = \frac{a^n}{u^n} & \left(\frac{u}{v}\right)^{-1} & = \frac{v}{u} \\[0.5em]
    \frac{\frac{a}{u}}{v} & = \frac{a}{uv} & \frac{a}{\frac{u}{v}} & = \frac{av}{u} & \frac{\frac{a}{u}}{\frac{v}{w}} & = \frac{aw}{uv}
    \end{align*}
    \endgroup
\end{bem}


\begin{nota}[Mehrfachprodukte] \label{mehrfachprodukt} \index{Leere Summe} \index{Leeres Produkt}
    Sei $M$ eine Menge mit einer assoziativen Verknüpfung $*$. Für $m,n\in \N$ mit $m\le n$ und $a_m,\dots , a_n\in M$ schreibt man
        \[ \mathop{\raisebox{-0.6ex}{\scalebox{2.5}{$*$}}}_{k=m}^n a_k := a_m * \ldots * a_n \]
    für die Verknüpfung der $a_m,\dots , a_n$ in aufsteigender Reihenfolge. Beachte, dass auf der rechten Seite keine Klammern gesetzt werden müssen, weil $*$ assoziativ ist, vgl. \cref{klammerfrei}. Es heißen
    \begin{itemize}
        \item $k$ die \textbf{Laufvariable}.\footnote{Es handelt sich um eine \emph{gebundene Variable} im Sinne von \cref{gebundenevariable}.}
        \item $m$ der \textbf{Startwert} der Laufvariable.
        \item $n$ der \textbf{Endwert} der Laufvariable.
    \end{itemize}
    Die Laufvariable kann auch allgemeinere Werte durchlaufen, wie etwa ganze Zahlen oder Elemente einer beliebigen totalgeordneten Menge.
    
    Für additiv und multiplikativ geschriebene Verknüpfungen gibt es Sonderzeichen:
    \begin{itemize}
        \item Bei einer additiv geschriebenen Verknüpfung bedient man sich eines großen Sigma $\Sigma$ (abkürzend für „Summe“):
            \[ \sum_{k=m}^n a_k := a_m + \ldots + a_n \]
        \item Bei einer multiplikativ geschriebenen Verknüpfung bedient man sich eines großen Pi $\Pi$ (abkürzend für „Produkt“):
            \[ \prod_{k=m}^n a_k := a_m \cdot \ldots \cdot a_n \]
    \end{itemize}
    Falls $M$ ein neutrales Element $e$ zur Verknüpfung $*$ enthält, sind Mehrfachprodukte auch für den Fall $m>n$, also falls es gar keine Indizes zwischen Start- und Endwert der Laufvariable gibt, erklärt. In diesem Fall ist
    \begin{alignat*}{2}
        & \mathop{\raisebox{-0.6ex}{\scalebox{2.5}{$*$}}}_{k=m}^n a_k := e && (\text{falls $m>n$}) \\
        \intertext{das neutrale Element. Bei additiv oder multiplikativ geschriebenen Verknüpfungen gilt dementsprechend}
        & \sum_{k=m}^n a_k = 0 \qquad\text{bzw.}\qquad && \prod_{k=m}^n a_k = 1 \qquad\qquad (\text{falls $m>n$})
    \end{alignat*}
    Man spricht von der \textbf{leeren Summe} und vom \textbf{leeren Produkt}.
    
    Ist überdies $M$ ein \emph{kommutatives} Monoid, so können Mehrfachprodukte über beliebige Familien mit endlichen Indexmengen gebildet werden: Ist $I$ eine Menge, die nur endlich viele Elemente enthält, und ist $(a_i)_{i\in I}$ eine durch $I$ indizierte Familie von Elementen aus $M$, so bezeichnet
        \[ \mathop{\raisebox{-0.6ex}{\scalebox{2.5}{$*$}}}_{i\in I} a_i \qquad\text{bzw. im additiven Fall:}\quad \sum_{i\in I} a_i \qquad\text{bzw. im multiplikativen Fall:}\quad \prod_{i\in I} a_i\]
    die Verknüpfung der $a_i$'s in einer beliebigen (irrelevanten, da $*$ kommutativ ist\footnote{vgl. \cref{reihenfolgeegal}}) Reihenfolge.
\end{nota}


\begin{bsp} \quad
    \begin{enumerate}
        \item(Binomischer Lehrsatz\footnote{\href{https://www.youtube.com/watch?v=462dkfAvlGo}{Francesco Binomi (1369-1420)}}) Für $x,y,n\in \N$ gilt:
            \[ (x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k}\cdot y^k \]
        wobei der \emph{Binomialkoeffizient} $\binom{n}{k}$ die Anzahl aller Möglichkeiten, aus $n$-vielen Gegenständen ohne Berücksichtigung der Reihenfolge genau $k$-viele auszuwählen, bezeichnet. Im Spezialfall $n=2$ ergibt sich die aus der Schule bekannte binomische Formel $(x+y)^2=x^2+2xy+y^2$.
        \item Die Notation für Mehrfachprodukte kennst du bereits aus \cref{chap:mengen}, wo sie für Durchschnitte, (disjunkte) Vereinigungen und Produkte von Mengen vorgestellt wurde, siehe etwa \cref{alternativmehrfachcapcup}.
        \item(„Unendliche“ Mehrfachprodukte?) In der Welt der zweistelligen Verknüpfungen, also dieses Kapitels, ist es nicht ohne Weiteres möglich, auch Verknüpfungen unendlich vieler Elemente zugleich zu definieren. Hierzu wären \emph{infinitäre Verknüpfungen} (d.h. Verknüpfungen, die unendlich viele Elemente entgegennehmen) oder Zusatzstruktur, wie z.B. eine \emph{Topologie}, nötig. Schon in der Ana1 können, aufbauend auf dem Begriff der \emph{Konvergenz}\footnote{siehe \cref{def:konvergenz}}, „unendliche Summen“ studiert werden. Beispielsweise gilt für jede Zahl $q\in \C$ mit $\vert q\vert < 1$:\footnote{vgl. \cref{aufg:geometrischereihe}}
            \[ \sum_{k=0}^\infty q^k = 1 + q + q^2 + q^3 + \ldots = \frac{1}{1-q} \]
        Der Ausdruck „$\sum_{k=0}^\infty$“ ist allein mit den Werkzeugen aus diesem Kapitel \emph{nicht} wohldefiniert, sondern muss in der Sprache der Analysis verstanden werden. Kannst du dir die Gleichung für den Fall $q=\frac{1}{2}$ intuitiv erklären?
    \end{enumerate}
\end{bsp}





\section{Gruppen}


\begin{defin}[Gruppe] \index{Gruppe} \index{abelsche Gruppe}
    Eine \textbf{Gruppe} ist ein Monoid, in dem jedes Element invertierbar ist. Konkret handelt es sich bei einer Gruppe also um ein Paar $(G,*)$, bestehend aus einer Menge $G$ und einer Verknüpfung $*$ auf $G$, für das die \emph{Gruppenaxiome} gelten:
    \begin{labeling}[(G1), labelindent=1.5em]
        \item Die Verknüpfung $*$ ist assoziativ.
        \item $G$ enthält ein neutrales Element.
        \item Jedes Element von $G$ ist invertierbar.
    \end{labeling}
    Ist überdies die Verknüpfung auch noch kommutativ, so spricht man von einer \textbf{abelschen Gruppe}\footnote{\href{https://de.wikipedia.org/wiki/Niels_Henrik_Abel}{Niels Henrik Abel (1802-1829)}} oder von einer \emph{kommutativen Gruppe}.
\end{defin}


\begin{bsp}
    Es gilt:
    \begin{enumerate}
        \item $(\Z,+),(\Q,+),(\R,+),(\C,+)$ sind jeweils abelsche Gruppen. Denn die Addition ist assoziativ, kommutativ, besitzt die $0$ als neutrales Element und für jede ganze bzw. rationale bzw. reelle bzw. komplexe Zahl $x$ ist $-x$ ebenfalls eine ganze bzw. rationale bzw. reelle bzw. komplexe Zahl und invers zu $x$.
        \item Das Monoid $(\N_0,+)$ ist keine Gruppe, da beispielsweise das Element $5\in \N_0$ nicht invertierbar ist.
        \item Sofern $X$ eine mindestens zweielementige Menge ist, ist das Monoid $\Abb(X,X)$ keine Gruppe.
        \begin{proof}[*]
            Seien $a\in X$ irgendein Element und $f:X\to X$ die konstante Abbildung, die alles auf $a$ abbildet. Weil $X$ mindestens zwei verschiedene Elemente enthält, ist $f$ nicht injektiv und nach \cref{bijektiviso} somit auch nicht invertierbar in $\Abb(X,X)$. Also ist $\Abb(X,X)$ keine Gruppe.
        \end{proof}
    \end{enumerate}
\end{bsp}


Viele interessante Verknüpfungen liefern erstmal nur Monoide, aber noch keine Gruppen. Allerdings kann aus jedem Monoid eine (mehr oder weniger große) Gruppe extrahiert werden, indem man sich einfach auf die invertierbaren Elemente einschränkt:


\begin{defin}[Einheitengruppe eines Monoids] \index{Einheitengruppe}
    Sei $M$ ein Monoid. Die Teilmenge
        \[ M^\times := \{a\in M\mid a\ \text{ist invertierbar} \} \]
    heißt die \textbf{Einheitengruppe} von $M$.
\end{defin}


\begin{satz} \label{einheitengruppe}
    Sei $(M,*)$ ein Monoid. Dann ist die Teilmenge $M^\times\subseteq M$ abgeschlossen unter der Verknüpfung $*$ und wird mit ihrer Einschränkung zu einer Gruppe. Ist $M$ ein kommutatives Monoid, so ist $M^\times$ eine abelsche Gruppe.
\end{satz}
\begin{proof}[*]
    Sei $e\in M$ das neutrale Element.

    (Abgeschlossenheit): Für alle $a,b\in M^\times$ ist auch $a*b\in M^\times$ aufgrund der Regel von Hemd und Jacke. Also schränkt sich $*$ zu einer Verknüpfung auf $M^\times$ ein.

    (Assoziativität): Nach \cref{verknuepfeigstabil} ist die auf $M^\times$ eingeschränkte Verknüpfung ebenfalls assoziativ.

    (Neutrales Element): Nach \cref{regelnfuerinv}a) ist $e\in M^\times$. Wegen
    \begin{align*}
        e*x& =x*e=x && \text{für alle}\ x\in M
    \end{align*}
    gilt dies erst recht auch für alle $x\in M^\times$. Somit ist $e$ auch das neutrale Element von $M^\times$.

    (Inverse): Sei $a\in M^\times$. Nach \cref{regelnfuerinv}b) ist auch $a^{-1}$ invertierbar, also $a^{-1}\in M^\times$. Wegen
    \begin{align*}
        a*a^{-1}=a^{-1}*a=e
    \end{align*}
    und weil $e$ das neutrale Element von $M^\times$ ist, ist dann $a^{-1}$ auch in $M^\times$ invers zu $a$.

    (Kommutativität): Ist $M$ ein kommutatives Monoid, so ist nach \cref{verknuepfeigstabil} auch die auf $M^\times$ eingeschränkte Verknüpfung kommutativ, sodass $M^\times$ in diesem Fall eine abelsche Gruppe ist.
\end{proof}


\begin{bsp} \index{Symmetrische Gruppe} \index{Permutation} \quad
    \begin{enumerate}
        \item Nach \cref{bsp:inverse} ist die Einheitengruppe des Monoids $(\R,\cdot)$ genau $\R\setminus \{0\}$. Somit ist $(\R\setminus \{0\},\cdot)$ eine Gruppe.
        \item Die Einheitengruppe des Monoids $(\Z,\cdot)$ ist $\{1,-1\}$. Also ist $(\{\pm 1\},\cdot)$ eine Gruppe, die aus genau zwei Elementen besteht.
        \item Die Einheitengruppe des Monoids $(\N_0,+)$ ist $\{0\}$. Daher ist $(\{0\},+)$ eine Gruppe, die nur ein einziges Element enthält. Einelementige Gruppen heißen \emph{triviale Gruppen}.\footnote{vgl. \cref{aufg:verknuepfungen}}
        \item Sei $X$ eine beliebige Menge. Die Einheitengruppe des Monoids $\Abb(X,X)$, deren Elemente also genau die invertierbaren Selbstabbildungen von $X$ sind, heißt die \textbf{symmetrische Gruppe} von $X$. Ihre Elemente heißen \textbf{Permutationen} von $X$. Notation:
            \[ S(X) := \{f\in \Abb(X,X)\mid f\ \text{ist invertierbar} \} \]
        Nach \cref{bijektiviso} besteht $S(X)$ genau aus den bijektiven Selbstabbildungen von $X$.
        \item(Vorschau auf LA) Als weiteres wichtiges Beispiel wird dir in der LA1 die Matrizengruppe $\mathrm{GL}_n(K)$ der invertierbaren $(n\times n)$-Matrizen begegnen.
    \end{enumerate}
    Beachte, dass wir bei keinem dieser Beispiele noch einmal beweisen müssen, dass eine Gruppe vorliegt. Alle Beweisarbeit wurde bereits im abstrakten \cref{einheitengruppe} verrichtet.
\end{bsp}


\begin{bem}[Endliche Permutationsgruppen]
    Für eine Zahl $n\in \N_0$ schreibt man
        \[ S_n := S(\{1,\dots , n\}) \]
    für die Permutationsgruppe der Menge $\{1,\dots , n\}$. Diese Gruppen sind von großer Bedeutung in der Gruppentheorie, da sie nach dem \href{https://de.wikipedia.org/wiki/Satz_von_Cayley}{Satz von Cayley}\footnote{\href{https://de.wikipedia.org/wiki/Arthur_Cayley}{Arthur Cayley (1821-1895)}} in einem gewissen Sinn „universell“ sind unter allen Gruppen, die nur endlich viele Elemente enthalten. Sie waren historisch auch die ersten Studienobjekte der Gruppentheorie, noch bevor das Konzept „Gruppe“ überhaupt definiert war. Die $S_n$-Gruppen werden dir bereits in der LA-Vorlesung wieder begegnen, dort spätestens im Kontext von \emph{Matrixdeterminanten}.
\end{bem}


\begin{vorschau}[* Gruppenvervollständigung] \label{gruppenvervollstaendigung}
    Neben dem Konzept „Einheitengruppe“ gibt es ein weiteres Rezept, um aus Monoiden Gruppen zu machen: die \href{https://de.wikipedia.org/wiki/Grothendieck-Gruppe}{Gruppenvervollständigung} (manche sagen auch: \emph{Grothendieck-Gruppe}\footnote{\href{https://de.wikipedia.org/wiki/Alexander_Grothendieck}{Alexander Grothendieck (1928-2014)}}).
    
    Während, um von einem Monoid zu seiner Einheitengruppe zu gelangen, die Trägermenge soweit verkleinert wird, bis nur noch die invertierbaren Elemente übrigbleiben, werden bei der Gruppenvervollständigung „künstliche Inverse“ hinzugefügt. Beispielsweise kann die Gruppe $(\Z,+)$ dadurch konstruiert werden, dass man dem Monoid $(\N_0,+)$ für jedes $n\in \N_0$ eine „künstliche Inverse $-n$“ beilegt. Auch die Zahlbereichserweiterung $\Z \mapsto \Q$ geschieht durch die Hinzufügung künstlicher Inverser, diesmal bezüglich der Multiplikation. Solche Techniken, bei denen man für eine Struktur gewisse wünschenswerte Eigenschaften künstlich erzwingt, sind typisch für die abstrakte Algebra und tauchen dort beispielsweise bei den Konzepten „Abelisierung“, „Quotientenkörper“, „Lokalisierung eines Rings“, „Tensoralgebra“ oder „Zerfällungskörper“ auf.
\end{vorschau}





\clearpage
\section{Aufgabenvorschläge}


\begin{aufg}[Eigenschaften von Verknüpfungen (L)] \label{aufg:verknuepfungen}
    Entscheidet für jede der folgenden Verknüpfungen, ob sie assoziativ ist, kommutativ ist, ob sie ein neutrales Element besitzt und ob sie ein Monoid oder gar eine Gruppe liefert.
    \begin{enumerate}
        \item Auf der Menge $\N$ die Verknüpfung $m*n:=\max \{m,n\}$.
        \item Auf der Menge $\N_0$ die Verknüpfung $m*n:=n^m$ (wobei $n^0=1$ ist für alle $n\in \N_0$).
        \item Auf einer beliebigen einelementigen Menge eine beliebige Verknüpfung.
        \item Auf der Gesamtheit aller Mengen die Verknüpfung $M*N:=\{M,N\}$.
    \end{enumerate}
\end{aufg}


\begin{aufg}[Einige Rechenregeln für Differenzen]
    Seien $(M,+)$ ein additiv geschriebenes kommutatives Monoid, $a,b\in M$ zwei beliebige und $u,v\in M^\times$ zwei invertierbare Elemente. Leitet die folgenden Regeln her:
    \begin{alignat*}{3}
        \text{a)}&\qquad & a-(u+v) & \quad=&\quad &a-u-v \\
        \text{b)}&\qquad & a-(u-v) & \quad=&\quad &a-u+v \\
        \text{c)}&\qquad & -(u-v) & \quad=&\quad &v-u \\
        \text{d)}&\qquad & a=b+u & \quad\Leftrightarrow&\quad &a-u=b
    \end{alignat*}
\end{aufg}


\begin{comment}
\begin{aufg}[Kürzbarkeit]
    Sei $(M,*)$ ein Monoid. Ein Element $a\in M$ heißt \textbf{kürzbar}, wenn „Multiplikation mit $a$“ eine Äquivalenzumformung ist, d.h. wenn für alle $x,y\in M$ die beiden Äquivalenzen
    \begin{align*}
        a*x& =a*y \quad \leftrightarrow\quad x=y\\
        \text{und}\qquad x*a& =y*a \quad \leftrightarrow\quad x=y
    \end{align*}
    gelten.
    \begin{enumerate}
        \item Beweist, dass jedes invertierbare Element kürzbar ist.
        \item Ist ein kürzbares Element auch immer invertierbar?
    \end{enumerate}
\end{aufg}
\end{comment}


\begin{aufg}[Geometrische Reihe] \label{aufg:geometrischereihe}
    Vollzieht den Beweis des folgenden Satzes nach. Ist der Beweis korrekt und vollständig? Kann er vereinfacht werden? Stimmt der Satz überhaupt?
    \begin{satz}
        Für alle $n\in \N$ und $q\in \R\setminus \{1\}$ gilt:
            \[ \sum_{k=0}^n q^k = \frac{1-q^{n+1}}{\kern-1.4em1-q} \]
    \end{satz}
    \begin{proof}
        Es ist:
        \begin{align*}
            (1-q) \cdot \sum_{k=0}^n q^k & = 1\cdot \left( \sum_{k=0}^n q^k \right) - q\cdot \left( \sum_{k=0}^n q^k \right) \\
            & = \left( \sum_{k=0}^n q^k \right) - \left( \sum_{k=0}^{n} q^{k+1} \right) \\
            & = \left( \sum_{k=0}^n q^k \right) - \left( \sum_{k=1}^{n+1} q^{k} \right) && (\text{„Indexshift“}) \\
            %& = \sum_{k=0}^n (q^k - q^{k+1}) \\
            & = 1 - q^{n+1} && (\text{„Teleskopsumme“})
        \end{align*}
    Division durch $(1-q)$ liefert die gewünschte Gleichung.
    \end{proof}
\end{aufg}