Lesson 2

The axiom of choice is one of the ZFC axioms, seemingly obvious. And we have already implicitly used it — for example, when selecting a countable subset in any infinite set. The axiom states that it is possible to choose one element from each set of any collection of non-empty sets: for any collection of non-empty sets \(\{X_{i}\}_{i \in I}\) there exists a function \(f\) such that \(f(i) \in X_{i}\) for any \(i \in I\). As a rule, proofs based on this hypothesis are non-constructive. Gödel showed that it cannot be disproved, and Cohen — that it cannot be derived from other axioms.

Despite the apparent obviousness of the hypothesis, it is worth remembering that intuition can often fail when working with infinite sets. We already considered the story of Hilbert's hotel above; now let us consider the story of Santa Claus. Imagine that one minute before the New Year, Santa Claus comes to the children with an infinite bag of candies: the candies are numbered with positive integers. One minute before the New Year, he gives the children candy 1, half a minute later — he takes candy 1 back and gives candies 2 and 3, a quarter of a minute later — he takes candies 2 and 3 back and gives candies \(\{4,5,6,7\}\). And so on. How many candies will the children have on New Year's Day? On the one hand, the number of candies with the children doubles each time. But in fact, there will be no candies with the children on New Year's Day: every specific candy will be taken back by Santa Claus.