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.
sind korrekt.
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