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)}$?

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

1 Answer 1

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

Improve this answer
$\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$
    – Calliope Ryan-Smith
    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$
    – Calliope Ryan-Smith
    Commented Feb 9 at 13:36

You must log in to answer this question.

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