Aufgabe 1
Den folgenden σ-Strukturen sollen die Formeln zugeordnet werden, die sie erfüllen. Eine Struktur kann mehrere Formeln erfüllen. Es gibt Abzug für falsche Zuordnung.
Aufgabe 2
Sei \( \mathcal{N} = \left( \mathbb{N}, +, \cdot \right) \) die Struktur der natürlichen Zahlen mit der üblichen Addition und Multiplikation. Ohne Begründung. Geben Sie die Formeln \( \varphi_1 \) bis \( \varphi_4 \) an, sodass gilt:
- \( \varphi_1 \left( \mathcal{N} \right) \) ist die Menge der Zahlen, die sich als dritte Potenz einer natürlichen Zahl schreiben lassen.
- \( \varphi_2 \left( \mathcal{N} \right) \) ist die Menge der der Paare \( \left(x, x^3 \right) \) mit \( x \in \mathbb{N} \).
- \( \varphi_3 \left( \mathcal{N} \right) \) ist die Menge der Zahlen, die größer als 4 sind.
- \( \varphi_4 \left( \mathcal{N} \right) \) ist die Menge der Primahlen. Die kleinste Primzahl ist 2.
Aufgabe 3
- Gibt es eine Signatur σ, sodass jede σ-Struktur endlich ist? Beweisen Sie Ihre Antwort.
- [Fehlt]
- Sei \( A \) eine endliche, nicht leere Menge und σ eine endliche, relationale Signatur. Zeigen Sie, dass es nur endlich viele σ-Strukturen mit Universum \( A \) gibt.
Aufgabe 4
Betrachten Sie folgende Signatur \( \sigma = \left\{ R \right\} \), wobei \( R \) ein 2-stelliges Relationssymbol ist.
- Was bedeutet es, dass der Sequenzenkalkül vollständig ist? Es ist nur nach Vollständigkeit gefragt, nicht nach Korrektheit.
- Zeigen Sie nur mit Hilfe des Sequenzenkalküls, dass die Sequenz \( \exists x \forall y \, R \left(x, y \right) \Rightarrow \forall y \exists x \, R \left(x, y \right) \) gültig ist. Geben Sie in jedem Schritt an, welche Regel verwendet wurde. In jedem Schritt darf nur eine einzige Regelanwendung gemacht werden. Falls Sie die Substitutionsregel anwenden, geben Sie bitte \( \psi \), \( t \) und \( t^\prime \) an.
- Zeigen oder widerlegen Sie die Korrektheit der folgenden Regeln:
- \( \frac{\displaystyle \Phi \Rightarrow \Delta, \psi \quad \Phi \Rightarrow \Delta, \varphi}{\displaystyle \Phi \Rightarrow \Delta, \psi \land \varphi} \),
- \( \frac{\displaystyle \Phi \Rightarrow \Delta, \varphi}{\displaystyle \Phi \Rightarrow \Delta} \).
Aufgabe 5 [fehlt]
[Ehrenfeucht-Fraïssé-Spiele und σ-Strukturen.]
Aufgabe 6
Sei \( \sigma := \left\{P, N \right\} \), wobei \( P \) und \( N \) einstellige Relationssymbole sind. Sei \( \mathcal{R} = \left( \mathbb{R}, P^R, N^R \right) \) die σ-Struktur mit
\[ P^R = \left\{ x \in \mathbb{R} \middle| x > 0 \right\}, \\ N^R = \left\{ x \in \mathbb{R} \middle| x < 0 \right\}. \]Geben Sie eine Formel \( \psi \) an, so dass für jede σ-Struktur \( \mathcal{B} \) gilt
\[ \mathcal{B} \models \psi \iff \text{ Duplikatorin gewinnt das 1-Runden-Spiel } \left( \mathcal{R}, \mathcal{B} \right). \]Begründen Sie Ihre Antwort.