Cantor's
Bargain

The Great Lister has a book that never ends. Every line of it is a row of two letters, m and w, and the rows never end either. He says: whatever row you write, I already have it in my book. Somewhere.

Write a row of m's and w's that is not in his book.

Three short rounds. Built from Georg Cantor's paper of 1891.

Book No.
Write a row of m's and w's that is not in the Lister's book.

You cannot strike out all the rows at once. So stop trying.

Take them one at a time. Your 1st letter deals with row 1. Your 2nd letter deals with row 2. Your 3rd with row 3. And so on. Then every row is struck out by the time you reach its number, and it no longer matters how many rows there are: you never have to be finished.

How? Look at row 1's 1st letter and write the other one. Row 1 is struck out. Look at row 2's 2nd letter and write the other one. Row 2 is struck out. The letters you have to look at run in a line from corner to corner. We colour that line teal.

The Lister agrees, on one condition: he writes each row only when you get to it, so he can copy what you have written so far. He thinks that will save him.

m
→
w
w
→
m

The letter on the teal line → you write the other one.

Not in the Book

The Lister tries once more. He puts your row into his book as row 1 and moves every other row down one. "Now it is in the book," he says. Watch the rule run on its own.

Georg Cantor, Über eine elementare Frage der Mannigfaltigkeitslehre (On an elementary question of the theory of manifolds), 1891. The two letters m and w, and the first three rows of the first book, are his. He went on, in the half of the paper this game leaves out, to show that the same trick works for any collection at all: there is no biggest infinity.

How to play

Write a row of m's and w's that is not in the Lister's book.

The Lister's book is a list of rows. Every row is made of two letters, m and w, and goes on for ever; the page shows the first six or ten letters of each. Your own row is the gold band underneath. Tap the m ticket or the w ticket to write your next letter.

Striking out a row

A row matches you while every letter you have written is the same as its letter in the same place. The moment one of your letters is different from the row's letter in that place, the row is struck out: it greys out, a line runs through it, and the letter that did it gets a ring. A struck-out row cannot be your row. Your row is "not in the book" once every row is struck out.

Round 1: the small book

Five rows, six letters each. Strike out all five before your six letters run out. Tip: look at the rows that still match you, and pick the letter that strikes out more of them.

Round 2: the endless book

The same game, but the book never ends. Every time you strike out rows, the Lister turns to rows further down that still match you. Write all six letters; then he has a word. Nobody wins this round. That is the point.

Round 3: Cantor's bargain

Ten rows, ten letters, a teal line from corner to corner. Your 1st letter deals with row 1, your 2nd with row 2, and so on: look at the letter on the teal line and write the other one. The Lister writes each row only when you reach it, copying what you have written so far, so the letter on the line is the only one that can strike the row out in time. If you write the same letter instead, the row slips: it stays in the book, still matching you, unless a later letter happens to strike it out.

The end

You see what your row proves, and the Lister gets one last try.

About the paper

The game in one line

A showman says his endless book holds every row of m's and w's. You write your own row letter by letter; each letter strikes out the rows that disagree with it there; against the endless book you can never strike them all, until you take Cantor's bargain and strike row 1 with letter 1, row 2 with letter 2, and so on. Then no row survives, the Lister's book is shown incomplete, and adding your row to it only makes a new missing row.

What the paper found

In 1891, in the first volume of the journal of the German Mathematical Union, Georg Cantor gave a new proof that some infinite collections are too big to be counted off as first, second, third, and so on. In 1874 he had proved it for the real numbers, by a harder route. Here he takes two characters, m and w, and the collection M of all endless rows of them, such as (m, m, m, …), (w, w, w, …) and (m, w, m, w, …). Suppose someone claims to have listed every row: E1, E2, E3, …. Write the list as a grid. Build a new row E0 by going down the diagonal, the first letter of row 1, the second letter of row 2, the third letter of row 3, and writing the other letter each time. E0 cannot be row u for any u, because at letter u it differs from row u by construction. So the list missed one, whatever the list was: M cannot be put in the form E1, E2, E3, …. M does not have the "power" of the whole numbers. In the second half of the paper, which this game leaves out, Cantor extends the argument to the collection of all ways of marking the elements of any set L with m or w, concluding that there is no greatest power: no biggest infinity.

Mechanism: ported

This game demonstrates Cantor's construction, run as written: for the ten rows of the last round, your letter u is set against row u's letter u, and the rule "write the other letter" leaves every row struck by its own number; adding your row to the book and running the rule again produces another row the book misses. The check that ships with the game runs the construction on hundreds of lists, random and adversarial, and on the paper's own three examples (which give E0 = w, m, w, …).

It assumes the game's framing. The rows in the paper are endless; the page shows six or ten letters and the contest runs on those. The Lister who turns to rows further down (round 2) and who writes each row to copy what you have written so far (round 3) is this game's dramatisation of the claim that an endless book contains everything; the paper's list is fixed in advance, and the rule beats a fixed list just as well, which is what the end screen shows. Striking the most rows per letter, the trick that wins round 1, is a strategy the small book rewards and the paper does not discuss. "Row u by letter u" is Cantor's own bookkeeping, drawn as a line; any pairing of rows with letters would do, and the game uses his.

The paper establishes that no sequence E1, E2, E3, … can contain every element of M, and so that M is not countable; the game's rounds are not evidence for this, they show the construction that proves it. The paper does not say anything about strategies, deadlines or showmen; those are the game's. The conclusion the game states, that there are more such rows than whole numbers, is the paper's; "some infinities are bigger than others" is the plain-language form of its claim that M does not have the power of the number series 1, 2, 3, ….

What is cut

The second half of the paper (the generalisation to any set L and the theorem that powers have no maximum); the 1874 proof and the remark that this one does not need the irrational numbers; Cantor's words for manifold, totality and power; the real numbers, which the game never mentions.

The paper

Georg Cantor, "Über eine elementare Frage der Mannigfaltigkeitslehre", Jahresbericht der Deutschen Mathematiker-Vereinigung 1 (1890–91): 75–78. No DOI. Read it, with an English translation, at logicmuseum.com/cantor/diagarg.htm (the Logic Museum); the game was built from that page's first half, which contains the diagonal argument.

Game built from this paper; the paper is the authority where the two disagree. Fonts: Rye, Alfa Slab One and Work Sans (SIL Open Font License). Book numbers are game seeds: the same number gives the same books, and the number is in the page address.