# Equivalent characterisations of Dedekind-finite proof

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$.

Edit

• What is "corollary 13 on page 49"? Dec 3, 2012 at 13:21

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)$.
$A$ is Dedekind-finite if and only if whenever $B\subsetneqq A$, $|B|<|A|$.