This is the title of a talk I gave at the CMU Graduate Student Seminar on Jan. 17, 2013.
Consider the following puzzle: infinitely many prisoners are put together into a room. Each is given either a white, or a black hat. A prisoner can see the color of all the other prisoner's hat, but not the color of his own hat. Each prisoner is then taken apart from the others, and asked the color of his own hat. If he answers correctly, he is freed. The prisoners are forbidden to communicate in any way once they are given their hat, but can agree on a strategy beforehand. How many prisoners can you guarantee to free ? In this talk, I will discuss the solution to this problem, and explain how to generalize it to obtain a strategy predicting (with high accuracy) the future values of a function, given only its past values. This counter-intuitive result will rely heavily on the axiom of choice (AC). Time permitting, I will also discuss what happens if one takes the above to be evidence that AC is wrong. For example, I will prove that assuming AC is false, it is possible there exists an equivalence relation on a set X which has strictly more equivalence classes than elements in X...