%% 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


\newcommand\AAAA{\mathfrak{A}}
\newcommand\BBBB{\mathfrak{B}}

\newcommand\LL{\mathcal{L}}

\newcommand\RRR{{\mathbb R}} 
\newcommand\CCC{{\mathbb C}} 
\newcommand\QQQ{{\mathbb Q}} 

\newcommand\st{\mathrm{st}}

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

\newcommand\AC{\mathsf{AC}}

\newcommand\lh{\mathrm{lh}}

% restriction:
\newcommand\rest{\upharpoonright}     % as a relation
\newcommand\res{\mathord {\upharpoonright}}  % less space around it

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


\bigskip

Let $F$ be an ordered field which properly extends $\RRR$.
Call $\varepsilon \in F$
\textit{infinitesimal} iff $\varepsilon  \ne 0$ but
$|\varepsilon| < |r|$ for all non-zero $r \in \RRR$. 
Call $\Delta \in F$
\textit{infinitely large} iff $|\Delta|  > |r|$ 
for all  $r \in \RRR$.  The following was more-or-less done in 770:
\begin{itemizz}
\item[a.] For any $s \in F \backslash \{0\}$,
$s$ is infinitesimal iff $1/s$ is infinitely large.
\item[b.] For any $s \in F$ which is not infinitely large,
there is a unique $t \in \RRR$ such that 
$s-t$ is infinitesimal or $0$.  This $t$ is called the
\textit{standard part} of $s$ ($\,t = \st(s)\,$).
\ \ $t = \sup\{r \in \RRR : r \le s\}$.
\item[c.] Infinitesimals exist.  \textit{Proof:}
Fix $s \in F \backslash \RRR$.
If $s$ is infinitely large then $1/s$ is infinitesimal.
Otherwise, $s - \st(s)$ is infinitesimal.
\end{itemizz}


\textbf{32.}
Let $(F; +, \cdot, <, \starg)$ be a proper elementary extension
of $(\RRR; +, \cdot, <, g)$, where $g: \RRR \to \RRR$ is a bounded function.
Note that by elementarity, $\starg$ extends $g$ and has the same bound,
so that $\st(\starg(s))$ is defined for each $s\in F$.
Prove that the following are equivalent:
\begin{itemizz}
\item[a.]  $\lim_{x \to 0} g(x)$ exists in $\RRR$.
\item[b.]  $\st(\starg(\varepsilon))$ has the same value for each
infinitesimal $\varepsilon$.
\end{itemizz}
Note that in (b), that value must be $\lim_{x \to 0} g(x)$.
\textit{Remark.} This problem is similar to HW28.

\bigskip
\textbf{33.}
\textit{Built-in Skolem Functions.}
Let $\Sigma$ be a set of sentences of $\LL$ and let
$\varphi(x_1, \ldots, x_n, y)$ be a formula of $\LL$.
Let $\LL' = \LL\cup \{f\}$ where $f$ is a new $n$--place function symbol.
Let $\Sigma' = \Sigma \cup \left\{\; \forall \vec x
\,[\exists y\, \varphi(\vec x, y)
\to \varphi(\vec x, f(\vec x))]\;\right\}$.
Then:
\begin{itemizz}
\item[a.] Prove that $\Sigma'$ is a \textit{conservative extension} of $\Sigma$.
That is, whenever $\psi$ is an  $\LL$--sentence,
if $\Sigma' \vdash \psi$ then $\Sigma \vdash \psi$.
\textit{Hint.} Every model of $\Sigma$ can be expanded to
a model of $\Sigma'$.
\item[b.] Let  $\LL = \{\in\}$ and let $\psi$ be $\AC$,
an $\LL$--sentence which says
that every set can be well-ordered.  Explain why (a) doesn't show that
$\mathit{ZF} \vdash \AC$.  Naively, we could apply (a) with
$\Sigma = \mathit{ZF}$, $n = 1$,
and $\varphi(x,y)$ the formula $y \in x$; then $f$ becomes a choice
function, so (naively), 
$\Sigma'  \vdash \AC$.  
\end{itemizz} 

\noindent
\textit{Remark.} A finitistic proof of (a) is known, but is rather
difficult.

\newpage

\textbf{34.}
(Chang-Keisler Exercise 3.1.1) Assume that $\AAAA \subseteq \BBBB$
and for all $a_1, \ldots, a_n \in A$ and $b \in B$, there is
an automorphism $\sigma$ of $\BBBB$ such that $\sigma(a_i)= a_i$
for each $i$ and $\sigma(b) \in A$.  Prove that
$\AAAA \preccurlyeq \BBBB$.  

Then, explain why this applies when
$\AAAA,\BBBB$ are infinite abelian groups of
exponent $p$ (where $p$ is prime), so that this theory is model-complete.


\bigskip
\textbf{35.}
Assume that $\Sigma$ is consistent.
Prove that $\Sigma$ has only finitely many complete extensions 
iff \textit{each} such extension is axiomatized by
$\Sigma \cup \{\psi\}$ for some sentence $\psi$.
\textit{Hint.} For $\rightarrow$,  induct on the number of extensions.  For
$\leftarrow$, use compactness.

\bigskip
\textbf{36.}
Prove that if $\Sigma$ has $<\! 2^{\aleph_0}$ many complete extensions,
then \textit{some} such extension is axiomatized by
$\Sigma \cup \{\psi\}$ for some sentence $\psi$.
\textit{Hint.} If there is no such $\psi$, construct a tree of
incompatible extensions.  So, you'll get $\psi_s$ for
$s \in 2^{<\omega}$ such that each
$\Sigma \cup \{\psi_s\}$ is consistent,
$\Sigma \cup \{\psi_s\} \cup \{\psi_t\}$ is inconsistent
whenever $s,t \in 2^n$ and $s \ne t$ ,
and each $\psi_s \vdash \psi_{s\res m}$ whenever
$m < \lh(s)$.

\bigskip
\textit{Remark.}  Let $X$ be a compact Hausdorff ($=T_2$) space.
The topological analog of
(35) says that
$X$ is finite iff every point is isolated.
The topological analog of
(36) says that
if $|X| <  2^{\aleph_0}$, then some point is isolated
(if $X$ has no isolated points, a tree argument shows that
$|X| \ge 2^{\aleph_0}$).


\end{document}