Explain what is meant by a structure for a first-order signature $\Sigma$, and describe briefly how first-order terms and formulae in the language over $\Sigma$ are interpreted in a structure. Suppose that $A$ and $B$ are $\Sigma$-structures, and that $\phi$ is a conjunction of atomic formulae over $\Sigma$ : show that an $n$-tuple $\left(\left(a_{1}, b_{1}\right), \ldots,\left(a_{n}, b_{n}\right)\right)$ belongs to the interpretation $\llbracket \phi \rrbracket_{A \times B}$ of $\phi$ in $A \times B$ if and only if $\left(a_{1}, \ldots, a_{n}\right) \in \llbracket \phi \rrbracket_{A}$ and $\left(b_{1}, \ldots, b_{n}\right) \in \llbracket \phi \rrbracket B$.

A first-order theory $\mathbb{T}$ is called regular if its axioms all have the form

$$(\forall \vec{x})(\phi \Rightarrow(\exists \vec{y}) \psi),$$

where $\vec{x}$and $\vec{y}$ are (possibly empty) strings of variables and $\phi$ and $\psi$ are conjunctions of atomic formulae (possibly the empty conjunction $T$ ). Show that if $A$ and $B$ are models of a regular theory $\mathbb{T}$, then so is $A \times B$.

Now suppose that $\mathbb{T}$ is a regular theory, and that a sentence of the form

$$(\forall \vec{x})\left(\phi \Rightarrow\left(\psi_{1} \vee \psi_{2} \vee \cdots \vee \psi_{n}\right)\right)$$

is derivable from the axioms of $\mathbb{T}$, where $\phi$ and the $\psi_{i}$ are conjunctions of atomic formulae. Show that the sentence $(\forall \vec{x})\left(\phi \Rightarrow \psi_{i}\right)$ is derivable for some $i$. [Hint: Suppose not, and use the Completeness Theorem to obtain a suitable family of $\mathbb{T}$-models $A_{1}, \ldots, A_{n}$.]