%% Process me in latex2e.

% BEGIN PREAMBLE

\documentclass[12pt]{article}
\pagestyle{empty}   % no page numbers
\nofiles % no aux file

% fonts:
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{latexsym}  % latex2e symbol package

% if needed, to get the format right:
 \addtolength{\textwidth}{30mm}
 \addtolength{\oddsidemargin}{-15mm}
%\addtolength{\textheight}{36mm}
%\addtolength{\topmargin}{-18mm}


\newcommand\AAAA{\mathfrak{A}}
\newcommand\SSSS{\mathfrak{S}}

\newcommand\LL{\mathcal{L}}

\newcommand\QQQ{{\mathbb Q}} 
\newcommand\ZZZ{{\mathbb Z}} 

\newcommand\aut{\mathrm{aut}}
\newcommand\TP{\mathrm{TP}}
\newcommand\Th{\mathrm{Th}}


% an itemize-like environment, without such large spacing
\newenvironment{itemizz}{\begin{itemize}\setlength{\itemsep}{-1mm}}
{\end{itemize}}


% END PREAMBLE

\begin{document}


\begin{center}
MATH 776 HOMEWORK 11 \\
{\it Semester II, 2006-2007} \\
{\it Due April 12}
\end{center}


\bigskip




\bigskip
\textbf{52.} (Marker, Exercise 3.4.4)
Prove quantifier elimination for $\Th(\omega; <, 0, S)$.
\emph{Remark.}  This theory is finitely axiomatizable; see
HW45.
\emph{Hint.} You can do this constructively, working from the axioms,
by reducing recursively each formula to a quantifier-free formula
or $T$ or $F$; this then provides a decision procedure for the theory.
Model-theoretically, it is sufficient to show
that every $n$--type is axiomatized by its quantifier-free sentences.
We already know
from HW45 that every $n$--type is realized
in $\omega + \ZZZ \cdot \QQQ$, so it is sufficient to show that in this
ordering, if two $n$--tuples $\vec a$ and $\vec b$ satisfy the same 
quantifier-free formulas, then
there is an automorphism moving $\vec a$ to $\vec b$.
Marker describes some other
semantic methods for proving quantifier elimination,
which could be applied here also.


\bigskip
\textbf{53.} Let $\LL = \{p_i : i \in \omega\}$, where each $p_i$
is a 1--place predicate.
Let $\Sigma$ say that the $p_i$ are independent
(as in HW30 and HW43).  Fix $\kappa \ge 2^{\aleph_0}$
and let $\SSSS$ be the model of $\Sigma$ size $\kappa$ such that for
each $f \in 2^\omega$, $A$ has $\kappa$ different elements
satisfying $\bigwedge_{i\in\omega} p_i^{f(i)}(x)$.  Prove:
\begin{itemizz}
\item[a.] In $\SSSS$, 
if two $n$--tuples $\vec a$ and $\vec b$ satisfy the same 
quantifier-free formulas, then there is an automorphism moving $\vec a$
to $\vec b$.
\item[b.] If $\AAAA\models\Sigma$ and  $|\AAAA| \le \kappa$, then $\AAAA$
has an elementary extension isomorphic to $\SSSS$ (this is like HW44b).
\item[c.] $\Sigma$ has quantifier elimination.
\item[d.] $\SSSS$ is saturated.
\end{itemizz}


\bigskip
\textbf{54.} (Marker, Exercise 4.5.45)
Assume that $\Sigma$ is a complete theory
in a finite $\LL$,
$\Sigma$ has infinite models,
$\Sigma$ has quantifier elimination,
and $\LL$ has no function or constant symbols.
Prove that $\Sigma$ is $\aleph_0$ categorical.
\emph{Hint.} You can show that $\TP_n(\Sigma)$ is finite
by showing that the Lindenbaum algebra is finite.
\emph{Remark.} The result is false if we allow function
symbols (see HW52), or if we let $\LL$ be countably infinite (see HW53).

\newpage

\bigskip
\textbf{55.} Find a complete $\Sigma$ in a countable $\LL$ with
$|\TP_1(\Sigma)| = 1$ and
$|\TP_2(\Sigma)| = 2^{\aleph_0}$.
\emph{Hint.} 
Let $\LL = \{p_i : i \in \omega\}$, where each $p_i$
is a 2--place predicate.  Let $\Sigma$ be the theory of
the model $\AAAA$ in which $A = 2^\omega$ and 
$p_i$ holds of $(x,y)$ iff $x_i = y_i$.
Then $|\TP_2(\Sigma)| = 2^{\aleph_0}$ follows from the $p_i$ being
independent.
$|\TP_1(\Sigma)| = 1$ holds because $\aut(\AAAA)$ is transitive, so
that for each $\varphi(x)$,
$\Sigma$ contains $\forall x \varphi(x)$ or  $\forall x \neg\varphi(x)$.
Note that if you view $\{0,1\}^\omega$ as a (topological) group
of exponent two, then the shift maps $x \mapsto a +x$ are 
automorphisms of $\AAAA$.



\bigskip

\textbf{56.}
Let $(A; <)$ be a saturated dense total order,
with $|A| = \kappa$.  Prove that $\kappa^{<\kappa} = \kappa$
(equivalently, $2^{<\kappa}  = \kappa$ and $\kappa$ is regular).
\textit{Hint.} First show that inside each open interval
you can find $\kappa$ disjoint subintervals.  Then,
you can embed the tree $\,{}^{< \kappa}\!\kappa$ into the intervals of $A$.
\textit{Remark.} If there are no inaccessible cardinals and
$2^{\aleph_\alpha} = \aleph_{\alpha+2}$ for all $\alpha$
(which is consistent), then there are no such $\kappa$ other than $\omega$.
\textit{Remark.} Actually, you don't need the order to be dense --
this just makes the proof slightly easier.



\end{document}