About Me

My photo

Wednesday, November 23, 2011

Godel's proof, compressed













silkop said...

In other news, the sentence "this is not a true sentence" seems neither true nor false, but it has to be. A mathematician's mind boggles and experiences some sort of awe and revelation while everyone else shrugs off the self-referential silliness and goes on about their business.

Justin Loe said...

Hawking made an interesting comment in a speech I found on the internet. Since this is not my field, I'm not weighing in with an opinion on its merits: " Instead, we and our models, are both part of the universe we are describing. Thus a physical theory, is self referencing, like in Gödel’s theorem. One might therefore expect it to be either inconsistent, or incomplete. The theories we have so far, are ~both inconsistent, and incomplete." http://www.physics.sfasu.edu/astro/news/20030308news%5CStephenHawking20030308.htm

RKU1 said...

Well, I'm no logician, but is it necessarily the case that a given sentence need be true or false?  Consider the sentence "Purple dinner vertical bloog-bloog"---is it true or false?  And if we accept the existence of meaningless or indeterminant sentences, does that not eliminate the paradox?

MtMoru said...

This is Godel's theorem in the language of the theory of computation. In the language of mathematical logic the theorem holds only for first order quantification. If quantification over sets is permitted elementary number theory is complete.

Christopher Chang said...

That sentence is not in the language: it isn't well-formed.

It's worth explicitly pointing out that the proof requires that a "NPR*x" construction exists in the language.  Much of Godel's proof involves the technical details of this construction (in languages powerful enough to express number theory).

silkop said...

Are you saying that Gödel's proof is more than observing that if you try to pull out the rug on which you are standing you will fall flat on your nose? Is his proof more significant than or equivalent to the halting problem in CS?

Graeme Wood said...

Brings to mind George Boolos's "Gödel's second incompleteness theorem explained in words of one syllable," Mind 103: 1-3 (1994).


Blog Archive