MathOverflow is a question and answer site for professional mathematicians. 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

Ryll-Nardzewski theorems states that if $T$ is a countable complete theory, then $T$ is $\aleph_0$-categorical if and only if for every $n<\omega$ there are only finitely many formulas $\varphi(x_1,\ldots,x_n)$ up to equivalence relative to $T$.

$T$ is a countable theory if it can be built in a countable language.

My question is: Is there a complete uncountable theory which is $\aleph_0$-categorical, but that for some $n<\omega$ there are infinitely many formulas $\varphi(x_1,\ldots,x_n)$ up to equivalence relative to $T$?


share|cite|improve this question
Welcome to MO! A local custom is that every question should normally bear at least one arXiv-style tag, e.g. "lo.logic" or "ct.category-theory". I've just added one to yours. – Tom Leinster Dec 13 '12 at 22:15
Ah yes. Another custom is that you don't ask the same question simultaneously here and at math.stackexchange, as this potentially wastes people's time. Your question here may get closed for this reason. – Tom Leinster Dec 13 '12 at 23:03
Yet another custom is to accompany links with text so you know why you may or may not want to click through. – François G. Dorais Dec 13 '12 at 23:32
up vote 7 down vote accepted

Let $T$ be the complete theory of $\mathbb N$, with a binary predicate $<$ for the standard ordering, unary predicates for all subsets of $\mathbb N$, and constants for all the elements of $\mathbb N$. This clearly has uncountably many inequivalent unary formulas. I claim that its standard model is, up to isomorphism, the only countable model. The main point in the proof is that there exist continuum many infinite subsets $A_i$ of $\mathbb N$ any two of which have a finite intersection. If $M$ were a nonstandard model, it would have an element $c$ greater (in the sense of $M$) than all the standard numbers; each $A_i$ woujld have an element $a_i$ greater than $c$ (because the sentence saying $A_i$ has arbitrarily large elements is in $T$); and these $a_i$'s would all be distinct (because each $A_i\cap A_j$ has a standard upper bound).

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.