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.