Exercises

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:

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.

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.

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:

5. The theory of a dense linear order without endpoints;
6. $ACF_p$ for $p$ prime or $0$;
7. 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.