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
up vote 8 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).

  • For your example $C_3$, simply that a statement or its negation is true does not imply that it is derivable too, or?? – StefanH Apr 13 '17 at 16:58
  • @StefanH: Yes, because the axioms make sure the $C_3$ is the only model of the theory. That's Gödel's completeness theorem: Any sentence that is true in every model of the theory is derivable from its axioms. – Henning Makholm Apr 13 '17 at 17:00
  • Oh, yes sure we are in first order logic. Then Gödels completeness theorem applies :) – StefanH Apr 13 '17 at 17:13

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.