Prädikatenlogik/Vollständigkeitssatz/Modellkonstruktion/Funktion/Dreifacher Nachfolger/Aufgabe

Das Symbolalphabet ${}S$ bestehe neben Variablen ${}x,y,z,\ldots$ aus einer Konstanten ${}0$ und einem einstelligen Funktionssymbol ${}f$. Wir betrachten die Teilmengen

${}\Gamma _{i}\subseteq L^{S}\,$

mit

${}\Gamma _{1}=\{fff0=0\}^{\vdash }\,,$

${}\Gamma _{2}=\{fffx=x\}^{\vdash }\,,$

${}\Gamma _{3}=\{\forall x{\left(fffx=x\right)}\}^{\vdash }\,.$

Es seien ${}\sim _{i}$ die zugehörigen Äquivalenzrelationen gemäß Bemerkung auf der Termmenge.

1. Gelten die Äquivalenzen

   $ffff0\sim _{1}f0,\,ffffff0\sim _{1}fff0,\,fffffffff0\sim _{1}fffffff0,\,ffffx\sim _{1}fx?$

2. Gelten die Äquivalenzen

   $ffffx\sim _{2}fx,\,ffffy\sim _{2}fy,\,fffx\sim _{2}y,\,ffffy\sim _{3}fy?$

3. Welche Inklusionsbeziehungen bestehen zwischen ${}\Gamma _{1},\Gamma _{2},\Gamma _{3}$?
4. Wie viele Termklassen gibt es zu ${}\sim _{1},\sim _{2},\sim _{3}$, wenn die Variablenmenge nur aus ${}x$ besteht?

Eine Lösung erstellen