13
$\begingroup$

Let us call a map $f: X \to Y$ between non-empty sets a "weak injection" if $f^{-1}(\{y\})\subseteq X$ is finite for every $y \in Y$.

Recall that the (Schroeder-)Cantor-Bernstein-Theorem (sometimes abbreviated by (CB)) states that if there are injections between two sets $X, Y$, then there is also a bijection between $X$ and $Y$. (CB) is a theorem of ${\sf (ZF)}$.

Consider the following statement:

(wiCB) If $X, Y$ are infinite sets such that there are weak injections between $X$ and $Y$, then there is a bijection between $X$ and $Y$.

Obviously, (wiCB) implies (CB). Can (wiCB) also be proved in ${\sf (ZF)}$?

$\endgroup$
1
  • 4
    $\begingroup$ I have also heard "finite-to-one" and, more cutely, "finjective" used for weakly injective. $\endgroup$ Commented Feb 5 at 14:42

1 Answer 1

18
$\begingroup$

No, it is not provable in $\mathsf{ZF}$.

It is consistent with $\mathsf{ZF}$ that there is a sequence of disjoint two-element sets whose union is not countable, i.e. $\vert A_i\vert=2$ but there is no bijection between $A:=\bigcup_{i\in\mathbb{N}}A_i$ and $\mathbb{N}$.

WLOG, $A\cap\mathbb{N}=\emptyset$. Now let $B_i=A_i\sqcup\{i\}$ and let $B=\bigcup_{i\in\mathbb{N}}B_i$. We have obvious weak injections $B\rightarrow\mathbb{N}$ and $\mathbb{N}\rightarrow B$, the former sending $x\in B_i$ to $i$ and the latter sending $i$ to $i$, but $B$ is not countable.

$\endgroup$
7
  • 1
    $\begingroup$ And more generally (wiCB) implies that the union of $\aleph_\alpha$ finite sets has cardinality at most $\aleph_\alpha$. $\endgroup$
    – bof
    Commented Feb 4 at 22:21
  • 1
    $\begingroup$ Hmm, this raises an interesting separate question of if wiCB is equivalent to Choice. My guess is that it is weaker. $\endgroup$
    – JoshuaZ
    Commented Feb 5 at 15:33
  • 2
    $\begingroup$ @JoshuaZ Probably decently weaker. E.g. if every set can be linearly ordered and $|X\times\omega|=|X|$ for all infinite $X$ then we get wiCB. That sounds doable in the "$\omega_1$ Cohen model", but I'm not certain. $\endgroup$ Commented Feb 5 at 17:24
  • $\begingroup$ @CalliopeRyan-Smith: It's not clear to me which is the "$\omega_1$ Cohen model". Note that $|X\times\omega|=|X|$ if and only if $|X|=|X|+|X|$, so we really just need that every set is linearly orderable along with that. Luckily, Sageev's model (which is really the only model we really know about where $|X|+|X|=|X|$ holds for every infinite set $X$ and choice fails) satisfies that every set can be linearly ordered. (This is Lemma 9.30 in his massive paper.) $\endgroup$
    – Asaf Karagila
    Commented Feb 8 at 21:11
  • $\begingroup$ @AsafKaragila $\operatorname{Add}(\omega_1,\omega_1)$, countable-support permutations of $\omega_1$, etc. My naive hope is (was?) that $\mathsf{SVC}(A)$ for a linearly orderable $A$ with $\aleph(A)>\aleph_0$ would be enough. $\endgroup$ Commented Feb 9 at 13:36

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.