University of Virginia Computer Science CS150: Computer Science, Fall 2005 |
(none) 17 October 2005 |
Axiomatic System — a formal system that attempts to codify a branch of knowledge into axioms and inference rules that produce all true statements.
What does it mean for an axiomatic system to be incomplete?
What does it mean for an axiomatic system to be inconsistent?
What can we say about an axiomatic system that is complete and
consistent?
Undecidable — a statement is undecidable in a given axiomatic system if it cannot be proven either true or false inside that system.
Russell's Paradox
S is the set of all sets that are not members of themselves.Gödel's Incompleteness Theorem: All logical systems of any complexity are incomplete: there are statements that are true that cannot be proven within the system. Gödel's Proof: (condensed)
Is S a member of itself?If S is an element of S, then S is a member of itself and should not be in S. If S is not an element of S, then S is not a member of itself, and should be in S.
In connection with the interview for his US citizenship, Gödel once told me
that for this occasion he had studied how the Indians had come to
America. Einstein and O.Morgenstern were his witnesses, and Morgenstern
has told different people about aspects of the event. The following
account is given by H-Zemanek and E.Kvhler. Even though the
routine examination G was to take was an easy matter, G prepared
seriously for it and studied the US Constitution carefully. On the day
before the interview G told Morgenstern that he had discovered a
logical-legal possibility of transforming the United States into a
dictatorship. Morgenstern saw that the hypothetical possibility and its
likely remedy involved a complex chain of reasoning and was clearly not
suitable for consideration at the interview. He urged G to keep quiet
about his discovery. The next morning Morgenstern drove Einstein and G
from Princeton to Trenton. Einstein was informed; on the way he told one
tale after another, to divert G from his Constitution-theoretical
explanations, apparently with success. At the office in Trenton, the
official in charge was Judge Philip Forman, who had inducted Einstein in
1940 and struck up a friendship with him. He greeted them warmly and
invited all three to attend the (normally private) examination of G.
The judge began, "You have German citizenship up to now." G interrupted
him, "Excuse me sir, Austrian." "Anyhow, the wicked dictator! but
fortunately that is not possible in America." "On the contrary," G
interjected, "I know how that can happen." All three joined forces to
restrain G so as to turn to the routine examination.
From Hao Wang, Reflections on Kurt Gödel.
Years ago, the Princeton physicist John Wheeler began to wonder whether
Heisenberg's uncertainty principle might not have some deep connection
to Gödel's incompleteness theorem (probably the second most
misunderstood discovery of the 20th century). Both, after all, seem to
place inherent limits on what it is possible to know. But such
speculation can be dangerous. "Well, one day [Wheeler recounts] I was at
the Institute of Advanced Study, and I went to Gödel's office, and there
was Gödel. It was winter and Gödel had an electric heater and had his
legs wrapped in a blanket. I said, 'Professor Gödel, what connection do
you see between your incompleteness theorem and Heisenberg's uncertainty
principle?' And Gödel got angry and threw me out of his office."
Jim Holt, Uncertainty About the Uncertainty Principle:
Can't anybody get Heisenberg's big idea right?,
Slate, 6 March 2002.
CS 150: Computer Science University of Virginia |
evans@cs.virginia.edu Using these Materials |