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

Übungsaufgaben

Aufgabe Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

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 Referenznummer erstellen

Erstelle Funktionssymbolstammbäume, die den arithmetischen Ausdrücken

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

entsprechen.

Aufgabe Referenznummer erstellen

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 Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

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 Referenznummer erstellen

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

Aufgabe Aufgabe 17.8 ändern

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

Aufgabe Referenznummer erstellen

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 Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 * Referenznummer erstellen

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.

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

Aufgabe Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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

Aufgaben zum Abgeben

Aufgabe (3 Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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

$M{\frac {m}{x}}\vDash \alpha _{k}$

bedeutet, dass ${}m$ in der Abschlusstabelle ${}k$ Punkte hat.

Aufgabe (3 Punkte)Referenznummer erstellen

Man gebe ein Beispiel für zwei (abstrakte) WM-Fußballgruppen, die die gleiche Abschlusspunktetabelle besitzen, aber nicht isomorph sind.