Math 776
Spring 2015

Instructor: Uri Andrews
Email: (My last name)
Office: 513 Van Vleck Hall
Office Hours: W. 2:15-3:15
Class Room: B131


Homeworks will be regularly assigned and posted here with due-dates. If you do not yet have the textbook and need to know what the problems are, please drop me an e-mail.
  1. Due Feb. 6th:
    1. Construct two structures $\mathcal A$ and $\mathcal B$ so that $\mathcal A \equiv \mathcal B$ (i.e. they are elementarily equivalent), but there is no elementary map from $\mathcal A$ to $\mathcal B$ and there is no elementary map from $\mathcal B$ to $\mathcal A$.
    2. Construct two structure $\mathcal A$ and $\mathcal B$ so that there is an elementary embedding $h:\mathcal A\rightarrow \mathcal B$ and an elementary embedding $g:\mathcal B\rightarrow\mathcal A$, but $\mathcal A\not\cong \mathcal B$.
    3. Let $\mathcal A$ be an $\mathcal L$-structure and $\phi(x,y)$ be an $\mathcal L$-formula. Suppose $X\subseteq A$ is an infinite set so that $\{(x,y)\in X\mid \mathcal A\models \phi(x,y)\}$ gives a linear ordering of $X$. Let $\tau$ be any linear order. Show that there is a structure $\mathcal B$ and a set $Y\subseteq B$ so that $\mathcal A\preceq \mathcal B$ and $\{(x,y)\in Y\mid \mathcal B \models \phi(x,y)\}$ gives a linear ordering on $Y$ isomorphic to $\tau$.
    4. We say that a set $A\subseteq \omega$ is a spectrum if there is a language $\mathcal{L}$ and a sentence $\phi$ so that $n\in A$ if and only if there is a model of $\phi$ of size $n$ (we call this $A$ the spectrum of $\phi$). The spectrum problem (still open and apparently quite hard) is to characterize which subsets of $\omega$ are spectra. In particular, it is no known if the complement of a spectrum is a spectrum. The following are easier:
      1. Show that if $X$ is any finite or co-finite subset of $\omega$, then $X$ is a spectrum.
      2. Show that the set of even numbers is a spectrum.
      3. Show that the set of odd numbers is a spectrum.
      4. Show that for any $n,m\in \omega$, the set of integers congruent to $n$ mod $m$ is a spectrum.
      5. Show that the set of powers of primes is a spectrum.
      6. Show that the set of powers of 17 is a spectrum.
      7. Show that if $X$ and $Y$ are spectra, then $X\cup Y$ is a spectrum and $X\cap Y$ is a spectrum.
    5. Let $\phi$ be a sentence so that the spectrum of $\phi$ is infinite. Show that $\phi$ has an infinite model. If $\phi$ has an infinite model, must the spectrum of $\phi$ be infinite?
  2. Due Feb 27:
    1. We say that $\mathcal A \preceq_k \mathcal B$ if whenever $\psi(\bar{x})$ is an $\exists_k$ formula (i.e. $\exists\forall\exists\ldots $ for length $k$) and $\bar{a}\in A$, then $\mathcal A \models \psi(\bar{a})$ if and only if $\mathcal B \models \psi(\bar{a})$. Let $L$ be a language, $T$ an theory in $L$, $n$ an integer $\geq 2$, and $\phi(\bar{x})$ an $L$-formula. Show that the following are equivalent:
      1. $\phi$ is equivalent modulo $T$ to a $\forall_n$ formula (defined like $\exists_n$, but it starts with a $\forall$).
      2. If $\mathcal A$ and $\mathcal B$ are models of $T$ such that $\mathcal{A} \preceq_{n-1} \mathcal{B}$, and $\bar{a}$ is a tuple from $A$ so that $\mathcal{B}\models \phi(\bar{a})$, then $\mathcal A \models \phi(\bar{a})$.
      3. $\phi$ is preserved in unions of $\preceq_{n-2}$-chains of models of $T$ (i.e., if $\mathcal{A}_i$ for $i\in \omega$ is a $\preceq_{n-2}$-chain of models of $T$ and $\mathcal{B}$, the union of the chain, is also a model of $T$, and $\bar{a}\in A_0$ is so that $\mathcal{A}_i\models \phi(\bar{a})$ for each $i$, then $\mathcal{B}\models \phi(\bar{a})$ as well).
    2. Let $L$ be a language and $T$ a theory in $L$. Show that the following are equivalent:
      1. $T$ is equivalent to a set of sentences of $L$ of the form $\forall x \exists \bar{y} \phi(x,\bar{y})$ (note that $x$ is a single variable, not a tuple) with $\phi$ quantifier-free.
      2. If $\mathcal A$ is an $L$-structure and for every element $a\in A$ there is a substructure of $\mathcal A$ which contains $a$ and is a model of $T$, then $\mathcal A \models T$
    3. Let $L$ be a language and $T$ a theory in $L$. Show that the following are equivalent:
      1. Whenever $\mathcal A$ and $\mathcal B$ are models of $T$ with $\mathcal A \preceq \mathcal B$, and $\mathcal A\subseteq \mathcal C \subseteq \mathcal B$, then $\mathcal C \models T$.
      2. Whenever $\mathcal A$ and $\mathcal B$ are models of $T$ with $A\preceq_2 \mathcal B$ and $\mathcal A \subseteq \mathcal C\subseteq \mathcal B$, then $\mathcal C\models T$.
      3. $T$ is equivalent to a set of $\exists\forall$ sentences.
    4. Let $L$ be the language $\{<\}\cup \{R_i\mid i\in \omega\}$ where $<$ and the $R_i$ are binary. Let $T$ be the theory that says $<$ is a linear order which is discrete (i.e. every element has an immediate predecessor and an immediate successor). Further, $T$ says that $R_i(x,y)$ holds if and only if $y>x$ and there are exactly $i$ elements in the interval between $x$ and $y$. Show that $T$ has quantifier elimination and is complete. Use this to conclude that the theory $T'$ in language $\{<\}$ which says that $<$ is a discrete linear order is also complete.
    5. Show that the theory of the reals $\mathcal R=(\mathbb{R}, +, -, \cdot , 0, 1)$ is model complete but does not have quantifier elimination. Hint: We will show in class that the theory of $(\mathbb{R}, +, -, \cdot , 0, 1, \leq)$ has quantifier elimination. Use this result.

Source of Problems:

A good source of problems can be found in the "M" section of old qualifying exams. They can all be found here. If you are a math graduate student, do consider taking 770 and the logic qual. After this course, you're most of the way there!


  1. Andres Caicedo's notes on proving compactness via the ultraproduct construction.