10
$\begingroup$

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?

$\endgroup$
9
  • $\begingroup$ It's not a partial order, since $\sf AC(2)\iff AC(4)$. (You are right to say preorder, though.) $\endgroup$ – Asaf Karagila Jul 5 '18 at 8:03
  • $\begingroup$ @AsafKaragila Oh, sorry, Asaf! I had in mind preorder (and wrote so in the body of the question). Now I will fix the title. $\endgroup$ – Taras Banakh Jul 5 '18 at 8:05
  • $\begingroup$ I had a conversation with Lorenz Halbeisen about this once. I don't remember the conclusion, though. There's some information in Jech "The Axiom of Choice" (Ch. 7), but I don't remember if there were any significant developments after that. $\endgroup$ – Asaf Karagila Jul 5 '18 at 8:05
  • 2
    $\begingroup$ Have you seen mathoverflow.net/questions/202586/… by the way? $\endgroup$ – Asaf Karagila Jul 5 '18 at 8:07
  • 2
    $\begingroup$ “Theorem 3” in Mathieu Baillif’s answer to his own question gives a complete description of the preorder, doesn’t it? $\endgroup$ – Emil Jeřábek Jul 5 '18 at 8:48
12
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ Every number $\ge8$ is the sum of a suitable amount of 3s and 5s (Frobenius coin problem), so you don’t need Goldbach’s conjecture. $\endgroup$ – Emil Jeřábek Jul 5 '18 at 8:59
  • $\begingroup$ Oh, that's nice. I do like the Goldbach conjecture connection though. But I'll edit this in. Thanks! $\endgroup$ – Asaf Karagila Jul 5 '18 at 9:00
  • $\begingroup$ Very nice, thanks for the answer. And what follows (or does not follow) from $AC_3$? $\endgroup$ – Taras Banakh Jul 5 '18 at 9:21
  • 3
    $\begingroup$ @TarasBanakh The criterion from Mathieu Baillif’s post shows that $\mathit{AC}_3$ does not imply anything besides itself and $\mathit{AC}_1$. $\endgroup$ – Emil Jeřábek Jul 5 '18 at 9:48
  • 1
    $\begingroup$ @Gro-Tsen As I already wrote above, Theorem 3, in the special case $Z=\{m\}$, gives a completely general finitary combinatorial criterion equivalent to $ZF\vdash C_m\to C_n$. The general statement is a bit unwieldy, but it’s quite easy to apply it to $m=3$. (Since 3 is not a nontrivial sum of numbers $>1$, and any group whose size is divisible by 3 contains an element of order 3, the criterion boils down to: any fixpoint-free subgroup $G\le S_n$ has size divisible by 3. So, it is enough to find a cyclic counterexample for $n\ne1,3$, i.e., write $n$ as a sum of numbers $>1$ not divisible by 3.) $\endgroup$ – Emil Jeřábek Jul 5 '18 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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