I am interested in proving the following statement:
A set is Dedekind-infinite if and only if it has a countably infinite subset.
Here is my attempt:
$(\Leftarrow)$ Suppose that $A$ has a countably infinite subset $E$. Arrange the terms of $E$ in a sequence $x_0,x_1,x_2,\dots$ of distinct elements. Now let $f:A\to A\setminus\{x_0\}$ be defined as follows:
$$
f(x)=
\begin{cases}
x_{n+1} &\text{if $x=x_n$ for some $n\in\mathbb N$} \\
x &\text{otherwise}
\end{cases}
$$
Then, $f$ is a bijection from $A$ to a proper subset of $A$, namely $A\setminus\{x_0\}$.
However, I am unsure how to prove the forward implication. Does it require a form of the axiom of choice?
Best Answer
Suppose $A$ is in bijection with a proper subset $B$, that is, there exists a bijection $f : A \to B$. Suppose $x_0 \in A-B$. Then we can define a sequence of distinct terms by $x_{n+1} = f(x_n)$, which is countably infinite as $f$ is injective.