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?
Best Answer
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.