6
$\begingroup$

I work in first order logic.

I noticed that a complete theory that is satisfied by finite models can only be satisfied by models of a given fixed finite cardinality. It made me think about the converse of Vaught's test given all assumptions but $\kappa$-categoricity. Namely,

is there a consistent complete theory without finite models in a countable language such that for every infinite cardinal $\kappa$ the theory is not $\kappa$-categorical?

Given an example of one such theory I would also find interesting knowing how has completeness been proved.

$\endgroup$
6
  • 2
    $\begingroup$ An example is the complete theory of $\mathbb{N}$ in the language $(+,\cdot,0,1)$. Trivially, this theory is complete, consistent and has no finite models. But it is a well known fact that this theory is not categorical for any infinite $\kappa$. $\endgroup$
    – russoo
    Commented Sep 25, 2015 at 12:27
  • $\begingroup$ @russoo The language (<) would do just as well, wouldn't it? $\endgroup$
    – bof
    Commented Sep 25, 2015 at 23:15
  • $\begingroup$ Thanks @russoo. Could you give me any insight on how it is proved that such theory is not categorical for any infinite $\kappa$ ? $\endgroup$
    – Anguepa
    Commented Sep 25, 2015 at 23:49
  • $\begingroup$ @Anguepa. The only proof I know uses so called $\kappa$-like models of arithmetic. The existence of such models is a somewhat non-trivial fact. $\endgroup$
    – russoo
    Commented Sep 28, 2015 at 10:29
  • $\begingroup$ @bof. Yes, the language $<$ is sufficient. $\endgroup$
    – russoo
    Commented Sep 28, 2015 at 10:30

3 Answers 3

5
$\begingroup$

A mathematically natural example is the theory of real closed fields. Reals which are not algebraic can be included or omitted in arbitrary-cardinality models as you desire, via compactness and omitting types; and a model of RCF, though it may have nontrivial automorphisms, will embed the algebraic reals in a unique way, so which rational cuts are realized is an isomorphism invariant.

$\endgroup$
4
$\begingroup$

Russoo gave (in a comment, unfortunately), the example of $(\mathbb{N},+,\cdot,0,1)$. While that works, there are tamer examples. Let $L$ be the language with a unary predicate $P_n$ for each $n \in \mathbb{N}$, and let $T$ assert these predicates are disjoint, and that each one has infinitely many realizations. $T$ is complete, and is not categorical for any $\kappa$: for any $\kappa$, there are models of size $\kappa$ containing a point not in any $P_n$, and there are models with no such point. $T$ is tame in that it is stable, if you know what that means.

For this $T$, and for similar theories, there is another test that works if you're trying to show completeness:

Let $T$ be any theory. If, for every $\aleph_0$-saturated $M,N$ modeling $T$, the family of isomorphisms between finitely generated substructures of $M$ and $N$ has the back-and-forth property, then $T$ eliminates quantifiers. If furthermore, for all such models, that family is non-empty, $T$ is complete. (A family $\mathcal{F}$ of partial functions $M \to N$ has the back-and-forth property if, for any $f \in \mathcal{F}, a \in M, b \in N$, there are $f_1,f_2 \in \mathcal{F}$ extending $f$ such that $a$ is in the domain of $f_1$ and $b$ is in the range of $f_2$.)

$\endgroup$
0
$\begingroup$

I might have found another example here.

$\endgroup$

You must log in to answer this question.

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