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

Übungsaufgaben

Aufgabe

Bestimme die funktionale Hülle zu einem Element ${}x\in M$ , wobei auf ${}M$ eine Permutation ${}\pi$ fixiert sei.

Es sei ${}S$ ein Symbolalphabet, das neben Variablen aus einer Konstanten ${}e$ und einem einzigen zweistelligen Funktionssymbol ${}f$ bestehe. Es sei ${}G$ eine endliche Gruppe, wobei ${}e$ als neutrales Element und ${}f$ als die Verknüpfung interpretiert werde. Zeige, dass die funktionale Hülle zu einem Element ${}g\in G$

mit der von  ${}g$

erzeugten Untergruppe übereinstimmt.

Aufgabe

Erstelle Funktionssymbolstammbäume, die den arithmetischen Ausdrücken

(x+y)z,\,xz+yz,\,x^{3}+yz^{2}

entsprechen.

Aufgabe

Definiere einen Isomorphismus auf ${}\{1,2,\ldots ,10\}$ zur Permutation

${}x$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$	${}9$	${}10$
${}\pi (x)$	${}4$	${}9$	${}3$	${}10$	${}8$	${}5$	${}2$	${}6$	${}7$	${}1$

anhand von Satz 17.6, wobei im ersten Schritt ${}4$ auf ${}6$ abgebildet werden soll.

Aufgabe

Bestimme die Automorphismengruppe zu einer fixierten Permutation ${}\pi$ auf einer endlichen Menge ${}M$ .

Aufgabe

Es sei ${}M=\mathbb {Z} /(12)$ , aufgefasst als Gruppe. Definiere entlang von Satz 17.6 einen Isomorphismus

\varphi \colon \mathbb {Z} /(12)\longrightarrow \mathbb {Z} /(12),

startend mit ${}S_{1}=\{0\}$ und weiter mit ${}S_{2}$ , wobei ${}S_{2}$ die funktionale Hülle von ${}0$ und ${}m_{2}=3$ sei, und ${}n_{2}$ als ${}9$ gewählt wird, etc. Welche Wahlmöglichkeiten hat man für ${}\varphi _{3}(m_{3})$ mit ${}m_{3}=1$ ?

Aufgabe

Definiere die Stelligkeit für ein formal-zusammengesetztes Funktionssymbol.

Aufgabe

Zeige, dass eine funktional abgeschlossene Teilmenge ${}T\subseteq M$ einer ${}S$ - Struktur ${}M$ auch unter jedem formal-zusammengesetzten Funktionssymbol abgeschlossen ist.

Aufgabe

Wir betrachten das Symbolalphabet ${}S$ , welches neben Variablen aus ${}0,1,+,\cdot$ besteht, mit der Standardinterpretation auf ${}\mathbb {R}$ . Bestimme die funktionale Hülle der einzelnen Elemente ${}1,3{\sqrt {7}},e,\pi$ . Welche sind untereinander ${}S$ - isomorph, welche nicht?

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.

Aufgabe

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 *

Es sei

{}S=\{0,1,+,\cdot ,\geq \}\,

das Symbolalphabet für einen angeordneten Körper und es sei ${}\mathbb {R}$ die ${}S$ - Struktur mit der Standardinterpretation.

Zeige, dass die Äquivalenzklassen zur elementaren Äquivalenz einelementig sind.
Zeige, dass es für die Elemente im Allgemeinen keinen charakterisierenden Ausdruck gibt.

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.6?

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.

Zu einer ${}S$ -Struktur ${}M$ und einer ${}S$ -Unterstruktur ${}N\subseteq M$ versteht man unter der relativen ${}S$ -Automorphismengruppe von ${}M$ bezüglich ${}N$ die Menge der ${}S$ - Automorphismen auf ${}M$ , die die Elemente aus ${}N$ in sich überführen. Sie wird mit ${}S-\operatorname {Aut} _{N}\,M$ bezeichnet.

Aufgabe

Es sei ${}S$ ein Symbolalphabet, ${}M$ eine ${}S$ - Struktur und ${}N\subseteq M$ eine ${}S$ - Unterstruktur. Zeige, dass die relative Automorphismengruppe ${}S-\operatorname {Aut} _{N}\,M$ eine Untergruppe der Automorphismengruppe ${}S-\operatorname {Aut} \,M$ ist.

Aufgabe

Interpretiere die Galoisgruppe zu einer Körpererweiterung ${}K\subseteq L$ als eine relative Automorphismengruppe zu einem geeigneten Symbolalphabet. Welche Rolle spielen dabei die Körperaxiome?

Aufgabe

Es sei ${}S$ ein Symbolalphabet, ${}M$ eine ${}S$ - Struktur und ${}N\subseteq M$ eine ${}S$ - Unterstruktur. Zeige, dass man durch eine Symbolmengenerweiterung ${}S\subseteq S'$ , wobei nur Konstanten hinzugenommen werden, erreichen kann, dass die relative Automorphismengruppe ${}S-\operatorname {Aut} _{N}\,M$ der ${}S'$ - Automorphismengruppe ${}S'-\operatorname {Aut} \,M$ entspricht (dazu muss insbesondere ${}S'$ auf ${}M$ und ${}N$ interpretiert werden).

Wir erinnern an die Definition eines algebraisch abgeschlossenen Körpers. Die komplexen Zahlen ${}{\mathbb {C} }$ sind algebraisch abgeschlossen (Fundamentalsatz der Algebra), die reellen Zahlen ${}\mathbb {R}$ nicht.

Ein Körper ${}K$ heißt algebraisch abgeschlossen, wenn jedes nichtkonstante Polynom ${}F\in K[X]$ eine Nullstelle in ${}K$ besitzt.

Aufgabe

Definiere über der Symbolmenge ${}\{0,1,+,\cdot \}$ einen algebraisch abgeschlossenen Körper mit Hilfe eines Axiomenschemas.

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