5
$\begingroup$

Set A is Dedekind infinite, i.e. there is a bijective function from A onto some proper subset B of A.

Please prove that A has a countably infinite proper subset.

1 Answers 1

9

If $f : A \to A$ is injective but not onto, fix some $a_0 \in A$ which is not in the range of $f$. Now recursively define $a_{n+1} = f(a_n)$ for $n \in \omega$. The injectivity of $f$ (and the initial choice of $a_0$) now implies that $a_n \neq a_m$ for $n \neq m$, and so $\{ a_n : n \in \omega \}$ is a countably infinite subset of $A$. (To ensure the properness of the subset just omit $a_0$ from the above set.)