diff options
Diffstat (limited to 'notes/mathe2/main.md')
| -rw-r--r-- | notes/mathe2/main.md | 2500 |
1 files changed, 2500 insertions, 0 deletions
diff --git a/notes/mathe2/main.md b/notes/mathe2/main.md new file mode 100644 index 0000000..80ff25e --- /dev/null +++ b/notes/mathe2/main.md @@ -0,0 +1,2500 @@ +--- +author: Marvin Borner +date: "`\\today`{=tex}" +lang: de-DE +pandoc-latex-environment: + bsp-box: + - bsp + defi-box: + - defi + visu-box: + - visu +toc-title: Inhalt +--- + +# Logik + +::: defi +Aussagen werden **einem** Wahrheitswert zugeordnet: **w** für *wahr* und +**f** für *falsch*. Eine Aussage, der der Wahrheitswert **w** schlicht +durch Festlegung zugewiesen wurde, heißt **Axiom**. +::: + +## Negation (nicht) + +- Notation: $\neg X$ + +- Gesprochen: `\enquote{nicht X}`{=tex} + + $X$ $\neg X$ + ------- ---------- + **w** **f** + **f** **w** + +- $\neg\neg x \iff x$ + +- $\neg (\forall x : P) \iff \exists x : (\neg P)$ + +- $\neg (\exists x : P) \iff \forall x : (\neg P)$ + +## Konjunktion (und) + +- Notation: $X \land Y$ + +- Gesprochen: `\enquote{X und Y}`{=tex} + + $Y$ $X$ $X \land Y$ + ------- ------- ------------- + **w** **w** **w** + **w** **f** **f** + **f** **w** **f** + **f** **f** **f** + +## Disjunktion (oder) + +- Notation: $X \lor Y$ + +- Gesprochen: `\enquote{X oder Y}`{=tex} + + $Y$ $X$ $X \lor Y$ + ------- ------- ------------ + **w** **w** **w** + **w** **f** **w** + **f** **w** **w** + **f** **f** **f** + +## Bijunktion (Äquivalenz) + +- Notation: $X \iff Y$ + +- Gesprochen: `\enquote{X genau dann wenn Y}`{=tex} + + $Y$ $X$ $X \iff Y$ + ------- ------- ------------ + **w** **w** **w** + **w** **f** **f** + **f** **w** **f** + **f** **f** **w** + +- Alternative: $(X \implies Y) \land (Y \implies X)$ + +## Subjunktion (Implikation) + +- Notation: $X \implies Y$ + +- Gesprochen: `\enquote{Aus X folgt Y}`{=tex} + + $Y$ $X$ $X \implies Y$ + ------- ------- ---------------- + **w** **w** **w** + **w** **f** **f** + **f** **w** **w** + **f** **f** **w** + +- Alternative: $(\neg X) \lor Y$ + +- Der Wahrheitswert der Implikation $X \implies Y$ bewertet nur die + Korrektheit des Schließens, nicht jedoch die Wahrheit der Aussagen + $X$ und $Y$ + +## Kontraposition + +- Definition: $X \implies Y \iff \neg Y \implies \neg X$ + + --------------------------------------------------------------------------------- + $X$ $Y$ $\neg Y$ $\neg Y$ $X \implies Y$ $\neg Y \implies \neg x$ + ------- ------- ---------- ---------- ---------------- -------------------------- + **w** **w** **f** **f** **w** **w** + + **w** **f** **f** **w** **f** **f** + + **f** **w** **w** **f** **w** **w** + + **f** **f** **w** **w** **w** **w** + --------------------------------------------------------------------------------- + +- Die Kontraposition ist sehr hilfreich für **Widerspruchsbeweise** + +## Quantoren + +- $\forall$: `\enquote{für alle}`{=tex} +- $\exists$: `\enquote{es existiert ein}`{=tex} +- $\exists!$: `\enquote{es existiert genau ein}`{=tex} +- $\nexists$: `\enquote{es existiert kein}`{=tex} + +## Präzedenz + +Sortiert nach stärkster Bindung: + +1. Negation ($\neg$) +2. Konjunktion ($\land$) und Disjunktion ($\lor$) +3. Implikation ($\iff$) und Äquivalenz ($\implies$) + +## Gesetze + +- Absorption + - $X \land w \iff X$ + - $X \land f \iff f$ + - $X \lor w \iff w$ + - $X \lor f \iff X$ +- Assoziativität + - $(X \lor Y) \lor Z \iff X \lor (X \lor Z)$ + - $(X \land Y) \land Z \iff X \land (X \land Z)$ +- Kommutativität + - $X \lor Y \iff Y \lor X$ + - $X \land Y \iff Y \land X$ +- Distributivität + - $X \land (Y \lor Z) \iff (X \land Y) \lor (X \land Z)$ + - $X \lor (Y \land Z) \iff (X \lor Y) \land (X \lor Z)$ +- De Morgansche Regeln + - $\neg (X \lor Y) \iff \neg X \land \neg Y$ + - $\neg (X \land Y) \iff \neg X \lor \neg Y$ + +# Mengen + +::: defi +Eine *Menge* ist eine Zusammenfassung von bestimmten, +wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens zu +einem Ganzen. Die in einer Menge zusammengefassten Objekte heißen +*Elemente* der Menge. +::: + +## Notation + +- Mengen angeben durch Auflisten der Elemente: $\{ 1,2,5,3,4,0 \}$ +- Mengen angeben durch Vorschreiben einer Eigenschaft: + $\{ x \mid x \text{ ist eine natürliche Zahl kleiner als } 6 \}$ +- $x \in M$ heißt `\enquote{x ist Element von M}`{=tex} +- $x \notin M$ heißt `\enquote{x ist nicht Element von M}`{=tex} +- $\{ \}$ und $\emptyset$ bezeichnen die *leere Menge* + +## Inklusionsrelationen + +- $M \subset N \iff (x \in M \implies x \in N)$ +- $M = N \iff (M \subset N \land N \subset M)$ +- $M \neq N \iff \neg (M = N) \iff ((\exists x \in M : x \notin N) \lor (\exists x \in N : x \notin M))$ +- $M \subsetneq N \iff (M \subset N \land M \neq N)$ + +## Zahlenbereiche + +$$ \P \subsetneq \N \subsetneq \Z \subsetneq \Q \subsetneq \R \subsetneq \C $$ + +- **Natürliche Zahlen**: $\N = \{ 0,1,2,3,4,5,... \}$ +- **Positive natürliche Zahlen**: $\N_{>0} = \{ 1,2,3,4,5,... \}$ +- **Ganze Zahlen**: $\Z = \{ ...,-3,-2,-1,0,1,2,3,... \}$ +- **Rationale Zahlen**: + $\Q = \{ \frac{p}{q} \mid p,q \in Z, q \neq 0 \}$ +- **Komplexe Zahlen**: $\C = 42$ TODO +- **Primzahlen**: Menge der natürlichen Zahlen $p$, die genau zwei + positive Teiler, nämlich $1$ und $p$, haben + +## Operationen von Mengen + +- $M \cap N = \{ x \mid x \in M \land x \in N \}$ heißt der + **Durchschnitt** von $M$ und $N$ +- $M \cup N = \{ x \mid x \in M \lor x \in N \}$ heißt die + **Vereinigung** von $M$ und $N$ +- $M \setminus N = \{ x \mid x \in M \land x \notin N \}$ heißt die + **Differenzmenge** von $M$ und $N$ +- $M \times N = \{ (x, y) \mid x \in M \land y \in N \}$ heißt das + **kartesische Produkt** von $M$ und $N$. Dabei ist $(x, y)$ ein + **geordnetes Paar (Tupel)**, und für zwei geordnete Paare + $(x, y), (u, v) \in M \times N$ gilt: + $$(x, y) = (u, v) \iff (x = u \land y = v)$$ +- $M$ und $N$ heißen genau dann **disjunkt**, wenn + $M \cap N = \emptyset$, d.h. wenn sie kein Element gemeinsam + besitzen +- $P = M \cupdot N \iff (P = M \cup N \land M \cap N = \emptyset)$ + beschreibt die **disjunkte Vereinigung** +- $\bigcap_{i \in I} M_i = \{ x \mid \forall i \in I : x \in M_i \}$ + heißt der **Durchschnitt** der $M_i$ +- $\bigcup_{i \in I} M_i = \{ x \mid \exists i \in I : x \in M_i \}$ + heißt die **Vereinigung** der $M_i$ +- $P = \bigcupdot_{i \in I} M_i \iff (P = \bigcup_{i \in I} M_i \land M_i \cap M_j = \emptyset\ \forall i,j \in I$ + mit $i \neq j)$ + +::: visu +**Visualisierung im Venn-Diagramm**: + +```{=tex} +\begin{tikzpicture}[thick, set/.style = {circle, minimum size = 2cm, fill=gray!30}] +\newcommand\intersection{0.8} + +% Set M +\node[set,label={135:$M$}] (M) at (0,0) {}; + +% Set N +\node[set,label={45:$N$}] (N) at (\intersection,0) {}; + +% Intersection +\begin{scope} +\clip (0,0) circle(1cm); +\clip (\intersection,0) circle(1cm); +\fill[orange!50](0,0) circle(1cm); +\end{scope} + +% Circles outline +\draw (0,0) circle(1cm); +\draw (\intersection,0) circle(1cm); + +% Set intersection label +\node at (\intersection/2,-1.5) {$M \cap N$}; + +\end{tikzpicture} +\begin{tikzpicture}[thick, set/.style = {circle, minimum size = 2cm, fill=orange!50}] +\newcommand\intersection{0.8} + +% Set M +\node[set,label={135:$M$}] (M) at (0,0) {}; + +% Set N +\node[set,label={45:$N$}] (N) at (\intersection,0) {}; + +% Circles outline +\draw (0,0) circle(1cm); +\draw (\intersection,0) circle(1cm); + +% Set intersection label +\node at (\intersection/2,-1.5) {$M \cup N$}; + +\end{tikzpicture} +\begin{tikzpicture}[thick, set/.style = {circle, minimum size = 2cm, fill=gray!30}] +\newcommand\intersection{0.8} + +% Set M +\node[set,fill=orange!50,label={135:$M$}] (M) at (0,0) {}; + +% Set N +\node[set,label={45:$N$}] (N) at (\intersection,0) {}; + +% Intersection +\begin{scope} +\clip (0,0) circle(1cm); +\clip (\intersection,0) circle(1cm); +\fill[gray!30](0,0) circle(1cm); +\end{scope} + +% Circles outline +\draw (0,0) circle(1cm); +\draw (\intersection,0) circle(1cm); + +% Set intersection label +\node at (\intersection/2,-1.5) {$M \setminus N$}; + +\end{tikzpicture} +\begin{tikzpicture}[thick, set/.style = {circle, minimum size = 2cm, fill=orange!50}] +\newcommand\intersection{2.1} + +% Set M +\node[set,label={135:$M$}] (M) at (0,0) {}; + +% Set N +\node[set,label={45:$N$}] (N) at (\intersection,0) {}; + +% Circles outline +\draw (0,0) circle(1cm); +\draw (\intersection,0) circle(1cm); + +% Set intersection label +\node at (\intersection/2,-1.5) {$M \cupdot N$}; + +\end{tikzpicture} +``` +::: + +::: bsp +**Beispiel** mit den Mengen $I = \{ 1, 2, 3 \}$, $M_1 = \{ a, 1, c \}$, +$M_2 = \{ b, 1, e \}$ und $M_3 = \{ d, 1, f \}$: +$$\bigcap_{i \in I} = \{ 1 \} \text { und } \bigcup_{i \in I} = \{ 1, a, b, c, d, e, f \}$$ +::: + +## Spezielle Mengen + +### Komplementärmenge + +Für eine Teilmenge $M$ einer Menge $N$ ist +$\overline{M} = N \setminus M$. + +::: visu +**Visualisierung**: + +```{=tex} +\begin{center}\begin{tikzpicture}[thick, set/.style = {circle, minimum size = 4cm, fill=gray!30}] + +% Set N +\node[set,fill=orange!50,label={45:$N$}] (N) at (0,0) {}; + +% Set M +\node[set,minimum size=2cm,label={135:$M$}] (M) at (0,0) {}; + +% Circles outline +\draw (0,0) circle(2cm); +\draw (0,0) circle(1cm); + +% Set intersection label +\node at (0,-2.5) {$\overline{M} = N \setminus M$}; + +\end{tikzpicture}\end{center} +``` +::: + +### Potenzmenge + +Für eine Menge $M$ ist die Potenzmenge +$\pot(M) = \{ A \mid A \subset M \}$. + +::: visu +**Visualisierung**: + +```{=tex} +\begin{center}\begin{tikzpicture} +\node (max) at (0,4) {$\{ x,y,z \}$}; +\node (a) at (-2,2) {$\{ x,y \}$}; +\node (b) at (0,2) {$\{ x,z \}$}; +\node (c) at (2,2) {$\{ y,z \}$}; +\node (d) at (-2,0) {$\{ x \}$}; +\node (e) at (0,0) {$\{ y \}$}; +\node (f) at (2,0) {$\{ z \}$}; +\node (min) at (0,-2) {$\emptyset$}; +\draw (min) -- (d) -- (a) -- (max) -- (b) -- (f) +(e) -- (min) -- (f) -- (c) -- (max) +(d) -- (b); +\draw[preaction={draw=white, -,line width=4pt}] (a) -- (e) -- (c); +\end{tikzpicture}\end{center} +``` +::: + +Außerdem gilt mit der endlichen Menge $M$: $|\pot(M)| = 2^{|M|}$ + +::: bsp +**Beispiel** mit der Menge $M = \{1,2,3\}$: +$$\pot(M) = \{\emptyset, \{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$$ +sowie $$|\pot(M)| = 8 = 2^{3} = 2^{|M|}$$ +::: + +## Gesetze + +- Assoziativität + - $(M \cup N) \cup P = M \cup (N \cup P)$ + - $(M \cap N) \cap P = M \cap (N \cap P)$ +- Kommutativität + - $M \cup N = N \cup M$ + - $M \cap N = N \cap M$ +- Distributivität + - $M \cap (N \cup P) = (M \cap N) \cup (M \cap P)$ + - $M \cup (N \cap P) = (M \cup N) \cap (M \cup P)$ +- Identität + - $M \cup \emptyset = M$ + - $M \subset N \implies M \cap N = M$ +- Komplement + - $M \subset N \implies M \cup (N \setminus M) = N$ + - $M \subset N \implies M \cap (N \setminus M) = \emptyset$ +- De Morgansche Regeln + - $M \setminus \bigcup_{i \in I} M_i = \bigcap_{i \in I} M \setminus M_i$ + - $M \setminus \bigcap_{i \in I} M_i = \bigcup_{i \in I} M \setminus M_i$ + +# Abbildungen + +::: defi +Es seien $M$ und $N$ zwei Mengen. Eine **Abbildung** oder **Funktion** +$f$ von $M$ nach $N$ ist eine *eindeutige Zuordnung*, die $jedem$ +Element $x \in M$ *genau ein* Element $f(x) \in N$ zuweist. Man +verwendet den Begriff Funktion nur dann, wenn $N = \R$ ist. +::: + +Man nennt $M$ den **Definitionsbereich** von $f$ und $N$ den **Ziel-** +oder **Wertebereich**. + +*Notation*: $$f: M \to N,\ x \mapsto f(x)$$ Für zwei Abbildungen +$f: M \to N$ und $g: X \to Y$ gilt: +$$f = g \iff (M = X \land N = Y \land \forall x \in M : f(x) = g(x))$$ + +## Legitime Abbildungen + +::: visu +**Visualisierung**: + +```{=tex} +\begin{center}\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}] +\node[ele,label=left:$a$] (a1) at (0,3) {}; +\node[ele,label=left:$b$] (a2) at (0,2) {}; +\node[ele,label=left:$c$] (a3) at (0,1) {}; + +\node[ele,label=right:$1$] (b1) at (2,3) {}; +\node[ele,label=right:$2$] (b2) at (2,2) {}; +\node[ele,label=right:$3$] (b3) at (2,1) {}; +\node[ele,label=right:$4$] (b4) at (2,0) {}; + +\node[draw,fit= (a1) (a2) (a3),minimum width=1.4cm] {} ; +\node[draw,fit= (b1) (b2) (b3) (b4),minimum width=1.4cm] {} ; +\draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b1); +\draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b4); +\draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b2); +\end{tikzpicture} +\hspace{1cm} +\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}] +\node[ele,label=left:$a$] (a1) at (0,3) {}; +\node[ele,label=left:$b$] (a2) at (0,2) {}; +\node[ele,label=left:$c$] (a3) at (0,1) {}; + +\node[ele,label=right:$1$] (b1) at (2,3) {}; +\node[ele,label=right:$2$] (b2) at (2,2) {}; +\node[ele,label=right:$3$] (b3) at (2,1) {}; +\node[ele,label=right:$4$] (b4) at (2,0) {}; + +\node[draw,fit= (a1) (a2) (a3),minimum width=1.4cm] {} ; +\node[draw,fit= (b1) (b2) (b3) (b4),minimum width=1.4cm] {} ; +\draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b4); +\draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b2); +\draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b1); +\end{tikzpicture}\end{center} +``` +::: + +## Illegitime Abbildungen + +::: visu +**Visualisierung**: + +```{=tex} +\begin{center}\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}] +\node[ele,label=left:$a$] (a1) at (0,3) {}; +\node[ele,fill=red,label=left:$b$] (a2) at (0,2) {}; +\node[ele,label=left:$c$] (a3) at (0,1) {}; + +\node[ele,label=right:$1$] (b1) at (2,3) {}; +\node[ele,label=right:$2$] (b2) at (2,2) {}; +\node[ele,label=right:$3$] (b3) at (2,1) {}; +\node[ele,label=right:$4$] (b4) at (2,0) {}; + +\node[draw,fit= (a1) (a2) (a3),minimum width=1.4cm] {} ; +\node[draw,fit= (b1) (b2) (b3) (b4),minimum width=1.4cm] {} ; +\draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b1); +\draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b2); +\draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b3); +\draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b3); +\end{tikzpicture} +\hspace{1cm} +\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}] +\node[ele,label=left:$a$] (a1) at (0,3) {}; +\node[ele,fill=red,label=left:$b$] (a2) at (0,2) {}; +\node[ele,label=left:$c$] (a3) at (0,1) {}; + +\node[ele,label=right:$1$] (b1) at (2,3) {}; +\node[ele,label=right:$2$] (b2) at (2,2) {}; +\node[ele,label=right:$3$] (b3) at (2,1) {}; +\node[ele,label=right:$4$] (b4) at (2,0) {}; + +\node[draw,fit= (a1) (a2) (a3),minimum width=1.4cm] {} ; +\node[draw,fit= (b1) (b2) (b3) (b4),minimum width=1.4cm] {} ; +\draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b1); +\draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b3); +\end{tikzpicture}\end{center} +``` +::: + +## Rechenregeln + +Mit den Abbildungen/Funktionen $f: U\to\R$, $g: V\to\R$ und $c\in\R$ +gilt: +`\begin{gather*} c \cdot f: U\to\R \to \R: x \mapsto c \cdot f(x) \\ f + g: U \cap V \to \R: x \mapsto f(x) + g(x) \\ f - g: U \cap V \to \R: x \mapsto f(x) - g(x) \\ f \cdot g: U \cap V \to \R: x \mapsto f(x) \cdot g(x) \\ \end{gather*}`{=tex} +Falls außerdem $\forall x \in U \cap V: g(x) \neq 0$: +$$\frac{f}{g}: U \cap V \to \R: x \mapsto \frac{f(x)}{g(x)}$$ + +## Selektionen + +### Einschränkung + +Mit der Abbildung $f: M \to N$ und $A \subset M$, ist +$$f_{\vert A}: A \to N,\ x \mapsto f(x)$$ die **Einschränkung** von $f$ +auf $A$. + +::: bsp +**Beispiel** mit $A = \{ b,c \}$: + +```{=tex} +\begin{center}\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}] +\node[ele,label=left:$a$] (a1) at (0,3) {}; +\node[ele,label=left:$b$] (a2) at (0,2) {}; +\node[ele,label=left:$c$] (a3) at (0,1) {}; + +\node[ele,label=right:$1$] (b1) at (2,3) {}; +\node[ele,label=right:$2$] (b2) at (2,2) {}; +\node[ele,label=right:$3$] (b3) at (2,1) {}; +\node[ele,label=right:$4$] (b4) at (2,0) {}; + +\node[draw,fit= (a1) (a2) (a3),minimum width=1.4cm] {} ; +\node[draw,fit= (b1) (b2) (b3) (b4),minimum width=1.4cm] {} ; +\draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b3); +\draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b2); +\draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b1); + +\node at (1,-1) {$f$}; +\end{tikzpicture} +\hspace{1cm} +\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}] +\node[ele,label=left:$ $] (a1) at (0,3) {}; +\node[ele,label=left:$b$] (a2) at (0,2) {}; +\node[ele,label=left:$c$] (a3) at (0,1) {}; + +\node[ele,label=right:$1$] (b1) at (2,3) {}; +\node[ele,label=right:$2$] (b2) at (2,2) {}; +\node[ele,label=right:$3$] (b3) at (2,1) {}; +\node[ele,label=right:$4$] (b4) at (2,0) {}; + +\node[draw,fit= (a1) (a2) (a3),minimum width=1.4cm] {} ; +\node[draw,fit= (b1) (b2) (b3) (b4),minimum width=1.4cm] {} ; +\draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b2); +\draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b1); + +\node at (1,-1) {$f_{\vert A}$}; +\end{tikzpicture}\end{center} +``` +::: + +### Identität + +Mit der Menge $M$ ist die Abbildung +$$\text{id}_M : M \to M,\ x \mapsto x$$ die **Identität** auf $M$. + +::: bsp +**Beispiel** mit $M = \{ 1,2,3 \}$: + +```{=tex} +\begin{center}\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}] +\node[ele,label=left:$1$] (a1) at (0,3) {}; +\node[ele,label=left:$2$] (a2) at (0,2) {}; +\node[ele,label=left:$3$] (a3) at (0,1) {}; + +\node[ele,label=right:$1$] (b1) at (2,3) {}; +\node[ele,label=right:$2$] (b2) at (2,2) {}; +\node[ele,label=right:$3$] (b3) at (2,1) {}; + +\node[draw,fit= (a1) (a2) (a3),minimum width=1.4cm] {} ; +\node[draw,fit= (b1) (b2) (b3),minimum width=1.4cm] {} ; +\draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b1); +\draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b2); +\draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b3); + +\node at (1,0) {$\text{id}_M$}; +\end{tikzpicture}\end{center} +``` +::: + +### Graph + +Mit der Abbildung $f: M \to N$ ist +$$\text{Graph}(f) = \{ (x, f(x)) \mid x \in M \} \subset M \times N$$ +der **Graph** von $f$. + +::: bsp +**Beispiel** mit Abbildung $f: \R\to\R,\ x \mapsto x^2$: + +```{=html} +<!-- prettier-ignore --> +``` +```{=tex} +\begin{center}\begin{tikzpicture} +\begin{axis}[axis lines = center] +\addplot[domain=-5:5,color=red]{x*x}; +\end{axis} +\end{tikzpicture}\end{center} +``` +::: + +- Für zwei Abbildungen $f: M \to N$ und $g: P \to N$ gilt: + $$f = g \iff \text{Graph}(f) = \text{Graph}(g)$$ +- Ist $\Gamma \subset M \times N$ so, dass + $$\forall x \in M\ \exists!\ y \in N: (x,y) \in \Gamma,$$ dann gibt + es eine Abbildung $f: M \to N$ mit $\Gamma = \text{Graph}(f)$ + +### Bild + +Mit der Abbildung $f: M \to N$ und $A \subset M$ ist +$$f(A) = \{ f(x) \mid x \in A \} \subset N$$ das **Bild** von $A$ +*unter* $f$. + +::: bsp +**Beispiel** mit $f: \R\to\R,\ x \mapsto x^2$ und +$A = \{ -2,-1,0,1,2 \} \subset M$: $$f(A) = \{ 0,1,4 \}$$ +::: + +$\text{im}(f) = f(M) \subset N$ heißt das **Bild** von $f$. +Umgangssprachlich bezeichnet das die Menge des getroffenen Zielbereichs. + +::: bsp +Mit vorigem **Beispiel**: $\text{im}(f) = \{ x\in\R \mid x \geq 0 \}$. +::: + +### Urbild + +Mit der Abbildung $f: M \to N$ und $B \subset N$ ist +$$f^{-1}(B) = \{ x \in M \mid f(x) \in B \} \subset M$$ das **Urbild** +von $B$ unter $f$. + +::: bsp +**Beispiel** mit $f: \R\to\R,\ x \mapsto x^2$ und +$B = \{ 0, 1, 4 \} \subset N$: $$f^{-1}(B) = \{ -2,-1,0,1,2 \}$$ +::: + +Ist $y \in N$ und $x \in M$ mit $f(x) = y$, so nennt man $x$ **ein +Urbild** von $y$ unter $f$. + +## Nachfolgerfunktion + +Die Abbildung $$\text{nf}: \N\to\N,\ x \mapsto x + 1$$ nennt man +**Nachfolgerfunktion**. Es gilt +$$\text{im}(\text{nf}) = \N \setminus \{ 0 \}$$ und +$$\forall y \in \text{im}(f): \text{nf}^{-1}(\{ y \}) = \{ y - 1 \}$$ + +## Eindeutigkeiten + +### Injektivität (linkseindeutig) + +Mit Abbildung $f: M \to N$: + +$$f \text{ ist injektiv} \iff \forall x,x' \in M: f(x) = f(x') \implies x = x'$$ +oder +$$f \text{ ist injektiv} \iff \text{jedes } y \in N \text{ hat höchstens ein Urbild}$$ +oder $$f \text{ ist injektiv} \iff f \text{ ist linksinvertierbar}$$ + +Es gilt: Bei injektivem $f$ gibt es eine oder keine Lösungen für +$f(x) = y$. + +::: visu +**Visualisierung**: + +```{=tex} +\begin{center}\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}] +\node[ele,label=left:$a$] (a1) at (0,3) {}; +\node[ele,label=left:$b$] (a2) at (0,2) {}; +\node[ele,label=left:$c$] (a3) at (0,1) {}; + +\node[ele,label=right:$1$] (b1) at (2,3) {}; +\node[ele,label=right:$2$] (b2) at (2,2) {}; +\node[ele,label=right:$3$] (b3) at (2,1) {}; +\node[ele,label=right:$4$] (b4) at (2,0) {}; + +\node[draw,fit= (a1) (a2) (a3),minimum width=1.4cm] {} ; +\node[draw,fit= (b1) (b2) (b3) (b4),minimum width=1.4cm] {} ; +\draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b1); +\draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b2); +\draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b4); + +\node at (1,-1) {injektiv}; +\end{tikzpicture} +\hspace{1cm} +\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}] +\node[ele,label=left:$a$] (a1) at (0,3) {}; +\node[ele,label=left:$b$] (a2) at (0,2) {}; +\node[ele,label=left:$c$] (a3) at (0,1) {}; + +\node[ele,label=right:$1$] (b1) at (2,3) {}; +\node[ele,fill=red,label=right:$2$] (b2) at (2,2) {}; +\node[ele,label=right:$3$] (b3) at (2,1) {}; +\node[ele,label=right:$4$] (b4) at (2,0) {}; + +\node[draw,fit= (a1) (a2) (a3),minimum width=1.4cm] {} ; +\node[draw,fit= (b1) (b2) (b3) (b4),minimum width=1.4cm] {} ; +\draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b2); +\draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b2); +\draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b4); + +\node at (1,-1) {nicht injektiv}; +\end{tikzpicture}\end{center} +``` +::: + +### Surjektivität (rechtstotal) + +Mit Abbildung $f: M \to N$: + +$$f \text{ ist surjektiv} \iff \forall y \in N\ \exists x \in M: f(x) = y$$ +oder $$f \text{ ist surjektiv} \iff \text{im}(f) = N$$ oder +$$f \text{ ist surjektiv} \iff \text{jedes } y \in N \text{ hat mindestens ein Urbild}$$ +oder $$f \text{ ist surjektiv} \iff f \text{ ist rechtsinvertierbar}$$ + +Es gilt: Bei surjektivem $f$ gibt es eine oder mehrere Lösungen für +$f(x) = y$. + +::: visu +**Visualisierung**: + +```{=tex} +\begin{center}\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}] +\node[ele,label=left:$a$] (a1) at (0,3) {}; +\node[ele,label=left:$b$] (a2) at (0,2) {}; +\node[ele,label=left:$c$] (a3) at (0,1) {}; +\node[ele,label=left:$d$] (a4) at (0,0) {}; + +\node[ele,label=right:$1$] (b1) at (2,3) {}; +\node[ele,label=right:$2$] (b2) at (2,2) {}; +\node[ele,label=right:$3$] (b3) at (2,1) {}; + +\node[draw,fit= (a1) (a2) (a3) (a4),minimum width=1.4cm] {} ; +\node[draw,fit= (b1) (b2) (b3),minimum width=1.4cm] {} ; +\draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b1); +\draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b2); +\draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b3); +\draw[->,thick,shorten <=2pt,shorten >=2] (a4) -- (b3); + +\node at (1,-1) {surjektiv}; +\end{tikzpicture} +\hspace{1cm} +\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}] +\node[ele,label=left:$a$] (a1) at (0,3) {}; +\node[ele,label=left:$b$] (a2) at (0,2) {}; +\node[ele,label=left:$c$] (a3) at (0,1) {}; +\node[ele,label=left:$d$] (a4) at (0,0) {}; + +\node[ele,label=right:$1$] (b1) at (2,3) {}; +\node[ele,fill=red,label=right:$2$] (b2) at (2,2) {}; +\node[ele,label=right:$3$] (b3) at (2,1) {}; + +\node[draw,fit= (a1) (a2) (a3) (a4),minimum width=1.4cm] {} ; +\node[draw,fit= (b1) (b2) (b3),minimum width=1.4cm] {} ; +\draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b1); +\draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b3); +\draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b3); +\draw[->,thick,shorten <=2pt,shorten >=2] (a4) -- (b3); + +\node at (1,-1) {nicht surjektiv}; +\end{tikzpicture}\end{center} +``` +::: + +### Bijektivität (eineindeutig) + +Mit Abbildung $f: M \to N$: + +$$f \text{ ist bijektiv} \iff f \text{ ist injektiv und surjektiv}$$ +oder +$$f \text{ ist bijektiv} \iff g: N \to M \text{ existiert}: (g \circ f = \text{id}_M) \land (f \circ g = \text{id}_N)$$ +oder +$$f \text{ ist bijektiv} \iff \text{jedes } y \in N \text{ hat genau ein Urbild}$$ +oder $$f \text{ ist bijektiv} \iff f \text{ ist invertierbar}$$ + +Es gilt: Bei bijektivem $f$ gibt es genau eine Lösung für $f(x) = y$. + +::: visu +**Visualisierung**: + +```{=tex} +\begin{center}\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}] +\node[ele,label=left:$a$] (a1) at (0,3) {}; +\node[ele,label=left:$b$] (a2) at (0,2) {}; +\node[ele,label=left:$c$] (a3) at (0,1) {}; +\node[ele,label=left:$d$] (a4) at (0,0) {}; + +\node[ele,label=right:$1$] (b1) at (2,3) {}; +\node[ele,label=right:$2$] (b2) at (2,2) {}; +\node[ele,label=right:$3$] (b3) at (2,1) {}; +\node[ele,label=right:$4$] (b4) at (2,0) {}; + +\node[draw,fit= (a1) (a2) (a3) (a4),minimum width=1.4cm] {} ; +\node[draw,fit= (b1) (b2) (b3) (b4),minimum width=1.4cm] {} ; +\draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b2); +\draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b3); +\draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b4); +\draw[->,thick,shorten <=2pt,shorten >=2] (a4) -- (b1); + +\node at (1,-1) {bijektiv}; +\end{tikzpicture} +\hspace{1cm} +\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}] +\node[ele,label=left:$a$] (a1) at (0,3) {}; +\node[ele,label=left:$b$] (a2) at (0,2) {}; +\node[ele,label=left:$c$] (a3) at (0,1) {}; +\node[ele,label=left:$d$] (a4) at (0,0) {}; + +\node[ele,label=right:$1$] (b1) at (2,3) {}; +\node[ele,fill=red,label=right:$2$] (b2) at (2,2) {}; +\node[ele,label=right:$3$] (b3) at (2,1) {}; +\node[ele,fill=red,label=right:$4$] (b4) at (2,0) {}; + +\node[draw,fit= (a1) (a2) (a3) (a4),minimum width=1.4cm] {} ; +\node[draw,fit= (b1) (b2) (b3) (b4),minimum width=1.4cm] {} ; +\draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b1); +\draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b3); +\draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b4); +\draw[->,thick,shorten <=2pt,shorten >=2] (a4) -- (b4); + +\node at (1,-1) {nicht bijektiv}; +\end{tikzpicture}\end{center} +``` +::: + +## Komposition + +Mit den Abbildungen $f: M \to N$ und $g: N \to P$, ist +$$g \circ f: M \to P,\ x \mapsto g(f(x))$$ die **Komposition** oder +**Verkettung** von $f$ und $g$. + +::: bsp +**Beispiel**: + +```{=tex} +\begin{center}\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}] +\node[ele,label=left:$a$] (a1) at (0,3) {}; +\node[ele,label=left:$b$] (a2) at (0,2) {}; +\node[ele,label=left:$c$] (a3) at (0,1) {}; + +\node[ele,label=right:$1$] (b1) at (2,3) {}; +\node[ele,label=right:$2$] (b2) at (2,2) {}; +\node[ele,label=right:$3$] (b3) at (2,1) {}; + +\node[ele,label=right:$\alpha$] (c1) at (4,3) {}; +\node[ele,label=right:$\beta$] (c2) at (4,2) {}; +\node[ele,label=right:$\gamma$] (c3) at (4,1) {}; + +\node[draw,fit= (a1) (a2) (a3),minimum width=1.4cm] {} ; +\node[draw,fit= (b1) (b2) (b3),minimum width=1.4cm] {} ; +\node[draw,fit= (c1) (c2) (c3),minimum width=1.4cm] {} ; +\draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b1); +\draw[->,thick,shorten <=2pt,shorten >=2] (b1) ++(13pt,0) -- (c2); +\draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b1); +\draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b2); +\draw[->,thick,shorten <=2pt,shorten >=2] (b2) ++(18pt,0) -- (c1); +\draw[->,thick,shorten <=2pt,shorten >=2] (b3) ++(12pt,0) -- (c3); + +\node at (1,0) {$f: M \to N$}; +\node at (3,0) {$g: N \to P$}; + +\draw[->,thick] (2,-1) -- (2, -2); +\end{tikzpicture}\end{center} +``` +```{=tex} +\begin{center}\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}] +\node[ele,label=left:$a$] (a1) at (0,3) {}; +\node[ele,label=left:$b$] (a2) at (0,2) {}; +\node[ele,label=left:$c$] (a3) at (0,1) {}; + +\node[ele,label=right:$\alpha$] (c1) at (4,3) {}; +\node[ele,label=right:$\beta$] (c2) at (4,2) {}; +\node[ele,label=right:$\gamma$] (c3) at (4,1) {}; + +\node[draw,fit= (a1) (a2) (a3),minimum width=1.4cm] {} ; +\node[draw,fit= (c1) (c2) (c3),minimum width=1.4cm] {} ; +\draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (c2); +\draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (c2); +\draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (c1); + +\node at (2,0) {$g \circ f: M \to P$}; +\end{tikzpicture}\end{center} +``` +::: + +### Assoziativität + +Mit den Abbildungen $f: M \to N$, $g: N \to P$ und $h: P \to Q$ gilt: +$$(h \circ g) \circ f = h \circ (g \circ f),$$ weshalb man auch kurz +$h \circ g \circ f$ schreibt. + +### Eindeutigkeiten unter Komposition + +Mit den Abbildungen $f: M \to N$ und $g: N \to P$ gilt: + +- Sind $f$ und $g$ injektiv, so ist $g \circ f$ injektiv. +- Sind $f$ und $g$ surjektiv, so ist $g \circ f$ surjektiv. +- Sind $f$ und $g$ bijektiv, so ist $g \circ f$ bijektiv. + +# Vollständige Induktion + +::: defi +Sei $\mathcal{A}(n)$ eine Aussageform mit zulässigen Werten $n\in\N$. +Falls $\mathcal{A}(0)$ wahr ist und +$\mathcal{A}(n) \implies \mathcal{A}(n+1)$ wahr ist, so ist +$\mathcal{A}(n)$ wahr für alle $n\in\N$. +::: + +- `\enquote{$\mathcal{A}(0)$ wahr}`{=tex} nennt man den + *Induktionsanfang* +- `\enquote{$\mathcal{A}(n)$ wird als wahr vorausgesetzt}`{=tex} nennt + man die *Induktionsvoraussetzung* +- `\enquote{$\mathcal{A}(n) \implies \mathcal{A}(n + 1)$}`{=tex} nennt + man den *Induktionsschluss* + +# Mächtigkeit von Mengen + +::: defi +- Eine Menge $M$ ist **endlich**, wenn sie nur endlich viele Elemente + enthält. In diesem Fall bezeichnet man mit $\#M = |M|$ die Anzahl an + Elementen in $M$ und nennt die Zahl die + **Mächtigkeit**/**Kardinalität** von $M$. Enthält $M$ unendlich + viele Elemente, so nennt man $M$ **unendlich** und setzt + $\#M = |M| = \infty$. +- Zwei Mengen $M$ und $N$ heißen **gleichmächtig**, wenn es eine + bijektive Abbildung $f: M \to N$ gibt. +- Eine Menge heißt **abzählbar unendlich**, wenn sie gleichmächtig zu + $\N$ ist. +- Eine Menge heißt **überabzählbar**, wenn sie weder endlich noch + abzählbar unendlich ist. +- Für $m,n\in\Z$ bezeichnet man mit + $$\{ m,...,n \} = \{ k\in\Z \mid m \leq k \leq n \}$$ die Menge der + ganzen Zahlen zwischen $m$ und $n$. +::: + +## Eigenschaften endlicher Mengen + +- Ist eine Menge endlich und enthält genau $n$ Elemente, so kann man + die Elemente in $M$ mit $x_1,x_2,x_3,...,x_n$ abzählen und man + erhält eine bijektive Abbildung + $$f: \{ 1,...,n \} \to M: i \mapsto x_i.$$ Umgekehrt erlaubt eine + solche Abbildung, die Elemente von $M$ abzuzählen und man erhält + $|M| = n$. Damit sieht man, dass eine Menge genau dann endlich von + Mächtigkeit $n$ ist, wenn es eine Bijektion von $\{ 1,...n \}$ nach + $M$ gibt. +- Ist die Menge $M$ endlich und $A \subset M$, so ist auch $A$ endlich + und $|A| \leq |M|$. +- Ist $M = A \cupdot B$ eine endliche Menge, so gilt + $|M| = |A| + |B|$. + +**Zusammenhang zwischen Mächtigkeit und Abbildung**: + +Mit den nicht-leeren endlichen Mengen $M$ und $N$ gilt: + +- $|M| \leq |N| \iff$ eine injektive Abbildung $f: M \to N$ existiert +- $|M| \geq |N| \iff$ eine surjektive Abbildung $f: M \to N$ existiert +- $|M| = |N| \iff$ eine bijektive Abbildung $f: M \to N$ existiert + +## Schubfachprinzip + +Aus dem Zusammenhang zwischen Mächtigkeit und Abbildung folgt +$$f: M \to N \text{ ist eine Abbildung und } |M| > |N| \implies f \text{ ist nicht injektiv}.$$ +Diese Kontraposition nennt man auch das **Schubfachprinzip**. +Umgangssprachlich heißt das: Wenn man $m > n$ Gegenstände auf $n$ +Schubfächer verteilen möchte, dann muss man in mindestens ein Schubfach +zwei legen. + +::: bsp +**Beispiel** des Versuchs einer Konstruktion einer injektiven Abbildung +trotz $|M| > |N|$ mit $M = \{ 1,2,3,4 \}$ und $N = \{ a,b,c \}$: + +```{=tex} +\begin{center}\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=-2pt}] +\node[ele,label=left:$1$] (a1) at (0,3) {}; +\node[ele,label=left:$2$] (a2) at (0,2) {}; +\node[ele,label=left:$3$] (a3) at (0,1) {}; +\node[ele,fill=red,label=left:$4$] (a4) at (0,0) {}; + +\node[ele,label=right:$a$] (b1) at (2,3) {}; +\node[ele,label=right:$b$] (b2) at (2,2) {}; +\node[ele,label=right:$c$] (b3) at (2,1) {}; + +\node[draw,fit= (a1) (a2) (a3) (a4),minimum width=1.4cm] {} ; +\node[draw,fit= (b1) (b2) (b3),minimum width=1.4cm] {} ; +\draw[->,thick,shorten <=2pt,shorten >=2] (a1) -- (b1); +\draw[->,thick,shorten <=2pt,shorten >=2] (a2) -- (b2); +\draw[->,thick,shorten <=2pt,shorten >=2] (a3) -- (b3); + +\node at (1,-1) {Injektivität nicht möglich}; +\end{tikzpicture}\end{center} +``` +::: + +# Äquivalenzrelationen + +::: defi +Mit den Mengen $M$ und $N$, ist jede Teilmenge $R \subset M \times N$ +eine **Relation** zwischen $M$ und $N$. Für $x \in M$ und $y \in N$ +schreibt man auch $xRy$ statt $(x,y) \in R$, wenn $x$ in Relation zu $y$ +bezüglich $R$ steht. +::: + +Für die Äquivalenzrelation $R$ auf die Menge $M$ gilt die Notation: +$$x \sim y \iff (x,y) \in R.$$ + +## Axiome + +1. *Reflexivität*: $x \sim x$ +2. *Symmetrie*: $x \sim y \implies y \sim x$ +3. *Transitivität*: $x \sim y \land y \sim z \implies x \sim z$ + +::: bsp +**Beispiel** einer abstrakten Alltagssituation: In einer Schule werden +SchülerInnen klassisch in Schulklassen unterteilt. Übertragen sind die +Axiome dann für die Schüler Alfred, Ben und Christoph: + +1. Alfred gehört zu einer Schulklasse: Er ist in derselben Schulklasse + wie er selbst. +2. Wenn Alfred in derselben Schulklasse ist wie Ben, dann ist Ben auch + in derselben Schulklasse wie Alfred. +3. Wenn Alfred in derselben Schulklasse ist wie Ben und wenn zugleich + Ben in derselben Schulklasse ist wie Christoph, dann ist auch Alfred + in derselben Schulklasse wie Christoph. + +In diesem Fall ist dann die Relation +`\enquote{SchülerIn $x$ ist in derselben Schulklasse wie SchülerIn $y$}`{=tex} +die *Äquivalenzrelation*, die SchülerInnen derselben Schulklasse +*äquivalent* und die Schulklassen die *Äquivalenzklassen*. +::: + +**Visualisierung** zu vorigem Beispiel (wunderschön): + +```{=tex} +\begin{center}\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1] +% Generated using mathcha.io +\draw [fill={rgb, 255:red, 216; green, 216; blue, 216 } ,fill opacity=0.38 ] (10.08,222.25) .. controls (10.08,106.27) and (152.23,12.25) .. (327.58,12.25) .. controls (502.93,12.25) and (645.08,106.27) .. (645.08,222.25) .. controls (645.08,338.23) and (502.93,432.25) .. (327.58,432.25) .. controls (152.23,432.25) and (10.08,338.23) .. (10.08,222.25) -- cycle ; +\draw [color={rgb, 255:red, 255; green, 0; blue, 0 } ,draw opacity=1 ][fill={rgb, 255:red, 255; green, 0; blue, 0 } ,fill opacity=0.07 ] (45,224.63) .. controls (45,156.9) and (106.8,102) .. (183.04,102) .. controls (259.28,102) and (321.08,156.9) .. (321.08,224.63) .. controls (321.08,292.35) and (259.28,347.25) .. (183.04,347.25) .. controls (106.8,347.25) and (45,292.35) .. (45,224.63) -- cycle ; +\draw [color={rgb, 255:red, 0; green, 56; blue, 255 } ,draw opacity=1 ][fill={rgb, 255:red, 0; green, 36; blue, 255 } ,fill opacity=0.09 ] (294,112.13) .. controls (294,66.77) and (334.54,30) .. (384.54,30) .. controls (434.55,30) and (475.08,66.77) .. (475.08,112.13) .. controls (475.08,157.48) and (434.55,194.25) .. (384.54,194.25) .. controls (334.54,194.25) and (294,157.48) .. (294,112.13) -- cycle ; +\draw [color={rgb, 255:red, 0; green, 255; blue, 18 } ,draw opacity=1 ][fill={rgb, 255:red, 0; green, 255; blue, 64 } ,fill opacity=0.15 ] (319,292.13) .. controls (319,238.48) and (380.8,195) .. (457.04,195) .. controls (533.28,195) and (595.08,238.48) .. (595.08,292.13) .. controls (595.08,345.77) and (533.28,389.25) .. (457.04,389.25) .. controls (380.8,389.25) and (319,345.77) .. (319,292.13) -- cycle ; +\draw [fill={rgb, 255:red, 255; green, 0; blue, 0 } ,fill opacity=1 ] (132.45,169.89) -- (152.06,172.25) -- (149.92,191.88) -- (145.56,186.38) -- (123.81,203.66) -- (128.18,209.15) -- (108.57,206.8) -- (110.71,187.17) -- (115.08,192.66) -- (136.82,175.39) -- cycle ; +\draw [fill={rgb, 255:red, 255; green, 0; blue, 0 } ,fill opacity=1 ] (171.25,236.85) -- (182.75,256.14) -- (161.41,263.16) -- (163.87,256.58) -- (131.04,244.31) -- (128.58,250.88) -- (117.08,231.59) -- (138.41,224.58) -- (135.95,231.15) -- (168.79,243.43) -- cycle ; +\draw [fill={rgb, 255:red, 255; green, 0; blue, 0 } ,fill opacity=1 ] (225.02,221) -- (219.54,243.94) -- (199.19,232.02) -- (205.65,229.26) -- (190.78,194.41) -- (184.32,197.16) -- (189.8,174.23) -- (210.15,186.14) -- (203.69,188.9) -- (218.56,223.75) -- cycle ; +\draw [fill={rgb, 255:red, 255; green, 0; blue, 0 } ,fill opacity=1 ] (141.42,125.91) .. controls (144.77,122.76) and (157.93,131.32) .. (170.82,145.04) -- (164.76,150.74) .. controls (151.87,137.03) and (138.7,128.46) .. (135.35,131.61) ;\draw [fill={rgb, 255:red, 255; green, 0; blue, 0 } ,fill opacity=1 ] (135.35,131.61) .. controls (132.69,134.11) and (137.01,143.23) .. (145.35,153.75) -- (143.33,155.65) -- (155.66,159.29) -- (153.44,146.15) -- (151.42,148.05) .. controls (143.08,137.53) and (138.76,128.4) .. (141.42,125.91)(135.35,131.61) -- (141.42,125.91) ; +\draw [fill={rgb, 255:red, 255; green, 0; blue, 0 } ,fill opacity=1 ] (280,228.97) .. controls (283.26,232.22) and (275.13,245.66) .. (261.84,258.99) -- (255.94,253.11) .. controls (269.23,239.78) and (277.36,226.34) .. (274.11,223.09) ;\draw [fill={rgb, 255:red, 255; green, 0; blue, 0 } ,fill opacity=1 ] (274.11,223.09) .. controls (271.52,220.52) and (262.54,225.14) .. (252.3,233.82) -- (250.34,231.86) -- (247.1,244.3) -- (260.17,241.65) -- (258.2,239.69) .. controls (268.44,231.01) and (277.42,226.4) .. (280,228.97)(274.11,223.09) -- (280,228.97) ; +\draw [fill={rgb, 255:red, 255; green, 0; blue, 0 } ,fill opacity=1 ] (71.28,251.71) .. controls (67.32,249.24) and (69.89,233.12) .. (77.02,215.69) -- (84.19,220.16) .. controls (77.06,237.58) and (74.49,253.71) .. (78.45,256.17) ;\draw [fill={rgb, 255:red, 255; green, 0; blue, 0 } ,fill opacity=1 ] (78.45,256.17) .. controls (81.59,258.13) and (87.9,250.9) .. (93.93,239.12) -- (96.32,240.61) -- (94.94,226.86) -- (84.38,233.17) -- (86.76,234.66) .. controls (80.73,246.43) and (74.42,253.66) .. (71.28,251.71)(78.45,256.17) -- (71.28,251.71) ; +\draw [fill={rgb, 255:red, 0; green, 255; blue, 91 } ,fill opacity=1 ] (417.45,243.89) -- (437.06,246.25) -- (434.92,265.88) -- (430.56,260.38) -- (408.81,277.66) -- (413.18,283.15) -- (393.57,280.8) -- (395.71,261.17) -- (400.08,266.66) -- (421.82,249.39) -- cycle ; +\draw [fill={rgb, 255:red, 0; green, 255; blue, 91 } ,fill opacity=1 ] (458.25,313.85) -- (469.75,333.14) -- (448.41,340.16) -- (450.87,333.58) -- (418.04,321.31) -- (415.58,327.88) -- (404.08,308.59) -- (425.41,301.58) -- (422.95,308.15) -- (455.79,320.43) -- cycle ; +\draw [fill={rgb, 255:red, 0; green, 255; blue, 91 } ,fill opacity=1 ] (513.48,300.42) -- (508.49,324.5) -- (487.65,311.44) -- (494.11,308.69) -- (478.26,271.55) -- (471.81,274.31) -- (476.8,250.23) -- (497.64,263.28) -- (491.18,266.04) -- (507.03,303.18) -- cycle ; +\draw [fill={rgb, 255:red, 0; green, 255; blue, 91 } ,fill opacity=1 ] (428.42,203.91) .. controls (431.77,200.76) and (444.93,209.32) .. (457.82,223.04) -- (451.76,228.74) .. controls (438.87,215.03) and (425.7,206.46) .. (422.35,209.61) ;\draw [fill={rgb, 255:red, 0; green, 255; blue, 91 } ,fill opacity=1 ] (422.35,209.61) .. controls (419.69,212.11) and (424.01,221.23) .. (432.35,231.75) -- (430.33,233.65) -- (442.66,237.29) -- (440.44,224.15) -- (438.42,226.05) .. controls (430.08,215.53) and (425.76,206.4) .. (428.42,203.91)(422.35,209.61) -- (428.42,203.91) ; +\draw [fill={rgb, 255:red, 0; green, 255; blue, 91 } ,fill opacity=1 ] (558,304.97) .. controls (561.26,308.22) and (553.13,321.66) .. (539.84,334.99) -- (533.94,329.11) .. controls (547.23,315.78) and (555.36,302.34) .. (552.11,299.09) ;\draw [fill={rgb, 255:red, 0; green, 255; blue, 91 } ,fill opacity=1 ] (552.11,299.09) .. controls (549.52,296.52) and (540.54,301.14) .. (530.3,309.82) -- (528.34,307.86) -- (525.1,320.3) -- (538.17,317.65) -- (536.2,315.69) .. controls (546.44,307.01) and (555.42,302.4) .. (558,304.97)(552.11,299.09) -- (558,304.97) ; +\draw [fill={rgb, 255:red, 0; green, 255; blue, 91 } ,fill opacity=1 ] (357.28,329.71) .. controls (353.32,327.24) and (355.89,311.12) .. (363.02,293.69) -- (370.19,298.16) .. controls (363.06,315.58) and (360.49,331.71) .. (364.45,334.17) ;\draw [fill={rgb, 255:red, 0; green, 255; blue, 91 } ,fill opacity=1 ] (364.45,334.17) .. controls (367.59,336.13) and (373.9,328.9) .. (379.93,317.12) -- (382.32,318.61) -- (380.94,304.86) -- (370.38,311.17) -- (372.76,312.66) .. controls (366.73,324.43) and (360.42,331.66) .. (357.28,329.71)(364.45,334.17) -- (357.28,329.71) ; +\draw [fill={rgb, 255:red, 0; green, 19; blue, 255 } ,fill opacity=1 ] (347.56,81.47) .. controls (351.45,77.84) and (365.02,86.04) .. (377.87,99.8) -- (370.81,106.39) .. controls (357.97,92.63) and (344.4,84.42) .. (340.5,88.06) ;\draw [fill={rgb, 255:red, 0; green, 19; blue, 255 } ,fill opacity=1 ] (340.5,88.06) .. controls (337.55,90.82) and (341,99.59) .. (348.44,109.67) -- (346.09,111.86) -- (360.23,116.27) -- (357.85,100.89) -- (355.5,103.08) .. controls (348.06,93) and (344.6,84.23) .. (347.56,81.47)(340.5,88.06) -- (347.56,81.47) ; + +\draw (153,153) node [anchor=north west][inner sep=0.75pt] [align=left] {Antonia}; +\draw (84,207) node [anchor=north west][inner sep=0.75pt] [align=left] {Benny}; +\draw (187,245) node [anchor=north west][inner sep=0.75pt] [align=left] {Christoph}; +\draw (440,230) node [anchor=north west][inner sep=0.75pt] [align=left] {Anne}; +\draw (371,284) node [anchor=north west][inner sep=0.75pt] [align=left] {Freddi}; +\draw (474,322) node [anchor=north west][inner sep=0.75pt] [align=left] {Dominik}; +\draw (360,105) node [anchor=north west][inner sep=0.75pt] [align=left] {Lars}; +\draw (150,52) node [anchor=north west][inner sep=0.75pt] [align=left] {\textbf{\underline{Alle SchülerInnen}}}; +\draw (232,158) node [anchor=north west][inner sep=0.75pt] [font=\normalsize,color={rgb, 255:red, 0; green, 0; blue, 0 } ,opacity=1 ] [align=left] {\textbf{\underline{Klasse 1}}}; +\draw (350,40) node [anchor=north west][inner sep=0.75pt] [align=left] {\textbf{\underline{Klasse 2}}}; +\draw (511.17,240) node [anchor=north west][inner sep=0.75pt] [align=left] {\textbf{\underline{Klasse 3}}}; +\end{tikzpicture}\end{center} +``` +## Äquivalenzklassen + +Mit der Menge $M$ und der Äquivalenzrelation $\sim$ auf $M$, heißt für +$x \in M$ die Menge $$[x] = \{ y \in M \mid y \sim x \}$$ die +**Äquivalenzklasse** von $x$. Jedes $y \in [x]$ heißt ein +**Repräsentant** der Klasse $[x]$. + +::: bsp +Mit dem vorigen **Beispiel** gilt: +$$[\text{Alfred}] = \{ \text{Alfred, Ben, Christoph} \},$$ sowie +$$[\text{Alfred}] = [\text{Ben}] = [\text{Christoph}].$$ +::: + +------------------------------------------------------------------------ + +Mit $$M/{\sim} = \{ [x] \mid x \in M \}$$ bezeichnet man die Menge der +**Äquivalenzklassen modulo der Äquivalenzrelation** $\sim$. + +::: bsp +Mit dem vorigen **Beispiel** gilt: +$$M/{\sim} = \{ [\text{Alfred}], [\text{Ben}], [\text{Christoph}], [\text{Philipp}], [\text{Anne}], [\text{Dominik}], [\text{Freddi}] \}.$$ +::: + +## Disjunkte Zerlegung + +Ist $(M_i)_{i \in I}$ eine disjunkte Zerlegung der Menge $M$ und die +Relation auf $M$ $$x \sim y \iff \exists i \in I : x,y \in M_i,$$ dann +ist $\sim$ eine Äquivalenzrelation auf $M$. + +------------------------------------------------------------------------ + +Ist $\sim$ eine Äquivalenzrelation auf der Menge $M$, dann bilden die +Äquivalenzklassen eine disjunkte Zerlegung von $M$, d.h. jedes $x \in M$ +liegt in genau einer Äquivalenzklasse. Insbesondere gilt für +Äquivalenzklassen $[x]$ und $[y]$ entweder $[x] = [y]$ oder +$[x] \cap [y] = \emptyset$. + +::: bsp +Voriges **Beispiel** der Schulklassen ist hilfreich um zu sehen, dass +kein Repräsentant in zwei Äquivalenzklassen gleichzeitig sein kann und +damit eine disjunkte Zerlegung der SchülerInnen vorliegen muss. +::: + +## Kongruenz modulo $n$ + +Mit $n\in\Z_{>0}$ und $a,b\in\Z$ wird die Äquivalenzrelation $\equiv$ +definiert: $$a \equiv b \pmod{n} \iff n \mid a - b$$ Das heißt, die +Reste der ganzzahligen Division von $a$ mit $n$, sowie von $b$ mit $n$, +müssen gleich sein. Zwei äquivalente Zahlen $a$ und $b$ werden dann auch +**kongruent modulo $n$** genannt. + +::: bsp +**Beispiel** mit $5 \equiv 11 \pmod{3}$: + +Die Aussage ist wahr, da $\frac{5}{3} = 1 \text{ Rest } 2$ und +$\frac{11}{3} = 3 \text{ Rest } 2$ die gleichen Reste besitzen bzw. auch +$3 \mid (11 - 5) = 3 \mid 6$ wahr ist. +::: + +Man bezeichnet die Äquivalenzklasse von $a\in\Z$ mit +$$[a] = \{ a+kn \mid k\in\Z \} = \{ b\in\Z \mid a \equiv b \pmod{n} \}$$ +Die Menge der Äquivalenzklassen ist $$\Z/n\Z = \{ [a] \mid a\in\Z \}$$ +und es gilt $|\Z/n\Z| = n$. + +### Teilbarkeit in Kongruenz + +Mit $a\in\Z$ und $n > 1$ ist die Kongruenz $$ax \equiv b \pmod{n}$$ +genau dann für alle $b\in\Z$ lösbar, wenn $\mathrm{ggT}(a,n) = 1$ gilt, +also wenn $$ax \equiv 1 \pmod{n}$$ lösbar ist. + +::: bsp +**Beispiel** mit $n=27$ und $a=5$: Es gilt $\mathrm{ggT}(5,27) = 1$. +Dann ist $$5 \cdot z \equiv b \pmod{27}$$ lösbar für jedes $b\in\Z$. Es +gilt $$5 \cdot 11 \equiv 1 \pmod{27}$$ und allgemein für +$z = 11 \cdot b$: +$$5 \cdot (11 \cdot b) \equiv (5 \cdot 11) \cdot b \equiv b \pmod{27}.$$ +::: + +Als direkte Konsequenz gilt dann: Mit $a\in\Z$, $n>1$ und +$[a] \in\Z/n\Z$ gilt +$$[a] \text{ ist invertierbar in } \Z/n\Z\quad\iff\quad\mathrm{ggT}(a,n) = 1$$ + +Jene invertierbaren Restklassen in $\Z/n\Z$ bezeichnet man dann als +**prime Restklassen** modulo $n$ und die Menge der Restklassen (modulo +$n$) als **prime Restklassengruppe** $(\Z/n\Z)^*$) (modulo $n$). +Außerdem wird die **Euler'sche $\varphi$-Funktion** für $n\in\N$ +definiert durch +$$\varphi(n) := \begin{cases}1, &\text{wenn } n=1\\\#(\Z/n\Z)^*, &\text{wenn } n>1\end{cases}$$ +wobei +$$\#(\Z/n\Z)^* = \#\{i\in\N \mid i < n \text{ und } \mathrm{ggT}(i,n) = 1 \}.$$ + +::: bsp +**Beispiel**: $$\varphi(p) = p - 1\quad\text{für } p\in\P$$ +$$\varphi(12) = 4 \text{ und } (\Z/n\Z)* = \{ 1,5,7,11 \}$$ +::: + +# Primzahlen + +::: defi +- Zu jeder Zahl $a\in\Z$ und $b\in\N_{>0}$ gibt es eindeutig bestimmte + Zahlen $q,r\in\Z$ mit $$a = qb + r,\quad 0 \leq r < b.$$ Dabei ist + $q$ der **Quotient** und $r$ der **Rest der Division** von $a$ und + $b$. +- Für eine Primzahl $p\in\P$ gilt mit $a,b\in\Z$: + $$p \mid a \cdot b \implies p \mid a \lor p \mid b.$$ +- Die Menge $\P$ der Primzahlen ist unendlich. +::: + +## Fundamentalsatz der Arithmetik + +Jedes $n\in\N \setminus \{0;1\}$ hat eine eindeutige Zerlegung +$$n=p_1^{v_1} \cdot p_2^{v_2} \cdot ... \cdot p_r^{v_r}$$ mit Primzahlen +$p_1 < p_2 < ... < p_r$ und $v_1, ..., v_r \in \N_{>0}$. Diese Zerlegung +nennt man die **Primfaktorzerlegung** von $n$. + +TODO: Erathostenes, ggT, euklidischer Algorithmus + +# Gruppen + +::: defi +Eine **Gruppe** ist ein Paar $(G,*)$ bestehend aus einer *nicht-leeren* +Menge $G$ und einer zweistelligen Operation `\enquote{$*$}`{=tex}, d.h. +einer Abbildung $$*: G \times G \to G: (g,h) \mapsto g * h,$$ sodass +folgende *Gruppenaxiome* gelten: + +1. *Assoziativgesetz*: $(g * h) * k = g * (h * k)\ \forall g,h,k \in G$ +2. *Existenz eines Neutralen*: + $\exists e \in G: \forall g \in G: e * g = g$ +3. *Existenz von Inversen*: + $\forall g \in G: \exists g^{-1} \in G: g^{-1} * g = e$ + +Eine Gruppe $(G,*)$ heißt **abelsch** oder **kummutativ**, wenn $(G,*)$ +zudem noch dem folgenden Axiom genügt: + +4. *Kommutativgesetz*: $g * h = h * g\ \forall g,h \in G$ +::: + +## Eigenschaften + +- Aufgrund der Axiome erhält man folgende Eigenschaften für eine + Gruppe $(G,*)$: + + - Das neutrale Element $e \in G$ ist eindeutig bestimmt und hat + die Eigenschaft $$e * g = g * e = g\quad\forall g \in G$$ + - Mit $g \in G$ ist das inverse Element $g^{-1}$ zu $g$ eindeutig + bestimmt und hat die Eigenschaft $$g^{-1} * g = g * g^{-1} = e$$ + - Für $g,h \in G$ gelten $(g^{-1})^{-1} = g$ und + $(g * h)^{-1} = h^{-1} * g^{-1}$ + +- Häufig wird `\enquote{$*$}`{=tex} die **Gruppenmultiplikation** + genannt. + +- Ist $(G,*)$ eine Gruppe mit endlich vielen Elementen $n\in\N$, so + bezeichnet man mit $\#G = |G| = n$ die **Ordnung** der Gruppe. + +## Kürzungsregeln + +Für die Gruppe $(G,*)$ gilt mit $g,a,b \in G$: + +- $g * a = g * b \implies a = b$ +- $a * g = b * g \implies a = b$ + +## Multiplikative Gruppe + +Wird die Gruppenoperation als Multiplikation und mit +`\enquote{$\cdot$}`{=tex} bezeichnet, so schreibt man + +- für das Neutrale Element $1_G$ bzw. 1 +- für das Inverse zu $g$ $g^{-1}$ oder $\frac{1}{g}$ +- häufig das Multiplikationszeichen nicht, wenn die Bedeutung klar + ersichtlich ist (z.B. $gh$ statt $g \cdot h$) +- für das Produkt von $g1,...,g_n \in G$ + $$\prod_{i=1}^n g_i = g_1 \cdot g_2 \cdot ... \cdot g_n$$ + +Außerdem gelten normale multiplikative Potenzgesetze. Allerdings gilt +$$(g \cdot h)^n = g^n \cdot h^n$$ **nicht** in nicht-abelschen Gruppen, +da z.B. mit $n = 4$ Kommutativität notwendig ist: + +::: bsp +**Beispiel**: +`\begin{splitty}(g \cdot h)^n &= g^n \cdot h^n \\ \implies (g \cdot h)^4 &= g^4 \cdot h^4 \\ \implies (g \cdot h) \cdot (g \cdot h) \cdot (g \cdot h) \cdot (g \cdot h) &= (g \cdot g \cdot g \cdot g) \cdot (h \cdot h \cdot h \cdot h) \\ \implies g \cdot h \cdot g \cdot h \cdot g \cdot h \cdot g \cdot h &= g \cdot g \cdot g \cdot g \cdot h \cdot h \cdot h \cdot h \end{splitty}`{=tex} +::: + +## Additive Gruppe + +Wird die Gruppenoperation als Addition und mit `\enquote{$+$}`{=tex} +bezeichnet, so schreibt man + +- für das Neutrale Element meist $0_G$ bzw. 0 +- für das Inverse zu $g$ meist $-g$ und meist $g - h$ statt $g + (-h)$ +- für die Summe von $g1,...,g_n \in G$ + $$\sum_{i=1}^n g_i = g_1 + g_2 + ... + g_n$$ + +Außerdem gelten normale additive Rechenregeln. Insbesondere muss man bei +Rechnungen aufpassen, die je nach Variablen unterschiedliche Operationen +mit gleichem Symbol nutzen. **Beispiel** mit $g,h \in G$ und +$m,n \in \Z$: + +- $\underbrace{(m + n)}_{\text{Add. in } \Z}g = \underbrace{mg + ng}_{\text{Add. in } G}$ +- $n \cdot \underbrace{(m + n)}_{\text{Add. in } G} = \underbrace{ng + nh}_{\text{Add. in } G}$ +- $0_\Z \cdot g = 0_G$ +- $n \cdot 0_G = 0_G$ + +## Permutationsgruppe + +Eine **Permutation** ist eine bijektive Abbildung einer endlichen Menge +auf sich selbst. Für ein $n\in\N$ verwendet man im Allgemeinen die Menge +$\{ 1,...,n \}$ und schreibt die Permutation +$$\begin{split}\sigma:\quad\{1,...,n\}\quad &\to \quad \{1,...,n\}\\\quad i \quad &\mapsto \quad \sigma(i)\end{split}$$ +als Tabelle +$$\sigma = \begin{pmatrix}1&2&...&n\\\sigma(1)&\sigma(2)&...&\sigma(n)\end{pmatrix}.$$ + +::: bsp +**Beispiel** mit $n=4$: +$$\sigma = \begin{pmatrix}1&2&3&4\\2&3&1&4\end{pmatrix}$$ Die +Permutation (bijektive Abbildung (!)) ist dann +`\begin{gather*}1\mapsto2\\2\mapsto3\\3\mapsto1\\4\mapsto4\end{gather*}`{=tex} +::: + +## Symmetrische Gruppe + +Die **Menge aller Permutationen** von $\{1,...,n\}$ wird mit $S_n$ +bezeichnet und bildet mit der Komposition "$\circ$" von Abbildungen als +Gruppenoperation ("Gruppenmultiplikation") +`\begin{splitty}\circ:\quad S_n\times S_n &\to S_n\\(\sigma,\tau) &\mapsto \sigma \circ \tau\end{splitty}`{=tex} +eine Gruppe $(S_n, \circ)$ die für $n > 2$ nicht abelsch ist. Diese +Gruppe nennt man die **Permutationsgruppe** oder die **Symmetrische +Gruppe der Ordnung $n$**. Es gilt $S_n = \mathrm{Sym}(\{1,...,n\})$. + +Eine Permutation, die nur zwei Elemente vertauscht, heißt +**Transposition** (2-Zykel). + +::: bsp +**Beispiel** 1: +$$\sigma = \begin{pmatrix}1&2&3&4&5&6&7\\2&3&1&4&5&7&6\end{pmatrix}\quad\text{Zykelschreibweise: }\sigma = (1,2,3)(4)(5)(6,7) = (1,2,3)(6,7)$$ +**Beispiel** 2: $$\sigma = (1,2,3)(6,7) = (1,2)(2,3)(6,7)$$ Dann ist +`\begin{splitty}\sigma(7)&=6\\\sigma(6)&=7\\\sigma(4)&=4\\\sigma(5)&=5\\\sigma(1)&=2\\\sigma(2)&=3\\\sigma(5)&=1\end{splitty}`{=tex} +::: + +Hat $\sigma \in S_n$ zwei Zerlegungen in Transpositionen +$\sigma_1,...,\sigma_k\in S_n$ und $\tau_1,...,\tau_l\in S_n$, d.h. +$$\sigma = \sigma_1...\sigma_k=\tau_1...\tau_l,$$ dann gilt +$k\equiv l \pmod{2}$ und man bezeichnet die **Signatur** von $\sigma$ +mit +$$\mathrm{sign}(\sigma) = (-1)^{\text{Anzahl von Transpositionen in einer Darstellung von $\sigma$}}.$$ +Man nennt eine Permutation $\sigma$ **gerade**, wenn +$\mathrm{sign}(\sigma)=1$ und **ungerade**, wenn +$\mathrm{sign}(\sigma) = -1$ ist. + +## Untergruppen + +::: defi +Mit der Gruppe $(G,*)$ mit neutralem Element $e \in G$, heißt die +Teilmenge $U \subset G$ **Untergruppe** von $G$, wenn gilt: + +1. $e \in U$ +2. $g,h \in U \implies g * h \in U$ +3. $g \in U \implies g^{-1} \in U$ +::: + +::: bsp +**Beispiel**: Die Menge der Vielfache einer Zahl $n$, d.h. die Menge +$n\Z = \{ n\cdot k \mid k \in \Z \}$, bildet eine Untergruppe von +$(\Z, +)$. +::: + +## Nebenklassen + +### Motivation + +$\Z = \{ ..., -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, ...\}$, dann ist +$\{...,-3,0,3,6,...\} = 3\Z$ eine Untergruppe von $Z$. +$\{...,-2,1,4,7,...\} = 1+3\Z$ sowie $\{...,-1,2,5,8,...\} = 2+3\Z$ sind +allerdings keine Untergruppen, aber **Nebenklassen**. + +### Definition + +Mit der Untergruppe $U\subset G$ und $g\in G$, ist die +**Linksnebenklasse** von $g$ bezüglich $U$ in $G$ die Menge +$$g * U = \{ g * u \mid u \in U \}.$$ Die **Menge der +Linksnebenklassen** ist dann $$G/U = \{ g * U \mid g \in G \}.$$ Die +**Rechtsnebenklasse** von $g$ bezüglich $U$ in $G$ ist die Menge +$$U * g = \{ u * g \mid u \in U \}.$$ Die **Menge der +Rechtsnebenklassen** ist analog enstprechend +$$U\backslash G = \{ U * g \mid g \in G \}.$$ + +------------------------------------------------------------------------ + +Mit der Untergruppe $U\subset G$ und $g,h \in G$ gilt: + +1. $g * U = h * U \quad\iff\quad h^{-1} * g\quad\in U.$ + + **Beispiel**: $1+3\Z = 10 + 3\Z \implies (-10) + 1\quad\in 3\Z.$ + +2. Je zwei verschiedene Nebenklassen sind disjunkt. + +3. Die Abbildung $f: U \to g*U$ mit $f(u) = g * u$ ist eine Bijektion. + +4. Die Anzahl der Linksnebenklassen von $U$ in $G$ ist gleich der + Anzahl der Rechtsnebenklassen von $U$ in $G$. Diese Anzahl heißt + **Index** $$[G : U] := |G/U| = |U\backslash G|$$ von $U$ in $G$. + +### Satz von Lagrange + +Mit der Untergruppe $U \subset G$ gilt $$|G| = |U| \cdot [G : U].$$ Es +folgt, dass *die Ordnung einer jeden Untergruppe die Gruppenordnung +teilen muss*. + +::: bsp +**Beispiel** bei Primzahlen: Mit $p\in\P$ gilt: Wenn $-1$ ein Quadrat in +$Z/p\Z$ ist, so ist $p-1$ durch $4$ teilbar. + +```{=tex} +\begin{proof} Mithilfe des Satz von Lagrange:\\ +$\exists i \in \Z/p\Z:\ i^2=-1$. Dann ist $U = \{ 1,-1,i,-i \} \subset (Z/p\Z)^*$ mit $|U| = 4$. Es gilt demnach: $$p-1 = |(\Z/p\Z)^*| = |U| \cdot [(\Z/p\Z)^* : U]$$ und deshalb $4 \mid (p-1)$. +\end{proof} +``` +::: + +## Zyklische Gruppen + +Mit der Gruppe $S \subset G$ ist das **Erzeugnis** von $S$ bzw. die von +$S$ **erzeugte Untergrupppe** definiert mit +$$\braket{S} = \bigcap \{ U \subset G \mid U \text{ ist Untergruppe von } G \text{ mit } S \subset U \}.$$Ist +$S = \{ g_1,g_2,... \}$ gegeben, schreibt man +$$\braket{g_1,g_2,...} = \bigcap \{ U \subset G \mid U \text{ ist Untergruppe von } G \text{, die } g_1, g_2, ... \text{ enthält} \}.$$ + +Insbesondere für $g\in G$ ist $\braket{g} = \{ g^k \mid k\in\Z \}$ die +von $g$ **erzeugte zyklische Untergruppe**. Die **Ordnung** von $g$ ist +die Ordnung von $\braket{g}$. + +Allgemein: Ist $G = \braket{g}$ für ein $g\in G$, dann heißt $G$ +zyklisch. + +::: bsp +**Beispiel**: + +1. $(\Z, +)$: $\Z = \braket{1} = \{ k \cdot 1 \mid k\in\Z \}$. +2. $(\Z/n\Z, +)$ ist eine zyklische Gruppe. +3. $((\Z/5\Z)^*, \cdot) \ni [1]$: + $\braket{[1]} = \braket{1_{(\Z/5\Z)^*}} = \braket{1} = \{ [1]^k \mid k\in\Z \} = \{ [1^k] \mid k\in\Z \} = \{ [1] \}$. + $$\braket{[2]} = \{ [2]^0, [2]^1, [2]^2, [2]^3, [2]^4 \}$$ + $$\implies |\braket{[2]}| = 4 \mid (5 - 1) = |(\Z/5\Z)^*|$$ +::: + +Mit der endlichen Gruppe $G$ und $g\in G$ gilt: +$$|\braket{g}| \mid |G|.$$ + +Außerdem gilt mit der Gruppe $G$ und $g\in G$: Die Ordnung von $g$ ist +unendlich und die kleinste positive ganze Zahl $k$ mit $g^k = e$, wobei +$e$ das neutrale Element der Gruppe ist. Demnach folgt: + +### Kleiner Satz von Fermat + +Ist $G$ eine endliche Gruppe, so gilt für alle Elemente $g\in G$: +$$g^{|G|} = e.$$ + +### Satz von Euler + +Mit $n\in \N_{>0}$ und $a \in \{ 1,2,...,n-1 \}$ gilt: Ist $a$ +teilerfremd zu $n$, so gilt $$a^{\varphi(n)} \equiv 1 \pmod{n}.$$ Ist +$n = p$ eine Primzahl, so gilt $$a^{p-1} \equiv 1 \pmod{p}.$$ + +## Klassifikation von zyklischen Gruppen + +Mit den Gruppen $G,H$ heißt die Abbildung $f: G\to H$ **Homomorphismus** +(der Gruppen $G$ und $H$), wenn gilt +$$\forall g,g'\in G: f(g *_G g') = f(g) *_H f(g').$$ + +------------------------------------------------------------------------ + +Ein **Isomorphismus** ist ein bijektiver Homomorphismus. Wenn es einen +Isomorphismus auf zwei Gruppen $G$ und $H$ gibt, heißen diese +**isomorph** und werden geschrieben als $G \cong H$. + +Für eine zyklische Gruppe $G$ gilt: +$$(G,*) \cong (\Z,+)\quad\text{oder}\quad(G,*) \cong (\Z/n\Z, +) \text{ mit } n = |G|.$$ + +------------------------------------------------------------------------ + +Ein **Automorphismus** ist ein Isomorphismus einer Gruppe auf sich +selbst. TODO? + +# Ringe und Körper + +::: defi +Ein **Ring** ist ein Tripel $(R,+,\cdot)$ bestehend aus einer Menge $R$ +zusammen mit zwei zweistellgen Operationen +$$+: R\times R \to R: (g,h) \mapsto g+h\quad \text{\enquote{Addition}}$$ +und +$$\cdot: R\times R \to R: (g,h) \mapsto g\cdot h\quad \text{\enquote{Multiplikation}}$$ +sodass folgende Axiome erfüllt sind: + +1. $(R,+)$ ist eine abelsche Gruppe mit neutralem Element $0_R$. +2. $R$ zusammen mit der Multiplikation `\enquote{$\cdot$}`{=tex} + erfüllt die Axiome + a. *Assoziativgesetz*: + $(g\cdot h) \cdot k = g \cdot (h \cdot k)\quad\forall g,h,k \in R$ + b. *Existenz eines Neutralen*: + $\exists 1_R \in R: \forall g\in R: 1_R \cdot g = g$ +3. *Zwei Distributivgesetze*: $\forall g,h,k \in R:$ + a. $(g+h) \cdot k = g\cdot k + h\cdot k$ + b. $g \cdot (h+k) = g\cdot h + g\cdot k$ +4. $0_R \neq 1_R$ + +Ein Ring $(R,+,\cdot)$ heißt **kommutativ**, wenn zudem noch die +Multiplikation dem folgenden Axiom genügt: + +5. *Kommutativgesetz*: $g\cdot h = h \cdot g\quad\forall g,h\in R$ + +Ein kommutativer Ring $(R,+,\cdot)$ heißt **Körper**, falls zusätzlich +gilt + +6. $(R\setminus \{0_R\},\cdot)$ eine abelsche Gruppe mit $1_R$ +::: + +TODO: Unterschied Ring Körper 9.3 + +::: bsp +**Beispiele**: + +- $\Z/n\Z$ ist ein kommutativer Ring. +- $\Z/p\Z$ ist ein Körper für $p\in\P$. +::: + +## Rechenregeln + +Mit Körper $K$, $x,y,z \in K$ und $u,v \in K \setminus \{ 0 \}$ gilt: + +- $-(-x) = x$ +- $x + y = z \iff x = z - y$ +- $-(x + y) = -x -y$ +- $0 \cdot x = x \cdot 0 = 0$ +- $(-x) \cdot y = x \cdot (-y) = -(x \cdot y)$ +- $(-x) \cdot (-y) = x \cdot y$ +- $x \cdot (y - z) = x \cdot y - x \cdot z$ +- $(x^{-1})^{-1} = x, \text{ für } x \neq 0$ +- $x \cdot y = 0 \iff x = y \text{ oder } y = 0$ +- $z \cdot x = z \cdot y,\ z \neq 0 \implies x = y$ +- $\frac{x}{u} \cdot \frac{y}{v} = \frac{x \cdot y}{u \cdot v}$ +- $\frac{x}{u} + \frac{y}{v} = \frac{x \cdot v + y \cdot u}{u \cdot v}$ + +## Unterringe + +Sei $(R,+,\cdot)$ ein Ring und $S \subset R$. Dann ist $(S,+,\cdot)$ ein +**Unterring**, wenn folgende Unterringkriterien erfüllt sind: + +1. $(S,+)$ ist eine Untergruppe von $(R,+)$. +2. $1_R \in S$. +3. $g,h \in S \implies g\cdot h \in S$. + +## Unterkörper/Teilkörper + +Sei $(K,+,\cdot)$ ein Körper und $L\subset K$. Dann ist $L$ ein +**Teilkörper**/**Unterkörper**, von $K$, wenn folgende Bedingungen +erfüllt sind: + +1. $g,h \in L \implies g+h,g\cdot h \in L$. +2. $0,1 \in L$. +3. $g\in L \implies -g \in L$. +4. $g\in L, g\neq 0 \implies g^{-1} \in L$. + +## Chinesischer Restsatz + +### Ziel + +Sei $m,n\geq 1$ und $a,b\in\Z$. Finde $x\in\Z$: $$x \equiv a \pmod{n}$$ +$$x \equiv b \pmod{m}$$ + +::: bsp +**Beispiele**: $$x \equiv 4 \pmod{7}$$ $$x \equiv 2 \pmod{6}$$ + +**Schreibe**: +$x = 4 \cdot ?_1 + 2 \cdot ?_2 \equiv 4 \cdot 1 + 2 \cdot 0 \pmod{4} \equiv 4 \cdot 0 + 2 \cdot 1 \pmod{6}$ + +**Demnach**: + +Für $?_1$ finde +$k\in\Z: 6\cdot k \equiv 1 \pmod{7} \implies 6^{-1} = 6$. + +Für $?_2$ finde +$k\in\Z: 7\cdot l \equiv 1 \pmod{6} \implies 7^{-1} = 1$. +::: + +### Definition + +Seien $m_1,...,m_r > 1$ paarweise teilerfremde Zahlen, $r>1$ und +$a_1,...,a_r \in \Z$ beliebig. Dann existiert ein $x\in\Z$ mit +$$x \equiv a_1 \pmod{m_i}\quad\forall i = 1,...,r$$ und je zwei Lösungen +$x,x'$ dieser Kongruenzen erfüllen +$$x \equiv x' \pmod{m},\quad m := \prod_{i=1}^r m_i.$$ + +```{=tex} +\begin{proof} Zunächst wird die \textit{Existenz} bewiesen. Es sei $n_i := \frac{m}{m_i} = m_1 \cdot ... \cdot m_{i-1} \cdot m_{i+1} \cdot ... \cdot m_r$. Dann ist $\mathrm{ggT}(m_i,n_i) = 1$ und nach 8.19 existiert $n_i^*$, sodass $[n_i^*] := [n_i]^{-1} \in \Z/m_i\Z$ ist, d.h. $n_i^* \cdot n_i \equiv 1 \pmod{m_i}$. Wenn nun $x := a_1n_1n_1^* + a_2n_2n_2^* + ... + a_rn_rn_r*$, gilt nach Konstruktion $m_i \mid n_j$ für $i\neq j$ und damit $a_jn_jn_j^* \equiv 0 \pmod{m_i}$ und daher $$x \equiv a_in_in_i^* \pmod{m_i} \equiv a_i \pmod{m_i}.$$ +Um die \textit{Eindeutigkeit} zu zeigen, seien $x, x'$ Lösungen der Kongruenzen (9.1). Dann gilt $x \equiv x' \pmod{m_i}$ für alle $i=1,...,r$ und daher auch $m_i \mid (x-x')$. Da dies für alle $i$ erfüllt ist, gilt auch $m \mid x$, woraus die Behauptung bewiesen ist. +\end{proof} +``` +::: bsp +**Beispiel**: $$x \equiv 6 \pmod{30}$$ $$x \equiv 2 \pmod{7}$$ Anwendung +des chinesischen Restsatzes: Setze $m_1 = \frac{m_1m_2}{m_1} = m_2 = 7$ +und $m_2 = \frac{m_1m_2}{m_2} = m_1 = 30$. + +- Bestimme Inverse von $n_1$ und $n_2$: + `\begin{splitty}30 &= 4\cdot 7 + 2\\7 &= 3 \cdot 2 + 1\\2 &= 2 \cdot 1 + 0\end{splitty}`{=tex} + und Rückeinsetzen: + `\begin{splitty}1 &= 7 - 3 \cdot 2\\&= 7 - 3 \cdot (30 - 4 \cdot 7)\\&= 13 \cdot 7 - 3 \cdot 30\end{splitty}`{=tex} + Also $13 \cdot 7 \equiv 1 \pmod{30}$. +- Lösung: + $$x = a_1n_1n_1^* + a_2n_2n_2^* = a_1 \cdot 7 \cdot 13 + a_2 \cdot 30 \cdot 4 = 6 \cdot 7 \cdot 13 + 2 \cdot 4 \cdot 30.$$ + Demnach: $$x \equiv 156 \pmod{210},$$ d.h. der nächste Vollmond am + Sonntag ist in $156$ Tagen und wiederholt sich dann alle $210$ Tage. +::: + +# Körper der komplexen Zahlen + +::: defi +Motivation: Lösung für $x^2 = -1$ mit $x = i$ und $i^2 = -1$. Also: +Konstruktion von $i$, damit dies erfüllt ist. + +Man kann den Körper der komplexen Zahlen konstruieren, indem man den +Körper $\R$ der reelen Zahlen und die Menge +$C := \R \times \R = \{(a,b) \mid a,b\in\R\}$ betrachtet mit den +folgenden Operationen: +`\begin{splitty}+:\quad C\times C\quad &\to \quad C\\((a,b),(c,d))&\mapsto (a,b)+(c,d) := (a+c, b+d)\end{splitty}`{=tex}und`\begin{splitty}\cdot:\quad C\times C\quad &\to \quad C\\((a,b),(c,d))&\mapsto (a,b)\cdot(c,d) := (ac - bd, ad + bc).\end{splitty}`{=tex}Also +definiert man: +`\begin{splitty}(x,0),\quad x\in\R &:= x\\(0,1)&:=i,\end{splitty}`{=tex} +da dann gilt: $$i^2 = (0,1)(0,1) = (-1,0) = -1.$$Für $z=(x,y)\in C$ +gilt: $$z = (x,0) + (0,1)(y,0) = x + iy.$$Außerdem gilt in +$\C$:`\begin{splitty}(x+iy)(u+iv) &= (xu + i^2yv) + i(xv+yu) = (xu - yv) + i(xv+yu).\end{splitty}`{=tex}Das +multiplikative Inverse von $x+iy$ ist demnach: +$$u+iv = \frac{x}{x^2 + y^2} - \frac{iy}{x^2+y^2}.$$ +::: + +## Operationen + +1. **Betragsfunktionen**: + `\begin{splitty}|\cdot|:\quad\C\quad&\to\quad\R_{\geq0}\\x+iy&\mapsto\sqrt{x^2+y^2}\end{splitty}`{=tex} +2. **Komplexe Konjugation**: + `\begin{splitty}\bar{\cdot}:\quad\C\quad&\to\quad\C\\z = x + iy &\mapsto \bar{z} := x - iy.\end{splitty}`{=tex} +3. **Realteil**: + `\begin{splitty}\mathrm{Re}:\quad\C\quad&\to\quad\R\\x+iy &\mapsto\quad x.\end{splitty}`{=tex} +4. **Imaginärteil**: + `\begin{splitty}\mathrm{Im}:\quad\C\quad&\to\quad\R\\x+iy &\mapsto\quad y.\end{splitty}`{=tex} + +## Geometrische Deutung + +### Graph von $z$ + +::: visu +Mit $z = x + yi = 4 + 5i$: + +```{=tex} +\begin{center}\begin{tikzpicture} +\begin{axis}[axis lines=center,xmin=-1,xmax=5,ymin=-1,ytick={-1,...,6},ymax=6,minor tick num=1,ticks=both,yticklabels={$-i$, $0$, $i$, $2i$, $3i$, $4i$, $5i$, $6i$}] +\addplot[black,mark=*] coordinates {(4,5)} {}; +\addplot[ultra thick,dashed,red] coordinates { (0,0) (4,0) } node[pos=0.5,above] {$\text{Re}(z)=4$}; +\addplot[,dashed,red] coordinates { (4,0) (4,5) } node[pos=0.5,left] {$\text{Im}(z)=5$}; + +\node [above,red] at (axis cs: 4,5) {$4+5i$}; +\end{axis} +\end{tikzpicture}\end{center} +``` +::: + +### Vektoraddition + +::: visu +Mit $z = x + yi = 1 + 3i$ und $w = u + vi = 4 + 2i$ und +$z + w = 5 + 5i$: + +```{=tex} +\begin{center}\begin{tikzpicture} +\begin{axis}[axis lines=center,xmin=-1,xmax=6,ymin=-1,ytick={-1,...,6},ymax=6,minor tick num=1,ticks=both,yticklabels={$-i$, $0$, $i$, $2i$, $3i$, $4i$, $5i$, $6i$}] +\addplot[black,mark=*] coordinates {(1,3)} {}; +\addplot[black,mark=*] coordinates {(5,5)} {}; +\addplot[black,mark=*] coordinates {(4,2)} {}; + +\addplot[red] coordinates { (0,0) (1,3) } node[pos=1,left] {$z$}; +\addplot[red] coordinates { (0,0) (5,5) } node[pos=1,above] {$z+w$}; +\addplot[red] coordinates { (0,0) (4,2) } node[pos=1,right] {$w$}; + +\addplot[dashed,red] coordinates { (1,3) (5,5) }; +\addplot[dashed,red] coordinates { (4,2) (5,5) }; +\end{axis} +\end{tikzpicture}\end{center} +``` +::: + +### Betrag + +::: visu +Mit $z = x + iy = 4 + 5i$, entspricht der Betrag +$|z| = \sqrt{x^2 + y^2} = \sqrt{4^2 + 5^2} \approx 6.4 = r$ der +euklidischen Länge des Vektors $z$: + +```{=tex} +\begin{center}\begin{tikzpicture} +\begin{axis}[axis lines=center,xmin=-1,xmax=5,ymin=-1,ytick={-1,...,6},ymax=6,minor tick num=1,ticks=both,yticklabels={$-i$, $0$, $i$, $2i$, $3i$, $4i$, $5i$, $6i$}] +\addplot[black,mark=*] coordinates {(4,5)} {}; +\addplot[red] coordinates { (0,0) (4,5) } node[pos=0.5,above] {$r$}; +\addplot[ultra thick,dashed,red] coordinates { (0,0) (4,0) } node[pos=0.5,above] {$\text{Re}(z)=4$}; +\addplot[dashed,red] coordinates { (4,0) (4,5) } node[pos=0.5,left] {$\text{Im}(z)=5$}; + +\node [above,red] at (axis cs: 4,5) {$4+5i$}; +\end{axis} +\end{tikzpicture}\end{center} +``` +::: + +### Einheitskreis + +$$z = \cos(\alpha) + i\sin(\alpha)$$ + +TODO. Tikz weird af + +**Euler-Formel**: $$\C\ni e^{i\alpha} = \cos(\alpha) + i\sin(\alpha)$$ +mit $\alpha$ als Winkel im Bogenmaß, sowie +$$|e^{i\alpha}| = 1,\quad\forall\alpha\in\R.$$ + +### Polarkoordinaten + +Mit dem Punkt $z' = \frac{z}{|z|}$ gilt: +$$z = x+iy = |z| \cdot \frac{z}{|z|} = |z| \cdot z' = |z| \cdot e^{i\alpha}.$$ +**Polarkoordinatendarstellung**: +$z = r \cdot e^{i\alpha} = r(\cos(\alpha) + i\sin(\alpha))$ + +TODO: Tikz Darstellung der Multiplikation + +`\begin{splitty}(r\cdot e^{i\alpha})(r'\cdot e^{i\alpha'}) &= r \cdot r' (\cos(\alpha) + i\sin(\alpha))(\cos(\alpha')+i\sin(\alpha'))\\&= ...\\&= r\cdot r' \cdot e^{i(\alpha+\alpha')}\end{splitty}`{=tex} + +## Gleichungen in $\C$ + +### Lineare Gleichung + +Finde $z\in\C$ mit $u,v\in\C$ und $u\neq0$: +`\begin{splitty} uz+v &= 0\\ \iff z &= -u^{-1} \cdot v \end{splitty}`{=tex} +Ist $u = a + ib$ und $v = c + id$ mit $a,b,c,d\in\R$, dann ist +$$z = -\frac{v}{u} = -\frac{c+id}{a + ib} \cdot \frac{a-ib}{a-ib} = -\frac{(ac+bd) - i(bc-ad)}{a^2+b^2} = -\frac{ac+bd}{a^2+b^2} + i\frac{bc-ad}{a^2+b^2}$$ + +### Quadratische Gleichungen + +Finde $z\in\C$ mit Koeffizienten $a,b,c\in\R,\quad a\neq0$, sodass +`\begin{splitty}az^2 + bz + c &= 0\\\iff a(z^2 + \frac{b}{a} \cdot z + \frac{z}{a}) &= 0\\\iff^{a\neq0} z^2 + \frac{b}{a}\cdot z + \frac{b^2}{4a^2} &= \frac{b^2}{4a^2} - \frac{c}{a}\\\iff (z+\frac{b}{za})^2 &= \frac{b^2-4ac}{4a^2}\\\iff z_{1,2} &= \pm \sqrt{\frac{b^2-4ac}{4a^2}} - \frac{b}{2a}\\&=\frac{-b\pm\sqrt{b^2-4ac}}{2a}\end{splitty}`{=tex} +$$z_{1,2} = \begin{cases}-\frac{b}{2a}\in\R,&\text{wenn } \Delta = 0\\\frac{-b\pm\sqrt{b^2-4ac}}{2a}\in\R,&\text{wenn } \Delta > 0\\\frac{-b\pm i\sqrt{4ac-b^2}}{2a} = \frac{-b}{2a}\pm i\frac{\sqrt{4ac-b^2}}{2a}, &\text{wenn } \Delta < 0\end{cases}$$ + +### Einheitswurzeln + +Sei $0\neq\omega = r \cdot e^{i\alpha} \in \C$ und $n\in\N$. Finde +$z\in\C$ mit $$z^n = \omega.$$ **Polarkoordinatendarstellung**: Betrag +und Argument von $z^n$ gleich $r$ und $\alpha$. Sei +$z = s\cdot e^{i\beta}$, dann sucht man $(s,\beta)$, sodass +$$z^n = s^n \cdot e^{i(n\beta)} = r \cdot e^{i\alpha} = \omega$$ also +$s^n = r$ und $n\beta = \alpha + 2 \pi k$ mit $k\in\Z$. **Also**: +$s = \sqrt[n]{r}$ und $\beta_k \frac{\alpha+2\pi k}{n}$ mit +$k=0,...,n-1$. Es gibt also $n$ Lösungen +$z_k = \sqrt[n]{r} \cdot e^{i\beta k},\quad k=0,...,n-1$. + +# Polynomringe + +::: defi +Sei $R$ ein kommutativer Ring. + +1. Ein **Polynom** über dem Ring $R$ in der Unbestimmten $X$ ist ein + Ausdruck der Form + $$f=f(x)=\alpha_nX^n+\alpha_{n-1}X^{n-1}+...+\alpha_0X^0=\sum_{i=0}^n \alpha_iX^i$$ + mit $n\in\N$ und **Koeffizienten** $\alpha_i\in R,\ i=0,...,n$. + Genauer ist $\alpha_i$ der **Koeffizient von $f$ zum Grad $i$**. Ist + $a_n=1$, so nennt man das Polynom $f$ **normiert**. +2. Ist $\alpha_n\neq0$, so ist $n$ der **Grad** $\mathrm{grad}(f)$ des + Polynoms $f$. Man definiert den Grad des **Nullpolynoms** $f=0$ als + $\mathrm{grad}(0) = -\infty$. +3. Ist $\mathrm{grad}(f)=2$, dann nennt man + $f(X) = \alpha_2X^2+\alpha_1X+\alpha_0$ auch **quadratische + Polynome**. Ist $\mathrm{grad}(f)=1$, dann spricht man auch von + **linearen Polynomen** $f(X)=\alpha_1X+\alpha_0$, und für + $\mathrm{grad}(f)=0$ von den **konstanten Polynomen** + $f(X)=\alpha_0$. +::: + +Ein **Polynomring** $R[X]$ ist dann die Menge aller Polynome in der +Unbestimmten $X$ mit Koeffizienten in einem Ring $R$, weshalb dieser +auch die Ringaxiome erfüllt. + +$R[X]$ besitzt die folgenden Operationen: + +1. $$\left(\sum_{i\in\N} \alpha_iX^i\right)+\left(\sum_{i\in\N} \beta_iX^i\right) = \sum_{i\in\N}(\alpha_i+\beta_i)X^i$$ +2. $$\left(\sum_{i\in\N} \alpha_iX^i\right)\cdot\left(\sum_{i\in\N} \beta_iX^i\right) = \sum_{i\in\N}\left(\sum_{k+l=i}(\alpha_k+\beta_l)X^i\right)$$ + +------------------------------------------------------------------------ + +Für $f,g\in R[X]$ gilt: +$$\mathrm{grad}(f+g)\leq\mathrm{max}(\mathrm{grad}(f),\mathrm{grad}(g))$$ +$$\mathrm{grad}(f\cdot g)\leq\mathrm{grad}(f) + \mathrm{grad}(g)$$ Ist +$R=K$ ein Körper, so gilt sogar: +$$\mathrm{grad}(f\cdot g)=\mathrm{grad}(f) + \mathrm{grad}(g)$$ + +## Polynomdivision + +Von nun an ist $R=K$ ein beliebiger Körper. + +------------------------------------------------------------------------ + +Seien $f,g\in K[X]$ und $g\neq0$ Polynome mit Koeffizienten in $K$. Dann +existieren eindeutig bestimmte Polynome $q,r\in K[X]$ mit +$$f=q\cdot g+r\quad\text{mit } \mathrm{grad}(r)<\mathrm{grad}(g).$$ Man +nennt $q$ den **Quotienten** und $r$ den **Rest der Division** von $f$ +durch $g$. + +::: bsp +**Beispiel**: + +```{=tex} +\polylongdiv[style=C]{X^4+2X^3-X+2}{3X^2-1} +``` +::: + +Mit $f,g\in K[X]$, definiert man **$g$ teilt $f$** oder **$g$ ist ein +Teiler von $f$**, wenn +$$g \mid f\quad:\iff\quad\exists q\in K[X]: f = g\cdot q.$$ Falls $g$ +kein Teiler von $f$ ist, so schreibt man $g \nmid f$. + +::: bsp +**Beispiel**: Das Polynom $X+1$ ist ein teiler von $X^2-1$ in $\R[x]$, +da $$X^2-1 = (X+1)(X-1) = X^2 - X + X - 1.$$ +::: + +Ein Polynom $f\in K[X]$ heißt **reduzibel**, wenn es nicht-konstante +Polynome $g,h\in K[X]$ gibt, sodass $f=g\cdot h$ gilt. Andernfalls heißt +$f$ **irreduzibel**. + +::: bsp +**Beispiel**: $X^2+1$ ist irreduzibel in $\R[X]$, aber reduzibel in +$\C[x]$, da $X^2 + 1 = (X - i)(X + i)$ gilt. +::: + +## Euklidischer Algorithmus + +------------------------------------------------------------------------ + +Ein Polynom $p\in K[X]$ ist **gemeinsamer Teiler** von Polynomen +$f,g\in K[X]$, wenn $p$ ein Teiler von $f$ und ein Teiler von $g$ ist. +Wir nennen $$p=\mathrm{ggT}(f,g)$$ einen **größten gemeinsamen Teiler** +von $f$ und $g$, falls $p$ durch jeden gemeinsamen Teiler von $f$ und +$g$ teilbar ist. Man nennt $p$ den **normierten größten gemeinsamen +Teiler**, wenn $p=\mathrm{ggT}(f,g)$ normiert ist. + +------------------------------------------------------------------------ + +Seien $f,g\in K[X]$, $g\neq0$ und +$\mathrm{grad}(f)\geq\mathrm{grad}(g)$. Setze man $r_0=f$ und $r_1=g$ +und berechne für $j=0,1,...$ die Division von $r_j$ durch $r_{j+1}$ mit +Rest $r_{j+2}$ bis $r_{j+2}=0$ gilt, d.h. finde $q_j\in K[X]$ so, dass +$$r_j=q_jr_{j+1}+r_{j+2}\quad\text{(mit } 0\leq\mathrm{grad}(r_{j+2}) < \mathrm{grad}(r_{j+1}))$$ +erfüllt ist. Ist $n=j+1\in\N$ gefunden mit $r_{n+1}=0$, dann gilt +$r_n=\mathrm{ggT}(f,g)$. + +TODO: Beispiel + +------------------------------------------------------------------------ + +Jedes nicht-konstante Polynom $f\in K[X]$ lässt sich als Produkt +irreduzible Polynome aus $K[X]$ darstellen. Diese Darstellung ist bis +auf die Reihenfolge und die Multiplikation mit konstanten Polynomen +eindeutig. + +## Nullstellen von Polynomen + +Ist $f\in K[X]$ ein Polynom mit **Nullstelle** $x_0\in K$, d.h. +$f(x_0) = 0$, so ist das Polynom (auch **Linearfaktor** genannt) +$g(X) = (X = x_0)$ ein Teiler von $f$. + +------------------------------------------------------------------------ + +Sei $0\neq f\in K[X]$, dann besitzt $f$ nur endlich viele paarweise +verschiedenen Nullstellen $\alpha_1,...,\alpha_r\in K$, wobei +$r \leq \mathrm{grad}(f)$ gilt. Weiter existieren +$n_1,...,n_r\in\N_{>0}$ sowie ein Polynom $g\in K[X]$ ohne Nullstellen +in $K$ mit $$f = \prod_{i=1}^r (X - a_i)^{n_i} \cdot g.$$ Dabei sind die +Exponenten $n_i$ sowie das Polynom $g$ eindeutig durch $f$ bestimmt. Wir +nennen $n_i$ die **Vielfachheit** der Nullstelle $a_i$. + +### Anzahl der Nullstellen + +Ein Polynom $f\in K[X]$ vom Grad $\mathrm{grad}(f) = n \geq 0$ hat +höchstens $n$ Nullstellen. + +### Fundamentalsatz der Algebra + +Jedes Polynom $f\in\C[X]$ zerfällt in Linearfaktoren, d.h. es lässt sich +als Produkt von Linearfaktoren schreiben. + +# Vektorräume + +::: defi +1. Ein **$K$-Vektorraum** ist eine Menge $V$, auf der eine (innere) + Verknüpfung + `\begin{splitty}+:\quad V\times V\quad&\to\quad V\\(u,v)\quad&\mapsto\quad u+v\end{splitty}`{=tex} + und eine **skalare Multiplikation** (äußere Verknüpfung) + `\begin{splitty}\cdot:\quad K\times V\quad&\to\quad V\\(\lambda,v)\quad&\mapsto\quad\lambda\cdot v\end{splitty}`{=tex} + definiert sind, sodass folgende **Vektorraumaxiome** erfüllt sind: + 1. $(V,+)$ ist eine abelsche Gruppe + 2. *Assoziativgesetz*: + $\forall \lambda,\gamma\in K \land v\in V: \lambda (\gamma \cdot v) = (\lambda \cdot \gamma) v$ + 3. *Neutrales Element*: $\forall v\in V: 1 \cdot v = v$ + 4. *Distributivgesetze*: + 1. $\forall \lambda\in K \land u,v\in V: \lambda \cdot (u+v) = \lambda \cdot u + \lambda \cdot v$ + 2. $\forall \lambda,\gamma\in K \land u\in V: (\lambda + \gamma) \cdot u = \lambda \cdot u + \gamma \cdot u$ +2. Die Elemente von $V$ heißen **Vektoren** und die Elemente in $K$ + **Skalare**. Das neutrale Element der Gruppe $(V,+)$ nennt man den + **Nullvektor** $0$. +3. Für $K=\R$ spricht man von einem **reelen Vektorraum** und für + $K=\C$ von einem **komplexen Vektorraum**. +::: + +::: bsp +**Beispiele**: + +1. $\R^n$: $n$-dimensionaler euklidischer Raum, welcher alle $n$-Tupel + der reelen Zahlen enthält. $\R^2$ ist entsprechend der klassische + zweidimensionale Raum mit Vektor $(x,y)^\top$; analog $\R^3$ mit + Vektor $(x,y,z)^\top$. $\R^n$ ist erweiterbar zu $\C^n$ und enthält + entsprechend zusätzlich die komplexen Zahlen. +2. Funktionenräume: Die Menge aller $K$-wertigen Abbildungen + $\mathrm{Abb}(X, K) = \{f: X \to K\}$. Dann gilt: + $$(f+g)(x) = f(x) + g(x),\quad\forall x\in X,$$ + $$(\lambda \cdot f)(x) = \lambda \cdot f(x),\quad\forall x\in X.$$ +3. Der Polynomring $K[X]$ über einem Körper $K$ ist ein $K$-Vektorraum. + Die Ringeigenschaften von $K[X]$ liefern eine Addition, die man als + Vektoraddition interpretieren kann. Die skalare Multiplikation mit + $\lambda\in K$ lässt sich als Multiplikation in $K[X]$ definieren, + indem man den Skalar $\lambda$ als konstantes Polynom mit dem Wert + $\lambda$ identifiziert (d.h. als Polynom + $\lambda X^0 = \lambda\in K[X]$). +::: + +## Unterräume + +### Untervektorraum + +::: defi +Mit dem $K$-Vektorraum $V$ und $U\subset V$ ist $U$ ein +$K$-**Untervektorraum** von $V$, wenn folgende Axiome erfüllt sind: + +1. $U\neq\emptyset$ +2. $u,v\in U\quad\implies\quad u+v\in U$ +3. $u\in U,\ \lambda\in K\quad\implies\quad\lambda u\in U$ + +Kurz spricht man auch von einem **Unterraum** $U$ von $V$. +::: + +::: bsp +**Beispiele**: + +1. Jeder $K$-Vektorraum $V$ hat die trivialen Unterräume $\{0\}$ und + $V$. +2. Die Menge aller Polynome vom Grad kleiner gleich $n\in\N$ + $$K[X]_{\leq n} = \{f\in K[X] \mid \mathrm{grad}(f) \leq n\}$$ ist + ein Unterraum von $K[X]$. Die Addition und Multiplikation können + jeweils den Grad nicht gehören und der Raum ist somit abgeschlossen. +::: + +## Familie von Vektoren + +::: defi +Eine Familie ist eine geordnete Ansammlung von Elementen. TODO: Mehr. +::: + +Mit der Familie von Untervektorräumen von $V$ namens $(U_i)_{i\in I}$ +ist auch $$\bigcap_{i\in I} U_i \text{ ein Untervektorraum von } V.$$ + +TODO: (Generell) TikZ aus Gekritzel? + +## Lineare Hülle {#lspan} + +::: defi +Mit der Familie von Vektoren in $V$ $\mathcal{F} = (v_i)_{i\in I}$ ist +eine **Linearkombination** von $\mathcal{F}$ (oder über $\mathcal{F}$) +ein Element der Form +$$\sum_{i\in I} \lambda_i v_i \in V,\quad \text{ wobei } \lambda_i \in K \text{ und } \lambda_i\neq0 \text{ für höchstes endlich viele } i\in I.$$ +Die Menge aller Linearkombinationen von $\mathcal{F}$ in $V$ wird als +**Erzeugnis** (**lineare Hülle**, **Spann**) von $\mathcal{F}$ +bezeichnet und mit +$$\mathrm{Lin}(\mathcal{F}) = \mathrm{Lin}((v_i)_{i\in I}) = \left\{ v\in V \biggm| v \text{ ist Linearkombination über } \mathcal{F} \right\}$$ +notiert. Dabei nennt man $\mathcal{F} = (v_i)_{i\in I}$ ein +**Erzeugendensystem** von $\mathrm{Lin}(\mathcal{F})$. Es gilt außerdem +$\mathrm{Lin}() = \{0\}$. +::: + +Eine **Linearkombination** von einer Familie von Vektoren +$\mathcal{F} = (v_1,...,v_n)$ in $V$ ist ein Element der Form +$$\mathrm{Lin}(\mathcal{F}) = \mathrm{Lin}(v_1,...,v_n) = \left\{\sum_{i=1}^n \lambda_iv_i \biggm| \lambda_i\in K, i\in I\right\}.$$ + +::: bsp +**Beispiele**: + +1. Die lineare Hülle der $n$ Koordinateneinheitsvektoren + (Basisvektoren) von $\R^n$ ist gerade wieder $\R^n$. +2. Die lineare Hülle von den Vektoren $(1,2)^\top$, $(3,6)^\top$ und + $(-2,-4)^\top$ ist die Gerade + $\{\vec{r}\mid\vec{r}=t(1,2)^\top,t\in\R\}$ da diese Gerade durch + jeden Vektor verläuft (bzw. Ergebnis einer Linearkombination ist). +3. Ist $V$ ein $\R$-Vektorraum $\R^3$ und $\mathcal{F} = (v_1,v_2)$ mit + $v_1 = (1,1,0)$ und $v_2 = (1,0,0)$ in $\R^3$, gilt + $$\mathrm{Lin}(\mathcal{F}) = \mathrm{Lin}(v_1,v_2) = \{(\lambda_1+\lambda_2,\lambda_1,0)\mid\lambda_1,\lambda_2\in\R\} = \{(\lambda_1',\lambda_2',0)\mid\lambda_1',\lambda_2'\in\R\}.$$ +::: + +::: visu +**Visualisierung** in $\R^3$. Zuerst mit $\vec{u}=(0,1,1)^\top$ und +$\vec{v}=(1,0,1)^\top$: + +```{=tex} +\begin{center}\begin{tikzpicture} +\begin{axis}[xlabel={$x$},ylabel={$y$},zlabel={$z$}] + \addplot3[surf, mesh] + {x+y}; + \fill[red] (0,0,0) circle (2pt); + \draw[->, ultra thick] (0,0,0) -- node [above] {$\vec{u}$} (0,3,3); + \draw[->, ultra thick] (0,3,3) -- node [above] {$\vec{v}$} (3,3,6); + \draw[->, ultra thick, blue] (0,0,0) -- node [above] {$\vec{k}$} (3,3,6); +\end{axis} +\end{tikzpicture}\end{center} +``` +Es entsteht ein linearkombinierter Vektor (in diesem Fall +$\vec{k} = 3\vec{u} + 3\vec{v} = (3,3,6)^\top$). Durch diesen Vektor +lässt sich entsprechend jeglicher Punkt auf der entstandenen Ebene (= +lineare Hülle) bestimmen. Nun kommt ein dritter Vektor $\vec{w}=(0,0,1)$ +hinzu: + +```{=tex} +\begin{center}\begin{tikzpicture} +\begin{axis}[xlabel={$x$},ylabel={$y$},zlabel={$z$}] + \addplot3[surf, mesh] + {x+y-8}; + \fill[red] (0,0,0) circle (2pt); + \draw[->, ultra thick] (0,0,0) -- node [above] {$\vec{u}$} (0,3,3); + \draw[->, ultra thick] (0,3,3) -- node [above] {$\vec{v}$} (3,3,6); + \draw[->, ultra thick] (3,3,6) -- node [right] {$\vec{w}$} (3,3,-2); + \draw[->, ultra thick, blue] (0,0,0) -- node [above] {$\vec{k}$} (3,3,-2); +\end{axis} +\end{tikzpicture}\end{center} +``` +$\vec{w}$ dient nun also als `\enquote{Veschiebungs}`{=tex}-Vektor, +welcher die Ebene in $z$-Richtung verschieben kann (im Bild mit Faktor +$-8$). Damit ergibt sich, dass die lineare Hülle der drei Vektoren nun +den ganzen Raum $\R$ umfasst. +::: + +Ist $\mathcal{F} = (v_i)_{i\in I}$ eine Familie von Vektoren in $V$, +dann ist $\mathrm{Lin}(\mathcal{F})$ ein Untervektorraum von $V$ und es +gilt $$\forall i\in I: v_i\in\mathrm{Lin}(\mathcal{F}).$$ + +------------------------------------------------------------------------ + +Ist $\mathcal{F} = (v_i)_{i\in I}$ eine Familie von Vektoren in $V$ und +$M = \{v_i\mid i\in I\}$ die Menge der Vektoren aus $\mathcal{F}$, dann +gilt +$$\mathrm{Lin}(\mathcal{F}) = \underset{U\text{ Unterraum von } V}{\bigcap_{M\subset U\subset V}} U.$$ + +------------------------------------------------------------------------ + +Existiert für einen Unterraum $U\subset V$ eine Familie von Vektoren +$\mathcal{F} = (v_i)_{i\in I}$, sodass $U = \mathrm{Lin}(\mathcal{F})$ +gilt, dann nennt man $\mathcal{F}$ ein **Erzeugendensystem** von $U$, +bzw. **$U$ wird von $\mathcal{F}$ erzeugt**. Ist $\mathcal{F}$ endlich, +so ist $U$ **endlich erzeugt** (von $\mathcal{F}$). + +## Lineare Unabhängigkeit + +::: defi +1. Eine Familie $\mathcal{F} = (v_i)_{i\in I}$ in V heißt genau dann + **linear abhängig**, wenn eine Linearkombination mit mindestens + einem Koeffizienten ungleich $0$ existiert, sodass mit $J\subset I$ + gilt + $$\sum_{i\in J} \lambda_iv_i = 0,\quad\exists i\in J: \lambda_i \neq 0.$$ +2. Dieselbe Familie $\mathcal{F}$ heißt genau dann **linear + unabhängig**, wenn diese nicht linear abhängig ist - also wenn jede + Darstellung der $0$ mittels einer Linearkombination ausschließlich + triviale Koeffizienten besitzt: + $$\sum_{i\in J} \lambda_iv_i = 0\quad\implies\quad\forall i\in J: \lambda_i=0.$$ +3. Dieselbe Familie $\mathcal{F}$ ist außerdem ganau dann linear + unabhängig, wenn sich jeder Vektor $v\in\mathrm{Lin}(\mathcal{F})$ + in eindeutiger Weise als Linearkombination aus Vektoren von + $\mathcal{F}$ schreiben lässt. +::: + +::: bsp +**Beispiele** bzw. vereinfachte Erklärung: + +1. Eine Vektorfamilie ist **linear abhängig**, wenn mindestens ein + Vektor bereits durch eine Linearkombination eines oder mehrerer + anderen Vektoren der Familie ersetzt werden könnte (er ist also + redundant für den linearen Spann). Das heißt der lineare Spann + verändert sich nicht, wenn man diesen Vektor entfernen würde. +2. Wenn hingegen jeder Vektor tatsächlich eine neue Dimension zum + linearen Spann hinzufügt, ist die Vektorfamilie **linear + unabhängig**. +::: + +::: visu +**Visualisierung** in $\R^3$. + +1. Mit linear abhängigen Vektoren $\vec{u}=(0,1,1)^\top$, + $\vec{v}=(1,0,1)^\top$ und $\vec{w}=(2,0,2)^\top$ entsteht ein + zweidimensionaler Spann, da $\vec{w}$ durch $2\vec{v}$ ersetzt + werden kann: + +```{=tex} +\begin{center}\begin{tikzpicture} +\begin{axis}[xlabel={$x$},ylabel={$y$},zlabel={$z$}] + \addplot3[surf, mesh] + {x+y}; + \fill[red] (0,0,0) circle (2pt); + \draw[->, ultra thick] (0,0,0) -- node [above] {$\vec{u}$} (0,3,3); + \draw[->, ultra thick] (0,3,3) -- node [above] {$\vec{v}$} (3,3,6); + \draw[->, ultra thick] (3,3,6) -- node [above] {$\vec{w}$} (5,3,8); + \draw[->, ultra thick, blue] (0,0,0) -- node [above] {$\vec{k}$} (5,3,8); +\end{axis} +\end{tikzpicture}\end{center} +``` +2. Mit linear unabhängigen Vektoren $\vec{u}=(0,1,1)^\top$, + $\vec{v}=(1,0,1)^\top$ und $\vec{w}=(0,0,1)^\top$ entsteht ein + dreidimensionaler Spann, da keiner der Vektoren durch eine + Linearkombination anderer Vektoren dargestellt werden kann (siehe + auch Kapitel *[Lineare Hülle](#lspan))*: + +```{=tex} +\begin{center}\begin{tikzpicture} +\begin{axis}[xlabel={$x$},ylabel={$y$},zlabel={$z$}] + \addplot3[surf, mesh] + {x+y-8}; + \fill[red] (0,0,0) circle (2pt); + \draw[->, ultra thick] (0,0,0) -- node [above] {$\vec{u}$} (0,3,3); + \draw[->, ultra thick] (0,3,3) -- node [above] {$\vec{v}$} (3,3,6); + \draw[->, ultra thick] (3,3,6) -- node [right] {$\vec{w}$} (3,3,-2); + \draw[->, ultra thick, blue] (0,0,0) -- node [above] {$\vec{k}$} (3,3,-2); +\end{axis} +\end{tikzpicture}\end{center} +``` +::: + +## Basis + +::: defi +Eine **Basis** $\mathcal{B}$ für $V$ ist ein linear unabhängiges +Erzeugendensystem für $V$, d.h. es gilt +$$\mathrm{Lin}(\mathcal{B}) = V\quad\land\quad\mathcal{B} \text{ ist linear unabhängig}.$$ +Sie ist also eine Familie an linear unabhängigen Vektoren, die einen +Raum aufspannen. +::: + +::: bsp +**Beispiele**: + +1. Die Koordinateneinheitsvektoren $e_1=(1,0,...,0)^\top$, + $e_2=(0,1,0,...,0)^\top$ bis $e_n=(0,0,0,...,1)^\top$ sind eine + Basis des $n$-dimensionalen Raumes $\R^n$ +2. Die Monome $1,x,x^2,x^3,...$ bilden eine Basis des + unendlichdimensionalen Raumes aller Polynome. +::: + +**Eigenschaften**: + +1. Aus jedem endlichen Erzeugendensystem eines Vektorraums kann man + eine Basis auswählen. +2. Jeder endlich erzeugte Vektorraum hat eine endliche Basis. +3. Jeder Vektorraum besitzt eine Basis. +4. Hat $V$ eine endliche Basis von $n$ Vektoren, so hat jede Basis von + $V$ genau $n$ Vektoren. +5. Jede linear unabhängige Familie von $n=\mathrm{dim}(V)$ Vektoren ist + eine Basis von $V$. + +TODO: 11.24? + +### Steinitzsches Austauschlemma + +Mit der endlichen Basis $\mathcal{B} = (b_1,...,b_n)$ von $V$ und +$V\ni b \neq 0$ existiert $i\in\{1,...,n\}$, sodass +$\mathcal{B}' = (b_1,...,b_{i-1}, b, b_{i+1},...,b_n)$ eine Basis von +$V$ ist. + +### Steinitzscher Austauschsatz + +Mit der endlichen Basis $\mathcal{B} = (b_1,...,b_n)$ von $V$ und der +linear unabhängigen Familie $\mathcal{F} = (b'_1,...,b'_m)$ ist +$m\leq n$ und es gibt $J\subset\{1,...,n\}$ derart, sodass man nach +Austausch von $(b_i)_{i\in J}$ gegen $\mathcal{F}$ wieder eine Basis von +$V$ erhält. + +## Dimension + +::: defi +Die **Dimension** $\mathrm{dim}_K(V)$ eines Vektorraums $V$ entspricht +der Anzahl der Vektoren einer Basis von $V$, sofern diese endlich ist, +und $\mathrm{dim}_K(V) = \infty$, wenn es keine endliche Basis von $V$ +gibt. Wenn aus dem Kontext klar wird, über welchem Körper der Vektorraum +gebildet ist, dann schreibt man auch +$\mathrm{dim}(V) = \mathrm{dim}_K(V)$. +::: + +Zusammenfassend gilt: + +```{=tex} +\begin{splitty} +&V \text{ ist $n$-dimensional}\\ +\iff &\text{Je $n$ linear unabhängige Vektoren bilden eine Basis.}\\ +\iff &\text{Eine (und damit jede) Basis hat $n$ Elemente.}\\ +\iff &\text{Es gibt $n$ linear unabhängige Vektoren mit $V = \mathrm{Lin}(v_1,...,v_n)$.}\\ +\iff &\text{Es gibt $n$ linear unabhängige Vektoren, aber jeweils $n+1$ Vektoren sind linear abhängig.} +\end{splitty} +``` +::: bsp +**Beispiele**: + +1. $\mathrm{dim}_K(K^n)=n$. +2. $\mathrm{dim}_\R(\R)=1,\ \mathrm{dim}_\Q(\R)=\infty$. +3. $\mathrm{dim}_\R(\C)=2.$ +::: + +# Lineare Abbildungen + +TUDU. + +# Matrizen + +TUDU. + +------------------------------------------------------------------------ + +## Blockmatrizen + +Eine **$m\times n$-Blockmatrix** $M$ über $K$ mit Blöcken +(Untermatrizen) $A_{ij} \in K^{m_i\times n_i}$ für $i=1,...,k$ und +$j=1,...,l$, sodass $m_1 + ... + m_k = m$ und $n_1+...+n_l=n$ ist, ist +ein rechteckiges Schema der Form +$$M = \begin{pmatrix}A_{11}&A_{12}&\dots&A_{1l}\\A_{21}&A_{22}&\dots&A_{2l}\\\vdots&\vdots&\ &\vdots\\A_{k1}&A_{k2}&\dots&A_{kl}\end{pmatrix}\in K^{m\times n}$$ + +::: bsp +**Beispiel**: +$$K^{n\times n} \ni M = \begin{pmatrix}A&B\\C&D\end{pmatrix}$$ TODO: +Elemente klassifizieren +::: + +Mit $$K^{n\times n} \ni M = \begin{pmatrix}A&B\\C&D\end{pmatrix}$$ und +$$K^{n\times n} \ni M\ = \begin{pmatrix}A'&B'\\C'&D'\end{pmatrix}$$gilt +$$MM' = \begin{pmatrix}A&B\\C&D\end{pmatrix}\begin{pmatrix}A'&B'\\C'&D'\end{pmatrix} = \begin{pmatrix}AA'+BC'&AB'+BD'\\CA'+DC'&CB'+DD'\end{pmatrix}$$ + +------------------------------------------------------------------------ + +Mit $$K^{n\times n} \ni M = \begin{pmatrix}A&B\\C&D\end{pmatrix}$$ und +$A\in K^{r\times r}$ und $C=0$ gilt: +$$M \text{ ist invertierbar} \iff A \text{ und } D \text{ sind invertierbar.}$$ +Ist dies der Fall, dann ist +$$M^{-1} = \begin{pmatrix}A^{-1}&-A^{-1}BD^{-1}\\0&D^{-1}\end{pmatrix}$$ + +------------------------------------------------------------------------ + +Die Menge aller invertierbaren Matrizen der Form +$\mathrm{GL}(n,K)\ni\begin{pmatrix}A&B\\0&D\end{pmatrix}$ mit $A,B,D$ +wie zuvor ist eine Untergruppe von $\mathrm{GL}(n,K)$. + +------------------------------------------------------------------------ + +Sei $A\in K^{n\times n}$ eine **(obere) Dreiecksmatrix**, d.h. +$$A=(a_{ij})_{ij} = 1,...,n \text{ und } a_{ij}=0\text{ für } i > j.$$ +Genau dann ist $A$ invertierbar, wenn alle $a_{ii} \neq 0, i=1,...,n$ +sind. + +Explizit geschrieben wird eine solche Matrix wie folgt: +$$A=\begin{pmatrix}a_{11}&a_{12}&\dots&a_{1n}\\0&a_{22}&\dots&a_{2n}\\\vdots&\ddots&\ddots&\vdots\\0&\dots&0&a_{mn}\end{pmatrix}$$ +Da $A$ invertirebar ist genau dann, wenn $A^\top$ invertierbar ist, gilt +die Aussage des vorigen Korollars auch für eine **(untere) +Dreiecksmatrix**, also der Transponierten der oberen Dreiecksmatrix. + +------------------------------------------------------------------------ + +Eine Diagonalmatrix +$D=\mathrm{diag}(d_{11},...,d_{nn}) \in K^{n\times n}$ ist genau dann +invertierbar, wenn $d_{ii} \neq 0$ für alle $i=1,...,n$ gilt. In diesem +Fall ist $$D^{-1} = \mathrm{diag}()$$ TUDU: REST + +------------------------------------------------------------------------ + +TODO: Lückenhaft + +## Elementare Zeilen- und Spaltenoperationen + +Eine Matrix $A\in K^{m\times n}$ besitzt **Zeilenstufenform**, wenn $A$ +folgende Form hat: $$A = \begin{pmatrix} + 0&\dots&0&a_{1j_1}&\ast&\dots&\ast&\ast&\ast&\dots&\ast&\ast&\ast&\dots&\ast\\ + 0&\dots&0&0&0&\dots&0&a_{2j_2}&\ast&\dots&\ast&\ast&\ast&\dots&\ast\\ + &\vdots&&&&\vdots&&&&\ddots&&&&\vdots&\\ + 0&\dots&0&0&0&\dots&0&0&0&\dots&0&a_{rj_r}&\ast&\dots&\ast\\ + 0&\dots&0&0&0&\dots&0&0&0&\dots&0&0&0&\dots&0\\ + &\vdots&&&&\vdots&&&&\vdots&&&&\vdots&\\ + 0&\dots&0&0&0&\dots&0&0&0&\dots&0&0&0&\dots&0 +\end{pmatrix}$$ wobei $j_1<j_2<...<j_r$ und $0\neq a_{kj_k}\in K$ für +$k=1,...,r$ gilt und $*$ für ein beliebiges Element in $K$ steht. Die +Einträge $a_{1j_1},...,a_{rj_r}$ sind die **Pivoteinträge**. Man sagt, +dass $A$ **normierte Zeilenstufenform** hat, wenn sie Zeilenstufenform +mit Pivoteinträgen $a_{1j_1} = ... = a_{rj_r} = 1$ besitzt. + +------------------------------------------------------------------------ + +Mit der Matrix $a\in K^{m\times n}$ mit Zeilenvektoren +$z_1,...,z_m\in K^{1\times n}$. Man unterscheidet drei Typen von +**elementaren Zeilenoperationen** der Matrix $A$: + +1. Addition des $\lambda$-fachen der $j$-ten Zeile zur $i$-ten Zeile + wobei $i\neq j$ und $\lambda\in K$: + $$Z_{\lambda;j,i}: \begin{pmatrix}z_1\\\vdots\\z_i\\\vdots\\z_j\\\vdots\\z_m\end{pmatrix} \mapsto \begin{pmatrix}z_1\\\vdots\\z_i+\lambda z_j\\\vdots\\z_j\\\vdots\\z_m\end{pmatrix}$$ +2. Vertauschen der $i$-ten mit der $j$-ten Zeile: + $$Z_{i,j}: \begin{pmatrix}z_1\\\vdots\\z_i\\\vdots\\z_j\\\vdots\\z_m\end{pmatrix}\mapsto\begin{pmatrix}z_1\\\vdots\\z_j\\\vdots\\z_i\\\vdots\\z_m\end{pmatrix}$$ +3. Multiplikation der $i$-ten Zeile von $A$ mit $0\neq\lambda\in K$: + $$Z_{\lambda;i}: \begin{pmatrix}z_1\\\vdots\\z_i\\\vdots\\z_m\end{pmatrix} \mapsto \begin{pmatrix}z_1\\\vdots\\\lambda\cdot z_i\\\vdots\\z_m\end{pmatrix}$$ + +Dieselben Regeln gelten analog auch für Spaltenvektoren und +Spaltenoperationen. + +------------------------------------------------------------------------ + +Mit der Matrix $A\in K^{m\times n}$ gelten folgende Aussagen: + +1. Man kann $A$ durch endlich viele elementaren Zeilenoperationen vom + Typ (i) und (ii) in Zeilenstufenform bringen. +2. Beistzt $A$ Zeilenstufenform, so kann man $A$ durch endlichviele + elementaren Zeilenoperationen vom Typ (iii) in normierte + Zeilenstufenform bringen. + +## Gaußsches Eliminationsverfahren + +Sei $0\neq A\in K^{m\times n}$. + +1. Finde die kleinste Zahl $0\leq j_1\leq n$, sodass die $j_1$-te + Spalte von $A$ keine Nullspalte ist. +2. Wähle $0\leq i_1 \leq m$ mit $a_{i_1j_1} \neq 0$ und vertausche die + $i_1$-te und die $1$-te Zeile, d.h. wende $Z_{1,i_1}$ auf $A$ an. + Die so erhaltene Matrix $B=Z_{1,i_1}(A)$ hat die Form + $$B=(b_{ij})=\begin{pmatrix}0&\dots&0&a_{i_1j_1}&\ast&\dots&\ast\\0&\dots&0&\ast&\ast&\dots&\ast\\\vdots&&\vdots&\vdots&\vdots&&\vdots\\0&\dots&0&\ast&\ast&\dots&\ast\end{pmatrix}$$ + wobei `\enquote{$\ast$}`{=tex} für ein beliebiges Element in $K$ + steht. +3. Für $i=2,...,m$ addiere man das $-\frac{b_{ij_1}}{a_{i_1j_1}}$-fache + der ersten Zeile zur $i$-ten Zeile, d.h. wende $Z_{\lambda_i;1,i}$ + mit $\lambda_i = -\frac{b_{ij_1}}{a_{i_1j_1}}$ für $i=2,...,m$ + sukzessive an. Dadurch ergibt sich eine Matrix + $C=(Z_{\lambda_m;1,m}\circ\dots\circ Z_{\lambda_2;1,2})(B)$ der Form + $$C = (c_{ij}) = \begin{pmatrix}0&\dots&0&a_{i_1j_1}&\ast&\dots&\ast\\0&\dots&0&0&\bullet&\dots&\bullet\\\vdots&&\vdots&\vdots&\vdots&&\vdots\\0&\dots&0&0&\bullet&\dots&\bullet\end{pmatrix}$$ + wobei `\enquote{$\ast$}`{=tex} für das gleiche Element wie in der + Matrix $B$ steht und TODO für ein beliebiges Element in $K$ steht. + Damit hat man für die erste Zeile den gewünschten Zustand erreicht. +4. Wiederhole Algorithmus auf $D=(c_{(i_1)j})_{i=1,...,m-1;j=1,...,n}$ + an. + +TODO: Beispiel Algorithmus Treppenform + +------------------------------------------------------------------------ + +Sei $A\in K^{m\times n}$ eine Matrix in Zeilenstufenform mit $r$ +Pivotspalten. Dann kann $A$ mittels endlich vieler elementarer +Spaltenoperationen vom Typ (i) und vom Typ (ii) auf folgende Gestalt +bringen $$\begin{pmatrix}D&0\\0&0\end{pmatrix}$$ wobei $D$ eine +$r\times r$-Diagonalmatrix ist. Durch Spaltenoperationen vom Typ (iii) +erreicht man weiter, dass $D=E_r$ gilt. + +## Elementarmatrizen + +Die elementaren Zeilenoperationen lassen sich als Matrix-Matrix Produkte +mit sogenannten **Elementarmatrizen** auffassen. + +1. Es gilt: + $$Z_{\lambda;i,j}(A) = \underbrace{\begin{pmatrix}1&0&&&&&0\\0&\ddots&&&&\\&&1&&\lambda&&\\&&&\ddots&&&\\&&&&1&&\\&&&&&\ddots&0\\0&&&&&0&1\end{pmatrix}}_{=:E_{m;\lambda_ij,i}\in K^{m\times m}} \cdot A$$ +2. Es gilt: + $$Z_{ij}(A) = \underbrace{\begin{pmatrix}1&0&&&&&0\\0&\ddots&&&&&\\&&0&&1&&\\&&&\ddots&&&\\&&1&&0&&\\&&&&&\ddots&0\\0&&&&&0&1\end{pmatrix}}_{=:E_{m;i,j}\in K^{m\times m}}$$ +3. Es gilt: + $$Z_{\lambda;i}(A) = \underbrace{\begin{pmatrix}1&0&&&&&0\\0&\ddots&&&&&\\&&1&&&&\\&&&\lambda&&&\\&&&&1&&\\&&&&&\ddots&0\\0&&&&&0&1\end{pmatrix}}_{=:E_{m;\lambda_ij,i}\in K^{m\times m}}$$ + +(TUDU: nicht ganz fertig) + +------------------------------------------------------------------------ + +Die elementaren Spaltenoperationen lassen sich auch als Matrix-Matrix +Produkte mit **Elementarmatrizen** auffassen. Operationen der Spalten +erfordern die Multiplikation mit Matrizen vonrechts, anstatt von links. +Sei $B\in K^{m\times n}$, dann gilt: + +1. $S_{\lambda;i,j}(B) = B\cdot E_{n;\lambda;i,j}$ +2. $S_{ij}(B) = B\cdot E_{n;i,j}$ +3. $S_{\lambda;i}(B) = B\cdot E_{n;\lambda;i}$ + +------------------------------------------------------------------------ + +Sei $A\in K^{m\times n}$. Dann gelten folgende Aussagen: + +1. Es gibt Elementarmatrizen $S_1,...,S_k\in K^{m\times m}$, sodass + $$S_k...S_1\cdot A$$ normierte Zeilenstufenform besitzt. +2. Besitzt $A$ Zeilenstufenform mit $r$ Pivotspalten, so gibt es + Elementarmatrizen $T_1,...,T_l\in K^{n\times n}$ mit + $$A\cdot T_1...T_l=\begin{pmatrix}E_r&0\\0&0\end{pmatrix}.$$ +3. Es gibt Elementarmatrizen $S_1,...,S_k\in K^{m\times m}$ und + $T_1,...,T_l\in K^{n\times n}$ mit + $$S_k...S_1\cdot A\cdot T_1...T_l=\begin{pmatrix}E_r&0\\0&0\end{pmatrix}$$ + +::: bsp +**Beispiel**: Bestimmen der Matrizen $S$ und $T$. +$$A=\begin{pmatrix}1&-1&1\\1&0&-1\end{pmatrix}\in\Q^{2\times3}$$ Nun +führt man folgende Schritte durch: + +```{=tex} +\begin{splitty} +&\left( \begin{pmatrix}1&-1&1\\1&0&-1\end{pmatrix},\begin{pmatrix}1&0\\0&1\end{pmatrix},\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix} \right )\\ +\leadsto &\left( \begin{pmatrix}1&-1&1\\0&1&-2\end{pmatrix},\begin{pmatrix}1&0\\-1&1\end{pmatrix},\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix} \right)\\ +\leadsto &\left( \begin{pmatrix}1&0&-1\\0&1&-2\end{pmatrix},\begin{pmatrix}1&0\\-1&1\end{pmatrix},\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix} \right)\\ +TUDU\\ +\end{splitty} +``` +::: + +# Der Rang einer Matrix + +::: defi +Sei $A\in K^{m\times n}$. + +1. Der **Spaltenraum** von $A$ ist der durch die Spalten $s_1,...,s_n$ + von $A$ erzeugte Untervektorraum $\mathrm{Lin}(s_1,...,s_n)$ von + $K^m$. +2. Der **Spaltenrang** von $A$ ist die Dimension des Spaltenraums von + $A$: + $$\mathrm{rank}_S(A) = \mathrm{dim}(\mathrm{Lin}(s_1,...,s_n))$$ +::: + +::: bsp +**Beispiele**: + +1. Der Spaltenrang der Einheitsmatrix in $K^n$ ist + $\mathrm{rank}_SE_n=n$. Allgemeiner gilt + $$\mathrm{rank}_S \begin{pmatrix}E_r&0\\0&0\end{pmatrix} = r.$$ +2. Mit der Matrix $\begin{pmatrix}1&3&3\\2&6&2\\3&9&1\end{pmatrix}$ + gilt + $\mathrm{Lin} = \left( \begin{pmatrix}1\\2\\3\end{pmatrix} \begin{pmatrix}3\\6\\9\end{pmatrix} \begin{pmatrix}3\\2\\1\end{pmatrix}\right) = \mathrm{Lin}\left(\begin{pmatrix}1\\2\\3\end{pmatrix} \begin{pmatrix}3\\2\\1\end{pmatrix}\right)$ + TUDU: Gekritzel +::: + +------------------------------------------------------------------------ + +Mit Matrix $A\in K^{m\times n}$ mit Spalten $s_1,...,s_n$ und +$\varphi_A: K^n\to K^m, v\mapsto Av$ gilt +$$\mathrm{im}(\varphi_A) = \mathrm{Lin}(s_1,...,s_n)\quad\text{und}\quad\mathrm{dim}(\mathrm{im}(\varphi_A)) = \mathrm{rank}_S(A)$$ + +------------------------------------------------------------------------ + +Mit Matrix $A\in K^{m\times n}$ gilt: + +1. Ist $T\in K^{n\times n}$ invertierbar, so gilt + $\mathrm{rank}_S(AT) = \mathrm{rank}_S(A)$. +2. Ist $S\in K^{m\times m}$ invertierbar, so gilt + $\mathrm{rank}_S(SA) = \mathrm{rank}_S(A)$. + +------------------------------------------------------------------------ + +Mit Matrix $A\in K^{m\times n}$ und $r\in\N$ sind folgende Aussagen +äquivalent: + +1. $\mathrm{rank}_S(A) = r$. +2. Es existieren Elementarmatrizen $S_1,...,S_K\in K^{m\times m}$ und + $T_1,...,T_1\in K^{n\times n}$ mit + $$S_k...S_1\cdot A\cdot T_1...T_l = \begin{pmatrix}E_r&0\\0&0\end{pmatrix}$$ + +------------------------------------------------------------------------ + +Sei $A\in K^{m\times n}$. Dann gilt: + +1. Der **Zeilenraum** von $A$ ist der durch die Zeilen $z_1,...,z_m$ + von $A$ erzeugte Untervektorraum $\mathrm{Lin}(z_1,...,z_m)$ von + $K^n$. +2. Der **Zeilenrang** von $A$ ist die Dimension des Zeilenraums von + $A$: + $$\mathrm{rank}_Z(A) = \mathrm{dim}(\mathrm{Lin}(z_1,...,z_m)).$$ + +------------------------------------------------------------------------ + +Sei $A\in K^{m\times n}$. Dann stimmen Zeilen- und Spaltenrang der +Matrix $A$ überein und man bezeichnet diesen als **Rang** von $A$: +$$\mathrm{rank}(A) = \mathrm{rank}_Z(A) = \mathrm{rank}_S(A).$$ + +------------------------------------------------------------------------ + +Für eine Matrix $A\in K^{n\times n}$ sind folgende Aussagen äquivalent: + +1. Die Spalten von $A$ bilden eine Basis des $K^n$. +2. Die Zeilen von $A$ bilden eine Basis des $K^n$. +3. Es gilt $\mathrm{rank}(A) = n$. +4. $A$ ist ein Produkt von Elementarmatrizen. +5. $A$ ist invertierbar. Insbesondere wird die Gruppe + $\mathrm{GL}(n,K)$ von den Elementarmatrizen erzeugt. + +::: bsp +**Beispiel**: Bestimmen dse Inversen zu +$$A = \begin{pmatrix}0&0&1\\-1&1&0\\1&0&1\end{pmatrix}\in\Q^{3\times 3}.$$ +Dazu bildet man das Tupel $(A,E_3)$: TUDU: Annotationen + +```{=tex} +\begin{splitty} +\left( \begin{pmatrix}0&0&1\\-1&1&0\\1&0&1\end{pmatrix}, \begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}\right) &\leadsto \left( \begin{pmatrix}1&0&1\\-1&1&0\\0&0&1\end{pmatrix}, \begin{pmatrix}0&0&1\\0&1&0\\1&0&0\end{pmatrix}\right)\\ +&\leadsto \left( \begin{pmatrix}1&0&0\\-1&1&0\\0&0&1\end{pmatrix}, \begin{pmatrix}-1&0&1\\0&1&0\\1&0&0\end{pmatrix}\right)\\ +&\leadsto \left( \begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}, \begin{pmatrix}-1&0&1\\-1&1&1\\1&0&0\end{pmatrix}\right) +\end{splitty} +``` +Damit erhält man +$$A^{-1} = \begin{pmatrix}-1&0&1\\-1&1&1\\1&0&0\end{pmatrix}.$$ +::: + +# Lineare Gleichungssysteme + +::: defi +Ein **lineares Gleichungssystem** über $K$ in den Variablen +$x_1,...,x_n$ ist ein Gleichungssystem der Form + +```{=tex} +\begin{splitty} +a_{11}x_1 + ... + a_{1n}x_n &= b_1,\\ +&\hspace*{2mm}\vdots\\ +a_{m1}x_1 + ... + a_{mn}x_n &= b_m, +\end{splitty} +``` +mit Koeffizienten $a_{ij},b_i\in K$. Man nennt das Gleichungssytem +**homogen**, falls $b_1=...=b_m=0$ gilt, und sonst nennt man es +**inhomogen**. + +Eine **Lösung** des Gleichungssystems ist ein Vektor $u\in K^n$, der +alle Gleichungen erfüllt. Das System heißt **lösbar**, wenn eine Lösung +existiert. +::: + +------------------------------------------------------------------------ |