[LINK] Cantor’s theorem, the prisoner’s dilemma, and the halting problem
I wouldn’t normally link to a post from my math blog here, but it concerns a cute interpretation of Cantor’s theorem that showed up when I was thinking about program equilibria at the April MIRI workshop, so I thought it might be of interest here (e.g. if you’re trying to persuade a mathematically inclined friend of yours to attend a future workshop). A short proof of the undecidability of the halting problem falls out as a bonus.
Typo in the first proof of Cantor’s theorem (you got in vs not in mixed up in the second case).
I hadn’t noticed before that Cantor’s theorem and Russell’s paradox were exactly the same argument. This makes me curious as to how Cantor failed to notice Russell’s paradox.
Edit: It appears that Cantor actually did figure out that Cantor’s theorem leads to things like Russell’s paradox in 1899, two years before Russell did.
Thanks for the correction! I think the main impediment to noticing Russell’s paradox was having the idea that something like that existed to be noticed.
Of course, when you ignore the payoff matrix, the argument is no longer really about the Prisoner’s Dilemma (and so I don’t know that it’s fair to accuse the barber paradox of having a lot of extra cruft not present in the PD formulation).
But I agree that this is a cute presentation of diagonal arguments in culturally relevant terms. A fun read.
Why do “many non-mathematicians” find Cantor’s theorem hard to believe?
I don’t know! Maybe the idea of mathematicians telling them they can’t do something is offensive to them. But if this is an indirect way of saying “please provide some evidence for this claim,” here’s some such evidence.
I think your references do not reference Hodges’ thoughtful article on Cantor cranks (I may be wrong, as I only scanned them briefly), so allow me to recommend it: http://www.math.ucla.edu/~asl/bsl/0401/0401-001.ps
Thank you for the interesting link.
Sorry, it wasn’t. I was just curious if you had any info.
This isn’t about the “meat” of your post, but: for someone who’s finding Cantor’s theorem hard to believe, it might be worth avoiding proof by contradiction, which can be confusing. I’d rather say “Let f be any element of (2^X)^X. Define S_f(x) = 1 - f(x)(x). Then for any x, f(x)(x) != S_f(x), which means f(x) != S_f. So for every f, there’s an S_f such that there’s no x that represents it.”