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

Übungsaufgaben

Aufgabe

Es sei ${}S=\{0,1,+,\cdot \}$ . Zeige, dass die Automorphismengruppen der ${}S$ -Strukturen ${}\mathbb {Q}$ und ${}\mathbb {R}$ jeweils trivial sind.

Aufgabe

Es sei ${}S=\{0,1,+,\cdot \}$ die Symbolmenge eines Körpers. Zeige, dass es einen Unterkörper ${}K\subseteq \mathbb {R}$ derart gibt, dass ${}S-\operatorname {Aut} \,K$ nicht trivial ist.

Es sei ${}S=\{0,1,+,\cdot ,\geq \}$ die Symbolmenge eines angeordneten Körpers. Zeige, dass für jeden Unterkörper ${}K\subseteq \mathbb {R}$ die Automorphismengruppe ${}S-\operatorname {Aut} \,K$ trivial ist.

Aufgabe

Es sei ${}S=\{0,1,+,\cdot ,\geq \}$ die Symbolmenge eines angeordneten Körpers. Zeige, dass es einen angeordneten Körper ${}K$ derart gibt, dass ${}S-\operatorname {Aut} \,K$ nicht trivial ist.

Aufgabe

Wir betrachten die beiden folgenden Punktkonfigurationen im ${}\mathbb {R} ^{2}$ ,

M=\{(0,0),(0,1),(1,0),(2,0)\}{\text{ und }}N=\{(0,0),(0,1),(1,0),(3,0)\}.

Zeige, dass es keine lineare Abbildung

\varphi \colon \mathbb {R} ^{2}\longrightarrow \mathbb {R} ^{2}

gibt, die ${}M$ in ${}N$ überführt. Widerspricht dies Satz 17.3?

Aufgabe

Es sei ${}S$ ein Symbolalphabet erster Stufe und ${}M$ eine ${}S$ - Struktur. Für jede elementare Äquivalenzklasse ${}[m]\subseteq M$ gebe es einen ${}S$ -Ausdruck ${}\alpha _{[m]}$ in einer freien Variablen ${}x$ , der die Klasse ${}[m]$ beschreibt. Zeige, dass für jedes ${}k$ -stellige Funktionssymbol ${}f$ aus ${}m_{1}\sim m_{1}',\ldots ,m_{k}\sim m_{k}'$ die elementare Äquivalenz ${}f^{M}(m_{1},\ldots ,m_{k})\sim f^{M}(m'_{1},\ldots ,m'_{k})$ folgt.

Aufgabe

Es sei ${}S$ ein Symbolalphabet erster Stufe und ${}M$ eine ${}S$ - Struktur. Für jede elementare Äquivalenzklasse ${}[m]\subseteq M$ gebe es einen ${}S$ -Ausdruck ${}\alpha _{[m]}$ in einer freien Variablen ${}x$ , der die Klasse ${}[m]$ beschreibt. Zeige, dass für ein ${}k$ -stelliges Funktionssymbol ${}f$ aus ${}m_{1}\sim m_{1}',\ldots ,m_{k}\sim m_{k}'$ nicht die Gleichheit ${}f^{M}(m_{1},\ldots ,m_{k})=f^{M}(m'_{1},\ldots ,m'_{k})$ folgen muss.

Aufgabe

Es sei ${}S$ das Symbolalphabet, das außer Variablen für jedes ${}k\in \mathbb {N} _{+}$ ein einstelliges Relationssymbol ${}R_{k}$ enthält. Wir betrachten die Menge ${}M=\mathbb {N} _{+}$ , wobei wir das Relationssymbol ${}R_{k}$ durch

R_{k}^{M}(n){\text{ genau dann, wenn }}n{\text{ ein Vielfaches von }}k{\text{ ist }}

interpretieren. Es sei ${}\alpha \in L^{S}$ ein Ausdruck in einer freien Variablen ${}x$ , wobei in ${}\alpha$ die Relationssymbole ${}R_{k_{1}},\ldots ,R_{k_{m}}$ vorkommen mögen. Es sei ${}k$ das kleinste gemeinsame Vielfache von ${}k_{1},\ldots ,k_{m}$ . Zeige, dass

M{\frac {n}{x}}\vDash \alpha

genau dann gilt, wenn

M{\frac {n+k}{x}}\vDash \alpha

gilt.

Aufgabe

Es sei ${}f$ ein zweistelliges Funktionssymbol und ${}g$ ein einstelliges Funktionssymbol. Man mache sich klar, dass die Symbolkette ${}fggg$ in zweifacher Weise als formal-zusammengesetztes Funktionssymbol gelesen werden kann.

Aufgabe

Es sei ${}S$ ein erststufiges Symbolalphabet, ${}M$ eine ${}S$ - Struktur und ${}T\subseteq M$ eine Teilmenge. Zeige, dass die (rekursiv definierte) funktionale Hülle von ${}T$ gleich dem Durchschnitt über alle funktional abgeschlossenen Teilmengen ${}N\subseteq M$ ist, die ${}T$ umfassen.

In der Mathematik interessiert man sich nicht nur für die von einer Teilmenge einer Struktur erzeugte funktionale Hülle, sondern auch für Unterstrukturen, in denen zusätzlich noch die gleichen Gesetzmäßigkeiten (ausgedrückt durch ein Axiomensystem ${}\Gamma$ ) wie in der Struktur gelten, beispielsweise die von einer Teilmenge erzeugten Untergruppen, Unterringe, Unterkörper, Untervektorräume. Diese von einer Teilmenge erzeugten ${}S-\Gamma$ -Strukturen kann man oft, wenn es sie überhaupt gibt, als Durchschnitt über alle ${}S-\Gamma$ -Unterstrukturen erhalten, die die Teilmenge umfassen.

Aufgabe

Wir betrachten die Gruppe ${}(\mathbb {Z} ,0,+)$ . Bestimme die funktionale Hülle von ${}T=\{15,20\}$ (hier spricht man vom erzeugten Untermonoid) und die von ${}T$ erzeugte Untergruppe.

Aufgabe

Das Symbolalphabet ${}S$ bestehe neben Variablen aus einem einstelligen Funktionssymbol ${}f$ und es sei ${}\Gamma =\{\alpha \}$ mit ${}\alpha =\forall x\exists y(fy=x)$ . Es sei ${}M=\mathbb {Z}$ , wobei ${}f$ als ${}+2$ interpretiert wird mit der einzigen Ausnahme

{}f(x)={\begin{cases}x+1,{\text{ falls }}x\geq 0\,,\\0,{\text{ falls }}x=-1\,,\\x+2,{\text{ falls }}x\leq -2\,.\end{cases}}\,

a) Zeige, dass ${}\Gamma$ von ${}M$ erfüllt wird.

b) Bestimme die funktionale Hülle von ${}\{0\}$ .

c) Zeige, dass die funktionale Hülle von ${}\{0\}$ nicht ${}\Gamma$ erfüllt.

d) Man gebe zwei funktional abgeschlossene, ${}\Gamma$ -erfüllende und ${}0$ enthaltende Teilmengen ${}T_{1},T_{2}\subseteq \mathbb {Z}$ an, deren Durchschnitt ${}T_{1}\cap T_{2}$ nicht ${}\Gamma$ erfüllt.

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Es sei ${}S$ ein Symbolmenge und ${}M$ eine endliche ${}S$ - Struktur. Zeige, dass zwei Elemente ${}m,n\in M$ genau dann elementar äquivalent sind, wenn es einen ${}S$ - Automorphismus

\varphi \colon M\longrightarrow M

mit ${}\varphi (m)=n$ gibt.

Aufgabe (4 Punkte)

Zeige, dass ein angeordneter Körper, der die Supremumseigenschaft für erststufige Ausdrücke besitzt, reell-abgeschlossen ist.

Verwende, dass Polynomfunktionen auf einem angeordneten Körper stetig sind.

Aufgabe (4 Punkte)

Es sei ${}S$ das Symbolalphabet, das neben Variablen aus einem zweistelligen Relationssymbol ${}G$ besteht. Wir betrachten vierelementige ${}S$ - Strukturen, die ${}\forall x\forall y{\left(Gxy\rightarrow \neg Gyx\right)}$ erfüllen (also WM-Fußballgruppen, wobei ${}G(m,n)$ als ${}m$ gewinnt gegen ${}n$ interpretiert wird). Erstelle Aussagen ${}\alpha _{0},\alpha _{1},\ldots ,\alpha _{9}$ in einer freien Variablen ${}x$ derart, dass