Spoiled for choice

 Hi! I'm Atul, in my last year of school and this is going to be my first blog post. For an introduction, I have a bronze at the IMO and a silver at the APMO this year. Apart from math, I also love reading, playing table tennis and making terrible jokes. Something I seem to miss out on saying often is that I love cats, especially colourful ones. Anyway, let's begin!

Like many things in math, the axiom of choice has a deceptively simple statement. All it says is - "Given a collection of nonempty sets, it is possible to pick an element from each of them". That... sounds pretty obvious and something that just should be true. And well, it is. At least for a finite collection of sets, it is definitely true. With some thought, it's also clear how to do it if the collection is countably infinite. But what if the number of sets is just extremely huge? When the sets are uncountably infinite, that's when the problems begin.

So far I've been rather handwavy, so let's get the formalities out of the way. A function $f$ defined on a collection of nonempty sets $X$, is called a choice function if $f(S) \in S$ for all $S \in X$. The axiom of choice states that every collection of sets $X$ has a choice function.

I should clarify though - although the axiom of choice leads to some very strange and crazy results, it is completely consistent and there's no "contradiction" that you can obtain from this. 

There are many statements that can be shown to be equivalent to the axiom of choice, such as "The cartesian product of nonempty sets is nonempty" or "Every set of numbers can be well-ordered". The proof of the first one isn't too hard and you can try it as an exercise, the second one uses ordinals, which are too complicated for this blog post, so I won't do that either.

Perhaps one of the most famous consequences of the Axiom of Choice (Or AC for short) is the Banach-Tarski Paradox, which states that "given a solid ball in 3d space, it can be split into finitely many pieces and rearranged into two solid balls of the exact same radius", which sounds ridiculous. But, I'm getting repetitive, this is pretty complicated too, and uses group theory, so not that either. 

So what will we do, you ask. Well let's beign with a simple sounding problem and then move on to more cool ones. They won't be boring, I promise.

Problem 1: Prove that every infinite set of numbers has a countably infinite subset.

Proof: The naive approach to this would probably be to just keep picking elements, don't we just get an infinite subset? The problem is that that only lets you get a subset with an arbitrarily large number of elements, but never infinite. And in fact, this problem cannot be solved without the axiom of choice.

Say $S$ is this infinite set of numbers and let $X$ be the power set of $S$. Let $f$ be a choice function on $X$. Define a function $g$ the following way. $g(1) = f(S)$ and $g(n) = f(S \setminus \{g(1), g(2), \cdots, g(n-1)\})$ for $n \geqslant 2$. This looks pretty similar to what we did above, but here there's no "choice" that needs to be made, the function is well-defined because the choice function does all of that for us. But fine that's still underwhelming.

Let's try an actually interesting (and counterintuitive) problem now:

Problem 2: There are countably many gnomes with hats in countably many colours. Each gnome can see the colours of every hat except the one that’s on his head. The gnomes can strategize before the hats are on their heads, but they cannot talk or communicate with each other once the hats are on. Show that they can figure out a strategy such that all, but finitely many of them will guess the colour of their hat correctly (all gnomes guess simultaneously).

Proof: This seems pretty messed up and no way it could be true. Unfortunately with the axiom of choice, it is possible. The idea is pretty clever and hard to think of if you haven't seen it before. Let $S$ be the set of all infinite sequences of natural numbers, FOR EXAMPLE: $1, 4, 5, 1, 2, \cdots$ Define an equivalence relation where $x \sim y$ if $x,y \in S$ and $x,y$ differ in at most finitely many places (you can also think of this as saying beyond a point $x$ and $y$ are the same sequence). Then, let $X$ be the set of all equivalence classes, and let $f$ be a choice function on $X$.

The gnomes then order themselves $g_1, g_2, \cdots$ and also order the colors $c_1, c_2, \cdots$ beforehand. Then, they consider the sequence of colours that the respective gnomes are wearing, clearly all gnomes see the entire sequence (call this sequence $s$) apart from one place (their own). But by the way the equivalence relation was defined, this is enough to determine the equivalence class (say $E$) that $s$ belongs to. Then, the $k$th gnome guesses the $k$th number in the sequence $f(E)$. Once again, by the way, the equivalence relation was defined, $f(E)$ and $s$ differ in finitely many places, and hence finitely many gnomes guess incorrectly, as desired. $\blacksquare$

If you thought gnomes were smart, well you'd be right, but ducks are even smarter, as we'll see in this next problem:

Problem 3: There are $100$ identical rooms with countably many boxes labelled with natural numbers. Inside each box, there is a real number. After discussing a strategy, $100$ ducks are sent to different rooms without any means of communication after that. While in the room the duck can open up boxes (perhaps countably many) and see the real number inside. Then each duck needs to guess the real number inside one of the unopened boxes. Show that there is a strategy that guarantees at least $99$ of those ducks makes a correct guess.

Proof: No, I promise the problem is true (if you actually believe that the problem statement even might be true, then you're either crazy or a genius). This seems even crazier than the previous one, there at least finitely many gnomes guessed wrong, but here at most one does?! Well look at the solution and see for yourself.

Define $X$ the same as the above solution, but with real numbers instead of natural numbers being elements of the infinite sequences. The fact that we're now using real numbers (which are uncountable) instead of natural numbers (which are reasonable and countable) actually does not change anything, we might as well have allowed uncountably many hats, that would have worked too, check it for yourself! But that's where the similarity ends, this time, the ducks are going to be a lot smarter. 

As above, let $f$ be the choice function on $X$ and let $g(S)$ denote the last digit at which $S$ and $f(S)$ differ (for some infinite sequence of reals $S$).

Number the boxes $B_1, B_2, \cdots$ and create $100$ groups, $G_1, G_2, \cdots, G_{100}$ where $G_i$ contains all boxes numbered $i \pmod {100}$. Let $b_i$ (for $1 \leqslant i \leqslant 100$) denote the sequence of real numbers in the boxes $B_i, B_{i+100}, B_{i+200}, \cdots$.

Let's pick a duck, say duck numbered $k$. Then the duck follows a two-stage process: in the first stage, it opens every box not in $G_k$. Therefore, it knows the sequences $b_1, \cdots, b_{100}$ except for $g_k$. It then computes the following number $$N_k = \max(\{b_1, b_2, \cdots, b_{100}\} \setminus \{b_k\}) + 1$$Then in the second stage, the duck opens all boxes of the form $B_{100i + k}$ for $i > N$ and then obtains some number say $b_k'$, and then guesses the $N$th digit of $f(b_k') = f(b_k)$ (where the equality is due to the equivalence relation).

The reason this works is that suppose some duck, say duck $k$, guesses wrongly. Then that means that $f(b_k)$ and $b_k$ differ in the $N$th place, and so $g(b_k) \geqslant N > b_i$ for any $i \neq k$. Since this cannot happen for two ducks (as there can be at most one strict maximum), it follows that at most one duck guesses wrongly, and so at least $99$ guess correctly, as desired. $\blacksquare$

That... was quite something. Now you've seen first-hand the weirdness that such an innocent and simple-looking statement can lead to. Before you give up hope in math, there's a more sane alternative for all of this. It's called the axiom of countable choice, where it restricts $X$ to be a countable collection of sets. This avoids all of the crazy and weird results due to the AC but also leaves behind all the nice things you need to prove results in analysis.

Oh and one last thing, if you enjoy doing puzzles, you may want to re-read the blog post again, begin from the beginning, or so I've been told often. If you need some help, here's an extract from a nonexistent book:

"staring into the Abyss, i was staying with the Cinians when i heard a sound below. listening to songs by Sia, i was doing pretty much nothing when i saw a couple of Mice scurrying across the floor. i nearly dropped my Purse in fright; that wouldn't do, i was the Scion of a family known for bravery. i was curious though, so i followed them, over the Wire fence, nearly getting my Hair caught in it. i don't know why i felt so drawn to them, maybe it's because at the Core, i'm a Rat too."

To finish, you may want to look at places with numbers, which might help. Anyway, good luck!

~Atul