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

Aus Wikiversity



Übungsaufgaben

Aufgabe

Es sei ein erststufiges Symbolalphabet und seien - Strukturen. Zeige folgende Aussagen.

  1. Die Identität

    ist ein Isomorphismus.

  2. Zu einem Isomorphismus

    ist die Umkehrabbildung

    ein Isomorphismus.

  3. Es seien

    und

    Homomorphismen (Isomorphismen). Dann ist auch die Hintereinanderschaltung ein Homomorphismus (Isomorphismus).


Aufgabe


Aufgabe

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


Die nächste Aufgabe verwendet die folgende Definition.

Es seien und zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung

heißt ordnungstreu (oder monoton), wenn für alle mit stets auch gilt.

Aufgabe

Es sei eine geordnete Menge und die Potenzmenge von . Zeige, dass die Abbildung

ordnungstreu und injektiv ist, wobei die Potenzmenge mit der Inklusion versehen ist.


Aufgabe

Es sei die Menge aller unendlichen Teilmengen von , versehen mit der Inklusion als Ordnung, und es sei das rechtsseitig offene reelle Einheitsintervall mit der Kleinergleich-Relation als Ordnung. Zeige, dass die Abbildung

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

Es sei ein Symbolalphabet, das neben Variablen aus einem einzigen einstelligen Relationssymbol besteht. Was bedeutet ein - Homomorphismus? Welche mathematische Signifikanz hat dieser Begriff?


Aufgabe

Es sei ein Symbolalphabet, das neben Variablen aus einem einzigen einstelligen Funktionssymbol besteht. Was bedeutet ein - Homomorphismus? Welche mathematische Signifikanz hat dieser Begriff?


Aufgabe

Es sei ein Symbolalphabet erster Stufe. Definiere eine -„Unterstruktur“ in einer - Struktur .


Aufgabe *

Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe. Es sei eine - Interpretation mit der Grundmenge und es sei mit der zugehörigen Äquivalenzrelation auf der Termmenge .

  1. Zeige, dass genau dann gilt, wenn gilt.
  2. Zeige, dass es eine injektive Abbildung

    mit

    gibt.

  3. Zeige, dass ein - Homomorphismus ist, wenn die Quotientenmenge mit der kanonischen - Struktur versehen wird.
  4. Es sei die kanonische Interpretation auf . Es sei vorausgesetzt, dass die Terminterpretation für surjektiv sei. Zeige, dass genau dann gilt, wenn gilt.


Aufgabe

Es sei ein erststufiges Symbolalphabet, und seien - Strukturen und

ein Homomorphismus. Es sei eine Variablenbelegung in und die nach übertragene Variablenbelegung. Es seien und die zugehörigen Interpretationen. Zeige, dass

für alle - Terme gilt.


Unter einem Automorphismus einer -Struktur versteht man einen Isomorphismus von nach . Man spricht von der -Automorphismengruppe von , geschrieben .

Aufgabe

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


Aufgabe

Es sei und sei versehen mit der natürlichen - Interpretation. Bestimme die - Automorphismengruppe von .


Aufgabe

Es sei ein erststufiges Symbolalphabet und eine - Struktur. Zeige, dass die elementare Äquivalenz von Elementen eine Äquivalenzrelation auf ist.


Aufgabe

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.


Aufgabe

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.


Aufgabe *

In einer Wohngemeinschaft leben die Personen . Wir betrachten die folgenden Relationen:

  1. bedeutet, dass und manchmal miteinander Tennis spielen,
  2. bedeutet, dass und manchmal miteinander Skat spielen,
  3. bedeutet, dass und manchmal miteinander Doppelkopf spielen.

In der WG gilt

  1. Charakterisiere umgangssprachlich die Person allein unter Bezugnahme auf die gegebenen Spielrelationen.
  2. Charakterisiere umgangssprachlich die Person allein unter Bezugnahme auf die gegebenen Spielrelationen.
  3. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen und den Relationssymbolen die Person .
  4. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen und den Relationssymbolen die Person .
  5. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen und den Relationssymbolen die Person .


Aufgabe

Es sei 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 elementar äquivalent sind.


Aufgabe

Es sei ein Symbolalphabet, das neben Variablen aus einem einzigen einstelligen Funktionssymbol besteht und es sei eine - Struktur, wobei als die Permutation mit

interpretiert werde. Bestimme die elementar äquivalenten Elemente von .


Aufgabe *

Charakterisiere den Punkt im skizzierten Graphen mit einem Ausdruck in einer freien Variablen über dem Symbolalphabet, das neben Variablen aus einem einzigen zweistelligen Relationssymbol besteht, das im angegebenen Modell durch einen Pfeil wiedergegeben wird.


Aufgabe

Wir betrachten das Symbolalphabet mit der natürlichen Interpretation auf . Zeige, dass jedes Element nur zu sich selbst elementar äquivalent ist.


Aufgabe

Es seien die Symbolalphabete , , und gegeben, die wir auf natürlich interpretieren. Bestimme zu diesen Symbolalphabeten jeweils die Äquivalenzklassen zur elementaren Äquivalenz.


Aufgabe

Bestimme die Äquivalenzklassen zur elementaren Äquivalenz in der zyklischen Gruppe zum Symbolalphabet .


Aufgabe *

Bestimme die Äquivalenzklassen zur elementaren Äquivalenz in der Gruppe zum Symbolalphabet .


Aufgabe

Es sei das Symbolalphabet, das außer Variablen für jedes ein einstelliges Relationssymbol enthält. Wir betrachten die Menge , wobei wir das Relationssymbol durch

interpretieren. Es sei ein Ausdruck in einer freien Variablen , wobei in die Relationssymbole vorkommen mögen. Es sei das kleinste gemeinsame Vielfache von . Zeige, dass

genau dann gilt, wenn

gilt.


Aufgabe

Es sei das Symbolalphabet, das neben Variablen aus einem zweistelligen Relationssymbol besteht und es sei

Zeige, dass eine vierelementige - Struktur, die erfüllt, äquivalent zur Gewinnstruktur in einer Vorgruppe bei einer Fußballweltmeisterschaft ist.

(Bemerkung: Eine zweistellige Relation wird oft durch ein Pfeildiagramm veranschaulicht.)

Aufgabe

Es sei das Symbolalphabet, das neben Variablen aus einem zweistelligen Relationssymbol besteht und es sei

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


Aufgabe

Es sei das Symbolalphabet, das neben Variablen aus einem zweistelligen Relationssymbol besteht. Wir betrachten Modelle, die aus einer vierelementigen Menge mit einer zweistelligen (Gewinn)-relation bestehen und die die Aussage erfüllen. Zeige, dass zwei verschiedene Elemente zueinander elementar äquivalent sein können, obwohl gilt ( und spielen also nicht unentschieden).


Aufgabe

Ein Turnier werde im KO-System mit Mannschaften ausgetragen, jedes Spiel endet also mit einem Gewinner und einem Verlierer und der Verlierer scheidet direkt aus (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 (je zwei Mannschaften sind also nicht elementar äquivalent).


Aufgabe *

Es sei das Symbolalphabet, das neben Variablen aus dem einzigen zweistelligen Relationssymbol besteht. Wir betrachten die KO-Runden (also ab dem Achtelfinale) der Fußballweltmeisterschaften von 2014 und von 2018, ohne das Spiel um Platz , als -Modelle, wobei wir als die Gewinnrelation interpretieren, d.h. besagt, dass gegen (gespielt und) gewonnen hat.

  1. Welche der folgenden Relationen sind für die WM 2014 wahr: Brasilien G Deutschland, Deutschland G Brasilien, Deutschland G Argentinien, Mexiko G Japan.
  2. Ist eine Charakterisierung des Weltmeisters?
  3. Charakterisiere durch einen -Ausdruck in der einen freien Variablen , dass eine Mannschaft mindestens das Halbfinale erreicht hat.
  4. Charakterisiere durch einen -Ausdruck in der einen freien Variablen , dass eine Mannschaft das Halbfinale, aber nicht das Finale erreicht hat.
  5. Betrachte Schweden bei der WM 2018. Man gebe einen -Ausdruck in der einen freien Variablen , der Schweden charakterisiert.
  6. Welche(n) Mannschaft(en) der WM 2014 erfüllt (erfüllen) den -Ausdruck, der Schweden bei der WM 2018 charakterisiert?
  7. Definiere einen - Isomorphismus zwischen der WM 2014 und der WM 2018.
  8. Ist dies auch ein Isomorphismus, wenn man das Spiel um Platz mitberücksichtigt?


Aufgabe

Es sei ein Symbolalphabet erster Stufe und eine - Struktur. Für jede elementare Äquivalenzklasse gebe es einen -Ausdruck in einer freien Variablen , der die Klasse beschreibt. Zeige, dass für jedes -stellige Funktionssymbol aus die elementare Äquivalenz folgt.


Aufgabe

Es sei ein Symbolalphabet erster Stufe und eine - Struktur. Für jede elementare Äquivalenzklasse gebe es einen -Ausdruck in einer freien Variablen , der die Klasse beschreibt. Zeige, dass für ein -stelliges Funktionssymbol aus nicht die Gleichheit folgen muss.




Aufgaben zum Abgeben

Aufgabe (4 Punkte)

Es seien widerspruchsfreie Ausdrucksmengen, die unter Ableitungen abgeschlossen seien, und seien bzw. die gemäß der Konstruktion zugehörigen Modelle. Zeige, dass es einen - Homomorphismus

gibt.


Aufgabe (2 Punkte)

Es sei ein Symbolalphabet, das neben Variablen aus einem einzigen einstelligen Funktionssymbol besteht und es sei eine - Struktur, wobei als die Permutation mit

interpretiert werde. Bestimme die elementar äquivalenten Elemente von .


Aufgabe (4 Punkte)

Es sei das Symbolalphabet, das neben Variablen aus einem zweistelligen Relationssymbol besteht und es sei

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


Aufgabe (8 Punkte)

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)

Es sei ein erststufiges Symbolalphabet und seien - isomorphe - Strukturen. Zeige, dass die zugehörigen Automorphismengruppen und isomorph sind.


Aufgabe (3 Punkte)

Bestimme die Äquivalenzklassen zur elementaren Äquivalenz in der zyklischen Gruppe zum Symbolalphabet .



<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2018) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)