% LaTex2e
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}
\usepackage{hyperref}

\pagestyle{myheadings}
\def\header{A.Miller\hfill Model Theory M776 \hfill \today\hfill }
\markboth\header\header

\newcount\probno
\probno=0
\def\prob#1{\advance\probno by 1 \par \bigskip
    \noindent{\bf Problem \the\probno .} (#1) \par}

\def\al{\alpha}
\def\continuum{{\mathfrak c}}
\def\elemsup{\succeq}
\def\elemsub{\preceq}
\def\ff{{\mathcal F}}
\def\ka{\kappa}
\def\dd{{\mathcal D}}
\def\kk{{\mathcal K}}
\def\ll{{\mathcal L}}
\def\om{{\omega}}
\def\poset{{\mathbb P}}
\def\proves{\vdash}
\def\rmiff{\mbox{ iff }}
\def\su{\subseteq}
\def\zz{{\mathbb Z}}
\def\isom{\simeq}
\def\pr{\prime}
\def\ult{{\mathcal U}}
\def\qq{{\mathbb Q}}

%%%%%%%%%%%%%
%
%  \def\la{\langle}
%  \def\ra{\rangle}
%  \def\reals{{\mathbb R}}
%  \def\rmand{\mbox{ and }}
%  \def\st{\;:\;} % such that
%  \newtheorem{theorem}{Theorem}
%  \newtheorem{lemma}{Lemma}
%  \newtheorem{cor}{Corollary}[theorem]
%%%%%%%%%%%%%

\newenvironment{theorem}{\par\bigskip\noindent{\bf Theorem}\em}{\par}
\newenvironment{cor}{\par\bigskip\noindent{\bf Corollary}\em}{\par}
\newenvironment{example}{\par\bigskip\noindent{\bf Example}\em}{\par}

\begin{document}

\begin{flushright}
Spring 2009
\end{flushright}

Homework problems are due in class one week from the day assigned
(which is in parentheses). 

\begin{theorem}
(Ehrenfeucht-Fr\"aisse 1960 \cite{ehrenfeucht}).
If $M$ and $N$ are $\ll$-structures
and $M\equiv_n N$, then $M$ and $N$ model the same $\ll$-sentences of
quantifier depth $\leq n$.
\end{theorem}

\prob{1-21 W} For structures $M$ and $N$ in the language
of pure equality, prove that $M\equiv_n N$ iff
$||M||=||N||$ or ($||M||\geq n$ and $ ||N||\geq n$).

\prob{1-21 W} Let $M$ be an equivalence relation with exactly
one equivalence class of size $n$ for each positive integer $n$
and no infinite classes.  Let $N$ be the same, except in addition
it has one infinite equivalence class.  Use Ehrenfeucht games
to prove that $M\equiv N$.

\begin{theorem}
(Ehrenfeucht-Fr\"aisse 1960).  If $\ll$ is a finite language which
contains only predicate symbols and constant symbols, then for
every $n\in\om$ there exist a finite set $F_n$ of
$\ll$-sentences each with quantifier depth $\leq n$ such
that for any two $\ll$-structures $M$ and $N$, if
($M\models \theta \rmiff N\models \theta $)
for every $\theta$ in $F_n$, then $M\equiv_n N$.
\end{theorem}

\prob{1-26 M} \noindent Let $L_n$ be a linear order of size $n$ and
$L_\infty=\om+\om^*$ where $\om^*$ is the order type of the
negative integers.

(a) Prove that for every $n<\om$ there is
an $N<\om$ such that $L_k\equiv_n L_\infty$ for all $k>N$.

(b) Use the part (a) to prove that the linear
orders $\om$ and $\om+\om^*+\om=\om+\zz$ are elementarily equivalent.

(c) Use part (b) to prove that $(\om, S)$ and
$(\om+\zz,S)$ are elementarily equivalent where $S$ is the
successor operation, $S(x)=x+1$.

\begin{theorem}
(Cantor 1880) If $M$ and $N$ are countable $\ll$-structures, then
$M\simeq N$ iff $M\equiv_\infty N$.
\end{theorem}

\prob{1-26 M} Let $T$ be a $\ll$-theory such that $T$ has no finite
models and $\ll$ is countable.  Prove that the following
are equivalent:
\begin{enumerate}
\item $T$ is $\om$-categorical
\item $M\equiv_\infty N$ for every pair of models $M$ and $N$ of $T$.
\end{enumerate}
Hint: You may use without proof a consequence of the Ryll-Nardzewski Theorem,
namely if $M$ is a model of $T$ and $a_1,\ldots,a_n$ a tuple from $|M|$,
then $$Th(M,a_1,\ldots,a_n)$$ is $\om$-categorical.  You may also
use the Downward-Lowenheim-Skolem-Tarski Theorem.

\begin{theorem}
(Carol Karp 1965). Given $\ll$-structures $M$ and $N$ the following
are equivalent:
\begin{enumerate}
\item $M$ and $N$ satisfy the same $\ll_{\infty,\om}$ sentences
\item $M\equiv_\infty N$
\end{enumerate}
\end{theorem}

\prob{1-28 W} Let $\kk$ be a class of $\ll$-structures.
\par\noindent Prove
that $\kk$ is EC iff both $\kk$ and $\overline{\kk}$
are ${\rm EC}_{\Delta}$.

\begin{theorem}
(\L os-Tarski 1955) A first-order theory $T$ is $\forall$-axiomatizable
iff the models of $T$ are closed under taking substructures.
\end{theorem}

\begin{cor} The class of models of a sentence $\theta$
is closed under taking substructures iff $\theta$ is
logically equivalent to a $\forall$-sentence.
\end{cor}

\begin{cor}
The class of models of a sentence $\theta$
is closed under taking superstructures iff $\theta$ is
logically equivalent to a $\exists$-sentence.
\end{cor}

\prob{2-02 M} Show that if a first-order theory $T$ is preserved
by taking superstructures, then it can be axiomatized by
existential sentences, i.e. $\exists$-sentences.

Hint: Suppose $M\models (\exists-sent)\cap T$.  Prove that
$Th_{\forall}(M)\cup T$ is consistent.

\begin{theorem}
(Elementary Chain Lemma Tarski-Vaught 1957) If
$$M_0\elemsub M_1\elemsub M_2\elemsub M_3 \elemsub \cdots$$
is a chain of elementary substructures and
$$N=\bigcup_{n<\om}M_n$$
then $M_k\elemsub N$ for all $k<\om$.
\end{theorem}

\begin{theorem}
(Chang-\L os-Suszko 1959) A first-order theory $T$ is axiomatizable
by $\forall\exists$-sentences iff the models of $T$ are closed
under chains of substructures.
\end{theorem}

\prob{2-04 W} (Directed Unions) Suppose $\dd$ is a
directed set of $\ll$-structures
and $M_\infty=\bigcup\dd$. Prove:
\par (a) Every $\forall\exists$-sentence
which is true in every $M\in\dd$, is true in $M_\infty$.
\par (b) If for every $M\su N$ in $\dd$ we have $M\elemsub N$, then
$M\elemsub M_\infty$ for every $M\in\dd$.

\prob{2-04 W} (Direct Limits).  Let $\poset=(\poset,\leq)$ be a poset
(partially ordered set),  $(M_p:p\in\poset)$ a family of
$\ll$-structures, and $j_{pq}:M_p\to M_q$ be maps for each $p\leq q$
in $\poset$.  State the appropriate conditions on $\poset$,
these structures, and these maps, so as to naturally generalize problem
above (a) and (b).

\prob{2-06 F} Show that $T=Th(\qq,\leq,S)$ where $S$ is the
successor function is finitely axiomatizable.  Warning: it is not
categorical in any power.

\begin{theorem}
(Lowenheim 1915) If $T$ is a theory in countable language and has
a model, then it has a countable model.
\end{theorem}

\begin{theorem}
(Lowenheim-Skolem) If $T$ is an $\ll$-theory which has an infinite
model, then $T$ has models of all cardinality $\ka\geq |\ll|+\om$.
\end{theorem}

\begin{theorem}
(Upward-Downward Lowenheim-Skolem-Tarski 1950s) See
\par \url{http://www.math.wisc.edu/~miller/old/m776-97/preq.pdf}
\end{theorem}

\begin{theorem}({\L}os-Vaught Test 1954)
If $T$ is an $\ll$-theory which has no finite models and
is $\ka$-categorical for some $\ka\geq |\ll|+\om$, then
$T$ is complete.
\end{theorem}

\begin{theorem}
(McKinsey 1943) A first-order theory $T$ is axiomatizable by
universal Horn sentences iff the class of models of $T$ is closed under
substructure and products.
\end{theorem}

\prob{2-09 M} Prove that the class of well-orderings is not
${\rm PC}_{\Delta}$ but its complement is.

\begin{theorem}
(Keisler Sandwich 1960) An $\ll$-theory $T$ is
$\exists\forall$-axiomatizable iff for any $\ll$-structures
$M_1\su M_2\su M_3$ with $M_1\elemsub M_3$, if $M_1\models T$,
then $M_2\models T$.
\end{theorem}

\prob{2-11 W} Let $M_1$ and $M_2$ be $\ll$-structures.  Prove
that $M_1\equiv M_2$ iff there are $\ll$-structures $N_1$ and $N_2$
such that $M_1\elemsub N_1$, $M_2\elemsub N_2$, and
$N_1\isom N_2$.

\begin{theorem}
(Lyndon 1959) A first-order theory $T$ is axiomatizable by
positive sentences iff the class of models of $T$ is closed under
homomorphic images.
\end{theorem}

{\it \noindent {\bf Key Lemma}.  Suppose $B\models Th_{POS}(A)$ then
\par (a) there exists $B^\pr\elemsup B$ and $f:A\to B^\pr$ such
that
$$(B,f(a))_{a\in |A|}\models Th_{POS}(A,a)_{a\in |A|}$$
\par (b) there exists $A^\pr\elemsup A$ and $g:B\to A^\pr$ such
that
$$(B,b)_{b\in |B|}\models Th_{POS}(A^\pr,g(b))_{b\in |B|}$$}



\prob{2-13 F} (a) Prove that
$$B\models Th_{POS}(A) \rmiff A\models Th_{\neg POS}(B)$$

(b) Find $A$ and $B$ such that
$B\models Th_{POS}(A)$ but $A\not\models Th_{POS}(B)$.

\prob{2-13 F} Prove Key Lemma part (b).



\begin{theorem}
(Craig's Interpolation Lemma 1957) Suppose $\theta_1$ is
an $\ll_1$-sentence, $\theta_2$ is
an $\ll_2$-sentence, and $\proves \theta_1\to \theta_2$.  Then
there exists $\rho$ an $\ll_1\cap \ll_2$-sentence such that
$\proves \theta_1\to \rho$ and $\proves \rho\to \theta_2$.
\end{theorem}

\prob{2-16 M} (Prove) Suppose $T_0$ is a complete $\ll_0$-theory,
$T_1$ is a complete $\ll_1$-theory, and $\ll=\ll_0\cap \ll_1$.
Then:

$T_0\cup T_1$ is consistent iff $(T_0\cap (\ll-sent))\cup
(T_1\cap (\ll-sent))$ is consistent.

\prob{2-16 M}(Millar) (Disprove) Suppose $T_i$ (for $i=1,2,3$) is
a complete consistent $\ll_i$-theory.  Then:

$T_1\cup T_2\cup T_3$ is consistent iff $T_i\cup T_j$ is consistent
for all $i$ and $j$.

\prob{2-18 W} Suppose that $M$ is an infinite $\ll$-structure,
$\leq$ is a binary relation symbol in $\ll$, and $\leq^M$ is a linear
order with no greatest element.  Prove there exists $N\elemsup M$ with
$||N||\leq \om_1+|\ll|+||M||$ and the cofinality of $\leq^N$ is
$\om_1$.

\begin{theorem}
(Beth Definability) With respect to theories, implicitely definable
implies explicitely definable.
\end{theorem}

\begin{theorem}
(Addison 1960 \cite{addison60}) Let $\ll$ be a language containing at least one
constant symbol.  Suppose $\theta_0$ is a universal $\ll$-sentence and
$\theta_1$ an existential $\ll$-sentence such that
$\proves\theta_0\to\theta_1$.  Then there exists a quantifier free $\ll$-sentence $\rho$
such that $\proves \theta_0\to\rho$ and $\proves \rho\to\theta_1$.
\end{theorem}

\prob{2-20 F} Suppose $\ll$ is language containing at least
one relation or operation symbol but no constant
symbols.  Show there exists $\theta_0$ a universal $\ll$-sentence
and $\theta_1$ an existential $\ll$-sentence
such that
\begin{enumerate}
\item $\theta_0\to\theta_1$ is a logical validity,
\item $\theta_1$ is not a logical validity, and
\item $\neg\theta_0$ is not a logical validity.
\end{enumerate}
Show that there is no such pair of sentences in the language of
pure equality.

\begin{theorem}
(Shoenfield 1960 in \cite{addison62}, \cite{shoenfield} p. 97)
Suppose $\theta_0$ is a $\forall\exists$-$\ll$-sentence and
$\theta_1$ is an $\exists\forall$-$\ll$-sentence such that
$\proves\theta_0\to\theta_1$.  Then there exists an $\ll$-sentence $\rho$
which is a boolean combination of existential and universal sentences
such that $\proves \theta_0\to\rho$ and $\proves \rho\to\theta_1$.
(Similar result holds for higher prenex classes.)
\end{theorem}

\prob{2-23 M} Let $R$ be a binary relation symbol.  Note that
$$\exists x \forall y \; R(x,y) \to  \forall y \exists x\; R(x,y)$$
Prove that there does not exist a
sentence $\rho$ which is a boolean combination of existential and
universal sentences and interpolates between them.

Hint: Consider $R$-structures in which every finite $R$-structure embedds.

\begin{theorem}
(Rabin 1959 \cite{rabin}, \cite{bell} p. 136.)
There is a complete theory $T$ in a language
of size continuum, which is categorical in power $\om$ and has no
model of size $\kappa$ with $\om<\kappa<|2^\om|$.
\end{theorem}

\prob{2-25 W} Give an example of a theory $T$ with arbitrarily large
finite models but no model of cardinality $\kappa$ with
$\om\leq \kappa <|2^\om|$.

\prob{2-25 W} Suppose that the continuum $|2^\om|$ is larger than
$\aleph_\om$.  Prove that for every $A\su \om$ there is a first order
theory $T_A$ such that for every $n<\om$

$\;\;T_A$ has a model of
cardinality $\om_n$ iff $n\in A$.

\bigskip
Open Question.  Can we find $T_A$ which is complete?

\bigskip

\begin{theorem}
(\L os 1955) For any $f_1,\ldots,f_n\in \prod_iA_i$ and formula
$\theta$ \par\noindent
$\prod_iA_i/\ult\models \theta([f_1],\ldots,[f_n])$
$\;\;$ iff $\;\;$
$\{i\in I: A_i\models \theta(f_1(i),\ldots,f_n(i))\}\in\ult$.
\end{theorem}

\prob{2-27 F} Prove \L os's Theorem for ultraproducts
$\prod_{n\in\om}A_n/\ult$ and the language $\ll(Q_{c^+})$ where
$Q_{c^+} x$ is the quantifier which means
``There are more than continuum many $x$ such that''.

\begin{theorem}
(Keisler unpublished see \cite{chang} p.472) If $T$ is a first-order
theory with a model of size $\kappa\geq \om$, then for every
$\lambda\geq \kappa^\om$ $\;\;T$ has a model of size $\lambda$.
\end{theorem}

\begin{theorem}
(Keisler 1959) (CH) If $A\equiv B$ are countable and $\ult$ is
a nonprincipal ultrafilter on $\om$, then
$A^\om/\ult\isom B^\om/\ult$.
\end{theorem}

\begin{theorem}
(Morley, Vaught 1962) If $A$ and $B$ are $\kappa$-saturated models
of size $\kappa$, then $A\isom B$.
\end{theorem}

\prob{3-04 W} Suppose $A$ is an $\ll$ structure and $\leq$ is
a binary relation symbol in $\ll$ such that
$A$ reducted to $\leq$ is a linear order of uncountable cofinality.
Prove:
\par (a) There exists a proper elementary extension $B\elemsup A$
such that $|A|$ is cofinal in $|B|$, i.e., no new elements come
at the end.
\par (b) There exists elementary extensions $B\elemsup A$ of
arbitrarily large cardinality such that $|A|$ is cofinal in $|B|$.



\begin{theorem}
(Hausdorf 1936 see \cite{kunen})
There are $2^\continuum$ many ultrafilters on $\om$.
\end{theorem}

\prob{3-06 F} Prove there exists $f_\al:\om\to\om$ for 
$\al<\continuum=|2^\om|$
such that for any $F\in [\continuum]^{<\om}$ and
$s:F\to\om$ there exists $n<\om$ such that $f_\al(n)=s(\al)$
for all $\al\in F$.

\prob{3-06 F} Prove that for any infinite cardinal $\ka$ there
are $2^{2^\ka}$ ultrafilters on $\ka$.

\begin{theorem}
(Morley-Vaught 1962) If $\ka\geq |\ll|+\om$ and $A$ an $\ll$-structure
of cardinality $2^\ka$, then there exists $B\elemsup A$ of
cardinality $2^\ka$ which is $\ka^+$-saturated.
\end{theorem}

\begin{theorem}
(Vaught) Let $T$ be  theory in a countable language. Then the following
are equivalent:
\begin{enumerate}
\item $T$ has a countable $\om$-saturated model
\item $T$ has a countable weakly-saturated model
\item $S_n(T)$ is countable for all $n$
\end{enumerate}
\end{theorem}

\begin{theorem}
(Vaught) A structure $A$ is $\om$-saturated iff it is
weakly saturated and $\om$-homogenous.
\end{theorem}

\begin{theorem}
(Vaught) If $\ll$ is countable and $A$ is a countable
$\ll$-structure, then there exists a countable $\om$-homogeneous
$B\elemsup A$.
\end{theorem}

\prob{3-11 W} Suppose $T$ is a consistent $\ll$-theory with only
infinite models.  Suppose $\leq$ is a binary relation symbol in $\ll$
such that $T\proves$``$\leq $ is a linear order''.
Prove that every $\om_1$-saturated model has cardinality at least
continuum.

\begin{theorem}
(Vaught's Two Cardinal) If a theory $T$ in a countable language 
with a distinguished predicate $U$ admits
$(\ka,\ka^+)$, then it admits $(\om,\om_1)$.
\end{theorem}

\begin{theorem}
(Henkin-Orey 1954) 
If $T$ is a consistent theory in a countable language and
$(\Sigma_n:n<\om)$ are nowhere dense partial types, then
$T$ has a model omitting all $\Sigma_n$.
\end{theorem}

\prob{3-13 F} Suppose that $T$ is an $\ll$-theory and 
$S_n(T)$ is countable.  Prove there exists a countable 
$\ll_0\su\ll$ such that every $\ll$-formula 
$\theta(x_1,\ldots,x_n)=\theta(\overline{x})$
there exists an $\ll_0$-formula $\theta_0(\overline{x})$ such that
$T\proves \forall \overline{x}\;\;
\left(\theta(\overline{x}) \;\leftrightarrow\; \theta_0(\overline{x})\right)
$.

\begin{theorem}
(Henkin-Orey 1954) If $T$ is an $\om$-complete consistent theory,
then $T$ has an $\om$-model.  If $T$ is complete and has an $\om$-model,
then $T$ is $\om$-complete.
\end{theorem}

\prob{3-23 M} Prove or Disprove.  Suppose $T$ is an $\ll$-theory where
$\ll$ is countable and $\Sigma_n$ for $n<\om$ are partial types.  Suppose
for every $N<\om$ that $T$ has a model omitting $(\Sigma_n:n<N)$.  Then
$T$ has a model omitting $(\Sigma_n:n<\om)$.

\begin{theorem}
(Keisler \cite{vaught-maa}) Suppose $A$ is a countable $\ll$-structure,
$\ll$ countable, and $\leq$ is a binary relation symbol in $\ll$ with the
properties:
\begin{enumerate}
\item $\leq^A$ is a linear order without a greatest element and
\item for any $\theta(x,y)$ with parameters from $A$ and
$a\in A$ if 
$$A\models \forall x<a \;\exists y\; \theta(x,y),$$ 
then there is a $b\in A$ such that 
$$A\models \forall x<a \;\exists y<b \;\theta(x,y).$$
\end{enumerate}
Then $A$ has a proper elementary end extension.
\end{theorem}

\prob{3-25 W}
Prove the converse to this theorem.  If $A$ has a proper 
elementary end extension, then (1) and (2) must hold.

\begin{theorem}
(Keisler) Two cardinal theorem for sentences of $\ll_{\om_1,\om}$.
\end{theorem}

\begin{theorem}
(MacDowell-Specker 1961) Every model of Peano Arithmetic,
has a proper elementary end extension.
(proof for countable models only)
\end{theorem}


\begin{theorem}
(Vaught) The set of logical validities for $\ll(Q)$ is computably
enumerable.
\end{theorem}

\begin{theorem}
(Fuhrken) $\ll(Q)$ is countably compact.
\end{theorem}



\prob{3-27 F}
(a) Prove that for $\ll$ countable that for any uncountable $A$
$\ll$-structure, there is $B$ of
cardinality $\om_1$ with $$B\elemsub_{\ll(Q)}A.$$ 
Here $Qx$ means ``there are uncountably many $x$ such that''.
\par (b) Prove that for any countable family $\ff$ of
$\ll_{\om_1,\om}$-formulas, each with only finitely many free
variables, for any $\ll$-structure $A$ there is a countable
$B$ with
$$B\elemsub_{\ff}A.$$

\begin{theorem}
(Ryll-Nardzewski 1959) Suppose $T$ is a countable,complete, consistent
$\ll$-theory without finite models. Then the following are equivalent:
\begin{enumerate}
\item $T$ is $\om$-categorical
\item $S_n(T)$ is finite for all $n<\om$
\item every $p\in S_n(T)$ is principal for all $n<\om$.
\end{enumerate}
\end{theorem}

\prob{3-30 M} Suppose $T_2$ is a countable, complete, consistent
$\ll_2$-theory without finite models, $\ll_1\su \ll_2$ and
$T_1=T_2\cap (\ll_1$-sentences).
\par (a) (Prove) $T_2$ $\om$-categorical implies $T_1$ $\om$-categorical.
\par (b) (Disprove) $T_1$ $\om$-categorical implies $T_2$ $\om$-categorical.
\par (c) (Prove) $T_1$ $\om$-categorical implies $T_2$ $\om$-categorical,
if $\ll_2=\ll_1\cup\{c\}$. 


\begin{theorem} Suppose $T$ is a countable, complete, consistent
$\ll$-theory without finite models.
Any two prime models of $T$ are isomorphic.
If $A$ is the prime model of $T$, then $A$ elementarily embedds in every
model of $T$.  Conversely, if $A$ embedds into model of $T$, then
$A$ is the prime model of $T$.
\end{theorem}

\begin{theorem} (Vaught 1961) Suppose $T$ is a countable,complete, consistent
$\ll$-theory without finite models.
Then $T$ has a prime model iff the principal types in $S_n(T)$ are
dense for for all $n<\om$.
\end{theorem}

\begin{theorem}
(Vaught Never Two) Suppose $T$ is a countable, complete, consistent
$\ll$-theory without finite models.  Then $I(\om, T)\neq 2$.
\end{theorem}

\begin{example}
(Ehrenfeucht) For each $n$ with $3\leq n<\om$ there is a
countable, complete theory $T$ with $I(\om, T) = n$.
\end{example}

\prob{4-01 W} Suppose $T$ is a countable, complete, consistent
$\ll$-theory without finite models.  Suppose that every countable
model of $T$ is $\om$-homogeneous.  Prove that
$I(\om, T) = 1$ or $I(\om, T) \geq \om$.

\begin{example}
(Kunen unpublished) There is a pseudo elementary class 
with exactly $\om_1$ countable
models up to isomorphism.  (Homogeneous linear orders).
\end{example}

\begin{theorem}
Ramsey's Theorem, finite version of Ramsey's Theorem.
\end{theorem}

\begin{theorem}
(Ehrenfeucht-Mostowski) Suppose $T$ is a first-order theory with
an infinite model and $(I,\leq)$ is a linear-order.  Then
$T$ has a model $A$ with $I\su |A|$ order-indiscernibles.
\end{theorem}

\prob{4-06 M} Let $\ll=\{R\}$ where $R$ is a binary relation symbol.
Prove there are finitely many infinite $\ll$-structures $M_i$ for $i<N$ such
that for every universal $\ll$ theory $T$  with an infinite model
some $M_i\models T$.  Extra credit: prove the same for $R$ 3-ary and
find the smallest $N$.

\begin{theorem}
(Ehrenfeucht-Mostowski) Suppose $T$ is a countable first-order theory with
an infinite model.  Then for any $\ka\geq\om$ $T$ has a model
of size $\ka$ which realizes only countably many types and
has $2^\ka$ automorphisms.
\end{theorem}

\prob{4-13 M} Suppose $T$ is a countable first-order theory with
an infinite model.  Prove that for every $\ka>\om$ that
$T$ has a model $A$ of size $\ka$ such that for every
countable $X\su |A|$, the structure $(A,c)_{c\in X}$ realizes
only countably many types.

\begin{theorem}
(Erdos-Rado) $\beth_n^+(\ka)\to (\ka^+)^{n+1}_\ka$.
\end{theorem}

\begin{example}
(Sierpinski) $2^\om\not\to (3)^2_\om$ $\;\;\;\; 2^\om\not\to (\om_1)^2_2$.
\end{example}

\prob{4-15 W} Suppose $T$ is a countable first-order theory with
an infinite model.  Prove that there exists countable models of $T$,
$A(X)$ for $X\su\om$, such that for any $X,Y\su \om$
$$X\su Y \rmiff A(X)\elemsub A(Y).$$

\def\ga{\gamma}

\begin{theorem}
(Vaught's two cardinals far apart) Suppose $T$ is a countable theory
with distinguished predicate $U$.  Suppose for every $n$
there is a $\ka\geq\om$ such that
$T$ has a model of type $(\beth_n(\ka),\ka)$.  Then for
every $\ga\geq \ka\geq \om$, 
$T$ has a model of type $(\ga,\ka)$.
\end{theorem}

\begin{theorem}
(Morley) The Hanf Number of $\ll_{\om_1,\om}$ is
$\beth_{\om_1}$.
\end{theorem}

\begin{theorem}
(Silver, Erdos, Rowbottom) Let $\ka_0$ be the least
$\ka$ such that $$\ka\to(\om)^{<\om}_2$$ 
Assume $\ka_0$ exists, then
\begin{enumerate}
\item $\ka_0$ is strongly inaccessible.
\item The Hanf Number of $\ll_{\om_1,\om_1}$ is at least $\ka_0$.
\item There are unboundedly many weakly compact cardinals less than $\ka_0$,
however $\ka_0$ is not weakly compact.
\end{enumerate}
\end{theorem}

\prob{4-22 W} Let $\ka_1$ be least such that $\ka_1\to(\om+1)^{<\om}_2$.
Prove $\ka_1>\ka_0$. Extra credit: prove it is strongly inaccessible.

\begin{theorem}
(Morley) If a countable first-order theory is categorical
in some uncountable power, then it is categorical in all
uncountable powers.
\end{theorem}

\prob{4-27 M} Let $T_n=Th(\om^\om,P_s)_{s\in\om^{\leq n}}$ where
$P_s$ is the unary predicate
$$P_s=\{x\in \om^\om\::\; s\su x\}.$$
Prove that
\par (a) rank$_{T_n}(x=x)=n+1$.
\par (b) Give an example of a $T$ such that
rank$_{T}(x=x)=\om$.

\begin{theorem}
(Shelah) Suppose $T$ is a countable theory.
\par (a) If there exists $\ka\geq\om$ such that $T$ is $\ka$-stable,
then $T$ is $\ka$-stable for every $\ka$ such that $\ka^\om=\ka$.
\par (b) $T$ is unstable iff $T$ has the order property.
\end{theorem}

\begin{thebibliography}{99}

\bibitem{addison60} Addison, J. W.; The theory of hierarchies. 1962 Logic,
Methodology and Philosophy of Science (Proc. 1960 Internat. Congr.) pp. 26--37
Stanford Univ. Press, Stanford, Calif.


\bibitem{addison62} Addison, J. W.; Some problems in hierarchy theory. 1962
Proc. Sympos. Pure Math., Vol. V pp. 123--130 American Mathematical Society,
Providence, R.I.

\bibitem{barwise} Barwise, Jon; Back and forth through infinitary logic. Studies
in model theory, pp. 5--34. MAA Studies in Math., Vol. 8, Math. Assoc. Amer.,
Buffalo, N.Y., 1973.

\bibitem{barwise-handbook}
Barwise, Jon; An introduction
to first-order logic pp. 5--46 in \cite{handbook}.

\bibitem{handbook} Barwise, Jon; {\bf Handbook of mathematical logic.} Edited by
Jon Barwise. With the cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis
and A. S. Troelstra. Studies in Logic and the Foundations of Mathematics, Vol.
90. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. xi+1165 pp.
ISBN: 0-7204-2285-X

\bibitem{bell} Bell, J. L.; Slomson, A. B.; Models and ultraproducts: An
introduction. North-Holland Publishing Co., Amsterdam-London 1969 ix+322 pp.

\bibitem{chang} Chang and Keisler; Model theory,
QA9.7 C45 1990, on reserve in math library.

\bibitem{ehrenfeucht} Ehrenfeucht, A.; An application of games to the
completeness problem for formalized theories.  Fund. Math.  49  1960/1961
129--141.
\par\url{http://matwbn.icm.edu.pl/tresc.php?wyd=1&tom=49}

\bibitem{feferman} Feferman, Anita Burdman; Feferman, Solomon;  {\bf Alfred
Tarski: life and logic.} Reprint of the 2004 original. Cambridge University
Press, Cambridge, 2008. vi+425 pp. ISBN: 978-0-521-71401-3 01A70 (03-03)

\bibitem{keisler-handbook}
Keisler, H. Jerome;  Fundamentals of model
theory pp. 47--103 \cite{handbook}.

\bibitem{keislersand}
Keisler, H. Jerome;
Theory of models with generalized atomic formulas.
J. Symb. Logic 25 1960 1--26.

\bibitem{kunen} Kunen, Kenneth; Ultrafilters and independent sets. Trans. Amer.
Math. Soc. 172 (1972), 299--306. 
\url{http://www.jstor.org/stable/1996350}

\bibitem{marker} Marker, David; Model theory : an introduction,
QA9.7 M367 2002, on reserve in math library.

\bibitem{pillay}
Pillay's lecture notes on model theory:
\par\noindent
\url{http://www.math.uiuc.edu/People/pillay/lecturenotes_modeltheory.pdf}

\bibitem{rabin} Rabin, Michael O.;
Arithmetical extensions with prescribed cardinality.
Nederl. Akad. Wetensch. Proc. Ser. A 62 = Indag. Math. 21 1959 439--446.

\bibitem{shoenfield} Shoenfield, Joseph R.; Mathematical logic. Addison-Wesley
Publishing Co., Reading, Mass.-London-Don Mills, Ont. 1967 viii+344 pp.

\bibitem{simpson}
Simpson's lecture notes on model theory:
\par\noindent
\url{http://www.math.psu.edu/simpson/courses/math563/}

\bibitem{vaught-maa} Vaught, Robert L.; Some aspects of the theory of models.
Papers in the foundations of mathematics. Amer. Math. Monthly 80 (1973), no. 6,
part II, 3--37.
\par\noindent
\url{http://www.jstor.org/stable/3038220}

\bibitem{weiss}
Weiss, William and Cherie D'Mello,
Fundamentals of Model Theory,
lecture notes are on-line:
\par\noindent
\url{http://www.math.toronto.edu/weiss/model_theory.html}

\end{thebibliography}

\end{document}
