Prädikatenlogik/Terme/Identifizierung in Interpretationen/Äquivalenzrelation/Aufgabe/Lösung

Aus Wikiversity


  1. Wegen und der Korrektheit des Ableitungskalküls ist überhaupt für jede Interpretation. Es liegt also eine reflexive Relation vor. Es sei nun . Dann gilt für jede Interpretation mit die Gleichheit und somit auch , also ist auch , was die Symmetrie beweist. Es gelte nun und , und es sei eine Interpretation mit . Dann ist und und somit auch wegen der Transitivität der Gleichheit. Also gilt , was die Transitivität beweist.
  2. Es sei . Wir behaupten, dass die Äquivalenz die Äquivalenz impliziert. Es sei dazu und eine Interpretation mit gegeben. Dann gilt erst recht und somit ist . Somit umfassen die Äquivalenzklassen zu die Äquivalenzklassen zu , die Äquivalenzklassen werden also größer.