Results 1 to 11 of 11

Math Help - Completeness and Incompleteness theorems

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    17

    Completeness and Incompleteness theorems

    Hi Folks, I was wondering if someone would be kind enough to explain the differences in the above theorems in as simple terms as possible. I've been reading various sites but I'm just getting more and more confused!

    My understanding is the the completeness theorem follows on from Russell and Whitehead's Principa Mathematica and states that any formal system that is robust enough to axiomatize arithmetic must have statements that are true but not provable. (I couldn't find any examples of this so if anyone has one....)

    BUT I can't see the difference between the above and in the incompleteness theorem.

    Any help greatly appreciated. Thanks.


    Dave.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    A completeness theorem is a statement that some theory or logic is complete. Now, there are two kinds of completeness: a syntactic completeness and a semantic one. A theory T (i.e., a set of formulas) is syntactically complete (with respect to some logic, i.e., axioms and inference rules) if T is consistent, i.e., T does not derive a contradiction, but if any formula is added to T, it becomes inconsistent. Note that this definition does not refer to models, interpretations, or truth; it only refers to derivability. On the other hand, a logic L is semantically complete if for any formula P, if P is valid (i.e., true in every interpretation), then P is derivable in L. There is also strong semantic completeness for a logic L, which says that if a theory T logically implies P, (i.e., if all formulas in T are true in some interpretation, then P is also true in that interpretation), then T derives P in L. The (weak) completeness is obtained when T is empty. The converse to semantic completeness is soundness.

    Thus, there is Gödel's completeness theorem, which says that classical first-order logic is semantically complete. It has nothing to do with arithmetic. On the other hand, Gödel's incompleteness theorem says that arithmetic (which is a theory) and all theories that contain it are syntactically incomplete. The fact that there exists a formula that is true in the standard model of natural numbers but is not derivable in arithmetic is an easy corollary: Suppose that neither A not ~A is derivable; one of them has to be true. Gödel's second incompleteness theorem gives a specific example of a formula such that it, as well as its negation, are not derivable in arithmetic: this is the formula that expresses the consistency of arithmetic.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    I believe that the Completeness Theorem says that any consistent set of sentences has a model. This is quite different from the incompleteness theorem.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    I believe that the Completeness Theorem says that any consistent set of sentences has a model.
    This is a closely related statement that is often used as a key lemma in proving that T |= P implies T |- P, my version of (strong semantic) completeness.

    Proposition. Suppose that every consistent set has a model. Then T |= P implies T |- P.
    Proof. Suppose that T\models P but T \nvdash P. Then T\cup\{\neg P\} is consistent. Therefore, there is a model M such that M\models T, but M\not\models P, which contradicts T\models P.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2009
    Posts
    17
    Quote Originally Posted by emakarov View Post
    It has nothing to do with arithmetic.
    Thanks for such a helpful reply - I really appreciate it. I'm still struggling to fully understand it though. I've copied something I was reading on one of (the many) sites I've been reading. Presumably, the writer is discussing Godel's Incompleteness theorem?


    KURT GODEL
    "But it soon became clear that naive use of sets could lead to contradictions (such as the set of all sets that aren't members of themselves). Set theory itself would have to be axiomatized. In their massive 3-volume Principia Mathematica, Russell and Whitehead built the foundations of mathematics on a set of axioms for set theory; they needed hundreds of preliminary results before proving that 1 + 1 = 2.

    There remained the problem of analyzing the axioms of set theory. Mathematicians hoped that their axioms could be proved consistent (free from contradictions) and complete (strong enough to provide proofs of all true statements). Gödel showed these hopes were overly naive. He proved that any consistent formal system strong enough to axiomatize arithmetic must be incomplete; that is, there are statements that are true but not provable. Also, one can't hope to prove the consistency of such a system using the axioms themselves. The basic idea of Gödel's proof, indirect self-reference, is strikingly simple, but tricky to grasp.
    "
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    Yes, this is talking about the incompleteness theorem. Gödel showed that there is a formula A independent from arithmetic, i.e., neither A not ~A is provable from arithmetic axioms. Since one of these formulas must be true in the standard model, arithmetic is not "strong enough to provide proofs of all true statements".

    Quote Originally Posted by emakarov
    A theory T is syntactically complete if T is consistent, but if any formula is added to T, it becomes inconsistent.
    To make it more precise, if any formula that is not derivable from T is added to T, it becomes inconsistent.

    I glossed over the following fact. Suppose T\nvdash A and T\nvdash\neg A. Why does this mean that T is incomplete according to the definition above? Because T\cup\{A\} is consistent. Indeed, if T\cup\{A\}\vdash\bot, then T\vdash\neg A (how this is shown depends on the details of the logic).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2009
    Posts
    17
    That's a great help. Thanks very much emakarov.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Oct 2009
    Posts
    17
    Still reading up on this and it's seems to be becoming clearer, thanks to the help here.

    Would this be a correct and simple summation for the completeness theorem: "for a logical consequence of a set of axioms, there is a proof of the consequence using the axioms and logical rules of reasoning."?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    Would this be a correct and simple summation for the completeness theorem: "for a logical consequence of a set of axioms, there is a proof of the consequence using the axioms and logical rules of reasoning."?
    Basically, yes. Usually we don't say that a formula P is a logical consequence of the set of axioms. Calling it this way means that for any interpretation I, if all axioms are true in I, then P is true in I. However, when we are talking about interpretations of a logic, they are already supposed to make all axioms true. It's not like we consider interpretations of classical logic, and only some of them make all axioms true; the truth of axioms is built in the concept of an interpretation. Formulas that are true in all interpretations are called valid. So: "All valid formulas have a proof using the axioms and logical rules of reasoning." In any case, this is a minor point.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Oct 2009
    Posts
    17
    emakarov, thanks very much for your help (and patience!), I really appreciate it. It's made a lot of help reading and understanding the information that I've collected.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    You are welcome.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Incompleteness thereom
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 28th 2010, 11:15 AM
  2. Replies: 0
    Last Post: November 27th 2009, 11:35 AM
  3. completeness
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: August 13th 2009, 07:30 PM
  4. Gödel's Incompleteness Theorem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: June 16th 2009, 11:44 PM
  5. Completeness
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 5th 2009, 12:52 AM

Search Tags


/mathhelpforum @mathhelpforum