Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Arbeitsblatt 14

Übungsaufgaben

Aufgabe

Es seien ${}S\subseteq S'$ Symbolalphabete und seien ${}L^{S}\subseteq L^{S^{\prime }}$ die zugehörigen Sprachen Es sei ${}\Gamma \subseteq L^{S}$ eine Ausdrucksmenge.

1. ${}\Gamma$ sei widerspruchsfrei. Ist dann auch ${}\Gamma$, aufgefasst in ${}L^{S^{\prime }}$, widerspruchsfrei?
2. ${}\Gamma$ sei maximal widerspruchsfrei. Ist dann auch ${}\Gamma$, aufgefasst in ${}L^{S^{\prime }}$, maximal widerspruchsfrei?

Aufgabe

Zeige durch ein Beispiel, dass Lemma 14.5 ohne die Voraussetzung, dass eine surjektive Terminterpretation vorliegt, nicht gelten muss.

Aufgabe

Es sei ${}S$ ein Symbolalphabet und ${}I$ eine ${}S$- Interpretation auf einer Menge ${}M$ mit der zugehörigen Terminterpretation. Zeige, dass man diese Terminterpretationsabbildung durch die Hinzunahme von Variablen (oder durch die Hinzunahme von Konstanten) surjektiv machen kann.

Aufgabe

Das Symbolalphabet ${}S$ bestehe aus einer einzigen Variablen ${}x$ und einem einzigen einstelligen Relationssymbol ${}P$. Zeige, dass zu einer Interpretation ${}I$ die Gültigkeitsmenge ${}I^{\vDash }\subseteq L^{S}$ keine Beispiele enthalten muss.

Aufgabe *

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache und ${}T$ die zugehörige Termmenge. Es sei ${}\Gamma \subseteq L^{S}$ eine Ausdrucksmenge.

1. Zeige, dass durch

   $s\cong _{\Gamma }t{\text{ genau dann, wenn }}I(s)=I(t){\text{ für jede Interpretation }}I{\text{ mit }}I\vDash \Gamma$

   eine Äquivalenzrelation auf ${}T$ definiert wird.

2. Wenn man ${}\Gamma$ vergrößert, werden dann die Äquivalenzklassen größer oder kleiner?

Aufgabe

Es sei ${}S$ ein Symbolalphabet, ${}T$ die zugehörige Termmenge und ${}L^{S}$ die zugehörige Sprache. Es sei ${}\Gamma \subseteq L^{S}$ eine Ausdrucksmenge. Zeige, dass die Äquivalenzrelation ${}\sim _{\Gamma }$ aus Konstruktion 14.7 die semantische Äquivalenz ${}\cong _{\Gamma }$ aus Aufgabe 14.5 impliziert.

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äß Konstruktion 14.7 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?

Aufgabe

Das Symbolalphabet ${}S$ bestehe neben Variablen ${}x,y,z,\ldots$ aus einer Konstanten ${}0$ und einem zweistelligen Funktionssymbol ${}+$. Es sei ${}\Gamma \subseteq L^{S}$ die Menge aller Ableitungen aus dem Axiomensystem

$\forall x(x+0=x),\,\forall x(0+x=x),\,\forall x\forall y\forall z((x+y)+z)=x+(y+z)),\,\forall x(x+x=0).$

Es sei ${}\sim$ die zugehörige Äquivalenzrelation gemäß Konstruktion 14.7. Zeige ${}x+y\sim y+x$ für jedes Variablenpaar ${}x,y$.

Aufgabe

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache. Zeige, dass zu

${}\Gamma =\emptyset \,$

die in Konstruktion 14.7 eingeführte Äquivalenzrelation die Identität ist.

Aufgabe

Es sei ${}\Gamma \subseteq L^{S}$ eine widersprüchliche, unter Ableitungen abgeschlossene Teilmenge. Zeige, dass es nur eine Termklasse im Sinne von Konstruktion 14.7 gibt.

Aufgabe

Es sei ${}\Gamma \subseteq L^{S}$ eine unter Ableitungen abgeschlossene Teilmenge, die zu je zwei Termen ${}s,t$ die Gleichheit ${}s=t$ enthalte. Wie viele Termklassen im Sinne von Konstruktion 14.7 gibt es? Ist ${}\Gamma$ widersprüchlich?

Aufgabe

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache. Die Ausdrucksmenge ${}\Gamma$ bestehe aus ${}x=y$, wobei ${}x,y$ verschiedene Variablen seien. Zeige, dass zwei Terme ${}s,t$ genau dann äquivalent im Sinne von Konstruktion 14.7 sind, wenn es eine Kette von Termen

$t_{0}=s,t_{1},t_{2},\ldots ,t_{k-1},t_{k}=t$

derart gibt, dass beim Übergang von ${}t_{i}$ nach ${}t_{i+1}$ genau ein Vorkommen von ${}x$ (bzw. ${}y$) in ${}t_{i}$ durch ${}y$ (bzw. ${}x$) ersetzt wird.

Aufgabe

Es sei ${}V$ eine Variablenmenge und ${}\simeq$ eine Äquivalenzrelation auf ${}V$ mit der Quotientenmenge ${}W=V/\simeq$. Es sei ${}S$ ein erststufiges Symbolalphabet mit ${}V$ als Variablenmenge und

${}\Gamma :={\left\{x=y\mid x\simeq y\right\}}^{\vdash }\,.$

Es sei ${}\sim$ die zugehörige Äquivalenzrelation auf der Termmenge gemäß Konstruktion 14.7. Zeige, dass die Termklassenmenge zu ${}\Gamma$ in kanonischer Weise mit der Termmenge zum Symbolalphabet ${}S'$ in Bijektion steht, wobei ${}S'$ aus ${}S$ entsteht, indem man die Variablenmenge ${}V$ durch ${}W$ ersetzt.

In der folgenden Aufgabe sollen die Variablen ${}x_{1},\ldots ,x_{n}$ verschieden sein. Dennoch gibt es zwei Interpretationen für Teil (2), die aber inhaltlich äquivalent sind.

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 Konstruktion 14.7. 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}\,.$

Aufgabe

Es sei ${}\alpha \in L^{S}$ ein atomarer Ausdruck, der zugleich eine Tautologie ist, also ${}\vdash \alpha$. Zeige, dass ${}\alpha$ gleich ${}s=s$ mit einem ${}S$- Term ${}s$ ist.

Aufgabe

Bestimme den Rang der folgenden Ausdrücke.

1. ${}a=fx$,
2. ${}\exists xa=fx$,
3. ${}{\left(\neg Rxy\wedge ffx=c\right)}\rightarrow {\left(\exists xa=fx\right)}$,
4. ${}{\left(\forall yRxy\right)}\rightarrow {\left(\exists xa=fx\right)}$.

Aufgabe

Zeige durch Induktion über den Aufbau der Ausdrücke, dass sich bei einer Termsubstitution der Rang eines Ausdrucks nicht ändert.

Aufgabe

Warum führt man im Beweis zum Satz von Henkin nicht Induktion über den Aufbau der Ausdrücke?

Aufgabe

Es sei ${}M$ ein kommutativer Halbring. Zeige, dass es eine eindeutig bestimmte (kanonische) Abbildung

$\varphi \colon \mathbb {N} \longrightarrow M$

gibt, die sowohl die Addition als auch die Multiplikation respektiert.

Aufgabe

Es sei ${}M$ ein Peano-Halbring und

$\varphi \colon \mathbb {N} \longrightarrow M$

die kanonische Abbildung. Zeige, dass ${}\varphi$ injektiv ist.

Aufgabe

Es sei ${}n\in \mathbb {N} _{+}$ und betrachte ${}M=\mathbb {Z} /(n)$ mit den natürlichen Operationen. Welche der Peano-Axiome gelten, welche nicht?

Aufgabe *

Es sei ${}M$ ein kommutativer Halbring und ${}x,y\in M$. Es sei

${}I:={\left\{u\in M\mid \exists a\exists b\exists c\exists d{\text{ mit }}u+ax+by=cx+dy\right\}}\,.$

1. Zeige, dass ${}I$ die folgenden drei Eigenschaften erfüllt.
   1. ${}0\in I$.
   2. Wenn ${}u,v\in I$ sind, so ist auch ${}u+v\in I$.
   3. Wenn ${}u\in I$ und ${}r\in M$ ist, so ist auch ${}ru\in I$.
2. ${}M$ erfülle nun die Abziehregel. Zeige, dass aus ${}u,v\in I$ mit ${}u=v+z$ auch ${}z\in I$ folgt.

Die folgende Aufgabe gibt eine Version des Lemmas von Bezout für Peano-Halbringe.

Aufgabe

Es sei ${}M$ ein Peano-Halbring und ${}x,y\in M$. Es sei

${}I:={\left\{u\in M\mid \exists a\exists b\exists c\exists d{\text{ mit }}u+ax+by=cx+dy\right\}}\,.$

Zeige, dass es ein eindeutig bestimmtes ${}v\in M$ derart gibt, dass ${}I$ aus sämtlichen Vielfachen von ${}v$ besteht. Zeige, dass ${}v$ der größte gemeinsame Teiler von ${}x$ und ${}y$ ist.

Aufgabe

Zeige, dass in einem Peano-Halbring ${}M$ die Begriffe irreduzibel und prim zusammenfallen.

Aufgabe

Zeige, dass in ${}M\subseteq \mathbb {Z} [V]$ aus Beispiel 13.9 durch ${}x\geq y$, falls es ein ${}z\in M$ mit ${}x=y+z$ gibt, eine totale Ordnung gegeben ist.

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Es sei ${}\Gamma$ eine Menge an ${}S$- Ausdrücken (über einem Symbolalphabet ${}S$), die folgende Eigenschaften erfüllt.

1. Für jeden Ausdruck ${}\alpha$ ist ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$.
2. Aus ${}\Gamma \vdash \alpha$ folgt ${}\alpha \in \Gamma$, d.h. ${}\Gamma$ ist abgeschlossen unter Ableitungen.
3. ${}\Gamma$ ist widerspruchsfrei.

Zeige, dass ${}\Gamma$ maximal widerspruchsfrei ist.

Aufgabe (4 Punkte)

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache. Es seien ${}s,t$ verschiedene Terme. Zeige, dass es eine ${}S$- Interpretation ${}I$ mit

${}I(s)\neq I(t)\,$

gibt.

Aufgabe (5 Punkte)

Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ die Peano-Arithmetik, also die Menge aller aus den erststufigen Peano-Axiomen ableitbaren Ausdrücke. Zeige, dass jeder variablenfreie Term im Sinne von Konstruktion 14.7 äquivalent zu einem Term ist, bei dem das Multiplikationszeichen nicht mehr vorkommt.

Aufgabe (8 (1+3+1+3) Punkte)

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 ${}R_{n}$ die Menge der ${}n$-stelligen Relationssymbole in ${}S$. Zeige die folgenden Aussagen.

1. Durch

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

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

2. Durch

   $P\simeq Q\,,{\text{ falls }}\Gamma \vdash \forall x_{1}\forall x_{2}\ldots \forall x_{n}{\left(Px_{1}\ldots x_{n}\leftrightarrow Qx_{1}\ldots x_{n}\right)}$

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

3. Die Äquivalenzrelation ${}\simeq$ impliziert die Äquivalenzrelation ${}\cong$.
4. Es sei ${}\sim$ die zu ${}\Gamma$ gehörende Äquivalenzrelation auf der Termmenge im Sinne von Konstruktion 14.7. Dann gilt für Terme mit ${}s_{1}\sim t_{1},\ldots ,s_{n}\sim t_{n}$ und Relationsssymbole ${}P,Q\in R_{n}$ mit ${}P\simeq Q$ die Beziehung

   $\Gamma \vdash Ps_{1}\ldots s_{n}\leftrightarrow Qt_{1}\ldots t_{n}.$

Aufgabe (2 Punkte)

Bestimme den Rang der folgenden Ausdrücke.

1. ${}gxy=c$,
2. ${}\forall xgcx=gxx$,
3. ${}{\left(\neg Pz\vee ggxyy=gcc\right)}\rightarrow {\left(\exists xPx\right)}$,
4. ${}{\left(\forall yPy\right)}\rightarrow {\left(\neg \exists xgcx=gcgcx\wedge c=c\right)}$.