Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/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 die Stelligkeit für ein formal-zusammengesetztes Funktionssymbol.
}
{} {}
\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
{}
{
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?
}
{} {}
\inputaufgabegibtloesung
{}
{
Es sei $S$ ein Symbolalphabet ohne Funktionssymbole und sei $M$ eine endliche $S$-\definitionsverweis {Struktur}{}{.} \aufzaehlungzwei {Charakterisiere die Automorphismengruppe von $M$ mit Hilfe der \definitionsverweis {elementaren Äquivalenzklassen}{}{.} } {Beweise Satz 17.6 in diesem Fall. }
}
{} {}
\inputaufgabe
{}
{
Es sei $S$ ein Symbolalphabet und sei $M$ eine endliche $S$-\definitionsverweis {Struktur}{}{} mit der Eigenschaft, dass alle \definitionsverweis {elementaren Äquivalenzklassen}{}{} einelementig seien. Beweise Satz 17.6 in diesem Fall.
}
{} {}
\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
{}
{
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
{}
{
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 $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}
{
Wir betrachten die
\definitionsverweis {Gruppe}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{ \Z/(2) \times \Z/(4)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Zeige, dass es in $G$ zueinander
\definitionsverweis {isomorphe}{}{}
\definitionsverweis {Untergruppen}{}{}
\mavergleichskette
{\vergleichskette
{H,H'
}
{ \subseteq }{G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
derart gibt, dass man einen Isomorphismus
\maabb {} {H} {H'
} {}
nicht zu einem
\definitionsverweis {Automorphismus}{}{}
auf $G$ fortsetzen kann. Sind diese Untergruppen elementar unterscheidbar?
}
{} {}
\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.
}
{} {}