This post is about an elementary result from mathematical logic (due to Stephen Yablo in the early 1990’s) that I think deserves to better known.
I’d always assumed that “Russell-like” logical paradoxes (e.g. the inability to assign either a true or a false value to the statement “this sentence is false”, or to the statement “the collection of collections that don’t contain themselves contains itself”) required circular self-reference. Apparently not, provided you use an infinite number of statements.
The construction is simple: consider an infinite sequence of sentences where is
is false for all
If you want to see the details of why this is problematic, it’s in the paper “Paradox Without Self Reference” available at http://www.mit.edu/~yablo/pwsr.pdf But I think it’s more fun to figure it out for yourself, and it’s not that hard. The difficulty was in realizing that the result was possible (I didn’t realize it, and I had more than enough mathematical training to do so before the paper was published), not in proving it.
In you really want to see an argument for why there’s a paradox, I’ll provide one here that’s slightly different in unimportant details only from the one in the paper. Firstly, we prove that for all , is false. Assume that for some we have that is true. Then we immediately have that is false. So there is a for which is true: which of course trivially implies that there is a for which is true. And so is false. This contradicts the starting assumption that is true, and so the only possibility is that for all we have that is false. But, if is false for all , then that implies that is true (in fact, it also implies that is true for all ). And there’s the paradox.
And, as a check, it’s worth considering what goes wrong with creating a paradox when there’s only a finite number, say , of statements . If we could show that all the are false, then we would still be able to conclude that is true and the paradox is there. But the argument for all the statements being false breaks down at i.e. for , since there is no that has to be false if is true. So, setting to false and to true is a valid assignment, and there’s no paradox.
The paper is extremely short: 2 pages with double spacing (it could easily fit on one page with single spacing). And despite what I said earlier about not reading it before trying to figure out the paradox for yourself, I certainly do recommend reading it. It shouldn’t require saying, but just to be explicit, if the choice is to either read this blog post, or to read the original paper, it’s a no brainer: read the original paper! There’s many reasons for that, but the most important one is that Stephen Yablo provides context that I’m skipping in this blog post.
The paper is a great candidate for Fermat’s library http://fermatslibrary.com/ (which just like Stephen Yablo’s result deserves to be better known). I nominated it for inclusion a week ago.