Thank you (was Re: Should I learn Python or Java?)

[Moshe Zadka]

On Mon, 8 Jan 2001 14:49:00 -0600, "Doug Ball" <doug at postsmart.net> wrote:

> Dear Peter and list:
> 
> Peter you mentioned in a posting:
> 
> "I don't think I know of any language without warts, and
> I think there's a theory (from Hofstadter? (sp?)) that
> says you can't have a theory that is both consistent and
> complete."
> 
> I am a big fan of such things and was excited to see you mention it.
> However I think you may be referring to Godel's Theorem.
> 
> If anyone is interested in this topic there is an excellent book entitled
> "Godel, Escher, Bach: an Eternal Golden Braid" by Douglas R. Hofstadter.  In
> his book, Dr. Hofstadter  restates Godel's theorem as: " All consistent
> axiomatic formulations of number theory include undecidable propositions."

Thanks for the clarification!
The "number theory" part is important -- you can have theories which
are both consistent and complete.
Two easy examples, one not so easy example
1. The theory of dense linear orders without minimum or maximum
2. The theory of complex numbers
3. [Hard!] The theory of real numbers

In fact, the proofs in 1+2 are very similar, but a bit painful: what you
prove is that every formula in the theory of linear orders/fields is
equivalent to an existential formula. Then you prove that the additions
of enough "solutions" makes every existential formula equivalent to
quantifier free formula. since the only qunatifier free statements
are either tautologies or contradictions, QED.

3 is similar, but proving that in the theory of ordered fields every
forumla is existential is considerably harder.

on-topic-ly y'rs, Z.
-- 
Moshe Zadka <sig at zadka.site.co.il>
This is a signature anti-virus. 
Please stop the spread of signature viruses!