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

\setcounter{section}{17}

\zwischenueberschrift{Übungsaufgaben}

\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.

}
{} {}

\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.3?

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ das Symbolalphabet, das außer Variablen für jedes
\mathl{k \in \N_+}{} ein einstelliges Relationssymbol $R_k$ enthält. Wir betrachten die Menge
\mathl{M=\N_+}{,} wobei wir das Relationssymbol $R_k$ durch
\mathdisp {R_k^M (n) \text{ genau dann, wenn } n \text{ ein Vielfaches von } k \text{ ist }} { }
interpretieren. Es sei
\mathl{\alpha \in L^S}{} ein Ausdruck in einer freien Variablen $x$, wobei in $\alpha$ die Relationssymbole
\mathl{R_{k_1} , \ldots , R_{k_m}}{} vorkommen mögen. Es sei $k$ das \definitionsverweis {kleinste gemeinsame Vielfache}{}{} von
\mathl{k_1 , \ldots , k_m}{.} Zeige, dass
\mathdisp {M { \frac{ n }{ x } } \vDash \alpha} { }
genau dann gilt, wenn
\mathdisp {M { \frac{ n+k }{ x } } \vDash \alpha} { }
gilt.

}
{} {}

\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.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{}
{

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
{}
{

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
{}
{

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
{}
{

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

}
{} {}