Prädikatenlogik/Koinzidenzlemma/Fakt/Beweis/Aufgabe/Lösung


(1). Wir führen Induktion über den Aufbau der -Terme. Für den Induktionsanfang müssen wir Variablen und Konstanten aus betrachten. Für eine Variable (oder eine Konstante) aus ist nach Voraussetzung . Im Induktionsschritt können wir annehmen, dass ein -stelliges Funktionssymbol aus gegeben ist sowie -Terme , für die die Interpretationsgleichheit schon gezeigt wurde. Nach Voraussetzung wird in beiden Interpretationen durch die gleiche Funktion interpretiert. Daher ist


(2). Wir führen Induktion über den Aufbau der -Ausdrücke, wobei die zu beweisende Aussage über je zwei Interpretationen zu verstehen ist. Für die Gleichheit und ein Relationssymbol aus folgt die Aussage unmittelbar aus (1), da ja in beiden Interpretationen als die gleiche Relation zu interpretieren ist. Der Induktionsschritt ist für Ausdrücke der Form aufgrund der Modellbeziehung unmittelbar klar. Es sei nun ein -Ausdruck der Form gegeben, und es gelte . Dies bedeutet aufgrund der Modellbeziehung, dass es ein derart gibt, dass gilt. Die beiden umbelegten Interpretationen und

stimmen auf den Symbolen aus und den in frei vorkommenden Variablen überein: Die Variable wird so oder so als interpretiert und die anderen freien Variablen aus sind auch in frei. Nach Induktionsvoraussetzung gilt und daher wiederum .