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}{⪯}_k\mathcal{B}$ if whenever $\psi (\overline{x})$ is an ${\mathrm{\exists }}_k$ formula (i.e. $\mathrm{\exists }\mathrm{\forall }\mathrm{\exists }\dots$ for length $k$) and $\overline{a}\in A$, then $\mathcal{A}\models \psi (\overline{a})$ if and only if $\mathcal{B}\models \psi (\overline{a})$. Let $L$ be a language, $T$ an theory in $L$, $n$ an integer $\ge 2$, and $\varphi (\overline{x})$ an $L$-formula. Show that the following are equivalent:
      1. $\varphi$ is equivalent modulo $T$ to a ${\mathrm{\forall }}_n$ formula (defined like ${\mathrm{\exists }}_n$, but it starts with a $\mathrm{\forall }$).
      2. If $\mathcal{A}$ and $\mathcal{B}$ are models of $T$ such that $\mathcal{A}{⪯}_{n-1}\mathcal{B}$, and $\overline{a}$ is a tuple from $A$ so that $\mathcal{B}\models \varphi (\overline{a})$, then $\mathcal{A}\models \varphi (\overline{a})$.
      3. $\varphi$ is preserved in unions of ${⪯}_{n-2}$-chains of models of $T$ (i.e., if ${\mathcal{A}}_i$ for $i\in \omega$ is a ${⪯}_{n-2}$-chain of models of $T$ and $\mathcal{B}$, the union of the chain, is also a model of $T$, and $\overline{a}\in A_0$ is so that ${\mathcal{A}}_i\models \varphi (\overline{a})$ for each $i$, then $\mathcal{B}\models \varphi (\overline{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 $\mathrm{\forall }x\mathrm{\exists }\overline{y}\varphi (x,\overline{y})$ (note that $x$ is a single variable, not a tuple) with $\varphi$ 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}⪯\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{⪯}_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 $\mathrm{\exists }\mathrm{\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^{\prime }$ in language $<$ which says that $<$ is a discrete linear order is also complete. The process of understanding the theory $T^{\prime }$ 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\ge 1$ and every $x$, $f^n(x)\ne 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 $\overline{a}$ from $A$, there is a formula $\psi (\overline{x})$ with $\mathcal{A}\models \psi (\overline{a})$ such that either (1) $\psi$ isolates a type over $T$ (i.e., $\psi$ is contained in exactly 1 $|\overline{a}|$-type) or (2) no isolated $|\overline{a}|$-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.