\documentclass[twoside,a4paper,12pt,draft]{article}
\usepackage{amssymb,amsmath,amsthm}
\title{Model-theory homework}
\date{2001, fall}
\author{Math 736---David Pierce}
\pagestyle{myheadings}
 \markboth{Model-theory homework IV}{Math 736, fall 2001}

% \addtolength{\voffset}{-2cm}
 %\addtolength{\textheight}{4cm}

\renewcommand{\theenumi}{\fnsymbol{enumi}}
\renewcommand{\labelenumi}{\textnormal{(\theenumi)}}


\newcommand{\Z}{\mathbf Z}          % the integers
\newcommand{\Q}{\mathbf Q}          % the rationals
%\newcommand{\A}{\mathbf A}          % affine space
\newcommand{\R}{\mathbf R}          % the reals
\newcommand{\N}{\mathbf{N}}         % the naturals
\newcommand{\C}{\mathbf{C}}         % the complex numbers
\newcommand{\F}{\mathbf{F}}         % (finite) field

\newcommand{\id}{\mathrm{id}}       % identity-function

\newcommand{\unit}[1]{{#1}^{\times}} % group of units of a ring

\newcommand{\stroke}{\mathrel{|}}   % stroke for semi-group example

\newcommand{\str}[1]{\mathcal{#1}}  % structure with universe #1

%I don't like the standard loose inequalities
\renewcommand{\leq}{\leqslant}
\renewcommand{\nleq}{\nleqslant}
\renewcommand{\geq}{\geqslant}

%I don't much like the standard here either:
\renewcommand{\setminus}{-}

%I don't want epsilon to look like `is an element of'
\renewcommand{\epsilon}{\varepsilon}

\newcommand{\To}{\longrightarrow}

\newcommand{\mapset}[2]{#2^{#1}}

\newcommand{\Mod}{\mathfrak{Mod}}
\DeclareMathOperator{\Th}{Th}
\newcommand{\pow}{\mathcal{P}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\arity}[1]{\textrm{arity}(#1)}
\newcommand{\proj}{\pi}
\newcommand{\inv}{^{-1}}
\newcommand{\Fm}[1]{\mathrm{Fm}^{#1}}
\newcommand{\Fmo}[1]{\mathrm{Fm}^{#1}_0}
\newcommand{\2}{\mathbf{F}_2}

\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\elsub}{\preccurlyeq}
\newcommand{\Ba}{\mathcal{M}^\mathrm{a}}  % a Boolean algebra
\newcommand{\Br}{\mathcal{M}^\mathrm{r}}  % a Boolean ring

\DeclareMathOperator{\diag}{diag}   % Robinson diagram of a structure

\DeclareMathOperator{\sgn}{sgn}     % signum of a permutation

\newcommand{\included}{\subseteq}   % the name suggests the meaning here
\newcommand{\lang}{\mathcal L}      % a language
\newcommand{\SL}{\mathrm{PL}}       % Propositional (was sentential) logic
\newcommand{\pairing}[1]{\langle#1\rangle} % pairing

\newcommand{\tech}[1]{\textbf{#1}}

 \newtheorem{lemma}{Lemma}
 %\setcounter{lemma}{-1}
 %\theoremstyle{definition}
 \newtheorem{problem}{Problem}


\newtheorem*{theorem}{Theorem}
%\newtheorem*{lemma}{Lemma}
\newtheorem*{corollary}{Corollary}

\theoremstyle{remark}
\newtheorem*{remark}{Remark}
\newtheorem*{example}{Example}
\newtheorem*{examples}{Examples}

%  For distinguishing claims made and proved within proofs
%\newtheoremstyle{subclaim}{0pt}{0pt}{\itshape}{}{\bfseries}{}{0em}{}
%\theoremstyle{subclaim}
%\newtheorem*{claim}{}

\newcommand{\tuple}{\mathbf}
\newcommand{\reduct}{\overline}

%  Should the word `modulo' be italicized?
\newcommand{\modulo}{\emph{modulo}\ }

%  To distinguish terms being defined
\newcommand{\defn}[1]{{\bf#1}}


 \setcounter{problem}{6}

\begin{document}
%\maketitle
\thispagestyle{empty}

\noindent\emph{Homework IV, Math 736, Model-Theory.}

Elements $a_0$, \dots, $a_{k-1}$ of an abelian group are called
\tech{additively independent} if
\begin{equation*}
\sum_{i<k}n_ia_i\neq0
  %n_0a_0+\dots +n_{k-1}a_{k-1}=0
  %\implies n_0=\dots=n_{k-1}=0
\end{equation*}
for all integers $n_0$ \dots, $n_{k-1}$, not all of which are 0.

\begin{problem}
Let $\Q$ be the \emph{abelian group} of rational numbers.  Show that
there is an abelian group $\str G$ such that:
\begin{enumerate}
\item
 $\str G\equiv\Q$, and
\item
 $\str
G$ contains $n$ additively independent elements for every $n$ in
$\omega$.
\end{enumerate}
Then show that any two such \emph{countable} groups are isomorphic.
\end{problem}

Now let $\lang$ be an arbitrary signature.  If $\str M,\str
N\in\Mod(\lang)$ and $\str M\included\str N$, let us write
\begin{equation*}
  \str M\preccurlyeq_1\str N
\end{equation*}
if the inclusion of $M$ in $N$ preserves \emph{universal} formulas of
$\lang$.

\begin{problem}
Prove that the following are equivalent:
\begin{enumerate}
  \item
  $\str M\preccurlyeq_1\str N$
  \item
  there is $\str R$ in $\Mod(\lang)$ such that $\str M\preccurlyeq\str R$
  and $\str N\included\str R$.
\end{enumerate}
\end{problem}

Suppose $\{\str M_n:n\in\omega\}$ is a subset of $\Mod(\lang)$ forming a
\tech{chain}, that is, $\str M_n\included\str M_{n+1}$ for all $n$ in
$\omega$.  Then the \tech{union} of this chain is defined to be the
structure $\str N$, where:
\begin{enumerate}
\item
 $N=\bigcup_{n\in\omega}M_n$, and
\item
 for all basic formulas $\phi$, if
$\tuple a$ is a tuple from $M_n$, and $\str M_n\models\phi(\tuple a)$,
then $\str N\models\phi(\tuple a)$.
\end{enumerate}
  (You should verify that $\str N$ is
well-defined, but you need not submit the verification.)  The chain is
called \tech{elementary} if $\str M_n\preccurlyeq\str M_{n+1}$ for all
$n$.

\begin{problem}
Show that the union of an elementary chain is an elementary extension of
each structure in the chain.
\end{problem}

Recall that a theory $T$ of $\lang$ is called \tech{model-complete} if
$\str M\preccurlyeq\str N$ whenever $\str M\included\str N$ and both
structures are models of $T$.  A formally weaker notion is
\tech{1-model-completeness}: $T$ is 1-model-complete if $\str
M\preccurlyeq_1\str N$ whenever $\str M\included\str N$ and both
structures are models of $T$.

\begin{problem}
Prove that 1-model-completeness and model-completeness coincide.
\end{problem}

\end{document}