Let $\mathsf C\_n$ denotes the statement: 


*for any family $\mathcal F$ of $n$-element sets there exists a choice function (i.e., a function $f:\mathcal F\to\bigcup\mathcal F$ such that $f(F)\in F$ for all $F\in\mathcal F$).*


It is known that $\mathsf C\_2\Rightarrow \mathsf C\_4$ in ZF. 


This fact suggests introducing a partial preorder $\preceq$ on the set $\mathbb N$ of positive integers defined by $n\preceq m$ if $\mathsf C\_m\Rightarrow \mathsf C\_n$ in ZF. 


Also we can write that $n\cong m$ if $\mathsf C\_n\Leftrightarrow \mathsf C\_m$.


It is easy to show that $n\preceq m$ if $n$ divides $m$. So, $1\preceq n$ for any $n\in\mathbb N$ and $2\preceq n$ for any even number $n$.


On the other hand, $\mathsf C\_2\Rightarrow \mathsf C\_4$ implies that $2\cong 4$.


What else is known about the partial preorder $\preceq$? Maybe there exists a precise (arithmetic) description of this preorder.


A more specific question: is $2^n\cong 2$ for any $n\in\mathbb N$?


I know that similar questions were studied by Mostowski, Tarski, Truss, Jech so maybe the answer is already known?



The partial preorder on $\mathbb N$ generated by the finite axioms of choice
In Jech's "The Axiom of Choice", at the end of Chapter 7, he formulates the following condition on two natural numbers $n>m$:



> 
> (S) There is *no* decomposition of $n$ into $p\_1+\ldots+p\_s=n$ such that $p\_i>m$ is a prime number for all $i$.
> 
> 
> 


And he goes on to prove that if $\mathsf{C}\_k$ holds for all $k\leq m$, then (S) implies $\mathsf{C}\_n$, and moreover if (S) fails, then there is a model of $\mathsf{C}\_k$ for all $k\leq m$, but $\lnot\mathsf{C}\_n$.




---


So, for example, if the Goldbach conjecture is true, then $\mathsf{C}\_2$ implies nothing more than $\mathsf{C}\_4$, since in that case every even number other than $2$ is the sum of two primes, and other than $4$ these primes have to be odd.


So this is now a question about number theory, rather than set theory, and I will let the experts in that field make their remarks.


*Emil Jeřábek notes in the comments that every $n\geq 8$ is the sum of some amount of $3$s and $5$, both prime and both odd, so $\mathsf{C}\_2$ does not extend its reach beyond $\mathsf{C}\_4$.*


