%% Process me in latex2e.

% BEGIN PREAMBLE

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

% fonts:
\usepackage{amsmath}  % so we can use \limsup
\usepackage{amssymb}


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


\newcommand\nnnn{\mathsf{n}}

\newcommand\AAAA{\mathfrak{A}}
\newcommand\RRRR{\mathfrak{R}}
\newcommand\FFFF{\mathfrak{F}}
\newcommand\SSSS{\mathfrak{S}}

\newcommand\LL{\mathcal{L}}
\newcommand\UU{\mathcal{U}}
\newcommand\PP{\mathcal{P}}

\newcommand\RRR{{\mathbb R}} 
\newcommand\CCC{{\mathbb C}} 
\newcommand\QQQ{{\mathbb Q}} 
\newcommand\ZZZ{{\mathbb Z}} 
\newcommand\NNN{{\mathbb N}} 

\newcommand\st{\mathrm{st}}
\newcommand\TP{\mathrm{TP}}
\newcommand\ZF{\mathrm{ZF}}
\newcommand\PA{\mathrm{PA}}
\newcommand\Th{\mathrm{Th}}

\newcommand\starg{{}^*\!g}
\newcommand\starh{{}^*\!h}

% 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 9 \\
{\it Semester II, 2006-2007} \\
{\it Due March 8}
\end{center}

\textbf{42}.
Let $\Sigma = \Th(\QQQ, <) = \Th(\, (0,1), < )$.
Prove that $|\TP_4(\Sigma)| = 75$.  \emph{Remark.}
Every $n$--type is realized in some countable model, and hence in $\QQQ$.
$|\TP_5(\Sigma)| = 541$.
$|\TP_6(\Sigma)| = 4683$.
$|\TP_7(\Sigma)| = 47293$.
$|\TP_8(\Sigma)| = 545835$.
$|\TP_9(\Sigma)| = 7087261$.
$|\TP_{10}(\Sigma)| = 102247563$.
$|\TP_{11}(\Sigma)| = 1622632573$.
$|\TP_{12}(\Sigma)| = 28091567595$.
$|\TP_{13}(\Sigma)| = 526858348381$.


\bigskip
\emph{Remark.} Assume that $\Sigma$ is consistent.
Then $\TP_0(\Sigma)$ has \emph{no} isolated points iff $\Sigma$
is \emph{essentially incomplete} (that is, no extension of $\Sigma$
by one more axiom is complete).
By the G\"odel Incompleteness Theorem, $\ZF$ and $\PA$ are
essentially incomplete.  Also, it is well-known that
every non-empty second countable boolean space with no isolated points
is homeomorphic to the Cantor set $2^\omega$ (equivalently, the theory
of atomless boolean algebras is $\aleph_0$--categorical).
Thus, $\TP_0(\ZF)$  and $\TP_0(\PA)$ are homeomorphic to the Cantor set.

\bigskip
\textbf{43}.
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.  If  
$p_i^1$ abbreviates $\neg p_i$ and $p_i^0$ abbreviates $p_i$ then
$\Sigma$ consists of all sentences of the form
$\exists x \bigwedge_{i < n} p_i^{s_i}(x)$, where $n \in \omega$
and $s \in 2^n$.
Then $\Sigma$ is complete and not $\kappa$--categorical
for any $\kappa \ge \aleph_0$ (see HW30).
Prove that $\TP_n(\Sigma, \LL)$ is homeomorphic to the Cantor set 
for each $n \ge 1$.  In the case $n = 1$, your homeomorphism should
be ``natural''.  For $n > 1$, you may use the above remark.

\bigskip
\textbf{44.} Let $\LL = \{\equiv\}$ and let $\Sigma$ be the
theory of an equivalence relation such that there is exactly
one equivalence class of each size $n$ (for  $0 < n < \omega$).
Let $\SSSS$ be the model with exactly $\aleph_0$ infinite classes,
each of size $\aleph_0$.
Let $\AAAA$ be the model with no infinite classes.  Prove that:
\begin{itemizz}
\item[a.] $\Sigma$ is not $\kappa$-categorical for any $\kappa \ge \aleph_0$.
\item[b.] Every countable model of $\Sigma$ has an
elementary extension isomorphic to $\SSSS$ (use the elementary diagram,
adding constants for representatives of the $\aleph_0$ infinite classes).
\item[c.] $\Sigma$ is complete (use (b)).
\item[d.] $\TP_1(\Sigma)$ is homeomorphic to $\omega + 1$.
\end{itemizz}
\emph{Remark.}  By (b), every $n$--type is realized in $\SSSS$,
so all $\TP_n(\Sigma)$ are countable, and hence scattered.
$\AAAA$ is the atomic model for $\Sigma$
(only isolated $n$--types are realized), and  $\SSSS$ 
is the countable saturated model
(everything that should be there is there).  Proving that a theory
is complete by showing that there is a unique saturated model in
some cardinality is a standard trick; Chang-Keisler does this
for real-closed fields (Theorem 5.4.4).


\bigskip
\textbf{45.}
Let $\LL = \{<\}$, and let $\Sigma$ be the (finite) set of axioms
which says that $<$ is a total order with a first element,
every element has a (unique)
successor, and every element other than the first one has a (unique)
predecessor. So, $(\omega, <) \models \Sigma$.  Prove:
\begin{itemizz}
\item[a.] $\AAAA \models \Sigma$ iff $\AAAA$ consists of $\omega$
followed by some (possibly empty) collection of blocks isomorphic to $\ZZZ$.
\emph{Remark.} This is similar to HW27a.
\item[b.] If $\AAAA \models \Sigma$ and $\AAAA$ is countable
then $\AAAA$ has an elementary extension isomorphic
to $\omega + \ZZZ \cdot \QQQ$.
\emph{Hint.} Take elementary extensions $\omega$ times.
Given $\AAAA_n$, make a list, in type $\le \omega$, of all
pairs of adjacent $\ZZZ$--blocks in $\AAAA_n$.
At stage $2^n 3^k$, make sure that the 
$k^{\mathrm{th}}$ pair from $\AAAA_n$ is not adjacent in $\AAAA_{2^n 3^k + 1}$.
Then the $\ZZZ$--blocks in $\AAAA_\omega$ will be densely ordered.
Likewise, make sure that there is no first
and no last $\ZZZ$--block in $\AAAA_\omega$.
\item[c.] $\Sigma$ is complete (use (b)).
\item[d.] $\Th(\omega, <)$ is decidable (use (c)).
\emph{Remark.} Quantifier-elimination gives you an algorithm
which will actually terminate (with reasonable inputs) before
the universe dies.
\end{itemizz}
\emph{Remark.} $\omega$ is the atomic model for $\Sigma$ and
$\omega + \ZZZ \cdot \QQQ$ is the saturated model.


\bigskip
\textbf{46.}
Let $\ell^\infty$ be the set of all bounded functions in $\RRR^\NNN$.
A \emph{Banach limit} (Banach, 1932) is a linear functional
$\Phi : \ell^\infty \to \RRR$ satisfying:
\begin{itemizz}
\item[1.] $\varliminf_n g(n) \le \Phi(g) \le \varlimsup_n g(n)$.
\item[2.] $\Phi(g) = \Phi(S(g))$, where $(S(g))(n) = g(n+1)$.
\end{itemizz}
To prove that such a $\Phi$ exists, let
$h(n) = \frac{1}{n}\sum_{\ell<n} g(\ell)$, and let
$\Phi(g) = \st(\starh(\nnnn))$, where $\nnnn$ is an infinitely 
large natural number.
\begin{itemizz}
\item[a.] Make this all rigorous by letting
$\LL \supseteq \{N\} \cup
\{  {}^\ulcorner\!\! f\! ^\urcorner : f \in \RRR^\RRR\}$,
where $N$ is a unary predicate.
Let $\RRRR$ be the natural model for $\LL$ with universe
$\RRR$, interpreting $N$ as $\NNN$.
Let $\FFFF$ be a proper elementary extension of $\RRRR$.
\item[b.] Now, let $\UU$ be a non-principal
ultrafilter on $\omega$ and let $\FFFF = \RRRR^\omega / \UU$.
Let $\nnnn \in \RRR^\omega / \UU$ be the equivalence class
of the map $n \mapsto n$.  Then prove that 
$\Phi(g)$ is just the $\UU$--limit of $h$;
that is, the unique $r \in \RRR$ such that 
$\{n \in \omega : r - \varepsilon < h(n) < r  + \varepsilon\} \in \UU$ 
for all $\varepsilon > 0$.
\end{itemizz}
\emph{Remark.} By (b), you can avoid all the logic in this construction;
if you just \emph{define} $\Phi(g)$ to be the $\UU$--limit of $h$,
you can easily check its properties directly.  You can find this proof
on-line at:
{\scriptsize
\verb+ http://planetmath.org/encyclopedia/ConstructionOfBanachLimitUsingLimitAlongAnUltrafilter.html +
}


\end{document}