Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $n\geq 2$ be a natural number and consider the following:

$AC(n)$: For each family $\{X_i\}_{i \in I}$ of $n$-element sets the product $\prod_{i\in I}X_i$ is non-empty.

Is it known that for which values of $m$ and $n$, $AC(m)$ and $AC(n)$ are equivalent !?

share|improve this question
3  
The classic reference is A. Mostowski,Axiom of choice for finite sets, Fund. Math. 33 (1945), 137-168. The matter is also discussed on pp. 101-108 of W. Sierpiński, Cardinal and Ordinal Numbers, second edition revised, Warszawa 1965. –  bof Feb 9 at 19:45
add comment

4 Answers 4

up vote 15 down vote accepted

There is about half a chapter devoted to this in Jech The Axiom of Choice, the key point is Theorem 7.15 which gives a condition for $\mathsf{AC}(n)\implies\mathsf{AC}(m)$. You may want to look around there (p.111 for the theorem).

share|improve this answer
2  
A reference of course is great, but would it be possible for you to mention what is the result? –  Joel David Hamkins Feb 9 at 12:53
    
@JoelDavidHamkins See the my answer (my comment in fact). –  Rita J Feb 9 at 13:56
1  
Joel, I have an excellent excuse why I didn't post it in my answer. I was going to when I'd get home but it's moot now... –  Asaf Karagila Feb 9 at 14:30
add comment

Thanks to @AsafKaragila, I found the Jech's book very useful. Here is the result in page 111 concerning to my question: (Note that in what follows $C_n$ is what I have called $AC(n)$.) I don't know how to put this as a comment. So I am writing this as a new answer.

(S) $\qquad$ There is no decomposition of $n$ in a sum of primes,
$$n = p_1 + \ldots + p_s,$$ $\qquad\quad\;\:$ such that $p_i > m$ for all $i = 1, \dots, s$.

(In particular, if $n > m$, then $n$ is not a prime.)

Theorem 7.15. If $m, n$ satisfy condition (S) and if $C_k$ holds for every $k \leq m$, then $C_n$ holds.

Theorem 7.16. If $m, n$ do not satisfy condition (S), then there is a model of set theory in which $C_k$ holds for every $k \leq m$ but $C_n$ fails.

(Images: Theorem 7.15, Theorem 7.16)

share|improve this answer
add comment

Since the question asked in particular about equivalence between $AC(m)$ and $AC(n)$ with $m,n\geq2$, it seems worth stating explicitly that the only non-trivial equivalence of this simple form is between $AC(2)$ and $AC(4)$. It is easy to see (though I overlooked it in the first version of this answer) that $AC(m)$ implies $AC(n)$ whenever $n$ divides $m$. The non-trivial direction, from $AC(2)$ to $AC(4)$, is a beautiful theorem of Tarski. (Thanks to bof for pointing out the error in the original version of this answer.)

It should perhaps also be mentioned that, although Mostowski proved a lot of results about implications of the form "$[AC(m_1)\land\cdots\land AC(m_k)]\implies AC(n)$, the complete characterization of which of these implications are provable in ZF was done by Gauntt. I don't think Gauntt ever published more than abstracts of this work, but there's a detailed exposition in a paper of John Truss, "Finite axioms of choice" [Annals of mathematical logic 6 (1973/4) 147-176].

share|improve this answer
    
@bof You're right. I'll edit the answer to correct this point. thanks. –  Andreas Blass Feb 10 at 14:22
add comment

Isn't the point that this is really all about finite groups? Given a group $G$, the $G$-axiom of choice says that for any collection of sets with a simply transitive action of $G$, we may choose from each set a coset of a proper subgroup.

Then $AC(n)$ is equivalent to the axiom of choice for all groups $G$ with a fixed-point-free action on $n$ objects.

The axiom of choice for a subgroup or a quotient group of a group implies the axiom of choice for that group.

I believe that all implications between different finite axioms of choice follow from these facts.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.