Written by mkoconnor

Making Money Disappear Through Infinite Iteration

In Joel David Hamkin’s paper Supertasks and Computation, he relates the following puzzle: Suppose that you have a countable infinity of dollar bills, and one day you meet the devil, who offers you the following bargain: In the first half minute from now, the devil will give you two dollar bills, and take one from you in return. In the quarter minute after that, the devil again gives you two dollar bills, and takes one from you in return. And so on, in the eighth of a minute after that, and the sixteenth of a minute after that, etc. After a minute, the whole transaction is complete. Should you take this bargain?

The answer is “no” and the reason is that the devil could do the following: Think of the bills you have at the start as being numbered 1, 3, 5, etc. and imagine that the devil has an initial pile of bills numbered 2, 4, 6, etc. Then on the nth transaction, the devil gives you the two lowest-numbered bills from his initial pile and takes bill n from you (one can easily show that you have bill n in your possession at this point). Since the devil takes bill n from you on the nth transaction, he gets all the bills in the end and you end up with nothing.

So, even though you start with infinitely many bills and each transaction produces a net gain of one bill for you, after all the transactions are done you have nothing.

In that puzzle, the devil was able to use a tricky strategy to give you more than he took at each stage and still end up with everything. In the following puzzle, which made the rounds when I was a graduate student, no matter what the devil does, he takes everything from you!

You and the devil are taking a train ride together. The train stops at each ordinal. At stop 0, you have countably infinitely many dollar bills. At each stop, the devil does the following two things (in order):

  1. If you have nonzero number of dollar bills, the devil takes one and destroys it.
  2. The devil gives you countably infinitely many dollar bills.

Prove that no matter what the devil does, when the train reaches stop \omega_1 (the first uncountable ordinal), you will have no money.

Solution below.

For each stop \alpha which is before \omega_1, let f(\alpha) be the first stop by which all the dollar bills which you had at stop \alpha which will be destroyed by the devil before stop \omega_1 have already been destroyed by the devil.

Since you have only countably many dollars, f(\alpha) is a supremum of countably many countable ordinals, and is therefore itself countable.

Now, let g(\alpha) = \sup \{\alpha, f(\alpha), f(f(\alpha)), \ldots \}. As a supremum of countably many countable ordinals, g(\alpha) is itself countable.

Lemma. For any \alpha, at stop g(\alpha), you have no money.

Proof. Suppose that you have at least one dollar bill at stop g(\alpha). Then one of your dollar bills will be destroyed by the devil at that stop. Let that be dollar bill D. Then you must have had D at all stops f^{(n)}(\alpha) for sufficiently large n. In particular, there is an ordinal \beta such that you had D both at stop \beta and stop f(\beta). But, by the definition of f, this is only possible if D is not destroyed at any countable ordinal. But D is destroyed at stop g(\alpha), which is a contradiction. \square

Corollary. At stop \omega_1, you have no money.

Proof. Suppose not. Any dollar bill that you have at stop \omega_1 you must have had at some countable ordinal \alpha. But then, by the above corollary, that dollar was destroyed by stop g(\alpha). \square

6 thoughts on “Making Money Disappear Through Infinite Iteration”

  1. I follow the argument, but it’s still a bit confusing. Let’s assume for the sake of contradiction that at every stop you have at least two bills. Then consider the following strategy for the devil. Fix one of the bills you have at stop 0, and at any stop, choose a bill other than this one to destroy (this strategy just needs AC, and the fact that you always have at least two bills). Then you must have this bill at the end. So by the above proof, the assumption must be false, so there must be some stop at which you have only one bill (or none).

    Clearly, such a stop can’t be at a successor ordinal, because at any successor ordinal you have countably many bills. I suppose it must be at one of those g(\alpha), though I guess I don’t really know much about what the structure of those ordinals is like.

    Reply

  2. One way to think about the g(\alpha) is the following. Suppose that at some stop \alpha, you have exactly two dollar bills. The devil destroys one, but since we’re supposing that he’s helping you is determined to preserve the other. How might the devil decide to do it? When he gives you countably infinitely new bills at \alpha, he could choose a mapping from \omega (representing the bills he just gave you) onto some countable interval above \alpha, say \lbrack \alpha,\beta). Then you are safe at least until \beta.

    However, you’ve gotten many new bills at the intervening stops and the devil can use them to preserve your dollar until some higher countable ordinal \beta_1. Using the dollar bills gained there, you will be safe until \beta_2, etc. But by stop \beta_\omega = \sup\{\beta_i\}, all of your “safety” dollar bills will be gone, and you will have just the one dollar bill left which the devil will have to destroy. This stop will be g(\alpha) under this strategy of the devil’s.

    As you can see, there is not necessarily any particular structure on the g(\alpha)‘s, in that they can be unboundedly high up in the countable ordinals.

    Reply

    1. Even in the initial problem, how do we account for the fact that at each ordinal stop there is a positive net gain? Here you say that at g(\alpha) there are no money but are we accounting for the fact that the devil gives us infinite (or two in the case of the original problem) dollars after taking the dollar bill?
      Even if at g(\alpha) we were to have nothing, don’t our resources get replentish?

      Reply
  3. Pingback: Ordinal music | Complex Projective 4-Space
  5. Pingback: Making Money Disappear Through Infinite Iteration, Now In YouTube Form! – XOR’s Hammer

Leave a reply to isomorphismes Cancel reply