Explain what is meant by a structure for a first-order signature $\Sigma$, and describe how first-order formulae over $\Sigma$ are interpreted in a given structure. Show that if $B$ is a substructure of $A$, and $\phi$ is a quantifier-free formula (with $n$ free variables), then

$$\llbracket \phi \rrbracket_{B}=\llbracket \phi \rrbracket_{A} \cap B^{n}$$

A first-order theory is said to be inductive if its axioms all have the form

$$\left(\forall x_{1}, \ldots, x_{n}\right)\left(\exists y_{1}, \ldots, y_{m}\right) \phi$$

where $\phi$ is quantifier-free (and either of the strings $x_{1}, \ldots, x_{n}$ or $y_{1}, \ldots, y_{m}$ may be empty). If $T$ is an inductive theory, and $A$ is a structure for the appropriate signature, show that the poset of those substructures of $A$ which are $T$-models is chain-complete.

Which of the following can be expressed as inductive theories over the signature with one binary predicate symbol $\leqslant$ ? Justify your answers.

(a) The theory of totally ordered sets without greatest or least elements.

(b) The theory of totally ordered sets with greatest and least elements.