We have some sort of machine that prints out statements in some sort of language. It needn't be a statement-printing machine exactly; it could be some sort of technique for taking statements and deciding if they are true. But let's think of it as a machine that prints out statements.
In particular, some of the statements that the machine might (or might not) print look like these:
P*x (which means that the machine will print x)
NP*x (which means that the machine will never print x)
PR*x (which means that the machine will print xx)
NPR*x (which means that the machine will never print xx)
For example, NPR*FOO means that the machine will never print FOOFOO. NP*FOOFOO means the same thing. So far, so good.
Now, let's consider the statement NPR*NPR*. This statement asserts that the machine will never print NPR*NPR*.
Either the machine prints NPR*NPR*, or it never prints NPR*NPR*.
If the machine prints NPR*NPR*, it has printed a false statement. But if the machine never prints NPR*NPR*, then NPR*NPR* is a true statement that the machine never prints.
So either the machine sometimes prints false statements, or there are true statements that it never prints.
So any machine that prints only true statements must fail to print some true statements.
Or conversely, any machine that prints every possible true statement must print some false statements too.
Pessimism of the Intellect, Optimism of the Will Favorite posts | Manifold podcast | Twitter: @hsu_steve
Wednesday, November 23, 2011
Godel's proof, compressed
I found this here, but it is originally due to Raymond Smullyan. I first learned about Godel's theorem when I read Douglas Hofstader's book Godel, Escher, Bach in high school. I still remember lugging the thick volume around in my backpack, and working through the early chapters on predicate logic. This treatment is much more compact! :^)
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.
ReplyDeleteHawking 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
ReplyDeleteWell, 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?
ReplyDeleteThis 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.
ReplyDeleteThat sentence is not in the language: it isn't well-formed.
ReplyDeleteIt'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).
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?
ReplyDeleteBrings to mind George Boolos's "Gödel's second incompleteness theorem explained in words of one syllable," Mind 103: 1-3 (1994).
ReplyDeletewww2.kenyon.edu/Depts/Math/Milnikel/boolos-godel.pdf