Friday, May 23, 2014

Thomson's lamp and the Axiom of Choice

Consider Thomson's lamp: a lamp with a pushbutton switch that toggles it on and off. The lamp starts in the off position, and then in the next half minute the button is pressed, and in the next quarter it is pressed again, and then in the neight eighth again, and so on. Then at the end of the supertask, the lamp is either on or off.

Now keep the lamp but change the story. During each of the ever shorter intervals, a coin is flipped and the switch is pressed if it lands heads, and not pressed if it lands tails. Moreover, the final state of the lamp depends on the results of the coin flips in the following ways:

1. The results of the coin flips determine the final state of the lamp.
2. For any sequence of coin flip results, if any one (and only one) coin flip had a different, the lamp's final state would have been different, too.
Surprisingly, the existence of a lamp that would work in this way implies a version of the Axiom of Choice. To see this, notice that if the coin flips are independent and fair, then the subset of the probability space where the lamp's final state is on is nonmeasurable.[note 1]

But of course, on some technical assumptions, the existence of a nonmeasurable set requires a version of the Axiom of Choice. So if we read the Thomson's lamp story in such a way that the final outcome is determined by which presses are made and which aren't, in such a way that changing a single press changes the final outcome, that story seems to commit us to a version of the Axiom of Choice.

Conversely, it is easy to use the Axiom of Choice for pairs to prove the existence of a function such as would be implemented by the lamp.[note 2]