Induktionsbeweise

Induktive Definition

$A_{0} \subseteq B$ Grundmenge

$f: B^{n} \mapsto B$ Bildungsregel (gibt true oder false aus)

Stufenweise Konstruktion

$A_{i+1}=A_{i} \cup\left\{f\left(x_{1}, \ldots, x_{n}\right) \mid x_{1}, \ldots, x_{n} \in A_{i}\right\}$

$\mathcal{A}=\bigcup_{i \geq 0} A_{i}$

Sätze

$A_{0} \subseteq \mathcal{A}$

$\mathcal A$ ist abgeschlossen unter $f$ :

$x_{1}, \ldots, x_{n} \in \mathcal{A} \Rightarrow f\left(x_{1}, \ldots, x_{n}\right) \in \mathcal{A}$

Ist $\mathcal A'$ abgeschlossen unter $f$ und gilt $A_{0} \subseteq \mathcal{A}^{\prime} \subseteq B$ , dann ist $\mathcal{A} \subseteq \mathcal{A}^{\prime}$

Schema einer Induktiven Definition

Man sagt $S$ ist die kleinste Menge die eine Bedingung erfüllen muss.

Initiale Bedingung

$E \subseteq S$

für eine vordefinierte Menge $E$

Spezialfall: Beide Mengen gleich $e_1, \dots, e_n \in S$

Induktive Bedingung

$O(s_{1}, \ldots, s_{n}) \in S$ wenn $s_{1}, \ldots, s_{n} \in S$

wobei $O$ ein Operator / eine Funktion ist vom Typ $S^{n} \mapsto S$

Implizit: Abschlussbedingung

Es ist sonst nichts Element von $S$

Beispiele

Gauss Sum
Induktionsannahme
Man zeige $\forall n\in \N:$
Sn=∑i=0ni=n(n+1)2S_{n}=\sum_{i=0}^{n} i=\frac{n(n+1)}{2}Sn=i=0∑ni=2n(n+1)
Induktionsbehauptung
Es gilt $S_{n+1}=S_{n}+n+1$
Beweis:
Sn+1=n(n+1)2+n+1=(n+1)(n+2)2=∑i=0n+1iS_{n+1}=\frac{n(n+1)}{2}+n+1=\frac{(n+1)(n+2)}{2} \color{grey} =\sum_{i=0}^{n+1} iSn+1=2n(n+1)+n+1=2(n+1)(n+2)=i=0∑n+1i
Induktionsanfang
Ebenso folgt aus der Induktionsannahme die Gültigkeit für $n = 0$ .

Terme
$\mathcal{T(D)}$ über $\mathcal D$ ist die kleinste Menge für die gilt
1. $I V S \subseteq \mathcal{T}(\mathcal{D})$
1. $K S \subseteq \mathcal{T}(\mathcal{D})$
1. $f^{\prime} \underline{(} t_{1} \underline , \ldots \underline , t_{n} \underline ) \in \mathcal{T}(\mathcal{D})$
  wenn $f^{\prime} \in F S_{n}(\mathcal{D})$ und $t_{1}, \ldots, t_{n} \in \mathcal{T}(\mathcal{D})$

Intendierte Semantik
Eigenschaften von $S$ können über mehrere Mengen definiert werden.
$\mathcal{M}_{\mathcal{T}}: E N V(\mathcal{D}) \times \mathcal{T}(\mathcal{D}) \mapsto D$

Beweis durch strukturelle Induktion

Induktionsbehauptung

Zu zeigen: $\forall s\in S: \Gamma(S)$

$\Gamma(S)$ heißt $s$ hat die Eigenschaft $\Gamma$

Induktionsanfang

$\forall e \in E\subseteq S: \Gamma(e)$

Induktionsannahme

$s_{1}, \ldots, s_{n} \in S$

Induktionsschritt

Wenn $\Gamma\left(s_{1}\right), \dots , \Gamma\left(s_{n }\right)$ und Induktionsannahme gelten, dann gilt die Induktionsbehauptung $\Gamma\left(O\left(s_{1}, \ldots, s_{n}\right)\right)$ .

Die Eigenschaft beibt nach der Operation erhalten.