Prädikatenlogik/Syntaktische Tautologien/Gleichheitstautologien/Textabschnitt

In der Prädikatenlogik gelten die beiden folgenden Tautologien für die Gleichheit.


Es sei ein Symbolalphabet, seien -Terme und sei ein -Ausdruck. Dann sind die beiden folgenden Ausdrücke syntaktische Tautologien.

Diese beiden Axiome (oder genauer Axiomenschemata) heißen Gleichheitsaxiom und Substitutionsaxiom. Mit einer aussagenlogischen Umformulierung sieht man, dass das Substitutionsaxiom äquivalent zu

ist.



Es sei eine beliebige -Interpretation. (1). Aufgrund der Bedeutung des Gleichheitszeichens unter jeder Interpretation gilt , also


(2). Es gelte

also und . Das bedeutet einerseits . Andererseits gilt nach dem Substitutionslemma

Wegen der Termgleichheit gilt somit auch

und daher, wiederum aufgrund des Substitutionslemmas, auch



Bei leerer Variablenmenge ist das Substitutionsaxiom aussagelos. In Hinblick auf Fakt fordern wir, dass die Variablenmenge stets unendlich ist.


Aus den Gleichheitsaxiomen lassen sich folgende Gleichheitstautologien ableiten (dabei sind Terme, ein -stelliges Funktionssymbol und ein -stelliges Relationssymbol).

(1). Aufgrund der Gleichheitsaxiome haben wir

und

wobei eine Variable sei, die weder in noch in vorkomme. Daher sind die beiden substituierten Ausdrücke gleich bzw. . Eine aussagenlogische Umstellung der zweiten Zeile ist

sodass sich aus der ersten Zeile mittels Modus ponens

ergibt.
(2). Es sei wieder eine Variable, die weder in noch in noch in vorkomme. Eine Anwendung des Substitutionsaxioms liefert

Nach Einsetzen und einer aussagenlogischen Umstellung ist dies die Behauptung.
Für (3) siehe Aufgabe.
(4). Es sei eine Variable, die weder in einem der noch in einem der vorkommt. Für jedes gilt nach Axiom  (2) (mit ) dann

also

Diese Ableitbarkeiten gelten auch, wenn man die Vordersätze durch ihre Konjunktion

ersetzt. Durch die Transitivität der Implikation ergibt sich daher