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?

Improve this question
$\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 ♦
    Commented Jul 5, 2018 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
    Commented Jul 5, 2018 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 ♦
    Commented Jul 5, 2018 at 8:05
  • 2
    $\begingroup$ Have you seen mathoverflow.net/questions/202586/… by the way? $\endgroup$
    – Asaf Karagila ♦
    Commented Jul 5, 2018 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
    Commented Jul 5, 2018 at 8:48

1 Answer 1

Reset to default
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$.

Improve this answer
$\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
    Commented Jul 5, 2018 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 ♦
    Commented Jul 5, 2018 at 9:00
  • $\begingroup$ Very nice, thanks for the answer. And what follows (or does not follow) from $AC_3$? $\endgroup$
    – Taras Banakh
    Commented Jul 5, 2018 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
    Commented Jul 5, 2018 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
    Commented Jul 5, 2018 at 14:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .