+1 Daumen
130 Aufrufe

Für eine Struktur \( \mathcal{M}=(D, I) \) schreiben wir \( |\mathcal{M}| \) für \( |D| \), die Mächtigkeit von \( D \). Wir nennen \( \mathcal{M} \) endlich, falls die Menge \( D \) endlich ist.

a) Geben Sie für jedes \( n \in \mathbb{N}, n \geqslant 1 \) abgeschlossene Formel \( A_{n} \) an, für die gilt:
\( \mathcal{M} \models A_{n} \) genau dann, wenn \( |\mathcal{M}|=n \).

b) Es sei \( B \) eine abgeschlossene Formel, in der, " "nicht vorkommt. Wie kann aus einem endlichen Modell \( \mathcal{M} \) für \( B \) ein Modell \( \mathcal{M}^{\prime} \) für \( B \) konstruiert werden, so dass \( \left|\mathcal{M}^{\prime}\right|=|\mathcal{M}|+1 ? \)
Dass \( \mathcal{M}^{\prime} \) Modell für \( B \) ist, muss hier nicht unbedingt bewiesen werden.

c) Schließen Sie aus b), dass es für kein \( n \in \mathbb{N}, n \geqslant 1 \) eine Formel gibt, die ohne,\( =" \) auskommt und äquivalent zur Formel \( A_{n} \) aus a) ist.


von
Für eine Struktur \( \mathcal{M}=(D, I) \) 

Was ist \(I\)?

in der, " "nicht vorkommt.

Was soll nicht vorkommen?

Was ist \(I\)?

I ist die Interpretation der Funktions- und Prädikatsymbole.

in der, " "nicht vorkommt.

Da sollte eigentlich ein "=" stehen. Habe ich vergessen, hinzuzufügen, sorry.

1 Antwort

0 Daumen
 
Beste Antwort

a) ist trivial.

b) Sei \( \mathcal{M}=(D, I)\models B \).

Sei \(a\in D\). Sei \(a^+ \notin D\) und \(D' =  D \cup \{a^+\}\).

Für jede Relation \(P\) aus \(I\) sei \(P^+\) die Relation, die man bekommt indem man in jedem Tupel von \(P\) jedes \(a\) durch \(a^+\) ersetzt. Nun setze \(P' \coloneqq P\cup P^+\).

Funktionen können als Relationen aufgefasst werden. Wie oben kann also aus jeder Funktion \(f\) eine Funktion \(f'\) konstruiert werden.

Sei \(I'\) die Interpretation der Funktions- und Prädikatsymbole durch die \(P'\) und \(f'\).

Dann ist \((D',I')\models B\).

c) ist trivial.

von 79 k 🚀

Gibt es zu a) und c) denn keine weitere Rechnung?

Doch gibt's. Aber die sind so einfach, dass du sie selbst hinbekommst.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community