The following is an exercise in Just/Weese:

Show in ZF that the following are equivalent for every set $A$:

(a) There is no injection $f: \omega \to A$

(b) Every injection $f: A \to A$ is a surjection

Can you tell me if my proof is correct? Thank you!

(b) $\rightarrow $ (a): Assume $\lnot$ (a) and let $f: \omega \hookrightarrow A$ be an injection. Then $A$ is infinite hence (by corollary 13 on page 49) there exists a map $g: A \to A$ that is injective but not surjective.

(a) $\rightarrow $ (b): Assume $\lnot$ (b) and let $f: A \to A$ be injective but not surjective. Let $a_0 \in f(A)^c$. Then the following map is an injection: define $g: \omega \to A$ as $g(\varnothing) = a_0$ and $g(n) = f(g(n-1))$.

To see that $g$ is injective assume $g(n) = g(m)$ for $n > m$. Then $g(n-1) = g(m-1)$ and so on, until $g(n-m) = g(\varnothing) = a_0$. But the empty set is the only element mapping to $a_0$ hence $n-m = \varnothing$ and hence $n = m$.


enter image description here

  • 1
    $\begingroup$ What is "corollary 13 on page 49"? $\endgroup$
    – William
    Dec 3, 2012 at 13:21

1 Answer 1


This approach misses the point of Dedekind-finiteness being different than finiteness without choice. It is possible to have infinite Dedekind-finite sets.

The idea is that if there is an injection $f\colon\omega\to A$ then we can define the following function: $$g(a) = \begin{cases} f(n+1) & \exists n\in\omega. f(n)=a\\ a & \text{otherwise}\end{cases}$$ And it can be shown that $g$ is injective but certainly not surjective, $f(0)\notin\operatorname{rng}(g)$.

Besides the above point, which I think is amiss when a book aspires to talk about AC later on, the first proof seems fine; and the second part of the proof you gave is fine too.

Just to give it a final touch, you might want to prove that these two are equivalent to the additional characterization:

$A$ is Dedekind-finite if and only if whenever $B\subsetneqq A$, $|B|<|A|$.


You must log in to answer this question.

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