Prädikatenlogik/Substitutionslemma/Fakt/Beweis

Beweis

Dies wird über den induktiven Aufbau der Terme bzw. der Ausdrücke bewiesen. (1). Für eine Konstante ist die Aussage richtig, da ihre Interpretation unverändert ist. Für eine Variable macht man eine Fallunterscheidung. Wenn

mit einer der an der Substitution beteiligten Variablen ist, so ist

Bei einer an der Substitution nicht beteiligten Variablen ist

Wenn ein -stelliges Funktionssymbol ist und Terme sind, für die die Gleichheit schon bekannt ist, so ist


(2). Für einen Ausdruck der Form bedeutet

einfach

Dies ist äquivalent zu

was nach dem ersten Teil einfach

bedeutet. Dies wiederum ist äquivalent zu

Es sei nun ein -stelliges Relationssymbol und seien Terme. Die Gültigkeit

bedeutet

und dies bedeutet, dass

zur Relation gehört. Nach dem ersten Teil ist dieses Tupel gleich

Wegen ist dies äquivalent zu

Für die weiteren Aussagen beweist man die Äquivalenz durch Induktion über den Aufbau der Ausdrücke, und zwar über alle Interpretationen simultan; dies ist für die aussagenlogischen Junktoren unmittelbar klar. Betrachten wir also einen Ausdruck der Form . Die Gültigkeit

bedeutet gemäß der Festlegung in Definition, dass

gilt, wobei in nicht vorkommt. Dies bedeutet, dass für jedes der Grundmenge der Interpretation die Beziehung

gilt. Nach Induktionsvoraussetzung (angewendet auf die Interpretation ) bedeutet dies

für alle . Aufgrund des Koinzidenzlemmas ist dies äquivalent zu

Dies ist äquivalent (für alle ) zu

was bei klar ist und bei aus dem Koinzidenzlemma folgt, da dann nicht in vorkommt. Dies bedeutet wiederum

und damit, wiederum nach dem Koinzidenzlemma, da die von verschiedenen Variablen in nicht frei vorkommen,