Let $T$ be a first order theory. Consider the following finiteness property for $T$:

If $M$ is a finite model for $T$, then the number of definable subsets of $M^n$ is bouned by a number $s(n)$ which depends on $n$ but not on $M$. Moreover, there are first order formulas $\phi_1,\ldots \phi_{s(n)}$ in the first order language of $T$ such that all the definable subsets of $M^n$ are of the form $\{(m_1,\ldots m_n)| \phi_i(m_1,\ldots,m_n)\}$ for some $i=1,\ldots s(n)$.

An example for such a theory is the theory of vector spaces over a finite field $k$. A slightly more general example is the theory of abelian groups of bounded rank. The theory of abelian groups or of groups will be a counter example, since the number of subsets $\{m\in M| m\text{ has order }n\}$ for different $n\in \mathbb{Z}$ is unbounded (for an arbitrary finite abelian group). Another counterexample is the theory of ordered sets, since the number of subsets $\{m\in M|\exists x_1,\ldots x_n : x_1<x_2<\cdots<x_n<m\}$ is unbounded for an arbitrary ordered set. My question is if this property was studied, and if there are any general things that can be said about such theories, or if they perhaps can be classified.

  • 3
    $\begingroup$ Are you aware of the Ryll-Nardzewski/Engeler/Svenonius theorem? $\endgroup$ – Emil Jeřábek Oct 13 '17 at 9:54
  • 3
    $\begingroup$ That is, for theories $T$ in a finite language, your condition holds iff the theory of pseudofinite models of $T$ has finitely many completions, each of which is $\omega$-categorical. $\endgroup$ – Emil Jeřábek Oct 13 '17 at 9:59
  • $\begingroup$ I was not aware of that theorem. Thank you for that. Is there any place where I can find some examples for theories satisfying that? $\endgroup$ – Ehud Meir Oct 13 '17 at 10:01
  • $\begingroup$ @EhudMeir: keywords which will lead you to examples are "$\aleph_0$-categorical theory" and "oligomorphic permutation group". In particular, countable-infinity of the domain of the structures in question seems to play an essential role in this topic. If a structure has coutable domain, then it's $\aleph_0$-categorical iff its automorphism group is oligomorphic. Very very roughly: for examples, you'll have to look into very symmetrical structures. And in particular: the theorem is vacuously true for finite cardinality, and false for uncountable cardinality. So, [...] $\endgroup$ – Peter Heinig Oct 13 '17 at 11:58
  • $\begingroup$ [...] roughly speaking, the 'place' where to look for examples is: highly symmetrical structures on $\omega$. $\endgroup$ – Peter Heinig Oct 13 '17 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.