[LINK] Cantor's theorem, the prisoner's dilemma, and the halting problem

post by Qiaochu_Yuan · 2013-06-30T20:26:03.002Z · LW · GW · Legacy · 9 comments

Contents

9 comments

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. 

9 comments

Comments sorted by top scores.

comment by AlexMennen · 2013-07-01T15:42:20.004Z · LW(p) · GW(p)

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.

Replies from: Qiaochu_Yuan
↑ comment by Qiaochu_Yuan · 2013-07-01T18:52:55.480Z · LW(p) · GW(p)

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.

comment by Quinn · 2013-06-30T23:05:41.086Z · LW(p) · GW(p)

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.

comment by [deleted] · 2013-07-03T08:08:33.770Z · LW(p) · GW(p)

Why do "many non-mathematicians" find Cantor's theorem hard to believe?

Replies from: Qiaochu_Yuan
↑ comment by Qiaochu_Yuan · 2013-07-03T08:51:38.695Z · LW(p) · GW(p)

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.

Replies from: Anatoly_Vorobey, None
↑ comment by Anatoly_Vorobey · 2013-07-04T17:49:18.462Z · LW(p) · GW(p)

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

Replies from: Tyrrell_McAllister
↑ comment by Tyrrell_McAllister · 2013-07-05T16:42:47.160Z · LW(p) · GW(p)

Thank you for the interesting link.

↑ comment by [deleted] · 2013-07-05T04:20:36.127Z · LW(p) · GW(p)

But if this is an indirect way of saying "please provide some evidence for this claim,

Sorry, it wasn't. I was just curious if you had any info.

comment by Paul Crowley (ciphergoth) · 2013-07-01T06:32:35.218Z · LW(p) · GW(p)

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."