4
$\begingroup$

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.

$\endgroup$
6
  • 3
    $\begingroup$ Are you aware of the Ryll-Nardzewski/Engeler/Svenonius theorem? $\endgroup$ Commented Oct 13, 2017 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$ Commented Oct 13, 2017 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
    Commented Oct 13, 2017 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$ Commented Oct 13, 2017 at 11:58
  • $\begingroup$ [...] roughly speaking, the 'place' where to look for examples is: highly symmetrical structures on $\omega$. $\endgroup$ Commented Oct 13, 2017 at 11:59

0

You must log in to answer this question.

Browse other questions tagged .