Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.)

share|cite|improve this question
By "sentence" $p$ you presumably mean an axiom scheme, not a sentence in the traditional sense. – André Nicolas Feb 27 '12 at 20:21
No! That's what fascinating about it: you only need a single first-order sentence - if you restrict your attention to infinite structures only. (Another way of saying this is that there is some sentence p such that T is the theory of consequences of p together with the scheme of sentences $q_n$, where $q_n$ asserts that the domain has size at least $n$.) – user13568 Feb 27 '12 at 20:34
My confusion is that if $T$ is complete, and has infinite models, and $p$ is true in some or all infinite models, then by completeness $p$ is true in all models. – André Nicolas Feb 27 '12 at 20:48
@André: The important part is that $p$ must be false in all non-models. That does not follow from completeness alone. – Henning Makholm Feb 28 '12 at 14:44

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<j\le n} x_i\ne x_j$$ 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.

share|cite|improve this answer
I assume that your language has at least one relation symbol distinct from $=$. – arjafi Feb 27 '12 at 20:46
Yes; otherwise everything is trivially categorical. But (waving hands frantically here) the additional relations cannot be of any use in an attempt to axiomatize the theory without also rejecting some infinite models. – Henning Makholm Feb 27 '12 at 20:48
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. – user13568 Feb 29 '12 at 0:11

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<z \land z < y)$, expressing that the distance between $x$ and $y$ is $(n+1)$, are distinct for all $n\in\omega$).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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