Another old blog entry, again about the foundations of math.
I recently came across one of the many videos on Youtube dealing with the problem of infinity. At the end of this posting, I am going to link some interesting ones for you. But the one I want to talk about deals with a very bizarre generalization from the finite to the infinite.
Let me first tell you the finite version. It is about a very nice trick which first seems impossible. Assume you are in a group of friends (i.e. finitely many, of course) with blue and red hats. Each of your friends can see all the other hats, but not his own. Your problem is that you want each member of the group to announce the correct color of his or her hat, one after the other. This is clearly not possible, but you can make it so that each but one announces the correct color. If you want to find a solution to this problem, go ahead. I’ll be waiting.
You certainly found the trick: The first person announces „red“, if the number of red hats he sees is even, and „blue“, if it is odd. You take this first round. At this point, all your friends will know the color of their hat. Neat, isn’t it? Moreover, you get a 50% chance to get your color right.
The video I am discussing generalizes this to an infinite number of friends, countable many. Now you can play the even-odd-trick only if you are in non-standard analysis and have a non-standard infinite natural number at your disposal. All standard friends will then get their hats correctly. But this is using a theory which is even more fantastic than the solution I show you below. If you up for a thought adventure go ahead and find a solution. Hint: You have to use the axiom of choice.
The proposed solution uses an equivalence relation on all sequences in the set {red,blue}. Two such sequences are considered equivalent if they are equal from some point on, i.e., they differ only in a finite number of places. This yields equivalence classes and you agree with your friends on a representative element of each and every equivalence class. Using this, each of your friends can come up with the same sequence of colors, and this sequence will agree with the correct sequence of hat colors from some point on, i.e., differ only at finitely many places. Note that all of you have the same sequence! So you, on number one position, only need to announce if you see an even or an odd number of discrepancies to this sequence. Then everyone will know if his hat color agrees with the color in the sequence or not.
A trained set theorist will immediately spot that the axiom of choice is needed to define a function Phi that maps any sequence to one representative. If this function exists it will compute the same representative even if we change a finite number of colors in the sequence. That is why the trick above works.
However, this is all too absurd for me to be considered of any value. Other mathematicians may disagree and find this to constitute a nice application of set theory. To me, it’s useless garbage. The problem is that there is absolutely no constructive way to compute the above wonder function Phi. To compute it you need to inspect the complete sequence at once. And this is not possible. You cannot get close to Phi(S) by inspecting the first N elements of the sequence S like you can get closer and closer to the square root of 2. After N elements of S, you know nothing at all about the Phi(S) you can choose.
In the video, there is another algorithm where you and your infinite number of friends announce their color at the same time. By announcing the color in the representative sequence, they will get „at most a finite number“ of colors wrong. In the finite case, this means they might get all wrong. This is again a useless generalization to the infinite case.
There is another trick if friend N can only see friends with a higher number as if you are standing in line. Again, if the first in the row announces the even or odd number of discrepancies, every following announcement (one after the other) can be made correctly. This does also work in the finite case as you will observe easily.
Posted at 2018/09/07.