Kurs:Mathematik für Elektrotechnik/Grundlagen

Axiomatische Methode

Wikipedia

Wikipedia: Axiom – Artikel in der Wikipedia

In der Mathematik werden grundlegende Sätze, die Axiome, definiert. Axiome sind atomar und können nicht auf grundlegendere Sätze zurückgeführt werden. Das logische Schließen von Axiomen auf eine Aussage wird als axiomatische Methode oder deduktive Methode bezeichnet. Diese Methode ist die Grundlage der gesamten Mathematik.

Die Methode geht vermutlich auf den griechischen Mathematiker Eudoxos von Knidos zurück und findet sich in den „Elementen“ des Euklid von Alexandria, welche etwa um 300 vor Christus verfasst wurden. Seitdem wurde die axiomatische Methode die Grundlage der exakten Wissenschaften. In Philosophiae Naturalis Principia Mathematica (Mathematische Prinzipien der Naturlehre) von 1686 hat Isaac Newton die Mechanik aus nur drei axiomatischen Gesetzen entwickelt.

Baruch de Spinoza verfasste das Werk Ethica, Ordine Geometrico Demonstrata, welches nach geometrischen (dh. deduktiven) Grundlagen geschrieben ist. David Hilbert vertrat zudem die Meinung, dass jede reife Wissenschaft der Axiomatisierung (dh. der Zerlegung ihrer Theorien und Sätze in Axiome) unterliegt.

Axiomatische Definition der natürlichen Zahlen

Der italienische Mathematiker Giuseppe Peano hat für die natürlichen Zahlen ein System von fünf Axiomen vorgeschlagen:

Definition:

Die Menge der natürlichen Zahlen ${}_{\mathbb {N} }$ hat folgende Eigenschaften:

1 ist eine natürliche Zahl.
$1\in \mathbb {N}$
Jeder natürlichen Zahl ${}_{n}$ ist eine andere natürliche Zahl ${}_{n'}$ zugeordnet, welche als Nachfolger von ${}_{n}$ bezeichnet wird.
1 ist kein Nachfolger.
Sind zwei natürliche Zahlen ${}_{m,n}$ verschieden, so sind auch deren Nachfolger ${}_{m',n'}$ verschieden.
$n\neq m\Rightarrow n'\neq m'$
Eine Eigenschaft, die für die sowohl für die Zahl 1, als auch eine natürliche Zahl n und deren Nachfolger ${}_{n'}$ gilt, gilt für alle natürlichen Zahlen. (Induktionsaxiom)

In der modernen Definition der natürlichen Zahlen wird anstatt der Zahl 1 mit der Zahl 0 begonnen. Die entsprechenden Axiome werden analog definiert.

siehe auch: Peano-Axiome

Ausgehend von den Peano`schen Axiomen, welche die natürlichen Zahlen definieren, werden die Operationen für die Addition, die Multiplikation, sowie die Vergleichsoperatoren (Relationen) <, >, ≤, und ≥ eingeführt.

Beispielsweise sei hier die rekursive Definition der Addition dargestellt:

Definition:

Für alle ${}_{n,k\in \mathbb {N} }$ wird ${}_{n+k}$ definiert. Dies geschieht rekursiv über eine vollständige Induktion:

$n+1:=n'$
$n+k':=(n+k)'$

Hier sei noch erwähnt, dass für die Definition der ganzen Zahlen, der rationalen Zahlen, sowie der irrationalen Zahlen keine weiteren Axiome benötigt werden. Stattdessen werden diese Zahlenmengen über entsprechende Definitionen auf der Basis der natürlichen Zahlen definiert.

Zahlenmengen

Wikipedia

Wikipedia: Zahlenmenge – Artikel in der Wikipedia

Eine Zahlenmenge ist eine genau definierte Menge von Zahlen. Die wichtigsten Zahlenmengen sind die natürlichen Zahlen ${}_{\mathbb {N} }$ , die ganzen Zahlen ${}_{\mathbb {Z} }$ , die rationale Zahlen ${}_{\mathbb {Q} }$ , die reellen Zahlen ${}_{\mathbb {R} }$ und die komplexen Zahlen ${}_{\mathbb {C} }$ . Jede dieser genannten Zahlenmengen ist eine Obermenge der jeweils zuvor genannten Zahlenmengen:

\mathbb {N} \subset \mathbb {\mathbb {Z} } \subset \mathbb {Q} \subset \mathbb {R} \subset \mathbb {C}

Natürliche Zahlen

Wikipedia

Wikipedia: Natürliche Zahlen – Artikel in der Wikipedia

Die natürlichen Zahlen werden wie zuvor gezeigt durch die Peano-Axiome definiert. Abhängig von der verwendenten Definition kann die Null Bestandteil der Menge der natürlichen Zahlen sein. Dies kann durch den Index oder eine explizite Zuweisung gekennzeichnet werden.

Definition:

$\mathbb {N} =\left\{1,2,3,\ldots \right\}$

$\mathbb {N} _{0}=\left\{0,1,2,3,\ldots \right\}=\mathbb {N} \cup \left\{0\right\}$

Ganze Zahlen

Wikipedia

Wikipedia: Ganze Zahlen – Artikel in der Wikipedia

Die ganzen Zahlen sind die Menge der natürlichen Zahlen, der Null, sowie der Menge der negierten natürlichen Zahlen.

Definition:

$\mathbb {Z} =\left\{\ldots ,-3,-2,-1,0,1,2,3,\ldots \right\}=-\mathbb {N} \cup 0\cup \mathbb {N}$

Rationale Zahlen

Wikipedia

Wikipedia: Rationale Zahlen – Artikel in der Wikipedia

Die Menge der rationalen Zahlen ${}_{\mathbb {Q} }$ besteht aus der Menge aller Brüche von Elementen von ${}_{\mathbb {Z} }$ , wobei der Nenner nicht Null sein darf.

Definition:

$\mathbb {Q} =\left\{{\frac {p}{q}}\ :\ p,q\in \mathbb {Z} \land q\neq 0\right\}$

Der Bruch ${}_{\frac {p}{q}}$ kann reduziert werden. Die Definition bleibt eindeutig, wenn ${}_{p}$ und ${}_{q}$ immer teilerfremd sind. Zudem bleibt sie auch dann eindeutig wenn ${}_{p}$ oder ${}_{q}$ immer positiv ist.

Die Dezimaldarstellung einer rationalen Zahl hat entweder endlich viele Dezimalstellen oder unendlich viele Dezimalstellen, wobei sich ein Block, bestehend aus einer oder mehreren Ziffern, immer wiederholt (z. B. ${}_{{\frac {10}{3}}=}$ ${}_{3{,}333.333\ldots =}$ ${}_{3{,}{\overline {3}}}$ oder ${}_{{\frac {10}{44}}=}$ ${}_{0{,}227.272\ldots =}$ ${}_{0{,}2{\overline {27}}}$ ). Wenn sich ein Block von Ziffern immer wieder wiederholt spricht man von einer periodischen Dezimalzahl.

Reelle Zahlen

Wikipedia

Wikipedia: Reelle Zahlen – Artikel in der Wikipedia

Die Menge der reellen Zahlen besteht aus der Menge der rationalen Zahlen und den irrationalen Zahlen. Irrationale Zahlen sind unendliche, nichtperiodische Dezimalbrüche. Bei den irrationalen Zahlen unterscheidet man zwischen algebraisch irrationalen Zahlen und transzendeten Zahlen.

Definition:

Eine irrationale Zahl ${}_{x\in \mathbb {R} \setminus \mathbb {Q} }$ ist eine algebraisch irrationale Zahl, wenn ${}_{x}$ die Lösung einer algebraischen Gleichung der Form

a_{n}\,x^{n}+a_{n-1}\,x^{n-1}+\ldots +a_{2}\,x^{2}+a_{1}\,x+a_{0}=0

mit ganzzahligen Koeffizienten ${}_{\{a_{0},\ldots ,a_{n}\}\in \mathbb {Z} }$ und ${}_{n\in \mathbb {N} }$ ist.

Definition:

Eine irrationale Zahl ist eine transzendente Zahl, wenn sie irrational aber nicht algebraisch irrational ist.

Beispiele für transzendente Zahlen sind die Kreiszahl ${}_{\pi }$ und die Eulersche Zahl ${}_{e}$ .

siehe auch: Reelle Zahlen

Komplexe Zahlen

Wikipedia

Wikipedia: Komplexe Zahlen – Artikel in der Wikipedia

Die Menge der komplexen Zahlen ${}_{\mathbb {C} }$ besteht aus zwei reellen Zahlen, wobei eine davon mit der imaginären Einheit i multipliziert wird.

Definition:

$\mathbb {C} =\left\{x+i\,y\ :\ x,y\in \mathbb {R} \land \left(i^{2}=-1\right)\right\}$

Definition:

Bei einer komplexen Zahl ${}_{z\in \mathbb {C} }$ wird die mit ${}_{i}$ multiplizierte reelle Zahl als Imaginärteil ${}_{\mathrm {Im} (z)}$ und die andere reelle Zahl als Realteil ${}_{\mathrm {Re} (z)}$ bezeichnet.

Beispiel:

Eine komplexe Zahl ${}_{z}$ sei gegeben durch

z:=x+i\,y\quad x,y\in \mathbb {R}

so gilt

\mathrm {Im} (z)=y

und

\mathrm {Re} (z)=x

siehe auch: Komplexe Zahlen

Aussagenlogik und Beweise

Wikipedia

Wikipedia: Aussagenlogik – Artikel in der Wikipedia

Die Aussagenlogik ist ein wesentliches Werkzeug zum Aufbau mathematischer Theorien. Das Grundelement sind die Aussagen.

Definition:

Eine Aussage ist ein Satz, dem genau einer der Wahrheitswerte wahr (w) oder falsch (f) zugeordnet werden kann.

Da nur zwei Wahrheitswerte möglich sind spricht man auch von zweiwertiger Logik.

Durch Verknüpfungen von Aussagen können neue Aussagen gewonnen werden. Im Wesentlichen definiert man für zwei Aussagen ${}_{A,B}$ die Verknüpfungen

Negation (nicht A)
$\neg A$
Konjunktion (A und B)
$A\land B$
Disjunktion (A oder B [oder beide])
$A\lor B$
Implikation (A impliziert B; aus A folgt B [aber nicht umgekehrt])
$A\Rightarrow B$
Äquivalenz (A gilt genau dann wenn B gilt [und umgekehrt])
$A\Leftrightarrow B$

Diese Verknüpfungen werden über Wahrheitstafeln definiert:

$A$	$B$	$\neg A$	$A\land B$	$A\lor B$	$A\Rightarrow B$	$A\Leftrightarrow B$
$w$	$w$	$f$	$w$	$w$	$w$	$w$
$w$	$f$	$f$	$f$	$w$	$f$	$f$
$f$	$w$	$w$	$f$	$w$	$w$	$f$
$f$	$f$	$w$	$f$	$f$	$w$	$w$

Um eine übermäßige Klammerung zu vermeiden wird, vergleichbar mit der Definition „Punktrechnung vor Strichrechnung“, eine Reihenfolge bei der Auswertung definiert:

Definition:

Treten in einer Aussage mehrere logische Operationen auf, werden diese in der folgenden Reihenfolge ausgewertet:

Negation
Konjunktion
Disjunktion
Implikation
Äquivalenz

De Morgan`sche Regeln

Wikipedia

Wikipedia: De Morgansche Regeln – Artikel in der Wikipedia

Die De Morgan`schen Regeln sind zwei grundlegende Regeln für logische Aussagen. Sie sind über den folgenden Satz definiert:

Satz:

Seien ${}_{A,B}$ Aussagen, dann gilt:

$\neg (A\land B)\Leftrightarrow \neg A\lor \neg B$
$\neg (A\lor B)\Leftrightarrow \neg A\land \neg B$

Der Beweis erfolgt durch Auflisten aller Möglichkeiten und der Gegenüberstellung der Ergebnisse in einer Wahrheitstabelle.

Beweis:

$A$	$B$	$\neg A$	$\neg B$	$A\land B$	$\neg (A\land B)$	$\neg A\lor \neg B$	$A\lor B$	$\neg (A\lor B)$	$\neg A\land \neg B$
$w$	$w$	$f$	$f$	$w$	$f$	$f$	$w$	$f$	$f$
$w$	$f$	$f$	$w$	$f$	$w$	$w$	$w$	$f$	$f$
$f$	$w$	$w$	$f$	$f$	$w$	$w$	$w$	$f$	$f$
$f$	$f$	$w$	$w$	$f$	$w$	$w$	$f$	$w$	$w$

Beweisführung

Wikipedia

Wikipedia: Beweis – Artikel in der Wikipedia

Definition:

Liegt ein Satz der Form ${}_{A\Rightarrow B}$ vor, wird ${}_{A}$ wahr angenommen. Kann man daraus durch auf die Wahrheit von ${}_{B}$ schließen, so ist die Aussage bewiesen. Diese Vorgehensweise wird als direkter Beweis bezeichnet.

Satz:

Für beliebige Aussagen ${}_{A,B}$ gilt der Zusammenhang

(A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)

Beweis:

$A$	$B$	$\neg A$	$\neg B$	$A\Rightarrow B$	$\neg B\Rightarrow \neg A$	$(A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)$
$w$	$w$	$f$	$f$	$w$	$w$	$w$
$w$	$f$	$f$	$w$	$f$	$f$	$w$
$f$	$w$	$w$	$f$	$w$	$w$	$w$
$f$	$f$	$w$	$w$	$w$	$w$	$w$

Definition:

Liegt ein Satz der Form ${}_{A\Rightarrow B}$ vor, so wird ${}_{B}$ falsch angenommen. Kann man daraus durch auf die Falschheit von ${}_{A}$ schließen, so ist die Aussage bewiesen. Diese Vorgehensweise wird als indirekter Beweis bezeichnet.

vollständige Induktion

Wikipedia

Wikipedia: vollständige Induktion – Artikel in der Wikipedia

Um eine Aussage ${}_{A(n)}$ für alle ${}_{n\geq n_{0}}$ mit ${}_{n,n_{0}\in \mathbb {N} }$ zu beweisen, benötigt man die vollständige Induktion. Diese setzt sich zusammen aus dem Induktionsanfang und dem Induktionsschluss. Beim Induktionsanfang wird hierbei die Aussage ${}_{A(n_{0})}$ bewiesen. Beim Induktionsschluss wird bewiesen, dass aus der Wahrheit von ${}_{A(n)}$ die Wahrheit von ${}_{A(n+1)}$ folgt.

Quantoren

Wikipedia

Wikipedia: Quantor – Artikel in der Wikipedia

Sätze in der Form einer Aussage in denen Variable auftreten, welche für die Objekte der entsprechenden mathematischen Theorie stehen, werden Aussageformen bezeichnet. Um aus Aussageformen konkrete Aussagen zu erhalten, werden Quantoren verwendet. Von besonderer Wichtigkeit sind hierbei der Allquantor ${}_{\forall }$ (für alle) und er Existenzquantor ${}_{\exists }$ (es gibt; es existiert).

Wenn mehrere Variable auftreten, wird jede Variable mit einem Quantor versehen. Um die Bedeutung der Aussage zu behalten, muss die Reihenfolge in der diese Variablen definiert werden beachtet werden.

Beispiel:

${}_{\forall Mensch\ :\ \exists Herz\ :\ hat(Mensch,Herz)}$	${}_{\nLeftrightarrow }$	${}_{\exists Herz\ :\ \forall Mensch\ :\ hat(Mensch,Herz)}$
Jeder Mensch hat ein Herz	${}_{\nLeftrightarrow }$	Es gibt ein Herz, welches alle Menschen haben

Bei der Negation einer Aussage müssen Allquantoren durch Existenzquantoren ersetzt werden, während Existenzquantoren durch Allquantoren ersetzt werden. Die Eigenschaft, welche die Aussage begründet, muss negiert werden.

Beispiel:

${}_{\neg (\forall Mensch\ :\ \exists Herz\ :\ hat(Mensch,Herz))}$	${}_{\Leftrightarrow }$	${}_{(\exists Mensch\ :\ \forall Herz\ :\ \neg hat(Mensch,Herz))}$
Nicht alle Menschen haben ein Herz.	${}_{\Leftrightarrow }$	Es gibt einen Menschen, der kein Herz hat.

Summen- und Produktezeichen

Die grundlegenden Rechenoperationen für alle Zahlen ${}_{a,b\in \mathbb {C} }$ , sowie alle Zahlen welche in einer Untermenge von ${}_{\mathbb {C} }$ enthalten sind, stellen die Addition ${}_{a+b}$ und die Multiplikation ${}_{a\,b}$ dar. Für Summen bzw. Produkte mit vielen Elementen wird mit dem Summenzeichen bzw. dem Produktzeichen eine Kurzschreibweise definiert.

Definition:

Das Summenzeichen wird definiert über

\sum _{k=m}^{n}{a_{k}}:=a_{m}+a_{m+1}+\ldots +a_{n-1}+a_{n}

mit ${}_{m,n\in \mathbb {N} }$ und ${}_{1\leq m\leq n}$ .

Satz:

Für das Summenzeichen gelten die folgenden Rechenregeln:

$\sum _{k=m}^{n+1}a_{k}$	$=$	$\sum _{k=m}^{n}a_{k}+a_{n+1}$
$\sum _{k=m}^{n}a_{k}\pm \sum _{k=m}^{n}b_{k}$	$=$	$\sum _{k=m}^{n}(a_{k}\pm b_{k})$
$s\,\sum _{k=m}^{n}a_{k}$	$=$	$\sum _{k=m}^{n}(s\,a_{k})$

Beweis: TODO

Satz:

Die geometrische Summenformel ist für alle reellen Zahlen ${}_{q\in \mathbb {R} \setminus 1}$ und alle ${}_{n\in \mathbb {N} }$ wie folgt definiert:

\sum \limits _{k=0}^{n}q^{k}={\frac {1-q^{n+1}}{1-q}}

Beweis:

Induktionsanfang mit ${}_{n=1}$ :
$\sum \limits _{k=0}^{1}q^{k}=1+q=(1+q)\,{\frac {1-q}{1-q}}={\frac {1-q^{2}}{1-q}}$
Induktionsschluss
1. Es wird angenommen, dass die geometrische Summenformel gilt:
  $\sum \limits _{k=0}^{n}q^{k}={\frac {1-q^{n+1}}{1-q}}\Leftrightarrow w$
2. Daraus folgt:
  $\sum \limits _{k=0}^{n+1}q^{k}=\sum \limits _{k=0}^{n}q^{k}+q^{n+1}={\frac {1-q^{n+1}}{1-q}}+q^{n+1}={\frac {1-q^{n+1}+q^{n+1}\,(1-q)}{1-q}}={\frac {1-q^{n+2}}{1-q}}$

Definition:

Das Produktzeichen wird definiert über

\prod _{k=m}^{n}{a_{k}}:=a_{m}\,a_{m+1}\,\ldots \,a_{n-1}\,a_{n}

mit ${}_{m,n\in \mathbb {N} }$ und ${}_{1\leq m\leq n}$ .

rekursive Definition

Wikipedia

Wikipedia: rekursive Definition – Artikel in der Wikipedia

Für Definitionen von Funktionen über alle natürlichen Zahlen wird die vollständige Induktion angewandt.

Potenz

Definition:

Die Potenz einer reellen Zahl ${}_{x\in \mathbb {R} }$ (n-te Potenz) mit einer natürlichen Zahl ${}_{n\in \mathbb {N} }$ ist definiert durch

x^{n}=\prod \limits _{1}^{n}x=x\,x\,\ldots \,x

Rekursiv wird dies definiert als:

$x^{1}:=x$
$x^{n+1}:=x\,x^{n}$

Falkultät

Definition:

Die Fakultät ${}_{n!}$ (n-Falkultät; n-Faktorielle) einer natürlichen Zahl ${n\in \mathbb {N} _{0}}$ ist rekursiv definiert durch

$0!:=1$
$1!:=1$
$(n+1)!:=n!\,(n+1)$ oder $n!:=n\,(n-1)!$

Binomialkoeffizienten

Wikipedia

Wikipedia: Binomialkoeffizient – Artikel in der Wikipedia

Definition:

Der Binomialkoeffizient ${}_{\binom {n}{k}}$ ist für ${}_{n.k\in \mathbb {N} _{0}}$ und ${}_{k\leq n}$ definiert durch

{\binom {n}{k}}:={\frac {n!}{k!\,\left(n-k\right)!}}

Ausgeschrieben gilt somit der Zusammenhang

{\binom {n}{k}}={\frac {(n-1+1)\,(n-2+1)\,\ldots \,(n-k+1)}{1\cdot 2\cdot \ldots \cdot k}}={\frac {n\,(n-1)\,\ldots \,(n-k+1)}{1\cdot 2\cdot \ldots \cdot k}}

Satz:

Für Binomialkoeffizienten gelten die folgenden Eigenschaften:

${\binom {n}{k}}={\binom {n}{n-k}}$
${\binom {n}{0}}={\binom {n}{n}}=1$
${\binom {n}{1}}={\binom {n}{n-1}}=n$

Diese Eigenschaften werden ua. dazu benötigt um bei einer numerischen Berechnung möglichst wenige Multiplikationen durchführen zu müssen.

Beweis: TODO

Satz:

Das Additionstheorem für Binomialkoeffizienten gilt für ${}_{n,k\in \mathbb {N} }$ und ${}_{1\leq k\leq n}$ mit

{\binom {n}{k-1}}+{\binom {n}{k}}={\binom {n+1}{k}}

Beweis:

${\binom {n}{k-1}}+{\binom {n}{k}}=$ ${\frac {n!}{(k-1)!\,(n-k+1)!}}+{\frac {n!}{k!\,(n-k)!}}=$ ${\frac {n!\,k+n!\,(n-k+1)}{k!\,(n-k+1)!}}=$ ${\frac {n!\,(n+1)}{k!(n-k+1)!}}=$ ${\frac {(n+1)!}{k!\,(n+1-k)!}}=$ ${\binom {n+1}{k}}$

Pascal`sches Dreieck

Beim Pascal'schen Dreieck wird jeder Koeffizient durch die Summe, gemäß dem Additionstheorem für Binominalkoeffizienten, der beiden darüberliegenden Koeffizient gebildet:

{\binom {0}{0}}

{\binom {1}{0}}

{\binom {1}{1}}

{\binom {2}{0}}

{\binom {2}{1}}

{\binom {2}{2}}

{\binom {3}{0}}

{\binom {3}{1}}

{\binom {3}{2}}

{\binom {3}{3}}

{\binom {4}{0}}

{\binom {4}{1}}

{\binom {4}{2}}

{\binom {4}{3}}

{\binom {4}{4}}

{\binom {5}{0}}

{\binom {5}{1}}

{\binom {5}{2}}

{\binom {5}{3}}

{\binom {5}{4}}

{\binom {5}{5}}

{\binom {6}{0}}

{\binom {6}{1}}

{\binom {6}{2}}

{\binom {6}{3}}

{\binom {6}{4}}

{\binom {6}{5}}

{\binom {6}{6}}

{\binom {7}{0}}

{\binom {7}{1}}

{\binom {7}{2}}

{\binom {7}{3}}

{\binom {7}{4}}

{\binom {7}{5}}

{\binom {7}{6}}

{\binom {7}{7}}

{\binom {8}{0}}

{\binom {8}{1}}

{\binom {8}{2}}

{\binom {8}{3}}

{\binom {8}{4}}

{\binom {8}{5}}

{\binom {8}{6}}

{\binom {8}{7}}

{\binom {8}{8}}

\vdots

\vdots

\vdots

\vdots

\vdots

\vdots

\vdots

\vdots

\vdots

\vdots

In Zahlen erhält man:

									$1$
								$1$		$1$
							$1$		$2$		$1$
						$1$		$3$		$3$		$1$
					$1$		$4$		$6$		$4$		$1$
				$1$		$5$		$10$		$10$		$5$		$1$
			$1$		$6$		$15$		$20$		$15$		$6$		$1$
		$1$		$7$		$21$		$35$		$35$		$21$		$7$		$1$
	$1$		$8$		$28$		$56$		$70$		$56$		$28$		$8$		$1$
$\vdots$		$\vdots$		$\vdots$		$\vdots$		$\vdots$		$\vdots$		$\vdots$		$\vdots$		$\vdots$		$\vdots$

Die Binominalkoeffizienten sind die Koeffizienten in der Entwicklung einer Gleichung der Form $(x+y)^{n}$ . Dies wird durch den Binomschen Lehrsatz ausgedrückt.

Binomischer Lehrsatz

Satz:

Für den Binomischen Lehrsatz gilt für alle ${}_{x,y\in \mathbb {R} }$ mit ${}_{n\in \mathbb {N} }$ der Zusammenhang

(x+y)^{n}=\sum \limits _{k=0}^{n}{\binom {n}{k}}\,x^{n-k}\,y^{k}

Beweis:

Der Binomische Lehrsatz wird mittels vollständiger Induktion für alle ${}_{n\in \mathbb {N} }$ bewiesen.

Induktionsanfang
$\sum \limits _{k=0}^{1}{\binom {1}{k}}\,x^{1-k}y^{k}={\binom {1}{0}}\,x^{1}\,y^{0}+{\binom {1}{1}}\,x^{0}\,y^{1}=(x+y)^{1}$
Induktionsschluss
1. Es wird angenommen, dass die Gleichung ${}_{(x+y)^{n}=\sum \limits _{k=0}^{n}{\binom {n}{k}}\,x^{n-k}\,y^{k}}$ gilt.
2. Durch Multiplizieren dieser Gleichung mit ${}_{x+y}$ erhält man:
  $(x+y)^{n+1}=$
  $\sum \limits _{k=0}^{n}{\binom {n}{k}}\,x^{n-k+1}\,y^{k}+\sum \limits _{k=0}^{n}{\binom {n}{k}}\,x^{n-k}\,y^{k+1}=$
  
  $\sum \limits _{k=0}^{n}{\binom {n}{k}}\,x^{n-k+1}\,y^{k}+\sum \limits _{k=1}^{n+1}{\binom {n}{k-1}}\,x^{n-k+1}\,y^{k}=$
  
  ${\binom {n}{0}}\,x^{n+1}\,y^{0}+\sum \limits _{k=1}^{n}{\binom {n}{k}}\,x^{n-k+1}\,y^{k}+\sum \limits _{k=1}^{n}{\binom {n}{k-1}}\,x^{n-k+1}\,y^{k}+{\binom {n}{n}}\,x^{0}\,y^{n+1}=$
  
  $x^{n+1}+\sum \limits _{k=1}^{n}\left[{\binom {n}{k}}+{\binom {n}{k-1}}\right]\,x^{n-k+1}\,y^{k}+y^{n+1}=$
  
  $x^{n+1}+\sum \limits _{k=1}^{n}{\binom {n+1}{k}}\,x^{n-k+1}\,y^{k}+y^{n+1}=$
  
  ${\binom {n+1}{0}}\,x^{n+1}y^{0}+\sum \limits _{k=1}^{n}{\binom {n+1}{k}}\,x^{n-k+1}\,y^{k}+{\binom {n+1}{n+1}}\,x^{0}\,y^{n+1}=$
  
  $\sum \limits _{k=0}^{n+1}{\binom {n+1}{k}}\,x^{n-k+1}\,y^{k}$

Beispiel:

Gesucht sei der 4. Koeffizient der Gleichung ${}_{(x+y)^{7}}$ . Aus dem Binomischen Lehrsatz erhält man

{\binom {n}{k}}\,x^{n-k}\,y^{k}={\binom {7}{4}}\,x^{7-4}\,y^{4}=35\,x^{3}\,y^{4}

Mengen

Definition:

Eine Menge gemäß Cantor ist eine Zusammenfassung unterscheidbarer Objekten zu einem Ganzen. Die Objekte, welche zu einer Menge zusammengefasst sind, werden als Elemente dieser Menge bezeichnet. Wenn ${}_{x}$ ein Element der Menge ${}_{M}$ ist, schreibt man ${}_{x\in M}$ , andernfalls ${}_{x\notin M}$ .

Definition:

Die Menge ohne Elemente wird als leere Menge ${}_{\emptyset }$ bezeichnet.

Definition:

Eine Menge ${}_{A}$ wird als Teilmenge einer Menge ${}_{B}$ bezeichnet, wenn jedes Element von ${}_{A}$ auch ein Element von ${}_{B}$ ist. Man schreibt dies als ${}_{A\subset B}$ (sprich: „A ist eine Teilmenge von B“, „A ist in B enthalten“, etc.).

Jede Menge enthält sowohl sich selbst als auch die leere Menge als Teilmenge.

Definition:

Die Mengen ${}_{A}$ und ${}_{B}$ sind gleich, wenn ${}_{(A\subset B)\land (B\subset A)}$ .

Definition:

Die Menge ${}_{A}$ ist eine echte Teilmenge von ${}_{B}$ , wenn ${}_{(A\subset B)\land (A\neq B)}$ gilt.

Satz:

$(A\subset B)\land (B\subset C)\Rightarrow (A\subset C)$

Definition:

Die Potenzmenge ${}_{{\mathcal {P}}(A)}$ einer Menge ${}_{M}$ ist die Menge aller Teilmengen von ${}_{M}$ .

Beispiel:

$A=\left\{a,b,c\right\}$

${\mathcal {P}}(A)=\left\{\emptyset ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\right\}$

Mengenoperationen

Definition:

Die Vereinigung ${}_{A\cup B}$ zweier Mengen ${}_{A}$ und ${}_{B}$ ist definiert durch

A\cup B:=\left\{x\left|(x\in A)\lor (x\in B)\right.\right\}

Satz:

Aus der Definition für die Vereinigung folgt der Zusammenhang

x\in \left(A\cup B\right)\Leftrightarrow (x\in A)\lor (x\in B)

Definition:

Der Durchschnitt ${}_{A\cap B}$ zweier Mengen ${}_{A}$ und ${}_{B}$ ist definiert durch

A\cap B:=\left\{x\left|(x\in A)\land (x\in B)\right.\right\}

Satz:

Aus der Definition für den Durchschnitt folgt der Zusammenhang

x\in \left(A\cap B\right)\Leftrightarrow (x\in A)\land (x\in B)

Definition:

Die Differenz ${}_{A\setminus B}$ (sprich: „A ohne B“) zweier Mengen ${}_{A}$ und ${}_{B}$ ist definiert durch

A\setminus B:=\left\{x\left|(x\in A)\land (x\notin B)\right.\right\}

Satz:

Aus der Definition für die Differenz folgt der Zusammenhang

x\in \left(A\setminus B\right)\Leftrightarrow (x\in A)\land (x\notin B)

Definition:

Das Komplement ${}_{A^{c}}$ bezüglich der Grundmenge ${}_{M}$ ist definiert durch

A\subset M:\ A_{M}^{c}:=M\setminus A

und

A\not \subset M:\ A_{M}^{c}:=\emptyset

Satz:

Aus der Definition für das Komplement folgt der Zusammenhang

A\subset M:\ x\in A_{M}^{c}\Leftrightarrow (x\in M)\land (x\notin A)

Definition:

Die Produktmenge ${}_{A\times B}$ (sprich: „A kreuz B“) zweier Mengen ${}_{A}$ und ${}_{B}$ ist definiert durch

A\times B:=\left\{\{a,b\}\left|(a\in A)\land (b\in B)\right.\right\}

Die Produktmenge ist daher die Menge aller geordneten Paare von Elementen aus den Mengen ${}_{A}$ und ${}_{B}$ .

Satz:

Aus der Definition für die Produktmenge folgt der Zusammenhang

\{a,b\}\in (A\times B)\Leftrightarrow (a\in A)\land (b\in B)

Beispiel:

$A=\{a_{1},a_{2},a_{3}\};\quad B=\{b_{1},b_{2}\}$

$A\times B=\left\{\{a_{1},b_{1}\},\{a_{1},b_{2}\},\{a_{2},b_{1}\},\{a_{2},b_{2}\},\{a_{3},b_{1}\},\{a_{3},b_{2}\}\right\}$

Mengenalgebra

Für beliebige Mengen $\ \{\}_{A}$ , $\ \{\}_{B}$ und $\ \{\}_{C}$ gelten

das Kommutativgesetz
1. $A\cup B=B\cup A$
2. $A\cap B=B\cap A\$
das Assoziativgesetz
1. $A\cup (B\cup C)=(A\cup B)\cup C$
2. $A\cap (B\cap C)=(A\cap B)\cap C\$
das Distributivgesetz
1. $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$
2. $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$
die De Morgan`schen Regeln
1. $(A\cup B)^{c}=A^{c}\cap B^{c}$
2. $(A\cap B)^{c}=A^{c}\cup B^{c}$

Abbildungen

Definition:

Eine Abbildung (Funktion) ${}_{f:\ A\rightarrow B}$ ist eine Vorschrift, welche jedem Element ${}_{a\in A}$ genau ein Element ${}_{f(a)\in B}$ zuordnet.

Die Menge ${}_{A}$ wird hierbei als Definitionsbereich bezeichnet, während die Menge ${}_{B}$ als Bildbereich (Zielmenge) und ${}_{f(a)}$ als Bild von ${}_{a}$ bezeichnet wird.

Als Bild der Abbildung ${}_{f}$ (Bildmenge) wird die Menge

f(A):=\{f(a):\ a\in A\}

bezeichnet. Der Graph der Abbildung ${}_{\mathrm {Graph} (f)}$ ist die Menge

\mathrm {Graph} (f):=\left\{\left.\{a,f(a)\}\right|a\in A\right\}\subset A\times B

Die exakte Schreibweise für eine Abbildung

f:\ A\rightarrow B,\quad a\mapsto f(a)

gibt den Definitionsbereich, den Bildbereich und die Abbildungsfunktion an. Meist wird jedoch abkürzend nur von der Abbildung ${}_{f}$ gesprochen.

Definition:

Eine Abbildung der Form ${}_{f:\ A\rightarrow B}$ ist

injektiv, wenn jedem ${}_{b\in B}$ höchstens ein ${}_{a\in A}$ zugeorndet wird:
$\forall a,b\in A:\ a_{1}\neq a_{2}\Rightarrow f(a_{1})\neq f(a_{2})$
surjektiv, wenn es zu jedem ${}_{b\in B}$ mindestens ein ${}_{a\in A}$ mit ${}_{b=f(a)}$ gibt:
$\forall b\in B:\ \exists a\in A:\ b=f(a)$
bijektiv, wenn es zu jedem ${}_{b\in B}$ genau ein ${}_{a\in A}$ mit ${}_{b=f(a)}$ gibt. Eine Abbildung ist also bijektiv, wenn sie sowohl injektiv als auch surjektiv ist.

Definition:

Die inverse Abbildung ${}_{f^{-1}}$ (auch inverse Funktion oder Umkehrfunktion) einer bijektiven Abbildung ${}_{f:\ A\rightarrow B}$ ist definiert durch

f^{-1}:\ B\rightarrow A,\quad f^{-1}(b)=a\Leftrightarrow f(a)=b

Satz:

Die inverse Abbildung [einer bijektiven Funktion] ist ebenfalls bijektiv.

Definition:

Eine Komposition (Zusammensetzung, Verschachtelung) ${}_{f\circ g}$ (sprich: „f von g“ oder „f angewandt auf g“) der Abbildungen ${}_{g:\ A\rightarrow B}$ und ${}_{f:\ C\rightarrow D}$ mit ${}_{g(A)\subset C}$ wird durch

f\circ g:\ A\rightarrow D,\quad s\mapsto f(g(x))

definiert.

Hierbei wird ${}_{f}$ als äußere und ${}_{g}$ als innere Abbildung bezeichnet.

Mächtigkeit und Abzählbarkeit von Mengen

Definition:

Die Mächtigkeit einer endlichen Menge ist gleich der Anzahl ihrer Elemente.

Satz:

Seien ${}_{A}$ und ${}_{B}$ gleich mächtige Mengen (dh. ${}_{A}$ und ${}_{B}$ haben die gleiche Anzahl an Elementen), so existiert zumindest eine bijektive Abbildung ${}_{A\sim B}$ von ${}_{A}$ auf ${}_{B}$ .

Umgekehrt gilt, dass wenn eine bijektive Abbildung ${}_{A\sim B}$ existiert, die Mengen ${}_{A}$ und ${}_{B}$ gleich mächtig sind.

Definition:

Eine Menge ist endlich (abzählbar endlich), wenn sie äquivalent zu einer Menge ${}_{\{1,\ldots ,n\}}$ mit ${}_{n\in N}$ ist.

Definition:

Eine Menge ist abzählbar (abzählbar unendlich), wenn diese äquivalent zu ${}_{\mathbb {N} }$ ist.

Definition:

Eine Menge, welche weder endlich noch abzählbar ist, wird als überabzählbar bezeichnet.

Satz:

Die Menge der rationalen Zahlen ${}_{\mathbb {Q} }$ ist abzählbar.

Beweis:

TODO: Cantor`sches Diagonalverfahren

Satz:

Die Vereinigung von abzählbar vielen abzählbaren Mengen ist abzählbar.

Beweis:

TODO: Cantors erstes Diagonalargument

Satz:

Die Menge der reellen Zahlen ${}_{\mathbb {R} }$ ist überabzählbar

Beweis:

TODO: Cantors zweites Diagonalargument

$A$	$B$	$\neg A$	$A\land B$	$A\lor B$	$A\Rightarrow B$	$A\Leftrightarrow B$
$w$	$w$	$f$	$w$	$w$	$w$	$w$
$w$	$f$	$f$	$f$	$w$	$f$	$f$
$f$	$w$	$w$	$f$	$w$	$w$	$f$
$f$	$f$	$w$	$f$	$f$	$w$	$w$

$A$	$B$	$\neg A$	$\neg B$	$A\land B$	$\neg (A\land B)$	$\neg A\lor \neg B$	$A\lor B$	$\neg (A\lor B)$	$\neg A\land \neg B$
$w$	$w$	$f$	$f$	$w$	$f$	$f$	$w$	$f$	$f$
$w$	$f$	$f$	$w$	$f$	$w$	$w$	$w$	$f$	$f$
$f$	$w$	$w$	$f$	$f$	$w$	$w$	$w$	$f$	$f$
$f$	$f$	$w$	$w$	$f$	$w$	$w$	$f$	$w$	$w$

$A$	$B$	$\neg A$	$\neg B$	$A\Rightarrow B$	$\neg B\Rightarrow \neg A$	$(A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)$
$w$	$w$	$f$	$f$	$w$	$w$	$w$
$w$	$f$	$f$	$w$	$f$	$f$	$w$
$f$	$w$	$w$	$f$	$w$	$w$	$w$
$f$	$f$	$w$	$w$	$w$	$w$	$w$

$A$	$B$	$\neg A$	$A\land B$	$A\lor B$	$A\Rightarrow B$	$A\Leftrightarrow B$
$w$	$w$	$f$	$w$	$w$	$w$	$w$
$w$	$f$	$f$	$f$	$w$	$f$	$f$
$f$	$w$	$w$	$f$	$w$	$w$	$f$
$f$	$f$	$w$	$f$	$f$	$w$	$w$

$A$	$B$	$\neg A$	$\neg B$	$A\land B$	$\neg (A\land B)$	$\neg A\lor \neg B$	$A\lor B$	$\neg (A\lor B)$	$\neg A\land \neg B$
$w$	$w$	$f$	$f$	$w$	$f$	$f$	$w$	$f$	$f$
$w$	$f$	$f$	$w$	$f$	$w$	$w$	$w$	$f$	$f$
$f$	$w$	$w$	$f$	$f$	$w$	$w$	$w$	$f$	$f$
$f$	$f$	$w$	$w$	$f$	$w$	$w$	$f$	$w$	$w$

$A$	$B$	$\neg A$	$\neg B$	$A\Rightarrow B$	$\neg B\Rightarrow \neg A$	$(A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)$
$w$	$w$	$f$	$f$	$w$	$w$	$w$
$w$	$f$	$f$	$w$	$f$	$f$	$w$
$f$	$w$	$w$	$f$	$w$	$w$	$w$
$f$	$f$	$w$	$w$	$w$	$w$	$w$

$A$	$B$	$\neg A$	$A\land B$	$A\lor B$	$A\Rightarrow B$	$A\Leftrightarrow B$
$w$	$w$	$f$	$w$	$w$	$w$	$w$
$w$	$f$	$f$	$f$	$w$	$f$	$f$
$f$	$w$	$w$	$f$	$w$	$w$	$f$
$f$	$f$	$w$	$f$	$f$	$w$	$w$

$A$	$B$	$\neg A$	$\neg B$	$A\land B$	$\neg (A\land B)$	$\neg A\lor \neg B$	$A\lor B$	$\neg (A\lor B)$	$\neg A\land \neg B$
$w$	$w$	$f$	$f$	$w$	$f$	$f$	$w$	$f$	$f$
$w$	$f$	$f$	$w$	$f$	$w$	$w$	$w$	$f$	$f$
$f$	$w$	$w$	$f$	$f$	$w$	$w$	$w$	$f$	$f$
$f$	$f$	$w$	$w$	$f$	$w$	$w$	$f$	$w$	$w$

$A$	$B$	$\neg A$	$\neg B$	$A\Rightarrow B$	$\neg B\Rightarrow \neg A$	$(A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)$
$w$	$w$	$f$	$f$	$w$	$w$	$w$
$w$	$f$	$f$	$w$	$f$	$f$	$w$
$f$	$w$	$w$	$f$	$w$	$w$	$w$
$f$	$f$	$w$	$w$	$w$	$w$	$w$