TU Wien:Mathematik 1 VO (Panholzer)/Stoff WS05/2. VO 17.10.2005

Mathematische Logik und Mengenlehre

Peano-Axiome

$\mathbb {N} =\{0,1,2,3,...\}$ - Menge der natürlichen Zahlen

Bezüglich der natürlichen Zahlen gelten die Peano-Axiome:

0 ist $\in \mathbb {N}$
$\forall n\in \mathbb {N} :\exists !n^{+}\in \mathbb {N}$ - für alle $n\in \mathbb {N}$ existiert genau ein Nachfolger $n^{+}$
0 ist kein Nachfolger (Einschränkung des vorhergehenden Punktes) - $\forall n\in \mathbb {N} :n^{+}\neq 0$
$\forall n,m\in \mathbb {N} :[n^{+}=m^{+}\Rightarrow n=m]$ - wenn die Nachfolger gleich sind, dann sind die Zahlen selbst gleich
Sei $S\subseteq \mathbb {N}$ $S\subseteq \mathbb {N}$ ( $\subseteq$ $\subseteq$ bedeutet Teilmenge ), für die gilt:
1. $0\in S$
2. $n\in S\Rightarrow n^{+}\in S$

Dann gilt: $S=\mathbb {N}$

Induktionsprinzip - sehr wichtige Beweismethode!

Eigenschaften der Menge der natürlichen Zahlen

Addition +, Multiplikation $\cdot$ für alle $n,m\in \mathbb {N}$ definiert - uneingeschränkt anwendbar.
Subtraktion -, Division / nur partiell ausführbar
Addition und Multiplikation erfüllen:
- Kommutativgesetz: $a+b=b+a$
- Assoziativgesetz: $a\cdot (b\cdot c)=(a\cdot b)\cdot c$
- Distributivgesetz: $a\cdot (b+c)=a\cdot b+a\cdot c$
Auf $\mathbb {N}$ ist die Ordnungsrelation $\leq$ definiert

Beweismethode der "Vollständigen Induktion"

Schluss von $n$ auf $n+1$

Idee: Man hat eine Vermutung für die Formel $\sum _{k=1}^{n}(2\cdot k-1)=n^{2}$ :

${\begin{matrix}\sum _{k=1}^{n}(2\cdot k-1)&=&n^{2}\\1+3+5+\ldots +2\cdot n-1&=&n^{2}\end{matrix}}$

Satz: Induktionsprinzip:

Sei $A(n)$ eine Aussage ( $n\in \mathbb {N}$ ) und es gelte:

$A(0)$ ist wahr
$A(n)\Rightarrow A(n+1)$ - Wenn $A(n)$ wahr ist, dann ist $A(n+1)$ auch wahr.

Dann gilt: $A(n)$ ist für alle $n\in \mathbb {N}$ wahr (Satz ist im Einklang mit den Peano-Axiomen).

Bemerkungen:

1. heißt Induktionsanfang
2. heißt Induktionsschluss
$A(n)$ ... Induktionsvorraussetzungen
$A(n+1)$ ... Induktionsbehauptung
Ersetzt man 1. durch 1.'.: $A(n_{0})$ ist wahr und 2. durch 2.': $\forall n\geq n_{0}:A(n)\Rightarrow A(n+1)$

Damit gilt: $A(n)$ ist für alle $n\geq n_{0}$ wahr!

Das Verfahren geht so vor sich:

$\sum _{k=1}^{n}(2\cdot k-1)=n^{2}\qquad \forall n\in \mathbb {N} ,n\geq 1$

Induktionsanfang:
- $n=0$ (Konvention - Betrag einer leeren Summe ist Null)
- $n=1,2,3,...$ bereits gezeigt (Fleißaufgabe)
Induktionsschluss:
- $A(n):\sum _{k=1}^{n}(2\cdot k-1)=n^{2}$
- $A(n+1):\sum _{k=1}^{n+1}(2\cdot k-1)=(n+1)^{2}$ (Annahme)

Beweis:

${\begin{array}{rcll}\sum _{k=1}^{n}(2k-1)&=&n^{2}&|+2(n+1)-1\\\sum _{k=1}^{n}(2k-1)+2(n+1)-1&=&n^{2}+2(n+1)-1\\\sum _{k=1}^{n}(2k-1)&=&(n+1)^{2}\\\Rightarrow A(n+1):\sum _{k=1}^{n}(2k-1)&=&(n+1)^{2}\end{array}}$

Weiteres Beispiel:

$\sum _{k=0}^{n}k={\frac {n\cdot (n+1)}{2}}$

Induktionsanfang: $A(0):\sum _{k=0}^{n}k=0$
Induktionsschritt: $A(n):\sum _{k=1}^{n}k={\frac {n\cdot (n+1)}{2}}$
Behauptung: $A(n+1):\sum _{k=1}^{n}k={\frac {(n+1)\cdot (n+2)}{2}}$ (Annahme)
Beweis:

${\begin{array}{rcll}\sum _{k=0}^{n}(k)&=&{\frac {n\cdot (n+1)}{2}}&|+(n+1)\\\sum _{k=0}^{n}(k)+(n+1)&=&{\frac {n\cdot (n+1)}{2}}+(n+1)\\\sum _{k=0}^{n+1}(k)&=&{\frac {n\cdot (n+1)}{2}}+{\frac {2(n+1)}{2}}\\\ &=&{\frac {n^{2}+n+2n+2}{2}}={\frac {n^{2}+3n+2}{2}}\\\sum _{k=0}^{n+1}k&=&{\frac {(n+1)(n+2)}{2}}=A(n+1)\end{array}}$

Daher gilt: $A(n)$ ist wahr $\forall n\in \mathbb {N}$ .

Allgemein: Ersetze 2. durch 2'.: $A(0),A(1),...,A(n)\Rightarrow A(n+1)$

Literatur

Skriptum: Seiten 1-3

Weblinks