Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/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.

}
{} {}

\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 \definitionsverweis {Symbolalphabet erster Stufe}{}{.} Definiere eine $S$-\anfuehrung{Unterstruktur}{} in einer $S$-\definitionsverweis {Struktur}{}{} $M$.

}
{} {}

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

}
{} {}

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

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.

}
{} {}

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{\operatorname{Aut}_S \, 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
{}
{

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

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{}
{

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

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

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

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

Bestimme die \definitionsverweis {Äquivalenzklassen}{}{} zur \definitionsverweis {elementaren Äquivalenz}{}{} in der \definitionsverweis {zyklischen Gruppe}{}{}
\mathl{\Z/(8)}{} zum Symbolalphabet
\mathl{S= \{ 0, +\}}{.}

}
{} {}