3
$\begingroup$

For sets $x, y$ we write $x\leq y$, if there is an injection $\iota: x \to y$, and we write $x \leq^* y$ if either $x = \emptyset$ or there is a surjection $s: y \to x$. In ${\sf (ZF)}$ we have that $x \leq y$ implies $y \leq^* y$.

Consider the following statements:

Partition principle (PP): For all sets $x, y$ we have that $x \leq^* y$ implies $x\leq y$.

Dual Cantor-Bernstein (CB)*: For all sets $x,y$, if $x\leq^* y$ and $y \leq^* x$, then there is a bijection $\varphi: x\to y$.

Via the "normal" Cantor-Bernstein theorem, which a theorem of ${\sf (ZF)}$, we can show that (PP) imples (CB)* in ${\sf (ZF)}$.

It seems to be open whether (CB)* implies the Axiom of Dependent Choice (DC). Since (PP) is stronger than (CB)*, this begs the question:

Does (PP) imply (DC) in ${\sf (ZF)}$?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ It’s not open, WPP (and thus CB*) implies DC, see Higasikawa’s Partition Principles paper. $\endgroup$
    – Elliot Glazer
    Commented Apr 13, 2022 at 18:55
  • 1
    $\begingroup$ While we're making remarks, begthequestion.info $\endgroup$
    – Asaf Karagila ♦
    Commented Apr 13, 2022 at 20:57
  • $\begingroup$ Apologies for a) misusing the "beg" term and b) missing Higasikawa's paper $\endgroup$
    – Dominic van der Zypen
    Commented Apr 14, 2022 at 9:37
  • $\begingroup$ @DominicvanderZypen I assume you meant the implication $x \leq y$ implies $x \leq^* y$. $\endgroup$
    – Juan Atacama
    Commented Sep 10 at 12:20
  • $\begingroup$ In ZF, we have that $x\leq y$ implies $x \leq^* y$: if $x\neq \emptyset$ and $x\leq y$, fix $a_0\in x$. Let $f:x\to y$ be an injection. Consider the set $\{(b, a): a\in x, b\in y, f(a) = y\}\cup \{(z,a_0): z\in y \setminus \text{im}(f)\}$. This provides a surjection $g:y\to x$, so $x\leq^* y$. - What is open, is whether the implication $x\leq^*y \implies x\leq y$ is a theorem of ZF. $\endgroup$
    – Dominic van der Zypen
    Commented Sep 10 at 18:04

1 Answer 1

Reset to default
8
$\begingroup$

Yes. This is a combination of facts.

  1. $\sf PP$ implies that if a set $X$ can be mapped onto an ordinal $\alpha$, then $\alpha$ injects into $X$. In other words, it implies that $\aleph^*(X)=\aleph(X)$ for any set $X$.

  2. $\sf AC_{WO}$, that is the axiom of choice from families of sets indexed by an ordinal, is equivalent to the statement "For every $X$, $\aleph^*(X)=\aleph(X)$".

  3. $\sf AC_{WO}$ implies $\sf DC$. This is due to the fact that if $T$ is a tree of height $\omega$ without cofinal branches, we can consider the various well-orderable subtrees of $T$, define a rank function on those and use that to define a rank function on $T$. Then, using $\sf AC_{WO}$ we can show that it is impossible that $T$ itself is not truly well-founded, which would mean that it has a maximal element.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

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