\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 11}
\end{Large}
\bigskip

Due April 8, 2026
\end{center}

\thispagestyle{empty}

\bigskip

\begin{enumerate}
\item
 Let $T$ be a completion of the theory of fields with an infinite model.
 Show that $T$ is not $\omega$-categorical. 

\smallskip

\noindent Hint: Use the Ryll-Nardzewski Theorem and show that the formulas $y=x^n$ for $n\in\N$ are inequivalent modulo $T$.
 
\item
 Characterize $\omega$-categorical vector spaces.

\smallskip

\noindent Hint: Consider a countable $\F$-vector space $V$ and distinguish whether the field $\F$ is finite/countable.

 
\item Show that there exists a countable bipartite graph that embeds all countable bipartite graphs.

\smallskip

\noindent Hint: The vertex set of a bipartite graph splits into two disjoint subsets $U_!$ and $U_2$ such that
 there are no edges between any two vertices in $U_i$ for any $i\in \{1,2\}$.

 Bipartite graphs can be considered as relational structures over the language $\LL = \{E,U\}$
 where $E$ is the binary edge relation and $U$ is an equivalence relation with at most two classes (namely, $U_1,U_2$)
 such that
\[ \forall x,y\  U(x,y) \rightarrow \neg E(x,y). \]
Argue that the class $K$ of finite bipartite graphs is Fra{\"i}ss\'e (no need to prove the properties in detail).

 Show that the Fra{\"i}ss\'e limit of $K$ (the generic bipartite graph) embeds all countable bipartite graphs. 
 
  
\item
 Show that if $\A$ is $\omega$-categorical, then the expansion $(\A,b)$ of $\A$ by a constant $b$ is also
 $\omega$-categorical.


%\item \cite[Ex 2.5.28c,d]{Ma:MT}
%  Generalize the example from class to show that there exist complete theories
%  $T_n$ with exactly $n\geq 4$ countable models. 
\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: 
