\chapter{Introduction}\label{ch:intro}

These notes are based on lectures given for Math 406,
`Introduction to
Mathematical Logic and Model-theory', at METU in 2004.  I have
expanded on a few points and rearranged some topics.

Background reading includes \cite{111-2004}.  Exercises appear here
and there, emphasized with bold type; and there are some sections
comprising exercises, as you can see from the table of contents.

\section{Building-blocks}

An \defn{ordered pair} $(a,b)$ is the set $\{\{a\},\{a,b\}\}$.  Then
the \defn{Cartesian product} $A\times B$ of the sets $A$ and $B$ is
the set
\begin{equation*}
  \{(a,b):a\in A\amp b\in B\}.
\end{equation*}
To express that $f$ is a \defn{function} from $A$ to $B$, we can just
write
\begin{equation*}
  f:A\To B.
\end{equation*}
This means $f$ is a subset of $A\times B$ with a certain property
(namely, for every $a$ in $A$, there is a unique $b$ in $B$ such that
$(a,b)\in f$; then we write $f(a)=b$).
The set of all functions from $A$ to $B$ can be denoted
\begin{equation}\label{eqn:map-set}
  B^A.
\end{equation}
(Some people write ${}^AB$.)
Let $\varN$ be the set of \defn{natural numbers}:
\begin{align*}
  \varN &= \{0,1,2,3,\dots\}\\
        &= \{0,0',0'',0''',\dots\}.
\end{align*}
It is notationally convenient to treat $0$ as $\emptyset$, and $x'$ as
$x\cup\{x\}$.  Then 
\begin{equation*}
  n=\{0,\dots,n-1\}
\end{equation*}
for all $n$ in $\varN$.  Under this understanding of the natural
numbers, the \defn{$n$th Cartesian power} of $A$ is precisely
\begin{equation*}
  A^n,
\end{equation*}
in the notation introduced on line~\eqref{eqn:map-set} above:
the $n$th Cartesian power of $A$ is the set of functions from $n$ to
$A$.  An element of $A^n$ can be written as 
\begin{equation*}
  (a_0,\dots,a_{n-1})
\end{equation*}
 or $\mathbf a$
or $\tuple a$; the function is then, in any case,
\begin{equation*}
  i\longmapsto a_i:n\To A,
\end{equation*}
and it can be called an \defn{(ordered) $n$-tuple} from $A$.

Note well that $A^0=\{\emptyset\}=\{0\}=1$; this is true even if $A$
is empty.  Also, every element of $A^1$ is $\{(0,a)\}$ for some $a$ in
$A$.  So we have a bijection
\begin{equation}\label{eqn:A1}
  a\longmapsto\{(0,a)\}:A\To A^1.
\end{equation}
We may sometimes treat this bijection as an \defn{identification};
that is, we may decide not to distinguish between $a$ and
$\{(0,a)\}$.

For any $m$ and $n$ in $\varN$, we have a bijection
\begin{equation}\label{eqn:concat}
  (\tuple a,\tuple b)\longmapsto \tuple a\concat\tuple b:A^m\times
  A^n\To A^{m+n}
\end{equation}
where $\tuple a\concat\tuple b$ is the $(m+n)$-tuple
$(a_0,\dots,a_{m-1},b_0,\dots,b_{n-1})$; this is the $(m+n)$-tuple 
 $\tuple c$ such
that
\begin{equation*}
  c_k=
  \begin{cases}
    a_k,&\text{ if }k<m;\\
    b_{k-m},&\text{ if }m\leq k<m+n.
  \end{cases}
\end{equation*}
We always treat the bijection in \eqref{eqn:concat} as an
identification. 

An \defn{$n$-ary operation on $A$} is a function from $A^n$ to $A$.
The set of these can be denoted
\begin{equation*}
  A^{A^n}.
\end{equation*}
In particular, a $0$-ary or \defn{nullary} operation on $A$ is an element of
$A^1$; by the bijection in~\eqref{eqn:A1} then, we may identify a
nullary operation on $A$ with an element of $A$.  

An \defn{$n$-ary relation on $A$} is a subset of $A^n$; the set of
these is $\pow{A^n}$.  

An $n$-ary operation on $A$ is then a (certain kind of) subset of
$A^n\times A$, and this product can be identified with $A^n\times A^1$
and hence with $A^{n+1}$; so an $n$-ary operation on $A$ can be
thought of as an $(n+1)$-ary relation on $A$.

\section{Structures}\label{S:structures}

Our fundamental object of study will be \tech{structures}.  The notion
of a structure provides a way to unify the treatment of many
mathematical ideas.  By our official definition,
a \defn{structure} is an ordered pair $(A,\interpretation)$, also
referred to as $\str A$, where:
\begin{mylist}
  \item
$A$ is a non-empty set, called the \defn{universe} of the structure;
\item
$\interpretation$ is a function, written also
  \begin{equation*}
    s\longmapsto s^{\str A},
  \end{equation*}
whose domain $\lang$ is called the \defn{signature} of the structure;
\item
$s^{\str A}$ is either an element of $A$ or an $n$-ary operation or
  relation on $A$ for some positive $n$, for each $s$ in $\lang$.
\end{mylist}
If $\lang=\{s_0,s_1,\dots\}$, then $\str A$ can be written
\begin{equation*}
  (A,s_0^{\str A}, s_{1}^{\str A},\dots).
\end{equation*}

\begin{examples}\label{examples:structures}
The following are structures:
  \begin{myenum}
    \item
  $(\varN,{}',0)$;
\item
a group $(G,\cdot,{}\inv,1)$;
\item
an abelian group $(G,+,-,0)$;
\item
a ring $(R,+,-,\cdot,0,1)$;
\item
the ring $\Z$ or $(\Z,+,-,\cdot,0,1)$;
\item
the field $\R$ or $(\R,+,-,\cdot,0,1)$;
\item
a partial order $(X,\leq)$;
\item
a vector-space $V$ over a field $K$; here the signature of $V$ is
$\{+,-,0\}\cup\{a\cdot{}:a\in K\}$, where $a\cdot{}$ is the unary
operation of multiplying by $a$;
\item
the \defn{power-set} structure on a non-empty set $\Omega$, namely
\begin{equation*}
  (\pow{\Omega},\cap,\cup,{}\comp,\emptyset,\Omega,\included); 
\end{equation*}
\item
the \defn{truth-}structure
\begin{equation*}
  (\B,\land,\lor,\lnot{}, 0,1,\models), 
\end{equation*}
where $\B=\{0,1\}$, and
  $\models$ is the binary relation $\{(0,0), (0,1), (1,1)\}$.   (The name
  `truth-structure' is my invention.)
  \end{myenum}
\end{examples}
The last two examples are the same if
  $\Omega=1$.  \defn{Propositional logic} studies the truth-structure;
  \defn{model-theory} studies \emph{all} structures.


With $\interpretation$ as above in the structure $(A,\interpretation)$:
\begin{mylist}
  \item
$s^{\str A}$ is the \defn{interpretation} in $\str A$ of $s$;
\item
$s$ is a \defn{symbol} for $s^{\str A}$.
\end{mylist}
So $s$ is one of the following:
\begin{mylist}
  \item
a \defn{constant};
\item
an \defn{$n$-ary function-symbol} for some positive $n$ in $\varN$;
\item
an \defn{$n$-ary predicate} (or \defn{relation-symbol}) for some
positive $n$ in $\varN$.  
\end{mylist}

Since nullary operations on $A$ can be considered as elements of $A$,
a constant can be considered as a nullary function-symbol.

Here are some observations about our definition of \tech{structure}:
\begin{mylist}
  \item
I am following the old convention (used for example in
\cite{MR0409165}) of denoting the universe of a structure by a Roman
letter, and the structure itself by the corresponding Fraktur or
Gothic letter.  Recent writers (as in \cite{MR1924282} or
\cite{MR1800596}) use `calligraphic' letters, not Fraktur:
\begin{center}
  \begin{tabular}{r | c | c | c | c | c | c | c}
For a structure with universe: & $A$ & $B$ & $C$ & \dots & $M$ & $N$ &
\dots \\ \hline
\rule{0mm}{4mm}I write: & $\str A$ & $\str B$ & $\str C$ &
\dots & $\str M$ & $\str N$ & \dots\\ \hline 
\rule{0mm}{4mm}Others may write: & $\mathcal A$ & $\mathcal B$ &
$\mathcal C$ & \dots & $\mathcal M$ & $\mathcal N$ & \dots
  \end{tabular}
\end{center}
Another option (taken in \cite{MR94e:03002}) is to use an ordinary letter
like $A$ for a structure, and then $\operatorname{dom}(A)$ for its
universe.  (Here `dom' stands for \tech{domain}.)
Finally, one might not bother to make a typographical
distinction between a structure and its universe.  Indeed, as
suggested in the examples, the
distinction is not easy to make with standard structures like $\Z$ or
$\R$. 
\item
Similarly, it is not always easy or convenient to distinguish between
a symbol and its interpretation.  A \defn{homomorphism} from a group
$G$ to a group $H$ is usually described as a function $f$ from $G$ to
$H$ such that 
\begin{equation*}
  f(g_0\cdot g_1)=f(g_0)\cdot f(g_1)
\end{equation*}
for all $g_e$ in $G$.  If we are trying to be precise, we should call
the groups $\str G$ (or $(G,\cdot^{\str G})$) and $\str H$ (or
$(H,\cdot^{\str H})$), and we should say that $f$ is such that
\begin{equation*}
  f(g_0\cdot^{\str G} g_1)=f(g_0)\cdot^{\str H} f(g_1)
\end{equation*}
for all $g_e$ in $G$.  But writing this way soon becomes tedious.
\item
In a structure $(A,\interpretation)$, the
\defn{interpretation}-function $\interpretation$ could be considered
to carry, within itself, the identity of the universe $A$.  
This is certainly true if the signature $\lang$ of the structure contains a
unary function-symbol $f$, since then $\interpretation$ determines
the function $f^{\str A}$ and hence its domain, $A$.  In any case, $A$
and $\interpretation$ work together to provide interpretations of the
symbols in $\lang$ \emph{as} elements of, or operations or relations on,
a certain set, namely $A$ itself.  That's all a structure is:
something that provides a mathematical 
interpretation for certain symbols.  We shall develop this idea
later.  What makes model-theory interesting is that the same symbols
can have different interpretions.  Here begins the distinction between
\defn{syntax} \label{syntax} (formal symbolism) and \defn{semantics}
(mathematical 
meaning). 
\end{mylist}


\section{Propositional logic}

Of the so-called \tech{truth-structure} given in the
Examples~\ref{examples:structures}, the signature is
\mbox{$\{\land,\lor,\lnot,0,1,\models\}$.}  Besides the binary predicate
$\models$ (which could also be written $\leq$), the symbols are
\defn{Boolean connectives}.  Other Boolean connectives are also used.
Each Boolean connective is an $n$-ary function-symbol for some $n$ in $\varN$,
and each has a standard interpretation as an operation on $\B$.
For example:
\begin{myenum}\setcounter{myenum}{-1}
\item
$0$ and $1$ are nullary connectives;
\item
$\lnot$ is a singulary or unary connective;
\item
$\land$, $\lor$, $\to$ and $\iff$ are binary connectives.
\end{myenum}
To give the interpretations of the connectives, we can understand $\B$
as a two-element abelian group with the addition-table
\begin{center}
  \begin{tabular}{c | cc}
$+$ & $0$ & $1$ \\ \hline
$0$ & $0$ & $1$ \\
$1$ & $1$ & $0$
  \end{tabular}.
\end{center}
Then one way to give the standard interpretations is:
\begin{myenum}\setcounter{myenum}{-1}
\item
the nullary connectives $0$ and $1$ are interpreted as themselves;
\item\label{page:lnot}
$\lnot$ is interpreted as the singulary operation $x\mapsto x+1$ on
  $\B$ 
\item
$\land$, $\lor$, $\to$ and $\iff$ are interpreted as the
  binary operations on $\B$ taking $(x,y)$ to $xy$, $xy+x+y$,
  $xy+x+1$ and $x+y+1$ respectively.
\end{myenum}
These interpretations can be given in other (but equivalent) ways:
For example, we can define $\to$
 by
\begin{equation*}
  (x\to y)=1\Iff x\models y.
\end{equation*}

In general,
a \defn{signature} for propositional logic is a set of Boolean
connectives.  Let $\lang$ be such.  The \defn{formulas} of $\lang$ are
certain strings of:
\begin{mylist}
  \item
symbols from $\lang$;
\item
\defn{propositional} variables $P_0$, $P_1$, $P_2$, \dots.
\end{mylist}
In particular:
\begin{mylist}
  \item
$P$ is a formula, if $P$ is a variable.
\item
$*F_0\dotsb F_{n-1}$ is a formula, if $*$ is an $n$-ary connective
  from $\lang$, and the $F_i$ are formulas.  (If $n=0$, then $*$ by
  itself is a formula.)
\end{mylist}
Commonly, if $*$ is binary, then, instead of $*F_0F_1$, one writes
\begin{equation*}
  (F_0*F_1).
\end{equation*}
A formula is \defn{$n$-ary} if its variables belong to the set
$\{P_0,\dots,P_{n-1}\}$.  (Alternatively, one may want to refer to a
formula as $n$-ary if it contains no more than $n$ distinct
variables.) 

Since each Boolean connective $*$ has a standard interpretation, also
denoted $*$, every $n$-ary formula
$F$ \defn{represents} an $n$-ary operation 
\begin{equation*}
  \tuple x\longmapsto \widehat F(\tuple x):\B^n\To \B
\end{equation*}
as follows:
\begin{mylist}
  \item
If $k<n$, then $P_k$ is an $n$-ary formula and, as such, represents
the operation
\begin{equation*}
  \tuple x\longmapsto x_k:\B^n\To\B
\end{equation*}
(which can be denoted $\widehat P_k$).
\item
If $*$ is $n$-ary, and $F_0$, \dots, $F_{n-1}$ are $k$-ary, then
$*F_0\dotsb F_{n-1}$ represents
\begin{equation*}
  \tuple x\longmapsto {}*(\widehat F_0(\tuple x),\dots,\widehat
F_{n-1}(\tuple x)):\B^k\To\B.
\end{equation*}
\end{mylist}
The notion that a propositional formula represents an operation will be
developed further in the next chapter in case $\lang$ is
$\{\lnot,\to\}$.  We shall be able to restrict ourselves to this
signature, because it is \tech{adequate}.
In general, a signature for propositional logic is \defn{adequate} if,
for each $n$-ary operation $f$ on
$\B$, there is an $(n+k)$-ary formula $F$ of $\lang$ (for some $k$)
such that
\begin{equation*}
  f(\tuple x)=\widehat F(\tuple x,\tuple y)
\end{equation*}
for all $\tuple x$ in $\B^n$ and $\tuple y$ in $\B^k$: that is, every
operation $f$ on $\B$ is \defn{represented} in $\lang$ by some formula
$F$.  
We allow the \tech{arity} of $F$ to be larger than that of $f$, since we
want it to be possible for signatures without nullary connectives to
be adequate.  (If something is $n$-ary, then its \defn{arity} is $n$.)
The following is proved in \cite{Post}:

\begin{theorem}
  A signature of propositional logic is adequate, provided that in it
  are represented:
  \begin{mylist}
    \item
the constant functions $0$ and $1$;
\item
the ternary function $f$ given by
\begin{center}
  \begin{tabular}{c|c|c|c}
$e_0$ & $e_1$ & $e_2$ & $f(\tuple e)$\\ \hline
$0$&$0$&$0$&$0$\\
$1$&$0$&$0$&$1$\\
$0$&$1$&$0$&$0$\\
$1$&$1$&$0$&$1$\\
$0$&$0$&$1$&$0$\\
$1$&$0$&$1$&$0$\\
$0$&$1$&$1$&$1$\\
$1$&$1$&$1$&$1$
  \end{tabular}.
\end{center}
  \end{mylist}
\end{theorem}

\begin{proof}
  By induction.  The nullary operations are represented by assumption.
  Suppose all
  $n$-ary operations are represented, and $g$ is $(n+1)$-ary.  Let
  $h_e$ be the $n$-ary operation $\tuple x\mapsto g(\tuple x,e)$, if
  $e\in \B$.  Then $g$ is
  \begin{equation*}
    (\tuple x,y)\longmapsto f(h_0(\tuple x),h_1(\tuple x),y).
  \end{equation*}
Since the $h_e$ are represented by inductive hypothesis, and $f$ is
represented by assumption,
$g$ is also represented.  By induction, the operations of all arities are
represented. 
\end{proof}

\begin{example}\label{example:prop}
The propositional signature  $\{\to,\lnot{}\}$ is adequate, because:
\begin{mylist}
  \item
  $P_0\to P_0$ represents $1$;
\item
  $\lnot(P_0\to P_0)$ represents $0$;
\item
the operation $f$ as in the theorem is
  represented by the formula 
  \begin{equation*}
      \lnot((\lnot P_2\to P_0)\to \lnot(P_2\to P_1)),
  \end{equation*}
  since its \defn{truth-table} is:
  \begin{center}
    \begin{tabular}{c|c|c|c|c|c|c|c|c|c}
$\lnot$ & $((\lnot$ & $P_2$ & $\to$ & $P_0)$ & $\to$ & $\lnot$ & $(P_2$ &
      $\to$ & $P_1))$\\ \hline
$0$&$1$&$0$&$0$&$0$&$1$&$0$&$0$&$1$&$0$\\
$1$&$1$&$0$&$1$&$1$&$0$&$0$&$0$&$1$&$0$\\
$0$&$1$&$0$&$0$&$0$&$1$&$0$&$0$&$1$&$1$\\
$1$&$1$&$0$&$1$&$1$&$0$&$0$&$0$&$1$&$1$\\
$0$&$0$&$1$&$1$&$0$&$1$&$1$&$1$&$0$&$0$\\
$0$&$0$&$1$&$1$&$1$&$1$&$1$&$1$&$0$&$0$\\
$1$&$0$&$1$&$1$&$0$&$0$&$0$&$1$&$1$&$1$\\
$1$&$0$&$1$&$1$&$1$&$0$&$0$&$1$&$1$&$1$
    \end{tabular}.
  \end{center}
(See also \cite[\S~2.2--3]{111-2004}.  This formula is \defn{logically
  equivalent}---or \tech{truth-equivalent} in the sense of
  \cite[\S~2.4]{111-2004}---to $(\lnot P_2\to P_0)\land(P_2\to 
  P_1)$.) 
\end{mylist}
\end{example}