Axiom of binary choice vs Axiom of finite choice

Binary axiom of choice: Every family of 2-sets has a choice function. Finite axiom of choice: Every family of finite sets has a choice function.

Taken as an axiom of set theory, how are these principles related: Is there any clever way to prove finite choice via binary choice, or is binary choice strictly weaker?

Solution 1:

Choice from pairs is in fact weaker than choice from finite sets. In fact, choice from pairs does not imply choice from $3$ sets, although it does imply choice from $4$ sets using a nice combinatorial argument.

You can find more details in Jech's Axiom of Choice book, in chapter 7.

Solution 2:

The study of finite choice axioms is quite interesting. Besides the reference given in Asaf's answer, there are a few papers covering this topic in detail. If you can track it down, I suggest you read

MR0360275 (50 #12725) Reviewed. Conway, J. H. Effective implications between the "finite'' choice axioms. In Cambridge Summer School in Mathematical Logic (Cambridge, 1971), A. R. D. Mathias and H. Rogers, eds., pp. 439–458. Lecture Notes in Math., Vol. 337. Springer, Berlin, 1973.

Let me quote from the nice review by R. C. Lyndon:

For $n>0$, let $[n]$ be the assertion that every collection of sets of cardinal $n$ admits a choice function. A. Tarski [Sur les ensembles finis, Fund. Math. 6 (1924), 45–95; Jbuch 50, 135] showed that $[2]$ and $[4]$ are equivalent ... This subject was developed by A. Mostowski [Axiom of choice for finite sets, ibid. 33 (1945), 137–168; MR0016352], and R. J. Gauntt [Notices Amer. Math. Soc. 17 (1970), 454, Abstract 70T-E12], in a recent work unknown to the author when this was written, gives a method for settling in principle all questions $[n_1]\&\dots\&[n_k]\Rightarrow[n]$?

Let $[n_1,\dots,n_k]$ be the assertion that a choice function exists for all $A_1\times \dots A_k$, where $A_i$ has cardinal $n_i$. It turns out that this condition depends only on $S=\langle n_1,\dots,n_k\rangle$, the additive semigroup generated by $n_1,\dots,n_k$, and thus we may write $[S]=[n_1,\dots,n_k]$. In the sequel, a prime-power refinement $T$ of $S$ is a semigroup $T$ containing $S$ and generated by prime-powers. If $G$ is a finite group, $\langle G\rangle=\langle n_1,\dots,n_k\rangle$, where the $n_i$ are the indices of all proper subgroups of $G$.

(1) For the condition $(∗)$: $[S_1]\&\dots\&[S_n]\Rightarrow[S]$, it is sufficient that, for all finite groups $G$ such that $S\subseteq \langle G\rangle$, some $S_i\subseteq\langle H\rangle$ for $H$ a subgroup of $G$.

(2) The same condition on all abelian $G$ is necessary for $(∗)$.

(3) For $(∗)$ it is sufficient that each of $\langle 2,5\rangle$, $\langle 3,4\rangle$, and every prime-power refinement $T$ of $S$ should contain some $S_i$.

(4) For $(∗)$ it is necessary that each prime-power refinement $T$ of $S$ contain some $S_i$.

Results (1), (2) and (4) are essentially due to Mostowski, who conjectured that the condition in (4) is also sufficient. (3) is new, and uses J. G. Thompson's classification of minimal simple groups ...

The proofs depend essentially on consideration of groups $G$ acting simultaneously on the $A_i$ ... The author also gives a table of all "essential" solutions of $[n_1],\dots,[n_k]\Rightarrow [n]$ for $n_1,\dots,n_k<n\le 64$. This paper is rich in explanations, examples, and unsolved problems.

For example, Conway's result give us that $[2]\Rightarrow[4]$, that $[2]\&[3]\Rightarrow[6]$, that $[2]\&[5]\&[3,7]\Rightarrow[10]$, etc. There are many additional results in the paper. For instance, as Conway states,

what can be said about the famous test case: $$\mbox{Do }[3] \& [5] \& [13] \mbox{ imply }[15]?$$ In particular, we show that there is no "effective" implication here, but that $[3] \& [5] \& [13]$ do (effectively) imply a weakened form of $[15]$ which in turn (ineffectively) implies that $[15]$ holds for well-ordered collections of sets, and so of course for countable collections of sets.

Let me add an unexpected and pretty application. In

MR2361620 Indexed. Shipman, Joseph. Improving the fundamental theorem of algebra. Math. Intelligencer 29 (2007), no. 4, 9–14,

J. Shipman studies extensions of the fundamental theorem of algebra. For instance: Assuming that $K$ has characteristic 0, that all elements of $K$ have square roots in $K(i)$, and that all odd-prime-degree polynomials in $K[x]$ have a root in $K$, then $K(i)$ is algebraically closed.

He then proceeds to extend this result by studying which collections of odd-prime-degrees are enough in the hypothesis to grant the conclusion. This leads to a characterization $(**)$ in terms of semigroups quite similar to Conway's results. Some details of the proofs are similar as well. This is not an accident; as Shipman indicates ([Co] is Conway's paper I have mentioned):

The inspiration for Theorem 1 was the work done by John H. Conway on "Finite Choice Axioms" in 1970, detailed in [Co]. Conway, building on earlier work of Mostowski and Tarski, identified a necessary and sufficient condition for effective implications between axioms of the form "Every collection of $n$-element sets has a choice function." Conway's group-theoretic condition is very similar to $(**)$, the difference being that one could use the semigroup $\langle H\rangle$ for any subgroup $H$ of a group $G$ acting fixed-point-freely on $\{1, \dots , n\}$, rather than requiring $G = H$. The present article also borrows some terminology, notational conventions, and proof ideas from Conway's work.