\documentclass{article}
\usepackage{flannery}
\psetupNotes
%%% my environments
\newtheorem*{theorem}{Theorem}
\theoremstyle{definition}\newtheorem*{definition}{Definition}
\theoremstyle{definition}\newtheorem*{notation}{Notation}
\theoremstyle{definition}\newtheorem*{exercise}{Exercise}
\theoremstyle{definition}\newtheorem*{corollary}{Corollary}
\theoremstyle{definition}\newtheorem*{example}{Example}
\newcommand{\huha}{\ensuremath{\vdash}\xspace}
\newcommand{\huhb}{\ensuremath{\vdash\dashv}\xspace}
\newcommand{\mlA}{\ensuremath{\mathfrak{A}}\xspace}
\newcommand{\mlB}{\ensuremath{\mathfrak{B}}\xspace}
\newcommand{\mlC}{\ensuremath{\mathfrak{C}}\xspace}
\newcommand{\mlD}{\ensuremath{\mathfrak{D}}\xspace}
\newcommand{\mlR}{\ensuremath{\mathfrak{R}}\xspace}
\newcommand{\mlQ}{\ensuremath{\mathfrak{Q}}\xspace}
\newcommand{\mlS}{\ensuremath{\mathfrak{R}}\xspace}
\newcommand{\mlT}{\ensuremath{\mathfrak{T}}\xspace}
\title{A Mathematical Introduction to Logic\\by Herbert B. Enderton\\Annotated Notes and Ramblings of a Tired Student}
\author{Prepared by Ryan Flannery}
\date{}
\begin{document}
\maketitle
\begin{center}
{\LARGE\bf These Notes are ROUGH and incomplete!\\
Once I have some free time they will be corrected and completed!}
\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{section}{1}\section{First-Order Logic}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{subsection}{1}\subsection{Truth And Models}
\begin{quote}
In sentential logic, we had truth assignments to tell us which sentence symbols
were to be interpreted as being true and whcih as false. In first-order logic,
the analogous role is played by {\em structures}, which can be thought of as
providing the dictionary for translations from the formal language into
English. Structures are sometimes called {\em interpretations}, but we prefer
to reserve that word for another concept encountered later.
\end{quote}
For a first-order language, a structure will consist of two things:
\begin{enumerate}
\item What collection of things the universal quantifier symbol ($\forall$)
refers to (i.e. the universe our structure is describing), and
\item What the other parameters (the predicate and function symbols) denote
\end{enumerate}
We may represent a structure \mlA as follows:
\begin{equation} \mlA=(U;\;P,\;f,\;c) \end{equation}
Where each symbol represents the following:
\begin{itemize}
\item $U^{\mlA}$ represents the universe (sometimes abbreviated $|\mlA|$)
and is the set of all objects that $\forall$ quantifies over
\item $P^{\mlA}$ represents some $n$-ary relation on $U$
\item $f^{\mlA}$ represents some $n$-ary function on $U$
\item $c^{\mlA}$ represents some constant symbol
\end{itemize}
If this doesn't make immediate sense, the following example should clear
things up.
\begin{example}
Let's assume we want to work in a system of basic number theory. Assume
our reduct of number theory contains the operations $S$ (successor
function) and $+$ (addition), the binary relation $\le$, a constant symbol
$0$, and that our universe is \setN (the set of all natural numbers). Our
structure \mlA would then be represented as follows:
\begin{equation} \mlA=(\setN;\;\le,\;S,\;+,\;0) \end{equation}
\end{example}
Now, certain statements may be true in one model and not another. To express
this, we introduce the following notation, that may be read as ``$\sigma$ is
true in \mlA''. \begin{equation} \proves_\mlA\sigma \end{equation}
\begin{theorem}
Assume that $s_1$ and $s_2$ are functions from $V$ (the set of all
variables) into $|\mlA|$ which agree at all variables (if any) that occur
in the wff $\phi$. Then
\begin{eqnarray}
\proves_\mlA\phi[s_1] & \text{iff} & \proves_\mlA\phi[s_2]
\end{eqnarray}
\end{theorem}
\begin{corollary}
For a sentence $\sigma$, either
\begin{enumerate}
\item \mlA satisfies $\sigma$ with every function $s$
from $V$ into $|\mlA|$
\item \mlA does not satisfy $\sigma$ with any such
function
\end{enumerate}
If (1) holds, then it is said that $\sigma$ is {\em true} in
\mlA (writtten $\proves_\mlA\sigma$) or that \mlA is a {\em model} of
$\sigma$. If (2) holds, then $\sigma$ is {\em false} in \mlA.
Notice that they cannot both hold since $|\mlA|$ cannot be empty.\\
Further, it is said that \mlA is a model of a set $\Sigma$ of sentences iff
it is a model of every member of $\Sigma$.
\end{corollary}
\begin{example}
Let \mlR be the real field (number theory with real numbers), with
$\mlR=(\setR;\;0,\;1,\;+,\;\times)$, and let \mlQ be the rational field
(number theory with rational numbers only), with
$\mlQ=(\setQ;\;0,\;1,\;+,\;\times)$. Is there a sentence $\sigma$ true
in one and false in the other?\\
Yes. Let $\sigma=\exists x(x\cdot x=1+1)$. The only possible value for
$x$ in $\sigma$ is $\sqrt{2}$, wich is not a rational number but is a real
number. Thus, $\proves_\mlR\sigma$ but $\not\proves_\mlQ\sigma$.
\end{example}
Enderton now begins formally developing a notion of logical implication.
In Endertion, logical implication is defined as follows:
\begin{definition}[Logical Implication \& Equivalence]
Let $\Gamma$ be a set of wffs, and $\phi$ a wff. Then $\Gamma$
{\em logically implies} $\phi$, written $\Gamma\implies\phi$ iff for every
structure \mlA for the language and every function $s:V\to|\mlA|$ such
that $\mlA$ satisfies every member of $\Gamma$ with $s$, \mlA also
satisfies $\phi$ with $s$.\\
Further, we define $\phi$ and $\psi$ to be {\em logically equivalent} iff
$\phi\implies\psi$ and $\psi\implies\phi$.
\end{definition}
The first-order analogue of the concept of a tautology is the concept of a
valid formula: A wff $\phi$ is {\em valid} iff $\emptyset\implies\phi$
(written $\implies\phi$). Thus $\phi$ is valid iff for every \mlA and every
$s:V\to|\mlA|$, \mlA satisfies $\phi$ with $s$.
\begin{corollary}
For a set $\Sigma$ and $\tau$ of sentences, $\Sigma\implies\tau$ iff every
model of $\Sigma$ is also a model of $\tau$. A sentence $\tau$ is valid
iff it is true in every structure.
\end{corollary}
Next, Enderton devlops the notion of {\em definability} in a structure, that
is, what is a given structure capable of defining?\\
A good example is the case of the real field, given by
$\mlR=(\setR;\;0,\;1,\;+,\;\times)$. In \mlR, what numbers could we define?
What set of numbers can be defined in $|\mlR|$ using only first-order logic
and the other symbols provided?\\
Consider the sentence $\sigma$, where $\sigma=\exists v_2(x=v_2\times v_2)$.
$\sigma$ then defines the set of all positive numbers, but leaves out all
negative numbers. Thus, we can say that $\sigma$ defines the interval
$[0,\infinity)$ in \mlR.
Now, we want to be able to determine what kind of models (what {\em class} of
models) will satisfy a given set of sentences. Consider a given set $\Sigma$
of sentences. $Mod\;\Sigma$ is then defined as the class of all structures
where each structure satisfies each member of $\Sigma$. We say that
$Mod\;\Sigma$ defines a {\em class} of structures, as opposed to a {\em set},
because the number of structures is too large to be a set and is a proper
class (as long as $Mod\;\Sigma$ is nonempty, of course).\\
We say that a class $\kappa$ of structures is an {\em elementary class (EC)}
iff $\kappa = Mod\;\tau$ for some sentence $\tau$. Also, $\kappa$ is an
{\em elementary class in the wider sense ($EC_\delta$)} iff
$\kappa=Mod\;\Sigma$ for some set $\Sigma$ of sentences.
Dealing with so many structures, is it possible for any two distinct
structures to be ``equivalent''? And if so, how?\\
Here is where Enderton develops a notion equivalence among structures.
\begin{definition}[Isomorphic Structures]
Two structure, \mlA and \mlB, are said to be {\em isomorphic} iff there is
a one-to-one correspondence betwen their universes, $|\mlA|$ and $|\mlB|$,
that preserves the operations and relations.
\end{definition}
To formally define this notion and to show that two isomorphic structures must
satisfy exactly the same sentences, we introduce the notion of a
{\em homomorphism}.
\begin{definition}[Homomorphism \& Isomorphism]
Let \mlA and \mlB be two distinct structures. A {\em homomorphism h} of
\mlA into \mlB is a function $h:|\mlA|\to|\mlB|$ with the properties:
\begin{enumerate}
\item For each $n$-place predicate parameter $P$ and each $n$-tuple
$$ of elements of $|\mlA|$,
\begin{eqnarray}
\in P^\mlA & \text{iff} & \in P^\mlB
\end{eqnarray}
\item For each $n$-place function symbol $f$ and each $n$-tuple,
\begin{equation}
h(f^\mlA(a_1,\ldots,a_n))=f^\mlB(h(a_1),\ldots,h(a_n))
\end{equation}
For any constant symbols, we simply have
\begin{equation}
h(c^\mlA=c^\mlB
\end{equation}
\end{enumerate}
If $h$ is one-to-one, then it is called an {\em isomorphism}.
\end{definition}
\begin{theorem}[Homomorphism Theorem]
Let $h$ be a homomorphism of \mlA into \mlB, and let $s$ map the set of
variables into $|\mlA|$. Then,
\begin{enumerate}
\item For any term $t$, we have
$h(\overline{s}(t))=\overline{h\circ s}(t)$, where $\overline{s}(t)$ is
computed in \mlA and $\overline{h\circ s}(t)$ is computed in \mlB.
\item For any quantifier-free formula $\alpha$ not containing the
equality symbol,
\begin{eqnarray}
\proves_\mlA \alpha[s] & \text{iff} \proves_\mlB \alpha[h\circ s]
\end{eqnarray}
\item If $h$ is one-to-one then in part (2), we may delete the
restriction that $\alpha$ not contain the equality symbol.
\item If $h$ is a homomorphism of \mlA {\em onto} \mlB, then in part (2)
we may delete the restriction that $\alpha$ be quantifier-free.
\end{enumerate}
\end{theorem}
\begin{definition}[Elementarily Equivalent Structures]
To structures \mlA and \mlB are said to be {\em elementarily equivalent}
(written $\mlA\equiv\mlB$) iff for any sentence $\sigma$,
\begin{eqnarray}
\proves_\mlA\sigma & \liff & \proves_\mlB\sigma
\end{eqnarray}
\end{definition}
\begin{corollary}
Isomorphic structures are elementarily equivalent. That is,
\begin{eqnarray}
\mlA\cong\mlB & \Rightarrow & \mlA\equiv\mlB
\end{eqnarray}
\end{corollary}
\begin{corollary}
Let $h$ be an automorphism of the structure \mlA, and let $R$ be an $n$-ary
relation on $|\mlA|$ definable in \mlA. Then for any $a_1,\ldots,a_n$ in
$|\mlA|$,
\begin{eqnarray}
\in R & \liff & \in R
\end{eqnarray}
\end{corollary}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{subsection}{5}\subsection{Models of Theories}
In a general sense, there are two types of models : finite and infinite.
Some sentences may have only finite models while others have only infinite.
Some may have both. An example is the sentence stating that $<$ is an
ordering relation with no largest element. Clearly, this statement is only
true in infinite models. Its negation, however, is true in any finite
model (and is thus called {\em finitely valid}). For another good example,
consider the sentence $\forall x\forall y(x=y)$. This sentence is true in
only finite models with one element!
\begin{theorem}
If a set $\Sigma$ of sentences has arbitrarily large finite models, then it
has an infinite model.
\end{theorem}
The above theorem is important. It states that it is impossible for any set
of sentences to be true in every finite model and false in every infinite one.
\begin{corollary}
The class of all finite structures is not $EC_\delta$ (for any set of
sentences). The class of all infinite structures is not $EC$ (for any
single sentence).
\end{corollary}
Previously, we defined $Mod\;\Sigma$ to be the class of all models that
satisfied a set of sentences. Now, we want to do a similar opertion only on
models. Let {\em the theory of \mlA}, written $Th\;\mlA$, be defined as the
set of all sentences true in \mlA.
\begin{theorem}
For a finite structure \mlA, $Th\;\mlA$ is decidable.
\end{theorem}
\begin{theorem}
For a finite language, ${\sigma|\sigma\text{sigma has a finite model}}$ is
effectively enumerable.
\end{theorem}
\begin{corollary}
For a finite language, let $\Phi$ be the set of sentences true in every
finite structure. Then its complement, $\overline{\Phi}$, is effectively
enumerable.
\end{corollary}
\begin{theorem}[Trakhtenbrot's Theorem]
The set of sentences
\begin{equation}
\Phi=\left\{\sigma|\sigma\text{is true in every finite structure}\right\}
\end{equation}
is not in general decidable or effectively enumerable.
\end{theorem}
Next, Enderton discusses the size of models. It can be shown that a
consistent set of sentences in a countable language has a countable model.
This leads us to the L\"{o}wenheim-Skolem theorem:
\begin{theorem}[L\"{o}wenheim-Skolem Theorem - Countable Models Only]
\begin{enumerate}
\item Let $\Gamma$ be a satisfiable set of formulas in a countable
language. Then $\Gamma$ is satisfiable in some countable structure.
\item Let $\Sigma$ be a set of sentences in a countable language. If
$\Sigma$ has any model, then it has a countable model.
\end{enumerate}
\end{theorem}
This theorem can be applied to prove the following. Choose any consistent
set of axioms for set theory. By this theorem, the axioms have some countable
model, $\mathfrak{G}$. We know from previous theorems that since
$\mathfrak{G}$ is a model of the chosen axioms, it must also be a model of all
sentences logically implied by those axioms. Here, an interesting paradox
(known as Skolem's paradox) arises. Of all the sentences logically implied
by these axioms, one states that there are uncountably many sets. Enderton
assures us that there is no contradiction here, since it is true that in
$\mathfrak{G}$ there can be a point (set) that cannot be put in a one-to-one
mapping with the natural numbers, as long as the {\em number} of points (sets)
is countable.
The L\"{o}wenheim-Skolem theorem can also be applied to show that for any
structure \mlA for a countable language, there is a countable structure \mlB
that is elementarily equivalent to \mlA ($\mlA\equiv\mlB$).
Concerning uncountable languages, the L\"{o}wenheim-Skolem theorem can be
stated as follows:
\begin{theorem}[L\"{o}wenheim-Skolem Theorem]
\begin{enumerate}
\item Let $\Gamma$ be a satisfiable set of formulas in a language of
cardinality $\lambda$. Then $\Gamma$ is satisfiable in some
structure of size $\le\lambda$.
\item Let $\Sigma$ be a set of sentences in a language of cardinality
$\lambda$. If $\Sigma$ has any model, then it has a model of
cardinality $\le\lambda$.
\end{enumerate}
\end{theorem}
The earlier version of this theorem can be stated as a special case, where
$\lambda=\aleph_0$.
\begin{theorem}[LST Theorem]
Let $\Gamma$ be a set of formulas in a language of cardinality $\lambda$,
and assume that $\Gamma$ is satisfiable in some infinite structure. Then
for every cardinal $\kappa\le\lambda$, there is a structure of cardinality
$\kappa$ in which $\Gamma$ is satisfiable.
\end{theorem}
\begin{corollary}
\begin{enumerate}
\item Let $\Sigma$ be a set of sentences in a countable language. If
$\Sigma$ has some infinite model, then $\Sigma$ has models of every
infinite cardinality.
\item Let \mlA be an infinite structure for a countable language. Then
for any infinite cardinal $\lambda$, there is a structure \mlB of
cardinality $\lambda$ such that $\mlB\equiv\mlA$.
\end{enumerate}
\end{corollary}
The above corollary can be used to show the following. Call a set $\Sigma$ of
sentences {\em categorical} iff any two models of $\Sigma$ are isomorphic.
The above corollary implies that if $\Sigma$ has any infinite models, then
$\Sigma$ is not categorical. For example, there is no set of sentences
whose models are exactly the structures isomorphic to
$(\setN;\;0,\;S,\;+,\;\cdot)$. Thus, first-order languages are limited in
their expressive powers.
Next, Enderton provides a new definition for a {\em theory}. Where we
previously defined a theory to be the set of all sentences implied by a
smaller set of sentences (thus, it was defined in relation to a set of
sentences), we now define a theory to be a set of sentences closed under
logical implication. (It should be easy to see the similarity between the
two definitions). With this new definition, $T$ is a theory iff $T$ is a set
of sentences such that for any sentence $\sigma$ of the language,
\begin{equation}
T\implies\sigma\lthen\sigma\in T
\end{equation}
\begin{definition}[Axiomatizable]
A theory $T$ is {\em axiomatizable} iff there is a decidable set of
$\Sigma$ of sentences such that $T=Cn\Sigma$.
\end{definition}
\begin{definition}[Finitely Axiomatizable]
A theory $T$ is {\em finitely axiomatizable} iff $T=Cn\Sigma$ for some
finite set $\Sigma$ of sentences.
\end{definition}
\begin{theorem}
If $Cn\Sigma$ is finitely axiomatizable, then there is a finite
$\Sigma_0\subseteq\Sigma$ such that $Cn\Sigma_0=Cn\Sigma$.
\end{theorem}
\begin{corollary}
\begin{enumerate}
\item An axiomatizable theory (in a reasonable language) is effectively
enumerable.
\item A complete axiomatizable theory (in a reasonable language) is
decidable.
\end{enumerate}
\end{corollary}
We say that a theory $T$ is $\aleph_0$-categorical iff all the infinite
countable models of $T$ are isomorphic. More generally, for a cardinal
$\kappa$, say that $T$ is $\kappa$-categorical iff all models of $T$ having
cardinality $\kappa$ are isomorphic.
\begin{theorem}[Lo\'{s}-Vaught Test]
Let $T$ be a theory in a countable language. Assume that $T$ has no
finite models.
\begin{enumerate}
\item If $T$ is $\aleph_0$-categorical, then $T$ is complete.
\item If $T$ is $\kappa$-categorical for some infinite cardinal
$\kappa$, then $T$ s complete.
\end{enumerate}
\end{theorem}
\begin{theorem}
\begin{enumerate}
\item The theory of algebraically closed fields of characteristic 0 is
complete.
\item The theory of the complex field $\mlC=(\setC;\;0,\;1,\;+,\;\cdot)$
is decidable.
\end{enumerate}
\end{theorem}
\begin{theorem}
Any countable model of $\delta$ is isomorphic to $(\setQ,<_Q)$.
\end{theorem}
\begin{definition}[Prenex Normal Form]
A formula is said to be in {\em prenex normal form} iff for some $n\ge 0$
\begin{equation}
Q_1 x_1 \ldots Q_n x_n \alpha
\end{equation}
where $Q_i$ is $\forall$ or $\exists$ and $\alpha$ is quantifier-free.
\end{definition}
\begin{theorem}[Prenex Normal Form Theorem]
For any formula, we can find a logically equivalent formula in prenex
normal form.
\end{theorem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{section}{3}\section{Second-Order Logic}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Second-Order Languages}
{\em coming soon!}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Skolem Functions}
{\em coming soon!}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Many-Sorted Logic}
{\em coming soon!}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{General Structures}
{\em coming soon!}
\end{document}