Prädikatenlogik/Modellkonstruktion/Funktionsäquivalenz/Semantisch und syntaktisch/Aufgabe

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache. Es sei ${}\Gamma \subseteq L^{S}$ eine Ausdrucksmenge. Zu fixiertem ${}n\in \mathbb {N} _{+}$ sei ${}F_{n}$ die Menge der ${}n$-stelligen Funktionssymbole. Zeige die folgenden Aussagen.

1. Durch

   $f\cong g\,,{\text{ falls }}I(f)=I(g){\text{ für alle Interpretationen }}I{\text{ mit }}I\vDash \Gamma$

   wird eine Äquivalenzrelation auf ${}F_{n}$ definiert.

2. Durch

   $f\sim g\,,{\text{ falls }}\Gamma \vdash \forall x_{1}\forall x_{2}\ldots \forall x_{n}fx_{1}\ldots x_{n}=gx_{1}\ldots x_{n}$

   wird eine Äquivalenzrelation auf ${}F_{n}$ definiert.

3. Die Äquivalenzrelation ${}\sim$ impliziert die Äquivalenzrelation ${}\cong$.
4. Es sei ${}\sim$ die zu ${}\Gamma$ gehörende formale Äquivalenzrelation auf der Termmenge im Sinne von Bemerkung. Dann gilt für Terme ${}s_{1}\sim t_{1},\ldots ,s_{n}\sim t_{n}$ und Funktionssymbole ${}f,g\in F_{n}$ mit ${}f\sim g$ die Beziehung

   ${}fs_{1}\ldots s_{n}\sim gt_{1}\ldots t_{n}\,.$

Eine Lösung erstellen