Take the 2-minute tour ×

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

Please proof that A has a countably infinite proper subset.

share|improve this question
Do you mean a countably infinite proper subset? –  Chris Eagle Sep 16 '12 at 13:57
I changed that. Thank you –  TheoYou Sep 16 '12 at 14:19
add comment

1 Answer

up vote 4 down vote accepted

Hint: If $f : A \to A$ is injective but not onto, then there is an $a \in A$ such that $f(x) \neq a$ for all $x \in A$. What happens when you iteratively apply the function $f$ to this element $a$?

share|improve this answer
I don't quite get it... –  TheoYou Sep 16 '12 at 14:24
@Theo: Let $x_0 = a$ and let $x_{i+1} = f(x_i)$ for all $i \in \mathbb N$. Is it possible that $x_i = x_j$ but $i \ne j$ for any $i,j \in \mathbb N$? –  Ilmari Karonen Sep 16 '12 at 14:29
@Theo: Exactly what Ilmari said... though I was trying to be less explicit as that pretty much gives the game away. –  Arthur Fischer Sep 16 '12 at 14:37
add comment

Your Answer


