kube@cogsci.berkeley.edu (Paul Kube) (06/02/87)
In article <1192@epimass.EPI.COM> jbuck@epimass.EPI.COM (Joe Buck) writes: >In article <8135@ut-sally.UUCP> turpin@ut-sally.UUCP (Russell Turpin) writes: >>Godel's *incompleteness* theorems simply say that your >>hypothetical logician, if consistent, might come across >>unprovable statements. In the first order predicate calculus, for >>example, there are fully quantified statements that can neither >>be proven or disproven. > >Godel's first incompleteness theorem states that you WILL, not MIGHT, >come up with unproveable statements if your axiom system is powerful >enough. The upshot of Goedel's incompleteness theorem is the unprovability of necessarily true statements, i.e., statements true in every model, for sufficiently powerful systems. That there are *some* statements your system can't prove is a good thing: but this is the requirement of consistency, not completeness. First order predicate calculus is both consistent and complete. / / / / --Paul.
moll@umn-cs.UUCP (06/08/87)
There have been several articles referring to completeness results in rather vague language, and there have been some inaccuracies. I will attempt to clear up some of the confusion for the uninitiated by presenting some (by necessity informal) definitions followed (without proof) by the Soundness, Completeness and Incompleteness theorems. A very lucid presentation of this material can be found in _Introduction to Mathematical Logic_ by Enderton. I hope this helps. It seems to me that there has been much confusion in this discussion over the difference between completeness of a logical system and completeness of a set of axioms. It is unfortunate that the same word was chosen for both concepts. The knowlegeable may want to skip down to the "Theorems" section. The uninterested may want to hit "n". ---------------------------Definitions----------------------------------- I will refrain from defining "statement" except to say that one may use the quantifiers "for all" and "there exists", logical connectives such as "and", "or" and "not", and a specified set of predicates and functions, such as ">" and "+". The term usually used in formal discussions is "sentence" or "wff". Just how much can be expressed in a statement depends on what set of predicates and functions are available. Axiom: A statement assumed true. The theorems to follow will discuss what can and cannot be proven from an arbitrary set of axioms. Model (of an axiom): A mathematical structure in which the axiom is true. For example, consider the statement "For all x, there is some y such that y>x". This statement is true about the integers, so the Integers is a model of this axiom. The Real numbers is also a model of this axiom as is the structure with only one element "x" where x>x. This last example may seem strange, but remember that ">" is just an arbitrary symbol; only the mathematical structure gives it "meaning" by defining which elements are "greater than" which. Logical system: A logical system specifies two things-- First, what statements are permitted and second, under what conditions a given statement may be "deduced" from some other statement(s). First order logic: 1st order logic allows statements using the quantifiers "for all" and "there exists" to range over (talk about) things in the universe being discussed. It is distinguished from second order logic in that second order logic allows the quantifiers to range over statements as well. There are many equivalent sets of rules of deduction for first order logic. Proof (of a statement from a set of axioms): A sequence of statements such that each statement is either an axiom or deducible from previous statements according to the rules of the logical system. Soundness (of a logical system): A logical system is sound if the following holds: Given a set of axioms and a statement which is provable from those axioms, that statement must be true in all models of those axioms. Completeness (of a logical system): A logical system is complete if the following holds: Given a set of axioms and a statement which is true in all models of those axioms, there must be a proof of that statement from those axioms. Completeness (of a set of axioms within a logical system): A set of axioms is complete if any statement (within the allowable language) is either provable or disprovable from those axioms. Consistency (of a set of axioms within a logical system): A set of axioms is consistent if no statement can be both proved and disproved. It is a curious fact that *anything* can be proved (and also disproved) from an inconsistent set of axioms. Recursive (set of axioms): A set of axioms is recursive if there is a Turing machine which, when given an arbitrary statement, can decide whether it is a member of the set of axioms. Note that a finite set of axioms is always recursive ----------------------------Theorems--------------------------------- Soundness: First order logic is sound. This assures us that if we can prove something, then it really does follow from the axioms. Completeness: First order logic is complete; see the definition of completeness of a logical system. This assures us that if some statement is always true whenever our axioms are true, then there is a proof of that statement. Incompleteness: No recursive set of axioms "of sufficient power" can be both complete and consistent. See the definition of completeness of a set of axioms. Here "of sufficient power" means that the axioms allow us to prove some basic facts about number theory which are sufficient to predict the actions of Turing machines and some other details. As a consequence of Soundness and Completeness, we know that a set of axioms has a model if and only if it is consistent. As a consequence of Incompleteness, given any consistent set of axioms "of sufficient power", there will be statements which are neither provable nor disprovable. By the completeness theorem we know that these new statements will be true in some models of the axioms and false in others. Further, the set of such statements must be infinite since otherwise we could add some subset of them to make a complete, recursive consistent set of axioms. ------------------------------Comments-------------------------------- In article <19216@ucbvax.BERKELEY.EDU> kube@cogsci.berkeley.edu.UUCP (Paul Kube) writes: >The upshot of Goedel's incompleteness theorem is the unprovability of >necessarily true statements, i.e., statements true in every model, for >sufficiently powerful systems. This is false in first order logic. By completeness, if a statement is true in all models of our axioms, then it is provable. Statements not provable nor disprovable are always true in some models of the axioms and false in others. In article <435@rlvd.UUCP> ian@pyr-a.UUCP (Tom Gunn) writes: > Paraphrasing Godel on incompleteness: "A formal system is either incomplete >or inconsistent". Taking the example of the predicate calculus, there are >statements that can neither be proven or disproven, but you cannot tell me >how many of them there are, and you cannot prove to me that there are no more >such statements. As long as you are working in first order logic with a recursive set of axioms of "sufficient power", then there will always be an infinite number of such statements. >Thus the system MAY be consistent, but you cannot know that >it is for sure. You may end up with an infinite number of axioms..... As for ending up with an infinite number of axioms, the point is that if you want a complete set of axioms, you will end up with an axiom set that is not only infinite, but non-recursive. This means that you won't always be able to tell whether a given statement is one of your axioms or not. >Someone should have shot Godel at birth. Gauss's father wanted him to be a bricklayer; what did your's want you to be? :-) I believe the posting that started this whole discussion was: >In article <3977@sdcc3.ucsd.EDU>, ma188saa@sdcc3.ucsd.EDU (Steve Bloch) writes: > I just thought of something: a consistent logician cannot believe > in its own consistency IF IT HAS READ GOEDEL. I believe there is a theorem that states that the consistency of a consistent theory cannot be formally proved from those axioms themselves. This, I expect, is what the Mr. Gunn refers to when he states that we cannot know for sure that our system is consistent. We can use one set of axioms to prove the consistency of another, but our first axiom (at least) we must simply assume to be consistent. The above mentioned theorem would be stronger than the version of the incompleteness theorem that I gave. If anyone out there can state this theorem succinctly (and is still awake after reading this article), please post or e-mail it to me. Richard J. Moll Snail mail: ...!ihnp4!umn-cs!moll 1485 East Seventh Street #219 moll@umn-cs.ARPA Saint Paul, MN 55106 moll.umn-cs@csnet-relay.ARPA -- Richard J. Moll Snail mail: ...!ihnp4!umn-cs!moll 1485 East Seventh Street #219 moll@umn-cs.ARPA Saint Paul, MN 55106 moll.umn-cs@csnet-relay.ARPA
franka@mmintl.UUCP (06/09/87)
In article <19216@ucbvax.BERKELEY.EDU> kube@cogsci.berkeley.edu.UUCP (Paul Kube) writes: >The upshot of Goedel's incompleteness theorem is the unprovability of >necessarily true statements, i.e., statements true in every model, for >sufficiently powerful systems. That there are *some* statements your >system can't prove is a good thing: but this is the requirement of >consistency, not completeness. First order predicate calculus is both >consistent and complete. Perhaps; but let us understand that "sufficiently powerful systems" means "second order systems" in this conclusion -- which is not at all the same as the "sufficiently powerful" requirement for the systems to which the incompleteness theorem itself applies to. And even then, every unprovable statement is false in some model if you fudge the definition of "model" a bit. -- Frank Adams ihnp4!philabs!pwa-b!mmintl!franka Ashton-Tate 52 Oakland Ave North E. Hartford, CT 06108