Math 776

Spring 2022

Instructor: Uri Andrews
Email: (My last name)
Office: 723 Van Vleck Hall
Textbook: "A Course in Model Theory" by Tent and Ziegler
Back-up book: "A Shorter Model Theory" by Wilfred Hodges
Sometimes Tent and Ziegler can be a bit terse and Hodges is more verbose, so I recommend it as a secondary source.


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. 10th:
    1. Tent-Ziegler Ex. 2.1.2
    2. Tent-Zigler Ex. 2.2.3
    3. Tent-Zigler Ex. 2.2.4
    4. Tent-Zigler Ex. 2.2.5
  2. Due Feb 17:
    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.
  3. Due March 3rd:
    1. 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. The process of understanding the theory $T'$ by finding and using the theory $T$ is called "finding an elimination set", i.e., finding a minimal set of formulas that by naming them, you get QE.
    2. Tent-Ziegler Ex. 3.3.1 (Show the theory RG of the random graph has QE and is complete (ignore the model companion part for now).
    3. (From August 2012 qual) Let $T$ be a theory in the language of a single unary function $f$ stating that $f$ has no loops (i.e., for every $n\geq 1$ and every $x$, $f^ n (x)\neq x$) and for every $x$, there are infinitely many $y$ with $f(y)=x$. Show that $T$ has QE, is complete, and is not $\kappa$-categorical for any infinite cardinal $\kappa$. (i.e. for any infinite $\kappa$, there exists 2 non-isomorphic models of $T$ of size $\kappa$).
  4. Due March 24nd:
    1. Tent-Ziegler Exercise 3.2.1 (Note that problem 1 here should read "For any $T$-e.c. structure ...").
    2. Tent-Ziegler Exercise 3.2.2
    3. (From Jan 2012 Qual) Let $T$ be a complete theory in a countable language with infinite models. Show that $T$ has a countable model $\mathcal A$ such that for every tuple $\bar a$ from $A$, there is a formula $\psi(\bar x)$ with $\mathcal A \models \psi(\bar a)$ such that either (1) $\psi$ isolates a type over $T$ (i.e., $\psi$ is contained in exactly 1 $\vert \bar a \vert$-type) or (2) no isolated $\vert \bar a \vert$-type contains $\psi$.
    4. Tent-Ziegler Exercise 4.2.6
    5. Tent-Ziegler Exercise 4.3.5
    6. Tent-Ziegler Exercise 4.3.6
  5. Due April 12th:
    1. (Warm-up to the next problem) Suppose $\mathcal M$ is saturated and $f:A\rightarrow B$ is an elementary map from $A\subset M$ to $B\subset M$ where $A,B$ have cardinality strictly less than the cardinality of $M$. Show that there is an automorphism of $\mathcal M$ extending $f$. (i.e., saturated structures are ultrahomogeneous)
    2. (From Aug 2017 Qual) Let $\mathcal M$ be a saturated structure. Suppose $X$ is a definable (with parameters) subset of $M^n$. Suppose also that $X$ is fixed by every automorphism of $\mathcal M$. Show that $X$ is definable without parameters.
    3. Tent-Ziegler Exercise 4.3.7
    4. Tent-Ziegler Exercise 4.3.10
    5. Tent-Ziegler Exercise 4.5.2
    6. Tent-Ziegler Exercise 4.5.3
    7. (From Aug 2011 Qual) Suppose $T$ is a complete first order theory in a countable language. Show that if $T$ has a countable saturated model, then $T$ has a countable prime model.

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.