\documentclass[12pt]{amsart}
\thispagestyle{empty}


\newcommand{\LL}{\mathcal{L}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\C}{\mathcal{C}}
\renewcommand{\a}{\bar{a}}
\renewcommand{\b}{\bar{b}}
\renewcommand{\c}{\bar{c}}
\newcommand{\x}{\bar{x}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\NN}{\mathcal{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Th}{\mathrm{Th}}
\newcommand{\Z}{\mathbb{Z}}


\begin{document}

\begin{center}
\begin{Large}
{\bf Math 2001 - Assignment 9}
\end{Large}
\bigskip

Due March 25, 2026
\end{center}

\thispagestyle{empty}

\bigskip

\begin{enumerate}
\item
 Give a quantifier-free formula which is equivalent to $\exists x\ ax^2+bx+c=0$ over
\begin{enumerate}
\item $(\mathbb{C},+,\cdot)$,
\item $(\R,+,\cdot)$.
\end{enumerate}
 Hint: Recall that on these  structures $-,0,1$ are definable. Use them if needed.


\item
 Let $\A\leq\B,\C$ be structures and let $h\colon\A\to\C$ be an embedding.
 Show that for every quantifier free formula $\phi(\x)$ and every $\a$ over $A$,
\[ \B\models\phi(\a) \text{ iff } \C\models\phi(h(\a)). \]

\item
 Let $\A,\B$ be $\LL$-structures. Show that if $\a\in A^n$ and $\b\in B^n$ satisfy the same
quantifier-free formulas, then the substructure $\langle\a\rangle$  of $\A$ generated by the entries
of $\a$ is isomorphic to the substructure $\langle\b\rangle$ of $\B$ generated by the entries of $\b$.



\item
 Let $s\colon\N\to\N,\ x\mapsto x+1$, be the successor function.
 Show that
\begin{enumerate}
\item
 the theory of $(\N,s)$ does not have quantifier elimination,
\item
 but the theory of $(\N,s,0)$ has quantifier elimination. 
\end{enumerate}
 
\end{enumerate}


%\begin{thebibliography}{1}
%\bibitem{En:MIL}
% Enderton. A Mathematical Introduction to Logic. Harcourt/Academic
%Press, 2nd edition, 2001. 

% \bibitem{Ma:MT}
%  Marker.
% \newblock Model Theory: An Introduction.
% \newblock Springer, 2002.

% \bibitem{TZ:CMT}
%  Tent, Ziegler. A Course in Model Theory. Lecture Notes in Logic, Cambridge, 2012. 
% \end{thebibliography}

\end{document}





%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
