\documentclass{amsart}

\usepackage{amssymb} 

\title{21-300 F15 HW 7}

\begin{document}



\maketitle


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

\begin{enumerate}

\item  Let $\mathcal L$ be some FOL. A sentence in $\mathcal L$ is said to be a $\forall \exists$
   sentence if it has the form $\forall y_1\; \ldots \forall y_m \; \exists z_1 \; \ldots \exists z_n \; \psi$
   where $\psi$ is quantifier free.

   Suppose that $T$ is a set of $\forall \exists$ sentences and that
 $\langle {\mathcal M}_n : n \in {\mathbb N} \rangle$ is 
   a sequence of structures, such that  ${\mathcal M}_n \models T$ and ${\mathcal M}_n$ is a substructure
   of ${\mathcal M}_{n+1}$. Letting $M = \bigcup_n M_n$, we define an $\mathcal L$-structure
   ${\mathcal M}$ with underlying set $M$ in the natural way. Prove that ${\mathcal M} \models T$.

\item Recall that ${\mathcal M}$ is an {\em elementary substructure of $\mathcal N$} when
   ${\mathcal M}$ is a substructure of $\mathcal N$, and
  ${\mathcal M} \models \phi(\vec m) \iff {\mathcal N} \models \phi(\vec m)$ for all
  formulae $\phi(\vec x)$ and all tuples $\vec m$ of elements of $M$.  

  Let  $\langle {\mathcal M}_n : n \in {\mathbb N} \rangle$ be 
   a sequence of $\mathcal L$-structures, such that ${\mathcal M}_n$ is an elementary substructure
   of ${\mathcal M}_{n+1}$. Letting $M = \bigcup_n M_n$, we define an $\mathcal L$-structure
   ${\mathcal M}$ with underlying set $M$ in the natural way. Prove that ${\mathcal M}_n$ is an
   elementary substructure of $\mathcal M$ for all $n$.

    Hint: Prove by induction on $\phi$ that for all $n$ and all $\vec m$ from $M_n$, 
    ${\mathcal M}_n \models \phi(\vec m) \iff {\mathcal M} \models \phi(\vec m)$.

\item Let $\mathcal L$ be a countable FOL, let $\mathcal M$ be an infinite $\mathcal L$-structure  and let $Y$ be any set. 
      Prove that there exists ${\mathcal N}$ such that ${\mathcal M}$ is an elementary substructure of
      $\mathcal N$ and there is an injective function from $Y$ to $N$.

      Hint: Expand the language with constants $c_a$ for $a \in M$ and $d_y$ for $y \in Y$. 
      Show that the theory $S \cup T$ is consistent where $S$ is the complete diagram of $\mathcal M$
      and $T$ is the set of formulae $d_y \neq d_{y'}$ for $y \neq y'$.  






\end{enumerate}

\end{document} 



