Mächtigkeit von Datenbereichen

Question

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.

Comments

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.

Answer 1

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.

Comments

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

---

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