# Choice function on family of fixed size sets -- what is the relationship between these axioms

For each $$n$$, consider the following property $$\text{ACF}_{n}$$ (axiom of choice on finite sets of size $$n$$):

For any family of sets $$\mathcal{F}$$ such that for all $$S \in \mathcal{F}$$, $$|S| = n$$, there is a choice function on $$\mathcal{F}$$ (i.e. a function $$f$$ such that $$f(S) \in S$$ for all $$S \in \mathcal{F}$$).

I'm currently interested in the situation where $$n \in \mathbb{N}$$ (and $$n \geq 2$$, since $$\text{ACF}_0$$ is just false and $$\text{ACF}_1$$ is a theorem of ZF), although $$n$$ being an infinite cardinal is interesting as well. For example, $$\text{ACF}_2$$ is the axiom of choice used in the famous example of picking a sock from an infinite family of pairs of socks.

Despite this being such a natural weakening of the axiom of choice (in my opinion), I couldn't find a name for this family of axioms. I believe that it is no stronger than the Boolean Prime ideal theorem; $$\text{ACF}_n$$ is true if there is a total order on $$\bigcup_{i \in I} S_i$$ (since in this case, the choice function can simply take the minimum of the set), and BPIT implies that every set can be totally ordered.

My main question is: are the $$\text{ACF}_n$$ independent of each other? At first, I thought $$\text{ACF}_n$$ would be weaker -- and probably strictly weaker -- than $$\text{ACF}_{n+1}$$, but actually I couldn't even figure out how to prove $$\text{ACF}_n$$ from $$\text{ACF}_{n+1}$$.

There are some implications, however. For example, $$\text{ACF}_2$$ and $$\text{ACF}_3$$ together imply $$\text{ACF}_4$$. Given a set $$S$$ of size $$4$$, we can pick a canonical member by first collecting all $$6$$ size-2 subsets, and applying the $$\text{ACF}_2$$ choice function on each one, picking the most frequently picked element. There can only be two-way or three-way ties, not four-way ties (since $$6$$ is not a multiple of $$4$$), so ties can be resolved by applying $$\text{ACF}_2$$ or $$\text{ACF}_3$$ again.

So what exactly is the relationship between all the $$\text{ACF}_n$$?

Edit: I realized that $$\text{ACF}_m$$ implies $$\text{ACF}_n$$ if $$m$$ is a multiple of $$n$$ (e.g. $$\text{ACF}_4$$ implies $$\text{ACF}_2$$) just by duplicating the elements. My new conjecture is that this is precise in terms of pairwise implications i.e. $$\text{ACF}_m$$ proves $$\text{ACF}_n$$ in ZF if and only if $$n \mid m$$. Is this actually true?

• Tarski proved that ACF${}_2$ implies ACF${}_4$. The proof is essentially what you wrote in the question, where you also assumed ACF${}_3$. The point is that, in case of a $3$-way tie, instead of invoking ACF${}_3$, you can just choose the one element not involved in the tie. Commented Aug 5, 2023 at 21:21
• Two references with a lot of information about implications between (conjunctions of) ACF${}_n$ axioms are: Andrzej Mostowski, "Axiom of choice for finite sets,'' Fund. Math. 33 (1945) 137--168 and John Truss, "Finite axioms of choice,'' Ann. Math. Logic 6 (1973) 147--176. Commented Aug 5, 2023 at 21:26
• More generally your idea for $ACF_4$ shows that if $n$ is not prime then $ACF_n$ follows from $ACF_m$ for all $m\leq n/2$ (pick a prime factor $p$ of $n$ and choose an element of each subset of size $p$; since $\binom n p$ is not divisible by $n$ the elements will not be chosen equally often and you can use this to choose a subset of size at most $n/2$). Commented Aug 5, 2023 at 22:25
• Related: Finite choice without AC AND Axiom of choice for sets of finite sets AND the two paragraphs beginning with "Chapter VI (pp. 95-96 & 99)" in (and my comment to) this MSE answer AND this 30 April 2007 sci.math post. Commented Aug 5, 2023 at 22:32
• There is a discussion of these choice axioms for $n$-element sets in Sierpinski's book Cardinal and Ordinal Numbers.
– bof
Commented Aug 6, 2023 at 3:02