Paradox Without Self Reference

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 S_1, S_2, S_3,\ldots where S_i is

S_j is false for all j \textgreater i

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 n, S_n is false. Assume that for some n \geqslant 1 we have that S_n is true. Then we immediately have that S_{n+1} is false. So there is a j \textgreater n+1 for which S_j is true: which of course trivially implies that there is a j \textgreater n for which S_j is true. And so S_n is false. This contradicts the starting assumption that S_n is true, and so the only possibility is that for all n we have that S_n is false. But, if S_n is false for all n, then that implies that S_1 is true (in fact, it also implies that S_m is true for all m). 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 N \geqslant 2, of statements S_n. If we could show that all the S_n are false, then we would still be able to conclude that S_1 is true and the paradox is there. But the argument for all the statements being false breaks down at S_N i.e. for n=N, since there is no S_{N+1} that has to be false if S_N is true. So, setting S_1, S_2, \ldots S_{N-1} to false and S_N 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.

Author: Walter Vannini

Hi, I'm Walter Vannini. I'm a computer programmer and I'm based in the San Francisco Bay Area. Before I wrote software, I was a mathematics professor. I think about math, computer science, and related fields all the time, and this blog is one of my outlets. I can be reached via walterv at gbbservices dot com.

Leave a Reply

Your email address will not be published.