Uniform bound on the sets defined by a formula

65 Views Asked by At

I want to show that if we consider a strongly minimal model $M$, then for every formula $\varphi(x,y)$, there is a integer $n_\varphi$ such that whenever $\varphi(M,a)$ is finite, its cardinal is less than $n_\varphi$.

What I tried is to first look at algebraically closed fields, because it is a theory that is quite easy to understand. What happens is that basic formulas are polynomials so the sets defined is either infinite, or bounded by the degree. Then when we turn to conjonction and disjonction, we need the fact that infinite definbable set are cofinite, so that's where the hypothesis of strongly minimal is useful in this example, to ensure that the intersection of cofinite sets are cofinite. And finally, we conclude for any formula by elimination of quantifiers.

But this is just an example, I indeed use the hypothesis strongly minimal at some point, but for a given structure, I don't know if it eliminate quantifiers or even what are basic formulas.

An other thing I was looking at, is the fact that the existence of such a $n_\varphi$ is equivalent to the existence of a formula $\psi(y)$ such that $\psi(b)$ holds whenever $\varphi(M,b)$ is finite (one direction is simply to say "there is more than $n_\varphi$ elements verifying $\varphi(x,b)$" and the other one rely on compactness theorem) but it doesn't help me as I have no idea of how strong minimality might help me find such a formula $\psi$.

1

There are 1 best solutions below

0
On BEST ANSWER

We define the following set of formulas $$ \Sigma_\varphi(y) = \{\exists^{> k}x \varphi(x, y) \wedge \exists^{> k}x \neg \varphi(x, y) : k \in \mathbb{N}\}. $$ This set cannot be consistent with the theory $\operatorname{Th}(M)$ of $M$, because otherwise there would be an elementarily equivalent $N$ with some $b \in N$ such that $\varphi(N, b)$ is infinite and co-infinite, contradicting strong minimality. So by compactness there is some $n_\varphi \in \mathbb{N}$ such that $\exists^{> n_\varphi}x \varphi(x, y) \wedge \exists^{> n_\varphi}x \neg \varphi(x, y)$ is inconsistent with $\operatorname{Th}(M)$. That is: $$ \operatorname{Th}(M) \models \neg \exists y(\exists^{> n_\varphi}x \varphi(x, y) \wedge \exists^{> n_\varphi}x \neg \varphi(x, y)). $$ This last formula is equivalent to $\forall y(\exists^{\leq n_\varphi}x \varphi(x, y) \vee \exists^{\leq n_\varphi}x \neg \varphi(x, y))$. We claim that $n_\varphi$ is as required. If $\varphi(M, a)$ is finite for some $a \in M$ then $\neg \varphi(M, a)$ is infinite. We thus have $M \models \neg \exists^{\leq n_\varphi}x \neg \varphi(x, a)$ and so we must have $M \models \exists^{\leq n_\varphi}x \varphi(x, a)$, as required.


You are right that we can now use $n_\varphi$ to express "$\varphi(x, y)$ has infinitely many elements" as a formula in the variable $y$. More precisely, $\exists^{> n_\varphi}x \varphi(x, y)$ is equivalent to $\exists^\infty x \varphi(x, y)$, modulo $\operatorname{Th}(M)$. Here $\exists^\infty$ is the quantifier saying that "there exist infinitely many". Of course, such a quantifier is generally not a first-order quantifier, but in the specific case of $\operatorname{Th}(M)$ we can express it using a first-order formula. In this case we say that $\operatorname{Th}(M)$ eliminates the quantifier $\exists^\infty$.