11
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ I assume we're talking about first-order logic here. Anyway, what precisely do you mean by a complete theory in this context. (Can you provide a link to where you saw the terminology?) If you mean a maximal consistent theory, then the answer is: there exist maximal consistent theories that are not categorical. $\endgroup$ Commented Sep 16, 2014 at 10:09
  • $\begingroup$ I mean "completeness" and "incompleteness" as in Godel theorem. $\endgroup$ Commented Sep 16, 2014 at 10:14
  • $\begingroup$ Goedel's completeness theorem does not say that a theory is complete, it say that first-order logic is complete (with respect to its usual semantics). Note that "incomplete" in the sense of Goedel's incompleteness theorem is not the negation of "complete" in the sense of Goedel's completeness theorem. They're different concepts altogether. (If you think this terminology is awful, know that I wholly agree with you.) $\endgroup$ Commented Sep 16, 2014 at 10:16
  • 1
    $\begingroup$ Yes, true arithmetic is maximal-consistent but (surprisingly!) non-categorical. In fact, as Mauro explains in his answer: every first-order theory with an infinite model is non-categorical. $\endgroup$ Commented Sep 16, 2014 at 10:28
  • 3
    $\begingroup$ The completeness in Godel's Completeness Theorem is the completeness of first-order logic; whereas the incompleteness in Godel's Incompleteness Theorems refers to incompleteness of certain theories in first-order logic. The theorems talk about different objects and refer to different types of "completeness". $\endgroup$ Commented Sep 16, 2014 at 10:28

3 Answers 3

Reset to default
14
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ It might be worth pointing out that while this is not a categorical theory, if $M,N$ are models of $T$ of the same cardinality, then they are isomorphic. $\endgroup$ Commented Sep 16, 2014 at 13:30
  • $\begingroup$ This answer argues that completeness (of a theory) doesn't imply categoricity. But this is not what the OP asked. He asked whether categoricity implies completeness. This post does nothing to answer this question. $\endgroup$ Commented Aug 15, 2021 at 12:53
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ This might be the longest thing you have written here so far. What happened to "Quick Solutions Rene"? $\endgroup$ Commented Sep 16, 2014 at 13:41
  • $\begingroup$ Thanks. That is exactly the answer to my question. $\endgroup$ Commented Sep 16, 2014 at 14:21

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.