2
$\begingroup$

I was alluded to the fact that there is no connection between the growth rate of the number of nonisomorphic finite models of a theory and the fact wether there are countably or uncountably many nonisomorphic countably infinite models.

There seem to be four types of theories (the examples are from answers and comments to my MSE question How many countable graphs are there?):

Type 1: Low growth rate of finite models (less than exponential), countably many infinite models
Example: theories with unary predicates only

Type 2: Low growth rate of finite models, uncountably many infinite models
Example: groups, fields

Type 3: High growth rate of finite models (at least exponential), countably many infinite models
Example: graphs with finitely many edges

Type 4: High growth rate of finite models, uncountably many infinite models
Example: graphs

All examples are first order theories except "graphs with finitely many edges" since finiteness cannot be defined in a first order language.

So my questions are:

What is a first order example of a Type 3 theory?

How can these types of theories be characterized?

One thing holds for all theories of Type 2 to 4: They must have "more" than unary predicates, for example a binary relation. (Could a unary function suffice?)

$\endgroup$
11
  • 1
    $\begingroup$ Does it really save you that much more time to say "FO" as opposed to "first-order"? $\endgroup$ Mar 18, 2011 at 15:01
  • $\begingroup$ No, it doesn't, you are right. $\endgroup$ Mar 18, 2011 at 15:11
  • $\begingroup$ If I am not mistaken, there is no first order theory (in the language with one binary relation) whose models are precisely the graphs with finitely many edges. $\endgroup$ Mar 19, 2011 at 6:01
  • $\begingroup$ And why do you say that groups are an example of a theory with low growth rate of finite models? What precisely do you mean by "low growth rate"? $\endgroup$ Mar 19, 2011 at 6:05
  • $\begingroup$ Sorry, that was a mistake, to be honest: I don't know which growth rate groups have! By "low growth rate" I mean that the number of structures of order $n$ grows slower than exponentially with respect to $n$. $\endgroup$ Mar 19, 2011 at 9:49

1 Answer 1

4
$\begingroup$

This is a bit of a cheat, but since you didn't disallow infinite theories: take the theory $T$ with one unary function symbol, the axiom $\forall x\,(f(x)=f(y)\to x=y)$, and the axioms $$\exists x_1,\dots,x_{2^k}\,\bigwedge_{1\le i<j\le2^k}x_i\ne x_j\to\forall x\,f^{(k)}(x)\ne x$$ for every $k\in\omega$. In an infinite model of $T$, $f$ is an injective function without cycles, i.e., a disjoint union of copies of $(\mathbb Z,s)$. Thus $T$ is uncountably categorical, and has countably many countable models.

On the other hand, a finite model of $T$ of size $n$ is a disjoint union of cycles of size $\ge\log_2n$. The number of such models is given by the partition function $p(\log_2n,n)$, which is easily seen to be $\ge2^{\Omega(\sqrt n)}$.

As for the second question, I doubt there is any simple equivalent characterization. Already determining whether a theory has countably or uncountably many countable models is nontrivial. (A useful condition is that if the theory has uncountably many complete extensions, or if one of its complete extensions has uncountably many complete $n$-types for some $n$, then it must have $2^\omega$ countable models, but this is by no means an equivalent characterization.) It's not even known whether a theory may have exactly $\aleph_1$ countable models (Vaught’s conjecture).


Since no one gave a better answer yet, I will say something relevant to the question whether there exists a finite example of a type 3 theory. It does not solve the problem (in a way I would find satisfactory, anyway), but it's good to keep it in mind.

If we have a finite language with only (non-nullary) predicates, then first-order logic satisfies a 0–1 law: for any sentence $\phi$, the asymptotic probability $$\mu(\phi)=\lim_{n\to\infty}\mu_n(\phi),\qquad\mu_n(\phi)=\frac{|\{M:|M|=n,M\models\phi\}|}{|\{M:|M|=n\}|}$$ exists and equals 0 or 1. The convergence is exponentially fast: $\mu_n(\phi)=\mu(\phi)+O(\alpha^n)$ for some constant $\alpha<1$. Moreover, the set $T_1$ of all sentences with probability 1 is a complete deductively closed theory, and it is $\omega$-categorical. $T_1$ can be explicitly axiomatized by so-called extension axioms, which state, roughly speaking, that any finite subset of the model can be extended by another element in the model to any possible configuration of the atomic relations.

If we allow constants in addition to predicates, the 0–1 law no longer holds, but the asymptotic probability exists, and it has the form $\mu(\phi)=a/2^b$ for integers $a,b$, where $b$ depends only on the language. We have $\mu_n(\phi)=\mu(\phi)+O(1/n)$. (Note that if $c,d$ are constants, $\mu_n(c=d)=1/n$.) $T_1$ is still axiomatized by the extension axioms, but it is no longer complete; its complete extensions are given by diagrams of finite models whose domains comprise pairwise distinct realizations of constants in the language. If we also allow unary function symbols, $\mu(\phi)$ exists, though it may be irrational: e.g., $\mu(\forall x\,f(x)\ne x)=1/e$. With binary function symbols, $\mu(\phi)$ may fail to converge.

Now, returning back to the case of relations and constants, let $\phi$ be a sentence such that $\mu(\phi)>0$. Then $\phi$ follows from a finite set $T$ of extension axioms together with a consistent quantifier-free sentence $\theta$. I claim that $T+\theta$, and therefore $\phi$, has $2^\omega$ nonisomorphic countable models. In order to simplify the notation, I will deal with the case where the language consists of only one binary relation symbol $E$, i.e., models are directed graphs. In this case, we can ignore $\theta$, and there is a constant $k$ such that $M\models T$ whenever the following holds: for any sets $A_0,B_0,A_1,B_1\subseteq M$ with $A_i\cap B_i=\varnothing$ and $|A_i|,|B_i|\le k$, there exists an $x\in M\smallsetminus(A_0\cup B_0\cup A_1\cup B_1)$ such that $E(x,y)$ for every $y\in A_0$, $\neg E(x,y)$ for every $y\in B_0$, $E(y,x)$ for every $y\in A_1$, $\neg E(y,x)$ for every $y\in B_1$, and we can also prescribe whether $E(x,x)$ holds or not.

Let $L$ be any countably infinite linear order. I claim that there exists a countable model $M_L\models T$ such that $L$ is the largest linearly ordered (under $E$) infinite submodel of $M_L$. Then $M_L\simeq M_{L'}$ can only hold for $L\simeq L'$, and since there are $2^\omega$ nonisomorphic linear orders, there are also $2^\omega$ nonisomorphic models of $T$. We construct $M_L$ as follows. We start with $L$, and then for any finite sets as above, we add an appropriate element $x$ in such a way that $\neg E(x,y)$ and $\neg E(y,x)$ hold for all $y\notin A_0\cup A_1\cup\{x\}$. By the construction, $L$ is a linearly ordered submodel of $M_L$. On the other hand, let $L'$ be an infinite linearly ordered submodel of $M_L$. If $L'\nsubseteq L$, let $x\in L'\smallsetminus L$. Since $x$ is connected to at most $2k$ points and $E\restriction L'$ is linear, $|L'\cap L|\le2k$. Moreover, any element of $L'\smallsetminus L$ is connected to at most $2k$ elements generated earlier, thus by the same argument, $|L'|\le2k+1$ is finite, a contradiction.

This shows that if $\phi$ is a sentence using predicates and constants only, then either $\phi$ has $2^\omega$ nonisomorphic countable models, or $\mu(\phi)=0$, and more precisely, $\mu_n(\phi)=O(1/n)$. The latter does, in a sense, mean a “low growth rate”, but it may well be exponential in absolute numbers. (Note that $\mu_n(\phi)$ counts all models, not non-isomorphic models. Obviously, the former is an upper bound on the latter, so this is not a priori a problem. Moreover, Fagin shows in the purely relational case that the asymptotic probability $\nu(\phi)$ computed over nonisomorphic models is the same as $\mu(\phi)$, with a similar rate of convergence.)

$\endgroup$
2
  • $\begingroup$ Didn't I implicitly disallow infinite theories by claiming that finiteness cannot be defined in a first order language? $\endgroup$ Mar 18, 2011 at 16:53
  • 1
    $\begingroup$ Finiteness cannot be defined by an infinite first-order theory either. (That is, you cannot axiomatize graphs with finitely many edges as in your example, although you can axiomatize graphs with infinitely many edges.) You implicitly allowed infinite theories by talking about theories instead of formulas in the first place. If that's not intended you should clarify the question. $\endgroup$ Mar 18, 2011 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.