Math 776

Fall 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 Sep. 23rd:
    1. Tent-Ziegler Ex. 1.2.2
    2. Tent-Ziegler Ex. 1.3.3
    3. Tent-Zigler Ex. 2.2.3
    4. Tent-Zigler Ex. 2.2.4
    5. Tent-Zigler Ex. 2.2.5
  2. Due Oct 28:
    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. 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.
    5. 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).
    6. (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$).
  3. Due November 14th:
    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. Tent-Ziegler Exercise 3.2.3
    4. (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$.
    5. Tent-Ziegler Exercise 4.3.1
    6. Tent-Ziegler Exercise 4.3.4
    7. Tent-Ziegler Exercise 4.3.7

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.