A list that cannot contain itself

Some sets contain themselves. The set of all things that are not teacups is not a teacup, so it contains itself. Most sets do not. Collect the ones that do not, and something breaks — by the same diagonal move that beats any list of real numbers, applied to a table whose rows and columns are the same objects.

Call the collection $R$. Ask the only question there is to ask: does $R$ contain itself?

If it does, then $R$ is one of the sets that do not contain themselves, so it does not. If it does not, then $R$ qualifies for membership in $R$, so it does. Either answer gives its own negation.

The table is the point #

Bertrand Russell found this in 1901 and it is usually presented as a verbal trick. The figure is there to say it is not.

Lay out a table whose rows and columns are indexed by the same collection of sets, with a mark at $(i, j)$ when set $i$ contains set $j$. The diagonal is then the sequence of answers to does this set contain itself, one per set.

Now take the complement of the diagonal. That is a row of marks — a specification of which sets belong — and it differs from row $k$ at column $k$ for every $k$. So it cannot be any of the rows.

That is the diagonal argument with nothing changed except what the table is about. Cantor’s version has rows indexed by whole numbers and columns by positions, and produces a sequence missing from a list. Russell’s has rows and columns indexed by the same sets, and produces a set missing from the collection of all sets — which is a contradiction rather than a discovery, because the collection was supposed to have everything in it.

The figure makes that concrete on a finite table where every claim can be checked by looking. Seven sets, a stated membership rule, the diagonal computed, and the complement compared against all seven rows. It is not any of them, and the generator asserts so before drawing.

That difference is the whole difference between a discovery and a contradiction. When the columns are indexed by something other than the rows, the built row is a new object and the conclusion is that the list was incomplete. When the columns are indexed by the rows themselves, the built row has to be one of them, and the conclusion is that the collection cannot exist.

So the two results are one construction pointed at two arrangements, and which of them comes out depends on a single decision about what the table is indexed by. That is worth holding onto, because the third use of it — in the next essay — points the same construction at a table whose rows are sentences and whose columns are the same sentences, and gets a third kind of answer again.

What exactly was assumed #

The paradox is not a fact about the word set. It is a refutation of a specific principle that was being used without comment.

Unrestricted comprehension. For any property $P$, there is a set of all things with property $P$.

That principle looks like a definition of what a set is, and it is what Frege’s system rested on. Take $P(x)$ to be $x$ does not contain itself, and comprehension supplies $R$, and $R$ cannot exist.

So the principle is false. Not restricted, not subtle, not in need of care — false, and the argument that refutes it is four lines long and uses nothing else.

Russell wrote to Frege about it in June 1902, while the second volume of Frege’s Grundgesetze was in press. Frege’s reply is one of the most frequently quoted passages in the subject:

Your discovery of the contradiction caused me the greatest surprise and, I would almost say, consternation, since it has shaken the basis on which I intended to build arithmetic.

He added an appendix acknowledging the problem and proposing a repair, and the repair was also inconsistent.

Why it took until 1901 #

Naive comprehension had been in use for as long as anyone had been reasoning about collections, which raises an obvious question: why did nobody hit this earlier?

Two reasons, and both are worth having.

Nobody had written the principle down. Reasoning about “the set of things such that…” was a habit rather than an axiom, and habits do not get stress-tested. Frege’s achievement was to make the principle explicit and formal, and making it explicit is what made it refutable — a system precise enough to be proved inconsistent is more advanced than one too vague to be proved anything.

Nobody had a reason to consider self-membership. Every collection anybody actually used — the primes, the continuous functions, the points of a line — is plainly not a member of itself, and the question does not arise. It arises only when all sets are being considered as a domain, which is what a foundation has to do and what ordinary mathematics never does.

So the paradox is a consequence of ambition rather than carelessness. It appeared at the exact moment somebody tried to write down what all the informal practice amounted to, and it appeared because they succeeded in writing it down.

The neighbours #

Once the shape is visible, the same argument turns up wherever something indexes itself — including inside arithmetic, where it becomes a sentence about its own provability.

The barber. In a village, the barber shaves exactly those who do not shave themselves. Who shaves the barber? The answer is that no such barber exists — an impossibility with a witness, in the manner of every classical construction that turned out to be unreachable — which is a fine conclusion about barbers and not about sets — the difference being that comprehension guaranteed the set and nothing guaranteed the barber.

The catalogue. A library catalogues its catalogues; some list themselves, some do not; the catalogue of all catalogues that do not list themselves cannot be written. The pattern is the diagonal of a square table, and it is the same table a bijection between two sets is built on when the rows and the columns are the same collection. Same argument, same conclusion, and again the conclusion is unremarkable because nobody had committed to the catalogue existing.

The set of all sets. If it existed, its subsets would all be sets and would therefore be members of it — but Cantor’s theorem says a set’s subsets outnumber its members. This is Cantor’s paradox, found before Russell’s and, in retrospect, the same discovery: Russell arrived at his by trying to find what went wrong with Cantor’s.

The pattern is worth saying plainly. A collection cannot contain a complete account of the things it can distinguish, because it can always distinguish one more thing than it contains, by diagonalising against itself.

The figure is the finite shadow of the argument. With four elements there is no paradox, only a count: sixteen is more than four, so of course a map from four things misses something. The paradox appears when the two collections are supposed to be the same collection, so that “misses something” and “contains everything” are both required.

The two repairs #

Mathematics did not stop. Two ways of restricting comprehension were found, both work, and they are quite different in spirit.

Types. Russell’s own answer, and Frege’s instinct too. Objects are stratified into levels: individuals at level 0, sets of individuals at level 1, sets of those at level 2, and so on. A set may only contain things of lower type, so $x \in x$ is not false but ungrammatical — it does not parse, in the way that green sleeps furiously does not.

This is a strong solution and a costly one. Every object carries a level, statements have to be checked for type-correctness, and natural constructions get duplicated at every level. Type theory survives and is the foundation of most proof assistants and of a good deal of programming-language theory, so the cost turned out to be worth paying in the places where the discipline is wanted anyway.

Separation. Zermelo’s answer in 1908, and the one ordinary mathematics uses. Comprehension is allowed only inside an existing set: given a set $A$ and a property $P$, there is a set of the elements of $A$ with property $P$. Carving out is allowed; conjuring is not.

Then $R$ becomes, for each set $A$, the set of elements of $A$ that do not contain themselves — which exists, and which by the same argument is not an element of $A$. That is no longer a contradiction; it is a theorem, and a useful one: for every set $A$ there is something not in $A$, so there is no set of everything.

The paradox has become a proof of a fact instead of a disaster. That transformation is the standard fate of a good paradox, and it is worth noticing how little had to change: the argument is untouched, and the only difference is that comprehension no longer hands over a set whose existence contradicts it.

What separation costs, and what it does not #

Zermelo’s fix has a reputation for being ad hoc, and the charge is worth answering because it is the natural first reaction.

The restriction was not chosen to block Russell’s set specifically. It follows from a picture of what sets are — the cumulative hierarchy, in which sets are built in stages, each stage containing sets whose members came from earlier stages. On that picture nothing ever contains itself, because a set’s members are strictly earlier than it, and the restriction to carving out of existing sets is what building in stages means.

That picture came later than the fix, which is the usual order. What matters is that it exists: the axioms are not a list of prohibitions assembled to avoid known accidents, but a description of a structure, and every axiom is true of that structure.

What the fix costs is a small amount of naturalness. The set of all groups does not exist, and neither does the set of all vector spaces, which are things a mathematician wants to say. The workaround is to call them classes — collections defined by a property, which may be too large to be sets and which cannot be members of anything. That is a bookkeeping burden rather than an obstacle, and most working mathematicians meet it once and then ignore it.

The stages, which are what the fix is faithful to #

The cumulative hierarchy is worth spelling out once, because it converts the restriction from a prohibition into a description.

Start with nothing: stage 0 is the empty set. Stage 1 is all subsets of stage 0, which is one set. Stage 2 is all subsets of stage 1. Continue, and keep going past the whole numbers into the transfinite, taking unions at limit stages. The sets are exactly the things that appear at some stage.

Two things follow immediately and both are exactly what is wanted.

Nothing contains itself. A set appears at some stage and its members appeared earlier, so $x \in x$ never holds. The diagonal of the membership table is blank, and its complement is the collection of all sets — which is not a set, because it never appears at any stage.

Separation is obviously true. Carving a subcollection out of a set $A$ that appeared at stage $α$ gives something whose members also appeared before stage $α$, so it appears at stage $α$ too. Nothing new is needed.

That is the sense in which Zermelo’s restriction is not ad hoc. It is what comprehension looks like to somebody who believes in the stages, and the stages are a picture somebody can hold rather than a rule somebody has to obey. Whether the picture is true is a separate question that this field does not have a way of answering — which is the honest position and the one the whole subject has settled into.

Self-membership is not the culprit #

The stages forbid $x \in x$, and it is tempting to read that as the diagnosis: circularity was the disease, and the hierarchy is the cure. That reading is natural, it is what most retellings imply, and it is wrong.

The prohibition has a name of its own. Foundation is the axiom asserting that every non-empty set has a member disjoint from it, which rules out $x \in x$, rules out two sets containing each other, and rules out any infinite chain of memberships descending forever. It is exactly the statement that the stages describe everything.

And it is not what saves the theory. Separation alone blocks Russell’s argument — the collection of non-self-membered elements of a given set exists, is not a member of that set, and contradicts nothing. Foundation was added afterwards, for tidiness and for the induction it makes available, and dropping it leaves the theory as consistent as it was.

More than that: circular sets can be positively asserted without trouble. Aczel’s anti-foundation axiom replaces Foundation with its opposite, allowing a set that is its own only member and a great many stranger objects besides, and the resulting theory is consistent exactly when ordinary set theory is. Such sets are used to model streams, processes and systems that observe themselves, where a hierarchy of stages is the wrong picture and circularity is the phenomenon being described.

So the honest diagnosis is narrower than the usual one. What fails is unrestricted comprehension — the belief that every property carves out a set — and not self-reference. Russell’s property is self-referential, and that is what makes it a good weapon against comprehension; it is not what makes comprehension false. Comprehension would have been in trouble for any property whose extension is too large or too awkward to be a set, and this one merely makes the trouble arrive in four lines.

The distinction matters for reading everything else in this ladder. The diagonal against a list of real numbers is self-referential in exactly the same way and produces a theorem rather than a contradiction. The sentence that says it has no proof is more self-referential still and produces an incompleteness rather than an inconsistency. In all three the construction is the same and the outcomes differ, and what differs is never the circularity — it is what the surrounding system had promised about the object being built.

Blaming self-reference is therefore a way of not learning the lesson. The lesson is that a principle guaranteeing the existence of things must be checked against the things it guarantees, and comprehension was never checked because nobody had written it down.

What was actually lost #

It is easy to tell this story as a crisis followed by a repair, with everything restored. Something was permanently lost, and it is worth naming.

Before 1901, the plausible position was that mathematics rests on logic alone — that arithmetic is analytic, derivable from principles about concepts and extensions with nothing else assumed. That was Frege’s programme and it was the most ambitious philosophical claim ever made for mathematics.

After 1901 the principle it needed is false, and every repair adds something that is not a logical truth. Zermelo’s axioms assert that sets exist, that infinite sets exist, that power sets exist; those are assumptions about a subject matter, not laws of thought. Russell’s types are a grammar imposed to prevent trouble, and his system also needed an axiom of infinity and an axiom of reducibility that nobody could call logical.

So the answer to is mathematics reducible to logic? is no, and the reason is this argument. What replaced the programme was a weaker and more durable claim: mathematics can be founded on a small number of explicit assumptions about sets, whose consistency is unproven and unprovable, and which have not produced a contradiction in a hundred and twenty years.

That is where the field stands, and the next essay is about why the unprovable in that sentence is not going to improve. The same diagonal, applied a third time.

A note on what a paradox is for #

It is worth separating three things that get called paradoxes, because only one of them is what this essay is about. The third of them — a sentence that is neither provable nor refutable — is not a paradox at all, and the essay after this one is about the difference.

A surprise is a true result that offends intuition. That a walk on the plane returns home and a walk in space does not is surprising and is not a paradox; nothing is wrong, and the only thing to repair is the expectation.

A puzzle is an argument with a hidden mistake. Most of the classical “paradoxes” of motion are of this kind, and the work is to find the step that does not follow.

An antinomy is what Russell found: a valid argument, from principles that were believed, to a contradiction. There is no hidden mistake, so nothing can be repaired by looking harder. Something believed has to be given up, and the only question is which thing.

That third category is rare and it is the productive one. It forces a decision that would otherwise be postponed indefinitely, and the decision is usually more informative than the paradox — separation, types and the cumulative hierarchy are all worth more than the observation that produced them.

The test for which kind is in front of a reader is whether the argument survives being made completely explicit. Russell’s does: it can be written in four lines with every step named, and it is drawn on this page on a finite table where every claim can be checked by eye. That is why it ended a research programme rather than starting an argument about it.