(This is a snapshot of my old weblog. New posts and selected republished essays can be found at raganwald.com.)
Monday, June 14, 2004
Hypergame and Infinity
The following account is drawn from Raymond Smullyan’s Satan, Cantor, and Infinity and Other Mind-boggling Puzzles
, a highly readable book of puzzles touching on truth, belief systems, self reference, provability, and incompleteness theory. Why am I bothering to put it on a web page? First, because it is aesthetically beautiful, and the act of recounting it pleases me. This is much the same as an artist drawing a landscape. Second, because doing so forces me to think more clearly about the problems, much as drawing the landscape forces the artist to look at it more closely.
Hypergame
Presume the existence of a class of games. The characteristics of these games are that the have alternating moves between two players, that the moves consist of a choice to be made by each player, and that for the purpose of this account it is of no consequence how quickly or slowly either player makes the choice of which move to choose.
The proposition is that by virtue of their rules, such games fall into two sets: those games which necessarily must end after a finite number of moves, and those games which need not necessarily end. For example, by virtue of its rules Naughts and Crosses must end after a finite number of moves (at most nine). Backgammon need not end after a finite number of moves, as there are legal sequences of moves whereby the players constantly hit and recirculate their chequers.
Hypergame is a two player game with alternating moves. The first player’s first move consists of naming a two player game with alternating moves which necessarily ends. The second player’s first move is to take the first move of that game, and the players alternate moves of that game until it ends.
For example, the first player may call “Naughts and Crosses.” The second player would then take the first move, marking a cross in one of the nine available squares. The first player would mark a naught in one of the eight remaining squares, and the two players would continue with naughts and crosses until the game ends. The first player could also call out “Chess,” in which case the second player would make the first move of a game of chess with one of the white pawns or knights, and the two players would carry on playing a game of chess to its eventual end.
Is this clear? Good. I will ask you this, then:
Is Hypergame a two player game with alternating rules which necessarily must end?
One argument is that it clearly ends. The first player picks a game which necessarily ends, say in no more than n moves. Therefore, that iteration of Hypergame will end in no more than n+1 moves, including the first player’s move of choosing Hypergame. Since every game the first player chooses must end, all possible games of Hypergame must necessarily end.
Another argument is that Hypergame does not necessarily end. We can prove this with reductio ad absurdum. Take the first argument that it necessarily ends. The first player is entitled to choose any two player alternating move game which necessarily ends. You can see where this is leading. The first player thus may choose “Hypergame.” Now the second player makes the first move of a game of Hypergame. And that is to choose a game which necessarily ends. So the second player may choose Hypergame as well. This sequence may be repeated indefinitely, which establishes that Hypergame need not necessarily end. Since assuming that Hypergame necessarily ends leads to a contradiction, one may argue that Hypergame need not necessarily end.
A third argument runs along the same lines in the reverse direction. Take the assumption, established in the previous paragraph, that Hypergame does not necessarily end. Well, this rules Hypergame out as a choice the first player may make, since the first player is required to choose a game which necessarily ends. If the first player cannot choose Hypergame, the previous proof collapses, and Hypergame is established as a game which necessarily ends.
Smullyan’s explanation, and my own feelings
Raymond Smullyan explains that the notion of a game is not well defined, which is why a paradox is possible. This is true, however I find that there is only a paradox when you subject the game to rigourous examination. When I consider the matter from a naive point of view, the paradox goes away.
Clearly, Hypergame ends in a finite number of moves if and only if neither player recursively chooses Hypergame. So where is the paradox? Well, there are some games which require that neither player choose a move which deliberately leaves either player no legal move. For example, Rail Baron is a train game wherein no player may use the same piece of track twice in the same journey. The rules prohibit a move which forces a player to do so. Likewise, there is a rarely used rule in Chess which ends the game should a player not be in check but have no legal move which does not place that player’s King in check.
The paradox rests on the self referential idea that Hypergame necessarily ends if and only if it does not necessarily end. As a practical matter, Hypergame ends unless either player chooses Hypergame, which causes Hypergame to not necessarily end. Therefore, the act of choosing Hypergame causes Hypergame to become unchoosable. Therefore, I am comfortable with the idea that Hypergame necessarily ends, however neither player may choose Hypergame.
Now, this is in direct conflict with the description of the game, which does not concern itself with games which ‘always’ end, or games which ‘have ended in every attempt since the dawn of man’, or what have you. The definition strictly concerns itself with whether a game must necessarily end, which is a question of logic.
So I accept Smullyan’s explanation, however I feel emotionally that Hypergame necessarily ends nevertheless.
Cantor’s Theorem
Cantor’s theorem is that the cardinality of an infinite set is less than the cardinality of the power set of that set. The basis for his proof is proof by contradiction, where he shows that for any scheme for putting the elements of the infinite set into a 1:1 correspondence with the elements of the power set is incomplete by constructing a member of the power set which cannot possibly correspond to a member of the infinite set.
Cantor’s proof used a particular construction for the member of the power set which is roughly analogous to Russell’s Barber paradox. For example, to prove that the set of all sets of integers is of a higher cardinality than the set of integers, presume that there is some scheme over of the set of all sets of integers which places the members in a 1:1 correspondence with a (possibly infinite) set of integers. If that is possible, then the set of all sets of integers is of no higher cardinality than the set of integers.
However, if that is impossible, then the set of all sets of integers is of a higher cardinality than the set of integers. To demonstrate the impossibility, we will now construct a set of integers which must necessarily not be in a 1:1 correspondence with any integer, no matter what correspondence is chosen. Obviously, if the set of all sets of integers is in a 1:1 correspondence with the set of integers, there is a unique integer associated with every set of integers. Cantor’s set was the set of all integers which are not members of the set they correspond to.
Call Cantor’s set Sx. For example, say there is an integer, n. There is a set, Sn, which corresponds to n. If n is a member of Sn, then n is not a member of Sx. But if n is not a member of Sn, then n is a member of Sx. The question is, what integer corresponds to Sx? Call that integer x. If x is a member of Sx, then Sx is no longer the set of all integers which are not members of the set they correspond to, since it contains a member x which is a member of the set it corresponds to x. Conversely, if x is not a member of Sx, then there is an integer, x, which is not a member of the set it corresponds to yet is not in Sx, which again is a contradiction.
Therefore, since any attempt to put the integers in a 1:1 correspondence with the set of all sets of integers fails, the set of all sets of integers is necessarily of a higher cardinality than the set of all integers.
William Zwicker’s Proof of Cantor’s Theorem
Zwicker’s proof uses a completely different set to show that the set of all sets of integers cannot be put in a 1:1 correspondence with the set of all integers. As above, presume such a correspondence. Now we define a path as being a non-empty ordered set of integers formed as follows:
Obviously, paths from any integer form a directed graph. Some such graphs have cycles, some are acyclic. And some graphs are finite, some infinite. For any integer, it may be possible to construct an infinite path, either because there is a path with a cycle from that integer, or because there is an infinitely long path leading from that integer. Conversely, it may not be possible to construct an infinite path from a particular integer. For a trivial example, if an integer, e, corresponds to the empty set, there are no infinite paths from the integer e. Another trivial example is a set which contains the integer which corresponds to that set. For example, if Sn contains n, then there is at least one path (n, n, n…) which is of infinite length leading from the integer n.
Now construct the set of all integers which do not lead to infinite paths. That set corresponds to an integer, x. Is x a member of that set? If it is, then there is an infinite set leading from x, which contradicts the claim that the set contains only the integers which do not lead to infinite paths. Conversely, if x is not a member of that set, then every path leading from x is finite which means that Sx does not contain an integer which does not lead to an infinite path. Therefore, there is a set of integers which cannot possibly correspond to any integer.
As Raymond Smullyan pointed out, this proof uses a completely different method for constructing a set which cannot be put into a 1:1 correspondence with any set.
As an exercise, think of values for x which lead to a contradiction without using the direct (x, x, x…) argument.
This is a repost of material that originally appeared on my old web site. If you found this amusing, you may also find Hypergame II interesting. And as Scott K. points out below, On Numbers and Games
is an absolute must-read if you are interested in Number Theory and games.
The following account is drawn from Raymond Smullyan’s Satan, Cantor, and Infinity and Other Mind-boggling Puzzles
, a highly readable book of puzzles touching on truth, belief systems, self reference, provability, and incompleteness theory. Why am I bothering to put it on a web page? First, because it is aesthetically beautiful, and the act of recounting it pleases me. This is much the same as an artist drawing a landscape. Second, because doing so forces me to think more clearly about the problems, much as drawing the landscape forces the artist to look at it more closely.Hypergame
Presume the existence of a class of games. The characteristics of these games are that the have alternating moves between two players, that the moves consist of a choice to be made by each player, and that for the purpose of this account it is of no consequence how quickly or slowly either player makes the choice of which move to choose.
The proposition is that by virtue of their rules, such games fall into two sets: those games which necessarily must end after a finite number of moves, and those games which need not necessarily end. For example, by virtue of its rules Naughts and Crosses must end after a finite number of moves (at most nine). Backgammon need not end after a finite number of moves, as there are legal sequences of moves whereby the players constantly hit and recirculate their chequers.
Hypergame is a two player game with alternating moves. The first player’s first move consists of naming a two player game with alternating moves which necessarily ends. The second player’s first move is to take the first move of that game, and the players alternate moves of that game until it ends.
For example, the first player may call “Naughts and Crosses.” The second player would then take the first move, marking a cross in one of the nine available squares. The first player would mark a naught in one of the eight remaining squares, and the two players would continue with naughts and crosses until the game ends. The first player could also call out “Chess,” in which case the second player would make the first move of a game of chess with one of the white pawns or knights, and the two players would carry on playing a game of chess to its eventual end.
Is this clear? Good. I will ask you this, then:
Is Hypergame a two player game with alternating rules which necessarily must end?
One argument is that it clearly ends. The first player picks a game which necessarily ends, say in no more than n moves. Therefore, that iteration of Hypergame will end in no more than n+1 moves, including the first player’s move of choosing Hypergame. Since every game the first player chooses must end, all possible games of Hypergame must necessarily end.
Another argument is that Hypergame does not necessarily end. We can prove this with reductio ad absurdum. Take the first argument that it necessarily ends. The first player is entitled to choose any two player alternating move game which necessarily ends. You can see where this is leading. The first player thus may choose “Hypergame.” Now the second player makes the first move of a game of Hypergame. And that is to choose a game which necessarily ends. So the second player may choose Hypergame as well. This sequence may be repeated indefinitely, which establishes that Hypergame need not necessarily end. Since assuming that Hypergame necessarily ends leads to a contradiction, one may argue that Hypergame need not necessarily end.
A third argument runs along the same lines in the reverse direction. Take the assumption, established in the previous paragraph, that Hypergame does not necessarily end. Well, this rules Hypergame out as a choice the first player may make, since the first player is required to choose a game which necessarily ends. If the first player cannot choose Hypergame, the previous proof collapses, and Hypergame is established as a game which necessarily ends.
Smullyan’s explanation, and my own feelings
Raymond Smullyan explains that the notion of a game is not well defined, which is why a paradox is possible. This is true, however I find that there is only a paradox when you subject the game to rigourous examination. When I consider the matter from a naive point of view, the paradox goes away.
Clearly, Hypergame ends in a finite number of moves if and only if neither player recursively chooses Hypergame. So where is the paradox? Well, there are some games which require that neither player choose a move which deliberately leaves either player no legal move. For example, Rail Baron is a train game wherein no player may use the same piece of track twice in the same journey. The rules prohibit a move which forces a player to do so. Likewise, there is a rarely used rule in Chess which ends the game should a player not be in check but have no legal move which does not place that player’s King in check.
The paradox rests on the self referential idea that Hypergame necessarily ends if and only if it does not necessarily end. As a practical matter, Hypergame ends unless either player chooses Hypergame, which causes Hypergame to not necessarily end. Therefore, the act of choosing Hypergame causes Hypergame to become unchoosable. Therefore, I am comfortable with the idea that Hypergame necessarily ends, however neither player may choose Hypergame.
Now, this is in direct conflict with the description of the game, which does not concern itself with games which ‘always’ end, or games which ‘have ended in every attempt since the dawn of man’, or what have you. The definition strictly concerns itself with whether a game must necessarily end, which is a question of logic.
So I accept Smullyan’s explanation, however I feel emotionally that Hypergame necessarily ends nevertheless.
Cantor’s Theorem
Cantor’s theorem is that the cardinality of an infinite set is less than the cardinality of the power set of that set. The basis for his proof is proof by contradiction, where he shows that for any scheme for putting the elements of the infinite set into a 1:1 correspondence with the elements of the power set is incomplete by constructing a member of the power set which cannot possibly correspond to a member of the infinite set.
Cantor’s proof used a particular construction for the member of the power set which is roughly analogous to Russell’s Barber paradox. For example, to prove that the set of all sets of integers is of a higher cardinality than the set of integers, presume that there is some scheme over of the set of all sets of integers which places the members in a 1:1 correspondence with a (possibly infinite) set of integers. If that is possible, then the set of all sets of integers is of no higher cardinality than the set of integers.
However, if that is impossible, then the set of all sets of integers is of a higher cardinality than the set of integers. To demonstrate the impossibility, we will now construct a set of integers which must necessarily not be in a 1:1 correspondence with any integer, no matter what correspondence is chosen. Obviously, if the set of all sets of integers is in a 1:1 correspondence with the set of integers, there is a unique integer associated with every set of integers. Cantor’s set was the set of all integers which are not members of the set they correspond to.
Call Cantor’s set Sx. For example, say there is an integer, n. There is a set, Sn, which corresponds to n. If n is a member of Sn, then n is not a member of Sx. But if n is not a member of Sn, then n is a member of Sx. The question is, what integer corresponds to Sx? Call that integer x. If x is a member of Sx, then Sx is no longer the set of all integers which are not members of the set they correspond to, since it contains a member x which is a member of the set it corresponds to x. Conversely, if x is not a member of Sx, then there is an integer, x, which is not a member of the set it corresponds to yet is not in Sx, which again is a contradiction.
Therefore, since any attempt to put the integers in a 1:1 correspondence with the set of all sets of integers fails, the set of all sets of integers is necessarily of a higher cardinality than the set of all integers.
William Zwicker’s Proof of Cantor’s Theorem
Zwicker’s proof uses a completely different set to show that the set of all sets of integers cannot be put in a 1:1 correspondence with the set of all integers. As above, presume such a correspondence. Now we define a path as being a non-empty ordered set of integers formed as follows:
- Take an integer as the first element of the path.
- Locate the set corresponding to that element.
- If it is empty, the path ends. Stop.
- If it is not empty, select an element from the set.
- Make that the next element.
- Go to step two.
Obviously, paths from any integer form a directed graph. Some such graphs have cycles, some are acyclic. And some graphs are finite, some infinite. For any integer, it may be possible to construct an infinite path, either because there is a path with a cycle from that integer, or because there is an infinitely long path leading from that integer. Conversely, it may not be possible to construct an infinite path from a particular integer. For a trivial example, if an integer, e, corresponds to the empty set, there are no infinite paths from the integer e. Another trivial example is a set which contains the integer which corresponds to that set. For example, if Sn contains n, then there is at least one path (n, n, n…) which is of infinite length leading from the integer n.
Now construct the set of all integers which do not lead to infinite paths. That set corresponds to an integer, x. Is x a member of that set? If it is, then there is an infinite set leading from x, which contradicts the claim that the set contains only the integers which do not lead to infinite paths. Conversely, if x is not a member of that set, then every path leading from x is finite which means that Sx does not contain an integer which does not lead to an infinite path. Therefore, there is a set of integers which cannot possibly correspond to any integer.
As Raymond Smullyan pointed out, this proof uses a completely different method for constructing a set which cannot be put into a 1:1 correspondence with any set.
As an exercise, think of values for x which lead to a contradiction without using the direct (x, x, x…) argument.
This is a repost of material that originally appeared on my old web site. If you found this amusing, you may also find Hypergame II interesting. And as Scott K. points out below, On Numbers and Games
is an absolute must-read if you are interested in Number Theory and games.
Comments on “Hypergame and Infinity”:
<< Home
Fascinating post. I'm intrigued by the mention of chess as a game that would qualify for Hypergame; are you sure that that's been established? I think that chess only ends if at least one player is determined that it do so. I can think of the following end states:
Checkmate (resignation assumes that checkmate will occur)
Draw, which occurs under in a number of ways:
- stalemate, in which one player cannot move except into check, which is probably the most common draw,
- perpetual check, in which one player demonstrates that s/he can not be stopped from checking the other indefinitely, but cannot muster mate,
- repetition, in which the same three-move sequence is repeated
- insufficient force, where one player enjoys an advantage that cannot force mate (a king and a knight against a king, for instance), which probably resolves to repetition, I suppose
If the game resolves to an easy mate (king & queen vs king), but the player in the advantage chooses not to pursue mate, and avoids repeating his moves within a three move sequence, I don't see that chess inevitably terminates in the same way that tic-tac-toe or Sprouts must.
Am I missing something?
Of course, this doesn't affect the larger thrust of your argument, unless it influences your opinion of your subjective impression of game termination.
You must have read Conway's _Numbers and Games_; I was thinking of it (particularly in connection with rigor and games) while reading your post.
Checkmate (resignation assumes that checkmate will occur)
Draw, which occurs under in a number of ways:
- stalemate, in which one player cannot move except into check, which is probably the most common draw,
- perpetual check, in which one player demonstrates that s/he can not be stopped from checking the other indefinitely, but cannot muster mate,
- repetition, in which the same three-move sequence is repeated
- insufficient force, where one player enjoys an advantage that cannot force mate (a king and a knight against a king, for instance), which probably resolves to repetition, I suppose
If the game resolves to an easy mate (king & queen vs king), but the player in the advantage chooses not to pursue mate, and avoids repeating his moves within a three move sequence, I don't see that chess inevitably terminates in the same way that tic-tac-toe or Sprouts must.
Am I missing something?
Of course, this doesn't affect the larger thrust of your argument, unless it influences your opinion of your subjective impression of game termination.
You must have read Conway's _Numbers and Games_; I was thinking of it (particularly in connection with rigor and games) while reading your post.
Actually, chess games are limited simply because the state space is limited, and thus, so is the space of possible three-move sequences, so that rule always applies sooner or later.
Chess doesn't usually count for hypergame, though, because there also is a time limit.
Chess doesn't usually count for hypergame, though, because there also is a time limit.
<< Home
