Every infinite set has an infinite countable subset?

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.

• Okay I have a problem with this "pick the next one and denote it" - pick the next one? Even with the countable quotients this is a weird claim, what's the next one after 1/2 say? – Alec Teal Jan 30 '15 at 15:46
• There are a couple of issue with this question. When you say countable subset, do you mean an infinite countable subset or a subset which is at most countable. If so, amWhy's answer will work. Also, when you say the "next one", that implies there is some order on the set. – Tim Raczkowski Jan 30 '15 at 15:46
• @user2345215 $A$ is finite if $A\sim J_n$ where $J_n$ is the set of the first $n$ positive integers. $A$ is infinite if $A$ is not finite. – Tien Kha Pham Jan 30 '15 at 15:54
• @Pål: No, this is not true. The statement is implied by the axiom of countable choice; but does not imply it in reverse. In particular it is possible that there are infinite sets without a countably infinite subset and every countable family of countable sets admits a choice function. – Asaf Karagila Jan 30 '15 at 16:04
• @AsafKaragila ah, thanks, let me leave the comment, for reasons of context. (In hindsight, I really did believe it was, so the entire statement was true! :) ) – Pål GD Jan 30 '15 at 16:11

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.

• Well, you could use "the next one" assuming there's a well ordering, which leads to an almost identical proof. – user2345215 Jan 30 '15 at 16:00
• Yes, that's true. I made my comment about "the next one" since the OP did not mention an order. :) – Tim Raczkowski Jan 30 '15 at 16:02
• This may be naive, but is the Axiom of choice really necessary? You can pick $n$ elements for any $n \in \mathbb{N}$, and so you can pick countably many elements. This can be done without the AC by proving there exists a "next" element via contradiction (assume there isn't, then it isn't infinite). – DanZimm Feb 1 '15 at 21:31
• why induction is not useful here? – Saravanan Dec 17 '19 at 4:39

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!

• @ I asked for the definition in the comments, you can find it there. – user2345215 Jan 30 '15 at 16:22
• with induction isn't possible proceed without axiom of choice? – Saravanan Dec 17 '19 at 4:38
• @Saravanan induction isn't able to work here because at each step you are deconstructing an existence statement in order to build the element of that step. – cody Dec 19 '19 at 22:06
• – cody Dec 19 '19 at 22:28

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.

• Had you read properly, you would have known that this is not the definition of infinite OP uses. Therefore, -1, as this is now effectively just a plug of your own blog. – Lord_Farin Feb 1 '15 at 20:23
• What in the OP suggests what definition used? – Dan Christensen Feb 1 '15 at 20:26
• My edit does, now, but it was based on the comment thread. – Lord_Farin Feb 1 '15 at 20:27
• The OP has just now specified his definition (8 minutes after my initial posting). – Dan Christensen Feb 1 '15 at 20:28
• Please do me a favour and click the link I provided. It's a comment from the OP, stating: "$A$ is infinite if $A$ is not finite." I simply extracted that information into the question to make it easier to find and to prevent misunderstandings like yours. – Lord_Farin Feb 1 '15 at 20:35