ABSTRACT
This chapter takes the reader into the world of the infinite, where the Axiom of Choice seems at first like a simple, handy tool. Indeed, it proves to be just the thing to allow infinite sets of prisoners to win hat games. But it also allows the second player to win a two-move game that he should obviously not be able to win. The reader is introduced to the concept of different size infinities, and will make use of them to grasp a mysterious exponential expression, track down a robot, and try to pack 8's and Y's in the plane. At the end of the chapter is what seems like perhaps the most elementary theorem in graph theory: if a graph has no odd cycle, then it is bipartite---that is, its vertices can be split into two sets in such a way that all edges cross from one set to the other. Yet, to prove this theorem for infinite graphs, the Axiom of Choice is needed; and indeed, a simple example is given of a graph with no odd cycles for which no bipartition will every be exhibited.
