Homeworks:

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:

Links

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