[OFFTOPIC] Goedel and the mathematic (was: Re: Copyright from the lcs-projekt!? [dwarf@polaris.net: Re: First cut at testing and validation]

Hello,

[warning, this is getting off topic fast]

On Sat, Aug 15, 1998 at 10:42:14AM +0100, Philip Hands wrote:
>
> Are you familiar with Godel's Theorem ?
>
>   When defining a mathematical system, you eventually get down to some
>   definitions that are neither provable, or disprovable within the system

You are confusing two things there, the axioms and the theorems. axioms are
not proofed by definition, they are defined and good is. The you have some
rules how to draw conclusions from the axioms. If you apply them, you get
theorems.

Goedels theorem itself says, that every axiomatic constructions of number
theory that is free of contradictions contains theorems where you can't
decide if they are true or false.

The difference from what you said above is subtle, but meaningful. First,
the system needs to contain a significant amount of complexity, and it is
necessary that it does not contain contradictions. And, more important,
it is not a "definition" that is neither provable nor disprovable (definitions
are "true" by definition), but theorems. This is surprising, as
the mathemticians had the hope that every theorem could be either proved or
disproved. That this is not true is the essence of Goedels theorem.

There is a whole in the mathematic, and you can't repair it. But it is hard
to give examples of such theorems. In fact, Goedel proofed his theorem by
constructing such a number theory and a theorem that can't be poved or
disproved.

>   (1 = 1'' in arithmetic for example).

It's a pity that it is not so easy. Instead Goedels theorem is pretty
weired, and you can't give any easy example of such a theorem. maybe an
example is the theorem, that there is no set with a cardinality between the
cardinality of the set of real numbers and the set of all subsets of the set
of real numbers (is somebody still reading here :). At least it was proved
that this theorem can neither be proved nor disproved.

I don't know if this has still something to do with the topic, but it was
fun for me to look up, and maybe some of you have had fun reading it.

Thank you,
Marcus

Here is Goedels theorem in its original version (and a bad translation by
me) (\ny is the greek letter n, I don't remember if \ny is correct TeX for
this) (Neg is negotiation).

"Zu jeder \omega-widerspruchsfreien rekursiven Klasse \kappa von
{\em Formeln\/} gibt es rekursive {\em Klassenzeichen\/} r, so daß weder
\ny Gen r noch Neg(\ny Gen r) zu Flg(\kappa) gehört (wobei \ny die frei
Variable aus r ist)."

"To everybody \omega-contradiction free recursive class \kappa of formulas
exists a recursive class sign r, so that neither \ny Gen r nor Neg(\ny Gen r)
belongs to Flg(\kappa) (where \ny is the free variable of r)."

--
"Rhubarb is no Egyptian god."        Debian GNU/Linux        finger brinkmd@
Marcus Brinkmann                   http://www.debian.org    master.debian.org
Marcus.Brinkmann@ruhr-uni-bochum.de                        for public  PGP Key
http://homepage.ruhr-uni-bochum.de/Marcus.Brinkmann/       PGP Key ID 36E7CD09