Solutions

1.

Let the domain be N, let $\alpha(f)$ denote ordinary multiplication, and let $\alpha(a)$ denote the number 0.

2.

Hint: Map everything to a one-element domain $\cal D$ composed of a. So suppose that $\phi$ is a positive atomic formula Rt₁ t₂. Then for arbitrary $\cal I$, $\cal I$(t₁) = a and $\cal I$(t₂) = a. In this case $\alpha(R)$ is $\{a\} \times \{a\}$, and of course it includes (a, a) as an element. With this key idea used, the proof is by induction on terms and positive formulas.

3.

Note that the formula $\exists x x = x$ is only satisfied by interpretations having domains composed of one or more elements, and that any interpretation satisfying $\exists x \exists y \, x \not= y$ must have a domain with at least two elements. The idea can be sustained ad infinitum. For example, $\exists x \exists y \exists z \, (x \not= y \wedge y \not= z \wedge x \not= z)$ is satisfied only by interpretations with domains having at least three elements. So we are entitled to define $\phi^{\ge n}$ to be the formula such that its models have domains containing at least n elements. Now set $\Omega_\infty = \{\phi^{\ge n} : n \in {\bf N}\}$. Clearly, an interpretation

$$\mbox{$\cal I$} \models \Omega_\infty \mbox{ iff } \mbox{it's domain $\cal D$ contains infinitely many elements}.$$

4.

This is trickier!