Exercises

Thanks to Paolo Marimon for kindly typing the exercises.

Model Theory and CombinatoricsArtëm Chernikov

Definition 1. Let $M_i$ for $i\in I$ a collection of $\mathcal{L}$-structures, $A_i\subseteq M_i$ be finite, and $\mathcal{U}$ be a non-principal ultrafilter on $I$. Let $M=\prod_\mathcal{U} M_i$. For $b\in M$ and $\phi(x, y)$ an $\mathcal{L}$-formula, we define the pseudofinite measure of $\phi(x, b)$ to be given by $\mu(\phi(x, b))=\lim_\mathcal{U} \frac{|\phi(A_i, b_i)|}{|A_i|}.$

Exercise 2. Prove that this definition is equivalent to defining the pseudofinite measure of $\phi(x, b)$ as $\mathrm{st}\left(\left(\frac{|\phi(A_i, b_i)|}{|A_i|} \middle | i\in I\right)\middle/\mathcal{U}\right)$

Definition 3. Let $\mathcal{M}\succeq(\mathbb{R}, +, \cdot, \dots )$ be o-minimal. Let $\lambda$ be the Lebsegue measure on $[0,1]$ in $\mathbb{R}$. Define $\mu(\phi(x, b)):=\lambda(\phi(M, b)\cap [0, 1]).$

Exercise 4. Show that by o-minimality this definition gives a Keisler measure.

Exercise 5. Let $\mathfrak{M}_x(A)$ be the space of Keisler measures over $A$. Show that $\mathfrak{M}_x(A)$ is a closed subspace of $[0, 1]^{\mathcal{L}(A)}$. Further show that $S_x(A)$ is closed in $\mathfrak{M}_x(A)$.

Definition 6. Let $\mu\in\mathfrak{M}_x(\mathbb{M})$ and $\nu\in\mathfrak{M}_y(\mathbb{M})$. We form the product $\mu \otimes \nu\in\mathfrak{M}_{xy}(\mathbb{M})$ via $\mu \otimes \nu|_A(\phi(x,y, b))=\int_{p\in S_y(Ab)}\mu(\phi(x, p, b)) \mathrm{d}\nu.$

Exercise 7. Show that for types (viewed as $\{0,1\}$-measures), this corresponds to the standard definition of product, where for global types $p\in S_x(\mathbb{M}), q\in S_y(\mathbb{M})$, $p\otimes q |_A=\{\mathrm{tp}(a, b)|b\vDash q|_A, a\vDash p|_{Ab}\}.$

Theorem 8 (Szemeredi Regularity Lemma). Let $\mu, \nu$ be definable and commuting measures. Let $E(x, y)$ be a definable binary relation. Then, for every $\epsilon>0$ there are partitions $V_1, \dots, V_n$ of $\mathbb{M}^{|x|}$ and $W_1, \dots, W_n$ of $\mathbb{M}^{|y|}$ and $\Sigma\subseteq [n]^2$ so that

1. $\mu\otimes \nu(\bigcup_{(i,j)\in\Sigma} V_i\times W_j)<\epsilon$;
2. For any $(i,j)\not\in \Sigma$ there is $d_{ij}\in[0,1]$ such that for every definable $A\subseteq V_i$, $B\subseteq W_j$, $\mu\otimes\nu(E\cap A\times B)\approx^\epsilon d_{ij}\mu(A)\nu(B).$

Exercise 9. Show that by compactness $n$ can be chosen to depend only on $\epsilon$.

Exercise 10. Show that bad pairs in the theorems above might be unavoidable. To do so consider the half-graph where $(i,j)\in E$ if and only if $i<j$.

Exercise 11. Show that a theory is NIP if and only if every formula has finite VC-dimension.

Exercise 12. Show that NIP is preserved under Boolean combinations.

Theorem 13. If $\phi(x, y)$ is a stable formula and $\mu(x)$ is a Keisler measure, then there exist $(p_i|i\in\omega)$ and weights $\alpha_i\in[0,1]$ such that $\sum_{i} \alpha_i=1$ such that for any $b\in\mathbb{M}^{|y|}$, $\mu(\phi(x, b))=\left(\sum_{i\in\omega} \alpha_i p_i\right)(\phi(x, b)).$

Exercise 14. Prove the theorem above (the proof uses Shelah’s $2$-rank).

Theorem 15. Let $\delta$ be the coarse pseudofinite dimension associated with the pseudofinite set $A$.

1. $\delta(A)=1$.
2. $\delta(B_1\cup B_2)=\mathrm{max}\{\delta(B_1), \delta(B_2)\}$ for pseudofinite $B_1, B_2$.
3. (Subadditivity) Let $Y\subseteq A\times A^m$ and $Z\subseteq A$ be pseudofinite with $\delta(Z)=\alpha$. Suppose that for all pairwise distinct $a_1, \dots, a_m\in Z$ we have that $\delta(\{x\in A| (x, a_1, \dots, a_m)\in Y\})\leq \beta.$ Then, $\delta(\{x\in A| \text{ there are } z_1, \dots, z_m \in Z \text{ distict and with } (x, z_1, \dots, z_m)\in Y\})\leq m\alpha+\beta$

Exercise 16. Prove the above property of coarse pseudofinite dimension.

Differential equations and functional transcendenceJames Freitag

Let $(\mathcal{U},\partial)$ denote a monster model of $\mathrm{DCF}_{0}$, fixed throughout. By $K \langle a\rangle$, we mean the differential field extension of $K$ generated by $a$. Often it is convenient to simplify the notation of derivations, so we will write $x’$ instead of $\partial(x)$, $x^{\prime\prime}$ instead of $\partial(\partial(x))$, etc.

1. Forking in Differentially Closed Fields

When working in differentially closed fields of characteristic zero, we can witness forking extensions of types in the following way. Let $p$ be a type over $A$ (a small subset of $\mathcal{U}$), let $B$ be a (small) set containing $A$, and let $q$ be a type over $B$ extending $p$. Then $q$ is a forking extension of $p$ if and only if for every $a\in\mathcal{U}$ such that $a\models q$, we have that $$\mathrm{tr.deg.}_{\mathbb{Q}\langle A\rangle}\mathbb{Q}\langle A, a\rangle > \mathrm{tr.deg.}_{\mathbb{Q}\langle B\rangle}\mathbb{Q}\langle B, a\rangle.$$

2. Lascar Rank

Lascar rank is the foundation rank for the forking relation. This is most naturally defined as an ordinal-valued rank on types Let $p \in S(A)$ be a complete type and $\alpha \in \text{On}$. We define $\operatorname{RU}(p) \geq \alpha$ by induction on $\alpha$.

• $\operatorname{RU}(p) \geq 0$ for any type $p$.
• $\operatorname{RU}(p) \geq \alpha+1$ if there is a forking extension $q \in S(B)$ of $p$ for $B \supseteq A$ such that $\operatorname{RU}(q) \geq \alpha$.
• When $\beta$ is a limit, $\operatorname{RU}(p) \geq \beta$ if $\operatorname{RU}(p) \geq \alpha$ for all $\alpha < \beta$.

When $X$ is a $K$-definable set, $\operatorname{RU}(X)$ is defined to be the supremum of the Lascar ranks of the types $p$ in the set $X$. When $X$ is an irreducible differential variety, recall that we had a notion of a generic point in the Kolchin topology on $X$ over $K$. The generic points are not necessarily of maximal Lascar rank (and vice versa).

Exercise 2.1. Let $p$ be a 1-type over $A$. What can you say about $p$ if $\operatorname{RU}(p) =0$?

In general, let $p$ be a type over $A$. If $a\models p$ and $a$ is differentially algebraic over $\mathbb{Q}\langle A\rangle$, then $\mathrm{RU}(p) \leq \mathrm{tr.deg.}_{\mathbb{Q}\langle A\rangle}\mathbb{Q}\langle A, a\rangle$.

Sometimes we write $\operatorname{RU}(a/A)$ for the Lascar rank of the type of $a$ over $A$.

Exercise 2.2. Let $C = \ker\partial$. Suppose that $c\in C$ is transcendental over $\mathbb{Q}$. Show that $\operatorname{RU}(c / \emptyset) = 1$.

Exercise 2.3. Show that if there is a $K$-definable bijection between $X$ and $Y$, then $\operatorname{RU} (X) = \operatorname{RU} (Y)$.

Now, let $a, b$ be tuples $\mathcal U$ and let $K$ be a small differential subfield. One reason that Lascar rank is so nice to work with is that it obeys a strong form of the fiber-dimension theorem, which we refer to as the Lascar inequalities: $$\operatorname{RU} (a/ K\langle b \rangle ) + \operatorname{RU} (b/ K ) \leq \operatorname{RU} ((a, b)/ K ) \leq \operatorname{RU} (a/ K \langle b \rangle ) \oplus \operatorname{RU} (b/ K )$$ Here $+$ denotes ordinal addition, while $\oplus$ denotes the Cantor sum (adding the ordinals like polynomials) – for instance, $2+ \omega = \omega$, while $2 \oplus \omega = \omega +2$.

2.1 Differentially transcendental elements

An element $z\in\mathcal{U}$ is said to be differentially transcendental over $A$ if $$\mathrm{tr.deg.}_{\mathbb{Q}\langle A\rangle}\mathbb{Q}\langle A\rangle\langle z\rangle$$ is infinite. In other words, for every $n\in\mathbb{N}$, if $P(X_{1},\ldots,X_{n+1})$ is a non-constant polynomial with coefficients in $\mathbb{Q}\langle A\rangle$, then $P(z,z’,\ldots,z^{(n)})\neq 0$.

Exercise 2.4. Let $p$ be the 1-type of a differentially transcendental element over $A$. Show that $\operatorname{RU}(p)=\omega$.

Exercise 2.5. Let $L$ be an $A$-definable line in $\mathcal U^{2}$. Show that $\operatorname{RU}(L) = \omega$.

2.2 The secant variety

Given a definable set $X\subset\mathcal{U}^{n}$ we define the secant variety of $X$ (denoted $\mathrm{Sec}(X)$) to be the union of all the lines that are defined by any pair of distinct points in $X$. Observe that $\mathrm{Sec}(X)$ is again a definable set.

Exercise 2.6. Give an upper bound for the rank of $\mathrm{Sec}(X)$ in terms of the rank of $X$. (Use Lascar’s inequalities).

Exercise 2.7. Suppose $V\subset \mathcal{U}^{n}$ is a definable set of finite rank. Show that there is a definable injection $V\hookrightarrow \mathcal{U}$.

3. Exercises leading to many open problems in algebraic differential equations

Consider the set $X\subset\mathcal{U}^{2}$ defined by $X_{1}^{\prime\prime}+X_{1} = X_{2}^{\prime\prime} + 3X_{2}$. As an introduction to the exercises that follow, we will begin by showing that $\operatorname{RU}(X)=\omega$. For this first observe that if we consider the following substitution $Z_{1} = X_{1} – X_{2}$, then the above equation becomes $Z_{1}^{\prime\prime}+Z_{1} = 2X_{2}$. Even more, we have produced a definable bijection between the solutions of $X_{1}^{\prime\prime}+X_{1} = X_{2}^{\prime\prime} + 3X_{2}$ and the solutions of $Z_{1}^{\prime\prime}+Z_{1} = 2X_{2}$, so both equations can be thought of as defining $X$. By taking the projection to the $Z_{1}$ coordinate, this last equation is in definable bijection with $\mathcal{U}$, so by the exercises above we can conclude that $\operatorname{RU}(X)=\omega$.

Exercise 3.1. Show that the subset of $\mathcal{U}^{2}$ defined by $X_{1}^{\prime\prime} + X_{1} = X_{2}’ + 3X_{2}$ has rank $\omega$.

Over the past several decades, numerous results in algebraic differential equations have relied on showing that certain types are minimal. Lets see an example of why the degree of nonminimality and knowledge about how Lascar rank works even for infinite rank types are useful tools for proving that certain types have rank one.

Exercise 3.2. Consider the equation $y^{\prime\prime}+y^2 = \alpha$ where $\alpha$ is differentially transcendental over $\mathbb{Q}$. Suppose that you know that the degree of nonminimality is at most two for this equation (this is true). Then, assuming that the generic point of the variety is not minimal, we would have that there is a nonalgebraic forking extension of $K \langle \alpha , y_1 , y_2 \rangle$, the differential field generated by two generic solutions to the equation. Convince yourself that this is equivalent to there being a $\mathbb Q \langle a \rangle$-differential subvariety of \begin{eqnarray*} y_1^{\prime\prime}+y_1^2 & = &\alpha \\ y_2^{\prime\prime}+y_2^2 &= & \alpha \\ y_3^{\prime\prime}+y_3^2 &= & \alpha \end{eqnarray*} whose generic solution generates a differential field of transcendence degree $5$ over $K \langle a \rangle$.

Exercise 3.3. Since $\alpha$ is differentially trascendental, show that the existence of a $\mathbb Q \langle a \rangle$-differential subvariety of \begin{eqnarray*} y_1^{\prime\prime}+y_1^2 & = &\alpha \\ y_2^{\prime\prime}+y_2^2 &= & \alpha \\ y_3^{\prime\prime}+y_3^2 &= & \alpha \end{eqnarray*} whose generic solution generates a differential field of transcendence degree $5$ over $K \langle a \rangle$ implies there is a $\mathbb Q$ differential subvariety of $$\label{underdet} \tag{3.1} \begin{array}{ccc} y_1^{\prime\prime}+y_1^2 & = & z \\ y_2^{\prime\prime}+y_2^2 &= & z \\ y_3^{\prime\prime}+y_3^2 &= & z \end{array}$$ which is proper and infinite Lascar rank. Give an upper bound on the Lascar rank of the system \ref{underdet} using the Lascar inequalities and our characterization of forking.

Exercise 3.4. The system \ref{underdet} is in definable bijection with the system: $$\label{underdet1} \tag{3.2} \begin{array}{ccc} y_1^{\prime\prime}+y_1^2 & = & y_2^{\prime\prime}+y_2^2 \\ y_2^{\prime\prime}+y_2^2 &= & y_3^{\prime\prime}+y_3^2 \\ \end{array}$$ The differential tangent space of a generic point $a$ on a differential variety $V$, denoted $T^\delta _a (V)$ is known to have the same Kolchin polynomial as $V$. So, one could show that system \ref{underdet1} has no proper subvarieties of infinite rank if one can show that the differential tangent space of the system of a generic solution $(a_1, a_2,a_3)$ has no infinite rank differential subvarieties. The system giving the differential tangent space of at $(a_1, a_2, a_3)$ is: $$\label{underdet2} \tag{3.3} \begin{array}{ccc} z_1^{\prime\prime}+2a_1 z_1 & = & z_2^{\prime\prime}+2a_2 z_2 \\ z_2^{\prime\prime}+2a_2 z_2 &= & z_3^{\prime\prime}+2a_3 z_3 \\ \end{array}$$ Can you use the kinds of transformations done above to show that the system \ref{underdet2} is in bijection with $\mathbb A^1$? Then by our sequence of reasoning, we would have proved that the original order two equation has Lascar rank $1$. This technique potentially works with a wide variety of differential equations.

4. An example

We don’t at the moment know an example of a theory with a type whose degree of nonminimality is larger than $2$. As outlined in lecture, one reasonable way to attempt to build one is the following:

1. design a theory with “many” orthogonality classes of nonlocally modular strongly minimal sets which are orthogonal to any type over the empty set.
2. Set things up so that for each $n$, there is at least one orthogonality class which needs $n$ many parameters to define any set to which it is nonorthogonal.

Exercise 4.1. Carry out the above construction.

O-minimality and Number TheoryGareth Jones

Exercise 1. Let $X\subseteq \mathbb{R}^n$ be definable in an o-minimal expansion of the reals $\widetilde{\mathbb{R}}=(\overline{\mathbb{R}}, \dots)$. Suppose that $X$ is countable. Show that $X$ is finite.

Exercise 2.

1. Write down a function $f:\mathbb{R}\to\mathbb{R}$ definable in $\mathbb{R}_{\mathrm{exp}}$ which is transcendental such that $\text{Graph}f \cap \mathbb{Q}^2 \text{ is infinite.}$
2. Show that there is an entire transcendental $f$ such that if $\alpha\in\overline{\mathbb{Q}}$, then $f(\alpha)\in\mathbb{Q}(\alpha)$.

Exercise 3. Fix $d$ and $H$. Show that the set$\left\{\alpha\in\overline{\mathbb{Q}} \middle| H(\alpha)\leq H, [\mathbb{Q}(\alpha): \mathbb{Q}]\leq d\right\}$is finite. Find upper bounds on its cardinality.

Suppose $\alpha$ is in this set. Show that $|\alpha|\leq H^d$.

Definition 4. For $X\subseteq \mathbb{R}^n$, we write$X(d, H)=X\cap\left\{\alpha\in\mathbb{Q}^n \middle| H(\alpha)\leq H, [\mathbb{Q}(\alpha): \mathbb{Q}]\leq d\right\}$

Exercise 5.

1. Suppose $\mathcal{U}\subseteq \mathbb{R}^n$ is open. What is $\mathcal{U}^{\mathrm{trans}}$?
2. Show that there is a transcendental analytic $f:(0,1)^2\to\mathbb{R}$ definable in $\mathbb{R}_{\mathrm{exp}}$ such that there is a $\delta>0$ and arbitrarily large $H$ such that $\#\mathrm{Graph}f(1, H)\geq H^\delta.$
3. Show that it looks unlikely that the algebraic part of a definable set is necessarily definable.
4. Suppose that $X$ is a definable curve. Is $X^\mathrm{alg}$ definable? (I don’t know!).
5. Show that the answer is yes assuming analytic cell decomposition.

For $\alpha\in\mathbb{N}^k$, $\alpha=(\alpha_1, \dots, \alpha_k)$ we write $D^\alpha f$ for the $\alpha$th derivative$\frac{\partial^{|\alpha|}}{\partial x_1^{\alpha_1}, \dots, \partial x_k^{\alpha_k}}f,$where $|\alpha|=\alpha_1+\cdots+\alpha_k$.

Theorem 6 ($C^r$-parametrization). Let $X\subseteq (0,1)^n$ be definable with dimension $k$. Let $r\in\mathbb{N}$. Then, there are $C^r$-maps $\phi_1, \dots, \phi_l:(0,1)^k\to X$ such that

1. $\bigcup \mathrm{Im}\phi_i=X$;
2. $||\phi_i||_r\leq 1$.

Recall that we write,$||\phi_i||_r=\max_{\substack{\|\alpha|\leq r\\ j=1, \dots, n}}\sup_{x\in(0,1)^k}|D^\alpha\phi_{i,j}(x)|,$where $\phi_{i,j}$ is the $j$th coordinate function for $\phi_i$.

Exercise 7. Use cell decomposition to prove the $C^0$-parametrization theorem.

Proposition 8 (Habegger). Suppose $k,n, d, D$ are positive integers with $k<n$, $D\geq (d+1)n$. Then, there is a positive integer $r$ and positive reals $c, \epsilon$ with the following property. Suppose $\phi:(0,1)^k\to (0,1)^n$ is $C^r$ with $||\phi||_r\leq 1$. Put $X=\mathrm{Im}\phi$. Then, for $H\geq 1$, the set $X(d, H)$ is contained in the union of at most $cH^\epsilon$ algebraic hypersurfaces of degree at most $D$ (i.e. zero sets of $P\in\mathbb{R}[X_1, \dots, X_n]$ of total degree $\leq D$).

Moreover, as $D\to\infty$, we have $\epsilon\to 0$.

Exercise 9. Use the Theorem and Proposition to prove the Pila-Wilkie Theorem in the case $n=2$. You might find the following useful:

If $\alpha\in\overline{\mathbb{Q}}$, then $H(\alpha)=H(-\alpha)$, and if $\alpha\neq 0$, then $H(\alpha)=H(\alpha^{-1})$.

O-minimality and tame topologiesAssaf Hasson

Exercise 1. Let $\mathcal{M}$ be an o-minimal structure and $f:M\to M$ a definable function.

1. Show that if $f$ is locally increasing at every point, then it is increasing. Reminder: $f$ is locally increasing at $a$ if there is an interval $I\ni a$ such that $f|_I$ is increasing.
2. Consider the following sets:
$U_+:=\left\{ x\in M \middle| \exists \epsilon (f(x)=\min\{f(y)|y\in[x, \epsilon)\})\right\}$
$U_-:=\left\{ x\in M \middle| \exists \epsilon (f(x)=\max\{f(y)|y\in[x, \epsilon)\})\right\}$
Prove that $U_+\cup U_-=M$.
3. Without loss of generality, there is an interval $[a,b]\subseteq U_+$ (Why?). Define $g:[a,b]\to M$ by
$g(x)=\inf\{y|y>x\wedge f(x)>f(y)\},$
setting $\inf(\emptyset)=-\infty.$
Show that $g$ is locally constant or locally decreasing at every point.
4. Define
$\epsilon(x):=\inf\{g(z)|x<z<g(x)\}.$
Show that there exists $x\in[a,b]$ such that $x \lneq \epsilon(x)$. Conclude that $f$ is strictly monotone on $(x, \epsilon(x))$.
5. Prove that if $f|_{(x, \epsilon(x))}$ is bounded, then $\lim_{t\to\epsilon(X)} f(t)$ exists.
6. Show that there are $-\infty=a_0<a_1<\dots<a_{n+1}=\infty$ such that $f|_{(a_i, a_{i+1})}$ is strictly monotone, or constant and continuous.

Exercise 2. Show that a cell is definably connected. Show that if the universe of $\mathcal{M}$ is $\mathbb{R}$, then cells are connected. Deduce that in $\mathcal{M}$ definable connectedness implies connectedness.

Exercise 3.

1. Show that $\mathrm{acl}$ satisfies exchange in o-minimal structures, i.e$.$, for any set of parameters $A$ if $a \in \textnormal{acl}(Ab) \setminus \textnormal{acl}(A)$ then $b \in \textnormal{acl}(Aa)$.
2. Show that in an $|A|$-saturated model an $A$-definable set $S$ contains a point $b$ such that $\mathrm{dim}_{\mathrm{acl}}(b/A)=k$ if and only if there exists a projection $\pi:S\to M^k$ such that $\pi(S)$ contains an open set.

NSOP1 and simplicityItay Kaplan

The formula $\phi(x,y)$ has the $k$-tree property if there are $(a_s|s\in\omega^{<\omega})$ such that:

1. Each path is consistent: $\left\{\phi(x, a_{\eta|_n})\middle| n<\omega\right\} \text{ is consistent for each } \eta:\omega\to\omega.$
2. For all $s\in\omega^{<\omega}$ the set of successors of $s$ is $k$-inconsistent: $\text{For all } s\in\omega^{<\omega}, \left\{\phi(x, a_{s\smallfrown \langle i\rangle}) \middle| i<\omega \right\} \text{ is } k\text{-inconsistent}.$

We say that $\phi(x, y)$ has the tree property $TP$ if it has the $k$-tree property for some $k<\omega$.

Exercise 1. Show that if $T$ has the tree property for some $k$ then it has the tree property for $k=2$.

An equivalent definition of stability for a formula is not having the binary tree property. The formula $\phi(x,y)$ has the binary tree property if there is $\langle b_s|s\in 2^{<\omega}\rangle$ such that for every $\eta:\omega\to 2$,$\left\{\phi(x, b_{\eta|_n})^{\eta(n)}\middle|n<\omega\right\} \text{ is consistent },$where $\phi^0=\neg\phi$ and $\phi^1=\phi$.

Exercise 2. Show that if $\phi$ has the tree property ($TP$) then it has the binary tree property ($BTP$). This yields an alternative proof that stable theories are simple.

We say that $I$ has the modelling property if given $(a_i|i\in I)$, there is $(b_i|i\in I)$ $I$-indiscernible based on $(a_i|i\in I)$. That is:For any finite set of $\mathcal{L}$-formulas $\Delta$ and $\overline{t}:=t_0, \dots, t_{n-1}$ from $I$ there is $\overline{s}:=s_0, \dots s_{n-1}$ from $I$ such that $\overline{s}\equiv^{\mathrm{qf}}_{\mathcal{L}’}\overline{t}$ and $\mathrm{tp}_\Delta(a_{\overline{s}})=\mathrm{tp}_\Delta(b_{\overline{t}})$.

Exercise 3. Show that if we change the definition of modelling property to say that $\Delta$ is all $\mathcal{L}$-formulas, then even $I=(\mathbb{N}, <)$ doesn’t have the modelling property.

Exercise 4. Prove that if $\phi$ has $TP$, then there is some $A$ and $p\in S(A)$ such that $p$ divides over any $B\subseteq A$ of size $|B|\leq |T|$. Hence, if $T$ is not simple, local character fails.

Exercise 5. For any theory, prove extension for non-forking independence: for $b\indep{A}{}C$ and any $d$, there is $b’\equiv_{AC} b$ such that $b’\indep{A}{}Cd$.

Exercise 6. Suppose that $T$ is not simple (so some formula has the tree property). Then, there is a formula $\phi(x, y)$ with $TP$ such that $x$ is a $1$-tuple.

Exercise 7(Probably true… open question). Show that if $I$ has the modelling property for all simple theories, then it has the modelling properties for all theories.

Exercise 1. Prove that the following theories are complete and have quantifier elimination:

1. The theory of the Random graph;
2. Let $\mathcal{L}=\{P_n\}_{n\in\mathbb{N}}$ be a language with countably many unary predicates. Let $T$ be axiomatised by the formulas say that for $n_1, \dots, n_k, m_1, \dots, m_r\in\mathbb{N}$, there are infinitely many elements such that $P_{n_1}, \dots, P_{n_k}$ holds of them and $P_{m_1}, \dots, P_{m_r}$ do not;
3. Let $\mathcal{L}=\{E_n\}_{n\in\mathbb{N}}$, be a language with countably many binary relations. Let $T$ say that the $E_i$ are equivalence relations where $E_0$ has infinitely many classes, $E_{n+1}$ refines $E_n$ and it splits each $E_n$-class into infinitely many equivalence classes;
4. Let $\mathcal{L}=\{E\}\cup\{ c_n\}_{n\in\mathbb{N}}$ where $E$ is a binary relation and the $c_n$ are constants. Let $T$ be the theory saying that $E$ is an equivalence relation with exactly one class of size $n$ for each $n\in\mathbb{N}$ and that $c_n$ is in that $E$-class. You might also want to think about why the theory of an equivalence class with exactly one class of size $n$ for each $n$ does not have quantifier elimination.

Other popular examples for which you might have seen a proof of quantifier elimination are:

1. The theory of a dense linear order without endpoints;
2. $ACF_p$ for $p$ prime or $0$;
3. The theory of non-trivial vector spaces over $\mathbb{Q}$.

Exercise 2. A type $p\in S(M)$ is $A$-invariant for $A\subset M$ if for any $\sigma\in\mathrm{Aut}(M/A)$, $\sigma(p)=p$. Show that an $A$-invariant type $p$ never divides over $A$. The type $p\in S(B)$ is finitely satisfiable over $A$ if for all $\phi(x,b)\in p$, there is some $a\in A$ with $\mathcal{U}\vDash\phi(a, b)$. Show that if $p\in S(B)$ is finitely satisfiable over $A$, then whenever $C\supset B$, there is some $q\in S(C)$ extending $p$ which is finitely satisfiable over $A$. Further prover that if $p$ is finitely satisfiable over $A$, it does not divide over $A$.

Exercise 3. Show that if $p\in S(B)$ divides over $A$, then for all $\kappa\geq \aleph_0$, there is some $B’\supset B$ with $|B’|=|B|+\kappa$ such that $p|_A$ has $\kappa$-many extensions to $B’$ which are $A$-conjugate over $B’$ and which divide over $A$.

Exercise 4. Determine the stability spectrum of each of the theories for which you proved quantifier elimination.

Exercise 5. If $\{a_i\}_{i<\omega}$ is a $C$-indiscernible sequence, then for $n, m<\omega$, $a_n\equiv_C^{\mathrm{stp}} a_m$.

Exercise 6. If $q$ is an extension of $p$, then $U(q)\leq U(p)$. Furthermore, $U(p)=0$ if and only if $p$ is algebraic.

Exercise 7. A sequence $(a_n)_{n\in\mathbb{N}}$ is $C$-independent if $a_n\indep{C}{}a_0, \dots, a_{n-1} \text{ for all } n\in\mathbb{N}.$ Show that if $T$ is superstable, given $b$ a finite tuple, there is some $n_0\in\mathbb{N}$ such that for all $n\geq n_0$, $b\indep{C}{}a_n$.

Exercise 8. (a) Show that $U$-rank is connected. That is, if $U(p)=\alpha>\beta$, then there is some $q$ which is a forking extension of $p$ such that $U(q)=\beta$.

(b) Given a countable set $A$, show that the collection of ordinals $\alpha$ such that $\alpha=U(p)$ for some $p\in S(A)$ is a set. In particular, show that there is some smallest $\beta_A\in \mathrm{ON}$ such that for $p\in S(A)$, $U(p)=\infty$ or $U(p)\leq \beta_A$. Further prove that if $\sigma:A\to A’$ is an automorphism, then $\beta_A=\beta_A’$.

(c) Conclude that for any type $p$, if $U(p)\geq (2^{\aleph_0})^+$, then $U(p)=\infty$.

Exercise 9. In this exercise we prove that $U$-rank is not necessarily continuous. Suppose that $T$ is superstable. Then, the function $\mathbb{U}:S(M)\to \mathrm{ON}$ sending $p$ to $U(p)$ is an actual function (by the previous exercise). By saying that $U$-rank is not continuous we mean that the preimage of $\{\beta \mid \beta<\alpha\}$ with respect to $\mathbb{U}$ is not necessarily open in the stone topology.

To prove this, consider the following example. Let $\mathcal{L}=\{P_n; E_n\}_{n\in\mathbb{N}}$ where the $P_n$ are unary predicates and the $E_n$ are binary relation symbols. Let $T$ be axiomatised by the following statements: the $P_n$ are disjoint and $E_n$ is an equivalence relation on $P_n$ with infinitely many classes all infinite.

Prove that $T$ is complete with quantifier elimination and also superstable (it is also $\omega$-stable).

Let $\mathcal{M}\models T$. For $n\in\mathbb{N}$ consider: $q_n=\{P_n(x)\}\cup\{\neg E_n(x, m) \mid m\in\mathcal{M}\}.$ Prove that $U(q_n)=2$. Now, consider $p(x)=\{\neg p_n(x)\}_{n\in\mathbb{N}}\cup\{x\neq m \mid m\in M\}.$ Show $U(p)=1$. However, any $\phi\in p$ contains a type of $U$-rank 2. Deduce $U$ is not continuous.