Category Archives: Set Theory

August 23, 2008 · 11:17 pm

Set Theory and Weather Prediction

Here’s a puzzle:

You and Bob are going to play a game which has the following steps.

  1. Bob thinks of some function f\colon \mathbb{R}\to\mathbb{R} (it’s arbitrary: it doesn’t have to be continuous or anything).
  2. You pick an x \in \mathbb{R}.
  3. Bob reveals to you the table of values \{(x_0, f(x_0))\mid x_0\ne x\} of his function on every input except the one you specified
  4. You guess the value f(x) of Bob’s secret function on the number x that you picked in step 2.

You win if you guess right, you lose if you guess wrong. What’s the best strategy you have?

This initially seems completely hopeless: the values of f on inputs x_0\ne x have nothing to do with the value of f on input x, so how could you do any better then just making a wild guess?

In fact, it turns out that if you, say, choose x in Step 2 with uniform probability from \lbrack 0,1\rbrack, the axiom of choice implies that you have a strategy such that, whatever f Bob picked, you will win the game with probability 1!

Continue reading →

11 Comments

Filed under Puzzles, Set Theory

August 22, 2008 · 4:54 pm

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.

Continue reading →

3 Comments

Filed under Ordinals, Puzzles, Set Theory

August 16, 2008 · 11:02 pm

One Puzzle with Two Totally Different Solutions

Peter Winkler‘s excellent book Mathematical Puzzles: A Connoisseur’s Collection has in it the problem of finding a partition of \mathbb{R}^3 into disjoint non-trivial circles. (Here “non-trivial” means “not a point.”) Winkler gives a very clever solution which is purely geometric.

Later, I read the same problem in Krzysztof Ciesielski‘s excellent book Set Theory for the Working Mathematician. In that book Ciesielski gives an almost purely set-theoretic solution.

I’ll discuss both solutions below. 　(Don’t read on yet if you want to think about the puzzle first.)
Continue reading →

4 Comments

Filed under Ordinals, Puzzles, Set Theory