Prädikatenlogik/Substitution/x durch x/Identität/Aufgabe/Lösung

1. Wir beweisen die Aussage durch Induktion über den Aufbau der Terme. Für Variablen ist bei  $y\ne x$  direkt  $y\frac{x}{x}=y$  und ferner  $x\frac{x}{x}=x$.  Konstanten bleiben bei jeder Substitution unverändert. Für ein $n$-stelliges Funktionssymbol $f$ und Terme $t_1,\dots ,t_n$ ist

   $(f{t}_1\dots t_n)\frac{x}{x}=f{t}_1\frac{x}{x}\dots t_n\frac{x}{x}=f{t}_1\dots t_n$

   nach Induktionsvoraussetzung.

2. Wir beweisen die Aussage durch Induktion über den Aufbau der Sprache für alle Variablen gleichzeitig. Wenn $\alpha$ eine Identität von Termen oder eine Relationsaussage ist, so ergibt sich die Behauptung unmittelbar aus Teil (1). Der Induktionsschritt für die aussagenlogischen Junktoren ergibt sich unmittelbar aus der Definition der Substitution. Bei $\mathrm{\forall }y\beta$ mit  $y\ne x$  kommt $y$ nicht im substituierenden Term vor, und daher ist  $v=y$  und

   $(\mathrm{\forall }y\beta )\frac{x}{x}=\mathrm{\forall }y(\beta \frac{y}{y})=\mathrm{\forall }y\beta$

   nach Induktionsvoraussetzung. Bei $\mathrm{\forall }x\beta$ ist $x$ nicht frei in $\beta$ und somit ist die relevante Termmenge leer und  $v=x$,  also

   $(\mathrm{\forall }x\beta )\frac{x}{x}=\mathrm{\forall }x(\beta \frac{x}{x})=\mathrm{\forall }x\beta$

   nach Induktionsvoraussetzung.

Zur gelösten Aufgabe