Jim Choate wrote: > > On Wed, 13 Nov 2002, Tyler Durden wrote: > >> Damn what a pack of geeks! (Looks like I might end up liking this list!) >> >> When we say "complete", are we talking about completeness in the Godelian >> sense? According to Godel, and formal system (except for the possibility of >> the oddballs mentioned below--I hadn't heard of this possibility) is >> "incomplete" in that there will exist true statements that can not be proven >> given the axioms of that system. > > Sorry for the long delay...very busy at work. > > As far as I am aware formal language definitions of 'complete' and Godel's > are the same. I've never seen anything from Godel that indicated > otherwise. > > Your comment is almost correct. Complete means that all true statements > can be written (which of course implies that all other statements -must- > be false). Incomplete means there are true statements which can't be > written in the -limited- syntax of the incomplete system (which again > implies there are false statements which can't be made).
Completeness has nothing to do with whether statements can or cannot be expressed within a system. A system is complete if every sentence that is valid within the system can be proved within that system. That is the formal definition, as used by Godel in his completeness theorem, in which he proved that FOPL is complete. The converse, that every provable statement is valid, is known as the Soundness theorem. The formal definition of completeness earlier used by Hilbert, Russell et al was almost identical but involved proving false statements to be false as well*. Godel used the same definition in his more famous incompleteness theorem, in which he proved proved that certain systems of logic, later (the next year iirc) proved to be those systems that allow Peano counting, cannot be both complete and consistent. FYI, consistent: no sentence can be proved both valid and false within a consistent system. -- Peter Fairbrother *I assume, I'm not that good at history of mathematics. Godel's completeness theorem also proved that his definition is all that is needed.
