Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There is a slot machine. You insert one coin, it destroy the coin and return countable number of coins. Then you can pick any one of the returned coin and put in the slot machine again.

Formally, each coin is an ordinal. let $f(a)$ be the coin you insert into the machine, $g(a)$ be the set of coins returned after inserting $f(a)$.

Certain conditions must hold for the function $f$ and $g$ for all ordinal $a, b \neq 0$.

  1. $f(a)=f(b)$ iff $a=b$
  2. $f(a)\in (\bigcup_{i<a} g(i)) \backslash \{ f(i) | i<a \}$
  3. $g(a)\cap g(b) = \emptyset$ if $a\neq b$.

You start with 1 coin $0$. so $f(0) = 0$.

Prove no matter what is the strategy for inserting the coins, there is an ordinal $\alpha < \omega_1$ where you lose all your coins. In other words, for any $f,g$ satisfying the above requirements, $$ \{f(i) | i<\alpha\} = \bigcup_{i<\alpha} g(i)$$

I learned about this an year ago. Now I have a hard time coming up with the proof. I can only find a simpler version of this problem as Ross–Littlewood paradox.

share|improve this question
3  
Could you explain the setup in a bit more detail? What's a strategy? What role does the ordinal play? It seems that a safe strategy would be to take one of the coins from the first return, put it in your pocket and never insert it; you will always have other coins to insert; so I presume that your definition of a strategy must somehow exclude this possibility? –  joriki Aug 8 '12 at 3:40
    
Joriki, my argument shows that the assertion "you will always have some other coin to insert" eventually becomes false. All those other coins will inevitably be played. –  JDH Aug 8 '12 at 3:52
add comment

1 Answer 1

up vote 8 down vote accepted

Let us suppose towards contradiction that you play according to a strategy that allows play to continue for $\omega_1$ many stages. At each countable stage $\alpha$, you have countably many coins $A_\alpha$ in your possession. One of them will be played right at that stage, and others perhaps will be played later. Let $B_\alpha\subset A_\alpha$ be the collection of those coins that will eventually be played at some countable stage, and let $\beta_\alpha$ be the supremum of the stages at which those coins will be played. Thus, every coin that you have at stage $\alpha$, if it will ever be played at a countable stage, will be played by stage $\beta_\alpha$.

Now, let $\gamma_0=1$, and $\gamma_{n+1}=\beta_{\gamma_n}$, and $\gamma=\sup_n\gamma_n$. This ordinal $\gamma$ is a countable limit ordinal since it is the supremum of a strictly increasing countable sequence of countable ordinals. Suppose that you have a coin $c$ to play at stage $\gamma$. You earned it at some earlier stage, before some $\gamma_n$. But in that case, if you were ever to play $c$, then you would have already played it by stage $\gamma_{n+1}$, strictly before $\gamma$. Thus, at stage $\gamma$ you must have no coin to play. Contradiction.

The argument amounts essentially to the fact about countable ordinals, that every function $f:\omega_1\to\omega_1$ has a closure point, an ordinal $\gamma$ such that $\alpha\lt\gamma\to f(\alpha)\lt \gamma$. Here, $f(\alpha)$ is the supremum of the stages where the coins that existed at stage $\alpha$ are played, if they are played at all. If $\gamma$ is closed under this function, then at stage $\gamma$, you can have no coins to play, since every such coin would have been born at an earlier stage $\alpha\lt\gamma$, and so if the strategy called for it to be played at $\gamma$ it would have already been played by stage $f(\alpha)$, which is strictly before $\gamma$.

One can show the existence of closure points in this general sense by simply iterating the function as I did above: $\gamma_0$ is arbitrary, $\gamma_{n+1}=\sup f[\gamma_n]+1$ and then $\gamma=\sup_n \gamma_n$ is the desired closure point, since any $\alpha<\gamma$ has $\alpha<\gamma_n$ for some $n$ and hence $f(\alpha)<\gamma_{n+1}<\gamma$.

share|improve this answer
add comment

Your Answer

 
discard

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.