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\neq 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},\ldots ,t_{n}$ ist

   ${}(ft_{1}\ldots t_{n}){\frac {x}{x}}=ft_{1}{\frac {x}{x}}\ldots t_{n}{\frac {x}{x}}=ft_{1}\ldots 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 ${}\forall y\beta$ mit ${}y\neq x$ kommt ${}y$ nicht im substituierenden Term vor, und daher ist ${}v=y$ und

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

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

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

   nach Induktionsvoraussetzung.

Zur gelösten Aufgabe