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

\setcounter{section}{17}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

mit der von $g$ 

\definitionsverweis {erzeugten Untergruppe}{}{} übereinstimmt.

}
{} {}

\inputaufgabe
{}
{

Erstelle Funktionssymbolstammbäume, die den arithmetischen Ausdrücken
\mathdisp {(x+y) z,\, xz +yz,\, x^3+yz^2} { }
entsprechen.

}
{} {}

\inputaufgabe
{}
{

Definiere einen \definitionsverweis {Isomorphismus}{}{} auf
\mathl{\{1,2 , \ldots , 10 \}}{} zur Permutation \wertetabellezehnausteilzeilen { $x$ }
{\mazeileundfuenf {1} {2} {3} {4} {5} }
{\mazeileundfuenf {6} {7} {8} {9} {10} }
{ $\pi(x)$ }
{\mazeileundfuenf {4} {9} {3} {10} {8} }
{\mazeileundfuenf {5} {2} {6} {7} {1} } anhand von Satz 17.6, wobei im ersten Schritt $4$ auf
\mathl{6}{} abgebildet werden soll.

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{M }
{ = }{ \Z/(12) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} aufgefasst als Gruppe. Definiere entlang von Satz 17.6 einen Isomorphismus \maabbdisp {\varphi} {\Z/(12) } {\Z/(12) } {,} startend mit
\mavergleichskette
{\vergleichskette
{S_1 }
{ = }{ \{0\} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und weiter mit $S_2$, wobei $S_2$ die funktionale Hülle von \mathkor {} {0} {und} {m_2 = 3} {} sei, und $n_2$ als $9$ gewählt wird, etc. Welche Wahlmöglichkeiten hat man für
\mathl{\varphi_3(m_3)}{} mit
\mavergleichskette
{\vergleichskette
{m_3 }
{ = }{1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{?}

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabegibtloesung
{}
{

Es sei
\mavergleichskettedisp
{\vergleichskette
{ S }
{ =} { \{0,1,+,\cdot, \geq \} }
{ } { }
{ } { }
{ } { }
} {}{}{} das \definitionsverweis {Symbolalphabet}{}{} für einen \definitionsverweis {angeordneten Körper}{}{} und es sei $\R$ die $S$-\definitionsverweis {Struktur}{}{} mit der Standardinterpretation. \aufzaehlungzwei {Zeige, dass die Äquivalenzklassen zur \definitionsverweis {elementaren Äquivalenz}{}{} einelementig sind. } {Zeige, dass es für die Elemente im Allgemeinen keinen charakterisierenden Ausdruck gibt. }

}
{} {}

\inputaufgabe
{}
{

Wir betrachten die beiden folgenden Punktkonfigurationen im $\R^2$,
\mathdisp {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 \maabbdisp {\varphi} {\R^2} { \R^2 } {} gibt, die $M$ in $N$ überführt. Widerspricht dies Satz 17.6?

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein erststufiges Symbolalphabet, $M$ eine $S$-\definitionsverweis {Struktur}{}{} und
\mathl{T \subseteq M}{} eine Teilmenge. Zeige, dass die \zusatzklammer {rekursiv definierte} {} {} \definitionsverweis {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 \zusatzklammer {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.

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

Das Symbolalphabet $S$ bestehe neben Variablen aus einem einstelligen Funktionssymbol $f$ und es sei
\mathl{\Gamma=\{ \alpha \}}{} mit
\mavergleichskette
{\vergleichskette
{ \alpha }
{ = }{ \forall x \exists y (fy = x) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Es sei $M= \Z$, wobei $f$ als $+2$ interpretiert wird mit der einzigen Ausnahme
\mavergleichskettedisp
{\vergleichskette
{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
\mathl{T_1,T_2 \subseteq \Z}{} an, deren Durchschnitt
\mathl{T_1 \cap T_2}{} nicht $\Gamma$ erfüllt.

}
{} {}

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

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {Symbolalphabet}{}{,} $M$ eine $S$-\definitionsverweis {Struktur}{}{} und
\mavergleichskette
{\vergleichskette
{N }
{ \subseteq }{M }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine $S$-\definitionsverweis {Unterstruktur}{}{.} Zeige, dass man durch eine Symbolmengenerweiterung
\mavergleichskette
{\vergleichskette
{S }
{ \subseteq }{S' }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} wobei nur Konstanten hinzugenommen werden, erreichen kann, dass die relative Automorphismengruppe
\mathl{S-\operatorname{Aut}_N \, M}{} der $S'$-\definitionsverweis {Automorphismengruppe}{}{}
\mathl{S'-\operatorname{Aut} \, M}{} entspricht \zusatzklammer {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 \zusatzklammer {Fundamentalsatz der Algebra} {} {,} die reellen Zahlen $\R$ nicht.

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

\inputaufgabe
{}
{

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

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{3}
{

Es sei $S$ ein Symbolmenge und $M$ eine \definitionsverweis {endliche}{}{} $S$-\definitionsverweis {Struktur}{}{.} Zeige, dass zwei Elemente
\mathl{m,n \in M}{} genau dann \definitionsverweis {elementar äquivalent}{}{} sind, wenn es einen $S$-\definitionsverweis {Automorphismus}{}{} \maabbdisp {\varphi} {M} {M } {} mit
\mavergleichskette
{\vergleichskette
{\varphi(m) }
{ = }{n }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gibt.

}
{} {}

\inputaufgabe
{4}
{

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

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

\inputaufgabe
{4}
{

Es sei $S$ das Symbolalphabet, das neben Variablen aus einem zweistelligen Relationssymbol $G$ besteht. Wir betrachten vierelementige $S$-\definitionsverweis {Strukturen}{}{,} die
\mathl{\forall x \forall y { \left( Gxy \rightarrow \neg Gyx \right) }}{} erfüllen \zusatzklammer {also WM-Fußballgruppen, wobei $G(m,n)$ als $m$ gewinnt gegen $n$ interpretiert wird} {} {.} Erstelle Aussagen
\mathl{\alpha_0, \alpha_1 , \ldots , \alpha_9}{} in einer freien Variablen $x$ derart, dass
\mathdisp {M { \frac{ m }{ x } } \vDash \alpha_k} { }
bedeutet, dass $m$ in der Abschlusstabelle $k$ Punkte hat.

}
{} {}

\inputaufgabe
{3}
{

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

}
{} {}