 # Hypergame Paradox and Cantor's Theorem

26 posts

 Not enough math threads. I'm going to summarize a paradox and how it can be used as an interpretation for a different-than-usual proof of Cantor's theorem (which implies that there are infinitely many different sizes of infinity). Feel free to skip huge descriptive sections if you don't care and are only partially interested. But, if you don't understand something, I should have included most of what you need to follow everything in the post, so go back. The original method of proving Cantor's theorem is less complicated because there's less background explanation and a few less definitions that go into it. But, I'm bored and I find this paradox cute, so I'm going to ramble about this one instead. Consider it a challenge. * * * # The Hypergame Paradox * * * This is a paradox concerning turn-based games with two players. For example, games like chess, tic-tac-toe, checkers, the card game "go fish". We need two quick definitions and then we can state the paradox: 1) We define such a game to be **finite** if any time the game is played, it will only last a finite number of turns. That is, there are no ways to play the game so that player 1 and player 2 can alternate taking turns infinitely many times. For example, in tic-tac-toe, there are a maximum of 9 turns, since there are only 9 spots on the board and in each turn one of the spots is filled. Tic-tac-toe might be a bit more restrictive than what we're going for since every tic-tac-toe game has 9 or less moves. We want to call a game "finite" even if we don't know in advance what the maximum number of moves is, but we know that it can't go on forever. 2) We define **Hypergame** to be a turn-based game with two players which is played as follows: On the first turn, player 1 selects a finite game. On the second turn, player 2 makes the first move in the selected finite game. Subsequent turns in Hypergame consist of the selected game being played to completion as normal. The winner of the selected game is declared the winner of Hypergame. **The paradox: Is Hypergame a finite game?** If Hypergame is not finite, then there is a way to play Hypergame such that player 1 and player 2 alternate taking turns into infinity without completing the game. However, in Hypergame, player 1 must on the first move select a finite game, and then the remaining moves must be moves in the finite game. So, it is impossible for Hypergame to continue infinitely long, since this would force an infinite number of turns to be taken in the selected finite game. If Hypergame is finite, then according to the rules of Hypergame, it is available for selection during the first turn. Hence, there can be an instance of Hypergame that is played as follows: Player 1 takes the first turn of Hypergame by selecting "Hypergame" as the finite game. Player 2 then takes the second turn of Hypergame, which is to make the first turn of the selected game, which happens to be Hypergame. This allows player 2 to select Hypergame as their turn. The game can then be played forever by having each player alternately state that they select Hypergame. This contradicts the assumption that Hypergame is finite. You can think about what causes this paradox. In the meanwhile, we'll use it to prove that there's different sizes of infinity. * * * # Some comments on sets and functions * * * Before we do the proof, we'll quickly review some basic ideas about sets and functions. We think of **sets** in math as objects which contain and are contained in other objects. So we discuss things like "the set of even integers", which contains "the set of powers of 2", and is contained in "the set of all integers". We accept the existence of an **empty set** , which is a set that contains nothing. When a set can be listed, we usually write it with the elements separated by commas inside curly braces; for example: {0,1,2} is the set containing the numbers 0, 1, and 2. The empty set is denoted {}. For completion, I'll note that we will make use of the set of integers, which is the collection of whole numbers {...,-2,1,0,1,2,...}. We'll also mention the real numbers, which informally is the collection of all numbers representable in decimal notation, even those with infinitely long, nonrepeating expansions. So the reals include the positive and negative integers and fractions, and also stuff like pi and e. We define a set A to be a **subset** of set B if everything inside A is also inside B. This is logically equivalent to the statement that nothing from A is missing from B. If we're thinking about Venn Diagrams, A is a subset of B if the circle labeled A is inside the circle labeled B. Some specific examples are: {1,2} is a subset of {1,2,3} because 1 and 2 are in {1,2,3} {1,4} is not a subset of {1,2,3} because 4 is not in {1,2,3} {} is a subset of every set because there isn't anything in {} missing from another set, since there isn't anything in {} at all to be missing. Given a set X, we define the **power set** P(X) to be the set containing all subsets of X. For example, if X is {0,1}, then the subsets of X are {}, {1}, {2}, {1,2}, and hence P(X) is {{}, {1}, {2}, {1,2}}. In general, for finite sized sets X of size N, the power set of X will have 2^N elements. Infinite sets are a bit trickier. Informally, a **function** is something that has an input set I and and output set O, and for everything in I, the function assigns exactly one output element in O. For example, there is a function from the real numbers to the real numbers defined by f(x) = 2\*x. The function f sends 2 to 2\*2 = 4. It is not ambiguous in that, if we give it 2 as an input again, it will always return 4. For contrast, consider instead the idea of taking a square root. If we do not restrict the square root operation to only return positive numbers, then both 2 and -2 would be acceptable outputs for the input 4. A function from input set I to output set O is called a **one-to-one correspondence** if every possible output y in O is used as a result for exactly one input x in I. For example, the function from the integers to the integers given by f(n) = n+1 is a one-to-one correspondence. This is because each output integer is the result for exactly one input number. In particular, if we want to know the unique number that gets sent to 5, it is 5-1 = 4, since our function sends 4 to 4+1 = 5, and it does not send any other number to 5. An example of a function which is not a one-to-one correspondence is the square function from the real numbers to the non-negative real numbers given by f(x) = x^2. To see why this is not a one-to-one correspondence, note that both -2 and 2 are sent to (-2)^2 = 2^2 = 4. Another useful way to think of one-to-one correspondences are as functions which can be used to pair the elements in the input and output sets. Using our f(n) = n+1 example, we see that it pairs up the collection of integers with itself, using the pairing (0,1), (1,2), (2,3) and so on, since 0 is sent uniquely to 1, 1 is sent uniquely to 2, and so on. * * * # How can we tell if two sets are the same size? * * * The reason those concepts above are useful for us right now is that they let us define a notion of sets being the same size, even when we can't count the two sets. Consider this: if someone hands you a pile of oranges and a pile of apples and asks if there's the same number of apples and oranges, one way to find out is to count the number of fruit in each pile and compare the numbers. For example, the pile of oranges might have 5 oranges, and the pile of apples might have 4 apples. You could then tell the person that they do not have the same number of apples and oranges, because 5 is not equal to 4. However, there is another way to reach this conclusion without counting the piles. You could repeatedly take 1 apple and 1 orange from each pile at the same time and set them aside. If the piles have the same amount, you'll be left with two empty piles in the end. But, if one pile has more than the other, you'll be left with one empty pile, and one pile with some fruit remaining. In our example of 5 oranges and 4 apples, you'll be left with 1 orange and 0 apples. This will let you know that there are not the same number of apples and oranges. **What does this have to do with that stuff about functions?** When we're pairing off the apples and oranges and taking them away one at a time, we're implicitly attempting to define a one-to-one correspondence between the set of apples and the set of oranges. **So why would we compare apples and oranges like this when we could count them?** Counting works great for apples and oranges because apples and oranges are usually handed to us in finite piles. If instead, someone handed you the set of integers and the set of real numbers and asked you whether they were the same size, things would be a bit more difficult. In that case, you can't wait until you've counted both sets to see if the resulting numbers are equal, since you'd never finish counting even just one of the sets. Naively, we might look at both sets, see that we can't count either, say they're both infinite and then declare that they are the same size, since they're both infinitely large. However, it turns out that if you use this alternate method, our notion will tell us that they are different sizes. We define two sets to be **of the same size** if there is a one-to-one correspondence between them. For example, the set of even integers is in one-to-one correspondence with the set of odd integers and hence they are the same size. To see this, consider the function that takes an even integer n and returns n+1. This pairs up each even number with a unique odd number, and covers all of both of the sets. As another example, without proof, the set of integers is _not_ the same size as the set of reals. There is no one-to-one correspondence between them. * * * # Cantor's Theorem * * * So now we can prove that there's different sizes of infinity. Specifically, we'll show that given any infinitely large set, there is a set which is infinite and of a different size. This set is actually a "bigger" infinity rather than a "smaller" one, which may be intuitively clear once we know that it is a different size, but we won't define those terms for now. **The statement of Cantor's Theorem:** Given an infinite set X, its power set P(X) is of a (larger) different size. The "larger" part is intuitive because any set can be embedded into its power set by sending the element x in X to the subset {x} in P(X). The point of the theorem is that there isn't any way to get a correspondence between the elements of X and all of the subsets of X. This is obvious for finite sets, where the powerset has exponentially more elements. It's not as clear for infinite sets. A consequence of this theorem is that higher order infinities can be repeatedly generated by repeatedly taking power sets. For example, if X is infinite, P(X) is bigger, P(P(X)) is bigger still, and so on. **The proof:** Suppose there is a one-to-one correspondence between X and its powerset P(X). We will show that a contradiction results and so this is impossible. Since the power set is the collection of all subsets of X, such a one-to-one correspondence gives us a pairing between elements of X and subsets of X, and so it allows us to label any subset S of X by an element of x. So we may write S\_x for the subset corresponding to the element x. Now, we will think of each element x in X as a possible state in a game, and we will think of the corresponding subset S\_x as the list of states that the next turn in the game can take you to. That is, S\_x gives the list of possible next states to choose from. Now, we define a **game sequence** to be a finite or infinite sequence (x\_1, x\_2, x\_3, ...) of elements in X (thought of as states), such that x\_(i+1) is always chosen from S\_(x\_i). That is, the "next" state in the sequence always has to be chosen from the possible states associated to the current one. We define an element x in X to be **finite** if every game sequence starting with x is finite. Now, finally, we consider the set Z which consists of all finite elements. That is, Z = {x, such that every game sequence starting with x is finite} How the Hypergame paradox relates to the proof should now be beginning to materialize. Our set Z is the collection of all "finite games", and so we can interpret it as the set of possible first turn choices in Hypergame. Since our proof of Cantor's Theorem begins with the assumption that we can label all of the subsets, and since Z is a subset of X, this means that Z = S\_x for some x, and we will discuss this particular x for the remainder of the proof. Essentially, we have assumed that there is a state x which is analogous to Hypergame. Our contradiction now results when we ask the question "Is x in Z", which corresponds analogously to "Is Hypergame finite". To complete the proof, we show that neither "yes" nor "no" can consistently answer the question, which demonstrates the impossibility of the assumption that each subset can be paired with exactly one element of X. **If x is in Z:** By the definition of Z, this means that every game sequence starting with x is finite in length. But we have assumed Z = S\_x and hence in this case, x is in S\_x. So there is a game sequence (x, x, x, x, ...), which satisfies the requirement that each subsequent element in the sequence is in the subset associated to the previous one. We've just repeatedly selected x from S\_x. This is a contradiction, since we have found a game sequence starting with x which is not finite, hence x is not finite, but x must be finite to be in Z. **If x is not in Z:** By the definition of Z, this means that x is not finite. That is, there is a game sequence beginning with x which is infinite in length. However, we have assumed Z = S\_x. So given any game sequence starting with x, the next element must come from Z, which is the collection of all finite elements. Hence the sequence must be finite in length. This is a contradiction since it implies that x is in fact finite. Given that we have reached a contradiction when we have only assumed that a one-to-one correspondence exists between X and P(X), we conclude that no such one-to-one correspondence can exist, and hence by our earlier definitions, X and P(X) are of a different size. * * * **So what's there to discuss?** Well. Maybe one of you decided to actually read this and had some interest, and had some questions about it. Perhaps some of you have some issues with the paradox: perhaps you think it isn't a paradox, or you see a problem with its statement. Maybe someone has some qualms with infinity or wants to talk about whether the idea of one-to-one correspondence actually captures the idea of size in a meaningful way for infinite quantities. I don't know, but maybe at least it isn't a politics or religion thread, so it's a welcome break for some of you. If you want to read the standard proof of Cantor's theorem: [here](http://en.wikipedia.org/wiki/Cantor%27s_theorem). If you want to read a section from where I got all this Hypergame stuff from: [here](http://docs.google.com/viewer?a=v&q=cache:2cOKqFvCRDEJ:www2.math.uic.edu/~kauffman/SatanCantor.pdf+Zwicker%27s_theorem&hl=en&gl=ca&pid=bl&srcid=ADGEESjZ4oAnvW58kwoYD_ioTSs3VJagP5E3MxL5TaAf86yT3h9TkajPNeSTyGD_pq2NIlOrX8ps8KBUmqM7_xVPlxY1dtsiS1NxVJ4--b1QUKtoQemZbdgUUGO1wvOJANCFOHcjNgaN&sig=AHIEtbTCFSMtzge-kvE8VDCFID447QtzEA). Might be a fun topic. But that’s a lot to read and understand at once. Got about halfway through I’ll finishes the rest after this post. In the mean time chess is not a finite game. What is useful about this when simpler proofs exist? Is it just for fun like finding new proofs of the Pythagorean theorem in a highschool geometry class? It’s similar to that, yeah. This proof came nearly a century after the original result, and its existence doesn’t represent any great shift in mathematics or anything. The result is considered very fundamental in set theory, and it’s kind of interesting to see alternate proofs of basic results, because sometimes it can get you to think in a different way or help highlight what is actually going on, so you can develop a better intuition. In this case, I personally just think its interesting that there’s a fairly straightforward way to match up the paradox and this version of the proof. That makes sense. It’s always nice to get a fresh look at stuff in mathematics. I also agree with you that more math threads could do this place some good, but unfortunately that long, well written proof and background information doesn’t leave much room for discussion. A real interactive thread would involve some problem solving between whoever happens to be around at the time. Actually, i think I do remember a thread about some kid asking for math homework help or something a while ago. Kinda fun. By the way, do you know where I can buy the box set for hypergame? I wonder what the included rulebook has to say on the issue of player 1 choosing Hypergame. Hypergame has this problem because of infinite recursion, thus it is technically infinite. For example, in coding. in the Constructor…. … playGame() … in the methods…. … public void playGame() { playGame() … } because playGame() is repetitively called, it will never result in an end. Of course, one can avoid this in programming by a break or a while loop (although break is considered improper programming technique). * * * As for infinity, because it has no definition, it is equally possible to prove that it is less than or bigger than itself. However, in calculus limits, they are reperesented as a variable that cancels out, for example, lim x—\> 0 (5x^2 + 3x/ 8x^2) = 5/8. This can also be seen using L’hospital’s rule, how slowly things cancel, but the size of infinity has nothing to do with the canceling; simply infinity in an equation is defined to be the same amount for the equation referred to throughout the equation. Thus, the size of infinity, is thus, non-necessary for performing mathematical operations (besides the sign change, but that’s why you have -infinity). Actually, you’re missing a logic check from the inside of that function. playGame() is only allowed to be called from within playGame() if it is shown not to be infinitely recursive. Otherwise it’s breaking the rules. The infinite amounts in this problem are different from the common convenience of the sideways in calculus. We aren’t saying that ∞ + 1 \> ∞ or anything of the like, we’re saying that one infinite set is bigger than another. It’s like different orders of infinity as opposed to values. Compare ∞ versus 2^∞. Ah, well then Hypergame breaks it’s own rules, and one would suggest that you create a seperate Game class which Hypergame runs. In Java, infinite recursion would just throw a Stack Overflow Error or a OutOfMemoryUsage Error, and since a computer’s memory is limited, I believe it fits the requirements of hypergame. The problem with HyperGame is actually with the definition itself. If you use an infinitely recursive technique without a break, you have got to expect it to go on infinitely. Thus by saying “It can’t”, it is impossible for such a game to exist. Ah, well the thing is with infinity is that it is an undefined number, thus in comparing it, one is attempting to define it. However, when comparing lim t—\> inf. y= t and lim t—\> inf y= 2^t, it can be seen that 2^t will reach infinity first (in terms of t), however, both will reach infinity eventually, although, at different terms of t. > Ah, well then Hypergame breaks it’s own rules, and one would suggest that you create a seperate Game class which Hypergame runs. Technically, it doesn’t break its own rules at any finite step. Since Hypergame can only chose a finite game and only adds 1 move to that finite game, it technically is finite. However, since it can choose itself an _infinite_ amount of times, the contradiction arises. Matt was pointing out that the inherent contradiction is this game provides an alternative proof for Cantor’s seminal theorem. > However, when comparing lim t—\> inf. y= t and lim t—\> inf y= 2^t, it can be seen that 2^t will reach infinity first (in terms of t), however, both will reach infinity eventually, although, at different terms of t. I feel like we’ve gone over this many times in the .999…=1 thread… None of them “reach” infinity in common sense terms, as reaching something implies a finite amount of steps. Rather, both are defined as having no upper bounds as their variable is allowed to have no upper bounds. They are just as “infinite” as eachother, but the ratio of (2^t/t) will greatly increase over an increase of t. In fact, this ratio approaches infinity and “reaches” it at just the same “time” as the other two functions. This post has been removed by an administrator or moderator This post has been removed by an administrator or moderator This post has been removed by an administrator or moderator > *Originally posted by **[TheAwsomeOpossum](/forums/9/topics/93615?page=1#posts-2051541):*** > > Ah, well then Hypergame breaks it’s own rules, and one would suggest that you create a seperate Game class which Hypergame runs. > > In Java, infinite recursion would just throw a Stack Overflow Error or a OutOfMemoryUsage Error, and since a computer’s memory is limited, I believe it fits the requirements of hypergame. The problem with HyperGame is actually with the definition itself. If you use an infinitely recursive technique without a break, you have got to expect it to go on infinitely. Thus by saying “It can’t”, it is impossible for such a game to exist. > > Ah, well the thing is with infinity is that it is an undefined number, thus in comparing it, one is attempting to define it. However, when comparing lim t—\> inf. y= t and lim t—\> inf y= 2^t, it can be seen that 2^t will reach infinity first (in terms of t), however, both will reach infinity eventually, although, at different terms of t. Impossibility is the whole point. Notice it is introduced as the Hypergame Paradox… > Can non math members play, or is this for math people only? How about a ‘easy’ explanation version? Hypergame: First person chooses a game, then the second person starts to play it. If the first person chooses tic tac toe, then the second person makes the first move in tic tac toe, and then the first person makes the second move. The thing is that the first person needs to choose a “finite” game. If Hypergame can be chosen, then it isn’t finite, so it shouldn’t be able to be chosen. If Hypergame can’t be chosen, then it is finite and thus should be able to be chosen. Therein lies the paradox. ‘easy’ enough? There’s so much you can say about the hypergame “paradox”. If a game is only finite _any time_ it is played, it will last a finite number of turns, it already can’t fit that definition. By choosing itself over and over, you’re creating an infinite amount of turns, and thus it is not always finite. It does not matter that there’s a possibility it becomes a finite game, as you just defined it as having to be _always_ a finite game, with a finite amount of turns. Chess is possible to end in a finite amount of turns, but it’s also possible to become an infinite game, which means it cannot be chosen, as it won’t _always_ be finite. I’m sorry, but you’d have to explain further why this is a paradox. If you choose hypergame as your selection every time, isn’t it obvious it can be an infinite game, so it should not be able to be chosen? > If Hypergame can’t be chosen, then it is finite and thus should be able to be chosen. This part I disagree with. How come it is finite by definition? Rather, the ability for hypergame to be an infinite game when it chooses itself means that it cannot choose itself, no matter what weird things our brains make up when we don’t choose it. Maybe it’s just the fact we’re trying to use contradicting concepts here. First off, chess is not an infinite game. If 50 moves are made without the taking of a piece or the advancement of a pawn, the game ends as a draw. A technicality, yes, but nevertheless in the rules of chess. > I’m sorry, but you’d have to explain further why this is a paradox. If you choose hypergame as your selection every time, isn’t it obvious it can be an infinite game, so it should not be able to be chosen? The reasoning is as follows: A Hypergame is defined as a game in which the first turn you choose a finite game to play. Thus, there is only one additional move to the usual finite amount of moves. I think you would agree that 1+(some finite number)=(some other finite number). Thus, since the Hypergame must then always be finite, it can choose _itself_. However, as matt pointed out, this causes a contradiction: it can now choose itself an infinite amount of times, thus making itself an infinite game, and thus contradicting its own nature. The reason you are having trouble pinning down whether the Hypergame is infinite or not is because it is neither. The Hypergame does not have a logical, consistent existence. The entire point was that matt used the Hypergame to provide an alternate _reductio ad absurdum_ style proof to prove Cantor’s Theorem. Saying that X has a 1-to-1 correspondence with P(X) is the same as saying that the Hypergame exists and is finite. Since the Hypergame cannot exist, there cannot be a 1-to-1 correspondence between X and P(X) if X is an infinite set. I’m going out on a limb here, but I think the way to relate this to the fact that there are infinitely more irrationals than there are rationals is to point out that each irrational can be “constructed” from a unique subset of **Q**. Thus, since there is not a 1-to-1 correspondence between **Q** and P( **Q** ), P( **Q** )= **R** is infinitely greater. Matt, please verify or negate my reasoning. I’m really not as well-versed as you are. EDIT: Even though chess is not an infinite game, I do believe that Checkers can be. > *Originally posted by **[Darkruler2005](/forums/9/topics/93615?page=1#posts-2051936):*** > > There’s so much you can say about the hypergame “paradox”. If a game is only finite _any time_ it is played, it will last a finite number of turns, it already can’t fit that definition. By choosing itself over and over, you’re creating an infinite amount of turns, and thus it is not always finite. It does not matter that there’s a possibility it becomes a finite game, as you just defined it as having to be _always_ a finite game, with a finite amount of turns. Chess is possible to end in a finite amount of turns, but it’s also possible to become an infinite game, which means it cannot be chosen, as it won’t _always_ be finite. > > I’m sorry, but you’d have to explain further why this is a paradox. If you choose hypergame as your selection every time, isn’t it obvious it can be an infinite game, so it should not be able to be chosen? > > > If Hypergame can’t be chosen, then it is finite and thus should be able to be chosen. > > This part I disagree with. How come it is finite by definition? Rather, the ability for hypergame to be an infinite game when it chooses itself means that it cannot choose itself, no matter what weird things our brains make up when we don’t choose it. > > Maybe it’s just the fact we’re trying to use contradicting concepts here. 1. If Hypergame can last an infinite number of turns, it cannot call itself. 2. If Hypergame cannot call itself, then all instances of the game being played will last a finite number of turns. 3. If all instances of the game end in a finite number of turns, Hypergame must be finite. 4. Since Hypergame is finite, Hypergame may call itself. 5. If Hypergame calls itself, it can last an infinite number of turns. 6. Return to 1. You get a loop of contradictory logic. The most obvious contradiction is 1 and 3. 1 is the premise, and 3 logically follows from that premise, yet also contradicts it. Hence the paradox. > *Originally posted by **[mxmm](/forums/9/topics/93615?page=1#posts-2052945):***\
> I’m going out on a limb here, but I think the way to relate this to the fact that there are infinitely more irrationals than there are rationals is to point out that each irrational can be “constructed” from a unique subset of **Q**. Thus, since there is not a 1-to-1 correspondence between **Q** and P( **Q** ), P( **Q** )= **R** is infinitely greater. Matt, please verify or negate my reasoning. I’m really not as well-versed as you are. I’m not sure if there are infinitely more irrationals than there are rationals. Irrationals (which I’m hoping refer to **(i)**, or **-1^(1/2)**, or the square root of a negative number) can only exist in conjunction with rationals. I think there might be a 1-to-1 correspondence between rational and irrational numbers, since for any irrational value of **x(i)**, there would also be a corresponding rational value of **x**. > EDIT: Even though chess is not an infinite game, I do believe that Checkers can be. If both players can get “kings” then the game is infinite, but I’m not sure whether or not that’s possible. =P > *Originally posted by **[mxmm](/forums/9/topics/93615?page=1#posts-2052945):*** > > I’m going out on a limb here, but I think the way to relate this to the fact that there are infinitely more irrationals than there are rationals is to point out that each irrational can be “constructed” from a unique subset of **Q**. Thus, since there is not a 1-to-1 correspondence between **Q** and P( **Q** ), P( **Q** )= **R** is infinitely greater. Yeah, that’s one way to show that the reals are bigger than the rationals. The only “problem” is that I don’t think I’ve seen a construction of the reals that obviously used every subset of the rationals. So you’d have to show that correspondence exists in a kind of roundabout way, which I’ll do below just for funzies. But yes, there is a one-to-one correspondence between P(Q) and R (or between P(Q) and the set of just the irrationals if you’d prefer), and so Cantor’s theorem shows that Q and R are not the same size. One of the standard constructions of the real numbers is as Dedekind cuts of rationals, which you can think of as subsets of the rationals satisfying certain properties. Since they are all subsets of the rationals, that construction gives you a clear one-to-one function from the reals to the power set of the rationals (send every real number to the subset that “constructed it”), but it doesn’t use all of the subsets, and doesn’t suggest an obvious one-to-one correspondence (it isn’t onto, just 1-1). It does show that the size of R is less than or equal to the size of P(Q) though. I can’t think of an obvious 1-1 correspondence between R and P(Q) at all really, and my first idea would be to use a correspondence between the naturals {0,1,2,…} and the rationals Q to get a correspondence between P(N) and P(Q), and then use a more obvious 1-1 function from P(N) into a subset of R, like the subset S is mapped to the real number which has a 1 in it’s n-th decimal place if n is in S (e.g.: {1,3,6} is mapped to 0.101001). After you compose those functions, it shows that the size of P(Q) is less than or equal to the size of R. Putting this together with the earlier result gives you that they’re the same size, and then you could use Cantor’s theorem to conclude that Q and R are different sizes. As a side note: Cantor originally proved that Q and R were different sizes before proving this more general theorem. I think his original proof was the one where he used a completeness property of the reals (something like that nested open intervals in R have nonempty intersection) to find a contradiction when assuming that there is a sequence of real numbers that hits all real numbers in some interval. I think later he came up with the more well-known diagonal argument where you attempt to list the reals, then construct a new real by going down the diagonal making sure the numbers are different. > *Originally posted by **[Darkruler2005](/forums/9/topics/93615?page=1#posts-2051936):*** > > … the ability for hypergame to be an infinite game when it chooses itself means that it cannot choose itself… You’re correct. But not being selectable is the same as being infinite because Hypergame is defined to be able to select all finite games. So if Hypergame can’t choose itself, then Hypergame is infinite. Now, Hypergame being infinite means there’s a way to play it that goes on forever, but because of how it’s played that means you select a finite game, and then play a finite game for infinitely long, which seems to be impossible. **EDIT:** Irrationals in all of this refers to real numbers which are not rational. That is, numbers which have decimal representations but may be infinitely long and non-repeating. Friendly examples include Pi, e, sqrt(2). The real numbers consist of the rationals and the irrationals, which are mutually exclusive subsets of the reals. These are not to be confused with imaginary numbers which are part of the complex numbers: an extension of the real numbers that includes all real numbers and additionally stuff like the square root of negative numbers. DoubleEdit: Standard examples of irrational numbers are standard :D Square root of -1 is a complex (imaginary) number, not an irrational. Rational are numbers that can be described as a ratio between two integers (‘normal’ fractions). Irrationals include the rest of them, like pi, e, and the square root of 2. > First off, chess is not an infinite game. If 50 moves are made without the taking of a piece or the advancement of a pawn, the game ends as a draw. A technicality, yes, but nevertheless in the rules of chess. Actually according to Wikipedia if I reading this right it only says a player can claim a draw if the want they don’t have to so it can go on forever. > The reason you are having trouble pinning down whether the Hypergame is infinite or not is because it is neither.> You get a loop of contradictory logic.> You’re correct. But not being selectable is the same as being infinite because Hypergame is defined to be able to select all finite games. So if Hypergame can’t choose itself, then Hypergame is infinite. Now, Hypergame being infinite means there’s a way to play it that goes on forever, but because of how it’s played that means you select a finite game, and then play a finite game for infinitely long, which seems to be impossible. Okay, I can live with that. However, this should point out that you would not logically be able to define hypergame like that. > First off, chess is not an infinite game. If 50 moves are made without the taking of a piece or the advancement of a pawn, the game ends as a draw. A technicality, yes, but nevertheless in the rules of chess.> Even though chess is not an infinite game, I do believe that Checkers can be. I don’t remember the 50-moves rule, but yes, that would be a technicality. If it didn’t have that rule, it would be possible to become infinite. > I can’t think of an obvious 1-1 correspondence between R and P(Q) at all really The easiest way would be to notice, as you said, that P( **N** )=P( **Q** ). I mean “=” here to imply that there is a 1-to-1 correspondence. Then, using the example similar to yours, show that all reals have a unique binary form, and that all binary forms are exhausted. In other words, do everything the same in your example except use base-2 instead of base-10. Sorry if that’s what you implied… I just saw that you said “decimal” place. > However, this should point out that you would not logically be able to define hypergame like that. Exactly. > Okay, I can live with that. However, this should point out that you would not logically be able to define hypergame like that. This is a key part of the proof. We reduce the problem of infinite sets down to a problem that is analogous to this, which gives a reductio ad absurdum. This post has been removed by an administrator or moderator Uh, Kasha, computers evaluate on a terms of priority, for example, in Java, int x = 0; if(x==0 || 5/x == 1) {… this statement does not throw an exception, because if(x==0) is done first, and results in TRUE, thus, the compiler skips the rest of the statement. Thus an infinite number of terms means it HAS to call itself. The return, calls the beginning of the method, before it finishes. For example int x = 0; public void play() { play(); x++; } due to it being an infinite loop, x would never go greater than 0 before a StackOverflowError was thrown. The method completes the recursive calls of play(), and stores the rest of the method in a stack, for completion later. However, eventually, the stack gets too large, and the method crashes into the exception. Thus, x never is able to grow. That’s why Hypergame (at least in programming), cannot exist because it’s rules contradict each other. The rules are A. The game cannot be infinite (the limited amount of space on a computer) B. The method recursively calls itself immediately in the method (causing an infinite loop) Thus the program crashes. And doesn’t work. This post has been removed by an administrator or moderator