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

1. Wegen ${}\vdash s=s$ und der Korrektheit des Ableitungskalküls ist ${}I(s)=I(t)$ überhaupt für jede Interpretation. Es liegt also eine reflexive Relation vor. Es sei nun ${}s\cong _{\Gamma }t$. Dann gilt für jede Interpretation ${}I$ mit ${}I\vDash \Gamma$ die Gleichheit ${}I(s)=I(t)$ und somit auch ${}I(t)=I(s)$, also ist auch ${}t\cong _{\Gamma }s$, was die Symmetrie beweist. Es gelte nun ${}r\cong _{\Gamma }s$ und ${}s\cong _{\Gamma }t$, und es sei ${}I$ eine Interpretation mit ${}I\vDash \Gamma$. Dann ist ${}I(r)=I(s)$ und ${}I(s)=I(t)$ und somit auch ${}I(r)=I(t)$ wegen der Transitivität der Gleichheit. Also gilt ${}r\cong _{\Gamma }t$, was die Transitivität beweist.
2. Es sei ${}\Gamma \subseteq \Gamma '$. Wir behaupten, dass die Äquivalenz ${}s\cong _{\Gamma }t$ die Äquivalenz ${}s\cong _{\Gamma '}t$ impliziert. Es sei dazu ${}s\cong _{\Gamma }t$ und eine Interpretation ${}I$ mit ${}I\vDash \Gamma '$ gegeben. Dann gilt erst recht ${}I\vDash \Gamma$ und somit ist ${}I(s)=I(t)$. Somit umfassen die Äquivalenzklassen zu ${}\cong _{\Gamma '}$ die Äquivalenzklassen zu ${}\cong _{\Gamma }$, die Äquivalenzklassen werden also größer.

Zur gelösten Aufgabe