A liar without a loop

“This sentence is false.” If it is true, then what it says holds, so it is false; if it is false, then what it says fails, so it is true. The liar has no consistent truth value, and every famous paradox of its family — Russell’s set of all sets that do not contain themselves, Grelling’s word ‘heterological’, Gödel’s sentence that says it has no proof — shares one feature with it. Each refers to itself, directly or through a loop, and it was natural to think that self-reference was the culprit: forbid a sentence from talking, however indirectly, about itself, and the paradoxes of truth would go away.

In 1993 Stephen Yablo published a two-page paper showing that this is not enough. Take an infinite list of sentences $S_1, S_2, S_3, \ldots$, where

$S_n$: for every $k > n$, $S_k$ is false.

No sentence mentions itself, and no sentence mentions an earlier one, so there is no loop of reference anywhere. And yet no assignment of true and false to the sentences is consistent with what they say.

Two steps each way #

Suppose some sentence, $S_n$, is true. Then what it says holds: every sentence after it is false. In particular $S_{n+1}$ is false. But every sentence after $S_{n+1}$ is also after $S_n$, so every one of them is false — which is exactly what $S_{n+1}$ says. So $S_{n+1}$ is true, contradicting what was just derived. No sentence can be true.

So every sentence is false. Then, in particular, every sentence after $S_1$ is false, which is what $S_1$ says; so $S_1$ is true. Contradiction again.

The figure lays the two halves out as rows of truth values. What is worth noticing is that no step looks backward. The first half uses only that $S_{n+1}$ talks about a subset of what $S_n$ talks about; the second half uses only that $S_1$ talks about everything after it. Neither half needs a sentence to say anything about itself.

Cut the list off, and the paradox disappears #

Truncate the list after $N$ sentences, so that $S_n$ says that every later sentence up to $S_N$ is false. Now there is a last sentence, $S_N$, and it says something about no sentences at all: “every sentence after me is false” is vacuously true. Then $S_{N-1}$, which denies $S_N$, is false; so is $S_{N-2}$, which denies $S_N$ among others; and so on. The truncated list has a consistent assignment, all false but the last.

It has exactly one. Testing all $2^N$ assignments for $N$ from 1 to 14 finds a single consistent one every time — 16,384 assignments tried at $N = 14$, one survivor — and it is always the one just described. The figure shows the first twelve. The single true sentence sits at the end of the list, wherever the end is.

That is where the paradox comes from. Make the list longer and the true sentence moves to the new end. There is no position at which it stays: for any fixed $n$, the value of $S_n$ is true only for the one list that stops at $n$, and false for every longer one. So the assignments of the finite lists converge, position by position, to “all false” — and “all false” is precisely the assignment the argument rules out for the infinite list. The finite solutions exist, they converge, and their limit is not a solution. Anyone who has met a limit that forgets to be continuous will recognise the shape.

Why a finite list without a loop never fails #

The truncated lists have a consistent assignment for a reason that has nothing to do with Yablo’s particular sentences. Take any finite system of sentences, each of which says that some truth function of other sentences holds, and suppose that the references form no loop. Then some sentence mentions no other sentence at all — otherwise, following references from sentence to sentence would eventually revisit one, making a loop. That sentence’s value is fixed outright. Remove it and repeat: the remaining system again has no loop, so again some sentence depends only on sentences already settled. Every value is forced, one at a time, and there is exactly one consistent assignment.

The figure tests this on random systems. Each of eight sentences is a random truth function of one to three others — true when the third sentence is false or the fifth is true, say. When every sentence mentions only later ones, all 3,000 systems have exactly one consistent assignment, as the argument requires. When sentences may mention any others, including themselves, loops appear, and the number of consistent assignments ranges from none — 1,259 of the 3,000 systems are paradoxical — to as many as eight. Paradox and over-determination both live in loops.

This is the theorem that made self-reference look like the culprit, and it is correct for finite systems. Yablo’s list satisfies its hypothesis locally — no loops — and fails its conclusion. The step that breaks is “some sentence mentions no other sentence”. In Yablo’s list every sentence mentions infinitely many others; there is no sentence to evaluate first, and the evaluation never starts. The reference relation is not well-founded: there is an infinite chain $S_1 \to S_2 \to S_3 \to \cdots$, each step a reference, with no end. The real condition for a system to be safe from paradox is not “no loops” but “no infinite descending chain of references”, and loops are only the finite way of having one.

Loops, odd and even #

The same counting can be done for the loops themselves, which makes the comparison sharp. Put $n$ sentences in a ring, each saying that the next one round is false. When the ring is even, true and false alternate and there are two consistent assignments; when it is odd, the alternation cannot close up, and there are none. The single liar is the ring of length one.

Change the claim so that each sentence in the ring says that all the others are false, and the picture changes again: exactly one sentence can be true, any one of them, so a ring of $n$ has $n$ assignments. Loops can be paradoxical or not, depending on what the sentences say about each other. What a finite loop-free system cannot be is anything but determined.

Six lists, and which ones fail #

Yablo’s list is one of many infinite lists in which each sentence refers only to later ones, and running through a few of them shows which feature produces the paradox. The test for the infinite lists is a search: every assignment that is eventually periodic — a stretch of up to six values followed by a block of up to six repeated for ever — is checked against every sentence, which is possible because a quantifier over all later sentences of such an assignment can be decided by looking at the rest of the stretch and one full block. That is 16,002 descriptions of assignments for each list.

All six lists, at every finite length, have exactly one consistent assignment, as the loop-free theorem says they must. The infinite lists differ. When each sentence says that the next one is false, there are two consistent assignments, alternating true and false, starting either way. When each says that the next two are both false, or that one of the next two is false, there are three each, periodic with period three. When each says that every later sentence is true, there are two — all true and all false — which is the truth-teller, “this sentence is true”, spread out along the list. Only the two lists that quantify over all later sentences — every one false, or some one false — have none.

Those are the lists in which each sentence depends on the whole infinite tail. A rule that looks a fixed distance ahead is a finite-state rule, and a sequence that obeys it can be built step by step, backwards from any periodic pattern; a rule that looks at the whole tail can ask a question about the limit, and the limit is where the finite solutions vanish. The search covers only eventually periodic assignments, so for the infinite lists it shows what it finds, not that nothing else exists. For Yablo’s list and its dual the argument above proves there is nothing at all.

When finite consistency does carry over #

The failure of the limit is not inevitable, and the cases where it does not happen explain the cases where it does. Consider the lists that look a fixed distance ahead, such as “the next two sentences are both false”. Each finite truncation has a consistent assignment, and the infinite list has one too. That is not luck. A rule that mentions only the next few sentences is a local constraint, and for local constraints there is a general theorem: if every finite piece can be satisfied, the whole infinite system can. The proof is the one in an infinite tree with an infinite path. Arrange the consistent assignments of the first $N$ sentences, for every $N$, into a tree in which each assignment of length $N + 1$ sits below the assignment of length $N$ it extends; every level is finite and non-empty, so by König’s lemma there is an infinite branch, and an infinite branch is a consistent assignment of the whole list.

The step that matters is “extends”. With a local rule, the first $N$ values of a consistent assignment of $N + 1$ sentences are, apart from the last few, a consistent assignment of $N$ sentences, so the tree is really a tree. With Yablo’s rule it is not: the unique assignment of 14 sentences, all false but the last, does not extend the unique assignment of 13, which made the thirteenth sentence true. Every level of the tree has one node, and no node lies below any other. There is no branch, because there are no edges. König’s lemma has nothing to work on, and that is the mechanism of the paradox stated combinatorially.

The same contrast decides the tiling problems that dominoes no algorithm can match leads to. Whether a set of square tiles with coloured edges can cover the whole plane is undecidable, but one thing about it is certain: if every finite square can be tiled, so can the plane, because matching edges is a local rule and König’s lemma applies. Yablo’s sentences are the opposite kind of constraint. Each one is about everything after it, and a constraint about an infinite tail is exactly the kind a finite stage cannot anticipate. The same lesson appears with the hats in infinitely many guessers, finitely many wrong, where a strategy that looks at the whole infinite tail achieves what no finite-lookahead strategy can. Infinite tails make the impossible possible there and the possible impossible here.

Is it self-referential after all? #

Graham Priest replied in 1997 that the paradox does contain a kind of circularity. To state the list one has to say, for every $n$, that $S_n$ is the sentence “for all $k > n$, $S_k$ is false”, and that is a single description of the whole list in which the predicate “is one of the sentences $S_n$” appears inside its own definition — a fixed point, of exactly the kind the diagonal builds when a program prints itself. Roy Cook and others have since given versions in languages built to exclude such fixed points, and the debate over whether Yablo’s list is “really” non-self-referential has not been settled, partly because there is no agreed definition of self-reference to settle it with.

What the computation shows is narrower and does not depend on that debate. As a structure of references — which sentences mention which — Yablo’s list has no loop, and the finite theory of such structures predicts exactly one consistent assignment. The infinite one has none, and the only difference is infinity.

A model where the last sentence exists #

Here is the surprising connection. Formalise the sentences in arithmetic with a predicate $T$ for truth, and write down one axiom for each ordinary number $n$: $T(n) \leftrightarrow \forall k > n\ \neg T(k)$. (Written instead as a single statement beginning “for all $n$”, the list is inconsistent outright, because the argument above can then be run inside any model.) Every finite set of these axioms has a model: if the largest $n$ mentioned is $m$, make $T$ true at $m + 1$ alone, and every axiom in the set holds, exactly as in a truncated list. By the compactness theorem, which an infinite tree with an infinite path proves in its combinatorial form, the whole infinite set then has a model too.

How can that be, when the argument above shows there is no consistent assignment? The answer is the one a number larger than every number gave: the model is non-standard. Its “numbers” include, beyond all the ordinary ones, infinite numbers, and the true sentence sits at one of them. Every sentence at an ordinary position is false, and the sentence “for all $k > n$, $S_k$ is false” fails for ordinary $n$ because of a sentence at an infinite position. In the ordinary numbers there is no end of the list; in a non-standard model there is something that plays the role of one. Yablo’s list is consistent but ω-inconsistent: it can be satisfied only by a model that disagrees with the ordinary numbers about what “for all $k$” covers. That is the same phenomenon that lets Gödel’s sentence be false in some models of arithmetic, met here from the side of truth instead of provability.

Finite lists of an infinite paradox #

Every figure is finite, and Yablo’s paradox exists only in the infinite list. The truncations show the true sentence running away; they cannot show that it runs away for ever, which is what the argument proves. The search over eventually periodic assignments shows that none of them fits Yablo’s list, but most infinite assignments are not eventually periodic, and the search says nothing about them; the proof that none fits is the two-line argument, not the computation.

The random systems illustrate the loop-free theorem and do not prove it — the proof is the evaluation from the sentences that mention nothing, given above — and the histogram for systems with loops describes one random model of sentences, with its own arbitrary choice of how many references each sentence has.

Assignments tested, the debate quoted #

Computed here: all $2^N$ assignments for Yablo’s list truncated at $N = 1$ to 14, and for six lists at $N = 1$ to 10; the 16,002 eventually periodic assignments of each infinite list, with the consistent ones listed; every assignment of rings of one to eight sentences of two kinds; and 6,000 random eight-sentence systems, half with references only forward.

Quoted: Yablo’s paper of 1993, Priest’s reply of 1997 and the later debate, the formalisation in arithmetic with its ω-inconsistency, discussed by Hardy, Ketland and others, and the compactness and non-standard-model arguments, which earlier essays derive.

Still open: what self-reference is #

There is no accepted definition of when a sentence, or a set of sentences, is self-referential, and so the question “is Yablo’s paradox self-referential?” has no agreed answer. Proposals define reference through the graph of which sentences mention which, through fixed points in the language, or through the way a sentence’s truth depends on others’. Thomas Forster, Cook, and Rabern, Rabern and Macauley have characterised which graphs of reference can carry a paradox at all — the “dangerous” graphs — and they include loop-free infinite ones like Yablo’s. A full description of the dangerous reference graphs, and an account of self-reference that the paradoxes respect, is not settled.

A more technical question concerns how much of arithmetic the paradox needs. Yablo’s list in its formal version is ω-inconsistent but not inconsistent; how little of the theory of numbers is required to derive an outright contradiction from versions of it, with which formulations of truth, has been mapped in part and not completely.

The end that is not there #

An infinite list of sentences, each saying that all the later ones are false, has no consistent assignment of truth values, though no sentence refers to itself or to anything earlier; every finite truncation has exactly one, with the last sentence alone true. A finite system with no loop of reference always has exactly one consistent assignment, found by evaluating from the sentences that mention nothing; Yablo’s list defeats that evaluation only by having no such sentence.

So the paradox does not need a loop. It needs a chain of reference with no end, and a loop is merely the finite way of having one. A non-standard model can supply the missing end, at an infinite position, and is the only kind of model that can.