Exercises

1.

Specify an interpretation on which the formula $\forall x \exists y f(x,y) = a$ is true.

2.

A formula that doesn't contain $\neg, \leftrightarrow$, or $\rightarrow$ is said to be positive. Show that for every positive formula $\phi$ (based on some symbol set S) there is an interpretation that satisfies it.

3.

Specify a set $\Phi_\infty$ such that its models are precisely the infinite interpretations. That is, this biconditional must be true:

$$\mbox{$\cal I$} \models \Phi_\infty \mbox{ iff } \mbox{$\cal D$ contains infinitely many elements}.$$

4.

A set M of natural numbers is called a spectrum if there is a symbol set S and an S-sentence^4.1 $\phi$ such that

$$M = \{n \in \mbox{{\bf N}} : \phi \mbox{ has a model containing exactly {\em n} elements}\}.$$

Show that every finite subset {1, 2, 3, $\ldots, n$} is a spectrum.