4
$\begingroup$

I have what I am sure is a trivial question, but I can't seem to answer it for myself.

In model theory, there is a theorem of Hrushovski which shows that if T is a totally categorical theory (i.e., T is complete and has exactly one model of each infinite cardinality up to isomorphism), then (i) T is not finitely axiomatizable, but (ii) T is finitely axiomatizable modulo infinity; that is, there is some sentence p such that T is precisely the set of sentences true in every infinite model of p.

My question is to what extent the converse holds. That is, let T be a (EDIT: complete) theory which is finitely axiomatizable modulo infinity, but which is not finitely axiomatizable. Then is T necessarily totally categorical, and if not, what sort of assumptions on T are enough to ensure total categoricity?

(The assumption that T is not actually finitely axiomatizable is clearly necessary: otherwise, take the theory DLO of dense linear orders without endpoints, which is countable categorical but not uncountable categorical.)

  • 1
    @André: The important part is that $p$ must be false in all _non-models_. That does not follow from completeness alone.2012-02-28

2 Answers 2

3

This is a nice question, it's too bad it was unanswered for so long. I'll give an example of a complete theory $T$ which is quasi-finitely axiomatizable (i.e. finitely axiomatizable modulo infinity) and not finitely axiomatizable, but not categorical in any cardinality.

Let $L = \{<\}$, and consider the theory $T$ of infinite discrete linear orders with endpoints. This says:

(1) $<$ is a linear order.

(2) There is a maximum element.

(3) There is a mininum element.

(4) If $x$ is not the maximum element, $x$ has a successor.

(5) If $x$ is not the minimum element, $x$ has a predecessor.

(6$_n$)$_{n\in\omega}$ There are at least $n$ elements.

Showing that $T$ is complete is a standard application of Ehrenfeucht-Fraïssé games.

Since (1)-(5) can each be expressed by a single sentence, the conjunction of these gives a finite axiomatization of $T$ modulo infinity: (6$_n$)$_{n\in\omega}$.

However, $T$ cannot be finitely axiomatizable, because it is pseudofinite. To spell this out, note that (1)-(5) are satisfied in any finite linear order. So if $\Delta$ is any finite collection of sentences of $T$, by compactness $\Delta$ is implied by a finite collection $\Delta'$ of the axioms of $T$ listed above. Now $\Delta'$ is satisfiable in any sufficiently large finite linear order, and hence so is $\Delta$. But $\Delta$ also has infinite models, since $T$ does, so $\Delta$ does not axiomatize a complete theory.

To finish, note that $T$ is not uncountably categorical (it's unstable), nor is it countably categorical (the formulas $\phi_n(x,y): \exists^{!n}z\, (x, expressing that the distance between $x$ and $y$ is $(n+1)$, are distinct for all $n\in\omega$).

1

Assuming that your logic includes equality, the answer to the first part of the question is "no".

For a counterexample, let $T$ be the theory with axioms $(\exists x_1)(\exists x_2)\cdots(\exists x_n) \bigwedge_{1\le i for all integers $n\ge 2$. Then the models of $T$ are exactly all infinite interpretations of its language. This is not finitely axiomatizable, because in the pure predicate calculus with equality, any sentence with an infinite model also has finite models.

However, $T$ is finitely axiomatizable modulo infinity (you can take $p$ to be any propositional tautology, for example), and -- provided we add some relation apart from equality to its vocabulary -- it is obviously very far from from categorical; so far that it seems doubtful that there is any natural way to extend your condition to a sufficient one, without the additional conditions being sufficient in themselves.

  • 3
    The problem here is that if your language includes other symbols, then T is not a complete theory. In my question, I intended to focus on only complete theories; this has now been fixed.2012-02-29