\documentclass{amsart}

\usepackage{amssymb} 

\title{21-300 F15 HW 6}

\begin{document}



\maketitle


   IMPORTANT: PLEASE EMAIL COMPLETED HOMEWORKS TO:
\begin{verbatim}
   lserafin.algebra@gmail.com
\end{verbatim}

\begin{enumerate}

\item Let ${\mathcal M}$ be a substructure of $\mathcal N$. Suppose that
    for every formula $\psi(z, y_1, \ldots y_n)$ and all
    $a_1, \ldots a_n \in M$, if there is $b \in N$ such that
   ${\mathcal N} \models \psi(b, a_1, \ldots a_n)$ then there
    is $a \in M$ such that ${\mathcal N} \models \psi(a, a_1, \ldots a_n)$.

    Prove that ${\mathcal M}$ is an elementary substructure of ${\mathcal N}$,
    that is to say for all $\phi(z_1, \ldots z_n)$ and all $a_1, \ldots a_n \in M$,
    ${\mathcal M} \models \phi(a_1, \ldots a_n) \iff {\mathcal N} \models \phi(a_1, \ldots a_n)$.

    Hint: You know from the midterm (and may assume here) that the conclusion is true for
    all quantifier free formulae $\phi$. Use the assumption to power an induction.
    Be careful, the conclusion talks about satisfaction in ${\mathcal M}$ and ${\mathcal N}$ but
    the assumption only mentions satisfaction in ${\mathcal N}$.


\item  Let $\mathcal L$ be a language with constant symbols $0$ and $1$, binary function symbols $+$, $\times$, $pow$ (for power)
    and binary relation symbols $\equiv$ (the equality symbol) and $<$. In a slight abuse of notation, let
    $\mathbb R$ be the $\mathcal L$-structure whose underlying set is the real numbers in which each
   symbol is given the natural interpretation; $pow^{\mathbb R}$ is the function which takes
   $(x, y)$ to $x^y$ when $x > 0$ and to zero otherwise. 


 Let $T$ be the complete diagram of $\mathbb R$,
   that is the set of all sentences of the expanded language which are true in $\mathbb R$.

\begin{enumerate}

\item  Let $c$ be a new constant and let $T^*$ be the theory 
    $T \cup \{ c_0 < c < c_r : r \in {\mathbb R}, r > 0 \}$. 
    Prove that $T^*$ is consistent.

\item  Let ${\mathbb R}^*$ be a model of $T^*$, and (in another abuse of notation) identify the
    real number $r$ with the interpretation of $c_r$ in ${\mathbb R}^*$.
    Let $d$ be the interpretation of $c$ in ${\mathbb R}^*$. 
\begin{enumerate}
\item Prove that in ${\mathbb R}^*$ there is a unique element $d'$ such that $d \times d' = 1$.
\item Prove that in ${\mathbb R}^*$, $d' > n$ for every natural number $n$.
\item Prove that in ${\mathbb R}^*$ there is an element $e$ such that $0 < e < d^n$ for every natural number $n$. 
\end{enumerate}


\end{enumerate}

\item Let $\phi_n$ be a sentence in the language of graphs expressing
    ``for every pair $(A, B)$ of sets of vertices with $A \cap B = \emptyset$
      and $\vert A \vert = \vert B \vert = n$ there is a vertex $v \notin A \cup B$
      such that $v E w$ for all $w \in A$ and $\neg v  E w$ for all $w \in B$''.
      Let $T^* = T_{graphs} \cup \{ \phi_n : n > 0 \}$. 

\begin{enumerate}
\item  Prove that $T^*$ has at least one countably infinite model (harder than it looks, try making a model where the
   underlying set is $\mathbb N$ using a listing of all pairs $(A, B)$ of disjoint subsets of $\mathbb N$ which have the same size).
\item Prove that any two countably infinite models of $T^*$ are isomorphic. Hint: back and forth. 
\end{enumerate} 


\item  Let $T$ be a theory and let $T \vdash \psi$, where $\psi$ is a quantifier-free sentence
   containing some constant symbols $c_1, \ldots c_n$ that are distinct and
   do not appear in $T$. Prove that $T \vdash \forall y_1 \; \ldots \forall y_n \; \psi'$,
   where $y_1, \ldots y_n$ are distinct variable symbols not appearing in $\psi$ and
   $\psi'$ is the result of replacing $c_i$  by $y_i$ for each $i$. 


\item   Let $T$ be a theory in a first order language ${\mathcal L}$, and let
    $T_\forall$ be the set of universal sentences $\psi$ of $\mathcal L$ such that $T \vdash \psi$
    (a sentence is {\em universal} if it has the form $\forall y_1 \ldots \forall y_n \: \psi(y_1, \ldots y_n)$
    where $\psi$ is quantifier-free).
   Prove that if ${\mathcal N} \models T$ and ${\mathcal M}$ is a substructure of ${\mathcal N}$ then 
    ${\mathcal M} \models T_\forall$. 

\item Let $T$ be a theory and let  ${\mathcal M} \models T_\forall$. Let $T^* = T \cup D$ where
    $D$ is the ``atomic diagram'' of ${\mathcal M}$, that is the set of all atomic sentences $\psi$ in the expanded langauge for
   ${\mathcal M}$ such that ${\mathcal M} \models \psi$. 

   Prove that $T^*$ is consistent. Hint: If not then $T$ proves the negation of a finite conjunction of elements of
   $D$. Now use a previous question. 

   Prove there is a structure $\mathcal N$ such that
   $\mathcal N \models T$ and ${\mathcal M}$ is a substructure of $\mathcal N$.  








\end{enumerate}

\end{document} 



