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.

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.

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, 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. 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.

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.

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.