Difference between completeness and categoricity

Question

I have problems understanding the difference between a categorical theory and a complete theory. My intuition says that every valid complete theory must be categorical. Is it true?

Clarification: by "complete theory" I mean "maximal consistent theory". Refer to the Wikipedia article: http://en.wikipedia.org/wiki/Complete_theory.

Here's what I understand:

• A theory is a tool to accept or reject structures.

• A theory can be trivial, that means it accepts any structure. Its axiom set evaluates to logical truth.

• A theory can be inconsistent, that means it rejects all structures. Its axiom set is contradictory and evaluates to logical false.

• A theory can be categorical, that means it accepts exactly one structure.

• A theory can be complete, that means it has something to say about any sentence, or incomplete, that means it leaves some sentences out.

Now, are the following claims correct?

• A trivial theory is incomplete, in fact it does not say anything about any sentence.

• An invalid theory is complete, in fact it says "yes" to every sentence (and to its negation too).

• A categorical theory is complete. That means, categoricity implies completeness.

Now, can there exist a theory that is complete and valid but not categorical? If yes, then how? If a theory is to have two different models, then it must leave some sentences undecided, so the models can differ in that point. Is it right?

Answer 1

There are a number of things I would like to clarify. Mathematicians are interested in theories (in the first order logic sense) for one of two reasons. Either we are interested to find (understand) all models of a given theory for example the theory of groups. Its models are groups and we would like to understand them. There are some consequences of the theory itself, such as the uniqueness of the unit, but these consequences are trivial and group theorests study the models.

Second we may be interested in the consequences of a particular theory, for example Euclidian geometry is a formalizable first order theory and we want to derive its consequences, almost all Greek mathematics falls in this category. Same with Peano arithmetic and set theory. (We can also then study the models of these theories.)

In the kind of Model theory you are working on usually complete theories are under consideration. Consider for example two nonisomorphic models of a theory, why are they nonisomorpic ? What distinguishes them ? First they may satisfy different formulas, $S_3$ and $\mathbb{Z}_6$ are both groups of the same size, why are they different ? One has is abelian and the other isnt, they are distinguished by a first order property. This is the easist way to show that models are nonisomorphic, so we will eliminate this possibility by considering complete theories, ones which already determine all first order properites. An example is torsion free divisible abelian groups.

A second way in which models can be distinguished is by size, this can always happen as pointed out by Mauro in his answer. The proper definition of categoricity is

$T$ is categorical in a cardinal $\kappa$ when all models of cardinality $\kappa$ are isomorphic.

As Maurio also pointed out if $T$ is categorical ins at least one infinite cardinal it is complete since otherwise you could get two models with different first order properties and thus non isomorphic.

A theory can be categorical in some powers but not others, for example torsion free divisible abelian groups is not $\aleph_0$ categorical but it is $\kappa$ categorical for all uncountable $\kappa$. What distinguishes the countable models ? It must be some kind of higher order property not expressible in first order logic. In fact it is the rank (=dimension as a vector space) of the group.

As a final example take the theory with infinitely many constants $c_n$ and axioms $$c_n\neq c_m$$ for $n\neq m$. This is not $\aleph_0$ categorical but it is $\kappa$ categorical for all uncountable $\kappa$.

Answer 2

In first-order logic, it is not so.

From the upward Löwenheim-Skolem theorem follows that there are no categorical first-order theories with infinite models.

The issue is that with f-o language we can use sentences like $\exists x \exists y (x \ne y \land y \ne x)$ to "characeterize" only domains of finite cardinality.

F-o language lacks the expressive capability to "handle" infinite cardinalities.

About the "more limited" property of $\kappa$-categoricity, see David Marker, Model theory : An introduction (2002), page 42 :

Theorem 2.2.6 (Vaught's Test) Let $T$ be a satisfiable theory [of signature $\mathcal L$] with no finite models that is $\kappa$-categorical for some infinite cardinal $\kappa \ge |\mathcal L|$. Then $T$ is complete.

[...]

The assumption that $T$ has no finite models is necessary. Suppose that $T$ is the $\{ +, 0 \}$-theory of groups, where every element has order $2$. In the exercises, we will show that $T$ is $\kappa$-categorical for all $\kappa \ge \aleph_0$. However, $T$ is not complete. The sentence $\exists x \exists y \exists z (x \ne y \land y \ne z \land z \ne x)$ is false in the two-element group but true in every other model of $T$.

Vaught's test implies that all of the categorical theories discussed above [e.g. the theory of torsion-free divisible Abelian groups] are complete. In particular, algebraically closed fields are complete.

Answer 3

Here is a simple example of a very concrete, complete, noncategorical theory.

Let $T$ be the first-order theory whose language has one unary relation symbol, $R$, and an axiom $(\forall x)R(x)$. The theory does not have the equality symbol $=$ or any symbols other than $R$ in its language.

Claim: This theory $T$ is complete: for each sentence $\phi$ in the language, the theory either proves $\phi$ or proves the negation of $\phi$.

Proof sketch: Given a sentence, we can remove all the quantifiers, and replace every term $R(z)$ in the formula with $\top$. Then the original sentence is provable in $T$ if and only if the resulting sentence is true statement in propositional logic.

Claim: The theory $T$ is not categorical.

Proof sketch: For any set $S$, we can turn $S$ into a model of $T$ by simply asserting that $R(z)$ holds for all $z \in S$. Two such models will be isomorphic if and only if they have the same number of elements.

This is also a very trivial example of the process known as quantifier elimination, which is a fundamental technique for showing that various theories are complete.