My favorite application of choice, known as ultrafilters: You know those "mathematicians wearing hats" games, where the solution is a Hamming code or some kind

My favorite application of choice, known as ultrafilters: You know those "mathematicians wearing hats" games, where the solution is a Hamming code or some kind of modular arithmetic thing? Here's one where there's no winning strategy. You have N mathematicians wearing hats whose colors are chosen uniformly and independently at random from a set C. They can see each others' hats but not their own. Simultaneously and without communication, each mathematician must guess their own hat color. Everyone who guesses right wins, and everyone who guesses wrong loses. A strategy maps (other mathematicians -> hat color) -> guess of your hat color, or if you're guessing randomly, then a distribution of guesses. No matter what strategy is chosen, N/|C| players win in expectation. There's no trick to improve this, though you can change the distribution of how many players win. For example, you can guarantee that at least floor(N/|C|) of them win. This is neat in that it works even in a derandomized setting, where the strategy must be deterministic and the hats are assigned maliciously by an opponent who knows the strategy. (This setting is easier to work with for infinite C, because you don't need to worry about probability distributions on infinite objects.) But if |C| > N, then you can't guarantee that anyone wins. OK, but what if there are infinitely many mathematicians, and you have the axiom of choice? In that case, there exists a strategy which guarantees that all but finitely many players will win — that is, the overwhelming majority of them will win. This works no matter how big C is, even if C is infinite, even if it's vastly larger than the set of players (eg if it's uncountable but the players are countable). Why? Well, consider the relation that two hat assignments are "almost the same" iff they differ in only finitely many places. This is an equivalence relation, so we can divide the space of hat assignments into equivalence classes. Assuming choice, there is a function F which maps an equivalence class to some element of it. Since these equivalence classes ignore finite differences, everyone can tell what equivalence class E has been assigned even without knowing their own hat color, so can guess their own color according to F(E). By construction this is in E, so it differs from the true assignment in only finitely many places, so all but finitely many players win. (The same holds for finitely many players too, but a strategy where all but finitely many players win is less impressive there.)