For each integer $n$, call ${\rm AC}(n)$ the axiom of choice restricted to families $(A_i)$ where $A_i$ has $n$ elements.

Tarski proved the funny following fact: ${\rm AC}(2) \Rightarrow {\rm AC}(4)$—if you know how to choose between 2 elements, you can choose between 4.

The proof is in fact quite easy. Consider a family $(A_i)$ of sets with 4 elements. I will use choice functions furnished by ${\rm AC}(2)$ to pick-up one preferred element from $A_i$. For simplicity, label the elements of $A_i$ as $\{a,b,c,d\}$ and remove the index $i$. Then, consider the set $\{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}\}$ of all pairs of elements of $A_i$. The hypothesis ${\rm AC}(2)$ allows to choose, for each of those pairs, one preferred element. Call $n_a,n_b,n_c,n_d$ the number of times $a,b,c,d$ has been chosen; one thus has $n_a+n_b+n_c+n_d=6$ and consider those elements which have been chosen the most often, those for which $n_?$ is maximal.

- If there is only one, let's choose it. (This happens in repartitions like $(3,1,1,1)$, etc.)
- If there are three such elements (the repartition must be $(2,2,2,0)$), let's choose the unique one which has never been chosen.
- There can't be four such elements because 4 does not divides 6.
- If there are two (repartition $(2,2,1,1)$), then use your 2-choice function on this pair!

The other funny, but more difficult, thing, is that ${\rm AC}(2)$ does not imply ${\rm AC}(3)$!

*Why?*because the group $\{\pm1\}$ can act without fixed points on a 2-elements set but cannot on a 3-elements set. I hope to be able to say more on this another day.
## No comments :

## Post a Comment