Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer

Your Answer

 
discard

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.