ian@oravax.UUCP (Ian Sutherland) (05/02/91)
In article <19592@cs.utexas.edu> turpin@cs.utexas.edu (Russell Turpin) writes: >I have found that the terminology involved also confuses some >people. In logic, one calls a theory undecidable if there is >a proposition P such that neither P nor ~P is provable in the >theory. Perhaps some people use "undecidable" this way, but that was not what I was taught. The notion you call "undecidable" above, I was taught to call "incomplete", and an "undecidable" theory was one whose set of theorems is not recursive. I believe this usage is standard; most logicians I know use the same terminology I do. >By extension, such a sentence is sometimes said to be >undecidable in the concerned theory. I was taught to call such sentences "independent of" the theory in question. -- Ian Sutherland ian@cambridge.oracorp.com Sans peur
unx20491@unx2.ucc.okstate.edu (Inscrutable Eric) (05/14/91)
In article <2285@oravax.UUCP> ian@oravax.odyssey.UUCP (Ian Sutherland) writes: >In article <19592@cs.utexas.edu> turpin@cs.utexas.edu (Russell Turpin) writes: >>I have found that the terminology involved also confuses some >>people. In logic, one calls a theory undecidable if there is >>a proposition P such that neither P nor ~P is provable in the >>theory. > >Perhaps some people use "undecidable" this way, but that was not what I >was taught. The notion you call "undecidable" above, I was taught to >call "incomplete", and an "undecidable" theory was one whose set of >theorems is not recursive. I believe this usage is standard; most >logicians I know use the same terminology I do. > >>By extension, such a sentence is sometimes said to be >>undecidable in the concerned theory. > >I was taught to call such sentences "independent of" the theory in >question. >-- Kurt Godel in a rather bold and daring move published a short :) work early in this century on the undecidability of certain propositions in formalized languages. In this context, undecidable was used to mean a statement in a formal system that could neither be proven true nor proven not true within the propositions and axioms of that particular system. It is true that such a sentence is independent of the system. In fact the sentence would never be proven to be within or without the set of true sentences in the system through recursive application of the axioms of the system. Thus the sentence would be independent of the system and its inclusion amongst the set of true statements would be an undecidable proposition. Since the sentence or its negation could, either one, be included as another axiom of an expanded formal system (ostensibly so all true theorems could be proven from the axioms), their independence from the system is brought further to light. An example of such an incomplete formal system (as if they all weren't) would be Euclid's first three postulates. This set excludes the much debated "Parallel Postulate." As Euclid showed, his formulation of the Geometry is consistent and well-formed in the sense that it does not produce its own logical self-contradictions. However, as Gauss, Lobachevsky and others have shown, the "negations" of that fourth postulate also produce consistent and well-formed Geometries. Thus the "Parallel Postulate" is undecidable with respect to the first three postulates (else some contradiction would have appeared in Euclidean or non-Euclidean Geometries) and the formal system of the first three postulates is incomplete with respect to the "Parallel Postulate." Now to the point: You both are describing similar situations when you use "undecidable" or "incomplete" as described WAY back there. However, you're describing it from different ends of the thing. To wit: An "incomplete" formal system has "undecidable" propositions. ------------------------------------------------------------------------ "I call myself `'d' Kidd,' because no one else will." unx20491@unx2.ucc.okstate.edu (Eric Gindrup) God created a countable infinity of numbers. All else is the work of consistent people. "Consistency is the hobgoblin of little minds." -- --------------------------------------------------------------------- "I call myself `'d' Kidd,' because no one else will." -- Me. unx20491@unx2.ucc.okstate.edu (Eric Gindrup) God created a countable infinity of numbers. All else is the work of