5
$\begingroup$

A set $X$ is Dedekind-infinite if there is an injective map $f: X\to X$ that is not surjective.

A set $X$ is dually Dedekind-infinite if there is a surjective map $f: X\to X$ that is not injective.

In ${\sf (ZF)}$, it is easy to see that any Dedekind-infinite set is dually Dedekind-infinite: Let $f:X\to X$ be a non-surjective injection. Pick $x_0\in X$ and let $g: X\to X$ be defined by $$\big\{\big(f(y), y\big): y\in f(X)\big\}\,\cup\,\big\{(z, x_0):z\in X\setminus f(X)\big\}.$$ Then $g$ is a non-injective surjection.

Consider the statement

(DD) Every dually Dedekind-infinite set is Dedekind-infinite.

It is not hard to see that (AC) implies (DD). Consider the partition principle:

(PP) If $X,Y$ are sets and there is a surjection $f:X\to Y$, then there is an injection $g:Y\to X$.

Question. In ${\sf (ZF)}$, are there any implications between (DD) and (PP)?

Note. It would also be interesting to see whether there is any implication between (DD) and the Dual Cantor Bernstein statement (CB)*, which is implied by (PP) in ${\sf (ZF)}$:

(CB)* If $X,Y$ are sets and $f:X\to Y$ and $g:Y\to X$ are surjections, then there is a bijection $\varphi:X\to Y$.

$\endgroup$

1 Answer 1

10
$\begingroup$

Tarski proved that if there is an infinite Dedekind-finite set, then there is one which is dually Dedekind-infinite as well.

Therefore, postulating that all dually Dedekind-infinite sets are Dedekind-infinite implies that that every Dedekind-finite set is finite.

This is a consequence of $\sf DC$, of course, which is a consequence of $\sf PP$.

$\endgroup$
3
  • 1
    $\begingroup$ Oh, that's a nice theorem. Do you have a reference? (Or a proof sketch?) $\endgroup$ Commented May 27 at 12:59
  • $\begingroup$ Sure. Look at the set of injective finite sequences, then look at the map which trims the last element from the sequence. It's in a few answers around the site, I'm certain, and you can play with the proof even more to get other crazy ideas. $\endgroup$
    – Asaf Karagila
    Commented May 27 at 15:24
  • $\begingroup$ Oh, that's right, I have seen that before. Thanks for the reminder! $\endgroup$ Commented May 27 at 16:05

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