- A new proof of Godel's incompleteness theorem that resembles the Surprise Exam Paradox. This is EXACTLY the kind of thing I was looking for.
- An argument that suggests that Godel's incompleteness theorem can be used to resolve the paradox.
Monday, February 28, 2011
Interesting Math related to the Unexpected Hanging Paradox
In a
prior post
I pondered if there was interesting MATH that relates to the
Unexpected Hanging Paradox.
At the time none of the comments really had any and, alas, I thought there was not.
(Thought looking back at the comments, the first one by Jeffe may be relevant.)
But recently Ran Raz emailed me a pointer to this paper by Kritchman and Raz:
The Surprise Examination Paradox and the Second Incompleteness Theorem.
See also
this post by Sam Alexander which explains some
of the paper very well.
The paper contains the following:
Subscribe to:
Post Comments (Atom)
Thanks for the link. By the way, Timothy Chow offers some great insight into what it means to "resolve a paradox" (in general), quite readable and well-worth reading, in his 1998 survey on the paradox: http://www-math.mit.edu/~tchow/unexpected.pdf
ReplyDeleteKritchman and Raz is a great paper. They take what Chow calls the "logical school" approach to the paradox. Another is the epistemological, where instead of using provability predicates, one uses non-classical knowledge connectives: if phi is a well-formed formula then so is K(phi), which means "phi is known". In my view, the trick K&R use translates nicely to the epistemological school where it provides evidence for throwing out the assumption that infallible knowers know their infallibility: reject K(K(phi)->phi) and not just this paradox but many others dissolve. There is some deep math here (even involving ordinal arithmetic and reflection principles of ZF) but it goes beyond the scope of this comment ;)
To me, the interesting thing about the paradox is the slippery nature of the English word "surprise". Once you mathematically define what the word "surprise" means (that definition which may not correspond to how people actually use the word), not only does the paradox disappear, but so does the reason it was interesting in the first place.
ReplyDeleteWe have an induction, so the conclusion is going to be determined by the base case, i.e., what happens at 1pm on Friday, the final day. Specify that and everything else becomes clear.
ReplyDeleteThere are two variables: what the prisoner knows/expects and whether he is hanged or not.
If the prisoner *must* be hanged, then the prisoner will know this when 1pm on Friday rolls around. Does he get hanged? The answer will define the base case.
If he gets hanged at 1pm on Friday then the premise that it can't happen if the prisoner knows/expects it to happen is violated. If he is set free then the premise that he must be hanged is violated. The paradox is then revealed to be an obvious contradiction of premises which renders our base case undefined and no induction is possible.
Godel-Russell problems only arise with the enforcement of the two premises at 1pm on Friday: if the prisoner knows he is going to be hanged then he must be set free, but if he is set free then his knowledge that he would be hanged was wrong ergo he will be surprised if he is in fact hanged. It's just an example of a "this statement is false" paradox that has been well-studied.
It seems to me that this way of looking at the problem does resolve the paradox in the sense that it clearly pinpoints the contradictory assumptions and how that contradiction short-circuits the purported induction.
Random Thought:
ReplyDeleteYou have Zeno's Paradox about space -does the arrow ever reach the target?
With the Hanging Paradox, the emphasis is on time and the prisoner's state of mind - does the sentence get carried out as predicted by the judge?
On a superficial level:
From the judge's point of view, the answer is "Yes". Surprise = "pop quiz", the prisoner did not know the scheduled time until it happened.
If the prisoner calculates the probability of being executed, then from his point of view the answer is "No": the longer he survives the less surprising is his fate.
Moral of the story on an informal level: "Growing old ain't fun, but it beats the alternative."
This is an excellent example of the deep seated methodological and organizational failures of modern analytic philosophy.
ReplyDeleteTHERE IS NO SURPRISE QUIZ/HANGING PARADOX (and while better than most this paper is yet another one that fails to notice this). I'll explain in detail below but just think about it for two seconds and try to find an interpretation for surprise where you are both convinced it will occur while still admitting the reasoning that entails no surprise can occur.
I'll admit when I first heard it as an undergrad I was puzzled but the first time I ever sat down and thought about it for more than a few minutes it became clear why it struck me as problematic despite possing no real problems.
Obviously if "the hanging/quiz will be a surprise" merely asserts the victims will be in a psychological state of surprise there is absolutely no issue. Our psychological states of surprise obviously don't track what we can or can't prove via long chains of reasoning. In this case there is no paradox since there are no real constraints on when we can FEEL surprised.
The statement seems disturbing because we naturally take "the hanging/quiz will be a surprise" to be shorthand for "the hanging/quiz would be a surprise for an ideally rational agent and since we don't really understand that notion because it doesn't make much sense we tend to just replace it with some vague idea about being able to prove the test will occur that morning. Now such a reasoning system seems to require it incorporate it's own proof predicate but it may be simple enough to do this without the normal contradiction of Lob's theorem.
Now either this proof system lets the victims infer the test/hanging will occur no day that week and thus as it's inconsistant that it will occur every day or it doesn't let them infer it will occur no day that week. Both cases are unremarkable. If the system is inconsistent then it's not a problem that the victims can prove they will be hung/quizzed each day as well as that they won't be. If the system is consistent than it doesn't capture the supposedly paradoxical reasoning that let us infer there would be no surprise quiz. Ok that's fine then too.
The problem with modern analytic philosophy is that I'm sure hundreds of really smart people realized this about the surprise quiz/hanging right away but rather than causing the paradox to be checked off as solved it just leaves only those who are still suffering from the simple confusion about interpreting surprise to write papers about it. It's the same way that no one with half a brain is going to write a serious paper about the validity of the ontological argument so the papers that appear will be written by those who are still confused.
======
At a math of physics conference if you tried to get up and badly resolve a solved problem you would be told the problem was solved, you are confused and need to withdraw your paper on it. Philosophers need to do this too but as long as they are willing to pretend Heidegger scholars and other contenentalists are engaged in a valid academic (as opposed to merely aesthetic) endeavor you can't expect the needed self-correction to occur.
This is said because there are a lot of important paradoxes we still haven't figured out where we are getting confused.
@JKU
ReplyDeleteThe closest thing to Godel's theorem in here might be the non-existance of any reasonable proof system that is both strong enough to allow the induction and yet accurately reasons about what that very system can prove. Lob's theorem says you can't have a proof predicate for any sufficently complex theory and sufficently complex was pretty weak if I remember.
See
ReplyDeletehttp://scholar.google.com/scholar?cluster=16749936485459308343&hl=en&as_sdt=0,44
Thanks for the pointer Moshe.
ReplyDeleteAn interesting thing in the article is the historical note that the paradox was first circulated by word of mouth in the 1940's.
Prisoners who survived the SS and/or Gestapo reported being given death sentences with an indefinite time of execution as part of the psychological torture.
One strategy was to put a group of prisoners together and then execute one a day just to play mind games with the rest.
An extra degree of cruel and unusual punishment, so to speak.
TruePath, Thanks for the pointer to Lob's Theorem.
ReplyDeleteI just bought a book "God Created the Integers" edited by Stephen Hawking of black hole fame because I was curious about the title.
The title comes from a quote by a 19th century mathematician Leopold Kronecker: "God created the integers. All the rest is the work of Man."
The "subjective feeling" is that paradoxes don't really exist in the grand scheme of things.
Is there a more natural way to navigate the integers without using a man-made (paradoxical) Arithmetic?
Food for thought, so to speak.
The file is damaged,it can not be opened now.
ReplyDeleteSuch is the reply,when I try to read the pdf file.
wang xiuli
This comment has been removed by the author.
ReplyDeleteWang- I tried all three links on the post and they all seem to work. EMAIL me your issue and I'll see whats up
ReplyDeletegasarch@cs.umd.edu
Mr.Gasarch
ReplyDeleteThe problem is caused by the proxy .I have fixed it .
Thank you
Wang Xiuli