%% 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}{4mm} \addtolength{\oddsidemargin}{-2mm} \addtolength{\textheight}{20mm} \addtolength{\topmargin}{-10mm} \newcommand\starg{{}^*\!g} \newcommand\LL{\mathcal{L}} \newcommand\RRR{{\mathbb R}} \newcommand\ZZZ{{\mathbb Z}} \newcommand\HF{\mathit{HF}} \newcommand\PA{\mathit{PA}} \newcommand\cccc{\mathfrak{c}} \newcommand\AAAA{\mathfrak{A}} \newcommand\BBBB{\mathfrak{B}} % an itemize-like environment, without such large spacing \newenvironment{itemizz}{\begin{itemize}\setlength{\itemsep}{-1mm}} {\end{itemize}} % END PREAMBLE \begin{document} \begin{center} MATH 770 HOMEWORK 6 \\ {\it Semester I, 2006-2007} \\ {\it Due December 14} \end{center} \bigskip \textbf{25.} Here is your token formal proof. It should convince you that our proof theory is a bit awkward in practice. But, our proof theory is also simple, which is good for proving abstract theorems about it. {\it Display\/} a formal proof of $\exists x (x = x)$ from $\emptyset$, using the proof theory on the handout. You may use the standard abbreviations for the sentences occurring in the proof, but don't skip steps in the proof. Observe that the sentences $\forall x (x = x \to \exists x (x = x))$ and $\forall x \exists x (x = x) \to \exists x (x = x)$ are logical axioms of types (5) and (4) respectively. \bigskip \textbf{26.} If $\Sigma, \Delta$ are sets of sentences of $\LL$, say that $\Sigma \circeq \Delta$ iff they have the same models. Prove that there is a finite $\Delta$ such that $\Sigma \circeq \Delta$ iff there is a finite $\Delta \subseteq \Sigma$ such that $\Sigma \circeq \Delta$. \emph{Remark.} Then $\Sigma$ is called \emph{finitely axiomatizable}. \bigskip \textbf{27.} Let $\AAAA = (\omega, <)$. Prove: \begin{itemizz} \item[a.] If $\BBBB \equiv \AAAA$ and $\BBBB \not\cong \AAAA$ then $\BBBB$ consists of $\omega$ followed by some collection of blocks isomorphic to $\ZZZ$. \emph{Remark.} Every such $\BBBB$ is $\equiv \AAAA$, but that's harder to prove. \item[b.] Assume that $\BBBB \equiv \AAAA$ and $\BBBB \not\cong \AAAA$, and assume that $E \subseteq B$ is definable and meets one of the $\ZZZ$--blocks. Then $E$ contains the entire block. \emph{Hint.} Consider automorphisms of $\BBBB$ which shifts the block. \item[c.] The set of even numbers is not definable in $\AAAA$. \emph{Hint.} A $\varphi$ for which $\forall x \,[\varphi(x) \iff \neg\varphi(S(x))]$ holds would contradict (b). Note that ``successor'' is definable. \item[d.] The set of even numbers is not $\Delta_0$ in $\HF$. \end{itemizz} \bigskip \textit{Definition.} $\AAAA \subseteq \BBBB$ (\textit{substructure}) iff $A \subseteq B$ and the functions and/or predicates of $\AAAA$ are the restrictions of the corresponding ones of $\BBBB$. $\AAAA \preccurlyeq_\varphi \BBBB$ means that $\AAAA \subseteq \BBBB$ and $\AAAA \models \varphi[\sigma]$ iff $\BBBB \models \varphi[\sigma]$ for all assignments $\sigma$ into $A$. $\AAAA \preccurlyeq \BBBB$ (\textit{elementary substructure}) iff $\AAAA \preccurlyeq_\varphi \BBBB$ for all $\varphi$ in $\LL$. \bigskip \textbf{28.} Assume that the ordered field $(F; +, \cdot, <, \starg)$ is a proper elementary extension of $(\RRR; +, \cdot, <, g)$. Fix $r \in \RRR$. Prove that the following are equivalent: \vbox{ % don't break this \begin{itemizz} \item[1.] $g$ is differentiable at $0$ and $g'(0) = r$. \item[2.] ${\starg(\varepsilon) - g(0) \over \varepsilon} \sim r$ for all infinitesimals $\varepsilon$. \end{itemizz} \textit{Remark.} There are many variants of this. For example, ${\starg(\varepsilon) - g(0) \over \varepsilon} \sim r$ for all positive infinitesimals $\varepsilon$ iff the derivative of $g$ from the right is $r$. } \bigskip \textbf{29.} With $\LL = \{\cdot, i, 1\}$, prove: \begin{itemizz} \item[a.] If $\varphi$ is a sentence true in all finite groups, then $\varphi$ is true in \emph{some} infinite group. \item[b.] If $\varphi$ is a sentence true in all finite abelian groups of exponent $p$ (where $p$ is prime), then $\varphi$ is true in \emph{all} infinite abelian groups of exponent $p$. \emph{Hint.} Use categoricity or completeness. \item[c.] Find a sentence $\varphi$ which is true in all finite groups and false in some infinite group. \emph{Hint.} Try $\forall x \, [x \ne 1 \to x^2 \ne 1] \to \forall x \exists y \, [ y^2 = x] $. \end{itemizz} \bigskip \textbf{30.} 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$. Prove that $\Sigma$ is complete and not $\kappa$--categorical for any $\kappa \ge \aleph_0$. \emph{Remark.} The theory of real-closed fields is a better example of this. \emph{Hint.} Prove that the reduct of $\Sigma$ to any finite subset of $\LL$ is $\aleph_0$--categorical. \bigskip \textbf{31.} Define $E \subseteq \omega\times\omega$ by: $ n E m \iff 2 \nmid \lfloor m 2^{-n} \rfloor $ (equivalently, there is a $1$ in place $n$ in the binary representation of $m$ (counting from the right; so $43 = 101011_b$ has a $1$ in places 0,1,3,5)) Prove that $(\omega; E) \cong (\HF; \in)$. \textit{Remark.} $|\HF| = \aleph_0$ is obvious from the definition of $\HF$, but the fact that there is this computable bijection is important in recursion theory if you want to identify the notion of ``decidable'' on $\HF$ with the notion of ``decidable'' on $\omega$. It's also important in proof theory when you show that Peano Arithmetic ($\PA$) is equivalent to the axioms $ZF - \infty + \mbox{all sets are finite}$. \emph{Examples.} If $f: \omega \to \HF$ is the isomorphism, then: \\ $f(0) = \emptyset = 0 $ \\ $f(1) = \{\emptyset\} = 1 $ \\ $f(2) = f(10_b) = \{1\} $ \\ $f(3) = f(11_b) = \{1,0\} = 2 $ \\ $f(5) = f(101_b) = \{\{1\},0\} $ \\ $f(43) = f(101011_b) = \{f(5), f(3), f(1), f(0)\} = \{\{\{1\}, 0\}, 2, 1, 0\}$\\ $f(2^{65536}) = \{ \{\{\{\{1\}\}\}\} \}$\\ $f(123456789123456789) = $\\ \phantom{foo}$\{$ {\tiny $\{\{\{1\}, 0\}, \{\{1\}\}, 2\},\: \{\{\{1\}, 0\}, \{\{1\}\}, \{1\}, 1, 0\},\: \{\{\{1\}, 0\}, \{\{1\}\}, \{1\}, 0\},\: \{\{\{1\}, 0\}, \{\{1\}\}, \{1\}\}, $\\ \phantom{foooooo}$ \{\{\{1\}, 0\}, \{\{1\}\}, 1\},\: \{\{\{1\}, 0\}, \{\{1\}\}, 0\},\: \{\{\{1\}, 0\}, 2, \{1\}, 1, 0\},\: \{\{\{1\}, 0\}, 2, \{1\}\},\: \{\{\{1\}, 0\}, 2, 1, 0\}, $\\ \phantom{foooooo}$ \{\{\{1\}, 0\}, 2, 0\},\: \{\{\{1\}, 0\}, 2\},\: \{\{\{1\}, 0\}, \{1\}, 1\},\: \{\{\{1\}, 0\}, 1, 0\},\: \{\{\{1\}, 0\}, 0\},\: \{\{\{1\}, 0\}\}, $\\ \phantom{foooooo}$ \{\{\{1\}\}, 2, \{1\}, 1, 0\},\: \{\{\{1\}\}, 2, \{1\}, 0\},\: \{\{\{1\}\}, 2, 1, 0\},\: \{\{\{1\}\}, 2, 1\},\: \{\{\{1\}\}, \{1\}, 1, 0\},\: \{\{\{1\}\}, \{1\}, 1\},\: $\\ \phantom{foooooo}$ \{\{\{1\}\}, \{1\}\},\: \{2, \{1\}, 1\},\: \{2, \{1\}\},\: 3, \{2, 1\},\: \{2, 0\},\: \{2\},\: \{\{1\}\},\: \{1\},\: 0$ } $\}$\\ Observe that $f$ lists all of $R(n)$ before going on to $R(n+1)$, so the length of the number $n$ is not simply related to the length of the expression for $f(n)$. \end{document}