Hypergame and Cantor’s Theorem, Part II

As promised on Monday, we present here William Zwicker’s proof of Cantor’s Theorem. But first: Let’s play Hypergame!

Hypergame

hypergame

We will be concerned with two-player games, where the players, who we will name Ada and Bertrand, alternate making plays. Let us say that a game is finite if it is guaranteed to end after a finite number of moves. For example, because of the 50-move rule, under which a game is a draw if 50 moves elapse in which no pawn is advanced and no piece is captured, chess is a finite game. In fact, there is a fixed upper bound (6000 is certainly enough) on the number of moves in a single chess game, but this is not true of all finite games. Consider the game in which the first player names a natural number, N, and the players then play N games of chess. This game is guaranteed to end after finitely many moves (6000 \cdot N is an upper bound), but there is no fixed upper bound before the game starts, as the first player could simply choose a larger number as N.

We are now ready to define Hypergame. The rules are as follows. On her first move, the first player names a finite game. The players then play a round of that game, beginning with the second player. For example, a round of Hypergame between Ada and Bertrand might go something like this:

Ada: Let’s play chess!

Bertrand: f3

Ada: e5

Bertrand: g4

Ada: Qa4#

Now for the crucial question: Is Hypergame a finite game?

Well, yes, obviously. One move of Hypergame consists of naming a finite game. The rest of the moves consist of a round of that finite game, which must, by definition, take only a finite number of moves. One plus a finite number is a finite number, so Hypergame must end after a finite number of moves and is thus a finite game.

But now, armed with the knowledge the Hypergame is a finite game, Ada and Bertrand may play the following round of Hypergame:

Ada: Let’s play Hypergame!

Bertrand: Let’s play Hypergame!

Ada: Let’s play Hypergame!

Bertrand: Let’s play Hypergame!

This is an infinite (and rather boring) round of Hypergame! But didn’t we prove in the previous paragraph that Hypergame is a finite game? What has gone wrong here? I’ll leave you to ponder this instructive question, pointing out that we haven’t really given a formal definition for a “game.” If you try to make this argument more rigorous by providing such a formal definition, does Hypergame actually qualify as a game?

Proof of Cantor’s Theorem

We now turn to Zwicker’s proof of Cantor’s Theorem, where the ideas from the Hypergame paradox will be put to good use. Recall that Cantor’s Theorem states that, for every set X, |X| < |\mathcal{P}(X)|. (Recall also that a review of relevant mathematical definitions is given here.)

Suppose Cantor’s Theorem is false and that there is a set X such that |X| \geq |\mathcal{P}(X)|. This means that there is a function f:X \rightarrow \mathcal{P}(X) that is onto, i.e. a function f such that, for every Y \in \mathcal{P}(X), there is x \in X such that f(x) = Y. We will use this function to derive a contradiction, thus showing that such a function cannot exist and proving Cantor’s Theorem.

We first need a definition. Consider a sequence \langle x_0, x_1, x_2, \ldots \rangle (the sequence could be finite or infinite) consisting of elements of X. We say this sequence is a sequence through f if, for every element x of the sequence, the next element of the sequence, if it exists, comes from f(x), i.e. x_1 \in f(x_0), x_2 \in f(x_1), etc.

As an example, suppose X = \mathbb{N} and we have f(3) = \{2, 17, 9\}, f(9) = \{3, 13, 8\}, and f(8) = \emptyset. Then \langle 3, 9, 8 \rangle is a (finite) sequence through f. If f(4) = \{5\} and f(5) = \{4\}, then \langle 4, 5, 4, 5, 4, \ldots \rangle is an infinite sequence through f.

Back to our general case. We say an element x \in X is infinitary if there is an infinite sequence through f starting with x. x is finitary if there is no such infinite sequence. Let Y be the set of all finitary elements of X. Y \in \mathcal{P}(X), so, since f is onto, there is x \in X such that f(x) = Y.

Is x finitary? Well, yes. This is the same as the argument that Hypergame is a finite game: Suppose (x_0, x_1, x_2, \ldots) is a sequence through f with x_0 = x. Then x_1 \in f(x) and f(x)=Y, so, by our definition of Y, we know that x_1 is finitary. Since (x_1, x_2, \ldots) is a sequence through f starting with x_1 and x_1 is finitary, (x_1, x_2, \ldots) must be a finite sequence. But then (x_0, x_1, x_2, \ldots) must also be finite, as it has just one more element. There are thus no infinite sequences through f starting with x, so x is finitary.

But now we have a problem. In fact, it is the same problem we had with Hypergame. Since x is finitary, we must have x \in Y, by the definition of Y. But this means that (x, x, x, x, \ldots), the infinite sequence, all of whose elements are x, is an infinite sequence through f starting with x. This contradicts the fact that x is finitary and completes our proof.

P.S. Hypergame and Zwicker’s proof of Cantor’s Theorem were brought to my attention by Raymond Smullyan’s excellent book, Satan, Cantor and Infinity, which I would highly recommend to all readers of this blog.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s