Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Arbeitsblatt 9

Bestimme die freien Variablen in den folgenden Ausdrücken, wobei ${\displaystyle {}x,y,z}$ Variablen seien und ${\displaystyle {}f}$ ein einstelliges Funktionssymbol und ${\displaystyle {}R}$ ein zweistelliges Relationssymbol sei.

1. ${\displaystyle {}\forall x{\left(fx=y\right)}}$,
2. ${\displaystyle {}\forall x{\left(fx=y\right)}\wedge \exists z{\left(fx=y\right)}}$,
3. ${\displaystyle {}\forall x\exists yRxfy}$,
4. ${\displaystyle {}{\left(\forall x\exists yRxfy\right)}\rightarrow x=y}$.

Bestimme die kleinsten Symbolmengen, mit denen die folgenden Ausdrücke formulierbar sind.

1. ${\displaystyle {}\exists y{\left(fx=y\right)}}$,
2. ${\displaystyle {}\forall x{\left(fx=gyc\right)}\wedge \exists z{\left(Rzxy\right)}}$,
3. ${\displaystyle {}\forall x\exists ySxhuy}$.

Es sei ${\displaystyle {}\alpha \in L_{0}^{S}}$ ein Satz einer erststufigen Spracheüber einem Symbolalphabet ${\displaystyle {}S}$. Es sei eine${\displaystyle {}S}$-Strukturmit Trägermenge ${\displaystyle {}M}$ gegeben und ${\displaystyle {}I_{1}}$ und ${\displaystyle {}I_{2}}$zwei auf ${\displaystyle {}M}$ definierte ${\displaystyle {}S}$-Interpretationen.Zeige ${\displaystyle {}I_{1}\vDash \alpha }$ genau dann, wenn ${\displaystyle {}I_{2}\vDash \alpha }$ gilt.

Es seien ${\displaystyle {}c,d}$ Konstanten einererststufigen Sprache,${\displaystyle {}x,y,z,v}$ Variablen, ${\displaystyle {}f}$ ein einstelliges und ${\displaystyle {}g,h}$ zweistellige Funktionssymbole. Bestimme die Substitution

${\displaystyle ghhxcdfz{\frac {fx,\,\,\,\,\,gxz,\,\,\,\,\,hvfx}{x,\,\,\,\,\,\,\,\,\,\,\,\,y,\,\,\,\,\,\,\,\,\,\,\,\,z}}.}$

Es sei ein Symbolalphabet ${\displaystyle {}S}$ einer Sprache erster Stufegegeben. Es seien ${\displaystyle {}x_{1},\ldots ,x_{k}}$ paarweise verschiedene Variablen und ${\displaystyle {}t_{1},\ldots ,t_{k}}$ fixierte${\displaystyle {}S}$-Terme.

a) Interpretiere die Termsubstitution${\displaystyle {}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}}$ als Abbildung.

b) Interpretiere die Substitution von Ausdrücken${\displaystyle {}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}}$ als Abbildung.

Es sei ein Symbolalphabet ${\displaystyle {}S}$ einer Sprache erster Stufegegeben.

1. Zeige, dass die Substitution${\displaystyle {}{\frac {x}{x}}}$ für die Terme die Identität ist.
2. Zeige, dass die Substitution${\displaystyle {}{\frac {x}{x}}}$ für die Ausdrücke die Identität ist.

Es sei ein Symbolalphabet ${\displaystyle {}S}$ einer Sprache erster Stufe gegeben, es sei ${\displaystyle {}x}$ eine Variable und ${\displaystyle {}t}$ ein fixierter${\displaystyle {}S}$-Term.Gehört die Symbolkette(!)${\displaystyle {}\alpha {\frac {t}{x}}}$ zu ${\displaystyle {}L^{S}}$?

Es sei ${\displaystyle {}c}$ eine Konstante einererststufigen Sprache,${\displaystyle {}x,y,z,u}$ Variablen, ${\displaystyle {}f}$ ein einstelliges Funktionssymbol, ${\displaystyle {}g,h}$ zweistellige Funktionssymbole und ${\displaystyle {}R}$ ein zweistelliges Relationssymbol. Bestimme dieSubstitution

${\displaystyle {\left(\forall yRxy\wedge \neg Ryfz\right)}{\frac {fx,\,\,\,\,\,gxz,\,\,\,\,\,hcfx}{x,\,\,\,\,\,\,\,\,\,\,\,\,y,\,\,\,\,\,\,\,\,\,\,\,\,z}}.}$

Es sei ein Symbolalphabet ${\displaystyle {}S}$ einer Sprache erster Stufe gegeben. Man gebe ein Beispiel für eine Substitution ${\displaystyle {}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}}$ und einen ${\displaystyle {}S}$-Ausdruck ${\displaystyle {}\alpha }$ derart, dass die sukzessive substituierten Ausdrücke

${\displaystyle \alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}},{\left(\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}},{\left({\left(\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}},\ldots }$

immer länger werden.

Es sei ein Symbolalphabet ${\displaystyle {}S}$ einer Sprache erster Stufegegeben. Es seien ${\displaystyle {}x_{1},\ldots ,x_{k}}$ paarweise verschiedene Variablen und ${\displaystyle {}t_{1},\ldots ,t_{k}}$ fixierte${\displaystyle {}S}$-Terme.Zeige, dass für jeden ${\displaystyle {}S}$-Satz ${\displaystyle {}\alpha \in L_{0}^{S}}$ die Gleichheit

${\displaystyle {}\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}=\alpha \,}$

gilt.

Es sei ${\displaystyle {}\alpha \in L^{S}}$. Zeige, dass die Gleichheit

${\displaystyle {}{\left(\alpha {\frac {y}{x}}\right)}{\frac {z}{y}}=\alpha {\frac {y,z}{x,y}}\,}$

im Allgemeinen nicht gilt.

Es sei ein Symbolalphabet${\displaystyle {}S}$ einer Sprache erster Stufegegeben. Es seien ${\displaystyle {}x_{1},\ldots ,x_{k}}$ paarweise verschiedene Variablen und ${\displaystyle {}t_{1},\ldots ,t_{k}}$ fixierte${\displaystyle {}S}$-Terme.Zeige, dass zu einemallgemeingültigenAusdruck ${\displaystyle {}\alpha }$ auch die Substitution ${\displaystyle {}\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}}$ allgemeingültig ist. Gilt hiervon auch die Umkehrung?

Es seien ${\displaystyle {}u,x,y,z}$ Variablen und ${\displaystyle {}f,g}$ einstellige Funktionssymbole. Bestimme, welche der folgenden Ausdrücke untereinander äquivalent sind.

a)

1. ${\displaystyle {}\forall x\forall y((fx=fy\rightarrow x=y)\wedge (gx=gy\rightarrow x=y))}$,
2. ${\displaystyle {}\forall x\forall y(fx=fy\rightarrow x=y)\wedge \forall x\forall y(gx=gy\rightarrow x=y)}$,
3. ${\displaystyle {}\forall x\forall y\forall u\forall z((fx=fy\rightarrow x=y)\wedge (gu=gz\rightarrow u=z))}$.

b)

1. ${\displaystyle {}\forall x\exists y(fy=x)\wedge \forall x\exists y(gy=x)}$,
2. ${\displaystyle {}\forall x\exists y{\left(fy=x\wedge gy=x\right)}}$,
3. ${\displaystyle {}\forall x\exists y\forall u\exists z(fy=x\wedge gz=u)}$,
4. ${\displaystyle {}\forall x\forall u\exists y\exists z(fy=x\wedge gz=u)}$.

Es sei ${\displaystyle {}\alpha }$ ein ${\displaystyle {}S}$-Ausdruck. Zeige, dass es einen ${\displaystyle {}S}$-Ausdruck ${\displaystyle {}\beta }$ der Form ${\displaystyle {}\beta =\alpha \wedge \gamma }$ derart gibt, dass

${\displaystyle {}\operatorname {Frei} _{}^{}{\left(\beta \right)}=\operatorname {Var} _{}^{}{\left(\alpha \right)}=\operatorname {Var} _{}^{}{\left(\beta \right)}\,}$

gilt.

Es sei ${\displaystyle {}f}$ ein einstelliges Funktionssymbol. Bestimme, welche der folgenden Ausdrücke untereinander äquivalent^[1]sind.

1. ${\displaystyle {}\forall x\exists y(fx=y)}$,
2. ${\displaystyle {}\forall x\exists x(fx=x)}$,
3. ${\displaystyle {}\exists x(fx=x)}$.

Man gebe für jedes ${\displaystyle {}r\in \mathbb {N} _{+}}$ ein Beispiel für eine Substitution ${\displaystyle {}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}}$ und einen ${\displaystyle {}S}$-Ausdruck ${\displaystyle {}\alpha }$ derart, dass die sukzessive substituierten Ausdrücke

${\displaystyle \alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}},{\left(\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}},{\left({\left(\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}},\ldots }$

eine Periode der Länge ${\displaystyle {}r}$ besitzen.

Es sei ein Symbolalphabet ${\displaystyle {}S}$ einer Sprache erster Stufegegeben. Es seien ${\displaystyle {}x_{1},\ldots ,x_{k},y_{1},\ldots ,y_{\ell }}$ paarweise verschiedene Variablen und ${\displaystyle {}t_{1},\ldots ,t_{k},s_{1},\ldots ,s_{\ell }}$ fixierte${\displaystyle {}S}$-Terme.Zeige, dass für Terme ${\displaystyle {}\tau }$, in denen ${\displaystyle {}y_{1},\ldots ,y_{\ell }}$ nicht vorkommen, die Gleichheit

${\displaystyle {}{\left(\tau {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}{\frac {s_{1},\ldots ,s_{\ell }}{y_{1},\ldots ,y_{\ell }}}=\tau {\frac {t_{1}{\frac {s_{1},\ldots ,s_{\ell }}{y_{1},\ldots ,y_{\ell }}},\ldots ,t_{k}{\frac {s_{1},\ldots ,s_{\ell }}{y_{1},\ldots ,y_{\ell }}}}{x_{1},\ldots ,x_{k}}}\,}$

gilt.

Es sei ein Symbolalphabet ${\displaystyle {}S}$ einer Sprache erster Stufegegeben. Es seien ${\displaystyle {}x_{1},\ldots ,x_{k},y_{1},\ldots ,y_{\ell }}$ paarweise verschiedene Variablen und ${\displaystyle {}t_{1},\ldots ,t_{k},s_{1},\ldots ,s_{\ell }}$ fixierte${\displaystyle {}S}$-Terme.Zeige durch ein Beispiel, dass für Terme ${\displaystyle {}\tau }$ die Gleichheit

${\displaystyle {}{\left(\tau {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}{\frac {s_{1},\ldots ,s_{\ell }}{y_{1},\ldots ,y_{\ell }}}=\tau {\frac {t_{1}{\frac {s_{1},\ldots ,s_{\ell }}{y_{1},\ldots ,y_{\ell }}},\ldots ,t_{k}{\frac {s_{1},\ldots ,s_{\ell }}{y_{1},\ldots ,y_{\ell }}}}{x_{1},\ldots ,x_{k}}}\,}$

nicht gelten muss.

Es sei ein Symbolalphabet ${\displaystyle {}S}$ einer Sprache erster Stufegegeben. Es seien ${\displaystyle {}x_{1},\ldots ,x_{k},y_{1},\ldots ,y_{\ell }}$ paarweise verschiedene Variablen und ${\displaystyle {}t_{1},\ldots ,t_{k},s_{1},\ldots ,s_{\ell }}$ fixierte${\displaystyle {}S}$-Terme.Zeige durch ein Beispiel, dass für Ausdrücke ${\displaystyle {}\alpha }$ die Gleichheit(von Ausdrücken)

${\displaystyle {}{\left(\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}{\frac {s_{1},\ldots ,s_{\ell }}{y_{1},\ldots ,y_{\ell }}}=\alpha {\frac {t_{1}{\frac {s_{1},\ldots ,s_{\ell }}{y_{1},\ldots ,y_{\ell }}},\ldots ,t_{k}{\frac {s_{1},\ldots ,s_{\ell }}{y_{1},\ldots ,y_{\ell }}}}{x_{1},\ldots ,x_{k}}}\,}$

nicht gelten muss.