# Complete/incomplete theory

I am thinking about completeness and incompleteness of theory's, and to illustrate both properties i am thinking of how to build an complete system, and then turn it into an incomplete one.

Example. Let the theory $\mathfrak{T}$ be the set of formulas that represent what a child (named raul) can speak in some point of the time. Let $D = \{ paul, raul \}$, $Functions = \{ fatherof \}$. Then the interpretation of the system affirms that raul knows who is his father. At some point, raul get's old and learns lots of new things. Then, if we update the interpretation of the system to reflect this change in the domain and don't update it's axioms, we should have a simple example of completeness/incompleteness in theories, right?

-
This reminds me less of classical logic and more of modal logic which has modal operators relating to the past and future. – Asaf Karagila Jun 15 '12 at 14:12
Indeed, this example is modeled much better in a modal logic than in predicate logic. I have posted it here because it seemed too appealing to illustrate completeness/incompleteness with this example, and maybe anyone could come up with something better. – felipegf Jun 15 '12 at 14:22

A simpler example would be to consider, for example, the elementary theory of groups, whose axioms are simply the group axioms. A model of the theory is just any group. Because both abelian and non-abelian groups exist, the theory can neither prove nor disprove $\forall a.\forall b.a*b=b*a$, and so it is incomplete.

On the other hand we can add some extra axioms to the theory that ensure that there is only one (isomporphism class of) models of the theory, for example:

1. $\exists a.\exists b.~a\ne b\land a\ne 1 \land b\ne 1$.

2. $\forall a.\forall b.~ a=1 \lor b=1 \lor a=b \lor a*b=1$.

The only model of the enlarged theory is the cyclic group of order 3. Every sentence $\phi$ in the language of group theory is either true or false in $C_3$, and so either $\phi$ or $\neg\phi$ must be provable in the extended theory -- the theory is now complete.

There are also complete theories that have more than one isomorphism class of models, but they are generally more complex -- especially showing that they are complete, as for example for Presburger arithmetic. Or else they are trivially complete by construction, such as the theory of true arithmetic whose axioms are all sentences in the language of basic arithmetic that are true in $\mathbb N$. (This theory is not recursively axiomatizable, however).

-