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

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.