\documentclass{amsart}

\usepackage{amssymb} 

\title{21-300 F15 HW 5}

\begin{document}



\maketitle

   A note on notation: We often write ``$\phi(y_1, \ldots y_n)$'' to 
   indicate that $\phi$ is a formula whose free variables have been listed
   without repetitions as $y_1, \ldots y_n$. 
   When $\mathcal M$ is a structure for the language of $\phi$, 
   and $a_1, \ldots a_n \in M$ then we often write
   ``$\mathcal M \models \phi(a_1, \ldots a_n)$'' as shorthand for 
   ``$\mathcal M \models \phi[y_1/c_{a_1}, \ldots y_n/c_{a_n}]$''.


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

\begin{enumerate}

\item    Let $T$ be a first-order theory in some language $\mathcal L$,
   let $\phi$ be  a formula with $x$ as its only free variable.
 Use the Completeness and Soundness
 theorems to show that
\begin{enumerate}
\item If $T \vdash \phi[x/c]$ where $c$ is a constant symbol not appearing in 
  $T$  or  $\phi$, then $T \vdash \forall x \; \phi$. 
\item If $T \cup \{ \phi[x/c] \} \vdash \psi$, where $c$ is a constant symbol not appearing
        in $T\cup \{\phi, \psi \}$, then
      $T \cup \{ \exists x \; \phi \} \vdash \psi$.
\end{enumerate}


\item Let $\mathcal M$ and  $\mathcal N$ be structures for some first-order language $\mathcal L$
   with underlying sets $M$ and $N$ respectively. A function $f: M \longrightarrow N$ is
   called a {\em homomorphism from $\mathcal M$ to $\mathcal N$} if
\begin{enumerate}
\item $f(c^{\mathcal M}) = c^{\mathcal N}$ for all constant symbols $c$.
\item For every relation symbol $R$  with arity $k$ and every
    $a_1, \ldots a_k \in M$,
 $R^{\mathcal M}(a_1, \ldots a_k) \implies R^{\mathcal N}( f(a_1), \ldots f(a_k) )$.
\item For every function symbol $G$ with arity $l$ and every 
    $a_1, \ldots a_l \in M$,
 $f(G^{\mathcal M}(a_1, \ldots a_l)) = G^{\mathcal N}(f(a_1), \ldots f(a_l))$.
\end{enumerate}

    Let $f$ be a  homomorphism from $\mathcal M$ to $\mathcal N$. For each closed term
    $t$ of the expanded language for $\mathcal M$,  let $\bar t$ be the closed  term of 
    the expanded language for $\mathcal N$ obtained by replacing each constant $c_a$ by
    the constant $c_{f(a)}$.

\begin{enumerate}

\item Prove that $f(t^{\mathcal M}) = {\bar t}^{\mathcal N}$ for each closed  term
    $t$ of the expanded language for $\mathcal M$. 

\item   Prove (by induction on $\phi$) that if $\phi(y_1, \ldots y_n)$ is
   a formula of $\mathcal L$ involving only the connectives $\wedge$ and $\vee$ and
   only the quantifier $\exists$, then for all $a_1 \ldots a_n \in M$
   $\mathcal M \models \phi(a_1, \ldots a_n) \implies {\mathcal N} \models  
   \phi(f(a_1), \ldots f(a_n))$.


   Hint: you should find the first part of the question helpful in doing the
   base case (when $\phi$ is atomic).

\end{enumerate}






\end{enumerate}

\end{document} 



