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

Übungsaufgaben

Aufgabe Referenznummer erstellen

Es sei ${}S$ ein erststufiges Symbolalphabet und ${}L,M,N$ seien ${}S$- Strukturen. Zeige folgende Aussagen.

1. Die Identität

   $\operatorname {Id} _{M}\colon M\longrightarrow M$

   ist ein Isomorphismus.

2. Zu einem Isomorphismus

   $\varphi \colon M\longrightarrow N$

   ist die Umkehrabbildung

   $\varphi ^{-1}\colon N\longrightarrow M$

   ein Isomorphismus.

3. Es seien

   $\psi \colon L\longrightarrow M$

   und

   $\varphi \colon M\longrightarrow N$

   Homomorphismen (Isomorphismen). Dann ist auch die Hintereinanderschaltung ${}\varphi \circ \psi$ ein Homomorphismus (Isomorphismus).

Aufgabe Referenznummer erstellen

Zeige, dass die Begriffe Gruppenhomomorphismus, Ringhomomorphismus, monotone Abbildung zwischen geordneten Mengen und lineare Abbildung unter den abstrakten Homomorphiebegriff (über welchem erststufigen Symbolalphabet ${}S$?) fallen.

Aufgabe Aufgabe 16.3 ändern

Es sei ${}S$ ein erststufiges Symbolalphabet, das keine Relationssymbole enthalte. Zeige, dass ein bijektiver ${}S$- Homomorphismus zwischen zwei ${}S$- Strukturen bereits ein ${}S$- Isomorphismus ist.

Aufgabe Referenznummer erstellen

Es sei ${}M$ die Menge aller unendlichen Teilmengen von ${}\mathbb {N} _{+}$, versehen mit der Inklusion als Ordnung, und es sei ${}[0,1[$ das rechtsseitig offene reelle Einheitsintervall mit der Kleinergleich-Relation als Ordnung. Zeige, dass die Abbildung

$\Psi \colon M\longrightarrow [0,1[,\,T\longmapsto \sum _{n\not \in T}{\left({\frac {1}{2}}\right)}^{n},$

eine bijektive, ordnungstreue Abbildung ist, deren Umkehrabbildung nicht ordnungstreu ist.

Warum beschränkt man sich auf unendliche Teilmengen? Wie sehen die „transportierten Ordnungen“ aus?

Aufgabe Referenznummer erstellen

Es sei ${}S$ ein Symbolalphabet erster Stufe. Definiere eine ${}S$-„Unterstruktur“ in einer ${}S$- Struktur ${}M$.

Aufgabe Aufgabe 16.6 ändern

Es sei ${}S$ ein erststufiges Symbolalphabet, ${}M$ und ${}N$ seien ${}S$- Strukturen und

$\varphi \colon M\longrightarrow N$

ein Homomorphismus. Es sei ${}\lambda$ eine Variablenbelegung in ${}M$ und ${}\varphi \circ \lambda$ die nach ${}N$ übertragene Variablenbelegung. Es seien ${}I$ und ${}J$ die zugehörigen Interpretationen. Zeige, dass

${}\varphi (I(t))=J(t)\,$

für alle ${}S$- Terme ${}t$ gilt.

Aufgabe Referenznummer erstellen

Es sei ${}S$ ein erststufiges Symbolalphabet und ${}M$ eine ${}S$- Struktur. Zeige, dass die elementare Äquivalenz von Elementen ${}m,n\in M$ eine Äquivalenzrelation auf ${}M$ ist.

Aufgabe Referenznummer erstellen

Es sei ${}S$ ein 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 ${}m,n\in M$ elementar äquivalent sind.

Unter einem Automorphismus einer ${}S$-Struktur ${}M$ versteht man einen Isomorphismus von ${}M$ nach ${}M$. Man spricht von der ${}S$-Automorphismengruppe von ${}M$, geschrieben ${}\operatorname {Aut} _{S}\,M$.

Aufgabe Referenznummer erstellen

Es sei ${}S$ ein erststufiges Symbolalphabet und ${}M$ sei eine ${}S$- Struktur. Zeige, dass die Menge der ${}S$-Automorphismen auf ${}M$ eine Gruppe bildet.

Aufgabe Referenznummer erstellen

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

Aufgabe * Referenznummer erstellen

Bestimme die Äquivalenzklassen zur elementaren Äquivalenz in der Gruppe ${}\mathbb {Z} /(2)\times \mathbb {Z} /(2)$ zum Symbolalphabet ${}S=\{0,+\}$.

Aufgabe Referenznummer erstellen

Es sei ${}S$ das Symbolalphabet, das neben Variablen aus einem zweistelligen Relationssymbol ${}G$ besteht und es sei

${}\Gamma =\{\forall x\forall y{\left(Gxy\rightarrow \neg Gyx\right)}\}\,.$

Zeige, dass eine vierelementige ${}S$- 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.)

Aufgabe Referenznummer erstellen

Es sei ${}S$ das Symbolalphabet, das neben Variablen aus einem zweistelligen Relationssymbol ${}G$ besteht und es sei

${}M=\{{\text{Bra}},{\text{Kam}},{\text{Kro}},{\text{Mex}}\}\,$

die ${}S$- Struktur, bei der ${}G(m,n)$ als ${}m$ gewinnt gegen ${}n$ (bei der Fußballweltmeisterschaft 2014) interpretiert wird. Bestimme die Äquivalenzklassen zur elementaren Äquivalenz, charakterisierende Ausdrücke und die Automorphismengruppe.

Aufgabe Referenznummer erstellen

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 (Gewinn)-relation ${}G^{M}$ bestehen und die die Aussage ${}\forall x\forall y{\left(Gxy\rightarrow \neg Gyx\right)}$ erfüllen. Zeige, dass zwei verschiedene Elemente ${}m,n\in M$ zueinander elementar äquivalent sein können, obwohl ${}G^{M}(m,n)$ gilt (${}m$ und ${}n$ spielen also nicht unentschieden).

Aufgaben zum Abgeben

Aufgabe (4 Punkte)Referenznummer erstellen

Es seien ${}\Gamma \subseteq \Gamma '\subseteq L^{S}$ widerspruchsfreie Ausdrucksmengen, die unter Ableitungen abgeschlossen seien, und seien ${}M$ bzw. ${}M'$ die gemäß der Konstruktion zugehörigen Modelle. Zeige, dass es einen ${}S$- Homomorphismus

$M\longrightarrow M'$

gibt.

Aufgabe (4 Punkte)Referenznummer erstellen

Es sei ${}S$ das Symbolalphabet, das neben Variablen aus einem zweistelligen Relationssymbol ${}G$ besteht und es sei

${}M=\{{\text{Deu}},{\text{Gha}},{\text{Por}},{\text{USA}}\}\,$

die ${}S$- Struktur, bei der ${}G(m,n)$ als ${}m$ gewinnt gegen ${}n$ (bei der Fußballweltmeisterschaft 2014) interpretiert wird. Bestimme die Äquivalenzklassen zur elementaren Äquivalenz, charakterisierende Ausdrücke und die Automorphismengruppe.

Aufgabe (8 Punkte)Referenznummer erstellen

Klassifiziere (bis auf Isomorphie) die möglichen Gewinnstrukturen bei einer Vierergruppe (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.)

Aufgabe (2 Punkte)Referenznummer erstellen

Es sei ${}S$ ein erststufiges Symbolalphabet und ${}M,N$ seien ${}S$- isomorphe ${}S$- Strukturen. Zeige, dass die zugehörigen Automorphismengruppen ${}\operatorname {Aut} _{S}\,M$ und ${}\operatorname {Aut} _{S}\,N$ isomorph sind.

Aufgabe (3 Punkte)Referenznummer erstellen

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