Every infinite set has a countably infinite subset. Prove every infinite set has a countably infinite subset.
I was wondering if this approach is completely correct for this problem, my approach was to recursively define a function $f: \mathbb{N} \rightarrow$ countably infinite subset of an infinite set.
Attempt:
Suppose $A$ is infinite. We will construct a function $f: \mathbb{N} \rightarrow B$, where $B \subset A$, and $B$ is countably infinite. Since $A \neq \emptyset$, we can choose an element $a_{1} \in A$. Set $f(1)=a_1$. Since $A$ is infinite, choose an element $a_2 \in A-\{a_1\}$.Set $f(2)=a_2.$Assume for each $m&lt;n$, $f(m)$ has been chosen. Since $A$ is infinite there exists in element $a_{n} \in A-\{a_1,...a_{n-1}\}$. Set $f(n)=a_n$. Now that $f$ has been defined inductively, $B=\{a_1,a_2,...\} \subset A$ is countably infinite.
Nerding on Wikipedia I discovered the following facts. A set that admits an injective function from natural numbers is called &quot;Dedekind-infinite&quot;. An infinite set is one that is not in bijection with a finite set $\{0, \ldots, n\}$.
Suppose we assume the Zermelo-Frankel (ZF) axioms. Then:

We always have that a Dedekind infinite set is infinite, because there exist no injection from $\mathbb{N}$ to a finite set.

Assume the countable axiom of choice ($AC_{\omega}$). Then your proof can actually be formalized to choose all the values $f(n) $ &quot;together&quot;. This is a very subtle point, but you should be aware that generally without the axiom of choice very pathologicsl things can happen, see for example the Banach-Tarski paradox.


Logicians would write this point as $ZF +AC_{\omega} $ proves &quot;infinite $\Rightarrow$ Dedekind-infinite&quot;.

If we don't assume the countable axion of choice, surprisingly there exist infinite sets which are not Dedekind-infinite! As far as I understood, this proof is not constructive however, so it is kind of a monster.

In this case, logicians would say that the equivalence &quot;Dedekind-infinite $\Leftrightarrow$ Infinite &quot; is strictly weaker than the countable axiom of choice.
Nerding on Wikipedia I discovered the following facts. A set that admits an injective function from natural numbers is called &quot;Dedekind-infinite&quot;. An infinite set is one that is not in bijection with a finite set $\{0, \ldots, n\}$.
Suppose we assume the Zermelo-Frankel (ZF) axioms. Then:

We always have that a Dedekind infinite set is infinite, because there exist no injection from $\mathbb{N}$ to a finite set.

Assume the countable axiom of choice ($AC_{\omega}$). Then your proof can actually be formalized to choose all the values $f(n) $ &quot;together&quot;. This is a very subtle point, but you should be aware that generally without the axiom of choice very pathologicsl things can happen, see for example the Banach-Tarski paradox.


Logicians would write this point as $ZF +AC_{\omega} $ proves &quot;infinite $\Rightarrow$ Dedekind-infinite&quot;.

If we don't assume the countable axion of choice, surprisingly there exist infinite sets which are not Dedekind-infinite! As far as I understood, this proof is not constructive however, so it is kind of a monster.

In this case, logicians would say that the equivalence &quot;Dedekind-infinite $\Leftrightarrow$ Infinite &quot; is strictly weaker than the countable axiom of choice.