\documentclass[12pt]{article}
\usepackage{amsmath, amsthm, amssymb, amsfonts}
\usepackage{enumerate}
\numberwithin{equation}{section}

\DeclareMathAlphabet{\mathscr}{OT1}{pzc}{m}{it}

%%%Document Configuration
\pagestyle{headings}
%\addtolength{\topmargin}{-.5in}
\textwidth = 6in 
\oddsidemargin = .25in
\evensidemargin = .25in
\voffset = -1in
\textheight = 9.5 in
%\textwidth = 6in
%\parindent = 0in
%\headsep = 0in
\relpenalty = 9999
\binoppenalty = 9999
%linespacing
\renewcommand{\baselinestretch}{1.25}
\reversemarginpar     
%%%

%%%Theorem Configuration
\theoremstyle{plain}
\newtheorem*{main}{Main~Theorem}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{exer}[thm]{Exercise}
\newtheorem{fact}[thm]{Fact}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{remark}[thm]{Remark}
%\newtheorem{hw}[section]{}
%\newtheorem{hw}[section]{HW}
\newtheorem{dfn}{Definition}[section]
%%%

%%%Bibliography Configuration
\bibliographystyle{plain}
%%%

%%%semantic definitions
\DeclareMathOperator*{\Aut}{Aut}
\DeclareMathOperator*{\Th}{Th}
\DeclareMathOperator*{\Mod}{Mod}
\renewcommand{\div}{\mid}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\implies}{\Rightarrow}
\renewcommand{\natural}{\mathbb{N}}
\newcommand{\Acl}[1]{\obar{#1}}
\newcommand{\assign}{\leftarrow}
\newcommand{\caseif}{\Rightarrow}
\newcommand{\caseonlyif}{\Leftarrow}
\newcommand{\cantprove}{\nvdash}
\newcommand{\complex}{\mathbb{C}}
\newcommand{\field}{\mathbb{F}}
\newcommand{\minus}{\setminus}
\newcommand{\power}[1]{{\cal{P}}({#1})}
\newcommand{\nonnegative}{\mathbb{N}}
\newcommand{\integer}{\mathbb{Z}}
\newcommand{\intersect}{\cap}
\newcommand{\isomorphic}{\simeq}
\newcommand{\obar}[1]{\overline{#1}}
\newcommand{\proves}{\vdash}
\newcommand{\rational}{\mathbb{Q}}
\newcommand{\real}{\mathbb{R}}
\newcommand{\union}{\cup}
\newcommand{\units}[1]{{\left(#1\right)}^{\times}}
%%%

%%%local definitions
\newcommand{\eleq}{\equiv}
\newcommand{\elleq}{\preccurlyeq}
\newcommand{\lang}[1]{{\cal{#1}}}
\newcommand{\Los}{{\L o\'s}}
\newcommand{\LS}{{L\"{o}wenheim-Skolem }}
\newcommand{\st}[1]{{\cal{#1}}}
\newcommand{\structure}[1]{{\cal{#1}}}
\newcommand{\struct}[1]{\left\langle#1\right\rangle}
\newcommand{\symAnd}{\mathop{\bigwedge}}
\newcommand{\symand}{\wedge}
\newcommand{\symimply}{\rightarrow}
\newcommand{\symiff}{\leftrightarrow}
\newcommand{\symnot}{\neg}
\newcommand{\symor}{\vee}
\newcommand{\WFF}{well-formed formula}
\newcommand{\0}{\textbf{0}}
\newcommand{\suc}{\textbf{S}}
\newcommand{\A}{\mathfrak{A}}
\newcommand{\B}{\mathfrak{B}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\NNN}{\mathfrak{N}}
\newcommand{\E}{\textbf{E}}
\newcommand{\Cn}{\textrm{Cn}}
\newcommand{\res}{\upharpoonright}
%%%

\begin{document}

\title{Mathematical Logic Review}\date{April 27, 2007}
\maketitle


\small{
This document is intended to serve as a review for the
logic qualifying exam at the CUNY graduate center.
Some of the results are written from memory and others
are copied directly from various textbooks including
Rothmaler's \emph{Model Theory},
Enderton's \emph{A Mathematical Introduction to Logic},
and Kunen's \emph{Set Theory: An Introduction to Independence Proofs}.}

\normalsize


%%%%%%%%%
\section{Model Theory}
%%%%%%
\subsection{Basic Definitions and Results}

\begin{dfn}[Theory]
For the purposes of this document,
a \textbf{theory} is a deductively closed set of sentences.
\end{dfn}

\begin{dfn}
A homomorphism $f : \st{M} \to \st{N}$ is called \textbf{strong}
if for all relations symbols $R$ in the language,
and for all $b_i \in |\st{N}|, R^\st{N}(b_0,\ldots,b_n)$ implies
there exists $a_i\in |\st{M}|$
such that $f(a_i)=b_i$ for each $i$ and $R^\st{M}(a_0,\ldots,a_n)$.
\end{dfn}
%
The notation $(\st{M},f[A])$
indicates an $L(\underline{A})$-structure
and means $f:A\rightarrow M$ and the constant symbol $\underline{a}$
is interpreted as $f(a)$.
This becomes simpler when $A\subseteq M$:
in this case, we have $(\st{M},A)$ and
the constant $\underline{a}$ is interpreted as $a$.

\begin{dfn}[Satisfaction with parameters]
\[
\st{M}\models\varphi(a) \iff
\st{M}^*\models\varphi_x(\underline a) \iff
\st{M}^*\models \varphi_x^{\underline a}\]
\end{dfn}

\begin{dfn}
The set defined by $\psi(\bar{x},y)$ in $\st{M}$ with parameter $b\in M$ is \[\psi(\st{M},b):=\{\bar{a}\in M^n : \st{M}\models\psi(\bar{a},b)\}\]
\end{dfn}

\begin{prop}\emph{(New constants)} Let $\Sigma$ be a set of $L$-sentences,
$\varphi \in L_n$ and
let $\obar{c}$ be an $n$-tuple of new constants not occuing in $L$. Then
\[
\Sigma\models_{L(\obar{c})}\varphi(\obar{c})
\iff
\Sigma\models_L \forall \obar{x} \varphi(\obar{x}).
\]
\end{prop}

\begin{prop}
A set of sentences is consistent if and only if it has a model.
\end{prop}

\begin{proof}
($\caseif$) If $\Sigma$ is inconsistent then it has no model.

\noindent($\caseonlyif$) If $\Sigma$ has no model then
$\Sigma^{\models}$ is the set of all sentences,
so some contradiction is a consequence of $\Sigma$.
That is, $\Sigma$ is inconsistent.
\end{proof}

\begin{prop}
The following are equivalent for every $L$-theory $T$.
\begin{enumerate}[(i)]
\item $T$ is a complete theory
\item $T$ is a maximal theory
\item $T$ is a maximal consistent set of $L$-sentences
\item $T=\Th(\st{M})$ for all $\st{M}\models T$
\item $T=\Th(\st{M})$ for some $\st{M}\models T$
\end{enumerate}
\end{prop}

\begin{cor}
Every consistent set $\Sigma$ of sentences is contained in a complete $L$-theory,
the completion of $\Sigma$.
\end{cor}

\begin{proof} Every consistent set $\Sigma$ of sentences has a model, call it $\st{M}$. Then $\Sigma\subseteq\Th(\st{M})$.\end{proof}

\begin{exer}
\end{exer}
Find a structure with a bijective endomorphism that is not an automorphism.
We need to find a structure with a bijective endomorphism
that is not \emph{strong}.
Let $\st{M}$ be the reals $\real$ with unary relation $E$ such that
$E(x) \iff x$ is even.
Then $f:\real \to \real$ with $f(x)=2x$ is a bijective endomorphism since
if $x$ is even, then $f(x)=2x$ is even.
However, $f$ is not an automorphism because $f(3)=6$ is even and $3$ is not.

\begin{exer}[Unique Readability]
\end{exer}
\begin{exer}[Coincidence Lemma]
\end{exer}

%%%%%%
\subsection{Filters and Ultraproducts}
\begin{dfn}
\label{filterdef}
A \textbf{filter} $F$ on a boolean algebra $\mathcal{B}$ is a subset of $B$
with the properties (\ref{F1}), (\ref{F2}) and (\ref{F3}).
An \textbf{ultrafilter} $U$ is a filter with property (\ref{UP}).
\begin{enumerate}[(i)]
\item $0\notin F$ \label{F1}
\item $a,b\in F$ implies $a\wedge b\in F$ \label{F2}
\item if $a\in F$ and $a\leq b$ then $b\in F$ \label{F3}
\item for every $a\in B$, either $a\in U$ or $\obar{a}\in U$. \label{UP}
\end{enumerate}
\end{dfn}

Note: It may be useful to think of sets in a filter as being ``big.''

\begin{prop}
Every set with the finite intersection property
can be extended to an ultrafilter.
\end{prop}

\begin{proof}
Let $F \subset \power{I}$ have the finite intersection property.
Let $F_0 = F$. If $\{F_i\}_{i < \kappa}$ is a chain with respect to inclusion
and every $F_i$ has the finite intersection property then
$\union F_i$ is an upper bound of this chain.
Therefore every chain extending $F$ has an upper bound,
hence by Zorn's lemma we may pick $U \in \power{I}$
a maximal extension $U$ of $F$
with respect to the finite intersection property.

All that remains is to show that such a set is an ultrafilter.
The finite intersection property implies that $\emptyset \not\in U$.
If $a \subset b \subset I$ and $b \in U$ then maximality implies that $a \in U$.
If $a, b \in U$ then $a \intersect b$ is nonempty.
Again since $U$ is maximal with respect to the finite intersection property
$a \intersect b \in U$.
Then $U$ is a filter.
Let $a \in U$ and $b \in I$.
If $a \intersect b$ is empty then $a \intersect (I\minus b)$ is nonempty
so $b \in U$ by maximality.
If $a \intersect b$ is nonempty then $b \in U$ by maximality.
Hence $a \intersect b$ is nonempty if and only if $b \in U$.
For all $b \in I$ either $b \in U$ or $I \minus b \in U$.
Therefore $U$ is an ultrafilter.
\end{proof}

\begin{dfn} Let $\st{M}_i$ be $L$-structures for $i\in I$, $\st{M}=\prod_i\st{M}_i$, $\obar{a}\in M^n$, and $F$ be a filter on $I$. We define

\emph{(1)} $\|\varphi(\obar{a})\|:=\{i\in I: \st{M}_i\models\varphi(\obar{a}(i))\}$

\emph{(2)} $\sim_F$ an equivalence relation on $\st{M}=\prod_i\st{M}_i$ where \[{a}\sim_F{b} \ \Longleftrightarrow \ \|a=b\|\in F\] and $a/F$ denotes the equivalence class of $a$.

\emph{(3)} $\st{M}/F=\prod_i\st{M}_i/F$ an $L$-structure called the \textbf{reduced product} of the \emph{(non empty)} $\st{M}_i$ w.r.t. $F$, with universe $M/F:=\{a/F:a\in\st{M}\}$ where

\hspace{.6in} -- $c^{\st{M}/F}=c^\st{M}/F=(c^{\st{M}_i}:i\in I)$

\hspace{.6in} -- $f^{\st{M}/F}(a/F)=f^\st{M}(a)/F=(f^{\st{M}_i}(a(i))/F$

\hspace{.6in} -- $R^{\st{M}/F}(a) \iff \|R(a)\|\in F$

\noindent If all the $\st{M}_i$ are the same $L$-structure, say $\st{N}$, then the reduced product is called the reduced power of $\st{N}$, written $\st{N}^I/F$.

Reduced products modulo ultrafilters are called \textbf{ultraproducts}.
\end{dfn}

\begin{thm} \emph{(\Los' Theorem)} Let $I$ be a set, $U$ an ultrafilter on $I$,
$\{\st{M}_i\}_{i \in I}$ structures.
Then for every $\obar{a} \in M$ and formula $\varphi$
\[
\prod_i \st{M}_i/U \models \varphi(\obar{a}/U) \iff \|\varphi(a)\| \in U
\]
\end{thm}

\begin{proof}[Proof Sketch]
The proof proceeds by induction on complexity of $\varphi$.
To prove the assertion for atomic formulas show by induction on terms that
\[
t^{\st{M}/U}(\obar{a}/U) = t^{\st{M}}(\obar{a})/U.
\]
For conjunction one direction follows by the finite intersection property
and the converse follows from the extension axiom (\ref{filterdef}.\ref{F3}).
For the existential step, note that
\begin{align*}
\st{M}/U \models \exists x \varphi(x,\obar{a}/U)
& \iff \st{M}/U \models \varphi(b, \obar{a}/U) \mbox{ for some } b \in M/U \\
& \iff \|\varphi(b,\obar{a}\| \in U\\
\st{M}/U \models \exists x \varphi(x,\obar{a}/U)
& \iff \|\exists x \varphi(x,\obar{a})\| \in U.
\end{align*}
One needs the ultrafilter axiom (\ref{filterdef}.\ref{UP}) only to prove the negation step.
\end{proof}

%%%%%%
\subsection{Compactness Theorem}

\begin{thm} \emph{(Compactness Theorem)}
A set of sentences $\Sigma$ has a model
if and only if
every finite subset has a model.
\end{thm}

\begin{proof}[Proof Sketch] Suppose $\Sigma$ is finitely satisfiable
and let $I = \{i\subseteq \Sigma: i\neq 0 \textrm{ is finite}\}$.
Then for each $i\in I$ there is a model $\st{M}_i\models i$.
The set
\[
F = \left\{
     \|\varphi_1\wedge\dots\wedge\varphi_n\| {\big|}
     n\in \omega \mbox{ and } \varphi_k\in\Sigma
    \right\} \subseteq \power{I}
\]
has the finite intersection property hence
can be extended to an ultrafilter $U$ on $I$ containing $F$.
Now choose $\varphi\in \Sigma$ then since $\|\varphi\|\in F\subseteq U$
we get by \Los' theorem that $\prod_i\st{M}_i/U\models\varphi$.
\end{proof}

\begin{cor} \emph{(Finiteness of Logical Implication)} If $\Sigma\models\varphi$ then there is a finite $\Sigma_0\subseteq\Sigma$ such that $\Sigma_0\models\varphi$.
\end{cor}

\begin{proof} If $\Sigma\models\varphi$ then $\Sigma\cup\{\lnot\varphi\}$ is inconsistent and by the compactness theorem some finite subset $\Gamma\subseteq\Sigma\cup\{\lnot\varphi\}$ is inconsistent. If $\lnot\varphi\notin\Gamma$ then $\Gamma\subseteq\Sigma$ and $\Gamma\models\varphi$ since $\Gamma$ has no models. If $\lnot\varphi\in\Gamma$, then $\Gamma=\Sigma_0\cup\{\lnot\varphi\}$ for some finite $\Sigma_0\subseteq\Sigma$ and by the inconsistency of $\Sigma_0\cup\{\lnot\varphi\}$ we have $\Sigma_0\models\varphi$ (for if $\st{M}\models\Sigma_0$ then $\st{M}\not\models\lnot\varphi$ because otherwise $\Sigma_0\cup\{\lnot\varphi\}$ is consistent).\end{proof}



\begin{thm} \emph{(\LS Theorem Upward)} If $\Sigma$ has an infinite model
or models of arbitrarily large finite cardinality
then $\Sigma$ has models for all cardinalities $\alpha >|L|$.
\end{thm}

\begin{proof} Let $C$ be a collection of constants not in the language $L$ of $\Sigma$ such that $|C|=\kappa>|L|$. Then the set \[\Gamma:=\Sigma\cup\{c\neq c':c,c'\in C\}\] is finitely satisfiable: Let $\Sigma_0\subseteq\Gamma$ be finite and let $C'$ denote the constants from $C$ appearing in sentences of $\Sigma_0$. We can define an $L(C')$-structure from the given $L$-structure(s) by interpreting the constants $c\in C'$ as distinct elements of the universe. If the given structure is infinite, of course we will have plenty of distinct elements to work with. If we are given arbitrarily large finite structures, we can choose one that is large enough to interpret the finitely many constants $C'$ as distinct elements. Either way, we see that $\Sigma_0$ is satisfiable. Hence by the compactness theorem, $\Gamma$ is satisfiable. So there is a $L(C)$-structure $\st{M}\models\Gamma$ with cardinality $\geq |C|=\kappa$. The $L$-reduct of $\st{M}$ is then an $L$-structure satisfying $\Sigma$.\end{proof}

\bigskip

\noindent *** Results on groups, rings, boolean algebras, vectorspaces, prime divisors, etc.




%%%%%%
\subsection{Some Topology}

\begin{thm} \emph{(Stone Representation Theorem)}
\end{thm}


%%%%%%
\subsection{The Diagram}

\begin{dfn} \emph{(Diagram)} Let $\st{M}$ be an $L$-structure. The \textbf{diagram} of $\st{M}$, written $D(\st{M})$, is the set of all $L(M)$-sentences that are true in $\st{M}$: 
\begin{align*}
D(\st{M})&:=\{\varphi(\obar{a}):\st{M}\models\varphi(\obar{a}), \textrm{ $\varphi\in L$ is atomic and $\obar{a}$ is from $M$}\} \\
 & \ \ \ \ \ \ \ \cup \{\lnot\varphi(\obar{a}):\st{M}\models\lnot\varphi(\obar{a}), \textrm{ $\varphi\in L$ is atomic and $\obar{a}$ is from $M$}\}
\end{align*}
\end{dfn}

\begin{dfn} $f:\st{M}\stackrel{\Delta}{\rightarrow}\st{N}$ means that $f:M\rightarrow N$ and $\st{M}\models\varphi(\obar{a})$ implies $\st{N}\models\varphi(f(\obar{a}))$ for all $\varphi\in\Delta\cap L$ and all matching tuples $\obar{a}$ from $M$.

\end{dfn}


\begin{lem} \emph{(The Diagram Lemma)} Suppose $\st{M}$ and $\st{N}$ are $L$-structures and $f:M\rightarrow N$. Then
\begin{itemize}
\item[\emph{(1)}] $\st{M}\subseteq\st{N}$ if an only if $M\subseteq N$, $M$ is closed under functions, and $(\st{N},M)\models D(\st{M})$; if an only if $\emph{id}_\st{M}:\st{M}\stackrel{\textbf{\emph{qf}}}{\hookrightarrow}\st{N}$.
\item[\emph{(2)}] $f:\st{M}\hookrightarrow \st{N} \iff f:\st{M}\stackrel{\textbf{\emph{qf}}}{\rightarrow}\st{N} \iff (\st{N},f[M])\models D(\st{M})$.
\item[\emph{(3)}] $\st{M}\hookrightarrow\st{N} \iff \st{N}$ has an $L(M)$-expansion which is a model of $D(\st{M})$.
\end{itemize}
\end{lem}

\begin{proof} (2) Suppose $f:\st{M}\hookrightarrow\st{N}$ and let $\st{M}\models\varphi(\obar{a})$ where $\varphi(\obar{a})$ is a \emph{sentence} in $L(M)$ (or equivalently $\varphi\in L_n$ and $\obar{a}\in M^n$. We show $\st{N}\models\varphi(\obar{a})$ by induction on $\varphi$. First suppose $\varphi(\obar{a})$ is an atomic formula, then $\st{N}\models\varphi(f(\obar{a}))$ follows because $f$ is a homomorphism (here $\varphi(\obar{a})$ is either a variable-free term equation or a relational $L(M)$-sentence. Then $f:\st{M}\stackrel{\textbf{qf}}{\rightarrow}\st{N}$ follows at once by induction.\end{proof}

Now suppose $f:\st{M}\stackrel{\textbf{qf}}{\rightarrow}\st{N}$. Suppose $\varphi(a)\in D(\st{M})$, then $\varphi(a)$ is an $L(\st{M})$ (variable free) literal and $\st{M}\models\varphi(a)$. Then just by definition of $f:\st{M}\stackrel{\textbf{qf}}{\rightarrow}\st{N}$.

Suppose $(\st{N},f[M])\models D(\st{M})$. We know $f:M\rightarrow N$ so we just need to show that $f$ is a strong injective homomorphism. Suppose $(\st{N},f[M])\models R(a_1,\ldots,a_n)$ for $a_a,\ldots,a_n\in M$. Since $(\st{N},f[M])$ thinks the diagram of $\st{M}$ is true, the diagram of $\st{M}$ can't contain $\lnot R(a_1,\ldots,a_n)$, because otherwise we have a contradiction. Hence $\st{M}\models R(a_1,\ldots,a_n)$ --- that is, $f$ is strong. To show injectivity, suppose $\st{M}\models m_1\neq m_2$ then since $(\st{N},f[M])\models D(\st{M})$ we have $f^\st{N}(m_1)\neq f^\st{N}(m_2)$ --- hence, $f$ is injective. Now we show $f$ is a homomorphism. Choose $c\in\textbf{C}$ such that $c^\st{M}=m\in M$. Then $\st{M}\models c=m$ so $c=m\in D(\st{M})$ and thus, $(\st{N},f[M])\models c=m$ or in other words, $c^\st{N} = f(m)=f(c^\st{M})$. The cases for showing that $f$ preserves functions and relations is similar.

\noindent (3) Now, (3) is immediate from (2), but there is also a simple more direct way of proving (3). ($\Leftarrow$) Suppose $\st{N}$ has an $L(M)$-expansion that is a model od $D(\st{M})$, call it $\st{N}'$. Define a function $h:M\rightarrow N$ by $h(m)=m^{\st{N}'}$ --- this is an injective homomorphism. ($\implies$) This direction requires something like (2).

\begin{prop} Isomorphic structures have the same theories. If $f:\st{M}\cong\st{N}$, then $f:\st{M}\stackrel{\equiv}{\hookrightarrow}\st{N}$, hence also $\st{M}\equiv\st{N}$ \emph{(}i.e., $\Th \ \st{M}=\Th \ \st{N}$\emph{)}.
\end{prop}

\begin{cor} Let $\st{M}$ be an $L$-structure and suppose there is an automorphism $f\in\emph{Aut}(\st{M})$ that sends $a$ to $b=f(a)$. Then $a$ and $b$ are indistiguishable by the language $L$ in the sense that
$\st{M}\models\varphi(a) \iff \st{M}\models\varphi(b)$ for all $\varphi\in L_1$.
\end{cor}

\begin{fact} The converse of the above corallary is not true. Let $\st{M}:=(\kappa,<)$ where $\kappa$ is some cardinal $\geq 2^\omega$. Since there are only countably many formulas in the language there must be distinct $\alpha,\beta\in\kappa$ such that $\alpha<\beta$ and
$\st{M}\models\varphi(\alpha) \iff \st{M}\models \varphi(\beta)$. However, there is no automorphism of $\st{M}$ sending $\alpha$ to $\beta$ because the only automorphism of $(\kappa,<)$ is the identity.
\end{fact}

\begin{cor} Sets definable without parameters are invariant under automorphisms. If $f\in\emph{Aut}(\st{M})$ then $f[\psi(\st{M})]=\psi(\st{M})$ for all $\psi\in L$.
\end{cor}



%%%%%%
\subsection{Preservation Theorems}

\begin{lem} Let $f:\st{M}\hookrightarrow\st{N}$. Then $\st{M}\Lleftarrow_\mathbf{\forall}\st{N}$ and even $(\st{M},M)\Lleftarrow_\mathbf{\forall}(\st{N},f[M])$.
\end{lem}

\begin{lem}The following are equivalent for any $L$-theories $T$ and $T'$.

\emph{(i)} Every model of $T'$ can be embedded in a model of $T$.

\emph{(ii)} $T_\forall\subseteq T'$.

\end{lem}

\begin{proof} (i) $\Longrightarrow$ (ii): It will suffice to show $T'\models T_\forall$ (in fact this is equivalent to (ii)). Suppose $\st{M}\models T'$, then by (i) $\st{M}\hookrightarrow\st{N}\models T$, and by the previous lemma $\st{M}\models T_\forall$.\end{proof}

\noindent (ii) $\Longrightarrow$ (i): Suppose $T_\forall\subseteq T'$ and $\st{M}\models T'$. We must show that there is $\st{N}\models T$ with $\st{M}\hookrightarrow\st{N}$. By the diagram lemma this is equivalent to the consistency of $T\cup D(\st{M})$. Suppose $T\cup D(\st{M})$ is inconsistent then there is a finite conjunction $\varphi(\bar{a})$ of $L(M)$-sentences such that $T\cup\{\varphi(\bar{a})\}$ is inconsistent. Thus, $T\models \lnot \varphi(\bar{a})$ and by the theorem on new constants $T\models\forall \bar{x}(\lnot\varphi(\bar{x}))$. Then since $T_\forall\subseteq T'$ and $\st{M}\models T'$ we have $\st{M}\models\forall \bar{x}(\lnot\varphi(\bar{x}))$, but this is impossible since $\varphi(\bar{a})\in D(\st{M})$.


%%%%%%
\subsection{Local Properties and Henkin's Criterion}

\begin{dfn} Let $\st{M}$ be an $L$-structure and $X\subseteq M$. The \textbf{substructure generated by} $X$ in $\st{M}$, written $\st{M}_X$, is the uniquely determined substructure with universe $\bigcap\{N:X\subseteq N \wedge \st{N}\subseteq\st{M}\}$.
\end{dfn}

\begin{dfn} Let $\mathscr{P}$ be a property of $L$-structures. We say that $\st{M}$ \textbf{has $\mathscr{P}$ locally} if every finitely generated substructure of $\st{M}$ has the property $\mathscr{P}$. A property is said to be \textbf{elementary (or axiomatizable)} if the class of all $L$-structures having this property is axiomatizable.
\end{dfn}

\noindent \textbf{Example:} Let $\st{N}:=(\natural,<)$ and define choose pairwise disjoint chains $\st{M}_n\subseteq\natural$ of length $n$. We define another $L$-structure $\st{M}$ on $M=\bigcup_{n\in\natural}M_n$ as follows: for $a,b\in M$ define $a<b$
if and only if
there is $n$ such that $a,b\in M_n$ and $\st{M}_n\models a<b$. Then $\st{N}$ is locally embeddable, but not embeddable in $\st{M}$. \emph{However}, $\st{N}$ is embeddable in $\Th\ \Mod \ \st{M}$ since the set of $L_<(\natural)$-sentences $\Th(\st{M})\cup\{i<j:i,j\in\natural\wedge i<j\}$ is consistent and each of its models has an infinite chain.

\begin{prop}[Henkin's Criterion] Let $\st{M}$ be an $L$-structure and $\textbf{K}$ an axiomatizable class of $L$-structures. Then $\st{M}$ is embeddable (in a memeber of) $\textbf{K}$ if and only if $\st{M}$ is locally embeddable in $\textbf{K}$.

\end{prop}



%%%%%%
\subsection{Malcev's Theorem}

Interpretation Lemma

Malcev's Theorem

%%%%%%
\subsection{Theory of Orderings}

Positive Diagram Lemma

\begin{prop} Every partial order on a set $A$ can be extended to a linear order on $A$.
\end{prop}

\begin{prop} Every finite partial order can be extended to a linear order.
\end{prop}

\begin{thm} \emph{(Cantor's Theorem)} All countable dense linear orderings without endpoints are isomorphic.
\end{thm}




%%%%%%
\subsection{Elementary Maps}

\begin{prop} The following are equivalent for any $L$-sructure $\st{M}$.

\emph{(i)} $\st{N}\equiv\st{M}$ implies $\st{N}\cong\st{M}$ for any $L$-structure $\st{N}$.

\emph{(ii)} $\st{M}$ is finite.
\end{prop}

\begin{prop} A theory is complete if and only if all of its models are elementarily equivalent.
\end{prop}

\begin{proof} ($\Leftarrow$) Suppose $T$ is not complete. Then $T\cup\{\sigma\}$ and $T\cup\{\lnot\sigma\}$ are consistent and thus have models, say $\st{N}$ and $\st{M}$ respectively. Clearly $\st{N}$ and $\st{M}$ are not elementarily equivalent.\end{proof}

($\implies$) Suppose $T$ is complete and $\st{M},\st{N}\models T$. Then since complete theories are maximal, we have $\Th(\st{M})=\Th(\st{N})=T$.

\begin{cor} A complete theory has a finite model if and only if it has up to isomorphism, only one model.
\end{cor}

\begin{proof} ($\implies$) Suppose $T$ is complete and $\st{M}\models T$ is a finite model with $|\st{M}|=n$. Then $\st{M}\models \exists^{=n} x (x=x)$. If $\st{N}\models T$ then $\st{M}\equiv\st{N}$ (by the previous result) and hence $\st{N}$ has $n$ elements. Since $\equiv$ is the same as $\cong$ for finite structures, we have $\st{N}\cong\st{M}$.\end{proof}

($\Leftarrow$) Suppose $T$ has up to $\cong$ only one model. If $T$ has an infinite model, then by the \LS (upward) theorem $T$ has models of every infinite cardinality $\geq|L|$, which is impossible. Hence $T$ has no infinite models $\implies$ $T$ has a finite model.

\begin{dfn} Elementarily embeddable
\end{dfn}

\begin{lem} \emph{(Elementary Diagram Lemma)}
\end{lem}

\begin{prop} Commutative diagram \emph{[Roth, p 114]}
\end{prop}

\begin{dfn} Elementary Substructures
\end{dfn}

\begin{lem} \emph{(Isomorphic Correction)}
\end{lem}

\begin{dfn}[The Tarski-Vaught condition]
For all $\st{N}$ all $\varphi$ and $\obar{a} \in \st{M}$
\begin{align*}
\label{TV}
\st{N} \models \exists x \varphi(x,\obar{a})
\implies \exists b \in M \mbox{ such that } \st{N} \models \varphi(b,a).
\tag{TV}
\end{align*}
\end{dfn}

\begin{prop} \emph{(Tarski-Vaught Test)}
Let $\st{M}, \st{N}$, be $\lang{L}$-structures
$\st{M} \elleq \st{N} \iff \st{M} \subset \st{N}$ and (\ref{TV}) holds.
\end{prop}

\begin{cor}[Automorphism Corollary to the Tarski-Vaught Test]
Let $\st{M}$ and $\st{N}$ be $\lang{L}$-structures with $\st{M} \subset \st{N}$.
If for all finite sets $A \subset M$ and all $c \in N$
there is an automorphism $f \in \Aut_A\st{N}$ fixing $A$
such that $f(c) \in M$
then $\st{M} \elleq \st{N}$.
\end{cor}

\begin{prop} The language $L_<$ cannont distinguish between $(\rational,<)$ and $(\real,<)$.
\end{prop}

\begin{prop} \emph{(\LS Downward for $\elleq$)}
Every subset $A \subset M$ of an infinite $\lang{L}$-structure $\st{M}$
is contained in an elementary substructure $\st{N}$
such that $\st{N} \eleq \st{M}$ and $|\st{N}| = |\lang{L}| + |A|$.
\end{prop}

\begin{proof}[Proof Sketch]
Let $A \subset M, |M| > |L|$, and $\kappa = |L| + |A|$.
Choose an ascending chain $\{A_i\}_{i < \omega}$ where $A_i \subset M$,
$|A_i| = \kappa$ and for all $i < \omega$
\[
\varphi \in \lang{L}_1(A_i) \mbox{ and } \st{M} \models \exists x \varphi
\implies
\exists a \in A_{i+1} \mbox{ such that } \st{M} \models \varphi(a).
\]
Given $A_i$, for every $\varphi \in \lang{L}(A_i)$
such that $\st{M} \models\exists x \varphi(x)$
pick a witness $b_\varphi \in M$ such that $\st{M} \models \varphi(b_\varphi)$.
Then let $A_i$ with these witnesses be $A_{i+1}$.
Note that this procedure keeps the cardinality constant for all $i < \omega$.
Then using the Tarski-Vaught test we can see that $N = \union_{i<\omega} A_i$
is the universe for a substructure
$\st{N} \eleq \st{M}$ where $|N| = |\lang{L}| + |A|$.
\end{proof}

\begin{thm}[\LS Theorem]~~~~~~~~~~~~~~~~~~
\begin{enumerate}[(1)]
\item Every $\lang{L}$-theory has a model of a cardinality $\leq |\lang{L}|$.
\item Every $\lang{L}$-theory with an infinite model has a model of every
cardinality $\geq |\lang{L}|$.
\end{enumerate}
\end{thm}

\begin{proof}
Let $\st{M}$ be a model of the $\lang{L}$-theory $T$.
Every finite model of $T$ has power even $< |\lang{L}|$.

Let $T$ have an infinite model.
Then for every $\kappa \geq |\lang{L}|$, the upward \LS yields
a model $\st{M}$ of $T$ such that $|M| \geq \kappa$.
Then by \LS downward for $\elleq$ gives us an elementary substructure
of cardinality $\kappa$.
Since this model is elementary equivalent to $\st{M}$,
it is also a model of $T$.
\end{proof}

\begin{prop} \emph{(\LS Upward for $\elleq$)}
Suppose $\st{M}$ is an infinite $\lang{L}$-structure
and $\kappa \geq |\lang{L}| + |M|$.
Then $\st{M}$ has an elementary extension of cardinality $\kappa$.
\end{prop}

\begin{cor} Given a set $\mathbf{K}$ of models of a complete theory $T$, there is a model of $T$ in which every model from $\mathbf{K}$ is elementarily embeddable.
\end{cor}

\begin{dfn} A theory is said to be \textbf{categorical} in a given cardinality $\lambda$ (or just $\lambda$-categorical) if it has, up to isomorphism, exactly one model of power $\lambda$.

A theory is \textbf{categorical} if it is categorical in some power $\geq |L|$.
\end{dfn}

\begin{thm}\emph{(Los-Vaught Test)} A categorical theory is complete if and only if it has no finite models.
\end{thm}

\begin{proof}
($\implies$) A categorical theory $T$ has a model of cardinality $>|L|\geq\omega$, and if it is complete we know that all of it's models are elementarily equivalent and thus not finite.
\noindent ($\Leftarrow$) Suppose $T$ has no finite models and is categorical, say in power $\kappa$. It will suffice to show that any two models of $T$ are elementarily equivalent. Suppose $\st{M},\st{N}\models T$. Then $\st{M}$ and $\st{N}$ are infinite and by the \LS theorem there are $\st{M}'\equiv\st{M}$ and $\st{N}'\equiv\st{N}$ with $|\st{M}'|=|\st{N}'|=\kappa$. We have $\st{M}\equiv\st{M}'\cong\st{N}'\equiv\st{N}$ and since isomorphic structures have the same theory, $\st{M}\equiv\st{N}$.
\end{proof}

%%%%%%
\subsection{Elimination}



\pagebreak 

%%%%%%%%%
\section{A Formal Proof System}
%%%%%%
\subsection{Basic Results}



\begin{prop} $\Gamma\vdash\varphi$
if and only if
$\Gamma\cup\Lambda$ tautologically implies $\varphi$.
\end{prop}

\begin{proof} ($\implies$) If $\varphi\in\Gamma\cup\Lambda$ then the result it obvious. The only other possibility is that $\varphi$ follows by modus ponens from $\psi$ and $\psi\rightarrow\varphi$ where (by induction) $\Gamma\cup\Lambda$ tautologically implies $\psi$ and $\psi\rightarrow\varphi$. Hence $\Gamma\cup\Lambda$ tautologically implies $\varphi$.\end{proof}

\noindent ($\Leftarrow$) Suppose $\Gamma\cup\Lambda$ tautologically implies $\varphi$. Then by \emph{sentential compactness}, there is a finite subset $\{\gamma_1,\ldots,\gamma_n,\lambda_1,\ldots,\lambda_m\}\subseteq\Gamma\cup\Lambda$ that tautologically implies $\varphi$. Then \[\gamma_1\rightarrow\ldots\rightarrow\gamma_n\rightarrow\lambda_1\rightarrow\ldots\rightarrow\lambda_m\rightarrow\varphi\] is a tautology, and by $n+m$ uses of modus ponens, we get $\Gamma\vdash\varphi$.


\begin{thm}[Generalization Theorem] If $\Gamma\vdash\varphi$ and $x$ does not occur free in any formula in $\Gamma$, then $\Gamma\vdash\forall x\varphi$.
\end{thm}

\begin{proof} \begin{itemize}
\item Suppose $\varphi\in\Lambda$, then $\forall x\varphi\in\Lambda$ and $\Gamma\vdash\forall x\varphi$.

\item Suppose $\varphi\in\Gamma$, then $x$ does not occur free in $\varphi$, so $\varphi\rightarrow\forall x \varphi$ is in axiom group 4 and $\Gamma\vdash\varphi\rightarrow\forall x \varphi$.

\item Suppose $\varphi$ follows from $\psi$ and $\psi\rightarrow\varphi$ where (by induction) $\Gamma\vdash\forall x\psi$ and $\Gamma\vdash\forall x (\psi\rightarrow\varphi)$. By axiom group 3 we have $\Gamma\vdash\forall x \psi \rightarrow\forall x \varphi$. Hence by modus ponens $\Gamma\vdash\forall x \varphi$.
\end{itemize}
\end{proof}

\begin{prop}[Rule T] If $\Gamma\vdash\alpha_1,\ldots,\Gamma\vdash\alpha_n$ and $\{\alpha_1,\ldots,\alpha_n\}$ tautologically implies $\beta$, then $\Gamma\vdash\beta$.
\end{prop}

\begin{proof} $\alpha_1\rightarrow\ldots\rightarrow\alpha_n\rightarrow\beta$ is a tautology and thus a logical axiom.\end{proof}

\begin{thm}[Deduction Theorem] $\Gamma;\psi\vdash\varphi$ if and only if $\Gamma\vdash\psi\rightarrow\varphi$.
\end{thm}

\begin{proof} ($\Leftarrow$) We have $\Gamma;\psi\vdash\psi\rightarrow\varphi$ and $\Gamma;\psi\vdash\psi$ so by modus ponens $\Gamma;\psi\vdash\varphi$.\end{proof}

\noindent ($\implies$) 
\begin{itemize}
\item If $\varphi$ is $\psi$ the the result is obvious.
\item If $\varphi$ is a logical axiom or a member of $\Gamma$, then $\Gamma\vdash\varphi$ and since $\varphi$ tautologically implies $\psi\rightarrow\varphi$ we have (by rule T) that $\Gamma\vdash\psi\rightarrow\varphi$.
\item Supose $\varphi$ follows by modus ponens from $\theta$ and $\theta\rightarrow\varphi$ where (by induction) $\Gamma\vdash\psi\rightarrow\theta$ and $\Gamma\vdash\psi\rightarrow(\theta\rightarrow\varphi)$. Since $\{\psi\rightarrow\theta,\psi\rightarrow(\theta\rightarrow\varphi)\}$ tautologically implies $\psi\rightarrow\varphi$, we have (by rule T) $\Gamma\vdash\psi\rightarrow\varphi$.
\end{itemize}

\begin{cor}[Contraposition] $\Gamma;\varphi\vdash\lnot\psi \iff \Gamma;\psi\vdash\lnot\varphi$.
\end{cor}



\begin{cor}[RAA] If $\Gamma;\varphi$ is inconsistent then $\Gamma\vdash\lnot\varphi$.
\end{cor}

\begin{proof} $\Gamma;\varphi$ inconsistent $\implies$ $\Gamma\vdash(\varphi\rightarrow\beta)\wedge(\varphi\rightarrow\lnot\beta)$ $\implies$ $\Gamma\vdash\lnot\varphi$ since $\{\varphi\rightarrow\beta,\varphi\rightarrow\lnot\beta\}$ tautologically implies $\lnot\varphi$.\end{proof}

\begin{thm}[Generalization on Constants] Suppose that $\Gamma\vdash\varphi$ and that $c$ is a constant that does not occur in $\Gamma$. Then there is a variable $y$ (which does not occur in $\varphi$) such that $\Gamma\vdash\forall y \varphi^c_y$. Furthermore, there is a deduction of $\forall y \varphi^c_y$ from $\Gamma$ in which $c$ does not occur.
\end{thm}

\begin{cor}[Generalization on Constants] Suppose $\Gamma\vdash\varphi^x_c$ where $c$ is a constant not occuring in $\Gamma$ or $\varphi$. Then $\Gamma\vdash\forall x \varphi$, and there is a deduction of $\forall x\varphi$ from $\Gamma$ in which $c$ does not occur.
\end{cor}

\begin{cor}[Rule EI] Suppose $c$ is a constant not occuring in $\Gamma$, $\varphi$, or $\psi$. Then \[\Gamma;\varphi^x_c\vdash\psi \ \Longrightarrow \ \Gamma;\exists x \varphi \vdash \psi.\] [EI stands for existential instantiation.]
\end{cor}

%%%%%%
\subsection{Soundness and Completeness Theorem}

\begin{thm}[Soundness Theorem]
If $\Gamma \proves \varphi$ then $\Gamma \models \varphi$.
\end{thm}

\begin{lem} Every logical axiom is valid.
\end{lem}

\begin{lem} $\bar{s}(u^x_t)=\obar{s(x|\bar{s}(t))}(u)$
\end{lem}

\begin{lem}[Substitution Lemma] If $t$ is a term substitutable for the variable $x$ in the wff $\varphi$ then \[\models_\A\varphi^x_t[s] \ \iff \ \models_\A\varphi[s(x|\bar{s}(t))].\]
\end{lem}

\begin{dfn} $\Gamma$ is \textbf{satisfiable} if there is some $\A$ and some $s$ such that $\A\models\Gamma[s]$.
\end{dfn}

\begin{cor} The following are equivalent.

\emph{(a)} If $\Gamma$ is satisfiable then $\Gamma$ is consistent.

\emph{(b)} If $\Gamma\vdash\varphi$ then $\Gamma\models\varphi$.
\end{cor}

\begin{proof} (a) $\implies$ (b): Suppose $\Gamma\not\models\varphi$, then $\Gamma;\lnot\varphi$ is satisfiable and hence consistent. Thus $\Gamma\not\vdash\varphi$.

\noindent (b) $\implies$ (b): Suppose $\Gamma$ is inconsistent, then $\Gamma\vdash\beta$ and $\Gamma\vdash\lnot\beta$. By (b) we have $\Gamma\models\beta\wedge\lnot\beta$ so that $\Gamma$ is unsatisfiable ($\st{M}\models\Gamma$ $\implies$ $\st{M}\models\beta\wedge\lnot\beta$ $\implies\Leftarrow$).
\end{proof}

\begin{dfn}[MM proof system]
For a fixed language $\lang{L}$
the components of the MM proof system are the following:
\begin{itemize}
\item Logical Axioms -- All logical validities, that is
any $\varphi$ such that $\st{M} \models \varphi$
for all $\lang{L}$-structures $\st{M}$.
\item Rules of Inference -- Modus ponens
\end{itemize}
\end{dfn}

\begin{dfn}[A more reasonable proof system]
For a fixed language $\lang{L}$
the components of this proof system are the following:
\begin{itemize}
\item Logical Axioms
 \begin{itemize}
 \item All \WFF s having the form of a propositional tautology,
  e.g. $\forall x \varphi(x) \symor \symnot \varphi(x)$.
 \item Equality axiom scheme
  \begin{itemize}
   \item $\forall x (x = x)$ (reflexivity)
   \item $\forall x y (x = y \symiff y = x)$ (symmetry)
   \item $\forall x y z (x = y \symand y = z \symiff x = z)$ (transitivity)
  \end{itemize}
 \item Quantifier axiom scheme
  \begin{itemize}
   \item
    $(\forall x \varphi(x) \symand \forall x (\varphi(x) \symimply \psi(x)))
    \symimply \forall x \psi(x)$
   \item $\forall x \varphi(x) \symiff \symnot \exists x \symnot \varphi(x)$
   \item $\varphi \symimply \forall x \varphi$
    when $x$ does not appear in $\varphi$
  \end{itemize}
 \item Evaluation axiom scheme
  \begin{itemize}
   \item $\forall x \exists y (f(x) = y)$
  \end{itemize}
 \end{itemize}
\item Rules of Inference -- Modus ponens
\end{itemize}
\end{dfn}

\begin{thm}[Completeness Theorem]~~~~~~~~~~~~~~~~~~
\begin{enumerate}[(a)]
\item If $\Gamma\models\varphi$ then $\Gamma\vdash\varphi$.
\item Any consistent set of formulas is satisfiable.
\end{enumerate}
\end{thm}

\begin{remark}[Proofs about proof systems]
Induction on proof systems proceeds much like
induction on complexity of formulas and terms, but in this case
the construction rules are the logical axioms and inference rules.
Therefore proofs may be reasonably divided into cases for logical axioms,
nonlogical axioms (those assumed for a given assertion) and the inference steps.
\end{remark}

\begin{proof}[Proof sketch for the MM proof system]
Soundness proceeds by induction on $\varphi$.
Then completeness follows from compactness.
If $T \models \varphi$ then $T \union \{\symnot \varphi\}$ is not satisfiable.
Therefore by compactness there is a finite $T_0 \subset T$
such that $T_0' = T_0 \union \{\symnot \varphi\}$ has no model.
Then $\symAnd_{\varphi \in T_0} \varphi \symimply \varphi$ is true in every model
hence it is an axiom of MM.
Then we can construct a proof of $\varphi$ in $n+1$ applications of modus ponens.
Hence $T \proves \varphi$.
\end{proof}

\begin{proof}[Proof sketch for the more reasonable proof system]
Prove the deduction lemma, that is
$T \union \{\varphi\} \proves \psi \iff T \proves (\varphi \symimply \psi)$,
by induction on proofs.
Note that $T \proves \varphi$
if and only if $T$ and $\symnot \varphi$ is inconsistent.
Further, proofs from $T$ involving new constants not appearing in $T$ are
correspond to universally quantified proofs upon replacement of the constant
with the universally bound variable.
Thus $T \proves \varphi(c) \implies T \proves \forall x \varphi(x)$.

From this observation it is clear that the Henken property
\begin{align*}
T \union \{ (\exists x \varphi(x)) \symimply \varphi(c)\}
\mbox{ is consistent for any } \varphi \tag{HP} \label{henken}
\end{align*}
can be used to extend any consistent theory $T$.
Since any consistent theory can be extended to a consistent complete theory,
in particular, we can extend $T$ to a Henkenized complete theory $T_H$.
Then we can construct a model of this theory \st{H}
by considering equivalence classes of constants
based on the equivalence relation defined by
\[
c \sim d \iff T_H \proves c = d.
\]
By induction on complexity of formulas we can show that this model
models only those sentences which correspond to proofs from $T_H$, that is,
\[
\st{H} \models \varphi([c]) \iff T_H \proves \varphi(c)
\]
where $[c]$ is the equivalence class of a Henken constant $c$.

Suppose $T \models \varphi$. Then $T \union \{\symnot \varphi\}$ has no model
hence it is inconsistent.
Therefore
\begin{align*}
T \union \{\symnot\varphi\} & \proves \varphi\\
T & \proves (\symnot \varphi \symimply \varphi).
\end{align*}
Finally $((\symnot \varphi \symimply \varphi) \symimply \varphi)$
is a tautology. Thus $T \proves \varphi$.
Consequently any consistent theory $T$ has a model $\st{M}$,
that is $T \proves \varphi \iff T \models \varphi$.
\end{proof}

%XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
\begin{cor} [Compactness Theorem] \emph{(a)} If $\Gamma\models\varphi$ then for some finite $\Gamma_0\subseteq\Gamma$ we have $\Gamma_0\models\varphi$. 

\emph{(b)} If every finite subset of $\Gamma$ is satisfiable then $\Gamma$ is satisfiable.
\end{cor}

\begin{proof} (a)\end{proof}
\begin{align*}
\Gamma\models\varphi &\Longrightarrow \Gamma\vdash\varphi \hspace{1in}\textrm{(completeness thm.)}\\
	&\Longrightarrow \Gamma_0\vdash\varphi \textrm{ for some $\Gamma_0\subseteq \Gamma$, deductions being finite}\\
	&\Longrightarrow \Gamma_0\models\varphi \hspace{1in}\textrm{(soundness thm.)}
\end{align*}

\noindent (b) If every finite subset of $\Gamma$ is satisfiable, then every finite subset is consistent. Hence $\Gamma$ is consistent (deductions being finite), and thus has a model.

\begin{thm}[Enumerability Theorem] For a reasonable language, the set of valid wffs can be effectively enumerated.
\end{thm}

\begin{proof} The set $\Lambda=\{\lambda_0,\lambda_1,\ldots,\}$ of logical axioms is decidable and we claim that the set of tautological consequences of $\Lambda$ is effectively enumerable. Given a wff $\tau$ check whether\end{proof}
\begin{align*}
\{\lambda_0\}&\models\tau \\
\{\lambda_0,\lambda_1\}&\models\tau\\
		&\vdots
\end{align*}
using truth tables. If $\Lambda\models\tau$ then by the finiteness of $\models$ (corollary to sentential compactness) we know that eventually we will have $\{\lambda_0,\ldots,\lambda_n\}\models\tau$. In this way we can effectively enumerate the tautological consequences of $\Lambda$ and the claim is established. Now, $\{\sigma:\sigma \textrm{ is a tautological consequence of $\Lambda$}\}$ $=\{\sigma:\ \emptyset\vdash\sigma\}=\{\sigma:\sigma \textrm{ is valid}\}$.


\begin{cor} Let $\Gamma$ be a deciadable set of formulas in a reasonable language. Then

\emph{(a)} The set of theorems $\Gamma$ is effectively enumerable.

\emph{(b)} The set $\Gamma^{\models}$ is effectively enumerable.
\end{cor}

\begin{proof} Enumerate all validities (by enumerability theorem); whenever you find one of the form \[\alpha_n\rightarrow\ldots\rightarrow\alpha_1\rightarrow\alpha_0\] check to see whether $\alpha_n,\ldots,\alpha_1$ are in $\Gamma$. If so then put $\alpha_0$ on the list of theorems of $\Gamma$. In this way any theorem of $\Gamma$ is eventually listed.\end{proof}

%%%%%%%%%
\section{Arithmetic}
%%%%%%
\subsection{Axiom Sets: $A_S$, $A_L$, $\NNN_A$, $A_E$}

\begin{dfn}
\begin{align*}
\NNN_S&=(\natural,0,S)\\
\NNN_L&=(\natural,0,S,<)\\
\NNN_A&=(\natural,0,S,<,+)\\
\NNN&=(\natural,0,S,<,+,\cdot,E)
\end{align*}
\end{dfn}

\begin{dfn} $A_S$ is defined to be the following set of axioms.
\begin{align*}
S1. \ & \forall x\suc x\neq\0 \\
S2. \ & \forall x\forall y (\suc x=\suc y \rightarrow x=y)\\
S3. \ & \forall y (y\neq\0\rightarrow\exists x (y=\suc x))\\
S4.1 \ & \forall x \suc x\neq x\\
\vdots \ & \\
S4.n \ & \forall x \suc^n x\neq x
\end{align*}
\end{dfn}

\begin{thm} $\Cn \ A_S$ is a complete theory.
\end{thm}

\begin{proof}
$\Cn \ A_S$ is categorical because if $\A$ and $\B$ are two models of the same uncountable cardinality then they have the same number of $\integer$-chains and are thus isomorphic. Since $\Cn \ A_S$ has no finite models, by the Los-Vaught test, $\Cn \ A_S$ is complete.
\end{proof}

\begin{cor} $\Cn \ A_S= \Th \ \NNN_S$
\end{cor}

\begin{proof} ($\subseteq$) This is clear since $\NNN_S\models A_S$.\end{proof}

($\supseteq$) Suppose $\sigma\in \Th \ \NNN_S$ and $\sigma\notin\Cn \ A_S$. Since $\Cn \ A_S$ is complete we have $\lnot\sigma\in\Cn \ A_S$, and since $\NNN_S\models A_S$ we have $\NNN_S\models\sigma$.

\begin{cor} $\Th \ \NNN_S$ is decidable
\end{cor}

\begin{proof} Any complete axiomatizable theory is decidable.\end{proof}

\begin{dfn} A theory $T$ \textbf{admits elimination of quantifiers}
if and only if
for every formula $\varphi$ there is a quantifier-free formula $\psi$ such that \[T\models(\varphi\leftrightarrow\psi)\]
\end{dfn}

\begin{thm} Assume that for every formula of the form \[\exists x (\alpha_0\wedge\dots\wedge\alpha_n)\] where each $\alpha_i$ is a literal, there is a quantifier free formula $\psi$ such that $T\models(\varphi\leftrightarrow\psi)$. Then $T$ admits elmination of quantifiers.
\end{thm}

\begin{proof} Use induction on \# of quantifiers.\end{proof}

\begin{thm} $\Th \ \NNN_S$ admits quantifier elimination.
\end{thm}


\begin{thm}\emph{(1)} $\Cn \ A_L$ is complete.

\emph{(2)} $\Cn \ A_L= \Th \ \NNN_L$.

\emph{(3)} $\Th \ \NNN_L$ is decidable.
\end{thm}

\begin{cor} A subset of $\natural$ is definable in $\NNN_L$
if and only if
it is either finite or has finite complement.
\end{cor}

\begin{cor} The addition relation $\{(n,m,p):n+m=p\}$ is not definable in $\NNN_L$.
\end{cor}

\begin{proof} If we could define addition we could then define the set of even numbers, but this set is neither finite nor has finite complement.\end{proof}

\begin{fact} $\Th \ \NNN_A$ does not have quantifier elimination.
\end{fact}

\begin{proof} The evens are definable by $\exists y (y+y=x)$ but are not definable by any quantifier free formula.\end{proof}

\begin{thm}[Presburger, 1929] The theory of $\NNN_A=(\natural;0,S,<,+)$ is decidable.
\end{thm}

\begin{thm} A set of natural numbers is definable in $(\natural;0,S,<,+)$
if and only if
it is eventualy periodic.
\end{thm}

\begin{cor} The multiplication relation $\{(n,m,p):n\cdot m=p\}$ is not definable in $(\natural;0,S,<,+)$.
\end{cor}



%%%%%%
\subsection{Quantifier Elimination and Decidability Results}
%%%%%%
\subsection{Incompleteness Theorems and Related Results}
%%%%%%%%%
\section{Set Theory}
%%%%%%
\subsection{Axioms of ZFC}
%%%%%%
\subsection{Basic Results}
%%%%%%
\subsection{Axiom of Choice}
%%%%%%
\subsection{Ordinals}
%%%%%%
\subsection{Cardinals}

%%%%%%%%%

\section{Computability}


\section{Exercises}

\# 1. Prove the Los-Vaught test.

\pagebreak

\tableofcontents


\end{document}
