Substitutionslemma
Es sei ein Symbolalphabet
einer Sprache erster Stufe gegeben und es seien
paarweise verschiedene Variablen und
fixierte
-Terme.
Es sei eine
-Interpretation
gegeben. Dann gelten folgende Aussagen.
- Für jeden
-Term
gilt
-

- Für jeden
-Ausdruck
gilt
-