\chapter{First-order logic}

Recall from \S~\ref{S:structures} the definitions and examples
involving \tech{structures}; these are the kinds of structures that we
shall now be dealing with.

Throughout this chapter, we shall let $\str A$ stand for an arbitrary
structure; its signature will be $\lang$.  So $\str A$ has 
universe $A$, which is just a non-empty set.  We shall use $c$, $R$
and $f$ to stand for arbitrary 
constants, predicates and relations of $\lang$,
respectively.  We shall use $n$ for the arity of $R$ and $f$.

Instead of propositional variables, we shall use a set of
\defn{individual variables,} namely
\begin{equation*}
  \{x_k:k\in\varN\}.
\end{equation*}

The structure $\str A$, as such, comes equipped with the operations
$f^{\str A}$ and the relations $R^{\str A}$.  We can combine these, in
the ways to be described below, so as to obtain new operations and
relations.  These new operations and relations will be symbolized by
certain strings:
\begin{mylist}
  \item
operations will be symbolized by \tech{terms;}
\item
relations will be symbolized by \tech{formulas.}
\end{mylist}

\section{Terms}

If $k<n$, then there is an $n$-ary operation
\begin{equation}\label{eqn:variable}
  \tuple a\longmapsto a_k
\end{equation}
on $A$.
This operation is \defn{projection} onto the $k$th coordinate.

Each element $b$ in $A$ determines, for each positive $n$,
the constant $n$-ary operation
\begin{equation}\label{eqn:constant}
  \tuple a\longmapsto b.
\end{equation}
If $b$ is $c^{\str A}$, then we have the $n$-ary operation $\tuple
a\mapsto c^{\str A}$.

More generally, if $\alpha$ is an $n$-ary operation on $A$, then there
is an $(n+k)$-ary operation on $A$, namely
\begin{equation*}
  (\tuple x,\tuple y)\longmapsto\alpha(\tuple x).
\end{equation*}

All operations on $A$ can be composed with one another:  If $\alpha$
is an $n$-ary operation on $A$, and $(\beta_k:k<n)$ is an $n$-tuple of

, and with
projections, to give other operations on $A$. 
The \defn{terms} of $\lang$ symbolize these possibilities.  The
symbols used in terms of $\lang$ are:
\begin{mylist}
  \item
the function-symbols $f$ of $\lang$;
\item
the constants $c$ of $\lang$;
\item
\defn{(individual) variables}, say from the set $\{\varble_k:k\in\varN\}$;
these will symbolize the projections.
\end{mylist}
Then the terms of $\lang$ are defined inductively thus:
\begin{mylist}
  \item
Each individual variable is a term of $\lang$.
\item
Each constant in $\lang$ is a term of $\lang$.
\item
If $f$ is an $n$-ary function-symbol of $\lang$, and $t_0$, \dots,
$t_{n-1}$ are terms of $\lang$, then the string
\begin{equation*}
  ft_0\dotsb f_{n-1}
\end{equation*}
is a term of $\lang$.  (This is not generally a string of length
$n+1$; it is a string whose length is $1$ more than the sum of the
lengths of the strings $t_k$.  If $f$ is binary, then we may
unofficially write the term as
$(t_0\mathrel f t_1)$ instead of $ft_0t_1$.)
\end{mylist}

Let the set of terms of $\lang$ be denoted
\begin{equation*}
  \Tm{}{\lang}.
\end{equation*}
As in propositional logic, so here, definition by recursion is
possible, because of the following:

\begin{theorem}[Unique Readability]
  Every term of $\lang$ is \emph{uniquely}
  \begin{equation*}
    st_0\dotsb t_{n-1}
  \end{equation*}
for some $n$ in $\varN$, some terms $t_k$ of $\lang$ (if $n\neq0$),
and some $s$ in $\lang$.  If $n\neq0$, then $s$ is an $n$-ary
function-symbol of $\lang$; if $n=0$, then $s$ is a constant of
$\lang$ or a variable.   
\end{theorem}

\begin{proof}
\textbf{Exercise.}  (The proof can be developed as for
[a Theorem]%~\ref{thm:UR}
.)
\end{proof}

Note well that, by our definition, none of the symbols used in terms
is a bracket. 

If the variables in a term $t$ come from $\{\varble_k:k<n\}$, then $t$ is
\defn{$n$-ary}; the set of $n$-ary terms of $\lang$ can be denoted
\begin{equation*}
  \Tm{n}{\lang}.
\end{equation*}
Note then
\begin{equation*}
  \Tm{0}\lang\included\Tm 1\lang\included\Tm2\lang\included\dotsb.
\end{equation*}
An $n$-ary term $t$ of $\lang$ determines an $n$-ary operation $t^{\str A}$
on $A$.  The formal definition is recursive:
\begin{mylist}
\item
  $\varble_k{}^{\str A}$ is $\tuple a\mapsto a_k$, if $k<n$ (as in
  \eqref{eqn:variable}). 
\item
$c^{\str A}$ is $\tuple a\mapsto c^{\str A}$ 
(as in \eqref{eqn:constant}; 
here $c$ is understood respectively as term
  and constant).
\item
$(ft_0\dotsb t_{n-1})^{\str A}$ is 
  \begin{equation*}
      \tuple a\longmapsto f^{\str A}(t_0{}^{\str
  A}(\tuple a), \dots,t_{k-1}{}^{\str A}(\tuple a)),
  \end{equation*}
 that is,
  $f^{\str A}\circ(t_0{}^{\str A},\dots,t_{k-1}{}^{\str A})$.
\end{mylist}
We have just extended the interpretation-function
$\interpretation$ of $\str A$ so as to
include a function
\begin{equation}\label{eqn:I}
  t\longmapsto t^{\str A}:\Tm n\lang\To A^{A^n}.
\end{equation}
If $t\in\Tm0\lang$, then $t^{\str A}=\{(0,a)\}$ for some $a$ in $A$;
but (as in ch.~\ref{ch:intro}) we can then identify
$t^{\str A}$ with $a$, and we
can call $t$ a \defn{constant term}.

Suppose $\lang\included\lang'$.  An \defn{expansion} of $\str A$ to
$\lang'$ is a structure $\str A'$ whose signature is $\lang'$, and
whose universe is $A$, such that
\begin{equation*}
  s^{\str A'}=s^{\str A}
\end{equation*}
for all $s$ in $\lang$.  Then $\str A$ is the \defn{reduct} of $\str
A'$ to $\lang$.

\begin{example}
  The ring $(\Z,+,-,\cdot,0,1)$ is an expansion of the abelian group
  $(\Z,+,-,0)$; the latter is a reduct of the former. 
\end{example}

We can treat the elements of $A$ as new constants (not belonging to
$\lang$); adding these to $\lang$ gives the signature $\lang(A)$.
Then $\str A$ has a natural expansion $\str A_A$ to this signature,
so that
\begin{equation*}
  a^{\str A_A}=a
\end{equation*}
for all $a$ in $A$.  (Some writers prefer to define $\lang(A)$ as
$\lang\cup\{c_a:a\in A\}$, and then to define $c_a{}^{\str A_A}=a$.)

In fact, when it comes to interpreting terms (and, later, formulas),
we always treat $\str A$ as if it were $\str A_A$.  This means that
every $n$-ary term $t$ of $\lang(A)$ has an interpretation $t^{\str
  A}$ in $\str A$
according to the definition above, provided we understand $a^{\str A}$
as $a$ itself when $a\in A$.  In other contexts, however, it will be
important to distinguish clearly between $\str A$ and $\str A_A$.  We
shall also want to speak of expansions $\str A_X$ of $\str A$, where
$X$ is an arbitrary subset of $A$.


If $t$ is an $n$-ary term of $\lang$ (or $\lang(A)$), and $\tuple a\in
A^n$, then the
result of replacing each $\varble_k$ in $t$ with $a_k$, for each $k$ in $n$,
can be written
\begin{equation*}
  t(\tuple a);
\end{equation*}
this is a constant term of $\lang(A)$.  For a recursive definition, we
have that $t(\tuple a)$ is:
\begin{mylist}
  \item
$a_k$, if $t$ is $\varble_k$;
\item
$c$, if $t$ is $c$;
\item
$ft_0(\tuple a)\dotsb t_{k-1}(\tuple a)$, if $t$ is $ft_0\dotsb
  f_{k-1}$. 
\end{mylist}
Thus we have defined a function
\begin{equation}\label{eqn:a}
  t\longmapsto t(\tuple a):\Tm n\lang\To \Tm 0{\lang(A)}.
\end{equation}
The tuple $\tuple a$ also determines the function
\begin{equation}\label{eqn:a-again}
  g\longmapsto g(\tuple a):A^{A^n}\To A.
\end{equation}
We now have several functions, in \eqref{eqn:I}, \eqref{eqn:a} and
\eqref{eqn:a-again}, fitting together into a square: 
\begin{equation*}
  \begin{CD}
    \Tm n\lang@>{\tuple a}>>\Tm 0{\lang(A)}\\
@V{\interpretation}VV @VV{\interpretation}V\\
A^{A^n} @>>{\tuple a}> A
  \end{CD}.
\end{equation*}
It doesn't matter which way you go around:

\begin{lemma}
  $t^{\str A}(\tuple a)=t(\tuple a)^{\str A_A}$ for all $n$-ary terms of
  $\lang$, all $\lang$-structures $\str A$, and all $n$-tuples $\tuple
  a$ from $A$.
\end{lemma}

\begin{proof}
  The claim is perhaps obvious; but there \emph{is} a proof by
  induction: 

If $t$ is $\varble_k$, then $t^{\str A}(\tuple a)=a_k$, and $t(\tuple
a)^{\str A_A}=a_k{}^{\str A_A}=a_k$.

If $t$ is $c$, then $t^{\str A}(\tuple a)=c^{\str A}$, while $t(\tuple
a)^{\str A_A}=c^{\str A_A}=c^{\str A}$.

Finally, if the claim holds when $t$ is any of terms $t_i$, and now
$t$ is $ft_0\dotsb
f_{k-1}$, then we have
\begin{align*}
  t^{\str A}(\tuple a)&= f^{\str A}(t_0{}^{\str A}(\tuple a),\dots,
  t_{k-1}{}^{\str A}(\tuple a))\\
&=f^{\str A}(t_0(\tuple a)^{\str A_A},\dots,t_{k-1}(\tuple a)^{\str
  A_A})\\
%&=f^{\str A}(t_0{}^{\str A}(\tuple a),\dots,t_{k-1}{]^{\str A}(\tuple a))\\
&=(ft_0(\tuple a)\dotsb t_{k-1}(\tuple a))^{\str A_A}\\
&=t(\tuple a)^{\str A_A}.
\end{align*}
This completes the induction.
\end{proof}

As an \textbf{exercise}, you can
  give a recursive definition of
  \begin{equation*}
    t(u_0,\dots,u_{n-1}),
  \end{equation*}
where $t$ is an $n$-ary term, and the $u_k$ are terms.  What is the
\defn{arity} of the resulting term?  Show that
  \begin{equation*}
    t(u_0,\dots,u_{n-1})^{\str A}(\tuple a)=t^{\str A}(u_0{}^{\str
    A}(\tuple a),\dots,u_{n-1}{}^{\str A}(\tuple a)).
  \end{equation*}
Note then that, if $t$ is $n$-ary, then $t$ is precisely the term
denoted 
\begin{equation*}
  t(\varble_0,\dots,\varble_{n-1}).
\end{equation*}

\begin{example}
  Let $\lang$ be the signature of rings (with identity), and let $\str
  A$ be $\Z$ (or $\Q$ or $\R$ or $\C$ or some other infinite integral
  domain or field).  If $t$ is a term of $\lang(A)$, then $t^{\str A}$
  is a \defn{polynomial} over $A$.  What if $\str A$ is finite, say
  the $2$-element field $\F_2$?  In that case, if $t$ is
  $\varble_0\cdot(\varble_0+1)$ or $0$, then
  $t^{\str A}(a)=0$ for all $a$ in $A$.  However,  $\varble_0\cdot(\varble_0+1)$
  and $0$ do not represent the same polynomial, since they have
  different interpretations in fields (like $\F_4$) that properly
  include $\F_2$.  (Here, $\F_4$ can be defined as $\F_2[X]/(X^2+1)$.)
\end{example}

\section{Formulas}

As terms symbolize operations, so \tech{formulas} will symbolize
relations.  Each
formula $\phi$ of $\lang$ will have an \tech{interpretation} $\phi^{\str A}$
that is a relation on $A$.  When this relation is nullary and is in
fact $\{\emptyset\}$, that is, $1$, then $\phi$ will be called
\tech{true} in $\str A$, and we 
shall write
\begin{equation*}
  \str A\models\phi.
\end{equation*}
Conversely, it is possible to define \tech{truth} in structures first,
and then interpretations.  We shall look at both approaches.

So-called polynomial equations are examples of \tech{atomic formulas},
which are the first kinds of formulas to be defined.  From these, we
shall define \tech{open formulas}, and then arbitrary \tech{formulas}.

\subsection*{Atomic formulas and their interpretations}

The \defn{atomic formulas} of $\lang$ are of two kinds:
\begin{mylist}
\item
If $t_0$ and $t_1$ are terms of $\lang$, then $t_0=t_1$ is an atomic
formula of $\lang$.  (Some writers prefer to use a symbol like
$\equiv$ instead of $=$.)
  \item
If $R$ is an $n$-ary predicate of $\lang$, and $t_0$, \dots, $t_{n-1}$
are terms of $\lang$, then $Rt_0\dotsb t_{n-1}$ is an atomic formula
of $\lang$.  (If $R$ is binary, then we may unofficially write
$(t_0\mathrel Rt_1)$ instead of $Rt_0t_1$.)
\end{mylist}
An atomic formula $\alpha$ can be called \defn{$k$-ary} if the terms
it is made from are $k$-ary.  

A polynomial equation in two variables over $\R$ has a solution-set,
 which can be considered as the \tech{interpretation} of the
 equation.  Likewise, arbitrary atomic formulas have solution-sets,
 which are their interpretations:  If
$\alpha$ is a $k$-ary atomic formula of $\lang$, then the
 \defn{interpretation} in $\str A$ of $\alpha$ is the 
$k$-ary relation $\alpha^{\str A}$ on $A$ defined as follows.
 (Strictly, the validity of the definition depends on
 Theorem~\ref{thm:UR-formulas} below.)
 \begin{gather}\label{eqn:=-int}
   (t_0=t_1)^{\str A}=\{\tuple a\in A^k:t_0{}^{\str A}(\tuple a)=t_1{}^{\str
    A}(\tuple a)\};\\ \label{eqn:R-int}
(Rt_0\dotsb R_{n-1})^{\str A}= \{\tuple a\in A^k:(t_0{}^{\str A}(\tuple
    a),\dots, t_{n-1}{}^{\str A}(\tuple a))\in R^{\str A}\}.
 \end{gather}
As a special case, if $k=0$, we have
\begin{align}\label{eqn:truth-=}
  (t_0=t_1)^{\str A}=1&\Iff t_0{}^{\str A}=t_1{}^{\str A};\\
  \label{eqn:truth-R} 
(Rt_0\dotsb t_{n-1})^{\str A}=1&\Iff (t_0{}^{\str A},\dots,t_{n-1}{}^{\str
    A})\in R^{\str A}.
\end{align}
Note that the atomic formula $t_0=t_1$ can be considered as the
special case of $Rt_0\dotsb t_{n-1}$ when $n=2$ and $R$ is $=$.  We
treat the special case separately because we consider the equals-sign to
be \emph{always} available for use in formulas, and we
\emph{always} interpret it as true equality.

\subsection*{Open formulas and their interpretations}

We can treat atomic formulas as propositional variables, combining
them to get \defn{open} (or \defn{quantifier-free}) \defn{formulas}:
\begin{mylist}
  \item
atomic formulas are open formulas;
\item
if $\phi$ and $\chi$ are open formulas, then so are $\lnot\phi$ and
$(\phi\to\chi)$. 
\end{mylist}
As with atomic formulas, so with arbitrary open formulas: they are
$k$-ary if the terms they are built up from are $k$-ary.
Hence, if $\phi$ and $\chi$ are $k$-ary open formulas, then so are
$\lnot\phi$ and 
$(\phi\to\chi)$.  We can now define interpretations of $k$-ary open
formulas by adding to~\eqref{eqn:=-int} and~\eqref{eqn:R-int} the
following rules (again, Theorem~\ref{thm:UR-formulas} is required): 
\begin{align}\label{eqn:int-not}
  (\lnot\phi)^{\str A}&=A^k\setminus \phi^{\str A}=(\phi^{\str
  A})\comp;\\ \label{eqn:int-to}
(\phi\to\chi)^{\str A}& =A^k\setminus(\phi^{\str A}\setminus\chi^{\str
  A})= (\phi^{\str A}\setminus\chi^{\str A})\comp.
\end{align}
In particular, if $k=0$, then:
\begin{align*}
  (\lnot \phi)^{\str A}=1&\Iff \phi^{\str A}=0;\\
(\phi\to\chi)^{\str A}=0&\Iff \phi^{\str A}=1\amp\chi^{\str A}=0. 
\end{align*}

\subsection*{Formulas in general}

Formulas in general may contain the \defn{existential quantifier}
$\exists$. 
The inductive definition of \defn{formula} is:
\begin{mylist}
  \item
atomic formulas are formulas;
\item
if $\phi$ and $\chi$ are formulas, then so are $\lnot\phi$ and
$(\phi\to\chi)$; 
\item
if $\phi$ is a formula, and $x$ is a variable, then $\Exists x\phi$ is
a formula.
\end{mylist}

The possibility of defining the foregoing interpretations of open
formulas depends on the following:

\begin{theorem}[Unique Readability]\label{thm:UR-formulas}
  Every formula of $\lang$ is \emph{uniquely} one of the following:
  \begin{mylist}
    \item
      an equation $t_0=t_1$, for some terms $t_e$ of $\lang$;
\item
a relational formula $Rt_0\dotsb t_{n-1}$ for some terms $t_k$ and
$n$-ary predicate $R$ of $\lang$, for some positive $n$;
\item
a negation $\lnot\phi$ for some formula $\phi$;
\item
an implication $(\phi\to\chi)$ for some formulas $\phi$ and $\chi$;
\item
an existential formula $\Exists x\phi$ for some formula $\phi$ and
some variable $x$.
  \end{mylist}
\end{theorem}

\begin{proof}
  \textbf{Exercise.}
\end{proof}

\subsection*{Towards interpretations in general}

In order to define interpretations of arbitrary formulas, we can still
use~\eqref{eqn:int-not} and ~\eqref{eqn:int-to} above to define
$(\lnot\phi)^{\str A}$ and 
$(\phi\to\chi)^{\str A}$ in terms of $\phi^{\str A}$ and $\chi^{\str
  A}$.  
However, we also must define  $(\Exists
{x}\phi)^{\str A}$ in terms of $\phi^{\str A}$; and we must first
define the \defn{arity} $\Exists x\phi$ in terms of the arity of
$\phi$.  This is not quite so easy.  We shall do it
presently.  When we are done, then, for every $n$-ary formula $\phi$
of $\lang$,
there will be an $n$-ary relation $\phi^{\str A}$ on $A$; this relation is
\defn{defined} by $\phi$, and the relation can be
called a \defn{$0$-definable} relation of $\str A$.  The
\defn{definable} relations are those defined by formulas of
$\lang(A)$; more generally, if $X\included A$, then the $X$-definable
relations are those defined by formulas of $\lang(X)$.  (Singulary
definable relations can just be called definable \defn{sets}.)

If $X$ and $Y$ are $k$-ary definable relations of $\str A$, then so
are $X\comp$, 
$X\cap Y$, $X\cup Y$, \&c.  In short, all \defn{Boolean combinations}
of definable relations are definable, since $\{\lnot{},\to\}$ is an
adequate signature for propositional logic.

Now, if $\phi$ is an $n$-ary formula, defining as such the $n$-ary
relation $X$, then we can also treat $\phi$ as $(n+1)$-ary,
defining the relation $X\times A$ on $A$.  This relation is the set
\begin{equation*}
  \{(\tuple a,b)\in A^{n+1}:\tuple a\in X\}.
\end{equation*}
This set is also $\pi\inv(X)$, where $\pi$ is the function
\begin{equation}\label{eqn:pi}
  (\tuple a,b)\longmapsto\tuple a: A^{n+1}\To A^n;
\end{equation}
this map is \defn{projection} onto the first $n$ coordinates.
In short then, \emph{inverse images} of definable sets under projections
are definable.  Using the quantifier $\exists$ in formulas will allow
\emph{images} under projections to be definable.

Indeed, suppose $\phi$ is an $(n+1)$-ary formula.  Then we can define
$(\Exists{\varble_n}\phi)^{\str A}$ to consist of those $\tuple a$ in $A^n$
such that 
there \emph{exists} $b$ in $A$ such that $(\tuple 
a,b)\in\phi^{\str A}$.
Hence
$(\Exists{\varble_n}\phi)^{\str A}$
is $\pi\setim(\phi^{\str A})$, the image of $\phi^{\str A}$,
where $\pi$ is the projection in \eqref{eqn:pi}.  

But what is $(\Exists{\varble_i}\phi)^{\str A}$ here, if $i<n$?  Defining
this takes a bit more work; see Remark~\ref{rem:def} below.
Meanwhile, we can give an alternative 
approach to interpreting formulas:

\subsection*{Truth}

Let $\Fm{}\lang$ be the set of formulas of $\lang$.  We recursively
define a function
\begin{equation*}
  \phi\longmapsto \fv\phi:\Fm{}\lang\To\pow{\{\varble_k:k\in\varN\}}
\end{equation*}
as follows:
\begin{mylist}
  \item
$\fv\alpha$ is the set of variables in $\alpha$, if $\alpha$ is
    atomic (for an \textbf{exercise}, this can be given a recursive
    definition); 
\item
$\fv{\phi\to\chi}=\fv\phi\cup\fv\chi$;
\item
$\fv{\Exists x\phi}=\fv\phi\setminus\{x\}$.
\end{mylist}
Then $\fv\phi$ is the set of \defn{free variables} of $\phi$.  

If
$\fv\phi=\emptyset$, then $\phi$ is a \defn{sentence}.  So an atomic
sentence $\alpha$ is a nullary atomic formula; in this case, we can
define
\begin{equation}\label{eqn:truth-atomic}
  \str A\models\alpha\Iff \alpha^{\str A}=1;
\end{equation}
in either case, $\alpha$ is \defn{true in $\str A$}.  Otherwise,
$\alpha$ is \defn{false} in $\str A$, and we can write
\begin{equation*}
  \str A\nmodels\alpha.
\end{equation*}
We can also define
\begin{align}\label{eqn:def-neg}
  \str A\models\lnot\sigma&\Iff \str A\nmodels\sigma;\\ \label{eqn:def-to}
\str A\nmodels(\sigma\to\tau)&\Iff \str A\models\sigma\amp
\str A\models\lnot\tau; 
\end{align}
provided $\sigma$ and $\tau$ are sentences for which truth and falsity
in $\str A$ have been defined.  
To define $\str A\models\Exists v\phi$, we should
assume that we have been working with formulas of $\lang(A)$ all
along, and we should define a kind of \tech{substitution}:

For formulas $\phi$, if $\varble$ is a variable and $t$ is a term, we
define the formula
\begin{equation*}
  \phi_t^{\varble}
\end{equation*}
recursively:
\begin{mylist}
  \item
If $\alpha$ is atomic, then $\alpha_t^{\varble}$ is the result of replacing
each occurrence of ${\varble}$ in $\alpha$ with $t$ (as an \textbf{exercise},
you can define this recursively);
\item
$(\lnot\phi)_t^{\varble}$ is $\lnot(\phi_t^{\varble})$;
\item
$(\phi\to\chi)_t^{\varble}$ is $(\phi_t^{\varble}\to\chi_t^{\varble})$;
\item
$(\Exists{\varble}\phi)_t^{\varble}$ is $\Exists{\varble}\phi$ (no change);
\item
$(\Exists u\phi)_t^{\varble}$ is $\Exists u\phi_t^{\varble}$, if $u$
  is not $\varble$. 
\end{mylist}
Then $\phi_t^x$ is the result of replacing each \emph{free} instance
of $x$ in $\phi$ with $t$.
Now we can define
\begin{equation}\label{eqn:truth-E}
  \str A\models\Exists{\varble}\phi\Iff\str
  A\models\phi_a^{\varble}\text{ for some $a$ in $A$.}
\end{equation}
We have now completed the definition of truth; it is expressed by
lines \eqref{eqn:truth-=}, \eqref{eqn:truth-R},
\eqref{eqn:truth-atomic}, \eqref{eqn:def-neg}, \eqref{eqn:def-to} and
\eqref{eqn:truth-E}. 

\subsection*{Interpretations}

If $\fv{\phi}\included\{\varble_k:k<n\}$, then $\phi$ can be called $n$-ary,
and we can write $\phi$ as
\begin{equation*}
  \phi(\varble_0,\dots,\varble_{n-1}).
\end{equation*}
Then, instead of $\phi_{a_0}^{x_0}\dotsb_{a_{n-1}}^{x_{n-1}}$, we
can write
\begin{equation*}
  \phi(a_0,\dots,a_{n-1})
\end{equation*}
or $\phi(\tuple a)$.  (Here, $\tuple a$ is a tuple of
\emph{constants}.  We could let it be a tuple $(t_0,\dots,t_{n-1})$ of
arbitrary terms; but then we should have to ensure that
$\phi(t_0,\dots,t_{n-1})$ is the result of \emph{simultaneously}
substituting each $t_k$ for the free instances of the corresponding
variable $x_k$.) 

\begin{lemma}
  Let $\phi$ be an $n$-ary formula of $\lang$.
  \begin{mylist}
\item    If $\phi$ is atomic, then $\phi^{\str A}=\{\tuple a\in A^n:\str
    A\models\phi(\tuple a)\}$. 
\item
If $\phi$ is $\lnot\chi$, then 
$\{\tuple a\in A^n:\str
    A\models\phi(\tuple a)\}=
\{\tuple a\in A^n:\str
    A\models\chi(\tuple a)\}\comp$.
\item
If $\phi$ is $(\chi\to\psi)$, then
\begin{equation*}
  \{\tuple a\in A^n:\str
    A\models\phi(\tuple a)\}=
\{\tuple a\in A^n:\str
    A\models\chi(\tuple a)\}\comp\cup
\{\tuple a\in A^n:\str
    A\models\psi(\tuple a)\}.
\end{equation*}
\item
If $\phi$ is $\Exists{\varble_n}\chi$, then
\begin{equation*}
  \{\tuple a\in A^n:\str A\models\phi(\tuple a)\}=\pi\setim(\{(\tuple
a,b)\in A^{n+1}:\str A\models\chi(\tuple a,b)\}),
\end{equation*} 
where $\pi$ (as in~\eqref{eqn:pi}) is projection onto the first $n$
coordinates. 
  \end{mylist}
\end{lemma}

\begin{proof}
  \textbf{Exercise.}
\end{proof}

Now we can define
\begin{equation*}
  \phi^{\str A}=\{\tuple a\in A^n:\str A\models\phi(\tuple a)\}
\end{equation*}
for all formulas $\phi$.


In a formula of $\lang(A)$, any constants from $A$ can be called
\defn{parameters}.  So the definable relations of $\str A$ are, more
fully, the relations definable \tech{with parameters}.

\begin{example}
  Algebraic geometry studies the definable relations of $\C$ and of
  other algebraically closed fields.  It can be shown that, on $\C$,
  all definable 
  relations are definable by \emph{open} formulas.  The
  model-theoretic expression for this fact is that the 
  \tech{theory} of algebraically closed fields admits
  \tech{elimination of quantifiers}.
\end{example}

As an \textbf{exercise}, you can think about what are the definable sets of
\begin{myenum}
  \item
the field $\C$;
\item
$(\varN,<,0)$;
\item
$(\varN,<)$;
\item
 $(\varN,s)$, if $s$ is $x\mapsto x+1$;
\item
a set (that is, a structure in the empty signature). 
\end{myenum}
You probably will not be able to \emph{prove} your answers at this point.



  \begin{remark}\label{rem:def}
    To complete our first approach to definable sets, let us ignore the
ordering of $\varN$.  If $I$ is a finite subset of $\varN$, and if
$\{i:\varble_i\in\fv\phi\}\included I$, let us say that $\phi$ is $I$-ary.
Let $A^I$ be the set of functions from $I$ to $A$, a typical such
function being denoted
\begin{equation*}
  (a_i:i\in I).
\end{equation*}
The definition of $\phi^{\str A}$ as a subset of $A^I$ starts out as
before.  To define $(\Exists{\varble_j}\phi)^{\str A}$, let $\pi_j^I$ be the
function
\begin{equation*}
  (x_i:i\in I)\longmapsto (x_i:i\in I\setminus\{j\}):A^I\To
  A^{I\setminus\{j\}}. 
\end{equation*}
Now we can define
\begin{equation*}
  (\Exists {\varble_j}\phi)^{\str A}=(\pi_j^I)\setim(\phi^{\str A}).
\end{equation*}
But this doesn't allow $\Exists v\phi$ to be treated as $J$-ary when
  $J$ contains $j$.  So we should say in addition that if $\phi$
  is $I$-ary, and $J$ is any finite subset of $\varN$, then the set
  \begin{equation*}
    \phi^{\str A}\times A^{J\setminus I}
  \end{equation*}
is the interpretation of $\phi$ when considered as $(I\cup J)$-ary.
Also,
  suppose
$\{i:\varble_i\in\fv{\Exists{\varble_j}\phi}\}\included J$.  Then $\phi$ is
  $(J\cup\{j\})$-ary, and we can define
\begin{equation*}
  (\Exists {\varble_j}\phi)^{\str A}=(\pi_j^{J\cup\{j\}})\setim(\phi^{\str
  A})\times A^{\{j\}\cap J}.
\end{equation*}
This formulation of definable relations is rather complicated to be useful;
the main point is that a geometric characterization of definable
relations is possible:

\begin{theorem}
  The family of $0$-definable relations of a structure $\str A$ of
  $\lang$ is the smallest family of relations on $A$ that is closed
  under Boolean operations, Cartesian products, projections and
  permutations of coordinates; that
  contains the diagonal $\{(a,a):a\in A\}$; and
  that contains the sets $\{c^{\str A}\}$, $R^{\str A}$ and
  $\{(a_0,\dots,a_n):f^{\str A}(a_0,\dots,a_{n-1})=a_n\}$.
\end{theorem}
  \end{remark}

\section{Logical consequence}

Having defined truth, we can define \tech{logical consequence}.  Let
$\Sn$ be the set of sentences of $\lang$.
The $\lang$-structure $\str A$ is a \defn{model} of a subset $\Sigma$ of
$\Sn$ if each sentence in $\Sigma$ is true in $\str A$; then we
can write
\begin{equation*}
  \str A\models\Sigma.
\end{equation*}
If a sentence $\sigma$ is true in every model of $\Sigma$, then
$\sigma$ is a \defn{(logical) consequence} of $\Sigma$, and we can write
\begin{equation*}
  \Sigma\models\sigma.
\end{equation*}
If $\emptyset\models\sigma$, then we can write just
\begin{equation*}
  \models\sigma;
\end{equation*}
in this case, $\sigma$ is a \defn{validity}.


Two sentences are \defn{(logically) equivalent} if
each is a logical consequence of the other.  

\begin{lemma}
Let $\sigma$ and $\tau$ be sentences of $\lang$.
\begin{mylist}
  \item
  $\sigma\models\tau$ if and only if ${}\models(\sigma\to\tau)$,
  for all $\sigma$ and $\tau$ in $\Sn$.
\item
$\sigma$ and $\tau$ are equivalent if and only if
  ${}\models(\sigma\to\tau)\land(\tau\to\sigma)$. 
\item
Logical equivalence is an equivalence-relation on $\Sn$.
\end{mylist}
\end{lemma}

\begin{proof}
  \textbf{Exercise}.
\end{proof}

Instead of the formula
$(\phi\to\chi)\land(\chi\to\phi)$, let us write
\begin{equation*}
  \phi\iff\chi.
\end{equation*}
By the lemma, $\sigma$ and $\tau$ are logically equivalent if and only
if $(\sigma\iff\tau)$ is a validity.
We may blur the
distinction between logically equivalent sentences, identifying
$\sigma$ with $\lnot\lnot\sigma$ for example.

Instead of $\lnot\Exists v\lnot\phi$, we may write
\begin{equation*}
  \Forall v\phi.
\end{equation*}
Then $\lnot\Forall v\phi$ is (equivalent to) $\Exists v\lnot\phi$.


\begin{example}\label{example:entailment}
  The sentence
  \begin{equation*}
      (\Forall x(Px\to Qx)\to(\Forall
xPx\to\Forall xQx))
  \end{equation*}
is a validity, 
 where $P$ and $Q$ are unary predicates.  To prove
this, note that, by \eqref{eqn:def-to}, it is enough to show that
$\str A\models(\Forall xPx\to\Forall xQx)$ whenever $\str
A\models\Forall x(Px\to Qx)$.  So suppose 
\begin{equation}\label{eqn:ex1}
  \str A\models\Forall
x(Px\to Qx).  
\end{equation}
It is now enough to show that, if also $\str
A\models\Forall xPx$, then $\str A\models\Forall xQx$.  So suppose
\begin{equation}\label{eqn:ex2}
  \str A\models\Forall xPx.
\end{equation}
Let $a\in A$.  Then $\str A\models Pa$, by~\eqref{eqn:ex2}.  But $\str
A\models (Pa\to Qa)$, by~\eqref{eqn:ex1}.  Hence $\str A\models Qa$.
Since $a$ was arbitrary, we have $\str A\models\Forall xQx$.
\end{example}


If $\fv\phi=\{u_0,\dots,u_{n-1}\}$, and $\str
A\models\Forall{u_0}\dotsb\Forall{u_{n-1}}\phi$, we may write just
\begin{equation*}
  \str A\models\phi.
\end{equation*}
Here, the sentence $\Forall{u_0}\dotsb\Forall{u_{n-1}}\phi$ is the
\defn{(universal) generalization} of $\phi$.  Now we can define
$\Sigma\models\phi$ for arbitrary formulas $\phi$ (although $\Sigma$
should still be a set of \emph{sentences}); we can also say that
arbitrary formulas $\phi$ and $\chi$ are \defn{(logically) equivalent}
if
\begin{equation*}
  \models(\phi\iff\chi).
\end{equation*}
For the formula $\phi$ with free variables $x_0$, \dots,
$x_{n-1}$, if we have
\begin{equation*}
  \str A\models\Exists{u_0}\dotsb\Exists{u_{n-1}}\phi,
\end{equation*}
then we can say that $\phi$ is \defn{satisfied} in $\str A$.

It can happen then that $\str A\nmodels\phi$ and $\str
A\nmodels\lnot\phi$.  However, if $\sigma$ is a \emph{sentence}, then
either $\sigma$ or $\lnot\sigma$ is true in $\str A$.

\begin{example}
  Each of the following formulas is true in every group:
  \begin{gather*}
    x\cdot(y\cdot z)=(x\cdot y)\cdot z,\\
    \begin{aligned}
      x\cdot 1&=x,\\
1\cdot x&=x,
    \end{aligned} \qquad
    \begin{aligned}
      x\cdot x\inv=1,\\
x\inv\cdot x=1.
    \end{aligned}
  \end{gather*}
\end{example}

If $\Sigma\included\Sn$, let
\begin{equation*}
  \Cn \Sigma=\{\sigma\in\Sn:\Sigma\models\sigma\}.
\end{equation*}

\begin{lemma}
  $\Cn{\Cn\Sigma}=\Cn\Sigma$.
\end{lemma}

\begin{proof}
Since  $\Sigma\included\Cn\Sigma$, we have $\Cn\Sigma\included\Cn{\Cn\Sigma}$.
  Suppose $\sigma\in\Cn{\Cn\Sigma}$.  Then $\Cn\Sigma\models\sigma$.
  But if $\str A\models\Sigma$, then $\str A\models\Cn\Sigma$, so in
  this case $\str A\models\sigma$.  Thus $\sigma\in\Cn\Sigma$.
\end{proof}

A subset $T$ of $\Sn$ is a \defn{theory} of $\lang$ if $\Cn T=T$.  A
subset $\Sigma$ of a theory $T$ is a set of \defn{axioms} for $T$ if 
\begin{equation*}
  T=\Cn\Sigma;
\end{equation*}
we may also say then that $\Sigma$ \defn{axiomatizes} $T$.

\begin{example}\label{examp:groups}
  The theory of groups is axiomatized by
  \begin{gather*}
   \Forall x\Forall y \Forall z x\cdot(y\cdot z)=(x\cdot y)\cdot z,\\
    \begin{aligned}
    \Forall x  x\cdot 1&=x,\\
\Forall x 1\cdot x&=x,
    \end{aligned} \qquad
    \begin{aligned}
    \Forall x  x\cdot x\inv=1,\\
\Forall x x\inv\cdot x=1.
    \end{aligned}
  \end{gather*}
\end{example}

If $\str A$ is an $\lang$-structure, let
\begin{equation*}
  \Th{\str A}=\{\sigma\in\Sn:\str A\models\sigma\}.
\end{equation*}

\begin{lemma}
  $\Th{\str A}$ is a theory.
\end{lemma}

\begin{proof}
  Say $\Th{\str A}\models\sigma$.  Since $\str A\models\Th{\str A}$,
  we have $\str A\models\sigma$, so $\sigma\in\Th{\str A}$.
\end{proof}

We can now call $\Th{\str A}$ the \defn{theory of} $\str A$.  Note
that, if $T$ is $\Th{\str A}$, then
\begin{equation*}
  T\models\sigma\Iff T\nmodels\lnot\sigma
\end{equation*}
for all sentences $\sigma$.
An arbitrary theory $T$ need not have this property; if it does,
then $T$ is \defn{complete}.  So, the theory \emph{of} a structure is
always complete.  The converse holds, by the next lemma; also,
the set $\Sn$ is a theory, but it is not
complete:  

\begin{lemma}\label{lem:complete}
Let $T$ be a theory of $\lang$.
\begin{mylist}
  \item
If $T$ has no model, then $T$ is $\Sn$ itself.  
\item
If $T$ is complete, then $T$ is $\Th{\str A}$ for some structure $\str
A$, which is a model of $T$. 
\item
If $T$ has a model $\str A$, then $T$ is included in $\Th{\str A}$,
which is a complete
theory: in particular
\begin{equation*}
  T\models\sigma\implies T\nmodels\lnot\sigma
\end{equation*}
for all $\sigma$ in $\Sn$.  
\item
Hence, to prove that $T$ is complete,
it is enough to show that $T$ has models and 
\begin{equation*}
  T\nmodels\sigma\implies  T\models\lnot\sigma
\end{equation*}
for all $\sigma$ in $\Sn$.
\end{mylist}
\end{lemma}

\begin{proof}
Consider the points in order:
\begin{mylist}
  \item
If $T$ is a theory with no models, and $\sigma$ is a sentence, then
  $\sigma$ is true in every model of $T$, so $T\models\sigma$, whence
  $\sigma\in T$.  
\item
If $T$ is complete, then by definition it cannot contain all
sentences, so it must have a model $\str A$.  Then $T\included\Th{\str
  A}$.  By this and completeness of $T$, we have
\begin{equation*}
  T\models\sigma\implies\alpha\models\sigma\implies
  \alpha\nmodels\lnot\sigma\implies T\nmodels\lnot\sigma\implies
  T\models\sigma
\end{equation*}
for all $\sigma$ in $\Sn{}{}$.  In short,
$T\models\sigma\Iff\str A\models\sigma$,
so $T=\Th{\str A}$.
\item
The set $\{\sigma,\lnot\sigma\}$ has no models.  
\item
Obvious.
\end{mylist}
This completes the proof.
\end{proof}

We can also speak of the theory of a \emph{class} of
$\lang$-structures.  If $K$ is such a class, then
$\Th K$ is the set of sentences of $\lang$ that are true in
\emph{every} structure in $K$.

In particular, if $\Sigma\included\Sn$, then we can define
\begin{equation*}
  \Mod \Sigma
\end{equation*}
to be the class of all models of $\Sigma$.  Then
\begin{equation*}
  \Th{\Mod\Sigma}=\Cn\Sigma.
\end{equation*}

\begin{example}
By definition, a group is just a model of the theory of groups, as
  axiomatized in Example~\ref{examp:groups}.  Hence this theory
  is $\Th K$, where $K$ is the class of all groups.
\end{example}

\section{Additional exercises}



\begin{myenum}
  \item
Letting $P$ and $Q$ be unary predicates, determine, from the
    definition of $\models$, whether the following hold.  (A method is
    shown in Example~\ref{example:entailment}.)
    \begin{mylist}
            \item
$(\Exists xPx\to \Exists xQx)\models\Forall x(Px\to Qx)$;
\item
$(\Forall xPx\to\Exists xQx)\models\Exists x(Px\to Qx)$;
\item
$\Exists x(Px\to Qx)\models(\Forall xPx\to\Exists xQx)$;
    \item
$\{\Exists x Px,\;\Exists xQx\}\models\Exists x(Px\land Qx)$;
\item
$\Exists xPx\to\Exists yQy\models\Forall x\Exists y(Px\to Qy)$.
    \end{mylist}
\item
Let $\lang=\{R\}$, where $R$ is a binary predicate, and let $\str A$
be the $\lang$-structure $(\Z,\leq)$.  Determine $\phi^{\str A}$ if
$\phi$ is:
\begin{mylist}
  \item
$\Forall {x_1}(Rx_1x_0\to Rx_0x_1)$;
\item
$\Forall {x_2}(Rx_2x_0\lor Rx_1x_2)$.
\end{mylist}
\item
    Let $\lang$ be $\{S,P\}$, where $S$ and $P$ are binary
    function-symbols.  Then $(\R,+,\cdot)$ is an $\lang$-structure.
    Show that the following sets and relations are definable in this
    structure:
    \begin{mylist}
            \item
$\{0\}$;
\item
$\{1\}$;
\item
$\{a\in\R:0< a\}$;
\item
$\{(a,b)\in\R^2:a<b\}$.
    \end{mylist}
\item
    Show that the following sets are definable in
    $(\varN,+,\cdot,\leq,0,1)$:
    \begin{mylist}
      \item
the set of even numbers;
\item
the set of prime numbers.
    \end{mylist}
\item
  Let $R$ be the binary
  relation 
  \begin{equation*}
      \{(x,x+1):x\in \Z\}
  \end{equation*}
 on $\Z$.  Show that $R$ is $0$-definable in the structure $(\Z,<)$;
  that is, find a binary formula $\phi$ 
  in the signature $\{<\}$ such that $\phi^{(\Z,<)}=R$.
\end{myenum}