Inhalt
Inhaltsverzeichnis
Strukturelle Induktion
Gegeben sie eine rekursiv definierte Menge und eine rekursiv definierte Funktion auf diese Menge. Um zu zeigen, das alle Elemente der Menge (z.B.
$x \in I$
eine bestimmte Eigenschaft (z.B.
$E \left( x \right)$
) haben nutzt man die strukturelle Induktion:
- Induktionsanfang (IA)
- Zeigen das das Element welches durch die erste Regel definiert wird die Eigenschaft hat
- Induktionsschluss(IS)
- Zeigen das jedes Element das durch die zweite Regel erzeugt wird die Eigenschaft hat wenn die Elemente auf die die zweite Regel zugreift diese Eigenschaften haben.
Die strukturelle Induktion greift also direkt auf die Regeln der rekursiven Definitionen zu. Die strukurelle Induktion ist ein Spezialfall von wohlfundierter Induktion.
Beispiele
1. Zeige das alle Elemente der Menge I die Eigenschaft E haben.
a) Zeige das gilt:
$E\left(nil\right)$
.BRb) Zeige das wenn
$E\left(l\right)$
gilt das auch
$E\left(1\mid nil\right)$
gilt.
2. Sei append so definiert:
a)
$nil\, append\, l=l$
b)
$1\mid l\, append\, l'=1\mid\left(l\, append\, l'\right)$
Zu zeigen: Für alle
$l , l'$
gilt
$S\left(l\, append\, l'\right)=S\left(l\right)+S\left(l'\right)$
Mittels struktureller Induktion ist dies so beweisbar:
IA:
$\forall l\in I gilt: S\left(nil\, append\, l\right)=S\left(nil\right)+S\left(l\right)$
BRIS:
$\forall l\in I\left(\forall l'\in I\left(S\left(l\, append\, l'\right)=S\left(l\right)+S\left(l'\right) \Rightarrow \forall l'\in I\left(S\left(1\mid l\, append\, l'\right)=S\left(1\mid l\right)+S\left(l'\right)\right)\right)\right)$
Wohlfundierte Induktion
Wir wollen mittels Induktion zeigen das eine nicht strukturell induktiv definierte Menge M (siehe Mengen) die Eigenschaft E hat. Hierzu muss meine eine wohlfundierte Relation über M finden.
Vorgehen bei einer wohlfundierten Induktion:
1. Finden einer wohlfundierten Relation
$\succ$
auf
$M$
.
2. Zeigen das gilt:
$\forall x \in M \left( \forall y \in M\left(\left(E\left(y\right)\wedge x\succ y\right)\Rightarrow E\left(x\right)\right)\right)$
(Wenn alle y mit
$x\succ y$
die Eigenschaft E haben dann hat auch x die Eigenschaft E ).