Mathematik_1.tex

% !TEX TS-program = pdflatex
% !TEX encoding = UTF-8 Unicode

\documentclass[a4paper, 12pt, twoside] {article}

\usepackage[utf8]{inputenc} % set input encoding (not needed with XeLaTeX)
\usepackage[ngerman]{babel}

\usepackage{amssymb} % math stuff
\usepackage{amsmath} % math stuff
\usepackage{multicol}
\usepackage{multirow}

\usepackage{geometry} 
\usepackage{graphicx}

% Overwrite symbols in author footnotes
\makeatletter
\let\@fnsymbol\@arabic
\makeatother

\usepackage[parfill]{parskip} % Activate to begin paragraphs with an empty line rather than an indent

%%% PACKAGES
\usepackage{booktabs} % for much better looking tables
\usepackage{array} % for better arrays (eg matrices) in maths
\usepackage{paralist} % very flexible & customisable lists (eg. enumerate/itemize, etc.)
\usepackage{verbatim} % adds environment for commenting out blocks of text & for better verbatim
\usepackage{subfig} % make it possible to include more than one captioned figure/table in a single float
% These packages are all incorporated in the memoir class to one degree or another...

%%% HEADERS & FOOTERS
\usepackage{fancyhdr} % This should be set AFTER setting up the page geometry
\pagestyle{fancy} % options: empty , plain , fancy
\renewcommand{\headrulewidth}{0pt} % customise the layout...
\lhead{}\chead{}\rhead{}
\lfoot{}\cfoot{\thepage}\rfoot{}

%%% SECTION TITLE APPEARANCE
\usepackage{sectsty}
\allsectionsfont{\sffamily\mdseries\upshape} % (See the fntguide.pdf for font help)
% (This matches ConTeXt defaults)

%%% ToC (table of contents) APPEARANCE
\usepackage[nottoc,notlof,notlot]{tocbibind} % Put the bibliography in the ToC
\usepackage[titles,subfigure]{tocloft} % Alter the style of the Table of Contents
\renewcommand{\cftsecfont}{\rmfamily\mdseries\upshape}
\renewcommand{\cftsecpagefont}{\rmfamily\mdseries\upshape} % No bold!

\usepackage{wasysym}
\usepackage{marvosym}

\usepackage{tikz}

\usepackage{venndiagram}

\usepackage{mathtools}

\usepackage{commath}

\usepackage{ulem}

\usepackage{titlesec}
\newcommand{\sectionbreak}{\clearpage}

\usepackage[
bookmarksnumbered=true
]{hyperref} % This should be the last package loaded.

\hypersetup{linktoc=all,  
hidelinks}


\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}

\newcommand{\attention}{{\fontencoding{U}\fontfamily{futs}\selectfont\char 66\relax}\space}


% \overfence definition
\let\overfence\overbrace % \overfence is similar to \overbrace
\let\downfencefill\downbracefill % match components of \overbrace
\patchcmd{\overfence}{\downbracefill}{\downfencefill}{}{}% patch \overfence...
\patchcmd{\downfencefill}{\braceru \bracelu}{}{}{}%... and \downfencefill

% \underfence definition
\let\underfence\underbrace % \underfence is similar to \underbrace
\let\upfencefill\upbracefill % match components of \underbrace
\patchcmd{\underfence}{\upbracefill}{\upfencefill}{}{}% patch \underfence...
\patchcmd{\upfencefill}{\bracerd \braceld}{}{}{}%... and \upfencefill

\makeatletter
\newcommand*{\bdiv}{%
  \nonscript\mskip-\medmuskip\mkern5mu%
  \mathbin{\operator@font div}\penalty900\mkern5mu%
  \nonscript\mskip-\medmuskip
}
\makeatother

\DeclareRobustCommand{\SkipTocEntry}[4]{} 

%%% END Article customizations

%%% CONTENT starts here

\title{Mathematik I WS 15/16}
\author{Thomas Dinges\thanks{thomas.dinges@student.uni-tuebingen.de} \and Jonas Wolf \thanks{mail@jonaswolf.de}}

\begin{document}
\maketitle

\vfill
\thanks{Inoffizielles Skript für die Vorlesung Mathematik I im WS 15/16, bei Britta Dorn. Alle Angaben ohne Gewähr. Fehler können gerne via E-Mail gemeldet werden.}

\newpage

\tableofcontents

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Kapitel 1: Logik
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Logik} %1

% =============
% 12 Oktober 2015
% =============

\subsection*{Aussagenlogik}
Eine \textbf{logische Aussage} ist ein Satz, der entweder wahr oder falsch (also nie beides zugleich) ist. 
Wahre Aussagen haben den Wahrheitswert 1 (auch wahr, w, true, t), falsche den Wert 0 (auch falsch, f, false).

Notation: Aussagenvariablen $A, B, C, ... A_1, A_2$.

Beispiele:
\begin{itemize}
\item 2 ist eine gerade Zahl (1)
\item Heute ist Montag (1)
\item 2 ist eine Primzahl (1)
\item 12 ist eine Primzahl (0)
\item Es gibt unendlich viele Primzahlen (1)
\item Es gibt unendlich viele Primzahlzwillinge (Aussage, aber unbekannt, ob 1 oder 0)
\item 7 (keine Aussage)
\item Ist 173 eine Primzahl? (keine Aussage)
\end{itemize}

% =============
% 14 Oktober 2015
% =============

Aus einfachen Aussagen kann man durch logische Verknüpfungen (\textbf{Junktoren}, z.B. und, oder, ...) kompliziertere bilden. Diese werden Ausdrücke genannt (auch Aussagen sind Ausdrücke). 
Durch sogenannte \textbf{Wahrheitstafeln} gibt man an, wie der Wahrheitswert der zusammengesetzten Aussage durch die Werte der Teilaussagen bedingt ist. Im folgenden seien $A, B$ Aussagen. 

Die wichtigsten Junktoren:

\subsection{Negation} %1.1
Verneinung von A: $\neg A$ (auch $\bar{A})$, \textit{nicht A}, ist die Aussage, die genau dann wahr ist, wenn A falsch ist.

Wahrheitstafel: \qquad
\begin{tabular}{| c | c |}
\hline
A & $\neg A$ \\
\hline
1 & 0 \\
0 & 1 \\
\hline
\end{tabular}

Beispiele: 
\begin{itemize}
\item $A$: 6 ist durch 3 teilbar. (1)
\item $\neg A $: 6 ist nicht durch 3 teilbar. (0)
\item $B$: 4,5 ist eine gerade Zahl (0)
\item $\neg B$: 4,5 ist keine gerade Zahl. (1)
\end{itemize}

\subsection{Konjunktion} %1.2
Verknüpfung von A und B durch \textit{und}: $A \wedge B$ ist genau dann wahr, wenn A und B gleichzeitig wahr sind.

Wahrheitstafel: \qquad
\begin{tabular}{| c c | c |}
\hline
A & B & $A \wedge B$ \\
\hline
1 & 1 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 0 \\
\hline
\end{tabular}

Beispiele:
\begin{itemize}
\item $\underbrace{\text{6 ist eine gerade Zahl}}_{A (1)}$ und $\underbrace{\text{durch 3 teilbar}}_{B (1)}$. (1)
\item $\underbrace{\text{9 ist eine gerade Zahl}}_{A (0)}$ und $\underbrace{\text{durch 3 teilbar}}_{B (1)}$. (0)
\end{itemize}

\subsection{Disjunktion} %1.3
\textit{oder}: $A \lor B$

Wahrheitstafel: \qquad
\begin{tabular}{| c c | c |}
\hline
A & B & $A \lor B$ \\
\hline
1 & 1 & 1 \\
1 & 0 & 1 \\
0 & 1 & 1 \\
0 & 0 & 0 \\
\hline
\end{tabular}

\attention Einschließendes oder, kein entweder...oder.

Beispiele:
\begin{itemize}
\item 6 ist gerade oder durch 3 teilbar. (1)
\item 9 ist gerade oder durch 3 teilbar. (1)
\item 7 ist gerade oder durch 3 teilbar. (0)
\end{itemize}

\subsection{XOR} %1.4
\textit{entweder oder}: A xor B, $A \oplus B$ (ausschließendes oder, exclusive or).

Wahrheitstafel: \qquad
\begin{tabular}{| c c | c |}
\hline
A & B & $A \oplus B$ \\
\hline
1 & 1 & 0 \\
1 & 0 & 1 \\
0 & 1 & 1 \\
0 & 0 & 0 \\
\hline
\end{tabular}

\subsection{Implikation} %1.5
\textit{wenn, dann}, $A \Rightarrow B$:
\begin{itemize}
\item wenn A gilt, dann auch B
\item A impliziert B
\item aus A folgt B
\item A ist \underline{hinreichend} für B,
\item B ist \underline{notwendig} für A
\end{itemize}

Wahrheitstafel: \qquad
\begin{tabular}{| c c | c |}
\hline
A & B & $A \Rightarrow B$ \\
\hline
1 & 1 & 1 \\
1 & 0 & 0 \\
0 & 1 & 1 \\
0 & 0 & 1 \\
\hline
\end{tabular}

\textbf{Merke: } \textit{ex falso quodlibet} : aus einer falschen Aussage kann man alles folgern!

(Die Implikation $A \Rightarrow B$ sagt nur, dass B wahr sein muss, \underline{falls} A wahr ist. Sie sagt nicht, dass B tatsächlich war ist.)

Beispiele:
\begin{itemize}
\item Wenn 1 = 0, bin ich der Papst. (1)
\end{itemize}

\subsection{Äquivalenz} %1.6
\textit{genau dann wenn}, $ A \Leftrightarrow B$ (dann und nur dann wenn, g.d.w, äquivalent, if and only if, iff)

Wahrheitstafel: \qquad
\begin{tabular}{| c c | c |}
\hline
A & B & $A \Leftrightarrow B$ \\
\hline
1 & 1 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\hline
\end{tabular}

Beispiele:
\begin{itemize}
\item Heute ist Montag genau dann wenn morgen Dienstag ist. (1)
\item Eine natürliche Zahl $\underbrace{\text{ist durch 6 teilbar}}_{A}$ g. d. w. sie $\underbrace{\text{durch 3 teilbar ist}}_{B}$. (0) 
$A \Rightarrow B$ (1) 

$B \Rightarrow A$ (0)
\end{itemize}

% =============
% 19 Oktober 2015
% =============

\subsection*{Festlegung}
$\neg$ bindet stärker als alle anderen Junktoren: $(\neg A \wedge B)$ heißt $ (\neg A) \wedge B$

\subsection{Beispiel} %1.7
\subsubsection*{a)}
Wann ist der Ausdruck $(A \lor B) \wedge \neg (A \wedge B)$ wahr?

$\rightarrow$ Wahrheitstafel

\begin{tabular}{| c c | c | c | c | c |}
\hline
A & B & $(A \lor B)$ & $(A \wedge B)$ & $\neg (A \wedge B)$  & $(A \lor B) \wedge \neg (A \wedge B)$ \\
\hline
1 & 1 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 & 1 \\
0 & 1 & 1 & 0 & 1 & 1 \\
0 & 0 & 0 & 0 & 1 & 0 \\
\hline
\end{tabular}

\attention Klammerung relevant

Welche Wahrheitswerte ergeben sich für
\begin{itemize}
\item $A \lor (B \wedge \neg A) \wedge B)$?
\item $A \lor B \wedge \neg A \wedge B$?
\end{itemize}

$(A \lor B) \wedge \neg (A \wedge B)$ und $(A \oplus B)$ haben dieselben Wahrheitstafeln.
Ausdrücke sehen unterschiedlich aus (Syntax), aber haben dieselbe Bedeutung (Semantik). Dies führt zu \textit{1.8 Definition}.

\subsubsection*{b)}
Wann ist $(A \wedge B) \Rightarrow \neg (C \lor A)$ falsch?

$\rightarrow$ Wahrheitstafel:
\underline{alle} möglichen Belegungen von $A, B, C$ mit $0 / 1$

\begin{tabular}{| c c c | c | c | c |}
\hline
A & B & C & $(A \wedge B)$ & $\neg(C \lor A)$ & $(A \wedge B) \Rightarrow \neg (C \lor A)$ \\
\hline
1 & 1 & 1 & 1 & 0 & 0 \\
1 & 1 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 \\
0 & 1 & 0 & 0 & 1 & 1 \\
0 & 0 & 1 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 & 1 \\
\hline
\end{tabular}

oder überlegen:

$(A \wedge B) \Rightarrow \neg  (C \lor A)$ ist nur 0, wenn

\qquad $(A \wedge B) = 1$, also $A = 1$ und $B = 1$

und

\qquad $\neg(C \lor A) = 0$ ist.

(Wissen: $A = 1$), also $\underline{C = 0}$ oder $ \underline{C = 1}$ möglich. 

\subsection[Definition (logische Äquivalenz)]{Definition} %1.8

Haben zwei Ausdrücke $\alpha$ und $\beta$ bei jeder Kombination von Wahrheitswerten ihrer Aussagevariablen den gleichen Wahrheitswert, so heißen sie \underline{logisch äquivalent}; man schreibt $\alpha \equiv \beta$. ('$\equiv$' ist kein Junktor, entspricht '$=$')

Es gilt: Falls $\alpha \equiv \beta$ gilt, hat der Ausdruck $\alpha \Leftrightarrow \beta$ immer den Wahrheitswert $1$.

\subsection[Satz (Eigenschaften logischer Aussagen)]{Satz} %1.9

Seien $A$, $B$, $C$ Aussagen.
Es gelten folgende logische Äquivalenzen:
\begin{description}
  \item[a) Doppelte Negation:]
  $A \equiv \neg(\neg A)$

  \item[b) Kommutativität von $\wedge$, $\lor$, $\oplus$, $\Leftrightarrow$:] \hfill
  \begin{itemize}
    \item $(A \wedge B) \equiv (B \wedge A)$
    \item $(A \lor B) \equiv (B \lor A)$
    \item $(A \oplus B) \equiv (B \oplus A)$
    \item $(A \Leftrightarrow B) \equiv (B \Leftrightarrow A)$

    \attention gilt nicht für '$\Rightarrow$' !! ($A \Rightarrow B \not\equiv B \Rightarrow A$)
  \end{itemize}  

  \item[c) Assoziativität von $\wedge$, $\lor$, $\oplus$, $\Leftrightarrow$:] \hfill
  \begin{itemize}
      \item $(A \wedge B) \wedge C \equiv A \wedge (B \wedge C)$
      \item $(A \lor B) \lor C \equiv A \lor (B \lor C)$
      \item $(A \oplus B) \oplus C \equiv A \oplus (B \oplus C)$
      \item $(A \Leftrightarrow B) \Leftrightarrow C \equiv A \Leftrightarrow (B \Leftrightarrow C)$
  \end{itemize}

  \item[d) Distributivität:] \hfill
  \begin{itemize}
  \item $A \wedge (B \lor C) \equiv (A \wedge B) \lor (A \wedge C)$
  \item $A \lor (B \wedge C) \equiv (A \lor B) \wedge (A \lor C)$
  \end{itemize}

  \item[e) Regeln von DeMorgan:] \hfill
  \begin{itemize}
  \item $\neg (A \wedge B) \equiv \neg A \lor \neg B$
  \item $\neg (A \lor B) \equiv \neg A \wedge \neg B$
  \end{itemize}

  \item[f)]
  $A \Rightarrow B \equiv \neg B \Rightarrow \neg A$

  \item[g)]
  $A \Rightarrow B \equiv \neg A \lor B$

  \item[h)]
  $A \Leftrightarrow B \equiv (A \Rightarrow B) \wedge (B \Rightarrow A)$
\end{description}
  (Alle Äquivalenzen gelten auch, wenn die Aussagevariablen durch Ausdrücke ersetzt werden.)

\underline{Beweis:} Jeweils mittels Wahrheitstafel (Übung!), zum Beispiel:

a) \qquad
\begin{tabular}{| c | c | c |}
\hline
A & $\neg A$ & $\neg (\neg A)$ \\
\hline
1 & 0 & 1 \\
0 & 1 & 0 \\
\hline
\end{tabular}

%% MISSING: arrows to show identity of columns 0 and 2

e) \qquad
\begin{tabular}{| c c | c | c | c | c | c |}
\hline
A & B & $(A \wedge B)$ & $\neg (A \wedge B)$ & $\neg A$ & $\neg B$ & $(\neg A \lor \neg B)$ \\
\hline
1 & 1 & 1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
\hline
\end{tabular}

%% MISSING: arrows to show identity of columns 3 and 6

\subsection{Bemerkung} %1.10
(1.9 f): $(A \Rightarrow B) \equiv \underbrace{(\neg B \Rightarrow \neg A)}_{\mathrlap{\text{wird \underline{Kontraposition} genannt, wichtig für Beweis. Wird im Sprachgebrauch oft falsch verwendet.}}}$

\hfill

\textbf{Beispiel:} $\underset{A}{\text{Pit ist ein Dackel.}} \Rightarrow \underset{B}{\text{Pit ist ein Hund.}}$

äquivalent zu: $(\neg B) \Rightarrow (\neg A)$

\qquad Pit ist kein Hund. $\Rightarrow$ Pit ist kein Dackel.

aber nicht zu: $B \Rightarrow A$

\qquad Pit ist ein Hund. $\Rightarrow$ Pit ist ein Dackel.

und nicht zu: $\neg A \Rightarrow \neg B$

\qquad Pit ist kein Dackel. $\Rightarrow$ Pit ist kein Hund.

\textbf{Beispiel:} Sohn des Logikers / bellende Hunde ($\rightarrow$ Folien)

\subsection{Bemerkung (Logisches Umformen)} %1.11
Sei $\alpha$ ein Ausdruck. Ersetzen von Teilausdrücken von $\alpha$ durch logisch äquivalente Ausdrücke liefert einen zu $\alpha$ äquivalenten Ausdruck. So erhält man eventuell kürzere/einfachere Ausdrücke, zum Beispiel:

$\neg (A \Rightarrow B) \underset{\text{1.9 g})}{\equiv} \neg (\neg A \lor B) \underset{\text{1.9 e)}}{\equiv} \neg (\neg A) \wedge (\neg B) \underset{\text{1.9 a)}}{\equiv} A \wedge \neg B$

% =============
% 21 Oktober 2015
% =============

\subsection[Definition (Tautologie, Kontradiktion, Erfüllbarkeit)]{Definition} %1.12
Ein Ausdruck heißt \underline{Tautologie}, wenn er für jede Belegung seiner Aussagevariablen, immer den Wert 1 annimmt. Hat er immer den Wert 0, heißt er \underline{Kontradiktion}. 
Gibt es mindestens eine Belegung der Aussagevariablen, so dass der Ausdruck Wert 1 hat, heißt er \underline{erfüllbar}.

\subsection{Beispiel} %1.13
\begin{itemize}
\item[a)] $A \lor \neg A$ Tautologie \newline $A \wedge \neg A$ Kontradiktion

\item[b)] $\neg (A \Rightarrow B ) \Leftrightarrow A \wedge \neg B$ Tautologie (vergleiche Beispiel in 1.11). \newline
$(A \Rightarrow B) \Leftrightarrow (\neg A \lor B)$ Tautologie (vergleiche Beispiel in 1.9g).

\item[c)] $A \wedge \neg B$ ist erfüllbar (durch $A = 1, B = 0$).
\end{itemize}

\subsection*{Prädikatenlogik}
Eine \underline{Aussageform} ist ein sprachliches Gebilde, dass formal wie eine Aussage aussieht, aber eine oder mehrere Variablen enthält.

Beispiel:
$P(x): \underbrace{x}_{Variable} \underbrace{< 10}_{\mathrlap{\text{Prädikat (Eigenschaft)}}}$

$Q(x): x$ studiert Informatik \\
$R(y): y$ ist Primzahl und $y^2+2$ ist Primzahl.

Eine Aussageform $P(x)$ wird zur Aussage, wenn man die Variable durch ein konkretes Objekt ersetzt. Diest ist nur dann sinnvoll, wenn klar ist, welche Werte für x erlaubt sind, daher wird oft die zugelassene Wertemenge mit angegeben. (hier Vorgriff auf Kapitel \textit{Mengen})

Im Beispiel:

$P(3)$ ist wahr, $P(42)$ falsch.

$R(2)$ ist falsch, $R(3)$ ist wahr.

Oft ist die Frage interessant, ob es wenigstens ein $x$ gibt, für das $P(x)$ wahr ist, oder ob $P(x)$ sogar für alle zugelassenen $x$ wahr ist.

\subsection[Definition (Prädikatenlogik)]{Definition} %1.14
Sei $P(x)$ eine Aussageform.

a) Die Aussage \textit{Für alle x (aus einer bestimmten Menge M) gilt $P(x)$.} ist wahr genau dann wenn $P(x)$ für alle in Frage kommenden $x$ wahr ist.

Schreibweise: $\underbrace{\forall}_{\text{für alle, für jedes}} x \underbrace{\in M}_{\text{aus der Menge M}} \underbrace{:}_{\text{gilt}} \underbrace{P(x)}_{\text{Eigenschaft}}$

auch $\underbrace{\forall}_{x \in M} P(x)$.

Das Symbol $\forall$ heißt All- Quantor, die Aussage All- Aussage.

b) Die Aussage \textit{Es gibt (mindestens) ein x aus M, das die Eigenschaft P(x) besitzt.} ist wahr, g.d.w P(x) für mindestens eines der in Frage kommenden x wahr ist.

Schreibweise: $\underbrace{\exists}_{\text{es gibt, es existiert}} x \in M \underbrace{:}_{\text{so dass gilt}} P(x)$.

$\exists$ heißt Existenzquantor und die Aussage Existenzaussage.

\subsection{Beispiel / Bemerkung} %1.15
Übungsgruppe G:
$\underbrace{a}_{Anna} \underbrace{b}_{Bob} \underbrace{c}_{Clara}$

$B(x): x$ ist blond. \\
$W(x): x$ ist weiblich.

$B(a) = 1$ \\
$W(b) = 0$

\begin{enumerate}

\item Alle Studenten der Gruppe sind blond. (1)

$\forall x \in G$: x ist blond

$\forall x \in G$: B(x) (1)

Das bedeutet:
a blond $\wedge$ b blond $\wedge$ c blond \newline
$\underbrace{B(a)}_{1} \wedge \underbrace{B(b)}_{1} \wedge \underbrace{B(c)}_{1}$

$\forall$ ist also eine Verallgemeinerung der Konjunktion.

\item Alle Studenten der Gruppe sind weiblich. (0)

$\underbrace{W(a)}_{1} \wedge \underbrace{W(b)}_{0} \wedge \underbrace{W(c)}_{1}$ $(0)$

\item Es gibt einen Studenten der Gruppe, der weiblich ist. (1)

$\exists x \in G$: W(x) (1)

bedeutet: $\underbrace{W(a)}_{1} \lor \underbrace{W(b)}_{0} \lor \underbrace{W(c)}_{1} = 1$

$\exists$ ist verallgemeinerte Disjunktion.

\item Aussage A: Alle Studenten der Gruppe sind weiblich. (0)

Verneinung von A? $\neg A$

\attention Nicht korrekt wäre: Alle Studenten der Gruppe sind männlich. (Wahrheitswert ist auch 0)

Korrekt: Nicht alle Studenten der Gruppe sind weiblich (1)
Es gibt (mindestens) einen Studenten der Gruppe, der nicht weiblich ist. (1)

\end{enumerate}

allgemeiner:

\subsection{Negation von All- und Existenzaussagen} %1.16

\begin{itemize}
\item[a)] $\neg (\forall x \in M: P(x)) \equiv \exists x \in M: \neg P(x)$
\item[b)] $\neg (\exists x \in M: P(x)) \equiv \forall x \in M : \neg P(x)$
\end{itemize}

(Verallgemeinerung der Regeln von DeMorgan)
(vergleiche Beispiel 1.15, 4):

$\neg (\forall x \in G: W(x))$

$\equiv \neg (W(a) \wedge W(b) \wedge W(c))$

$\underbrace{\equiv}_{\mathrlap{DeMorgan}} (\neg W(a)) \lor (\neg W(b)) \lor (\neg W(c))$

$\equiv \exists x \in G: \neg W(x)$

% =============
% 26 Oktober 2015
% =============

\subsection*{Bemerkung}
Aussageformen können auch mehrere Variablen enthalten, Aussagen mit mehreren Quantoren sind möglich.

Zum Beispiel:

$\exists x \in X \quad \exists y \in Y: P(x,y)$ \\
$\exists x \in X \quad \forall y \in Y: P(x,y)$ \\
$\forall x \in X \quad \exists y \in Y: P(x,y)$ \\
$\forall x \in X \quad \forall y \in Y: P(x,y)$

Negation dann durch mehrfaches Anwenden von 1.16, zum Beispiel:

$\neg (\forall x \in X \quad \forall y \in Y \quad \exists z \in Z : P(x,y,z))$ \\
$\equiv \exists x \in X : \neg (\forall y \in Y \quad \exists z \in Z : P(x,y,z))$ \\
$\equiv \exists x \in X \quad \exists y \in Y : \neg (\exists z \in Z : P(x,y,z))$ \\
$\equiv \exists x \in X \quad \exists y \in Y \quad \forall z \in Z : \neg P(x,y,z))$

\textbf{Also: }\\
ändere $\exists$ in $\forall$, \\
\text{\qquad \quad} $\forall$ in $\exists$, \\
verneine Prädikat.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Kapitel 2: Mengen
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Mengen} %2

\subsection{Definition (Georg Cantor, 1845-1918)} %2.1

Eine \underline{Menge} ist eine Zusammenfassung von bestimmten, wohlunterscheidbaren Objekten (\underline{Elementen}) unserer Anschauung oder unseres Denkens zu einem Ganzen.

Im Folgenden seien $A$, $B$ Mengen.

\begin{description}
\item[a)] 
	$\quad x \in A : x \text{ ist Element der Menge } A$ \\
	$x \notin A: x \text{ ist nicht Element der Menge } A$ \\
	oder auch: \\
	$A \ni x : x \text{ ist Element der Menge } A$ \\
	$A \not \ni x: x \text{ ist nicht Element der Menge } A$
\item[b)]
	Eine Menge kann beschrieben werden durch:
	\begin{itemize}
		\item Aufzählung ihrer Elemente, zum Beispiel: \\
		$M_1 = \{a,b,c\} \qquad \text{(}=\{c,a,b\} \text{, d.h. Reihenfolge spielt keine Rolle)}$ \\
		\textbf{Achtung:} Keine Wiederholungen! \\
		$M_2 = \{\smiley,\frownie\}$ \\
		$M_3 = \{ \underline{3}, \underline{\{1,2\}}, \underline{M_1}\}$ \\
		geht nur bei endlichen Mengen oder bestimmten unendlichen Mengen, zum Beispiel: \\
		$\mathbb{N} = \{1,2,3,4,...\}$ Menge der natürlichen Zahlen \\
		$\mathbb{N}_0 = \{0, 1,2,3,4,...\}$ Menge der natürlichen Zahlen mit der Null \\
		$\mathbb{Z} = \{0,1,-1,2,-2,...\}$ Menge der ganzen Zahlen

		\item Charakterisierung ihrer Elemente: \\
		$A = \{x \mid x \text{ besitzt die Eigenschaft } E\}$, z.B.:\\ %TODO: OS Skript nutz hier ":" statt \mid?
		$A = \{n \underbrace{\mid}_{\mathrlap{\text{sprich: \textit{''mit der Eigenschaft''}}}} n \in \mathbb{N} \text{ und n ist gerade}\}$\\
		$\quad = \{2,4,6,8,...\}$ \\
		$\quad = \{ x \mid \exists k \in \mathbb{N} \text{ mit } x = 2 \cdot k\} = \{2k \mid k \in \mathbb{N}\}$ \\
		
		Bsp: $\mathbb{Q} = \{\frac{a}{b} \mid a,b \in \mathbb{Z}, b \neq 0 \}$ Menge der rationalen Zahlen		
	\end{itemize}
\item[c)]
	Mit $\emptyset$ bezeichnen wir die Menge ohne Elemente (\underline{leere Menge})
\item[d)]
	Mit $\abs{A}$ bezeichnen wir die Anzahl der Elemente der Menge $A$ (\underline{Kardinalität} oder \underline{Mächtigkeit} von $A$), zum Beispiel: \\
	$\abs{\{1,a,*\}} = 3, \quad \abs{\emptyset} = 0, \quad \abs{\mathbb{N}} = \infty, \quad \abs{\{\mathbb{N}\}} = 1$
\item[e)]
	$A \cap B \underbrace{:=}_{\mathrlap{\text{wird definiert als}}} \{x \mid x \in A \wedge x \in B\}$ heißt \underline{Durchschnitt} oder \underline{Schnittmenge} von $A$ und $B$.
	
	Grafische Veranschaulichung: Venn-Diagramm (\attention gilt nicht als Beweis)
	
	\begin{venndiagram2sets}
	\fillACapB
	\end{venndiagram2sets}

	
\item[f)]
	$A \cup B :=\{x \mid x \in A \lor x \in B \}$ heißt \underline{Vereinigung} von $A$ und $B$.
		
	\begin{venndiagram2sets}
	\fillA \fillB
	\end{venndiagram2sets}
	
\item[Beispiele:]
	$A = \{1,2,3\}$, $B = \{2,3,4\}$, $C = \{4\}$\\ \\
		$A \cap B = \{2,3\}$,\\
		$A \cap C = \emptyset$,\\
		$B \cap C = \{4\} = C$,\\
		$A \cup B = \{1,2,3,4\}$
		
\item[g)]
	$A$ und $B$ heißen \underline{disjunkt}, falls gilt $A \cap B = \emptyset$
		
	\begin{venndiagram2sets}[overlap=-20]		
	\end{venndiagram2sets}
	
\item[h)]
	$A$ heißt \underline{Teilmenge} von $B$, $A \subseteq B$, falls gilt: \\
	$x \in A \Rightarrow x \in B$\\
	Oder in Worten: Jedes Element von $A$ ist auch Element von $B$.
	
	Dasselbe bedeutet die Notation\\
	$B \supseteq A$ \\
	($B$ ist Obermenge von $A$)
	
	Beispiel: $\{1,2\} \subseteq \{1,2,3\} \subseteq \mathbb{N} \subseteq \mathbb{N}_0 \subseteq \mathbb{Z} \subseteq \mathbb{R}$ (reelle Zahlen)
	% TODO: Verify, OS Skript weicht ab.
	
	Es gilt: $\emptyset \subseteq A$ für jede Menge $A$.

	\textbf{Achtung: } Unterschied $\subseteq, \in$ !\\
	Zum Beispiel: \\
	$A = \{1, \mathbb{N}\}$ (hier ist die Menge $\mathbb{N}$ ein Element von A, keine Teilmenge!)\\
	$1 \in A, \qquad \mathbb{N} \in A, \qquad \mathbb{N} \nsubseteq A, \qquad 2 \notin A, \qquad \{1\} \subseteq A$
	%TODO Fehlende Zeile hier?

% =============
% 28 Oktober 2015
% =============

\item[i)]
	Zwei Mengen A, B heißen \underline{gleich} $(A = B$, falls gilt: $A \subseteq B$ und $B \subseteq A$
	(also $x \in A \Rightarrow / \Leftarrow / \Leftrightarrow x \in B$.

	%TODO Diagramm

	Darin liegt ein Beweisprinzip: Man zeigt $A = B$, indem man zeigt:
	\begin{itemize}
	\item $x \in A \Rightarrow x \in B$
	\item $x \in B \Rightarrow x \in A$ (mehr später)
	\end{itemize}

	Beispiel: \\
	$A = \{2, 3, 4\}, \qquad B = \{ x \in \mathbb{N} \mid x > 1$ und $x < 5\}$ \\
	$A = B$

\item[j)]
	$A \subsetneq B (A \subsetneqq B)$ bedeutet $A \subseteq B$, aber $A \neq B$.

	(d.h. $\exists x \in B$ mit $x \notin A$, aber $x \in B$) %TODO Verify \notin

	(A ist \underline{echte} Teilmenge von B.)

	%TODO Diagramm

\item[k)]
	Mit $P(A) := \{ B \mid \text{B ist eine Teilmenge von A}\} = \{B \mid B \subseteq A\}$
	bezeichnen wir die Menge aller (echten oder nicht echten) Teilmengen von A, die sogenannte \underline{Potenzmenge von A}.
	$(\emptyset \subseteq A \forall A, A \subseteq A \forall A)$

	Beispiel:

	$A = \{1,\}, P(A) = \{\emptyset, \{ \underbrace{1}_{A}\}\}$

	$B = \{1, 2\}, P(B) = \{ \emptyset, \{1\}, \{2\}, \{ \underbrace{1, 2}_{B}\}\}$

	$C = \{1, 2, 3\}, P(C) = ...$ (8 Elemente)

	$P(\emptyset) = \{ \emptyset \}$

	Was ist $P (P(A))$? \\
	$P(P(A)) = P(\{ \emptyset, \{ 1 \}\}) = \{ \emptyset, \{ \emptyset \}, \{1 \}, \{ \emptyset, \{ 1 \}\}$ %TODO: Klammern?

\item[l)]
	$A \backslash B := \{ x \mid x \in A$ und $x \notin B \}$ heißt die \underline{Differenz} (\textit{A ohne B}).

	Ist $A \subseteq X$ mit einer Obermenge $X$, so heißt $X \backslash A$ das \underline{Komplement} von $A$ (bezüglich $X$).
	Wir schreiben $A^C_X$ oder kurz $A^C$ (wenn X aus dem Kontext klar ist).

	%TODO Diagramme

\item[m)]
	$A \triangle B := (A \backslash B) \cup (B \backslash A)$ heißt die symmetrische Differenz von $A$ und $B$. %TODO: delta statt triangle?

	%TODO Diagramm

\end{description}

\subsection[Bemerkung (Verallgemeinerung von Vereinigung und Durchschnitt)]{Bemerkung} %2.2
Verallgemeinerung der Vereinigung und des Durchschnitts:

$A_1 \cap A_2 \cap ... \cap A_n = \{x \mid x \in A_1 \wedge x \in A_2 \wedge ... \wedge x \in A_n\}$

$$=: \bigcap_{i = 1}^{n} A_i$$

$A_1 \cup ... \cup A_n = \{x \mid x \in A_1 \lor  ... \lor x \in A_n\}$

$$=: \bigcup_{i = 1}^{n} A_i$$

Beziehungsweise noch allgemeiner:

Sei $S$ eine Menge von Mengen (\textit{System von Mengen})

$\cap A = \{ x \mid x \in A \forall A \in S\} $ \\
$ A \subset S$

$\cup A = \{ x \mid \exists A \in S$ mit $x \in A\} $ \\
$ A \in S$

\subsection[Definition (kartesisches Produkt)]{Definition} %2.3
Seien $A, B$ Mengen.

$A \underbrace{\times}_{Kreuz} B := \{(a, b) \mid a \in A, b \in B\}$

Die Menge aller geordneten Paare, heißt \underline{kartesisches Produkt} von $A$ und $B$ (nach René Descartes, 1596 - 1650).

Dabei legen wir fest: $(a, b) = (a', b')$ mit $(a, a' \in A, b, b' \in B):$ \\
$\Leftrightarrow a = a' \text{ und } b = b‘$.

Allgemein sei für Mengen $A_1, ... A_n (n \in \mathbb{N})$ \\
$A_1 \times A_2 \times ... \times A_n := \{a_1, a_2, ..., a_n) \mid a_i \in A_i, \forall i = 1 ... n\}$ \\
die Menge aller \underline{geordneten n-Tupel} (mit analoger Gleichheitsdefinition).

$(n = 2: \text{Paare}, n = 3: \text{Tripel})$

Schreibweise: \\
$$A_1 \times ... \times A:n =: \bigtimes_{i=1}^{n} A_i$$

Ist eine der Mengen $A_1, ... A_n$ leer, setzen wir $A_1 \times ... \times A_n = \emptyset$.

Statt $A \times A$ schreiben wir auch $A^2$, statt $\underbrace{A \times ... \times A}_{n-Faktoren} = A^n$.


\subsection{Beispiel} %2.4
$A = \{1, 2, 3\}, B = \{3, 4\}$

$(1, 3) \in A \times B, \underbrace{(3, 1)}_{B \times A} \notin A \times B,$

$(\underbrace{3}_{B \times B}, \underbrace{3}_{A \times A}) \in A \times B\in B \times A$

$(1, 2) \in A \times B, \in A \times A$

$A \times B = \{(1, 3), (1, 4), (2, 3), (2, 4), (3, 3), (3, 4)\}$

$B \times A = ...$

$B \times B = B^2 = \{(3, 3), (3, 4), (4, 3), (4, 4)\}$

% ==============
% 2 November 2015
% ==============

\subsection{Satz (Rechenregeln für Mengen)} %2.5

Seien $A$, $B$, $C$, $X$ Mengen. Dann gilt:
\begin{itemize}
	\item[a)]
		$A \cup B = B \cup A$ \\
		$A \cap B = B \cap A$ \\
		(Kommutativgesetz)
		
	\item[b)]
		$(A \cup B) \cup C = A \cup (B \cup C)$ \\	
		$(A \cap B) \cap C = A \cap (B \cap C)$ \\
		(Assoziativgesetz)
		
	\item[c)]
		$(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$ \\
		$(A \cap B) \cup C = (A \cup C) \cap (B \cup C)$ \\
		(Disbributivgesetz)
		
	\item[d)]
		$A,B \subseteq X$, dann \\
		$(A \cap B)^C_X = A^C_X \cup B^C_X$ \\
		$(A \cup B)^C_X = A^C_X \cap B^C_X$ \\
		(Regeln von DeMorgan)
		
	\item[e)]
		$A \subseteq X$, dann $(A^C_X)^C_X = A$
		
	\item[f)]
		$A \Delta B = (A \cup B) \setminus (A \cap B)$
		
		$(=\{x \mid x \in A \oplus x \in B\})$
			
		\begin{venndiagram2sets}
		\fillANotB \fillBNotA
		\end{venndiagram2sets}
		
	\item[g)]
		$A \cap B = A$ genau dann, wenn $A \subseteq B$ \\
		$(A \cap B) = A \quad \Leftrightarrow \quad A \subseteq B)$
		
	\item[h)]
		$A \cup B = A \quad \Leftrightarrow \quad B \subseteq A$
\end{itemize}

\subsubsection*{Beweis}

\begin{itemize}
	\item[a)]
		$A \cup B = \{x \mid x \in A \lor x \in B\}$ \\
		$\qquad \underset{\mathllap{\text{1.9 b)}}}{=} \{x \mid x \in B \lor x \in A\} = B \cup A$ \\
		\hfill \\		
		$A \cap B$ analog
		
	\item[b), c)]
		Übung, wie a) \\
		benutze Assoziativgesetz (1.9 c) ) bzw. Distributivgesetz (1.9 d) ) für logische Äquivalenzen.
		
	\item[d)]
		$(A \cap B)^C_X$ \\
		$ = \{x \mid x \in X \setminus (A \cap B) \}$ \\
		$ = \{x \mid x \in X \land (x \notin (A \cap B)) \}$ \\
		$ = \{x \mid x \in X \land \neg (x \in (A \cap B)) \}$ \\
		$ = \{x \mid x \in X \land \neg (x \in A \land x \in B) \}$ \\
		$ \underset{\mathllap{\text{De Morgan 1.9 e)}}}{=} \{x \mid x \in X \land (x \notin A \lor x \notin B)\}$ \\
		$ = \{x \mid ((x \in X) \land (x \notin A)) \lor ((x \in X) \land (x \notin B)) \}$ \\
		$ = A^C_X \cup B^C_X$
		
		2. Regel analog
		
	\item[e)]
		ähnlich
	\item[f) g) h)]
		später
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Kapitel 3: Beweismethoden
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Beweismethoden} %3

Ein mathematischer \underline{Beweis} ist die Herleitung der Wahrheit (oder Falschheit) einer Aussage aus einer Menge von \underline{Axiomen} (nicht beweisbare Grundtatsachen) oder bereits bewiesenen Aussagen nmittels logischen Folgerungen.

Bewiesene Aussagen werden \underline{Sätze} genannt.

\hfill

\underline{Lemma} - Hilfssatz, der nur als Grundlage für wichtigeren Satz formuliert und bewiesen wird.

\underline{Theorem} - wichtiger Satz

\underline{Korollar} - einfache Folgerung aus Satz, z.B. Spezialfall

\underline{Definition} - Benennung/Bestimmung eines Begriffs/Symbols

$\square$ - Zeichen für Beweisende ($\blacksquare$, q.e.d., wzbw...)

\hfill

Mathematische Sätze haben oft die Form:

Wenn $V$ (Voraussetzung) gilt, dann gilt auch $B$ (Behauptung)

($V$, $B$: Aussagen), kurz: $V \Rightarrow B$

Zu zeigen ist also, dass $V \Rightarrow B$ eine wahre Aussage ist.

\subsection{Direkter Beweis} %3.1

Gehe davon aus, dass $V$ wahr ist, folgere daraus, dass $B$ wahr ist.

[\space\space Sei $V$ wahr, $\Rightarrow$ ... \\
\text{\qquad\qquad\qquad} $\Rightarrow$ ... \\
\text{\qquad\qquad\qquad} $\Rightarrow$ ... \\
\text{\qquad\qquad\qquad} \space $\vdots$ \\
\text{\qquad\qquad\qquad} $\Rightarrow$ $B$ ist wahr\space\space]

Beispiel: $\underbrace{\text{Sei $n \in \mathbb{N}$. Ist $n$ gerade}}_{V}$, $\underbrace{\text{so ist auch $n^2$ gerade}}_{B}.$

\underline{Beweis:} Sei $n \in \mathbb{N}$ gerade. \hfill // V ist wahr
$\Rightarrow n = 2 \cdot k$ für ein $k \in \mathbb{N}$ \\
\text{\qquad\qquad} ($\exists k \in \mathbb{N}$ mit $n = 2 \cdot k$) \\
$\Rightarrow n^2 = (2 \cdot k)^2 = 4 \cdot k^2 = 2 \cdot (2k^2)$ \\
$\Rightarrow n^2$ ist gerade. \hfill // B ist wahr

\hfill $\square$

\subsection{Beweis durch Kontraposition} %3.2

vgl. Satz 1.9 f) \qquad $A \Rightarrow B \quad \equiv \quad \neg B \Rightarrow \neg A$

Statt $V \Rightarrow B$ zu zeigen, können wir also auch $\neg B \Rightarrow \neg V$ zeigen.


[ Es gelte $\neg B \Rightarrow$ ... \\
\text{\qquad\qquad\qquad} $\Rightarrow$ ... \\
\text{\qquad\qquad\qquad} $\Rightarrow$ ... \\
\text{\qquad\qquad\qquad} \space $\vdots$ \\
\text{\qquad\qquad\qquad} $\Rightarrow$ es gilt $\neg V$ ]

\hfill

\underline{Beispiel:} Sei $n \in \mathbb{N}$.

$\underbrace{\text{Ist $n^2$ gerade}}_{V}$, $\underbrace{\text{so ist auch $n$ gerade}}_{B}$.

\hfill

\underline{Beweis durch Kontraposition:}

Sei $n$ ungerade. \hfill // $\neg B$ gilt.

$\Rightarrow n = 2k + 1$ für ein $k \in \mathbb{N}_0$ \\
$\Rightarrow n^2 = (2k+1)^2 = 4k^2+4k+1 = \underbrace{\underbrace{2(2k^2+2k)}_{\text{gerade}}+1}_{\text{ungerade}}$ \\
$\Rightarrow n^2$ ist ungerade. \hfill // $\neg V$ gilt.

\hfill $\square$

\subsection{Beweis durch Widerspruch, indirekter Beweis} %3.3

Zu zeigen ist Aussage $A$. Wir gehen davon aus, dass $A$ \underline{nicht} gelte ($\neg A$ ist wahr) und folgern durch logische Schlüsse eine zweite Aussage $B$, von der wir wissen, dass sie falsch ist. Wenn alle logischen Schlüsse korrekt waren, muss also $\neg A$ falsch gewesen sein, also $A$ wahr.

( $((\neg A \Rightarrow B) \land (\neg B)) \Rightarrow A$ ist Tautologie)

% ==============
% 4 November 2015
% ==============

\textbf{Beispiel:} [Euklid] $\sqrt{2} \notin \mathbb{Q}$

\underline{Beweis:} Wir nehmen an, dass die Aussage falsch ist, also $\sqrt{2} \in \mathbb{Q}$ gilt,
das heißt $\sqrt{2} = \frac{p}{q}$ mit p, q $\in \mathbb{Z} (q \neq 0)$ teilerfremd (vollständig gekürzter Bruch)

$\Rightarrow 2 = \frac{p^2}{q^2}$

$\Rightarrow p^2 = 2q^2$, also ist $p^2$ gerade, damit aber auch p gerade (Beispiel in 3.2), also $p = 2  \cdot  r$ mit $r \in \mathbb{Z}$.

$\Rightarrow p^2 = (2r)^2 = 2q^2$ \\
$\Rightarrow 4r^2 = 2q^2$ \\
$\Rightarrow \underline{2r^2 = q^2}$ \\
$\Rightarrow q^2$ gerade \\
$\Rightarrow q$ gerade

Also: $p$ gerade, $q$ gerade, Widerspruch zu $p, q$ teilerfremd.

Also war die Annahme falsch, es muss $\sqrt{2} \notin \mathbb{Q}$ gelten. $\square$

\subsection{Vollständige Induktion} %3.4
Eine Methode, um Aussagen über natürliche Zahlen zu beweisen.

\textbf{Beispiel:} Gauß

$ 1 + 2 + ... + 100 = ?$

\begin{tabular}{c c c c c }
1 & 2 & 3 & ... & 50 \\
+ 100 & 99 & 98 & ... & 51 \\
\hline
101 & 101 & 101 & ... & 101 \\
\end{tabular}

$50  \cdot  101 = 5050$

$(= \frac{100}{2}  \cdot  101)$

\underline{Allgemein:} \\
$ 1 + 2 + 3 + ... + n \underbrace{=}_{Vermutung} \frac{n (n+1)}{2}$ \\
$(n \in \mathbb{N})$

\subsubsection{Prinzip der vollständigen Induktion} %3.4.1
Sei $n_0 \in \mathbb{N}$ fest vorgegeben (oft $n_0 = 1)$. \\
Für jedes $n \geq n_0, n \in \mathbb{N}$, sei $A(n)$ eine Aussage, die von $n$ abhängt.

Es gelte:
\begin{enumerate}
\item $A(n_0)$ ist wahr (\textit{Induktionsanfang})
\item $\forall n \in \mathbb{N}, n \geq n_0$:
$\underbrace{\text{Ist} A(n) \text{wahr,}}_{Induktionsvorraussetzung} \underbrace{\text{so ist} A(n+1) \text{wahr}}_{Induktionsbehauptung}.$ (\textit{Induktionsschritt})
\end{enumerate}

Dann ist die Aussage $A(n)$ für alle $n \geq n_0$ wahr. (\textit{Dominoprinzip})

(\underline{Bemerkung}: gilt auch für $\mathbb{N}_0$ ($n_0 = 0$ auch möglich) und für $n_0 \in \mathbb{Z}$, Behauptung gilt dann für alle $n \in \mathbb{Z}$ mit $n \geq n_0$).

\underline{Beispiel}: 

\begin{description}

\item[a) Kleiner Gauß]
$1 + 2 + ... + n = \frac{n(n+1)}{2} \forall n \in \mathbb{N}$

\underline{Beweis}:

$A(n) : 1 + 2 + ... + n = \frac{n(n+1)}{2}$

\begin{itemize}
\item Induktionsanfang $(n = 1): A(1): 1 = \frac{1 \cdot (1+1)}{2}$
\item Induktionsschritt:

Induktionsvorraussetzung: \\
sei $n \geq 1$. Es gelte $A(n)$, d.h. $1+ ... +n = \frac{n(n+1)}{2}$

Induktionsbehauptung: \\
Es gilt $A(n+1)$, d.h. $1+ ... +n + (n+1) = \frac{(n+1) (n+1 + 1)}{2}$

Beweis: $\underbrace{1 + 2 + ... + n}_{} + (n+1) \underbrace{=}_{Ind.vor.} \underbrace{\frac{n(n+1)}{2}} + (n+1)$

$\qquad\qquad\qquad\qquad\qquad\qquad\qquad$ \space
$ = \frac{n^2 + n + 2n + 2}{2}$

$\qquad\qquad\qquad\qquad\qquad\qquad\qquad$ \space
$=\frac{(n+1)(n+2)}{2}$

$A(n+1)$ \hfill $\square$

\end{itemize}

\item[b)]

$A(n): 2^n \geq n \forall n \in \mathbb{N}$
\begin{itemize}
\item Induktionsanfang: $(n = 1 ) : A(1)$ gilt: $2^1 \geq 1$
\item Induktionsschritt:

Induktionsvorraussetzung: \\
Sei $n \geq 1$. Es gelte $A(n)$, d.h. $2^n \geq n$

Induktionsbehauptung: (Zu zeigen!): \\
Es gilt $A(n+1)$, d.h. $2^{n+1} \geq n+1$.

Beweis: $2^{n+1} = 2 \cdot 2^n \underbrace{\geq}_{Ind.vor.} 2  \cdot  n$

$\qquad\qquad\qquad\qquad\qquad$
$= n + n$

$\qquad\qquad\qquad\qquad\qquad$
$\geq n + 1$,

$\qquad\qquad$
also \qquad $2^{n+1} \geq n+1$ \hfill $\square$
\end{itemize}

\end{description}

\subsubsection{Bemerkung} %3.4.2
Für Formeln wie in Beispiel 3.4.1a) benutzen wir das \textit{Summenzeichen} $\Sigma$ (Sigma, großes griechisches S)

$\displaystyle\sum_{k = 1}^{n} k = \frac{n(n+1)}{2}$
$1 + 2 + 3 + ... +n$
$k = 1 k = 2 k = 3 k = n$ %Tabelle

weitere Bsp:

$\sum_{k = 1}^{n} 2k = 2 \cdot 1 + 2 \cdot 2 + ... 2 \cdot n$
$\sum_{k=4}^{n} 2k = 2 \cdot 4 + 2 \cdot 5 + .... 2 \cdot n$

$\sum_{k=1}^{3} 7 = 7 + 7 + 7 = 21$ %unten drunter k = 1 k= 2 k = 3

allg. $\sum_{k=m}^{n} a_k = a_m + a_{m+1} + a_n$
$(a_m, a_{m+1}, ... ,a_n \in \mathbb{R})$

k heißt Summationsindex

$\sum_{k=m}^{n} a_k = \sum_{i = m}^{n} a_i$

Schreibweisen:

$\displaystyle\sum_{k = 1}^{n} a_k, \sum_{k = 1}^{n} a_k, \sum_{k \in \mathbb{N}} a_k, \sum_{k=1, k \neq 2}^{4} a_k = a_1 + a_3 + a_4$

Für $n < m$ setzt man

$\sum_{k=m}^{n} a_k = 0$ (leere Summe), z.B. $\sum_{k=7}^{3} k = 0$ \\

% ==============
% 9 November 2015
% ==============

\textbf{Produktzeichen $\Pi$} (Pi, großes griechisches P)

$\displaystyle\prod_{k=m}^{n} a_k = a_m  \cdot  a_{m+1} ... a_n,$ \\
für $n < m$ setze $\displaystyle\prod_{k=m}^{n} a_k = 1$

\underline{Rechenregeln für Summen} (zu beweisen z.B. durch vollständige Induktion)

\begin{description}
	\item[a)] \hfill

	$\sum_{k=m}^{n} a = (n - m+ 1)  \cdot  a$

	$(\sum_{k=3}^{5} a = a + a + a = (5-3+1) \cdot a)$

	\item[b)] \hfill

	$\sum_{k=m}^{n} (c  \cdot  a_k) = c  \cdot  \sum_{k=m}^{n} a_k$

	\item[c) Indexverschiebung] \hfill

	$\sum_{k=m}^{n} a_k = a_m + a_{m+1} + ... a_n$ \\
	$\qquad = a_{(m + e) - e} + a_{(m+e+1)-e} + ... + a_{(n+e)-e}$

	neuer Summationsindex $j := k +e$ \\
	(k durchläuft Werte: $m, m+1 ..., n$, \\
	j durchläuft Werte: $m + e, m+e+1, ... n+e)$

	also gilt
	$\sum_{k=m}^{n} a_k = \sum_{j = m+e}^{n+e} a_{j-e}$

	(Beispiel:
	$\sum_{k=0}^{5} a_k  \cdot  x^{k+2} = \sum_{j = 2}^{7} a_{j-2}  \cdot  x^j)$

	\item[d) Addition von Summen gleicher Länge] \hfill

	$\sum_{k=m}^{n} (a_k + b_k) = \sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k$

	\item[e) Aufspalten] \hfill

	$\sum_{k=m}^{n} a_k = \sum_{k=m}^{l} a_k + \sum_{k=l+1}^{n} a_k$ für  $m < l < n$

	\item[f) Teleskopsumme] \hfill

	$\sum_{k=m}^{n} (a_k - a_{k+1}) = a_m - a_{n+1}$

	$\sum_{k=m}^{n} (a_k - a_{k+1}) = (a_m - a_{m+1} + (a_{m+1} - a_{m+2} + (a_{m+2} ... ) + (a_n - a{n+1})))$ % Durchgestrichen

	\item[g) Doppelsummen] \hfill

	$\sum_{i=1}^{n} \sum_{j=1}^{m} a_{ij}$

	$= \sum_{i=1}^{n} (a_{i1} + a_{i2} + ... + a_{im}$ \\
	$= a_{11} + a_{12} + a_{13} + ... + a_{1m}$ \\
	$+ a_{21} + a_{22} + a_{2m}$ \\
	$+ ...$ \\
	$+ a_{n1} + a_{n2} + ... + a_{nm}$

	$\sum_{j=1}^{m} \sum_{i=1}^{n} aj$

\end{description}

\subsubsection{Verschärftes Induktionsprinzip} %3.4.3

$A(n), n_0$ wie in 3.4.1

Es gelte:
\begin{itemize}
	\item[(1)] $A(n_0)$ ist wahr
	\item[(2)] $\forall n \geq n_0:$ \\
	Sind $A(n_0), \quad ... \quad , A(n)$ wahr, so ist $A(n+1)$ wahr.
	
	(d.h. $A(n_0) \land A(n_0+1) \land ... \land A(n) \Rightarrow A(n+1)$)
\end{itemize}
Dann ist A(n) wahr für \underline{alle} $n \in \mathbb{N}, n \geq n_0$

\hfill

\underline{Beispiel: } $A(n)$: Jede natürliche Zahl $n > 1$ ist Primzahl oder Produkt von Primzahlen.

\underline{Beweis:}

\underline{Induktionsanfang:} ($n_0=2$). $n=2$ ist Primzahl \checkmark

\underline{Induktionsschritt:} Sei $n \geq n_0 \qquad (n \geq 2)$

\underline{$\bullet$ Induktionsvoraussetzung:}

Aussage gilt für $2,3,4,...,n$

($A(2),A(3),A(4),...,A(n)$ wahr)

\underline{$\bullet$ Induktionsbehauptung:}

$A(n+1)$ gilt, d.h. $n+1$ ist Primzahl oder Produkt von Primzahlen.

Beweis:

\begin{itemize}
\item falls $n+1$ Primzahl, so gilt $A(n+1)$
\item falls $n+1$ keine Primzahl, dann ist $n+1 = k \cdot l$, für $k,l \in \mathbb{N}$, \\
$1 < k < n+1, \quad 1 < l < n+1$ ($k=l$ möglich).

Nach Induktionsvoraussetzung:

Aussage gilt für $k$ und $l$ $\Rightarrow$ $n+1$ ist Produkt von Primzahlen. \\
$A(n+1)$ ist wahr. \hfill $\square$
\end{itemize}


\subsection{Schubfachprinzip} %3.5

\subsubsection{Idee} %3.5.1
In einem Schrank befinden sich $n$ verschiedene Paar Schuhe. Wie viele Schuhe muss man maximal herausziehen, bis man sicher ein zusammenpassendes Paar hat?

(Antwort: $n+1$)

\subsubsection{Satz (Schubfachprinzip, engl.: {\it pigeon hole principle})} %3.5.2

Seien $k,n \in \mathbb{N}$.

Verteilt man $n$ Objekte auf $k$ Fächer, so gibt es ein Fach, das mindestens $\ceil{\frac{n}{k}}$ Objekte enthält.

(Dabei bezeichnet $\ceil{x}$ die kleinste ganze Zahl $z$ mit $x \leq z$.)

\underline{Beweis} (durch Kontraposition):

( $\underbrace{n \text{ Objekte, } k \text{ Fächer}}_{A} \Rightarrow \underbrace{\exists \text{ Fach mit mind. } \ceil{\frac{n}{k}} \text{ Objekten}}_{B}$

statt $A \Rightarrow B$ zeige $\neg B \Rightarrow \neg A$

\begin{itemize}
\item[$(\neg B)$]
	Jedes Fach enthalte höchstens $\ceil{\frac{n}{k}}-1$ Objekte.
	
	Dann ist die Gesamtzahl von Objekten höchstens
	
	$$k \cdot \underbrace{(\ceil{\frac{n}{k}}-1)}_{< \frac{n}{k}} < k \cdot \frac{n}{k} = n$$

\item[$(\neg A)$]
	es gibt also \underline{weniger} als $n$ Objekte
	\hfill $\square$

\end{itemize}

% ==============
% 11 November 2015
% ==============

\subsubsection{Beispiel} %3.5.3

\begin{description}
\item[a)]
Wieviele Menschen müssen auf einer Party sein, damit \underline{sicher} 2 am selben Tag Geburtstag haben?

367

\item[b)]
Auf jeder Party mit mindestens 2 Gästen gibt es 2 Personen, die dieselbe Anzahl \underline{Freunde} auf der Party haben.

Beweis: Sei $n$ die Anzahl der Partygäste. Jeder Gast kann mit $0, 1, 2, ..., n-1$ Gästen befreundet sein ($n$ Möglichkeiten).

Aber: Es kann nicht sein, dass ein Gast $0$ Freunde hat und gleichzeitig ein Gast $n-1$ (=alle) Freunde hat.

$\Rightarrow$ Es gibt $n-1$ mögliche Werte für die Anzahl der Freunde, entspricht $n-1$ Fächern.

Jeder der $n$ Gäste trägt sich in ein Fach ein \\
$\Rightarrow$ mindestens $2$ Gäste sind im selben Fach. \hfill $\square$

\item[c)]
In Berlin gibt es mindestens 2 Personen, die genau dieselbe Anzahl Haare auf dem Kopf haben.

Beweis: Anzahl Haare im Durchschnitt:

\begin{tabular}{ c c }
blond & 150.000 \\
braun & 110.000 \\
schwarz & 100.000 \\
rot & 90.000
\end{tabular}

zur Sicherheit: maximal 1 Millionen Haare möglich \\
entspricht 1 Mio Fächer.

Anzahl Einwohner in Berlin: 3,5 Millionen $\Rightarrow$ Behauptung 3.5.2 \hfill $\square$

\end{description}

\subsection{Weitere Beweistechniken (Werkzeugkiste)} %3.6

\begin{description}
\item[a)]
Wichtigste Technik: Ersetzen eines mathematischen Begriffs durch seine Definition (und umgekehrt).
$A( \subset B = \{x \mid x \in A \lor x \in B\})$

\item[b)]
Aussagen der Form $\forall a \in S$ gilt $P(a)$: \\
beginne mit: Sei $a \in S$, zeige $P(a)$.

\item[c)]
Aussage der Form $\exists a \in S$ mit $P(a)$ \\
oft: finde/gebe konkretes Element $a$ an, für dass $P(a)$ gilt.

\item[d)]
Gleichheit von Mengen zeigt man oft mittels Inklusion (vgl. Definition 2.1(i))

Zu zeigen: $A = B$ ($A, B$ Mengen) \\
zeige: $A \subseteq B$ (Sei $a \in A \Rightarrow ... \Rightarrow ... \Rightarrow a \in B$) 2.1 (i)) \\
und $B \subseteq A$ (Sei $b \in B \Rightarrow ... \Rightarrow ... \Rightarrow b \in A$)

\textit{$\subseteq$} ...\\
\textit{$\supseteq$} ... \\

\underline{Beispiel:} 2.5f)

$A \triangle B = (A \cup B) \backslash (A \cap B)$

Beweis:

\begin{itemize}
\item{$\subseteq$} \\
Sei $x \in A \triangle B = (A \backslash B) \cup (B \backslash A)$

\begin{itemize}
\item[1. Fall]: \hfill \\
$x \in A \backslash B$, dann gilt $x \in A$, also $x \in A \cup B$

Außerdem $x \notin B$, also gilt auch $x \notin A \cap B$

$\Rightarrow x \in (A \cup B) \backslash (A \cap B)$

\item[2.Fall] \hfill \\
Ist $ x \in B \backslash A$, so argumentiere analog.
\end{itemize}

\item{$\supseteq$} \\
Sei $x \in (A \cup B) \backslash (A \cap B)$ \\
$\Rightarrow x \in A$ oder $x \in B$.

\begin{itemize}
\item[1.Fall] \hfill \\
$x \in A$, so ist $x \notin B$, da $x \notin A \cap B$ \\
$\Rightarrow x \in A \backslash B \subseteq (A \backslash B) \cup (B \backslash A)$ \\
$ = A \triangle B$, \\
d.h. $x \in A \triangle B$.

\item[2.Fall] (1. Fall analog) \hfill \\
$x \in B$, so $x \notin A$, da $x \notin A \cap B$ \\
$\Rightarrow x \in B \backslash A \subseteq A \triangle B$ \\
Also $x \in A \triangle B$
\end{itemize}

\end{itemize}

\item[e)]
Äquivalenzen $(A \Leftrightarrow B, A, B$ Aussagen) werden meist in 2 Schritten bewiesen:

\textit{Hinrichtung} zeigt $A \Rightarrow B$, \\
\textit{Rückrichtung} zeigt $B \Rightarrow A$.

\textit{$\Rightarrow$: ...} \\
\textit{$\Leftarrow$: ...}

(oft auch eine von beiden mittels Kontraposition)

\underline{Beispiel:} 2.5g) $A \cap B = A \Leftrightarrow A \subseteq B$

Beweis: \\
\textit{$\Rightarrow$}: Sei $ A \cap B = A$. Dann ist $A = A \cap B \subseteq B$ \\
\textit{$\Leftarrow$}: Sei $A \subseteq B$. Dann ist $A \subseteq A$ und $A \subseteq B$, \\
also ist $A \subseteq A \cap B$ \\
außerdem $A \cap B \subseteq A$

$\Rightarrow A = A \cap B$ \hfill $\square$

2.5h) analog.

\item[f)]
Äquivalenzen der Form: \\
Sei ... . Dann sind folgende Aussagen äquivalent:

\begin{itemize}
\item a) ...
\item b) ...
\item c) ..
\item d) ...
\end{itemize}

Zeigt man durch \textit{Ringschluss}: \\
Zeige $a) \Rightarrow b) \Rightarrow c) \Rightarrow d) \Rightarrow a)$ \\
(oder andere Reihenfolge, soll \textit{Ring} geben.)

\end{description}

% ==============
% 16 November 2015
% ==============

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Kapitel 4: Abbildungen
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Abbildungen} %4

\subsection{Definition} %4.1

\begin{itemize}
\item[a)] Eine \underline{Abbildung} (oder \underline{Funktion})
$$f \colon A \rightarrow B$$ besteht aus
	\begin{itemize}
	\item zwei nicht-leeren Mengen:\\
		$A$, dem \underline{Definitionsbereich} von f \\
		$B$, dem \underline{Bildbereich} von f
	\item und einer Zuordnungsvorschrift, die \underline{jedem} Element 
	$a \in A$ \underline{genau} \underline{ein} Element $b \in B$ zuordnet
	\end{itemize}
	
Wir schreiben dann $b = f(a)$, nennen $b$ das \underline{Bild} oder den \underline{Funktionswert} von $a$ (unter $f$), und $a$ (ein) \underline{Urbild} von $b$ (unter $f$).

Notation:
$$f \colon A \to B$$
$$\qquad\quad a \mapsto f(a)$$

\item[b)] Die Menge $G_f := \{(a,f(a)) \mid a \in A\} \subseteq A \times B$ heißt der \underline{Graph} von $f$.

\end{itemize}

\subsection{Beispiele} %4.2
Siehe Folien!

\subsection{Beispiele} %4.3

\begin{itemize}
\item[a)] $A$ Menge

	$id_A \colon A \rightarrow A$ \\
	$\text{\qquad\space} x \mapsto x$
	
	identische Abbildung
	
\item[b)] 
		$\text{\quad} f \colon \mathbb{R} \rightarrow \mathbb{R}$ \\
		$\text{\space\qquad\space} x \mapsto x^2$ ist Abbildung (aus der Schule bekannt als $f(x)=x^2$)
		%TODO Graph von x^2
		
\item[c)] $\land$ kann als Abbildung aufgefasst werden, $+$ ebenso:

$\land \colon \{0,1\} \times \{0,1\} \rightarrow \{0,1\}$ \\
$\text{\qquad\qquad\quad} (A,B) \mapsto A \land B$

$+ \colon \mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R}$ \\
$\text{\qquad}(a,b) \mapsto a+b$
\end{itemize}

Allgemein bezeichnet man eine Abbildung $\{0,1\}^n \rightarrow \{0,1\}^m$ ($n,m \in \mathbb{N}$) als boolesche Funktion.

\subsection[Definition (Gleichheit von Abbildungen)]{Definition} %4.4

Zwei Abbildungen $f \colon A \rightarrow B$, $g \colon C \rightarrow D$ heißen \underline{gleich} (in Zeichen: $f=g$), wenn:
\begin{itemize}
\item $A=C$
\item $B=D$
\item $f(a)=g(a)$
\end{itemize}
$\forall a \in A (=C)$

\subsection{Beispiel} %4.5

$f \colon \{0,1\} \rightarrow \{0,1\}, x \mapsto x$ \\
$g \colon \{0,1\} \rightarrow \{0,1\}, x \mapsto x^2$

$f=g$

\subsection[Definition (Bild, Urbild, Injektivität, Surjektivität, Bijektivität)]{Definition} %4.6

Sei $f \colon A \rightarrow B$, seien $A_1 \subseteq A, B_1 \subseteq B$ Teilmengen.

Dann heißt

\begin{itemize}
\item[a)] $f(A_1) := \{f(a) \mid a \in A_1\} \subseteq B$ das \underline{Bild} von $A_1$ (unter $f$) (Bildmenge).

(Beispiel: $f \colon \mathbb{N} \rightarrow \mathbb{N}$ \\
$\text{\qquad\qquad\qquad} x \mapsto 2x$ \\
$\text{\qquad\qquad} A_1 = \{1,3\}$ \\
$\text{\space\qquad\space} f(A_1) = \{f(1), f(3)\} = \{2,6\}$ )

\item[b)] $f^{-1}(B_1) := \{a \in A \mid f(a) \in B_1\} \subseteq A$ \\
das \underline{Urbild von $B_1$} (unter $f$).

(Beispiel oben: $B_1 = \{8,14,100\}, f^{-1}(B_1) = \{4,7,50\}$ \\
$\text{\qquad\qquad\qquad\quad} B_2 = \{3\}, f^{-1}(B_2) = \emptyset$ )

\item[c)] $f$ \underline{surjektiv}, falls gilt: $f(a) = B$

(d.h. $\forall b \in B \exists a \in A : f(a) = b$ )

{\color{orange} [ alle Elemente von B werden getroffen ] }

\item[d)] $f$ \underline{injektiv}, falls gilt:

$\forall a_1, a_2 \in A$ mit $a_1 \neq a_2$ gilt $f(a_1) \neq f(a_2)$

(äquivalent: $f(a_1) = f(a_2) \Rightarrow a_1 = a_2$ )

{\color{orange} [ kein Element von B wird doppelt getroffen ] }

\item[e)] $f$ \underline{bijektiv}, falls $f$ surjektiv und injektiv ($f$ ist Bijektion).

{\color{orange} [ jedes Element wird genau einmal getroffen ] }

\end{itemize}

\subsection{Beispiele} %4.7
siehe Folien

\begin{itemize}
\item[a)] $f$ aus Beispiel in 4.6 a) ist injektiv, aber nicht surjektiv:

$f(\mathbb{N})$ ist Menge der geraden natürlichen Zahlen, nicht $\mathbb{N}$.

\item[b)] $f \colon \mathbb{R} \rightarrow \mathbb{R}$ \\
$\text{\space\quad\space} x \mapsto x^2$

nicht surjektiv:

$f(\mathbb{R}) = \mathbb{R}^+_0 = \{x \in \mathbb{R} \mid x \geq 0 \} \neq \mathbb{R}$

nicht injektiv:

$f(1) = f(-1) = 1$ \\
$f(2) = f(-2) = 4$

\hfill

$g \colon \mathbb{R}^+_0 \rightarrow \mathbb{R}^+_0$ \\
$\text{\qquad} x \mapsto x^2$

injektiv, surjektiv, bijektiv

\item[c)] $f \colon \mathbb{R} \rightarrow \mathbb{R}$ \\
	$x \mapsto 2x+1$
	
	ist surjektiv:
	
	Sei $y \in \mathbb{R}$. Zeige: $\exists x \in \mathbb{R}$ mit $y = 2x+1$ (vgl. 3.6 b) )
	
	Wähle $x = \frac{y-1}{2}$
	
	$f$ ist injektiv:
	
	angenommen, es gibt $x_1,x_2 \in \mathbb{R}$ \\
	mit $f(x_1) = f(x_2)$, d.h. \\
	$2x_1+1 = 2x_2+1$, \\
	dann folgt $x_1 = x_2$. \qquad $\circledast$	
\end{itemize}

% ==============
% 23 November 2015
% ==============

\subsection[Definition (Umkehrfunktion)]{Definition} %4.8
Sei $f \colon A \rightarrow B$ bijektiv. Dann definieren wir die \underline{Umkehrfunktion}.

$f^{-1} \colon B \rightarrow A$, indem wir jedem $b \in B$ dasjenige $a \in A$ zuordnen, für das $f(a) = b$ gilt.

\subsection{Beispiel} %4.9
$A (a_1, a_2, a_3) \qquad B (b_1, b_2, b_3)$

$f \colon (A \rightarrow B)$ bijektiv \\
$a_1 \rightarrow b_2$ \\
$a_2 \rightarrow b_3$ \\
$a_3 \rightarrow b_1$ \\

$f^{-1} \colon B \rightarrow A$ \\
$b_1 \rightarrow a_3$ \\
$b_2 \rightarrow a_1$ \\
$b_3 \rightarrow a_2$ \\

\subsection{Bemerkung} %4.10
Man kann jedem $b \in B$ wirklich ein $a \in A$ zuordnen, das $f(a) = b$ erfüllt, denn $f$ ist surjektiv. Nur \underline{ein} solches $a$, denn $f$ ist injektiv.

\subsection[Definition (Hintereinanderausführung/Komposition)]{Definition} %4.11
Seien $g \colon A \rightarrow B$ \qquad $f \colon B \rightarrow C$ \\
Abbildungen.

Dann heißt die Abbildung:
$f \circ g \colon A \rightarrow C$ \\
$a \rightarrow (f \circ g) (a):=$ \\
$f(g(a)) \forall a \in A$

die \underline{Hintereinanderausführung} oder \underline{Komposition} von $f$ mit $g$.

\textit{f nach g}

$A \underbrace{\rightarrow}_{g} B \underbrace{\rightarrow}_{f} C$ % Pfeil unten von A nach C mit "f o g"

\subsection{Beispiel} %4.12
$A = B = C = \mathbb{R}$

$f \colon \mathbb{R} \rightarrow \mathbb{R} \qquad g \colon \mathbb{R} \rightarrow \mathbb{R}$ \\
$\qquad x \rightarrow x + 1 \qquad x \rightarrow 2x$

$(f \circ g) (x) = f(g(x)) = f(2x) = 2x+1$

$(g \circ f) (x) = g(f(x)) = g(x+1) = 2 \cdot (x+1)$ \\
$= 2x +2$

hier also $f \circ g \neq g \circ f$!

\subsection[Satz (Eigenschaften der Komposition)]{Satz} %4.13
Die Komposition \{inj., surj., bij\} Abbildungen ist \{inj., surj., bij\}

Beweis: Pü / Ü

\subsection{Satz (Charakterisierung bijektiver Abbildungen)} %4.14

Sei $f \colon A \rightarrow B$ eine Abbildung.

$f$ ist bijektiv genau dann, wenn es eine Abbildung
$g \colon B \rightarrow A$ gibt mit \\
$g \circ f = id_{A}$ und  $f \circ g = id_{B}$.

Diese Abbildung $g$ ist eindeutig und genau die Umkehrfunktion von $f$, also \\
$g = f^{-1}$.

$f^{-1}$ ist ebenfalls bijektiv und es gilt $(f^{-1})^{-1} = f$

\underline{Beweis: }

\begin{itemize}

\item[''$\Rightarrow$'']

Sei $f$ bijektiv. Dann existiert für jedes $b \in B$ genau ein $a \in A$ mit \textcolor{orange}{\underline{\textcolor{black}{$b = f(a)$}}}.

Definiere nun also $g: B \rightarrow A$ mit \color{red} \underline{\color{black} $g(b)=a$}\color{black}, dann gilt die Aussage:

$(g \circ f) (a) = g(\textcolor{orange}{\underline{\textcolor{black}{f(a)}}}) = g(\textcolor{orange}{\underline{\textcolor{black}{b}}}) = a = id_A(a)$

$(f \circ g) (b) = f(\textcolor{red}{\underline{\textcolor{black}{g(b)}}}) = f(\textcolor{red}{\underline{\textcolor{black}{a}}}) = b = id_B(b)$

\item[''$\Leftarrow$'']

Es existiere Abbildung $g$ wie angegeben (zu zeigen: $f$ ist bijektiv)

\begin{itemize}
\item[$\bullet$] \textbf{$f$ surjektiv:} Sei $b \in B$. Dann ist $g(b) \in A$, $f(\underbrace{g(b)}_{\mathrlap{\text{das ist das gesuchte $a$! ( $a := g(b)$ )}}}) = id_B(b) = b$, d.h. $g(b)$ ist Urbild von $b$ unter $f$.

\item[$\bullet$] \textbf{$f$ injektiv:} 

Sei \textcolor{red}{\underline{\textcolor{black}{$f(a_1) = f(a_2)$}}}

Dann ist $\underline{\underline{a_1}} = g(\textcolor{red}{\underline{\textcolor{black}{f(a_1)}}}) = g(f(a_2)) = \underline{\underline{a_2}}$

\item[$\bullet$] \textbf{Eindeutigkeit von $g$:} 

Angenommen es gäbe Abbildungen $g_1,g_2$ mit angegebenen Eigenschaften.

Sei $b \in B$. Dann gibt es genau ein $a \in A$ mit \textcolor{orange}{\underline{\textcolor{black}{$f(a)=b$}}}.

Also $g_1(b) = g_1(\textcolor{orange}{\underline{\textcolor{black}{f(a)}}}) = a = g_2(\textcolor{orange}{\underline{\textcolor{black}{f(a)}}}) = g_2(\textcolor{orange}{\underline{\textcolor{black}{b}}})$, \\
d.h. $g_1 = g_2$

\item[$\bullet$] \textbf{$f^{-1}$ bijektiv, $(f^{-1})^{-1} = f$:}

folgt aus $f \circ f^{-1} = id_B$, $f^{-1} \circ f = id_A$, \\
wende Aussage des Satzes auf $f^{-1}$ an. \hfill $\square$

\end{itemize}

\end{itemize}

\subsection[Bemerkung / Definition (Endlichkeit, Mächtigkeit)]{Bemerkung / Definition} %4.15

Bijektivität erlaubt präzise Definition der Endlichkeit / Unendlichkeit von Mengen:

\begin{itemize}
\item[a)] Menge $M \neq \emptyset$ heißt \underline{endlich} $\Leftrightarrow \exists n \in \mathbb{N} : \exists$ bijektive Abbildung $f \colon \{1,...,n\} \to M$.

($\emptyset$ wird auch als endlich bezeichnet).

Andernfalls heißt $M$ \underline{unendlich}.

[Hilberts Hotel]

\item[b)] Zwei Mengen $M_1, M_2$ heißen \underline{gleichmächtig}, falls es eine bijektive Abbildung $g \colon M_1 \rightarrow M_2$ gibt.

\underline{Beispiel:} $\mathbb{N}, 2\mathbb{N}$ (alle geraden natürlichen Zahlen) gleichmächtig:

$$g \colon \mathbb{N} \to 2\mathbb{N}$$
$$\quad n \mapsto 2n$$ \hfill ist bijektiv.



% ==============
% 25 November 2015
% ==============

\item[c)] Menge $M$ heißt \underline{abzählbar unendlich}, wenn $M$ gleichmächtig ist wie $\mathbb{N}$, d.h. $\exists$ bijektive Abbildung.

$h \colon \mathbb{N} \rightarrow M$.

\end{itemize}

\underline{Beispiel:}
\begin{itemize}
\item $\mathbb{N}$  abzählbar unendlich: $h = id_{\mathbb{N}}$
\item $\mathbb{N}$ abzählbar unendlich: $h \colon \mathbb{N} \rightarrow \mathbb{N}_{0} (x \rightarrow x-1)$ ist bijektiv.
\item $\mathbb{Z}$ ist abzählbar unendlich: (Geschichte vom Teufel:  $h \rightarrow \mathbb{Z}$ \\
$1 \rightarrow$ 0 \\
$2 \rightarrow 1$ \\
$3 \rightarrow -1$ \\
$4 \rightarrow 2$ \\
$\underbrace{5}_{Tag} \rightarrow \underbrace{-2}_{Zahl}$ \\
$\vdots$

allgemein: \\
\[ x \rightarrow
  \begin{cases}
    k & \text{falls } x = 2k+1 (\text{für } k = 0, 1, 2, ...)\\
    -k  & \text{falls } x = 2k (\text{für } k = 1, 2, 3, ...)\\
  \end{cases}
\]

\item $\mathbb{Q}$ ist abzählbar unendlich:

$$\frac{1}{1} \frac{1}{2} \frac{1}{3} \frac{1}{4} \frac{1}{5} ...$$

$$\frac{2}{1} \frac{2}{2} \frac{2}{3} \frac{2}{4} \frac{2}{5} ...$$

$$\frac{3}{1} \frac{3}{2} \frac{3}{3} \frac{3}{4} \frac{3}{5} ...$$

$$\vdots$$

Cantorsches Diagonalverfahren.

\item $\mathbb{R}$ ist \underline{nicht} abzählbar unendlich! \\
(Beweis von Cantor, 2. Diagonalisierungsargument)
$\rightarrow$ eventuell später

\item $P(\mathbb{N}$ ist nicht abzählbar unendlich (allgemein: $\mid A \mid < \mid P(A) \mid$ Satz von Cantor.)

\end{itemize}

\subsection{Satz (Wichtiger Satz für endliche Mengen)} %4.16
Seien $A, B \neq \emptyset$ endliche Mengen, $\mid A \mid = \mid B \mid$, und $f \colon A \rightarrow B$ eine Abbildung.

Dann gilt $f$ injektiv $\Leftrightarrow f$ surjektiv $\Leftrightarrow f$ bijektiv.

\underline{Beweis:}

Wir setzen $n: \mid A \mid = \mid B \mid$. Es genügt zu zeigen $f$ injektiv $\Leftrightarrow f$ surjektiv.

$\Rightarrow$ Sei $f$ injektiv, d.h. falls $a_1, a_2 \in A$ mit $a_1 \neq a_2$, dann gilt $f(a_1) \neq f(a_2)$.

D.h., verschiedene Elemente aus $A$ werden auf verschiedene Elemente aus $B$ abgebildet, die $n$ Elemente aus $A$ also auf $n$ verschiedene Elemente aus $B$. \\
Da $B$ genau $n$ Elemente besitzt, ist $f$ surjektiv. $(f(A) = B)$.

[formaler: d.h. $\mid f(A) \mid = \mid A \mid = \mid B \mid$. \\
Da $f(A) \subseteq B$ endlich, folgt $f(A) = B$. \hfill $\square$

\subsection{Das Prinzip der rekursiven Definition von Abbildungen} %4.17

Sei $B \neq \emptyset$ Menge, $n_0 \in \mathbb{N}$, \qquad $A = \{n \in \mathbb{N} \mid n \geq n_0\}$.

Man kann eine Funktion $f: A \rightarrow B$ definieren durch
\begin{itemize}
\item Angabe des Startwerts $f(n_0)$
\item Beschreibung, wie man für jedes $n \in A$ den Funktionswert f(n+1) aus $f(n)$ berechnet (\underline{Rekursionsschritt}).
\end{itemize}

\subsection{Beispiel} %4.18
\begin{description}

\item[a)] Die Fakultätsfunktion:
$f \colon \mathbb{N}_0 \rightarrow \mathbb{N}$ \\
mit $f(0) = 0\underbrace{!}_{\text{Fakultät}} = 1$ (Startwert)

$f(n+1) = (n+1)! = n! (n + 1)$ für alle $n \geq 0$

Also: \\
$f(1) = 1! = 0!  \cdot  1$ \\
$f(2) = 2! = 1!  \cdot 2 = 1  \cdot  2 = 2$ \\
$f(3) = 3! = 2! \cdot 3 = 1  \cdot  2  \cdot  3$ \\
$f(4) = 4! = 3! \cdot 4 = 1  \cdot  2  \cdot  3  \cdot  4$ \\
$\vdots$ \\
$f(70) = 70! \approx 1,2 \cdot 10^{100}$

\item[b)] Potenzen: für festes $x \in \mathbb{R}$ definiere \\
$x^0 =1$ \\
$x^{n+1} = x^n  \cdot  x$ für alle $n \geq 0$

$(Px : \mathbb{N}_0 \rightarrow \mathbb{R} \qquad n \rightarrow x^n)$

\item[c)] Eine Pflanze verdopple jeden Tag die Anzahl ihrer Knospen und produziere eine zusätzliche.

$f \colon \mathbb{N} \rightarrow \mathbb{N}$ beschreibe die Anzahl der Knospen nach $n$ Tagen.

$f(1) = 1$ \\
$f(2) = 2 \cdot 1 + 1 = 3$ \\
$f(3) = 2 \cdot 3 + 1 = 7$ \\
$f(4) = 2 \cdot 7+1 = 15$ \\
$\vdots$ \\
$f(n+1) = 2  \cdot  f(n) +1$

% ==============
% 30 November 2015
% ==============

Wieviele Knospen gibt es nach 100 Tagen? \\
$\Rightarrow$ Geschlossene / explizite Form von $f$ gefragt.

Vermutung: $f(n) = 2^n - 1$

(Bemerkung: bessere Methoden (statt vermuten / raten) in der Vorlesung \textit{Algorithmen}, dort z.B. auch mathematische Strukturen wie oben, diese werden \textit{Bäume} (Graphen) genannt.

Beweis: vollständige Induktion

\begin{itemize}
\item[Induktionsanfang:] \hfill \\
$f(1) = 2^1 -1 = 1$

\item[Induktionsschritt:] \hfill \\
\textbf{Induktionsvoraussetzung:} \\
sei $f(n) = 2^n - 1 \forall n \geq 1$

\textbf{Induktionsbehauptung:} \\
$f(n+1) = 2^{n+1} -1$

\textbf{Beweis:}

$f(n+1) \underbrace{=}_{Definition} 2 \cdot f(n) + 1$ \\
$\underbrace{=}_{Ind. vor.} 2 (2^n -1) +1$ \\
$= 2^{n+1} - 2 + 1$ \\
$= 2^{n+1} - 1$ \hfill $\square$

\end{itemize}

\end{description}

\subsection{Bemerkung} %4.19
Die rekursive Definition kann verallgemeinert werden: benutze zur Definition von $f(n+1)$ die vorigen $k(k \in \mathbb{N}$ Werte von $f$, also $\underbrace{f(n), f(n-1), ..., f(n-k+1)}_{\text{k Stück}}$

und gebe $k$ Startwerte $f(n_0), f(n_0 + 1), ..., f(n_0 + k - 1)$

\subsection{Beispiel (Fibonacci-Zahlen)} %4.20
$k = 2$

$f(1) = 1$ \\
$f(2) = 1$ \\
$f(n+1) = f(n) + f(n-1)$

$(f(3) = f(2) + f(1) = 1 + 1 = 2,$ \\
$f(4) = 2 + 1 = 3$, \\
$f(5) = 3 + 2 = 5$, \\
$f(6) = 8$, \\
$f(7) = 13...)$

explizite Form:
$$f(n) = \frac{1}{\sqrt{5}} (( \frac{1 + \sqrt{5}}{2})^n - (\frac{1- \sqrt{5}}{2})^n)$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Kapitel 5: Relationen
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Relationen} %5

\subsection{Definition} %5.1
Seien $M_1, ..., M_n$ \\
nicht leere Mengen \\
$(n \in \mathbb{N})$.

\begin{description}

\item[a)] \hfill \\
Eine \underline{n-stellige Relation} über $M_1, ..., M_n$ ist eine Teilmenge von $M_1 \times ... \times M_n$.
Ist $M_1 = ... = M_n = M$, d.h. $R \subseteq M^n$,
so spricht man von einer \underline{n-stelligen Relation auf M}.

\item[b)]  \hfill \\
(speziell: $n = 2$, zweistellige Relation auf $M$: \\
Sei $M \neq \emptyset$ Menge. Eine Teilmenge $R_{\sim} \subseteq M \times M$ heißt \underline{(zweistellige) Relation auf M}. Statt $(a, b) \in R_{\sim} $(mit $a, b \in M$) schreibt man kurz $a R_{\sim} b$ oder $a \sim b$ (\textit{a steht in Relation zu b})

\end{description}

\subsection{Beispiel} %5.2

\begin{description}
\item[a)] \hfill \\
Relationale Datenbanken ($\rightarrow$ Folie)

\item[b)] \hfill \\
$M = \{1, 2, 3 \} ,$ \\
$R_{\sim} = \{(1, 2), (1, 3), (2, 3) \}$ \\
also: $1 \sim 2, 1  \sim 3, 2  \sim 3$

Hierfür sind wir die Notation \textit{$<$} gewohnt: \\
$1 < 2, 1 < 3, 2 < 3$ (\textit{Kleiner-Relation})

Ähnlich: $\geq$ auf $M: R_{\geq} = \{(1, 1), (2, 1), (3, 1), (2, 2), (3, 2), (3, 3) \}$

allgemeiner: kleiner-Relation auf $\mathbb{Z}$: \\
$R_{<} \{(x, y) \mid x, y \in \mathbb{Z}, x < y \}$ \\
$R_{\leq} ... \leq$

\item[c)] \hfill \\
Teiler-Relation R, auf $\mathbb{Z}$: \\
$R_{|} = \{(x, y) \mid x, y \in \mathbb{Z}$ und $ \exists k \in \mathbb{Z}$ mit \\
$x \mid y$ (\textit{x teilt y})

z.B. $6|42, \quad 3|-27, \quad 7|0$

\item[d)] Sei $M$ die Menge aller Menschen, $R_m = \{(a, b) \mid a, b \in M$ und $a$ und $b$ haben dieselbe Mutter \}

\end{description}

Zwei wichtige Typen von Relationen auf einer Menge: \\
Ordnungsrelationen und Äquivalenzrelationen.

\subsection[Definition (Ordnungsrelation, partielle/totale/vollständige/lineare Ordnung)]{Definition} %5.3
Sei $M \neq \emptyset, R_{\preceq}$ (oder $\preceq$) eine Relation auf $M$ mit folgenden Eigenschaften:

\begin{enumerate}

\item $\forall x \in M: x \preceq x$ (Reflexivität)

\item $\forall x, y \in M: (x \preceq y \wedge y \preceq x) \Rightarrow x = y$ (Antisymmetrie)

\item $\forall x, y, z \in M: (x \preceq y \wedge y \preceq z) \Rightarrow x \preceq z$ (Transitivität)

\end{enumerate}

Dann heißt $\preceq$ \underline{Ordnungsrelation} oder \underline{(partielle) Ordnung} auf $M$.

Gilt zusätzlich:

\begin{enumerate}

\item[4.] $\forall x, y \in M: x \preceq y$ oder $y \preceq x$,
so heißt $\preceq$ eine \underline{totale} (oder \underline{vollständige}, oder \underline{lineare}) Ordnung.
\end{enumerate}

% ==============
% 02 Dezember 2015
% ==============

Ist $x \preceq y$ und $x \neq y$, so schreibt man $x \prec y$.

\subsection{Beispiele} %5.4

\begin{itemize}
\item[a)]
$R_\leq$ auf $\mathbb{Z}$ (Beispiel 5.2 b)) ist totale Ordnung auf $\mathbb{Z}$, ebenso auf $\mathbb{Q},\mathbb{R}$.

$R_<$ ist \underline{keine} partielle Ordnung; (1),(4) nicht erfüllt:
	
	\begin{itemize}
	\item[(1):] für kein $x \in \mathbb{Z}$ gilt $x < x$
	\item[(4):] für $x=y$ gilt weder $x<y$ noch $y<x$.
	\end{itemize}
	
\item[b)]
$R_|$ (5.2 c)) auf $\mathbb{N}$ ist partielle Ordnung, nicht total (zum Beispiel gilt für $3,4 \in \mathbb{N}$ weder $3|4$ noch $4|3$.).

$R_|$ auf $\mathbb{Z}$ ist \underline{keine} partielle Ordnung; nicht antisymmetrisch: \\
z.B. $-3|3$, $3|-3$, aber $3 \neq -3$

\item[c)] Teilmengenrelation ($\subseteq$) auf $\mathcal{P}(M)$ ist partieller Ordnung, für $\abs{M} > 1 $ nicht total (Übung).

\item[d)] Beispiel für Relation, die (1),(2) erfüllt, aber nicht (3):

$M=\{1,2,3\}$\\
$R = \{\underbrace{(1,1),(2,2),(3,3)}_{\text{$\rightarrow$ reflexiv}},(1,2), \textcolor{red}{*} \text{ } (2,3)\}$

\textcolor{red}{$*$} Achtung: $(2,1) \notin R$, sonst müsste $2=1$ gelten (wegen Antisymmetrie).

$(1,2) \in R, (2,3) \in R$, aber $(1,3) \notin R$

$\Rightarrow$ \underline{nicht} transitiv.

$(1,\overfence{2),(2},2) \qquad (1,2) \checkmark \qquad (1,\overfence{1),(1},2) \qquad (1,2)\checkmark$

\item[e)] Sei $\leq$ partielle Ordnung auf $M$, $n \in \mathbb{N}$.

Dann definiere die \underline{lexikographische Ordnung} $\leq_{lex}$ auf $M^n$ wie folgt:

$x = (x_1,...,x_n) \leq_{lex} y = (y_1,...,y_n) :\Leftrightarrow$ \\
$x = y$ oder $x_i < y_i$ für das kleinste $i$ mit $x_i \neq y_i$

(Übung: $\leq_{lex}$ ist partielle Ordnung)

(Falls $\leq$ totale Ordnung auf M ist, dann $\leq_{lex}$ totale Ordnung auf $M^n$, vgl. Wörterbuch)

Beispiel: $M=\{a,b,c\} \quad a < b < c$ \\
dann ist z.B. auf $M^4$

$(a,a,a,a) \leq_{lex} (a,a,a,b) \leq_{lex} ... \leq_{lex} (a,b,a,c) \leq_{lex} ... \leq_{lex} (a,b,b,a) \leq_{lex} ... \leq_{lex} (c,c,c,c)$
	
\end{itemize}

\textbf{Äquivalenzrelationen:}

2 Elemente äquivalent, falls sie sich bezüglich einer Eigenschaft gleichen/ähnlich sind, z.b. Farbe, gleiche Übungsgruppe, gleicher Rest bei Division durch 3, ...

\subsection[Definition (Äquivalenzrelation)]{Definition} %5.5

Eine Relation $\sim$ auf einer Menge $M \neq \emptyset$ heißt \underline{Äquivalenzrelation} falls gilt:

\begin{itemize}
\item[(1)] \textbf{Reflexivität:} $x \sim x$ für alle $x \in M$.
\item[(2)] \textbf{Symmetrie:} $\forall x,y \in M : x \sim y \Rightarrow y \sim x$
\item[(3)] \textbf{Transitivität:} Für alle $x, y, z \in M$ gilt: falls $x \sim y$ und $y \sim z$, dann ist auch $x \sim z$. % TODO Umformen wie (2)?
\end{itemize}

\subsection{Beispiele} %5.6

\begin{itemize}
\item[a)] $<$-Relation (Beispiel \textit{5.2 b)}) ist keine Äquivalenzrelation (nicht reflexiv, nicht symmetrisch, transitiv).

$\geq$ keine Äquivalenzrelation (reflexiv, nicht symmetrisch, transitiv)

\item[b)] $M \neq \emptyset$ beliebig, $a \sim b :\Leftrightarrow a = b$

Gleichheit ist eine Äquivalenzrelation

($= \quad := \{(a,a) \mid a \in M\}$)

\item[c)] $R_m$ (Mutter-Relation) aus Beispiel 5.2 d) ist Äquivalenzrelation

% ==============
% 07 Dezember 2015
% ==============

\item[d)] $M = \mathbb{Z}, a \sim b: \Leftrightarrow b - a$ ist gerade, \\
d.h. $\exists k \in \mathbb{Z}$ mit $b-a = 2 \cdot k$.

$\sim$ ist Äquivalenzrelation:
\begin{itemize}
\item reflexiv: Sei $a \in M$, dann gilt $a \sim a$, \\
denn $a-a = 0 = 2 \cdot 0$

\item symmetrisch: Sei $a \sim b$ \\
$\Rightarrow b-a = 2 \cdot k$ für ein $k \in \mathbb{Z}$ \\
$\Rightarrow a-b = -2 \cdot k = 2 \cdot  \underbrace{(-k)}_{\in \mathbb{Z}}$ \\
$\Rightarrow b \sim a$

\item transitiv: seien $a \sim b, b \sim c \Rightarrow \exists k, l \in \mathbb{Z}$: \\
$b-a = 2 \cdot k, \quad c-b = 2 \cdot l$ \\
$\Rightarrow c-a = (c-b) + (b-a) = 2l + 2k = 2 \cdot (\underbrace{l+k}_{\in \mathbb{Z}})$ \\
$\Rightarrow a \sim c$

\end{itemize}

\item[e)] analog: wähle $r \in \mathbb{N}$ fest, $M = \mathbb{Z}$ \\
$a \sim b: \Leftrightarrow b - a$ ist durch $r$ teilbar (d.h. $\exists k \in \mathbb{Z}$ mit $b-a = r \cdot k)$

$\sim$ ist Äquivalenzrelation.

\end{itemize}

\subsection[Definition (Äquivalenzklassen)]{Definition} %5.7
Sei $\sim$ eine Äquivalenzrelation auf $M \neq \emptyset$.

Dann heißt für $x \in M$ die Menge \\
$[x] := \{y \in M \mid y \sim x \}$ die \underline{Äquivalenzklasse von $x$ (bzgl. $\sim$) auf $M$}.

\subsection{Beispiel} %5.8

\begin{itemize}
\item[a)] Gleichheit liefert triviale, nämlich einelementige Äquivalenzen:

$[x] = \{x\} \forall x \in M$

\item[b)] vgl. Beispiel 5.6d), $M = \mathbb{Z}, a \sim b \Leftrightarrow b-a$ gerade \\
$[0] = \{b \in \mathbb{Z} \mid b-0$ gerade $\} = $ Menge der geraden Zahlen

\qquad $= [2] = [4] = [-2] = ...$

$[1] = \{b \in \mathbb{Z} \mid b-1$ gerade $\} = $ Menge der ungeraden Zahlen

\qquad $= [3] = [5] = [-1] = ...$

Es gilt: $[0] \cup [1] = \mathbb{Z}$, und $[0] \cap [1] = \emptyset$ \\
(\textit{disjunkte Vereinigung}, Zerlegung von $\mathbb{Z}$, siehe folgende Definition.)
\end{itemize}

\subsection[Definition (paarweise disjunkte Mengen, disjunkte Vereinigung, Zerlegung/Partition)]{Definition} %5.9
Sei $M \neq \emptyset, Z \subseteq \mathcal{P}(M)$ eine Menge von Teilmengen von $M$.

Die Elemente von $Z$ seien \underline{paarweise disjunkt} , d.h. $\forall A, B \in Z$ mit $A \neq B$ gilt $A \cap B = \emptyset$.

$(Beispiel: M := \{1, 2, 3, 4, 5\}$, \\
$Z' := \{\{1\}, \{1, 2\}, \{3, 4\}\}$ \\
$Z := \{\{1\}, \{2, 3\}, \{4, 5\}\}$ \\

Elemente von $Z'$ nicht paarweise disjunkt, aber Elemente von $Z$ paarweise disjunkt.)

Dann heißt die Vereinigung $\displaystyle\bigcup_{A \in Z} A$ auch \underline{disjunkte Vereinigung},
Notation: $\displaystyle\bigcup_{A \in Z} A$ (oder $\displaystyle\biguplus_{A \in Z} A)$.

Gilt zusätzlich $\displaystyle\bigcup_{A \in Z} A = M$, so heißt $Z$ \underline{Zerlegung} oder \underline{Partition} von $M$.

\subsection{Satz (Klasseneinteilung, Zerlegung durch Äquivalenzklassen)} %5.10
Sei $\sim$ Äquivalenzrelation auf $M \neq \emptyset$. Dann gilt:

\begin{itemize}
\item [(1)] für jedes $x \in M$ ist $[x] \neq \emptyset$
\item [(2)] $\displaystyle\bigcup_{x \in M} [x] = M$
\item [(3)] $\forall x, y \in M$ gilt entweder $[x] = [y]$ oder $[x] \cap [y] = \emptyset$
\end{itemize}

In Worten: Über $\sim$ wird M zerlegt in nicht leere, paarweise disjunkte Mengen (die Äquivalenzklassen).

\underline{Beweis:}

(1) $x \sim x \quad \forall x \in M$ (Reflexivität) \\
$\Rightarrow x \in [x]$

(2) zeige $=$, also $\subseteq, \supseteq$:

$\subseteq \displaystyle\bigcup_{x \in M} [x]_{\subseteq M} \subseteq M$ (nach Definition).

$\supseteq M = \displaystyle\bigcup_{x \in M} \{x\} \underbrace{\subseteq}_{(1)} \displaystyle\bigcup_{x \in M} [x],$ \\
also $M \subseteq \displaystyle\bigcup_{x \in M} [x]$.

(3) wir zeigen: $[x] \cap [y] \neq \emptyset \Rightarrow [x] = [y]$

Sei dazu $z \in [x] \cap [y]$ (denn Schnitt $\neq \emptyset$) \\
$\Rightarrow z \sim x$ und $z \sim y$ (*) \\
$\Rightarrow x \sim z$ und $y \sim z$ (**) \\
wir zeigen: [x] = [y]

\begin{itemize}
\item $[x] \subseteq [y]$: sei $u \in [x]$ \\
$\Rightarrow u \sim x$ \\
$\Rightarrow u \sim z$ \\
Transitivität, $x \sim z$ (**) \\
$\Rightarrow u \sim y$ \\
Transitivität, $z \sim y$ (*)

$\Rightarrow u \in [y]$.

\item $[x] \supseteq [y]$: sei $u \in [y]$ \\
$\Rightarrow u \sim y$ \\
$\Rightarrow u \sim z$ \\
(Transitivität, $y \sim z$ (**))

$\Rightarrow u \sim x$ \\
Transitivität, $z \sim x$ (*) \\
$\Rightarrow u \in [x]$ \\
Also insgesamt $[x] = [y]$. \hfill $\square$

\end{itemize}

% ==============
% 09 Dezember 2015
% ==============

Eine Äquivalzenzrelation auf einer Menge $M$ liefert also eine Zerlegung von $M$. Es gilt auch die Umkehrung.

\subsection[Satz zu Äquivalenzrelationen]{Satz} %5.11

Sei $M \neq \emptyset$ eine Menge, $Z$ eine Zerlegung von $M$, $M= \displaystyle\bigcup_{A \in Z} A$.

Definiere für $x,y \in M$:

$x \sim y :\Leftrightarrow x$ und $y$ liegen in derselben Menge $A \in Z$.

Dann ist $\sim$ eine Äquivalenzrelation auf $M$, und die Äquivalenzklassen bezüglich $\sim$ sind genau die Mengen $A \in Z$.

% TODO Figure (Set M with disjunct subsets)

\underline{Beweis:} 
\begin{itemize}
\item $\sim$ ist reflexiv:

Sei $x \in M = \displaystyle\bigcup_{A \in Z} A$

$\Rightarrow x \in A$ für ein $A \in Z$

$\Rightarrow x \sim x$

\item $\sim$ ist symmetrisch:

Sei $x \sim y$, d.h. $x,y \in A$ für ein $A \in Z$.

$\Rightarrow y \sim x$

\item $\sim$ ist transitiv:

Seien $x \sim y, y \sim x$, d.h. $x,y \in A$ und $y,z \in B$ für passende $A,B \in Z$

$y \in A \cap B \Rightarrow A = B$ (Zerlegung ist \underline{disjunkte} Vereinigung)

$\Rightarrow x,z \in A$

$\Rightarrow x \sim z$

\item Äquivalenzklassen: folgt aus Definition von $\sim$. \hfill $\square$
\end{itemize}

\subsection[Definition (Repräsentantensystem)]{Definition} %5.12

Sei $\sim$ eine Äquivalenzrelation auf $M$.

Eine Teilmenge von $M$, die aus jeder Äquivalenzklasse bezüglich $\sim$ \underline{genau ein} Element (einen sogenannten Repräsentanten) enthält, nennt man ein \underline{Repräsentantensystem von $\sim$}.

\subsection{Beispiel} %5.13

Beispiel 5.6 d / 5.8 b:

$a \sim b \Leftrightarrow b-a$ gerade.

Äquivalenzklassen waren $[0],[1]$

Repräsentantensysteme sind zum Beispiel $\{0,1\}$ oder $\{2,9\}$ oder $\{-42,3\}$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Kapitel 6: Elementare Zahlentheorie
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Elementare Zahlentheorie} %6

\subsection[Definition (Teiler und Vielfaches)]{Definition} %6.1

Seien $a,b \in \mathbb{Z}, b \neq 0$.

$b$ heißt \underline{Teiler von $a$} ($b$ teilt $a$, $b \mid a$), falls $q \in \mathbb{Z}$ existiert mit $a = q \cdot b$.

(d.h. $\frac{a}{b}= q \in \mathbb{Z}$)

$a$ heißt dann \underline{Vielfaches} von $b$.

($b \nmid a$ bedeutet: $b$ ist kein Teiler von $a$)

(Beispiel: $6 \mid 42 \;, \quad -5 \mid 10 \;, \quad 5 \nmid 42 \;, \quad 1 \mid -1 \;, \quad 1 \mid 0 \;, \quad 0$ ist nie Teiler einer Zahl.)

\subsection[Satz (Betrag, Eigenschaften von Teiler und Vielfachem)]{Satz} %6.2

Seien $a,b,c,d \in \mathbb{Z}$

\begin{itemize}

\item[a)] Ist $b \mid a$, dann auch $\abs{b} \mid a$, $b \mid \abs{a}$ und $\abs{b} \mid \abs{a}$.

($\abs{b}$ bezeichnet den Betrag von $b$,

$\abs{b} = \begin{cases}
b & \text{, falls } b \geq 0 \\
-b & \text{, falls }  b < 0
\end{cases} )$

\item[b)] Falls $b \mid c$ und $b \mid d$, dann $b \mid k \cdot c + l \cdot d \qquad \forall k,l \in \mathbb{Z}$

\item[c)] Ist $b \mid a$ und $a \neq 0$, dann $\abs{b} \leq \abs{a}$

\item[d)] Ist $b \mid a$ und $a \mid b$, dann $a = \pm b$

\end{itemize}

\underline{Beweis:}

\begin{itemize}

\item[a)] Sei $b \mid a$.

	\begin{itemize}
	\item Ist $b > 0$, so ist $\abs{b} = b$, also gilt $\abs{b} \mid a$.
	
	\item Ist $b < 0$, so ist $\abs{b} = -b$ \\
		$b \mid a$, d.h. $\exists q \in \mathbb{Z}$ mit $a = q \cdot b = (-q) \cdot (-b) = (-q) \cdot \abs{b}$.
		
		$(-q) \in \mathbb{Z}$, also gilt $\abs{b} \mid a$.

	\end{itemize}
	
	Restliche Behauptung analog!
	
\item[b)] $b \mid c$, d.h. $\exists q \in \mathbb{Z}$ mit $c = q \cdot b$

$\Rightarrow k \cdot c = k \cdot q \cdot b \hfill \forall k \in \mathbb{Z}$

$b \mid d$, d.h. $\exists m \in \mathbb{Z}$ mit $d = m \cdot b$

$\Rightarrow \underline{l \cdot d = l \cdot m \cdot b} \hfill \forall l \in \mathbb{Z}$.

$\Rightarrow \uline{k\cdot c} + \uwave{l \cdot d} = \uline{k \cdot q \cdot b} + \uwave{l \cdot m \cdot b} = \underbrace{(k \cdot q + l \cdot m)}_{\in \mathbb{Z}} \cdot b \hfill \forall k,l \in \mathbb{Z}$

$\Rightarrow b \mid k \cdot c + l \cdot d \hfill \forall k,l \in \mathbb{Z}$

\item[c)] $b \mid a \;$, nach Teil a) also $\abs{b} \mid \abs{a}$

$\Rightarrow \abs{a} = \underbrace{q}_{\mathllap{\in \mathbb{N} \text{, da } \abs{a},\abs{b} \geq 0 \text{ und } a \neq 0}} \cdot \abs{b} = \underbrace{\abs{b} + \abs{b} + ... + \abs{b}}_{q \text{ Summanden}} \geq \abs{b}$

\item[d)] Da $b \mid a$ und $a \mid b$, sind $a,b \neq 0$

Nach c): $\ \abs{b} \leq \abs{a}$ und $\abs{a} \leq \abs{b} \Rightarrow \abs{a} = \abs{b}$, d.h. $a = \pm b$. \hfill $\square$

\end{itemize}

Teilbarkeit in $\mathbb{Z}$ ist im Allgemeinen nicht erfüllt. Daher ist Teilen mit Rest wichtig.

\subsection{Satz und Definition: Division mit Rest} %6.3

Seien $a,b \in \mathbb{Z}, b \neq 0$.

Dann existieren \uline{eindeutig bestimmte} $q,r \in \mathbb{Z}$ mit

$\begin{rcases}
(1) & a = q \cdot b + r \\
(2) & 0 \leq r < \abs{b}
\end{rcases}$ Division mit Rest

% ==============
% 14 Dezember 2015
% ==============

$q$ wird \underline{Quotient} genannt, $r$ \underline{Rest}.

Bezeichnung: $q = a$ div $b$ \\
$r = a \bmod b$ (\textit{modulo})

Es gilt also $\underbrace{a \text{ mod } b}_{Rest} = 0 \Leftrightarrow b \mid a$

\subsection{Beispiel} %6.4

\begin{itemize}

\item $a = 22, b = 5, 22 = 4 \cdot 5 +2$ \\
$22$ div $5 = 4, 22 \bmod 5 = 2$

\item $a = 22, b = -5, 22 = -4 \cdot (-5) + 2$ \\
$22$ div $(-5) = -4, 22 \bmod (-5) = 2$

\item $a = -22, b = 5, -22 = -5 \cdot 5+3$ \\
(\attention ($0 \leq r < 5$)!) \\
$-22$ div $5 = -5, -22 \bmod 5 = 3$

\item $a = -22, b = -5, -22 = 5 \cdot (-5) + 3$ \\
$-22$ div $(-5) = 5, -22 \bmod (-5) = 3$

\end{itemize}

\underline{Beweis von 6.3:}

\begin{itemize}

\item Existenz von $q$ und $r$ mit $(1), (2)$:

\underline{1. Fall}: $b > 0$ \\
Sei $q$ die größte ganze Zahl mit $q \leq \frac{a}{b}$ \\
$(q = \floor{\frac{a}{b}})$

Dann ist $b \cdot q \leq a$ \\
(da $b > 0$ !)

Setze $r:= a - b \cdot q$ \\
es gilt also $r \geq 0$ \\
$\Rightarrow a = q \cdot b +r$ ((1) gilt) %TODO 1 Fall bis hierher in blauen Kasten oder so *

Zu zeigen bleibt noch: $r < |b| = b$ \\
Widerspruchsbeweis: \\
angenommen, $r \geq b$. Dann ist \\
$r = b+s$ für ein $s \geq 0$,
d.h. $a = q \cdot b + (\underbrace{b+s}_{r})$ \\
$b(q+1)+s = a$ \\
$\Rightarrow q +1 + \underbrace{\frac{s}{b}}_{\geq 0} = \frac{a}{b}$ \\
$\Rightarrow q + 1 \leq \frac{a}{b}$ zur Wahl von $q \quad$ \Lightning

Also gilt $0 \leq r < b$

\underline{2. Fall}: $b < 0$ \\
Es gilt (*) mit $|b|$, \\ %TODO Prüfen was (*) bedeutet, genauer erklären (roter Stern? siehe weiter unten)
also gilt $a = q  \cdot  |b| + r, \underbrace{0 \leq r < |b|}_{\text{schon ok}}$ \\
für $b < 0$: \\
$a = q \cdot (-b) + r$ \\
$= (-q)  \cdot  b + r$

\item $q, r$ sind eindeutig bestimmt:

angenommen, $\exists q_1, q_2, r_1, r_2 \in \mathbb{Z}$, so dass \\
$a = \underline{q_1 \cdot  b + r_1 = q_2 \cdot b+r_2}$ \\
$0 \leq r_1, r_2 < |b|$.

Sei o.B.d.A (ohne Beschränkung der Allgemeinheit) $r_2 \geq r_1$

Dann ist $(q_1 - q_2)  \cdot  b = r_2 - r_1 \geq 0$, \\ % Roter Stern Formel
also $b \mid (r_2-r_1)$

wir zeigen $(r_2-r_1 = 0)$ durch Widerspruch:

angenommen, $r_2-r_1 \neq 0$. \\
$b \mid (r_2-r_1), (r_2-r_1 \neq 0)$ \\
$\underbrace{\Rightarrow}_{6.2.c)} |b| \leq \abs{r_2 - r_1} = r_2 - r_1  < r_2 < |b|$ \\
Also gilt $r_1 = r_2$. \\
Wegen (*), da $b \neq 0, q_1=q_2$. %TODO Prüfen was (*) bedeutet, genauer erklären
%Roter Stern

\end{itemize}

\subsection[Definition (Gaußklammer / Ab- und Aufrundungsfunktion)]{Definition} %6.5
Sei $x \in \mathbb{R}$. \\
$\ceil{x} = $ kleinste ganze Zahl z mit $z \geq x$
(\textit{ceiling}-Funktion, aufrunden) \\
$\floor{x} = $ größte ganze Zahl $z$ mit $z \leq x$ 
(\textit{floor}-Funktion, abrunden)

\subsection{Beispiel} %6.6
$\ceil{3} = 3, \ceil{\frac{4}{3}} = 2,  \floor{\frac{4}{3}} = 1, \ceil{-\frac{4}{3}} = -1, \floor {-\frac{4}{3}} = -2$

Anwendung: Stellenwertsysteme zur Basis $b\ (b \in \mathbb{N}, b > 1)$

$b = 2$: Binärsystem \\
$b = 8$: Oktalsystem \\
$b = 10$: Dezimalsystem \\
$b = 16$: Hexadezimalsystem

\subsection{Satz (b-adische Darstellung)} %6.7

Sei $b \in \mathbb{N}, b > 1$.
Jede natürliche Zahl $n \in \mathbb{N}_0$, lässt sich \underline{eindeutig} darstellen in der Form: \\
$n = \displaystyle\sum_{i=0}^{k} x_j  \cdot  b^i$,
wobei für $k$ und $x_i$ gilt:

(1) $k = 0$ für $n = 0$ \\
$b^k \leq n < b^{k+1}$ für $n > 0$

(2) $x_i \in \mathbb{N}_0, 0 \leq x_j \leq b -1$,
$x_k \neq 0$ für $n \neq 0$.

(Die $x_i$ heißen \underline{Ziffern} von n bzgl. b. \\
Schreibweise: $n= (x_k ... x_0)_b$

oder, falls $b$ klar (z.B. $b = 10$) \\
$n = x_k...x_0$

\subsection{Beispiel} %6.8
$b = 2$ (Binärsystem)

$6 = 1 \cdot \underbrace{2^2}_{b^2} + 1 \cdot \underbrace{2^1}_{b^1} + 0 \cdot \underbrace{2^0}_{b^0}$ $(k = 2)$ \\
$(6)_{10} = (110)_2$

$9 = 1 \cdot 2^3 + 0 \cdot 2^2  \cdot  0 \cdot 2^1 + 1 \cdot 2^0$
$(9)_{10} = (1001)_2$

$0 = (0)_2$ \\
$1 = (1)_2$ \\
$2 = (10)_2$ \\
$3 = (11)_2$ \\
$4 = (100)_2$ \\
$5 = (101)_2$ \\
$\vdots$

Ziffern für $b=16$:
$0, 1, ...9, A, B, C, D, E, F$

$(11)_{10} = (B)_{16}$

\underline{Beweis (6.7):}

verschärfte Induktion nach $n$: \\
Induktionsanfang: $n = 0$ (hat Darstellung $(0)_b$)

Induktionsschritt: sei $n > 0$.
\begin{itemize}

\item Induktionsvorraussetzung: Die Aussage gelte für alle $n' \in \mathbb{N}_0$ mit $n' < n$,

\item Induktionsbehauptung: Die Aussage gilt für $n$.

% ==============
% 16 Dezember 2015
% ==============

\item Beweis:

Nach Satz über Division mit Rest (6.3) gilt \\
$\exists q, r \in \mathbb{Z}$ mit $n = q \cdot b + r$ \\
Setze $x_0 = r$ \\
(also $x_0 = n \bmod b$ und $n' = q$ und $n' = \frac{n-x_0}{b}$), \\
dann ist $0 \leq n' < n$

Nach Induktionsvorraussetzung gilt also $n' = \displaystyle\sum_{i=0}^k x'_i  \cdot  b^i, k, x'_i$ mit $(1), (2)$ \\
setze $x_{i+1} = x'_i$ für $i = 0, 1, ..., k$

Dann ist $n = n' \cdot b + x_0$ \\
$=\displaystyle\sum_{i=0}^{k} x'_i \cdot b^{i+1} + x_0$ \\
$=\displaystyle\sum_{i=1}^{k+1} x_i  \cdot  b^i + x_0$ \\
$=\displaystyle\sum_{i=0}^{k+1} x'i  \cdot  b^i$

-(1) und (2) gelten:

(2) gilt nach Konstruktoren der $x_i$ \/
(1):

-falls $n' = 0, [z.z: b^0 \leq n < b^1$] \\
dann ist $n = x_0$. \\
wegen $x_0 < b$ ist $b^0 = 1 \leq n < b^1$

- falls $n'>0$ [z.Z: $b^{k+1} \leq n < b^{k+2}]$ \\
dann gilt (Ind.Vor.) $b^k \leq n' < b^{k+1}$

$\Rightarrow b^{k+1} \leq b \cdot n' \leq \underbrace{b \cdot n' + x_0}_{n}$

zeige II: Es ist $n' \leq b^{k+1} - 1$, also \\
$b n' \leq b^{k+2} - b$

$\Rightarrow \underbrace{b n' + x_0}_{n} \leq b^{k+2} - b + x_0 < b^{k+2}$

- Darstellung ist eindeutig: \\
Sei $n = \displaystyle\sum_{i=0}^{k} x_i \cdot  b^i = \displaystyle\sum_{i=0}^{l} y_i  \cdot  b^i$ \\
$(x_i, y_i, k, l$ mit $(1), (2)$

Dann ist $x_0 = n \bmod b = y_0$ \\
wende Ind.Vor. an auf $n' = \frac{n-x_0}{b} = \frac{n-y_0}{b}$, Beh. folgt. \hfill $\square$

\end{itemize}

\subsection{Korollar}  %6.9

Der Beweis liefert ein Verfahren zur Bestimmung der Darstellung von $n \in \mathbb{N}_0$ zur Basis $b > 1$:

$n_0 := n, \quad x_0 := n_0 \bmod b$ \\
$n_1 := \frac{n_0-x_0}{b}, \quad x_1 := n_1 \bmod b$ \\
$\text{\quad}\ \ \vdots$ \\
$n_k := \frac{n_{k-1}-x_{k-1}}{b}, \quad x_k := n_k \bmod b$

solange, bis $n_k < b$ (d.h. $x_k=n_k$)

Dann $n = (n_k n_{k-1} \ ... \ n_0)_b$

\subsection{Beispiel} %6.10

\begin{itemize}
\item[a)] $(41)_{10}$ im Binärsystem ($b=2$) (mit Algorithmus aus 6.9)

$41 \bmod 2 = \textcolor{orange}{1}$ \\
$\frac{41-\textcolor{orange}{1}}{2} = 20, \quad 20 \bmod 2 = \textcolor{brown}{0}$ \hfill $|\,\;\,\;\,\;\,\;\,\;01$ \\
$\frac{20-\textcolor{brown}{0}}{2}=10, \quad 10 \bmod 2 = \textcolor{blue}{0}$ \hfill $|\,\;\,\;\,\;\,\;001$ \\
$\frac{10-\textcolor{blue}{0}}{2}=5, \quad 5 \bmod 2 = \textcolor{red}{1}$ \hfill $|\,\;\,\;\,\;1001$ \\
$\frac{5-\textcolor{red}{1}}{2}=2, \quad 2 \bmod 2 = \textcolor{green}{0}$ \hfill $|\,\;\,\;01001$ \\
$\frac{2-\textcolor{green}{0}}{1}=1 < b (=2)$, fertig. \hfill $|\,\;101001$ \\
also $(41)_{10} = (101001)_2$

oder (gut bei kleinen Zahlen):

höchste 2er-Potenz $\leq 41$ ist $\uline{2}^5=32$ \\
$41-32 = 9$ \\
höchste 2er-Potenz $\leq 9$ ist $\uline{2^3=8}$ \\
$9-8 = \uline{1 = 2^0}$ \\
$(41)_{10} = 2^5+2^3+2^0 = (101001)_2$

\item[b)] $(41)_{10}$ im Hexadezimalsystem:

$41 \bmod 16 = 9$ \hfill $|\,\;\,\;9$ \\
$\frac{41-9}{16} = 2 < 16$, fertig \hfill $|\,\;29$ \\

$(41)_{10} = (29)_{16}$ \\
$[$ oder: $(41)_{10} = (\underbracket[0.75pt]{10}\ \underbracket[0.75pt]{1001})_2 \\
\text{\qquad \qquad \quad} = (\underbracket[0.75pt]{0010}\ \underbracket[0.75pt]{1001})_2 = (29)_{16}\ \\ \\
\text{\qquad \qquad \qquad} (0010)_2 = (2)_{10} = (2)_{16} \\
\text{\qquad \qquad \qquad} (1001)_2 = (9)_{10} = (9)_{16} \ ]$

\item[c)] $(41)_5$ im 3er-System: 

$(41)_5 = 4 \cdot 5^1 + 1 \cdot 5^0 = (21)_{10}$

$21 \bmod 3 = 0$ \hfill $|\,\;\,\;\,\;0$ \\
$\frac{21-0}{3}=7, \quad 7 \bmod 3 = 1$ \hfill $|\,\;\,\;10$ \\
$\frac{7-1}{3}=2 < 3$, fertig \hfill $|\,\;210$ \\
$(41)_5 = (210)_3$

\end{itemize}

% ==============
% 11 Januar 2016
% ==============

\subsection{Satz (Rechenregeln für modulo)} %6.11
Seien $a, b \in \mathbb{Z}, m \in \mathbb{N}$

\begin{itemize}

\item $(a \bmod m) \bmod m = a \bmod m$

$M(M(a)) = M(a)$

\item Platzhalter $*:\ +,-,\cdot$
\begin{align*}
\text{Dann } (a * b) \bmod m  &\overset{(i)}{=}  [(a \bmod m) * (b \bmod m)] \bmod m \\
 &\overset{(ii)}{=}  [(a * (b \bmod m)] \bmod m \\
 &\overset{(iii)}{=}  [(a \bmod m) * b] \bmod m
\end{align*}

\end{itemize}

\underline{Beweis}

\begin{itemize}

\item[a)] $a = q  \cdot  m + \underbrace{r}_{a \bmod m}$
$ r = 0  \cdot  m + \underbrace{r}_{r \bmod m}$

\item[b)]

\begin{itemize}

\item[(i)]

\begin{itemize}
\item[$\bullet$] für $+$

$a = q_1  \cdot  m + r_1$ \\
$b = q_2  \cdot  m + r_2$ \\
$r_1 = a \bmod m$ \\
$r_2 = b \bmod m$

Wir haben \\
(1) $a + b = (q_1 + q_2) \cdot m + r_1 + r_2$ \\
(2) $r_1 + r_2 = q \cdot m + s$

(1, 2) (3) $a + b = (q_1 + q_2 + q) \cdot m + s$

also $(a + b) \bmod m = s = (r_1 + r_2) \bmod m$

\item[$\bullet$] für $* \cong -$ analog
\item[$\bullet$] für $* \cong \cdot$

$a \cdot b = (q_1  \cdot  q_2  \cdot  m + r_1  \cdot  q_1 + r_2  \cdot  q_2)  \cdot  m + r_1  \cdot  r_2.$

$\Rightarrow (a \cdot b) \bmod m = [r_1  \cdot  r_2] \bmod m$ \\
$= [(a \bmod m)  \cdot  (b \bmod m)] $\\
 = 6.11 a) \\
$ [(a  \cdot  b) \bmod m] \bmod m$

\end{itemize}

\item [(ii)] $[a * (b \bmod m)] m \bmod m \underbrace{=}_{so} [a \bmod m( * (b \bmod m) \bmod m) \bmod m] \bmod m$

 $\underbrace{=}_{6.11a)} [(a \bmod m) * (b \bmod m)] \bmod m$ \\

\item[(iii)] analog \hfill $\square$

\end{itemize}
\end{itemize}

 \subsection{Bemerkung} %6.12
 6.11 gilt auch für mehr als 2 Summanden / Faktoren.

 z.B. $(a \cdot b \cdot c) \bmod m$
 $= [(a \bmod m) b \cdot (c \bmod m)] \bmod m$

 6.11 wiederholt anwenden

 \subsection{Beispiele} %6.13
 \begin{itemize}

 \item $a = 10, b = 7, m = 4$ \\
 $ a \bmod m = 2, b \bmod m = 3$ \\

\begin{itemize}
\item[($+$)] $ [(a \bmod m) + (b \bmod m)] \bmod m = (2+3) \bmod 4 = 1$ \\
$(a + b) \bmod m = 17 \bmod 4 = 1$

\item[($-$)] $[(a \bmod m) - (b \bmod m)] \bmod m = (2 - 3) \bmod 4 = 3$ \\
$(a - b) \bmod m = (10-7) \bmod 4 = 3$

\item[($\cdot$)] $[(a \bmod m) \cdot (b \bmod m)] \bmod m = (2 \cdot 3) \bmod 4 = 2$ \\
$(a \cdot b) \bmod m = 70 \bmod 4 = 2$
\end{itemize}

Beobachtung: mod-Regeln können große Zwischenergebnisse vermeiden

 \item $(11 \cdot 12 \cdot 13) \bmod 7$ ? \\
 $\begin{aligned}
 (11 \cdot 12 \cdot 13) \bmod 7 &= 11 \cdot 12 \cdot 13) \bmod 7 = (1716) \bmod 7 = 1 \\
 \text{oder } (11 \cdot 12 \cdot 13) \bmod 7 &= [(11 \bmod 7)(12 \bmod 7) (13 \bmod 7)] \bmod 7 \\
 &= (4 \cdot 5 \cdot 6) \bmod 7 \\
 &= 120 \bmod 7 = 1 \\
 \text{oder } (11 \cdot 12 \cdot 13) \bmod 7 &= [((-3) \bmod 7) \cdot ((-2) \bmod 7) \cdot ((-1) \bmod 7)] \bmod 7 \\
 &= ((-3) \dot (-2) \cdot (-1)) \bmod 7 \\
 &= (-6) \bmod 7 = 1
 \end{aligned}$

 \item Welchen Rest lässt $(214936)^{1517433}$ bei Division durch 7?
 \begin{align*}
  [(214936)^{1517433}] \bmod 7 &=  \left[ \left(
  \begin{array}{r}
  210000\\
  + 4900 \\
  + 35 \\
  + 1 
  \end{array}\right) \bmod 7 \right]^{1517433} \bmod 7 \\
 							 &= (1 \bmod 7)^{1517433} \bmod 7 = 1
 \end{align*}

 \begin{itemize}
 \item Welchen Rest lässt $(214935)^{1517433} \bmod 7$ \\
 $\rightarrow$ Rest 0.

 \item Welchen Rest lässt $(214934)^{1517433} \bmod 7$ \\
 $(214935-1)^{1517433} \bmod 7$ \\
 $=(-1)^{1517433} \bmod 7 = (-1) \bmod 7 = 6$

 \item $\begin{aligned}[t]
(214937)^{1517433} \bmod 7 &=(2^{3 \cdot 505811}) \bmod 7 \\
						   &= ((2^3)^{505811}) \bmod 7 \\
						   &=(8^{505811}) \bmod 7  \\
						   &= 1^{505811} \bmod 7 = 1
\end{aligned}$

\end{itemize}

 \item Teilbarkeit und Quersummen

 \textbf{Satz:} Sei $ a \in \mathbb{N}, n \geq 1, t \in \mathbb{N}, t \mid n$ \\
$a = \displaystyle\sum^{k}_{i = 0} a (n+1)^i \qquad (n+1)$ - adische Darstellung \\

$8 = 0 \cdot 2^0 + 0 \cdot 2^1 + 0 \cdot 2^2  + 1 \cdot 2^3 = (1000)_2$ \\

Quersumme \\
$Q_{n+1} (a) \displaystyle\sum^{k}_{i=0} a_i$

Es gilt $t \mid a \Leftrightarrow t \mid Q(a)$

3-Regel. 123 durch 3 teilbar \\
9-Regel 51111 durch 9 teilbar.

\item ISBN-10 (veraltet) %e change itemize
Internationale Standard-Buch-Nr \\
9 Kennziffern, 10. Stelle (Prüfziffer) \\
$a_1 - a_2 a_3 a_4 - a_5 a_6 a_7 a_8 a_9 - a_{10}$ \\

$a_{10}\ = (\displaystyle\sum^{9}_{i=0} a_i  \cdot  i) \bmod 11 \qquad a_{10} = 10, \rightarrow a_{10} = x$

WHK: \\
$3-540-20521-7$ \\
$3-540-20522-5$ \\
$1-540-20523-1$

\end{itemize}

\subsection{Definition (Kongruenzrelationen modulo m)} %6.14
Sei $m \in \mathbb{N}$. Für $a, b \in \mathbb{Z}$ definiere \\
$a \equiv b \pmod m : \Leftrightarrow m \mid (a-b)$ \\

''a kongruent b modulo m''

Beispiel: $17 \equiv -4 \pmod 7 \qquad 17 \neq \bmod -4 \bmod 7 = 3$

Beachte: \\
$\bullet \equiv \bullet \pmod m$ ist Relation auf $\mathbb{Z}$ \\
$\bullet \bmod m : \mathbb{Z} \rightarrow \{0, 1, ..., m-1\} \qquad a \rightarrow a \bmod m$

\subsection[Satz (zu Kongruenzrelationen)]{Satz} %6.15
\begin{itemize}

\item[a)] $a \equiv b \pmod m \Leftrightarrow a \bmod m = b \bmod m$
\item[b)] $a \equiv 0 \pmod m \Leftrightarrow m \mid a$
\item[c)] $a \bmod m \equiv a \pmod m$
\item[d)] Kongruenzrelation modulo m ist Äquivalenzrelation
\item[e)] $a \equiv b \pmod m , c \in \mathbb{Z} \Rightarrow c \cdot a \equiv c \cdot b \pmod m$

\end{itemize}

\subsection{Beispiel} %6.16
\begin{itemize}

\item $17 \bmod 7 = 3$ \\
$17 \equiv 3 \pmod 7$ \\
$17 \equiv 10 \pmod 7$ \\
$17 \equiv -4 \pmod 7$

\item $2 \cdot 3 \equiv 2 \cdot 2 \pmod 2$ \\
$6 \equiv 4 \pmod 2$ \\
aber $3 \not\equiv 2 \pmod 2$

\end{itemize}

\subsection*{Beweis zu 6.15)}

\begin{itemize}

\item[a)] \begin{itemize}

\item["`$\Rightarrow$"'] $ a \equiv b \pmod m \Leftrightarrow a = k m + b$ für $k \in \mathbb{Z}$ \\
$\Rightarrow a \bmod m = (k  \cdot  m) \bmod m + b \bmod m = b \bmod m$

\item["`$\Leftarrow$"'] $a \bmod m = b \bmod m \Rightarrow$ \\
$a = a_1 \cdot m + r$ (1) \\
$b = a_2 \cdot m + r$ (2)

$a -b = (a_1 - a_2) \cdot m$ \\
$\Rightarrow m | (a -b)$

\end{itemize}

\item[b)] Spezialfall von a) $\qquad$ ($b=0$)

% ==============
% 13 Januar 2016
% ==============

\item[c)] zu zeigen: $a \bmod m \equiv a \pmod m$ \\
$\overset{\text{a)}}{\Leftrightarrow} (a \bmod m) \bmod m \overset{\text{6.11 a)}}{=} a \bmod m$

\item[d)] reflexiv? symmetrie, transitivität?

$m \mid (a-a) \checkmark \qquad m \mid (a-b) \checkmark \qquad \Leftrightarrow m \mid (b-a)$ 

$m \mid (a-b), \quad m \mid (b-c) \Rightarrow m \mid [\underbrace{(a-b)+(b-c)}_{(a-c)}]$

\item[e)] $m \mid (a-b) \Rightarrow a-b = k \cdot m \quad k \in \mathbb{Z}$ \\
$\text{\qquad \quad} \Rightarrow ca-cb = c \cdot k \cdot m = kc \cdot m$ \\
$\text{\qquad \quad} m \mid (ca-cb)$

\end{itemize}

Wiederholung: Kongruenz modulo m
$\text{\qquad \quad} m \in \mathbb{N} \quad a,b \in \mathbb{Z}$ \\
$\text{\qquad \quad} a \equiv b \pmod m$ \\
$\text{\qquad \quad} :\Leftrightarrow m \mid (a-b)$

\subsection[Satz und Definition (Äquivalenzklassen, Kongruenzrelation, \newline Repräsentantensysteme)]{Satz und Definition} %6.17

Die Äquivalenzklassen der Kongruenzrelation modulo m sind genau die Mengen

$\{k \cdot m : k \in \mathbb{Z}\}, \{1 + km : k \in \mathbb{Z}\}, ... \{(m-1)+km : k \in \mathbb{Z}\}$

Kurzschreibweise: $r+m \mathbb{Z} \quad r=0, ..., m-1$

Die Menge $\mathbb{Z}_m = \{0,1,...,m-1\}$ ein Repräsentantensystem.

Beispiel: $\bmod 2$ gerade und ungerade \\
$\text{\qquad \quad}\mathbb{Z}_2 = \{0,1\}$

Beispiel 6.16: 
\begin{align*}
x &\equiv 3 \pmod 7 \\
3 &\equiv 3 \pmod 7 \\
10 &\equiv 3 \pmod 7 \\
17 &\equiv 3 \pmod 7
\end{align*}

\subsection[Satz (Eigenschaften der Kongruenzrelation)]{Satz} %6.18

Seien $a_1 \equiv a_2 \pmod m$ und $*:\ +,-,\cdot$ \\
$\text{\qquad} b_1 \equiv b_2 \pmod m$
	
Dann $a_1 * b_1 \equiv a_2 * b_2 \pmod m$
	
Beweis:	Nach 6.14 a)
\begin{align*}
a_1 \bmod m &= a_2 \bmod m & (1) \\
b_1 \bmod m &= b_2 \bmod m & (2)
\end{align*}
\begin{align*}
\text{Dann } (a_1 * b_1) \bmod m &\overset{\text{6.11b)}}{=} [(a_1 \bmod m) * (b_1 \bmod m) ] \bmod m \\
&\overset{(1,2)}{=}  [(a_2 \bmod m) * (b_2 \bmod m)] \bmod m \\
&\overset{\text{6.11b)}}{=} (a_2 * b_2) \bmod m
\end{align*}
\hfill $\square$


\subsection{Beispiel} %6.19

\begin{itemize}
\item[a)] Welche Zahlen erfüllen die Voraussetzung?
\begin{align*}
&											&	2x + 1 &\equiv 5 \pmod 6 \\
&											&	      1 &\equiv 1 \pmod 6 \\
& \overset{\text{6.18}}{\Leftrightarrow}	&	     2x &\equiv 4 \pmod 6
\end{align*}

Welche $x \in \{0,...,5\} = \mathbb{Z}_6$ erfüllen die Kongruenzrelation?

$x=2, \qquad x=5$

$2x \equiv 4 \pmod 6 \Leftrightarrow 2 \cdot (x \bmod 6) \equiv 4 \pmod 6$

Lösungsmenge: $(2+6\mathbb{Z}) \cup (5+6\mathbb{Z})$		

\item[b)] $x^2 + 3y = 3z^2 \qquad x,y,z \in \mathbb{Z}$

Trick Mod-Reihe:

\begin{align*}
	(x \bmod 3)^2 &\equiv 2 \pmod 3 \\
	0^2 &\equiv 0  \pmod 3 \\
	1^2 &\equiv 1 \pmod 3 \\
	2^2 &\equiv 1 \pmod 3
\end{align*}
	
Gleichung hat keine Lösung!

\end{itemize}

\subsection[Definition (größter gemeinsamer Teiler, kleinste gemeinsame Vielfache)]{Definition} %6.20

Seien $a_1, ..., a_r \in \mathbb{Z}$

\begin{itemize}
\item[a)] Ist mindestens ein $a \neq 0$, so ist der \underline{größte gemeinsame Teiler} $ggT(a_1, ..., a_r)$ die größte \underline{natürliche} Zahl, die alle $a_i$ teilt.

\item[b)] Sind alle $a \neq 0$, so ist das \underline{kleinste gemeinsame Vielfache} $kgV(a_1,..., a_r)$ die kleinste \underline{natürliche} Zahl die von allen $a_i$ geteilt wird.

\end{itemize}

\subsection{Bemerkung} %6.21

\begin{itemize}
\item[a)] $ggT(a_1,..., a_r)$ existiert und ist eindeutig.

	$\text{\qquad} 1 \mid a_i \qquad \forall i \in \{1,...,r\} \qquad t \leq \abs{a_i}$
	
\item[b)] $kgV(a_1,..., a_r)$ existiert und ist eindeutig.

	$\text{\qquad} \abs{a_1} \cdot ... \cdot \abs{a_r}$ wird von allen $a_i$ geteilt.
	
\item[c)] $ggT(a_1, ..., a_r) = ggT(\abs{a_1},...,\abs{a_r})$
	$kgV(a_1, ..., a_r) = kgV(\abs{a_1},...,\abs{a_r})$.
	
\end{itemize}

\subsection[Definition (teilerfremd, paarweise teilerfremd)]{Definition} %6.22

Ist $ggT(a_1,...,a_r) = 1$, so heißen $a_1,...,a_r$ \underline{teilerfremd}.

Ist $ggT(a_i, a_j) = 1$	für alle $i \neq j$, so heißen $a_1,...,a_r$ \underline{paarweise} teilerfremd.

Stärker als Teilerfremd

$6,10,15$ \\
$ggT(6,10) = 2$ \\
$ggT(10,15) = 5$ \\
$ggT(6,15) = 3$ \\
$ggT(6,10,15) = 1$


Berechnung des $ggT$ zweier Zahlen mit \underline{Euklidischem Algorithmus} \hfill (Euklid 365 v.Chr. - 300 v.Chr.)

Grundprinzipien im folgenden Lemma:

\subsection[Lemma (Bestimmung des ggT)]{Lemma} %6.23

Seien $a,b,q \in \mathbb{Z} \quad b \neq 0$. Dann ist

$ggT(a,b) = ggT(q \cdot a + b, a)$.

[Beachte für den zweiten ggT: ist $a=0$, so ist $q \cdot a + b = b \neq 0$ ]

Beweis:	$\quad t \mid (q \cdot a + b) \land t \mid a \overset{\text{6.2 b)}}{\Leftrightarrow} t \mid a \land t \mid b$
\hfill $\square$

Gegeben seien jetzt $a,b$, nicht beide 0, O.B.d.A $b \neq 0$

Wir wollen $ggT(a,b)$ bestimmen.

\begin{align*}
\text{Setze } a_0 &= a, \quad a_1 = b & \\
a_0 &= q_1 a_1 + a_2 		& \text{(Division mit Rest)} \\
	a_1 &= q_2 a_2 + a_3		& \text{(Division mit Rest)} \\
		&\text{\space\:}\vdots \\
	a_{n-1} &= q_n a_n + 0		&\text{erstes Mal Rest 0}
\end{align*}
	
Nun ist $ggT(a,b) = ggT(a_0,a_1) \overset{\text{6.23}}{=} ggT(a_1,a_2) = ... = ggT(a_{n-1},a_n) = \abs{a_n}$.

Beachte: Ist $n \geq 2$, so auch $a_n > 0$, d.h. $ggT(a_{n-1},a_n) = a_n$.

D.h. nur für $n=1$, d.h. $b \mid a$, muss man Betrag verwenden (falls $b < 0$).

Beweis für Euklidischen Algorithmus \checkmark

\subsection{Euklidischer Algorithmus} %6.24

Input: $a,b \in \mathbb{Z} \qquad$ nicht beide 0

IF $b = 0$, then $y := \abs{a}$ \\
IF $b \neq 0$ and $b \mid a$, then $y := \abs{b}$ \\
IF $b \neq 0$ and $b \nmid a$ then $x:= a, \quad y := b$ \\
$\text{\qquad}$	while $x \bmod y \neq 0$ do \\
$\text{\qquad\qquad} r := x \bmod y, \quad x := y, \quad y := r$

Output $y\ (= ggT(a,b))$

Beispiel:

\begin{itemize}
\item[a)] $ggT(-20,0) = 20$
\item[b)] $ggT(-20,-10) = 10$
\item[c)] $a=48, \quad b=-30$ \\
	also $x=48, \quad y=-30$ \\	
	$48 \bmod (-30) = 18 \neq 0 \qquad x =-30, \quad y=18$ \\	
	$(-30) \bmod 18 = 6 \neq 0 \qquad x=18, \quad y=6$ \\	
	$18 \bmod 6 = 0$ \\	
	$\rightarrow ggT(48,-30) = 6$
\end{itemize}

% ==============
% 18 Januar 2016
% ==============

\subsection{Satz (Bachét de Mérirac (1581 - 1638))} %6.25

Seien $a, b \in \mathbb{Z}$, nicht beide $0$. Dann existieren  $s, t$ mit $ggT(a, b) = sa + tb$

Anmerkung: In Literatur  auch Lemma von Bezont.

\textbf{Beweis:}

Ist $b = 0, ggT(a, b) = |a| = s \cdot a + t \cdot b$ mit

\[ s =
  \begin{cases}
    1 & \text{falls } a > 0 \\
    -1  & \text{falls } a < 0 \
  \end{cases}
\]

Ist $b \neq 0, b | a$ so $ggT(a, b) = |b| = s \cdot a + t \cdot b$ mit

\[ t =
  \begin{cases}
    1 & \text{falls } b > 0 \\
    -1  & \text{falls } b < 0 \
  \end{cases}
\]

Ist $b \neq 0, b \nmid a \qquad a_0 = a, a_1 = b$

EA: $a_0 = q_1 \cdot a_1 + a_2$, \\
$a_1 = q_1 \cdot a_2 + a_3, ... ,a_{n-1} = q_n a_n + 0$ \\
$ggT(a, b) = a_n$

Zeige durch Induktion nach j die Existenz von $s_j, t_j \in \mathbb{Z}$ mit \\
$A(j): a_j = s_j \cdot a_0 + t_0 \cdot a_1$ \\
beachte die Induktion läuft nur solange wie $a_j$ definiert ist.

I.A: \\
$A(0): j = 0: s_0 = 1, t_0 = 0 \qquad a_0 = 1 \cdot a_0 + 0 \cdot a_1$ \checkmark \\

$A(1): j=1: s_1 = 0, t_1 = 1 \qquad a_1 = 0 \cdot a_0 + 1 \cdot a_1$ \checkmark

I.S: \\
I.V: Sei $2 \leq j \leq n$ und es gelte: \\
$A(j-2): a_{j-2} =  s_{j-2} \cdot a_b + t_{j-2} \cdot a_1$
$A(j-1): a_{j-1} =  s_{j-1} \cdot a_b + t_{j-1} \cdot a_1$

I.B: $A(j) (A(j-2) \wedge A(j-1) \Rightarrow A(j))$ \\
EA

$a_j = a_{j-2} - q_{j-1} \cdot a_{j-1}$

$\underbrace{=}_{I.V.} s_{j-2} \cdot a_0 + t_{j-2} \cdot a_1 - q_{j-1} \cdot (s_{j-1} + t_{j-1} a_1)$

$= \underbrace{(s_{j-2} - q_{j-1} \cdot s_{j-1})}_{=: s_j} \cdot a_0 + \underbrace{(t_{j-2} - q_{j-1} \cdot t_{j-1})}_{=: t_j} \cdot a_1$

$\Rightarrow$ Satz folgt mit $j = n$ und $s = s_n, t = t_n$ \hfill $\square$

\subsection{Erweiterter Euklidischer Algorithmus} %6.26

Input $a, b \in \mathbb{Z}$ (nicht beide $0$)

IF $b = 0$ then \\
$\text{\qquad} y := \abs{a}$, if $a > 0$ then $s := 1$ else $s := -1$ \\
$\text{\qquad} t = 0$

IF $b \neq 0$ and $b \mid a$ then \\
$\text{\qquad} y := \abs{b},\ s = 0$, if $b > 0$ then $t := 1$ else $t := -1$

IF $b \neq 0$ and $b \nmid a$ then \\
$\text{\qquad} x := a,\ y := b, s_1 := 1, s_2 := 0, t_1 := 0, t_2 := 1$ \\
$\text{\qquad}$ while $x \mod y \neq 0$ do \\
$\text{\qquad\qquad} q := x \bdiv y,\ r = x \bmod y,$ \\
$\text{\qquad\qquad} s = s_1 - q \cdot s_2, \qquad t := t_1 - q \cdot t_2,$ \\
$\text{\qquad\qquad} s_1 = s_2,\ s_2 = s, \qquad t_1 = t_2,\ t_2 = t,$ \\
$\text{\qquad\qquad} x = y,\ y = r$
\begin{align*}
\text{Output:} \quad & y(ggT(a,b)) & : \; y(=ggT(a,b)),s,t(y=s \cdot a + t \cdot b) \\
& s,t (y = s \cdot a + t \cdot b) &
\end{align*}

Beispiel: $a = 48, b = -30$

\begin{tabular}{r | c | c | c | c | c | c | c | c | c | c | c}
\cline{2-11}
& x & y & $s_1$ & $s_2$ & s & $t_1$ & $t_2$ & t & q & r \\
\cline{2-11}
& 48 & -30 & 1 & 0 & & 0 & 1 & & & \\
\cline{1-11}
\multicolumn{1}{| r |}{$0 \neq 18 = 48 \bmod (-30) = 18 \neq 0$} & -30 & 18 & 0 & 1 & 1 & 1 & 1 & 1 & -1 & 18 \\
\cline{1-11}
\multicolumn{1}{| r |}{$= 6 \neq 0$} & \multirow{2}{*}{18} & \multirow{2}{*}{6} & \multirow{2}{*}{1} & \multirow{2}{*}{2} & \multirow{2}{*}{\uline{2}} & \multirow{2}{*}{1} & \multirow{2}{*}{3} & \multirow{2}{*}{\uline{3}} & \multirow{2}{*}{-2} & \multirow{2}{*}{6} \\
\multicolumn{1}{| r |}{$(-30) \bmod 18$} & &&&&&&&&& \\
\cline{1-11}
$18 \mod 6 = 0$ & \multicolumn{11}{l}{$6 = 2 \cdot 48 + 3 \cdot (-30) \rightarrow$ nicht eindeutig} \\
 & \multicolumn{11}{l}{$48 = (-1) \cdot (-30) + 18 \quad s = s_1 - q \cdot s_2 \quad t = t_1 - q \cdot t_2$}
\end{tabular}

Beachte: Darstellung ist nicht eindeutig! \\
$\text{\qquad\qquad} 6 = 7 \cdot 48 + 11 \cdot (-30)$

\subsection{Korollar} %6.27
(Seien $a, b, c \in \mathbb{Z}$ und $m \in \mathbb{N}.$

\begin{itemize}

\item[a)] Sind $a, b$ nicht beide $0$, so gilt:
$a$ und $b$ teilerfremd $\Leftrightarrow \exists s, t \in \mathbb{Z}: s \cdot a + t \cdot b = 1$

\item[b)] Sind $a, b$ nicht beide $0$. So gilt:
Ist $c|a$ und $c|b$, so gilt $c | ggT(a, b)$

\item[c)] Ist $ggT(a, b) = 1$ und $a|b \cdot c$, so $a | c$

\item[d)] Ist $ggT(c, m) = 1$ und $c \cdot a \equiv c \cdot b (\mod m)$
so gilt $a \equiv b (\mod m)$

\end{itemize}

Beweis:

\begin{itemize}

\item[a)] $\Rightarrow$: 6.25 \\
$\Leftarrow d = ggT(a, b)$ \\
nach 6.2.b): $d | \underbrace{sa + tb}_{1} \Rightarrow d = 1$

\item[b)] 6.25 $ggT(a, b) = s \cdot a + t \cdot b$ \\
$c |a \wedge c | b \underbrace{\Rightarrow}_{6.2b)} c | sa + tb$

\item[c)] 6.25 $\exists s, t \in \mathbb{Z}$ mit $1 = s \cdot a + t \cdot b$ \\
also $c = s \cdot c \cdot a + t \cdot c \cdot b$ \\
Da $a | a$ und $a | bc$, folgt (6.2b) \\
$a | sca + tbc \Rightarrow a | c$

\item[d)] $m | c (a-b), ggT(c, m) = 1$

$\Rightarrow m | (a -b)$ also $a \equiv b (\mod m)$

Vergleiche: 6.15e).

\end{itemize}

\subsection{Bemerkung} %6.28

\begin{itemize}

\item[a)] Ist $k > 2$, so $ggT(a_1, ..., a_k) = ggT(ggT(a_1, ...a_k), a_k)$

\item[b)] $\exists s_1, ... s_k, s \in \mathbb{Z}$ mit $ggT(a_1, ... a_k) = s_1 a_1 + ... + s_k a_k$ (Beweis per Induktion)

\item[c)] 6.27c) Verallgemeinerbar auf k Zahlen: \\
$c | a_1, ... , a_k \Rightarrow c | ggT(a_1, ... , a_k)$

\item[d)] Ist $k > 2$, so $kgV(a_1, ... , a_k) = kgV(kgV(a_1, ..., a_k), a_k) a_{k-1}$ \\
und $a \neq 0$ (alle nicht 0)

\end{itemize}

\subsection[Definition (Primzahl)]{Definition} %6.29
Eine natürliche Zahl $p > 1$ heißt Primzahl, wenn $1$ und $p$ die einzigen natürlichen Zahlen sind,
die $p$ teilen.

(D.h. $ggT(k, p) = 1$ für alle $1 \leq k \leq p$)

\subsection{Satz} %6.30
Ist $p$ eine Primzahl, $a_1, ... ,a_k \in \mathbb{Z}$ und $p | a_1 \cdot a_2 \cdot, ... \cdot a_k$ \\
so existiert $1 \leq j \leq k$ mit $p | a_j$

Beweis: Induktion nach $k$:

IA: \\
$k = 1$ \checkmark

IS: \\
$k -1 \rightarrow k$ Gilt $p | a_k$ \checkmark \\
Ist $p \nmid a_k$ so $ggT(p, a_k) = 1$ (P Primzahl) \\
Nach 6.27c): $p | a_1 \cdot ... \cdot a_{k-1}$ \\
$\Rightarrow p | a_j$ für ein $1 \leq j \leq k - 1$ \hfill $\square$

\subsection{Fundamentalsatz der elementaren Zahlentheorie} %6.31
Zu jeder natürlichen Zahl $a \geq 2$ gibt es endlich viele
verschiedene Primzahlen $p_1, ... ,p_n$ und natürliche Zahlen $e_1, ... ,e_n$ mit
$a = p_{1}^{e_1} \cdot ... \cdot p_{n}^{e_n}$
Die $p_i$ heißen Primfaktoren von $a$. Die Darstellung von $a$ als Produkt von Primzahlen
ist bist auf die Reihenfolge eindeutig.

% ==============
% 20 Januar 2016
% ==============

$$a = \prod_{i=1}^{n} p^{e_i}_i = p_1^{e_1} \cdot ... \cdot p_n^{e_n}$$

Beweis: Existenz (per Induktion)

IA: $\qquad a = 2$ \checkmark

IS: $\qquad$ IV: $\quad$ Aussage gilt für $2, ..., a-1$

$\qquad\quad\ \ $ IB: $\quad$ Aussage gilt für $a$.

Beweis:

\qquad	Fall 1: $a$ Primzahl \checkmark
	
\qquad	Fall 2: $a$ keine Primzahl
	
\qquad	$a=b \cdot c$ für $1 \lneq b, c \lneq a$
	
\qquad	wende I.V. auf $b$ und $c$ an $\rightarrow$ fertig.
	
Eindeutigkeit (per Induktion) über $s(a) := \sum_{i=1}^{n} e_i$ \hfill $s(2) = 1, \ s(4) = 2$

IA:		$s(a) = 1 \Rightarrow a$ Primzahl \checkmark

IV:		Aussage gelte für alle $a', s(a') < s(a)$

IB:		Aussage gilt auch für $a$

Beweis:
$$a = p_1 \cdot ... \cdot p_m = q_1 \cdot ... \cdot q_e \qquad | s(a) = m \leq l$$
\hfill $p_i, q_j$ Primzahl (nicht unbedingt verschieden)

$$p_1 \mid a \Rightarrow p_1 \mid q_1 \cdot ... \cdot q_e \overset{6.30}{\Rightarrow} p_1 \mid q_j \text{ für ein } j$$

$$\overset{q_j \text{ Prim}}{\Rightarrow} p_1 = q_j \rightarrow a' = p_1 \cdot ... \cdot p_n = q_1 \cdot q_{q-1} \cdot q_{q+1} \cdot ... \cdot q_e$$

\qquad \qquad wende I.V: auf $a'$ an, fertig \hfill $\checkmark$

\subsection{Korollar (Euklids Lemma)} %6.32

Es gibt unendlich viele Primzahlen.

Beweis: Angenommen es gibt nur endlich viele Primzahlen $p_1, ..., p_n$

$a = p_1 \cdot p_2 \cdot ... \cdot p_n + 1$

$\overset{6.31}{\Rightarrow} \exists p_i \quad p_i \mid a \quad q = p_i \quad 1 \leq i \leq n$
	
Dann gilt nach 6.2 b) $\quad q \mid \underbrace{a - p_1 \cdot ... \cdot p_n}_{=1}$

$\Rightarrow q = 1$ \Lightning

\subsection{Korollar} %6.33

Seien $a,b \in \mathbb{N} \quad a,b \geq 2$

Seien $P(a)$ und $P(b)$ die Menge der Primteiler von $a$ und $b$, d.h.

$$ a = \prod_{p \in P(a)} p^{n(p)} \quad b = \prod_{p \in P(b)} p^{m(p)}	\qquad n(p), m(p) \in \mathbb{N}$$

Dann ist $$ggT(a,b) = \prod_{p \in P(a) \cap P(b)} p^{min(n(p),m(p))}$$

\hfill (Hinweis: Leeres Produkt $= 1$)
	
$$KgV(a,b) = \prod_{p \in P(a) \setminus P(b)} p^{n(p)} \cdot \prod_{p \in P(a) \cap P(b)} p^{max(n(p),m(p))} \cdot \prod_{p \in P(b) \setminus P(a)} p^{m(p)}$$

insbesondere $a \cdot b = ggT(a,b) \cdot KgV(a,b)$

\underline{Beispiel}

$a = 1248 = 2^5 \cdot 3 \cdot 13$

$b = 3780 = 2^2 \cdot 3^3 \cdot 5 \cdot 7$

$ggT(a,b) = 2^2 \cdot 3^1 = 12$

$KgV(a,b) = 2^5 \cdot 3^3 \cdot 5 \cdot 7 \cdot 13 = 393 120$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Kapitel 7: Kombinatorik
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Kombinatorik} %

Ziel: Anzahlbestimmungen von endlich vielen verschiedenen Objekten (Kombinationen).

\subsection{Satz} %7.1

\begin{itemize}
\item[a)] Seien $A,B$ endliche Mengen.

Dann gilt: $\abs{A \cup B} = \abs{A} + \abs{B} - \abs{A \cap B}$

\item[b)] $A_1, ..., A_n$ endliche Mengen.

Dann $\abs{A_1 \times ... \times A_n} = \prod_{i=1}^n \abs{A_i}$

$(q_1, ..., q_n) \in \prod_{i=1}^n A_i$

\end{itemize}

Beweis: klar

%%  TODO: Zeichnung A \cap B mit je einigen Elementen, 3 in A, 2 in B, 1 in A cap B. Text dazu: 4+3-1 = 6

Bemerkung: a) lässt sich verallgemeinern $\leadsto$ Ein-/Ausschlussprinzip (WHK 2.32)

Beweis (per Induktion):

IA: $n=1$ \checkmark

IS: $n \to n+1$

$\abs{A_1 \times ... \times A_n \times A_{n+1}} = \sum_{a \in A_{n+1}} \abs{A_1 \times ... \times A_n \times \{a\}} = \abs{A_{n+1}} \cdot \abs{A_1 \times ... \times A_n} \overset{I.V.}{=} \abs{A_{n+1}} \cdot \prod_{i=1}^n \abs{A_i} \checkmark$ \hfill $\square$

\subsection{Beispiel} %7.2

\begin{itemize}
\item[a)] Wieviele ''Wörter'' der Länge $n$ gibt es über dem ''Alphabet'' \{0,1\}

$\to$ Wort der Länge $n \cong $ n-Tupel.

$\abs{\{0,1\}^n} = 2^n$

$\abs{\{0,1\}^3} = \abs{\{(0,0,0),(0,0,1),...\}} = 8$

\item[b)] Wie viele Folgen der Länge 1000 aus den Symbolen $A,G,C,T$ gibt es?

$\to 4^{1000}$

\end{itemize}

\uline{Auswahlanzahlen}

Anzahl an möglichen Auswahlen von $k$ Objekten aus einer Menge mit $n$ Objekten.


%% TODO: Zeichnung: Zwei Mengen mit Punkten, erste Menge mit n bezeichnet, Pfeil von Menge 1 zu 2, mit k bezeichnet

\begin{itemize}
\item Reihenfolge relevant oder nicht
\item Wiederholung möglich oder nicht
\end{itemize}
$\to$ 4 Typen von Auswahlen

\subsection{Geordnete Auswahl ohne Wiederholung} %7.3

\underline{Fragestellung I}

Menge $B$ (''Urne'') mit $n$ verschiedenen Objekten $b_1,...,b_n$. Wähle nacheinander $k$ davon aus und lege sie der Reihenfolge nach aus.

$\leadsto (b_{i_1}, b_{i_2},...,b_{i_k})$ Dabei $i_j \neq i_l \quad j \neq l$

%% TODO Zeichnung: Menge {a,b,c} mit zwei Pfeilen: Pfeil "a b" führt zu (b,a); Pfeil "b a" führt zu (a,b); außerdem (b,a) \neq a(b)

Wie viele solcher $k$-Tupel sind möglich?

\underline{Fragestellung II} (nur andere Interpretation)

Wie viele \uline{injektive} Abbildungen  $\pi = \left( \begin{array}{c c c}
1 & ... & k \\
b_{i_1} & ... & b_{i_k}
\end{array} \right)$

$\pi(a) = \pi(b) \overset{\pi \text{ injektiv}}{\Rightarrow} a = b$

\subsection{Definition} %7.4

Setze für $k,n \in \mathbb{N}$

$(n)_k := n \cdot (n-1) \cdot ... \cdot (n-k+1)$

Also $(n)_1 = n$ und für $k > n, \quad (n)_k = 0$

(Rekursive Definition $(n)_k := (n)_{k-1} \cdot \underbrace{(n-k+1)}_{=n-(k-1)}$ )

Für $k \leq n : (n)_k = \frac{n!}{(n-k)!}$

Insbesondere $(n)_n = n!$

\subsection{Satz} %7.5

Es gibt genau $(n)_k$ viele Auswahlen von $k$ Objekten aus einer Menge $B$ mit $n$ Objekten, wenn keine Wiederholungen möglich sind und die Anordnung berücksichtigt wird.

\uline{Beispiel:} Erste 3 Plätze bei einem Rennen mit 12 Teilnehmern.

% ==============
% 25 Januar 2016
% ==============

%TODO Skizze der Urne

\textbf{Beweis} Sei $n \in \mathbb{N}$ beliebig, aber fest. Induktion nach $k$:

\uline{Ind.anf.}: $k=1$: $n$ Möglichkeiten $(n)_1 = n$ \checkmark

\uline{Ind.schritt}: Sei $k \geq 1$.

\uline{Ind.vor}: Aussage sei wahr für $k$

\uline{Ind.beh}: Die Aussage gelte für $k+1$, d.h. bei $k+1$ Objekten gibt es $(n)_{k+1}$ Möglichkeiten.

\uline{Beweis}:

\begin{itemize}

\item falls $k+1 > n$, dann $0$ Möglichkeiten $= (n)_{k+1}$

\item falls $k+1 \leq n$: Nach Ind.vor. gibt es $(n)_k$ Möglichkeiten, $k$ Elemente aus $B$ auf die Plätze $1, ... ,k$ zu verteilen.

Für jede davon gibt es $n-k$ Möglichkeiten, Platz $k+1$ zu besetzen.

$\Rightarrow$ insgesamt $(n)_k \cdot (n-k)$

$$\underbrace{(n)_k}_{\frac{n \cdot (n-1) \cdot ... \cdot (n-k+1)}{k \text{ Faktoren}}} \cdot (n-k) = (n)_{k+1}$$
\hfill $\square$

\end{itemize}

\subsection{Beispiel} %7.6
\begin{itemize}

\item[a)] Beispiel 7.3 Pferderennen:

$12 \cdot 11 \cdot 10 = 1320$ Möglichkeiten für die ersten drei Plätze.

\item[b)] Anzahl der Wörter der Länge $3$ über $\{a, b, ... ,z\}$, die keinen Buchstaben enthalten:

$26 \cdot 25 \cdot 24 = 15600$

Wie viele davon enthalten ein $x$?

$26 \cdot 25 \cdot 24 - \underbrace{25 \cdot 24 \cdot 23}_{\text{ohne } x} = 25 \cdot 24 \cdot (26 - 23) = 1800$

(vergleiche: Anzahl aller Wörter der Länge $3$ (7.1b)) \\
$= 26^3 = 17576$)

\end{itemize}

Aus 7.3 und 7.5 folgt:

\subsection{Korollar} %7.7

$A, B \neq \emptyset$ endliche Mengen mit $|A| = k, |B| = n$, dann gibt es genau $(n)_k$ injektive Abbildungen $A \rightarrow B$.

$|A| = k, \quad |B| = n$ \\
$(n)_k$ injektive Abbildungen $A \rightarrow B$

Insbesondere: $|A| = |B| = n$, dann gibt es $(n)_n = n!$

Bijektionen $A \rightarrow B$

\subsection{Definition} %7.8

Eine bijektive Abbildung $A \rightarrow B$ heißt \uline{Permutation auf A}.

Anzahl der Permutationen auf endlicher Menge $A = |A| !$ (Korollar 7.7)

speziell: $A = \{1, ..., n\}, |A| = n$ \\
Dann bezeichnet $S_n$ die Menge aller Permutationen auf $A$, es gilt also $|S_n| = n!$

\subsection{Geordnete Auswahl mit Wiederholung} %7.9

%TODO Urnen Skizze

Wähle $k$ mal ein Objekt aus der Urne mit $n$ Objekten aus, dabei wird die Reihenfolge der Ziehungen notiert und das Objekt nach der Auswahl wieder in die Urne zurückgelegt.

\uline{Beispiel:} \\
Ziehen einer Losnummer , (Erstellung eines Autokennzeichens)

Oder: Färbe die Objekte $1, ... ,k$ mit jeweils einer von $n$ Farben, die Farbe darf dabei mehrfach verwendet werden.

\subsection{Satz} %7.10
Es gibt genau $n^k$ geordnete Auswahlen mit möglicher Wiederholung von $k$ Elementen aus einer Menge $B$ mit $n$ Elementen.

\uline{Beweis:} \\
Menge aller Auswahlen ist $\underbrace{B \times B \times ... \times B}_{k} = B^k$

Nach 7.1 gilt $|B^k| = |B|^k = n^k$. \hfill $\square$

\subsection{Bemerkung / Korollar} % 7.11

Schreibe Auswahl als \quad
$
\begin{pmatrix}
1 & 2 & ... & k \\
b_1 & b_2 & ... & b_k
\end{pmatrix}
$

($b_i \in B$, nicht notwendig verschieben), dann ist die Anzahl der Auswahlen in 7.10 genau die Anzahl \uline{aller} Abbildungen $\{1, ... ,k\} \rightarrow B$

Also gibt es genau $n^k$ Abbildungen $A \rightarrow B$, wenn $|A| = k, \quad |B| = n$.

\subsection{Ungeordnete Auswahl ohne Wiederholung} %7.12
%TODO Urnen Skizze

Urne mit $n$ Objekten, wähle $k$ Objekte aus, Reihenfolge ist unerheblich (\textit{Korb}). Wie viele Möglichkeiten (verschiedene Korbfüllungen) gibt es?

\uline{Beispiel:} \\
Lotto $(n = 49, k = 6)$

Feuerwehrproblem


% ==============
% 27 Januar 2016
% ==============

d.h. wie viele k-elementige Teilmengen besitzt eine n-elementige Menge?

\subsection[Definition (Binomialkoeffizient)]{Definition} %7.13

$n,k \in \mathbb{N}_0$

$\binom{n}{k} := \begin{cases}
0 & \text{, falls } k > n \\
\frac{n!}{k! \cdot (n-k)!} & \text{, falls } 0 \leq k \leq n
\end{cases}$

("n über k")

\underline{Binomialkoeffizient}

(für $n,k \in \mathbb{N}$ gilt also $\binom{n}{k} = \frac{(n)_k}{k!}$)

$\binom{n}{0} = 1 = \binom{n}{n}$

$\binom{n}{1} = n = \binom{n}{n-1}$

$\binom{n}{2} = \frac{n(n-1)}{2}$

\subsection[Bemerkung/Satz (Pascal'sches Dreieck)]{Bemerkung / Satz} %7.14

\begin{itemize}
\item[a)] $\binom{n}{k} = \binom{n}{n-k}$

\item[b)] $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$ (Übung)
\end{itemize}

$\leadsto$ Pascal'sches Dreieck

\begin{tabular}{rrcccccccccr}
$n=0$: & & & & & & 1 & & & & &\\
$n=1$: & & & & & 1 & & 1 & & & &\\
$n=2$: & & & & 1 & & 2 & & 1 & & &\\
$n=3$: & & & 1 & & 3 & & 3 & & 1 & &$\leftarrow  \binom{3}{0} \binom{3}{1} \binom{3}{2} \binom{3}{3}$\\
$n=4$: & & 1 & & 4 & & 6 & & 4 & & 1 & \\
 & & \multicolumn{9}{c}{\vdots} &
\end{tabular}

\begin{tabular}{cccc}
$\text{\qquad\:}$ & $\uparrow$ & $\uparrow$ & \\
& $k=0$ & $k=1$ & ... 
\end{tabular}

\subsection[Satz (Anzahl ungeordneter Auswahlen)]{Satz} %7.15

Die Anzahl der ungeordneten Auswahlen ohne Wiederholung von k Elementen aus einer Menge $B$ mit $n$ Elementen ist $\binom{n}{k}$.

Dies ist genau die Anzahl der k-elementigen Teilmengen von $B$.

\underline{Beweis}

\begin{itemize}
\item Satz gilt für $\underbrace{k > n}_{\leadsto 0}$ und $\underbrace{k = 0}_{\leadsto 1}$

\item Sei $1 \leq k \leq n$.

Anzahl geordneter Auswahlen ohne Wiederholung

$\underset{\text{7.5}}{=} (n)_k$

$((a,b,c),(b,a,c),(c,a,b), ...)$

\nopagebreak

$\text{\qquad\quad} \searrow \quad \downarrow \quad \swarrow \qquad \qquad \}\ 3!$

\nopagebreak

$\text{\qquad\qquad} \{a,b,c\}	\qquad \leftarrow$ ungeordnete Menge (Urne) %% TODO Urne statt Menge anzeigen

je $k!$ dieser geordneten Auswahlen führen zur selben ungeordneten Auswahl, erhalte als $\frac{(n)_k}{k!} = \binom{n}{k}$ \hfill $\square$

\end{itemize}

\subsection[Beispiel (Lotto 6 aus 49)]{Beispiel}

\begin{itemize}
\item[a)] Lotto 6 aus 49

$\binom{49}{6} = \frac{49!}{6! \cdot 43!} = 13.983.816$

Wahrscheinlichkeit für 6 Richtige im Lotto: $\frac{1}{13.983.816}$

\item[b)] Anzahl Möglichkeiten für genau 4 Richtige:

$\underbrace{\binom{6}{4}}_{\mathllap{\text{\# von 6 Gewinnzahlen 4 anzukreuzen}}} \cdot \underbrace{\binom{43}{2}}_{\mathrlap{\text{\# von 43 Nicht-Gewinnzahlen 2 anzukreuzen}}} = 15 \cdot 903 = 13.545$

Wahrscheinlichkeit für 4 Richtige: $\frac{13.540}{13.983.816} \approx 0,00097 (\approx 0,1\%) $

\item[b)] Wie viele Binärzahlen der Länge $n$ gibt es, die an genau $k$ Stellen eine 1 haben?

(Urne mit den Stellen $1,...,n$, ziehe $k$ Stellen (Anordnung egal), die mit 1 gelegt werden $\leadsto \binom{n}{k}$)

\end{itemize}


\subsection{Satz (Binomialsatz / binomischer Lehrsatz)} %7.17

$a,b \in \mathbb{R}, n \in \mathbb{N}_0$

$$(a+b)^n = \sum_{k=0}^n \binom{n}{k} \cdot a^{n-k} \cdot b^k$$
$$ = \underbrace{\binom{n}{0}}_{1} \cdot a^n \underbrace{b^0}_{1} + \binom{n}{1} a^{n-1} \cdot b^1 + \binom{n}{2} a^{n-1} b^2 + ... + \binom{n}{n-1} a^1 b^{n-1} + \binom{n}{n} \cdot a^0 \cdot b^n$$

$(a+b)^1 = a + b \\
(a+b)^2 = \uline{1}a^2 + \uline{2}ab + \uline{1}b^2 \\
(a+b)^3 = \uline{1}a^3 + \uline{3} \cdot a^2b + \uline{3}ab^2 + \uline{1} \cdot b^3$

Unterstrichene Zahlen: siehe Pascal'sches Dreieck (7.14)

\underline{Beweis:} mittels Induktion über $n$ und 7.14 b), siehe WHK 2.28

\subsection{Ungeordnete Anzahl mit Wiederholung} %7.18

%% TODO Zeichnung Urnenziehung

Wähle $k$ Objekte aus $n$ Objekten aus, Wiederholungen erlaubt, Reihenfolge nicht relevant. Wie viele verschiedene Korbfüllungen gibt es?

\subsection{Satz} %7.19

Die Anzahl der Möglichkeiten, aus $n$ Objekten $k$ Objekte auszuwählen, wenn Wiederholungne erlaubt sind und die Reihenfolge irrelevant ist, ist $\binom{n+k-1}{k}$.

\underline{Beweis:} Wir können $m_1$ mal das erste Objekt, $m_2$ mal das 2. Objekt, usw. ..., $m_n$ mal das $n$. Objekt wählen, wobei $m_1+m_2+...+m_n = k$ gelten muss.

Jede solche Wahl entspricht einer $(n+k-1)$-stelligen Binärzahl mit $k$ Einsen und $n-1$ Nullen:

$(\underbrace{1...1}_{m_1}\ \underbrace{0}_{\text{Trennzeichen}}\ \underbrace{1...1}_{m_2}\ 0\ ... \ 0\ \underbrace{1...1}_{m_n})$

Wie viele Binärzahlen dieser Art ($k$ mal $1$, $n-1$ mal $0$) gibt es?

vgl. Beispiel 7.16 c) $\qquad \binom{n+k-1}{k}$

\subsection[Beispiel (IKEA)]{Beispiel} %7.20

IKEA hat 3 verschiedene Arten von Schrauben.

Wie viele Möglichkeiten gibt es, Päckchen aus 10 Schrauben zusammenzustellen?

%% TODO Zeichnung Urne

$$\binom{3+10-1}{10}$$

% ============
% 1 Februar 2016
% ============

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Kapitel 8: Die reellen Zahlen
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Die reellen Zahlen} %8

Wir beschreiben die Menge $\mathbb{R}$ der reellen Zahlen durch ein Axiomensystem bestehend aus

\begin{itemize}

\item Körperaxiomen ($\Rightarrow$ Mathe III, algebraische Strukturen von $\mathbb{R}$, beschreiben die Grundrechenarten ($+, -, \cdot, \backslash$))

\item Anordnungsaxiomen

\item Vollständigkeitsaxiomen

\end{itemize}

Aus diesen kann jede Aussage über $\mathbb{R}$ abgeleitet werden.

\subsection{Anordnungsaxiome / Definition} %8.1

In $\mathbb{R}$ sind gewisse Zahlen $x$ als \underline{positiv} ausgezeichnet (kurz: $x > 0$), sodass gilt:

\begin{enumerate}

\item für jedes $x \in \mathbb{R}$ gilt genau eine der Aussagen $x = 0, x > 0, -x > 0$.

\item $x > 0, \quad y > 0 \quad \Rightarrow x + y > 0$

\item $x > 0, \quad y > 0 \quad \Rightarrow x \cdot y > 0$

\end{enumerate}

Um Elemente aus $\mathbb{R}$ miteinander vergleichen zu können, schreiben wir:

$x > y: \Leftrightarrow x - y > 0$ \\
$x \geq y: \Leftrightarrow x - y > 0$ \\
oder $x = y$

Für $x > y$ schreiben wir auch $y \underbrace{<}_{(\leq)} x$ \\
Gilt $x < 0$, so heißt $x$ \underline{negativ}.

Einfache Folgerungen aus 8.1 und den bekannten Rechenregeln (für Addition, Subtraktion, Multiplikation und Division) in $\mathbb{R}$: (ohne Beweis)

\subsection{Satz} %8.2
Seien $x, y, z, a, b \in \mathbb{R}$. Dann gilt:

\begin{itemize}

\item[a)] Es gilt genau eine der Aussagen \\
$x = y, \quad x < y, \quad x > y$ (Trichotomiegesetz)

\item[b)] $x < y$ und $y < z \Rightarrow x < z$ (Transitivität)

\item[c)] $x < y \Rightarrow x + a < y + a$ \\
$x < y, a \leq b \Rightarrow x + a < y + b$ (Monotonie der Addition)

\item[d)] $x < y, a > 0 \Rightarrow a \cdot x < a \cdot y$ \\
$x < y, a < 0 \Rightarrow a \cdot x > a \cdot y$ (Monotonie der Multiplikation)

\item[e)] $x, y > 0 \Rightarrow x + y > 0$ und $x \cdot y > 0$ \\
$x > 0, y < 0 \Rightarrow x \cdot y < 0$ \\
$x, y < 0 \Rightarrow x + y < 0$ und $x \cdot y > 0$

insbesondere ist $x^2 \geq 0 \forall x \in \mathbb{R}$ \\
$(x^2 > 0$ für $x \neq 0)$

\item[f)] $0 < x < y \Rightarrow 0 < \frac{1}{y} < \frac{1}{x}$

\end{itemize}

Auf diesen Regeln beruhen die bekannten Rechenregeln für Ungleichungen, z.B. für welche $x \in \mathbb{R}$ ist
$x - 1 \leq -2x + 8$?

$x - 1 \leq -2x + 8 \Leftrightarrow$ 8.2c) (addiere 1, addiere 2x)

$3x \leq 9 \underbrace{\Leftrightarrow}_{8.2d) (\text{mult. mit} \frac{1}{3})} x \leq 3$

\subsection{Definition (Intervalle)} %8.3

Seien $a, b \in \mathbb{R}, a < b$ endliche Intervalle:

$(a, b) := \{x \in \mathbb{R} \mid a < x < b\}$ offenes Intervall (mit Endpunkten $a, b$)

(auch Schreibweise $]a, b[$ üblich)

$[a, b] := \{x \in \mathbb{R} \mid a \leq x \leq b \}$ abgeschlossenes Intervall

$(a, b] := \{x \in \mathbb{R} \mid a < x \leq b \}$ halboffenenes Intervall

Unendliche Intervalle: \\
$[a, \infty) := \{x \in \mathbb{R} \mid a \leq x$ oder $x \geq a \}$

$(-\infty, \infty) := \mathbb{R}$

Entsprechend: $[a, b), (-\infty, a]$, \\
$(a, \infty), (-\infty, a)$

weitere übliche Schreibweisen:

$\mathbb{R}^- := (-\infty, 0), \mathbb{R}^{}_{0} := (-\infty, 0]$

$\mathbb{R}^+ := (0, \infty), \mathbb{R}^{+}_{0} := [0, \infty)$

\subsection{Beispiele (Ungleichungen, Intervalle)} %8.4

Für welche $x \in \mathbb{R}$ ist $\frac{1}{x-2} \leq \frac{2}{x+3}$? (*)

\underline{1. Fall:} \\
$x + 3 < 0$, \\
d.h. $x < -3$ \\
$\Rightarrow x -2 < -5 < 0$ \\
dann ist (*) \\
$\Leftrightarrow x + 3 \leq 2 (x-2) = 2x-4$ \\
$\Leftrightarrow x \geq 7$, \\
nicht möglich, $L_1 = \emptyset$

\underline{2. Fall:} \\
$x + 3 > 0, x - 2 < 0$, d.h. $-3 < x < 2$ \\
dann ist (*) \\
$\Leftrightarrow x + 3 \geq 2(x-2) = 2x -4$ \\
$\Leftrightarrow x \leq 7$

$\Rightarrow L_2 = (-3, 2)$

\underline{3.Fall:} \\
$x + 3, x - 2 > 0$, d.h. $x > 2$ \\
dann (*) \\
$\Leftrightarrow x \leq 7$
$\Rightarrow L_3 = [7, \infty)$

Lösungsmenge von (*) ist \\
$L = L_1 \cup L_2 \cup L_3 =$ \\
$(-3, 2) \cup [7, \infty)$

\subsection{Wiederholung (Betrag)} %8.5
Für $x \in \mathbb{R}$ ist $|x| = $ max $\{x, -x\}$ \\
\[ =
  \begin{cases}
    x, & x \geq 0 \\
   - x, & x < 0 \\
  \end{cases}
\]

$|x|$ entspricht dem Abstand von $x$ zu $0$.

Für $x, y \in \mathbb{R}$ ist $|x - y|$ der Abstand zwischen $x$ und $y$.

\subsection{Satz (Rechenregeln für den Betrag)}

\begin{itemize}

\item[a)] $|x| \geq x$ und $|x| \geq -x$

\item[b)] $|x| = |-x| \geq 0$, \\
$|x| = 0 \Leftrightarrow x = 0$

\item[c)] $|x \cdot y| = |x| \cdot |y|$

\item[d)] $|x+y| \leq |x| + |y|$ (Dreiecksungleichung)

\end{itemize}

Beweis: a) - c) einfache Ü

zu d) \\
Nach a) gilt $-x \leq |x|, -y \leq |y|$

$\underbrace{\Rightarrow}_{8.2c)} -x -y \leq |x| + |y|$

ebenso $x \leq |x|, \quad y \leq |y|$ \\
$x+y \leq |x| + |y|$

%Geschweifte Klammer bei den Beiden führt zu:

$|x + y| \leq |x| + |y|$ \hfill $\square$

\subsection{Rechnen mit Betrag} %8.7

für welche $x \in \mathbb{R}$ gilt $|x+1| \leq |x-2|$?

% ============
% 3 Februar 2016
% ============

Wichtige Stellen: $-1, 2$ %TODO: Zahlenstrahl mit Pfeil auf -1 und 2, nice to have

\underline{1.Fall:}

$x \leq -1$: \\
dann ist $|\underbrace{x+1}_{< 0}| = -x + 1 = -x - 1$ \\
und $ |\underbrace{x-2}_{< 0}| = -(x-2) = -x + 2$

also $-x -1 \leq -x + 2$ \\
$\Rightarrow -1 \leq 2$, \\
gilt für alle $x$.

\underline{2.Fall:}

$x \geq 2$: \\
dann $|\underbrace{x+1}_{> 0}| = x+1$ \\
$|\underbrace{x-2}_{\geq 0}| = x-2$,

also $x + 1 \leq x - 2$ \\
$\Leftrightarrow 1 \leq -2$ \\
gilt für kein $x$.

\underline{3.Fall:}

$-1 < x < 2$, \\
dann $|\underbrace{x+1}_{> 0}| = x + 1$ \\
$|\underbrace{x-2}_{< 0}| = -(x-2)$

also $x+1 \leq -x + 2$ \\
$\Leftrightarrow x \leq \frac{1}{2}$

Insgesamt: $|x + 1| \leq |x-2|$ \\
gilt für alle $x \leq \frac{1}{2}$


\subsection{Definition (obere und untere Schranken)} %8.8

Sei $A \subseteq \mathbb{R}, A \neq \emptyset$.

$A$ heißt \uline{nach oben beschränkt}, wenn es ein Element $S \in \mathbb{R}$ gibt mit $a \leq S \  \forall a \in A$.

$A$ heißt \uline{nach unten beschränkt}, wenn es ein Element $s \in \mathbb{R}$ gibt mit $a \geq s \  \forall a \in A$.

$S$ heißt dann \uline{obere Schranke}, $s$ \uline{untere Schranke}.

Ist $A$ sowohl nach oben als auch nach unten beschränkt, so heißt $A$ \uline{beschränkt}.

(d.h. $\exists s,S \in \mathbb{R}$ mit $s \leq a \leq S \ \forall a \in A$).

\subsection{Beispiel} %8.9

\begin{itemize}
\item[a)] $\mathbb{N}$ nach unten beschränkt, z.B. durch $-3$ oder $-\frac{1}{2}$ oder $0$ oder $1$

\item[b)] $\mathbb{Z}$ weder nach oben noch nach unten 

\item[c)] $(-10,2)$ oder $[3,12)$ beschränkt
\end{itemize}

\subsection{Bemerkung} %8.10

$S,s$ aus 8.8 sind nicht eindeutig.

Ist $A$ nach oben (unten) beschränkt, gibt es unendlich viele obere (untere) Schranken.

Welche ist die ""beste""?

Das führt zu folgender Definition.

\subsection{Definition (Supremum und Infimum)} %8.11

Sei $\emptyset \neq A \subseteq \mathbb{R}$.

Die Zahl $S_0 \in \mathbb{R}$ heißt \uline{kleinste obere Schranke} oder \uline{Supremum} von $A$ ($S_0 = sup(A)$), wenn sie eine obere Schranke ist und es keine kleinere Schranke von $A$ gibt.

(d.h. $S_0 \leq S$ für jede obere Schranke $S$ von $A$)

$s_0 \in \mathbb{R}$ heißt \uline{größte untere Schranke} oder \uline{Infimum} von $A$ ($s_0 = inf(A)$), wenn sie eine untere Schranke ist und es keine größere Schranke von $A$ gibt.

(d.h. $s_o \geq s \forall$ untere Schranke $s$ von $A$)

\subsection{Beispiel} %8.12

$A := \{a \in \mathbb{R} \mid 0 < a \leq 1\} = (0,1]$ ist beschränkt.

$sup(A) = 1$ \\
$inf(A) = 0$

klar: $0$ ist untere Schranke. Wieso ist $0$ \underline{größte}?

Angenommen, $s > 0$ sei eine untere Schranke, also $s \leq a \ \forall a \in A$.

Dann ist aber $\frac{s}{2} < s$, aber $\frac{s}{2} \in A$, also war $s$ nicht $\leq a$ für \uline{alle} $a \in A$.

$\Rightarrow s$ ist keine untere Schranke.

$\Rightarrow s_0 = 0$ ist größte untere Schranke.

\subsection{Definition (Maximum/Minimum)} %8.13

$\emptyset \neq A \subseteq \mathbb{R}$

Gilt $M = sup(A)$ und $M \in A$, so heißt $M$ \uline{Maximum} von $A$ ($max(A)$).

Gilt $m = inf(A)$ und $m \in A$, so heißt $m$ \uline{Minimum} von $A$ ($min(A)$).

Man sagt: Supremum/Infimum ""werden angenommen"" (sind Element der Menge $A$).

\subsection{Bemerkung} %8.14

Ist $A = \{a_1,...,a_n\}$ endlich, so existieren $min(A)$ und $max(A)$.

\subsection{Beispiel} %8.15

\begin{itemize}
\item[a)]

$A = (0,1]$ (Beispiel 8.12)

$sup(A) = 1 = max(A)$

$inf(A) = 0$, $min(A)$ existiert nicht

% ============
% 10 Februar 2016
% ============

\item[b)]

$A = \{\frac{1}{n} \mid mn \in \mathbb{N}\}$

beschränkt $(0 < \frac{1}{n} \leq 1)$

$\sup A = 1 = \max A$

$\inf A = 0 \notin A$

\end{itemize}

\subsection{Vollständigkeitsaxiom} %8.16
Ist $\emptyset \neq A \subseteq \mathbb{R}$, und ist $A$ nach oben (unten) beschränkt,
so existiert $\sup A (\inf A)$.
(Jede nichtleere, nach oben beschränkte Menge $A \subseteq \mathbb{R}$ besitzt ein Supremum.)

\subsection{Bemerkung / Beispiel} %8.17
Für $\mathbb{Q}$ gilt 8.16 \underline{nicht}.

$A := \{x \in \mathbb{Q} \mid x > 0$ und $x^2 < 2\} \subseteq \mathbb{Q}$

besitzt \underline{kein} Supremum in $\mathbb{Q}$

Man sagt: $\mathbb{Q}$ ist \underline{nicht vollständig}.

In $\mathbb{R}$ besitzt die Menge $A$ das Supremum $\sup A = \sqrt{2}$ ($\rightarrow$ siehe 8.18),
aber $\sqrt{2} \notin \mathbb{Q}$, vgl. Beispiel in 3.3.

\subsection{Satz} %8.18
Sei $a \in \mathbb{R}_{0}^{+}$.

Dann $\underbrace{\exists ! }_{\text{es existiert genau ein}} x \in \mathbb{R}_{0}^{+}$ mit $x^2 = q$.

Diese Zahl $x$ heißt die \underline{Wurzel von $a$} und wird mit $\sqrt{a}$ bezeichnet.

(Allgemein: Ist $n \in \mathbb{N}$, so hat die Gleichung $x^n = q$ eine eindeutige bestimmte nicht negative Lösung, diese wird als n-te Wurzel $\sqrt[n]{a}$ bezeichnet.)

\underline{Beweisskizze:}

\begin{itemize}

\item $\underline{a = 0}: 0 \cdot 0 = 0$ \checkmark

\item $\underline{a > 0}:$ dann ist $x$, fall ex., $> 0$. \\
def. $M := \{ x \in \mathbb{R}^{+} \mid x^2 \leq a\}$

Zeige: $M$ ist nach oben beschränkt.

$\underbrace{\Rightarrow}_{8.16} s := \sup M$ existiert,

Zeige: $s$ ist gesuchte Lösung, d.h. $s^2 = a$. \hfill $\square$

\end{itemize}

\subsection{Approximation von $\sqrt{2}$, Bisektionsverfahren} %8.19

Siehe Folien.

\subsection{Satz: Prinzip des Archimedes}

Sei $x \in \mathbb{R}$. Dann $\exists n \in \mathbb{N}$ mit $n > x$.

\underline{Beweis:}

Angenommen, $\exists x_0 \in \mathbb{R}$, so dass $x_0 \geq n \forall n \in \mathbb{R}$

$\Rightarrow \mathbb{R}$ nach oben beschränkt.

$\underbrace{\Rightarrow}_{8.16} s := \sup (\mathbb{N})$ existiert (und ist \underline{kleinste} obere Schranke von $\mathbb{N}$)

$\Rightarrow s-1$ ist keine obere Schranke mehr

$\Rightarrow \exists n_0 \in \mathbb{N}$ mit $s-1 < n_0$

$\Rightarrow \mathbb{N} \ni n_0 + 1 > s$ \mbox{\Lightning} zur Supremums-Eigenschaft. \hfill $\square$

\subsection{Korollar} %8.21
Sei $\varepsilon > 0 \in \mathbb{R}$.

Dann $\exists n \in \mathbb{N}$ mit $\frac{1}{n} < \varepsilon$.

\underline{Beweis:}

Zu der reellen Zahl $\frac{1}{\varepsilon}$ gibt es nach 8.20 ein $n \in \mathbb{N}$ mit $n > \frac{1}{\varepsilon}$.

Da $\varepsilon > 0$, folgt $\frac{1}{n} < \varepsilon$

\subsection{Korollar (klassische Schlussweise der Analysis)} %8.22
Ist $0 \leq x < \frac{1}{n} \quad \forall n \in \mathbb{N}$, so gilt $x = 0$.

\underline{Beweis:}

Angenommen, $x > 0$.

$\Rightarrow n \cdot x < 1 \quad \forall n \in \mathbb{N}, $ \mbox{\Lightning} zu 8.21. \hfill $\square$

\end{document}