The Axiom of Choice
It is stating that for every indexed family of non empty sets there exists a function which choosesan element of each set.
Problem: The Axiom of Choice just states the existence of a choice function but not its construction. So it is refused by some mathematicians.
Infinite hatted queue paradox:
Setting:
-A finite number of prisoners are placed in a line, facing forward.
-The warden places either a black or a white hat on each prisoner’s head.
-Then he asks, starting from the back of the line, each prisoner for the colour of his own hat.
-Any prisoner who guesses correctly may go free.
-Every prisoner can hear everyone else’s guesses and whether or not they were right.
-If all prisoners can agree on a strategy before, what is the best?
Solution:
Use an abelian group structure, like the modular arithmetic. Therefore convert the colours into numbers. Then each prisoner, except the first one, can determine his colour by considering the difference between the sum of hat colours his predecessor states and the sum of hat colours he counts. (sum = sum of hat colours in front of the prisoner)
All, except the first one, can go free.
Changes in the infinite case:
-There is a countable infinite number of prisoners.
-Prisoners cannot hear previous guesses and whether they were correct.
Solution:
Substitute the colours as before by numbers and get an infinite sequence of numbers. Define an equivalence relation, by stating that 2 sequences are equivalent, if they are equal after a finite number of entries. Use the Axiom of Choice to pick an element out of each equivalence class.Then all prisoners take the representative, they have all agreed on before, after identifying the real sequence of hat numbers with the corresponding equivalence class. Now they guess as if they were in the pre-chosen element in that equivalence class.
After a finite number of incorrect guesses, each prisoner will guess his colour correctly!
The Banach-Tarski Paradox
Its statement is, that given a solid ball in the 3-dimensional space, there exists a decomposition of that ball into a finite number of disjoint subsets, which can be rearranged by translations and rotations to result in two identical copies of the original ball.
Important steps of the proof:
- Find a paradoxical decomposition of the free group in two generators
- Find a group of rotations in 3-d space isomorphic to the free group in two generators
- Use the paradoxical decomposition of that group and the Axiom of Choice to produce a paradoxical decomposition of the hollow unit sphere and then transfer it to the solid ball.
Sources:
-The Banach-Tarski Paradox (Stan Wagon)
-
-
-