Every infinite set has an infinite countable subset?

Question

As the title says, that's all my question. Let me state it again:

Is it true that every infinite set has an infinite countable subset?

It seems so trivial, my thought goes like this: pick an arbitrary element and denote it as $x_1$; pick the next one and denote it $x_2$, and so on.

Is my proof correct? Since it seems so simple, I'm not sure of it.

---

To avoid any further confusion, the definitions used are:

Finite: In bijection with $\{1\ldots n\}$ for some $n$.
Infinite: Not finite.
Countably infinite: In bijection with $\Bbb N$.
Countable: Finite or countably infinite.

Answer 1

You are on the right track, however you cannot use the phrase "the next one". The idea is:Let $S$ be an infinte set. Pick an element $x_1\in S$, then since $\{x_1\}$ is finite, $S\setminus\{x_1\}\ne\emptyset$, so pick an element $x_2\in S\setminus\{x_1\}$ and so on.

Note the Axiom of Choice is involved here.

Answer 2

If your definition of "$X$ is infinite" is

There is an injective map $i:\mathbb{N} \rightarrow X$

Then the theorem is trivial: take the image $i(\mathbb{N})$. However this question is often posed with a different definition of infinite: a set $X$ is infinite if it is not finite, i.e.

There exists no bijection $\{1,\ldots,n\}\rightarrow X$ for any $n\in\mathbb{N}$.

Surprisingly, building a countably infinite subset of $X$ with this definition is not as trivial as it sounds! Essentially your idea is correct: choose some $x_0\in X$, since $X$ is not empty ($\emptyset=\{1,\ldots,0\}$, so $X$ cannot be equal to it). Then choose some $x_1\in X$ such that $x_1\neq x_0$ since if there were none, $X$ would be in bijection with $\{1\}$, repeat this for $x_2, x_3$, etc.

This doesn't quite work: for each sequence $x_0,\ldots, x_n$ it's easy to build $x_{n+1}$ by contradiction, but it's quite hard to build the whole sequence $(x_n)_{n\in\mathbb{N}}$ uniformly. It's a problem of "swapping quantifiers":

$$ \forall n,\exists x_0,\ldots,x_n\ i,j\leq n, i\neq j\Rightarrow x_i\neq x_j$$

is not equivalent to

$$ \exists (x_n)_{n\in\mathbb{N}},\forall n, i,j\leq n, i\neq j \Rightarrow x_i\neq x_j$$

without the axiom of choice. With the axiom of choice this becomes quite easy, e.g. by using Zorn's lemma (I'll let you work out the details).

It is a surprising fact that some form of the axiom of choice is needed to show this equivalence. This type of counter intuitive "uniform choice" problem happens a lot when dealing with infinite sets, which is why it is crucial to always explicitly state which definitions you are using, and be very careful with your proofs!

Answer 3

If you are using Dedekind's definition of infinity, then there must exist an injective, but not surjective function $f: S \to S$, where $S$ is your infinite set. Then there must also exist a countable $n\subset S$ that is order-isomorphic to $\mathbb {N}$ with the function $f$ serving as the successor function and any element outside the range of $f$ serving as the first element $0$ (or $1$).

For details and formal proofs, see my posting "Infinity: The Story So Far" at my math blog.