%% 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 \usepackage{pifont} % so we can use ZapfDingbats % if needed, to get the format right: \addtolength{\textwidth}{30mm} \addtolength{\oddsidemargin}{-15mm} \addtolength{\textheight}{9mm} \addtolength{\topmargin}{-4mm} % \newcommand\one{\mathbbold{1}} % 1, for forcing orders and boolean algebras. \newcommand\AAAA{\mathfrak{A}} \newcommand\BBBB{\mathfrak{B}} \newcommand\AAA{\mathcal{A}} \newcommand\LL{\mathcal{L}} \newcommand\BB{\mathcal{B}} \newcommand\RRR{{\mathbb R}} \newcommand\ZZZ{{\mathbb Z}} \newcommand\st{\mathrm{st}} \newcommand\Fn{\mathrm{Fn}} \newcommand\TP{\mathrm{TP}} \newcommand\Th{\mathrm{Th}} \newcommand\starg{{}^*\!g} \newcommand\stuff{\hbox{Stuff}} % 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 8 \\ {\it Semester II, 2006-2007} \\ {\it Due February 22} \end{center} \bigskip \textbf{37.} Assume that $\Sigma$ in $\LL$ is consistent and has no finite models. \begin{itemizz} \item[a.] Assume that $\Sigma$ is \emph{not} model-complete, so that there are $\AAAA,\BBBB \models \Sigma$ with $\AAAA \subseteq \BBBB$ but $\AAAA \not\preccurlyeq \BBBB$. Prove that one can find such $\AAAA,\BBBB$ with $\AAAA$ uncountable. \item[b.] Explain why this proves that the theory of infinite torsion-free divisible abelian groups is model-complete. \end{itemizz} \emph{Remark and Hint.} (a) illustrates the fact that one may view a pair of models, $\AAAA,\BBBB$ as a first-order entity (possibly expanding $\LL$), and apply standard model-theoretic techniques to it. You can also easily get $\AAAA$ and $\BBBB$ to be $\aleph_1$--saturated, once you know what ``$\aleph_1$--saturated'' means. HW34 shows that in some cases one can prove model-completeness by a simple automorphism argument. (b) widens the set of examples to which this argument applies by avoiding the finite dimensional cases where HW34 doesn't apply. \bigskip \textbf{38}. Let $({}^*\RRR, {}^*\stuff)$ be an ordered field which is a proper elementary extension of the real numbers $(\RRR, \stuff)$. Let $n \in {}^*\RRR$ be an infinitely large natural number. Prove that $$ \varepsilon\ :=\ {1 \over n} \sum_{j < n} e^{j/n} \ -\ (e - 1) $$ is infinitesimal and non-0. Explain exactly what $\stuff$ is here for this argument to work. \textit{Remark.} It's more elegant to think of the elementary extension as being created by an ultrapower, so that whatever stuff you need automatically gets extended. \textit{Remark.} Note that to prove $\st(\varepsilon) = 0$, you only need that $\int_0^1 e^x\,dx = e-1$, but to prove $\varepsilon \ne 0$, you need to evaluate the sum explicitly, since a finite Riemann sum might happen to equal the integral exactly. You could use monotonicity of the exponential function or the fact that $e$ is transcendental. \bigskip \textbf{39.} Let $\Sigma$ be the theory of infinite abelian groups of exponent $30$. Prove that $\Sigma$ has exactly $\aleph_0$ complete (and maximal) extensions. Which of these are isolated (i.e., given by a single additional sentence)? \textit{Hint.} In all cases, you can prove completeness via $\aleph_0$-categoricity; there's only $\aleph_0$ countable models. Note that an abelian torsion group is a direct sum of its primary components. $\TP_0(\Sigma)$ is homeomorphic to the ordinal $\omega^2 + 1$. In the Cantor-Bendixson sequence (see HW12), $(\TP_0(\Sigma))^{(3)} = \emptyset$, $(\TP_0(\Sigma))^{(2)}$ contains the single point $\Th( (\ZZZ_2)^\omega \oplus (\ZZZ_3)^\omega \oplus (\ZZZ_5)^\omega )$, and $(\TP_0(\Sigma))^{(1)}$ contains points such as $\Th( (\ZZZ_2)^\omega \oplus (\ZZZ_3)^{23} \oplus (\ZZZ_5)^\omega )$. \textit{Remark.} ``Exponent $30$'' means $\forall x \, [x^{30} = 1]$. \bigskip \textbf{40.} Let $\BB$ be an arbitrary boolean algebra. Prove that $\BB$ is isomorphic to a Lindenbaum algebra $\AAA(\Sigma, \LL)$ in pure propositional logic. \emph{Hint.} Let $\LL = \BB$, viewed as a set of proposition letters, and let $\Sigma$ be the set of sentences whose truth value is $1$. \emph{Remark.} In universal algebra, you would say that every boolean algebra is a quotient of a free algebra. This is like the fact that every group is a quotient of a free group. One can generalize this to arbitrary equational varieties. The book \textit{A Course in Universal Algebra} by Burris and Sankappanavar is on line at \verb+http://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html +. \bigskip \textbf{41.} Work in ZF (without AC), but assume that the Compactness Theorem holds for propositional logic. Prove that every space of the form $2^I$ is compact. Here, $2 = \{0,1\}$ has the discrete topology and $2^I$ has the Tychonov topology. So, a basic clopen set is of the form $N_\sigma = \{f \in 2^I : \sigma \subseteq f\}$ where $\sigma \in \Fn(I,2)$ (the set of finite partial function from $I$ to $2$). \emph{Hint.} Let $\LL$ be a set of proposition letters. Then $f \in 2^\LL$ is a structure for $\LL$. A cover of $2^\LL$ by basic clopen sets can be identified with an inconsistent set of axioms. For example, if $\sigma$ is {\scriptsize$ \renewcommand{\arraystretch}{0.6} \arraycolsep=1pt \left( \begin{array}{ccc} p& q& r\\ 0&1&0 \end{array} \right) $}, then $f \notin N_\sigma$ iff $f \models p \vee \neg q \vee r$. \medskip \emph{Remark.} In ZF, the following statements are equivalent and are referred to as the BPIT. The BPIT is not provable in ZF (Cohen) and doesn't imply AC (Halpern and L\'evy). \begin{itemizz} \renewcommand\labelitemi{\ding{"2B}} \item The Boolean Prime Ideal Theorem: Every boolean algebra has a prime ideal (equivalently, an ultrafilter). \item Every filter on a boolean algebra can be extended to an ultrafilter. \item The Compactness Theorem for propositional logic. \item The Compactness Theorem for predicate logic. \item The Tychonov Theorem for compact $T_2$ spaces. \item The Tychonov Theorem for the space $2 = \{0,1\}$. \end{itemizz} The Tychonov Theorem for $T_1$ spaces implies the Axiom of Choice (Kelley). The BPIT implies that there is a Lebesgue non-measurable set, since a non-principal ultrafilter on $\omega$ yields a non-measurable subset of $2^\omega$ (by the zero-one law). \end{document}