Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/Arbeitsblatt 16/latex
\setcounter{section}{16}
\zwischenueberschrift{Übungsaufgaben}
\inputaufgabe
{}
{
Es sei $S$ ein
\definitionsverweis {erststufiges Symbolalphabet}{}{}
und
\mathl{L,M,N}{} seien
$S$-\definitionsverweis {Strukturen}{}{.}
Zeige folgende Aussagen.
\aufzaehlungdrei{Die Identität
\maabbdisp {\operatorname{Id}_{ M }} {M} {M
} {}
ist ein
\definitionsverweis {Isomorphismus}{}{.}
}{Zu einem Isomorphismus
\maabbdisp {\varphi} {M} {N
} {}
ist die Umkehrabbildung
\maabbdisp {\varphi^{-1}} {N} {M
} {}
ein Isomorphismus.
}{Es seien
\maabbdisp {\psi} { L} {M
} {}
und
\maabbdisp {\varphi} { M} {N
} {}
Homomorphismen
\zusatzklammer {Isomorphismen} {} {.}
Dann ist auch die
\definitionsverweis {Hintereinanderschaltung}{}{}
\mathl{\varphi \circ \psi}{}
ein Homomorphismus
\zusatzklammer {Isomorphismus} {} {.}
}
}
{} {}
\inputaufgabe
{}
{
Zeige, dass die Begriffe \definitionsverweis {Gruppenhomomorphismus}{}{,} \definitionsverweis {Ringhomomorphismus}{}{,} \definitionsverweis {monotone Abbildung zwischen geordneten Mengen}{}{} und \definitionsverweis {lineare Abbildung}{}{} unter den \definitionsverweis {abstrakten Homomorphiebegriff}{}{} \zusatzklammer {über welchem \definitionsverweis {erststufigen Symbolalphabet}{}{} $S$?} {} {} fallen.
}
{} {}
\inputaufgabe
{}
{
Es sei $S$ ein \definitionsverweis {erststufiges Symbolalphabet}{}{,} das keine Relationssymbole enthalte. Zeige, dass ein \definitionsverweis {bijektiver}{}{} $S$-\definitionsverweis {Homomorphismus}{}{} zwischen zwei $S$-\definitionsverweis {Strukturen}{}{} bereits ein $S$-\definitionsverweis {Isomorphismus}{}{} ist.
}
{} {}
Die nächste Aufgabe verwendet die folgende Definition.
Es seien
\mathkor {} {(M_1, \leq_1)} {und} {(M_2, \leq_2)} {}
zwei Mengen, auf denen jeweils eine
\definitionsverweis {Ordnung}{}{}
definiert ist. Eine
\definitionsverweis {Abbildung}{}{}
\maabbeledisp {F} {M_1} {M_2
} {x} {F(x)
} {,}
heißt \definitionswort {ordnungstreu}{}
\zusatzklammer {oder \definitionswort {monoton}{}} {} {,}
wenn für alle
\mavergleichskette
{\vergleichskette
{x,x'
}
{ \in }{M_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{x
}
{ \leq_1 }{x'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
stets auch
\mavergleichskette
{\vergleichskette
{F(x)
}
{ \leq_2 }{F(x')
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
\inputaufgabe
{}
{
Es sei $(M, \leq)$ eine \definitionsverweis {geordnete Menge}{}{} und $\mathfrak {P} \, (M )$ die \definitionsverweis {Potenzmenge}{}{} von $M$. Zeige, dass die Abbildung \maabbeledisp {} {M} {\mathfrak {P} \, (M ) } {x} {{ \left\{ y \in M \mid y \leq x \right\} } } {,} \definitionsverweis {ordnungstreu}{}{} und \definitionsverweis {injektiv}{}{} ist, wobei die Potenzmenge mit der \definitionsverweis {Inklusion}{}{} versehen ist.
}
{} {}
\inputaufgabe
{}
{
Es sei
\mathl{M}{} die Menge aller unendlichen Teilmengen von $\N_+$, versehen mit der Inklusion als
\definitionsverweis {Ordnung}{}{,}
und es sei
\mathl{[0,1[}{} das rechtsseitig offene
\definitionsverweis {reelle Einheitsintervall}{}{}
mit der Kleinergleich-Relation als Ordnung. Zeige, dass die Abbildung
\maabbeledisp {\Psi} {M} {[0,1[
} {T} { \sum_{n \not \in T} { \left( { \frac{ 1 }{ 2 } } \right) }^n
} {,}
eine bijektive,
\definitionsverweis {ordnungstreue}{}{}
Abbildung ist, deren Umkehrabbildung nicht ordnungstreu ist.
}
{Warum beschränkt man sich auf unendliche Teilmengen? Wie sehen die \anfuehrung{transportierten Ordnungen}{} aus?} {}
\inputaufgabe
{}
{
Es sei $S$ ein Symbolalphabet, das neben Variablen aus einem einzigen einstelligen Relationssymbol besteht. Was bedeutet ein $S$-\definitionsverweis {Homomorphismus}{}{?} Welche mathematische Signifikanz hat dieser Begriff?
}
{} {}
\inputaufgabe
{}
{
Es sei $S$ ein Symbolalphabet, das neben Variablen aus einem einzigen einstelligen Funktionssymbol besteht. Was bedeutet ein $S$-\definitionsverweis {Homomorphismus}{}{?} Welche mathematische Signifikanz hat dieser Begriff?
}
{} {}
\inputaufgabe
{}
{
Es sei $S$ ein \definitionsverweis {Symbolalphabet erster Stufe}{}{.} Definiere eine $S$-\anfuehrung{Unterstruktur}{} in einer $S$-\definitionsverweis {Struktur}{}{} $M$.
}
{} {}
\inputaufgabegibtloesung
{}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und $L^S$ die zugehörige Sprache erster Stufe. Es sei $I$ eine
$S$-\definitionsverweis {Interpretation}{}{}
mit der Grundmenge $N$ und es sei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \defeq }{ I^\vDash
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit der
\definitionsverweis {zugehörigen Äquivalenzrelation}{}{}
$\sim$ auf der Termmenge $T$.
\aufzaehlungvier{Zeige, dass
\mavergleichskette
{\vergleichskette
{s
}
{ \sim }{t
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
genau dann gilt, wenn
\mavergleichskette
{\vergleichskette
{I(s)
}
{ = }{I(t)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}{Zeige, dass es eine injektive Abbildung
\maabbdisp {\psi} {T/\sim } { N
} {}
mit
\mavergleichskettedisp
{\vergleichskette
{ \psi([t])
}
{ =} { I(t)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gibt.
}{Zeige, dass $\psi$ ein
$S$-\definitionsverweis {Homomorphismus}{}{}
ist, wenn die Quotientenmenge
\mathl{T/\sim}{} mit der kanonischen
$S$-\definitionsverweis {Struktur}{}{}
versehen wird.
}{Es sei $J$ die kanonische Interpretation auf $T/\sim$. Es sei vorausgesetzt, dass die Terminterpretation für $N$ surjektiv sei. Zeige, dass
\mathl{I \vDash \alpha}{} genau dann gilt, wenn
\mathl{J \vDash \alpha}{} gilt.
}
}
{} {}
\inputaufgabe
{}
{
Es sei $S$ ein
\definitionsverweis {erststufiges Symbolalphabet}{}{,}
\mathkor {} {M} {und} {N} {}
seien
$S$-\definitionsverweis {Strukturen}{}{}
und
\maabbdisp {\varphi} {M} {N
} {}
ein
\definitionsverweis {Homomorphismus}{}{.}
Es sei $\lambda$ eine
\definitionsverweis {Variablenbelegung}{}{}
in $M$ und $\varphi \circ \lambda$ die nach $N$ übertragene Variablenbelegung. Es seien
\mathkor {} {I} {und} {J} {}
die zugehörigen Interpretationen. Zeige, dass
\mavergleichskettedisp
{\vergleichskette
{\varphi(I(t))
}
{ =} {J(t)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
$S$-\definitionsverweis {Terme}{}{}
$t$ gilt.
}
{} {}
Unter einem \stichwort {Automorphismus} {} einer $S$-Struktur $M$ versteht man einen Isomorphismus von $M$ nach $M$. Man spricht von der $S$-\stichwort {Automorphismengruppe} {} von $M$, geschrieben
\mathl{S-\operatorname{Aut} \, M}{.}
\inputaufgabe
{}
{
Es sei $S$ ein
\definitionsverweis {erststufiges Symbolalphabet}{}{}
und
\mathl{M}{} sei eine
$S$-\definitionsverweis {Struktur}{}{.}
Zeige, dass die Menge der $S$-Automorphismen auf $M$ eine
\definitionsverweis {Gruppe}{}{}
bildet.
}
{} {}
\inputaufgabe
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{ S
}
{ = }{ \{0,+\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und $\Z$ sei versehen mit der natürlichen
$S$-\definitionsverweis {Interpretation}{}{.}
Bestimme die
$S$-\definitionsverweis {Automorphismengruppe}{}{}
von $\Z$.
}
{} {}
\inputaufgabe
{}
{
Bestimme die \definitionsverweis {Automorphismengruppe}{}{} zu einer fixierten \definitionsverweis {Permutation}{}{} $\pi$ auf einer endlichen Menge $M$.
}
{} {}
\inputaufgabe
{}
{
Es sei $S$ ein
\definitionsverweis {erststufiges Symbolalphabet}{}{}
und $M$ eine
$S$-\definitionsverweis {Struktur}{}{.}
Zeige, dass die
\definitionsverweis {elementare Äquivalenz}{}{}
von Elementen
\mathl{m,n \in M}{} eine Äquivalenzrelation auf $M$ ist.
}
{} {}
\inputaufgabe
{}
{
Wir betrachten das Spiel Schnick Schnack Schnuck mit den Objekten Schere, Stein, Papier, Brunnen. Charakterisiere jedes Objekt mit einem Ausdruck, in dem nur auf die Gewinnrelation Bezug genommen wird.
}
{} {}
\inputaufgabe
{}
{
In einer Wohngemeinschaft wohnen Albert, Beowulf, Clara, Dora, Emil und Gundula. Dabei können Albert und Beowulf kochen, die anderen vier nicht. Emil findet Beowulf doof, Dora findet Albert und Clara doof, Clara und Gundula finden beide ebenfalls den Albert doof. Charakterisiere jede Person durch einen sprachlichen Ausdruck, in dem nur auf die Kochfähigkeit und das Dooffinden Bezug genommen wird.
}
{} {}
\inputaufgabegibtloesung
{}
{
In einer Wohngemeinschaft leben die Personen
\mathl{A,B,C,D,E}{.} Wir betrachten die folgenden Relationen:
\aufzaehlungdrei{
\mathl{Txy}{} bedeutet, dass $x$ und $y$ manchmal miteinander Tennis spielen,
}{
\mathl{Sxyz}{} bedeutet, dass $x,y$ und $z$ manchmal miteinander Skat spielen,
}{
\mathl{Kxyzw}{} bedeutet, dass $x,y,z$ und $w$ manchmal miteinander Doppelkopf spielen.
}
In der WG gilt
\mathdisp {TDE, SABC, SABE, KACED} { . }
\aufzaehlungfuenf{Charakterisiere umgangssprachlich die Person $D$ allein unter Bezugnahme auf die gegebenen Spielrelationen.
}{Charakterisiere umgangssprachlich die Person $C$ allein unter Bezugnahme auf die gegebenen Spielrelationen.
}{Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen
\mathl{T,S,K}{} die Person $A$.
}{Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen
\mathl{T,S,K}{} die Person $B$.
}{Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen
\mathl{T,S,K}{} die Person $E$.
}
}
{} {}
\inputaufgabe
{}
{
Es sei $S$ ein
\definitionsverweis {erststufiges Symbolalphabet}{}{,}
das nur aus einer Variablenmenge besteht, die Konstantenmenge und die Mengen der Funktionssymbole und der Relationssymbole seien also leer. Zeige, dass je zwei Elemente
\mathl{m,n \in M}{}
\definitionsverweis {elementar äquivalent}{}{}
sind.
}
{} {}
\inputaufgabe
{}
{
Es sei $S$ ein Symbolalphabet, das neben Variablen aus einem einzigen einstelligen Funktionssymbol $f$ besteht und es sei
\mavergleichskette
{\vergleichskette
{M
}
{ = }{ \{1 , \ldots , 8\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
$S$-\definitionsverweis {Struktur}{}{,}
wobei $f$ als die
\definitionsverweis {Permutation}{}{}
$\pi$ mit \wertetabelleachtausteilzeilen { $x$ }
{\mazeileundfuenf {1} {2} {3} {4} {5} }
{\mazeileunddrei {6} {7} {8} }
{ $\pi(x)$ }
{\mazeileundfuenf {2} {5} {6} {8} {4} }
{\mazeileunddrei {3} {1} {7} }
interpretiert werde. Bestimme die
\definitionsverweis {elementar äquivalenten}{}{}
Elemente von $M$.
}
{} {}
\inputaufgabegibtloesung
{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Tred-G.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Tred-G.svg } {} {Dmitry_Dzhus} {Commons} {gemeinfrei} {}
Charakterisiere den Punkt $d$ im skizzierten Graphen mit einem Ausdruck in einer freien Variablen $x$ über dem Symbolalphabet, das neben Variablen aus einem einzigen zweistelligen Relationssymbol $R$ besteht, das im angegebenen Modell durch einen Pfeil wiedergegeben wird.
}
{} {}
\inputaufgabe
{}
{
Wir betrachten das
\definitionsverweis {Symbolalphabet}{}{}
\mavergleichskette
{\vergleichskette
{ S
}
{ = }{\{ +,0\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit der natürlichen Interpretation auf $\N$. Zeige, dass jedes Element nur zu sich selbst
\definitionsverweis {elementar äquivalent}{}{}
ist.
}
{} {}
\inputaufgabe
{}
{
Es seien die
\definitionsverweis {Symbolalphabete}{}{}
\mavergleichskette
{\vergleichskette
{ S
}
{ = }{\{ +,0\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
\mavergleichskette
{\vergleichskette
{ T
}
{ = }{\{ +,0,1 \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
und
\mavergleichskette
{\vergleichskette
{R
}
{ = }{ \{0,1,+,\cdot \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gegeben, die wir auf $\Z$ natürlich interpretieren. Bestimme zu diesen Symbolalphabeten jeweils die
\definitionsverweis {Äquivalenzklassen}{}{}
zur
\definitionsverweis {elementaren Äquivalenz}{}{.}
}
{} {}
\inputaufgabe
{}
{
Bestimme die
\definitionsverweis {Äquivalenzklassen}{}{}
zur
\definitionsverweis {elementaren Äquivalenz}{}{}
in der
\definitionsverweis {zyklischen Gruppe}{}{}
\mathl{\Z/(4)}{} zum Symbolalphabet
\mathl{S= \{ 0, +\}}{.}
}
{} {}
\inputaufgabegibtloesung
{}
{
Bestimme die
\definitionsverweis {Äquivalenzklassen}{}{}
zur
\definitionsverweis {elementaren Äquivalenz}{}{}
in der
\definitionsverweis {Gruppe}{}{}
\mathl{\Z/(2) \times \Z/(2)}{} zum Symbolalphabet
\mavergleichskette
{\vergleichskette
{S
}
{ = }{ \{ 0,+ \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
{} {}
\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 $S$ das Symbolalphabet, das neben Variablen aus einem zweistelligen Relationssymbol $G$ besteht und es sei
\mavergleichskettedisp
{\vergleichskette
{\Gamma
}
{ =} { \{ \forall x \forall y { \left( Gxy \rightarrow \neg Gyx \right) } \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Zeige, dass eine vierelementige
$S$-\definitionsverweis {Struktur}{}{,}
die $\Gamma$ erfüllt, äquivalent zur Gewinnstruktur in einer Vorgruppe bei einer Fußballweltmeisterschaft ist.
}
{(Bemerkung: Eine zweistellige Relation wird oft durch ein Pfeildiagramm veranschaulicht.)} {}
\inputaufgabe
{}
{
Es sei $S$ das Symbolalphabet, das neben Variablen aus einem zweistelligen Relationssymbol $G$ besteht und es sei
\mavergleichskettedisp
{\vergleichskette
{M
}
{ =} {\{ \text{Bra},\text{Kam},\text{Kro},\text{Mex} \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die
$S$-\definitionsverweis {Struktur}{}{,}
bei der $G(m,n)$ als $m$ gewinnt gegen $n$
\zusatzklammer {bei der Fußballweltmeisterschaft 2014} {} {}
interpretiert wird. Bestimme die Äquivalenzklassen zur elementaren Äquivalenz, charakterisierende Ausdrücke und die Automorphismengruppe.
}
{} {}
\inputaufgabe
{}
{
Es sei $S$ das Symbolalphabet, das neben Variablen aus einem zweistelligen Relationssymbol $G$ besteht. Wir betrachten Modelle, die aus einer vierelementigen Menge $M$ mit einer zweistelligen
\zusatzklammer {Gewinn} {} {-}relation $G^M$ bestehen und die die Aussage
\mathl{\forall x \forall y { \left( Gxy \rightarrow \neg Gyx \right) }}{} erfüllen. Zeige, dass zwei verschiedene Elemente
\mathl{m,n \in M}{} zueinander
\definitionsverweis {elementar äquivalent}{}{}
sein können, obwohl
\mathl{G^M(m,n)}{} gilt
\zusatzklammer {$m$ und $n$ spielen also nicht unentschieden} {} {.}
}
{} {}
\inputaufgabe
{}
{
Ein Turnier werde im KO-System mit $2^n$ Mannschaften ausgetragen, jedes Spiel endet also mit einem Gewinner und einem Verlierer und der Verlierer scheidet direkt aus \zusatzklammer {es gebe kein Spiel um Platz drei oder ähnliches} {} {.} Das Turnier sei vorbei. Zeige, dass man jede Mannschaft in der Prädikatenlogik allein mit der Gewinnrelation adressieren kann \zusatzklammer {je zwei Mannschaften sind also nicht \definitionsverweis {elementar äquivalent}{}{}} {} {.}
}
{} {}
\inputaufgabegibtloesung
{}
{
Es sei $S$ das Symbolalphabet, das neben Variablen aus dem einzigen zweistelligen Relationssymbol $G$ besteht. Wir betrachten die KO-Runden
\zusatzklammer {also ab dem Achtelfinale} {} {}
der Fußballweltmeisterschaften von 2014 und von 2018, ohne das Spiel um Platz $3$, als $S$-Modelle, wobei wir $G$ als die Gewinnrelation interpretieren, d.h.
\mathl{xGy}{} besagt, dass $x$ gegen $y$
\zusatzklammer {gespielt und} {} {}
gewonnen hat.
\aufzaehlungacht{Welche der folgenden Relationen sind für die WM 2014 wahr: Brasilien G Deutschland, Deutschland G Brasilien, Deutschland G Argentinien, Mexiko G Japan.
}{Ist
\mathl{\forall y xGy}{} eine Charakterisierung des Weltmeisters?
}{Charakterisiere durch einen $S$-Ausdruck in der einen freien Variablen $x$, dass eine Mannschaft mindestens das Halbfinale erreicht hat.
}{Charakterisiere durch einen $S$-Ausdruck in der einen freien Variablen $x$, dass eine Mannschaft das Halbfinale, aber nicht das Finale erreicht hat.
}{Betrachte Schweden bei der WM 2018. Man gebe einen $S$-Ausdruck in der einen freien Variablen $x$, der Schweden charakterisiert.
}{Welche(n) Mannschaft(en) der WM 2014 erfüllt (erfüllen) den $S$-Ausdruck, der Schweden bei der WM 2018 charakterisiert?
}{Definiere einen
$S$-\definitionsverweis {Isomorphismus}{}{}
zwischen der WM 2014 und der WM 2018.
}{Ist dies auch ein Isomorphismus, wenn man das Spiel um Platz $3$ mitberücksichtigt?
}
}
{} {}
\inputaufgabe
{}
{
Es sei $\{ 0,1,+,\cdot, \geq\}$ das Symbolalphabet für einen
\definitionsverweis {angeordneten Körper}{}{.}
Wir betrachten zu
\mavergleichskette
{\vergleichskette
{m,n
}
{ \in }{ \N_+
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Ausdrücke
\mathl{\alpha_{m,n}}{} in der einen freien Variablen $x$, die durch
\mathdisp {x + \cdots + x \geq 1 + \cdots + 1} { }
gegeben sind, wobei links $m$ mal $x$ und rechts $n$ mal $1$ steht.
Wir betrachten den angeordneten Körper $\R$.
\aufzaehlungdrei{Zeige mit Hilfe von
\mathl{\alpha_{m,n}}{,} dass verschiedene reelle Zahlen nicht zueinander
\definitionsverweis {elementar äquivalent}{}{}
sind.
}{Zeige, dass nicht alle reellen Zahlen durch einen Ausdruck in einer freien Variablen charakterisierbar sind.
}{Zeige, dass jede rationale Zahl
\zusatzklammer {innerhalb der reellen Zahlen} {} {}
durch einen Ausdruck in einer freien Variablen charakterisierbar ist.
}
}
{} {}
\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.
}
{} {}
\zwischenueberschrift{Aufgaben zum Abgeben}
\inputaufgabe
{4}
{
Es seien
\mathl{\Gamma \subseteq \Gamma' \subseteq L^S}{}
\definitionsverweis {widerspruchsfreie}{}{}
Ausdrucksmengen, die unter Ableitungen abgeschlossen seien, und seien
\mathkor {} {M} {bzw.} {M'} {}
die gemäß der
\definitionsverweis {Konstruktion}{}{}
zugehörigen Modelle. Zeige, dass es einen
$S$-\definitionsverweis {Homomorphismus}{}{}
\maabbdisp {} {M} {M'
} {}
gibt.
}
{} {}
\inputaufgabe
{2}
{
Es sei $S$ ein
\definitionsverweis {erststufiges Symbolalphabet}{}{}
und
\mathl{M,N}{} seien
$S$-\definitionsverweis {isomorphe}{}{}
$S$-\definitionsverweis {Strukturen}{}{.}
Zeige, dass die zugehörigen
\definitionsverweis {Automorphismengruppen}{}{}
\mathkor {} {\operatorname{Aut}_S \, M} {und} {\operatorname{Aut}_S \, N} {}
\definitionsverweis {isomorph}{}{}
sind.
}
{} {}
\inputaufgabe
{8}
{
Klassifiziere \zusatzklammer {bis auf Isomorphie} {} {} die möglichen Gewinnstrukturen bei einer Vierergruppe \zusatzklammer {wie bei einer Fußballweltmeisterschaft} {} {.}
}
{} {(Bemerkung: Es wird also eine vollständige Liste aller möglichen Isomorphietypen verlangt. Die Liste muss systematisch sein und die Vollständigkeit begründet werden.)}
\inputaufgabe
{2}
{
Es sei $S$ ein Symbolalphabet, das neben Variablen aus einem einzigen einstelligen Funktionssymbol $f$ besteht und es sei
\mavergleichskette
{\vergleichskette
{M
}
{ = }{ \{1 , \ldots , 10 \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
$S$-\definitionsverweis {Struktur}{}{,}
wobei $f$ als die
\definitionsverweis {Permutation}{}{}
$\pi$ mit \wertetabellezehnausteilzeilen { $x$ }
{\mazeileundfuenf {1} {2} {3} {4} {5} }
{\mazeileundfuenf {6} {7} {8} {9} {10} }
{ $\pi(x)$ }
{\mazeileundfuenf {5} {10} {8} {4} {3} }
{\mazeileundfuenf {6} {9} {1} {7} {2} }
interpretiert werde. Bestimme die
\definitionsverweis {elementar äquivalenten}{}{}
Elemente von $M$.
}
{} {}
\inputaufgabe
{4}
{
Es sei $S$ das Symbolalphabet, das neben Variablen aus einem zweistelligen Relationssymbol $G$ besteht und es sei
\mavergleichskettedisp
{\vergleichskette
{M
}
{ =} {\{ \text{Deu}, \text{Gha}, \text{Por}, \text{USA} \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die
$S$-\definitionsverweis {Struktur}{}{,}
bei der $G(m,n)$ als $m$ gewinnt gegen $n$
\zusatzklammer {bei der Fußballweltmeisterschaft 2014} {} {}
interpretiert wird. Bestimme die Äquivalenzklassen zur elementaren Äquivalenz, charakterisierende Ausdrücke und die Automorphismengruppe.
}
{} {}
\inputaufgabe
{3}
{
Bestimme die
\definitionsverweis {Äquivalenzklassen}{}{}
zur
\definitionsverweis {elementaren Äquivalenz}{}{}
in der
\definitionsverweis {zyklischen Gruppe}{}{}
\mathl{\Z/(8)}{} zum Symbolalphabet
\mathl{S= \{ 0, +\}}{.}
}
{} {}