3
$\begingroup$

The finiteness lemma states the following:

Fix an $o$-minimal structure $M$. Let $A\subseteq M^2$ be a definable subset, such that for every $x\in M$ $A_x=\{y|(x,y)\in A\}$ is finite. Then there exists $k\in\mathbb{N}$ such that $|A_x|<k$ for every $x\in M$.

My attempt:

I'm trying to approach the problem via the compactness theorem. Let $\phi$ be the formula which defines $A$, and take the contrapositive. That is, suppose that there is not a $k\in\mathbb{N}$ such that $|A_x|<k$ for every $x\in M$.

We note then that the set of sentences $\sigma_n: \exists x|A_x|>n$, for $n\in\mathbb{N}$ is true of $A$. One may show these are in fact sentences by rewriting the $\sigma_n$ as $$\sigma_n:\exists x\exists y_1...\exists y_{n+1}\bigg(\bigg(\bigwedge_\limits{1\leq i\leq{n+1}}\phi(x,y_i)\bigg)\wedge\bigg(\bigwedge_\limits{1\leq i<j\leq{n+1}}\neg y_i=y_j\bigg)\bigg).$$

Now, taking $A$, our definable set, we construct a structure $\mathcal{A}=(A,...)$ in the standard language of $o$-minimality (noting that $\mathcal{A}$ is not itself $o$-minimal). It follows easily that $\mathcal{A}\vDash\forall\vec{x}\phi$, and $\mathcal{A}\vDash\sigma_n$, by assumption of the contrapositive. We then note that the set of sentences $\forall\vec{x}\phi\cup\{\sigma_n\}_{n\in\mathbb{N}}$ is finitely satisfiable by $\mathcal{A}$, such that by compactness the entire set must be satisfiable by some model.

It is also clear to show that $A$ is itself a model of the infinite set of sentences (again by the contrapositive assumption), but this is akin to saying that there is some fiber $A_x$ which is infinite, thereby completing the proof by contrapositive.

--

I do not think this proof is valid. I think a problem arises in my final paragraph. It seems to me that I should not be able to say that $\mathcal{A}$ acts as a model for the infinite set of sentences. And even if that step is valid, it doesn't necessarily suggest that any fiber is infinite. And yet, the lemma the way is phrased, suggests that one may use the compactness theorem to prove it.

Are there any other avenues to approaching this problem via compactness?

$\endgroup$
8
  • $\begingroup$ What does $o$-minimality mean? $\endgroup$
    – Berci
    Jul 9, 2019 at 12:01
  • $\begingroup$ @Berci Only definable sets are finite unions of points and intervals. $\endgroup$
    – quanticbolt
    Jul 9, 2019 at 12:14
  • 2
    $\begingroup$ My question is whether you're allowed to use the fact that o-minimality is preserved by elementary equivalence. (The result you are trying to prove is often used to prove that fact, so that might be circular.) $\endgroup$
    – Eric Wofsey
    Jul 9, 2019 at 15:36
  • 1
    $\begingroup$ It is a good exercise to understand the relation between the finiteness lemma and the fact that o-minimality is preserved under elementary equivalence. It is also probably enlightening to understand an independent proof of the finiteness lemma. $\endgroup$
    – nombre
    Jul 9, 2019 at 16:33
  • 2
    $\begingroup$ What you've written starts making no sense already in the third paragraph. What is "the standard language of o-minimality"? An o-minimal structure can be in any language, as long as the language includes a distinguished binary relation symbol $<$. It's especially unclear what language you want to consider on $A$, since $A\subseteq M^2$. Finally, even if we can make sense of a natural language for $\mathcal{A}$, it will not follow that $\mathcal{A}\models \forall x\, \phi$, unless $\phi$ is (equivalent to) a universal formula. $\endgroup$
    – Alex Kruckman
    Jul 9, 2019 at 17:50

1 Answer 1

Reset to default
4
$\begingroup$

The claim is true without the assumption of o-minimality if $M$ is $\omega$-saturated. (It is a standard exercise. I'll add the proof at the next edit, if required.)

Let $N\succeq M$ be $\omega$-saturated. If we can show that $A_x$ is finite for every $x\in N$ we are done.

Suppose not for a contradiction. Let $A_c$ be infinite for some $c\in N$. By o-minimality, $A_c$ contains an open interval. Then $N\models \exists a,b,c\ (a,b)\subseteq A_c$. Then the same holds in $M$. Contradiction.

$\endgroup$
2
  • 1
    $\begingroup$ Nice answer. The key thing that's going on here is the fact that "infiniteness is definable", also known as "elimination of $\exists^\infty$". For a definable set $A\subseteq M^2$ in an o-minimal structure, the set $\{x\in M\mid A_x\text{ is infinite}\}$ is definable (uniformly in the definition of $A$) by the formula expressing "$A_x$ contains an open interval": $\exists y\,\exists z\, \forall w\, (y<w<z\rightarrow A(x,w))$. $\endgroup$
    – Alex Kruckman
    Jul 9, 2019 at 18:06
  • 1
    $\begingroup$ Now it's a good exercise to prove for a general theory (no o-minimality assumption) that for any formula $\varphi(x,y)$, the following are equivalent: (1) There exists a formula $\psi(x)$ such that for any model $M\models T$ and any $a\in M$, the set $\{b\in M\mid M\models \varphi(a,b)\}$ is infinite if and only if $M\models \psi(a)$. (2) There exists a natural number $k$ such that for any model $M\models T$ and any $a\in M$, if $\varphi(a,M)$ is finite, then $|\varphi(a,M)|\leq k$. $\endgroup$
    – Alex Kruckman
    Jul 9, 2019 at 18:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .