11
$\begingroup$

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 !?

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – bof
    Feb 9, 2014 at 19:45

4 Answers 4

16
$\begingroup$

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).

$\endgroup$
3
  • 2
    $\begingroup$ A reference of course is great, but would it be possible for you to mention what is the result? $\endgroup$ Feb 9, 2014 at 12:53
  • $\begingroup$ @JoelDavidHamkins See the my answer (my comment in fact). $\endgroup$
    – Rita J
    Feb 9, 2014 at 13:56
  • 1
    $\begingroup$ 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... $\endgroup$
    – Asaf Karagila
    Feb 9, 2014 at 14:30
10
$\begingroup$

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)

$\endgroup$
8
$\begingroup$

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].

$\endgroup$
2
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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