Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let there be 2 players, p$\mathbb{N}$ and p$\mathbb{R}$. They are playing the Set Cardinality Game where p$\mathbb{N}$ has to present some number n that has not been used in the game so far by either of the players and it is in the set of natural numbers $\mathbb{N}$. Afterwards the player p$\mathbb{R}$ has to take some real number from the set $\mathbb{R}$ that has not been used before too. E.g If p$\mathbb{R}$ chooses 4, then both p$\mathbb{R}$ and p$\mathbb{N}$ cannot use it any more. By taking one number at time from their sets they are passing the turns.

If the player p$\mathbb{N}$ cannot find such a number n anymore, he loses and p$\mathbb{R}$ wins and vice versa. The game finishes only if one of the players wins.

1. Given that any of them starts first, is there any strategy for p$\mathbb{R}$ to defeat p$\mathbb{N}$ in an infinite amount of time?

2. If not, how should the game be modified so that p$\mathbb{R}$ could win? The game rules cannot rely on the properties of the numbers in the sets, but only on their amount.

3. Can other players like p$\aleph_N$ defeat p$\mathbb{N}$ where p$\aleph_N$ has the set which is a superset of $\mathbb{N}$ and its cardinality is $\aleph_N$? Players with other cardinalities are also welcome. What is the precise amount of the steps p$\aleph_N$ would need to win?

I will appreciate solutions, explanations and also references what I should study to know more on the subject. I am still an undergraduate student.

share|improve this question
What is R, the reals? How long is the game? Longer than $\omega$ steps, I suppose? (You can use $\LaTeX$ expressions by enclosing in dollar signs.) –  François G. Dorais Feb 5 '12 at 14:36
None of the players can win in $\omega$ steps or fewer. With $\omega+1$ steps, pN's opponent can always win by choosing the first available natural number at each round, exhausting N in $\omega$ steps. –  François G. Dorais Feb 5 '12 at 14:40
Yes, they are reals, thank you for pointing out I can use $\LaTeX$. So if I understand, in general p$\aleph_N$ with a set A can be defeated by another player whose set is a superset of A in $\omega_N+1$ steps? –  Dávid Tóth Feb 5 '12 at 15:19
What if pN plays with a countable set not containing any real and they are playing in a universe where there is no subset of the reals of size $\aleph_1$? –  Ramiro de la Vega Feb 5 '12 at 16:29
@Ramiro: pN still can't win because she will exhaust all of N by herself in some countable ordinal number of steps. If pN plays first on limit rounds, then pR can just wait the game out copying pN's moves using an injection from pN's countable set into $\mathbb{R}$. If pR plays first on limit rounds, then it's less clear what happens. It's probable that a winning strategy for pR gives an injection from $\omega_1$ into $\mathbb{R}$, but that's not entirely clear to me right now. –  François G. Dorais Feb 5 '12 at 16:39

2 Answers 2

up vote 1 down vote accepted
  1. Yes.
  2. Any proper superset of $N$ will do. Just exhaust $N$ first and only play a non-member of $N$ when $N$ is exhausted, winning in the next step.
share|improve this answer
Thank you for your answer, together with the comments of François G. Dorais, it is clearer to me, however I have not thought yet of other universes like Ramiro de la Vega mentioned which may be worth exploring. –  Dávid Tóth Feb 7 '12 at 8:45
Reals always have an uncountable subset (uncountable inside the universe), supposing we are talking within $ZF$ or similar. I supposed that Ramiro was asking, what if $pR$ were somehow banned from stepping on $pN$'s candidate values, to which he received a perfect answer. Or am I just missing a more specialized topic/axiomatics here? –  Jirka Hanika Feb 18 '12 at 11:44

As Francois mentioned, pR can reserve an injective copy $C$ of pN's set and copy pN's moves using corresponding elements of $C$. If pR has to play first at a limit ordinal, he could just play from $R \setminus C$. As the reals are uncountable in any universe this is a winning strategy for pR.

share|improve this answer
You need some choice to keep picking numbers from R-C. Even if R-C is uncountable, I don't know how to write a strategy without an injection from $\omega_1$ into R-C, whose existence is not provable in plain ZF. –  François G. Dorais Feb 11 '12 at 3:32
Perhaps I'm missing something here. The game ends at a countable stage so pR's plays from $R\setminus C$ won't produce an injection from $\omega_1$ to $R$. If we need a more precise strategy, what about this? We may assume that the injective copy of pN's set is the set of positive integers $P$. For each turn $n<\omega$, pR plays -n. At every turn after that, pR plays the continued fraction defined by all previous plays of pN. –  Patrick Reardon Feb 13 '12 at 0:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.