Axiom of choice for sets of finite sets

Question

The question I am going to ask is really to satisfy my curiosity, as I am not at all an expert of the subject and do not plan to really work on it. Hence, if you think the question is not suitable for MO, I'll delete it. I did some browsing but could not locate any answer, but maybe I missed something simple.

Take ZF as a basis. If $Z\subset\omega$, denote by $AC(Z)$ the axiom of choice for sets of (finite) sets whose cardinality is in $Z$:

$AC(Z)$: If $x\not=\emptyset$ and for all $y\in x$ we have $|y|\in Z$, then there is a choice function on $x$.

Thus $AC(\omega)$ is the axiom of choice for sets of finite sets, and $AC(\{n\})$ (for $n\in\omega$) the axiom of choice for sets of $n$-elements sets. The implications between $AC(Z)$ for finite $Z$ and $AC(\{n\})$ have apparently been well studied in the first years of the 70s (and before by Tarski and Mostowski), I don't know to which point the question is entirely solved.

Just to give an idea, some (classical ?) implications I found in the literature are:

\begin{align*}AC(\{2\})&\Leftrightarrow AC(\{4\}),\\ AC(\{3,7\})&\Rightarrow AC(\{9\}),\\ AC(\{2,3,7\})&\Rightarrow AC(\{14\}). \end{align*}

It is easy to see that $AC(\{n\cdot m\})\Rightarrow AC(\{n\})$: Given $x$ containing $n$-element sets, there is a choice function on $\{y\times m\,:\,y\in x\}$ by $AC(\{n\cdot m\})$, the projection on the first factor gives a choice function on $x$. Thus, if $Z$ contains all the multiples of some given $n$, then $AC(Z)\Leftrightarrow AC(\omega)$.

My question is whether there is some kind of converse:

If $AC(Z) \Leftrightarrow AC(\omega)$, can we say something about $Z$ ?

For instance, I am sure that $Z$ cannot be finite, but can it be Dedekind finite ? Must it be "big" in any appropriate sense ?

Answer 1

I think such a set must contain a multiple of $p$ for each prime $p$. Otherwise, there is nothing to rule out the possibility of a bunch of sets of size $p$ where you are able to choose an action of the cyclic group of order $p$ on each set by. no further structure. I bet you can prove this with symmetric models.

On the other hand, if you have a multiple of $p$ you get $p$, and if you have all $p\leq n$ you get $n$ by one of the classical results of this theory (I think Tarski?).

The reason this works is because of groups. Given a set of sets of size $n$, you get a set of $S_n$-torsors - the sets of total orderings of each of the sets. If, for any set of $G$-torsors, you can reduce it to a disjoint union of sets of $H$-torsors for $H$ a subgroup of $G$, by induction you can trivialize any set of $G$-torsors for any group $G$.

This induction step follows from the axiom of choice for sets of size $p$ for each prime $p$: Because every group $G$ has a subgroup of order $p$ for some $p$, you can choose one element from each orbit of that order $p$ subgroup in the set. Having done that, the symmetry group of your torsor must be reduced to some smaller group, the stabilizer of the set of chosen elements, and you can choose in some algorithmic way one coset of that stabilizer, as desired.

So the condition is: $Z$ must contain some multiple of each prime.

Answer 2

A set of natural numbers (or any well-orderable set) can't be Dedekind-finite without being finite.

A good source for information about implications between axioms of the sort you're considering is a paper of John Truss, "Finite axioms of choice" [Ann. Math. Logic 6 (1973/74), 147–176.]

Answer 3

Since Gerry Myerson asked for a summary after my reading of Truss' paper (kindly suggested by Andreas Blass), I post this answer after having accepted Will Sawin's, which basically gave the solution, although I am not completely convinced that it is really complete (see below for more on this).

Although I did not notice it when I posted the original question, there are actually two closely related but slightly different versions that one may ask:

Question 1: For which $Z\subset\omega$ do we have ''$\forall n\in Z$ $AC(\{n\})$ $\Leftrightarrow$ $\forall n\in \omega$ $AC(\{n\})$''?

Question 2: For which $Z\subset\omega$ do we have $AC(Z)\Leftrightarrow AC(\omega)$?

They are different since there is (for instance) a model of $\forall n\in \omega$ $AC(\{n\})$ which does not satisfy $AC(\omega)$, see Theorem 7.11 in Jech's "The axiom of Choice". Notice that $AC(Z)\Rightarrow\forall n\in Z$ $AC(\{n\})$ and if $Z$ is finite, then of course both are equivalent.

Will Sawin gave the correct answer for Question 1:

Theorem 1: ''$\forall n\in Z$ $AC(\{n\})$ $\Leftrightarrow$ $\forall n\in \omega$ $AC(\{n\})$'' holds iff $Z$ contains a multiple of each prime number.

The reverse implication can be proved as follows: first notice that $\forall n\in Z$ $AC(\{n\})$ implies $AC(\{p\})$ for each prime $p$. Then, apply the following general result (Theorem 7.15 in Jech's book):

Theorem 2: If (S) holds for $n,m$, then $AC(\{1,\dots,m\})\Rightarrow AC(\{n\})$.

(S) is the property: There is no decomposition of $n$ in a sum of primes $n=p_1+\dots +p_s$ such that $p_i > m$ for all $i=1,\dots,s$. Thus, $AC(\{1,\dots,m\})$ implies $AC(\{1,\dots,p-1\})$, where $p$ is the smallest prime bigger than $m$. It follows that "$\forall p$ prime $AC(\{p\})$" implies "$\forall n\in\omega AC(\{n\})$". (The proof of Jech's result is actually very similar to what Will wrote.)

For the forward implication, we may use the following result, found in Truss' paper:

Theorem 3 (Mostowski-Gauntt-Truss): Let $Z\subset\omega$. Then $AC(Z)\Rightarrow AC(\{n\})$ iff $\mathsf{D}(n,Z)$ holds.

Let $\mathfrak{S}_n$ be the permutation group of $n$. $\mathsf{D}(n,Z)$ denotes the following property: for each subgroup $G\subset\mathfrak{S}_n$ without fixed point, there is a subgroup $H\subset G$ and proper subgroups $K_1,\dots, K_r$ of $H$ such that $\sum|H:K_i|\in Z$.

It is then easy to see that if no multiple of some prime $p$ is in $Z$, then $\mathsf{D}(p,Z)$ does not hold: let $G\subset\mathfrak{S}_n$ be the cyclic group of order $p$, the only proper subgroup of $G$ is the trivial group, hence $\sum|H:K_i|$ is a multiple of $p$.

Truss uses permutation models to prove Theorem 3, I did not have the time to really read it carefully (and he actually proves something more general, as his model of $\neg AC(\{n\})$ satisfies $AC$ for ordered sets of finite sets, for instance).

As for Question 2, Theorem 3 actually proves:

Theorem 4: If $AC(Z)$ implies $AC(\omega)$, then $Z$ contains a multiple of each prime.

But I don't know whether the converse holds as well. A priori, it might be the case that $AC(Z)$ and $AC(\{n\})$ for each $n\in\omega$ do hold, but $AC(\omega)$ does not. I hoped I'd grasp sufficiently quickly how permutation models work to be able to settle this, but I haven't for now, and since I won't have much time in the following weeks to investigate further, I decided to post the answer as it is. Do not hesitate to edit it if I missed something simple.