ping Xanthian was Re: Wikipedia on "Decision Problems"

From: artist formally known as |-|erc (h_at_r.c)
Date: 12/22/04 

Date: Wed, 22 Dec 2004 13:47:12 +1000

> > Here is a link to the Wikipedia article:
> >
> > http://en.wikipedia.org/wiki/Decision_problem
>
> The article on the incompleteness theorems needs some work as well:
>
> "In any consistent formalization of mathematics that is sufficiently
> strong to axiomatize the natural numbers -- that is, sufficiently strong
> to define the operations that collectively define the natural numbers --
> one can construct a statement that can be neither proved nor disproved
> within that system."
>
> "Gödel's theorems are theorems in first-order logic, and must ultimately
> be understood in that context."
>
> "What Gödel showed is that in most cases, such as in number theory or real
> analysis, you can never discover the complete list of axioms. Each time
> you add a statement as an axiom, there will always be another statement
> out of reach."
>
> "In first-order logic, theorems are recursively enumerable: you can
> write a computer program that will eventually generate any valid proof."
>
> "The theorem only applies to systems that allow you to define the
> natural numbers as a set. It is not sufficient that the system contain
> the natural numbers. You must also be able to express the concept "x is
> a natural number" using your axioms and first-order logic. There are
> plenty of systems that contain the natural numbers and are complete. For
> example, both the real numbers and complex numbers have complete
> axiomatizations."
>
> I've been hoping a sufficiently motivated expert would fix it one of
> these days.

Xanthian? do you want to correct this godel summary? see if your reputation of
explaining godel is justified.

Herc

Quantcast