7
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ 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? $\endgroup$ – Alec Teal Jan 30 '15 at 15:46
  • $\begingroup$ 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. $\endgroup$ – Tim Raczkowski Jan 30 '15 at 15:46
  • 1
    $\begingroup$ @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. $\endgroup$ – Tien Kha Pham Jan 30 '15 at 15:54
  • 1
    $\begingroup$ @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. $\endgroup$ – Asaf Karagila♦ Jan 30 '15 at 16:04
  • 1
    $\begingroup$ @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! :) ) $\endgroup$ – Pål GD Jan 30 '15 at 16:11
5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Well, you could use "the next one" assuming there's a well ordering, which leads to an almost identical proof. $\endgroup$ – user2345215 Jan 30 '15 at 16:00
  • 1
    $\begingroup$ Yes, that's true. I made my comment about "the next one" since the OP did not mention an order. :) $\endgroup$ – Tim Raczkowski Jan 30 '15 at 16:02
  • 1
    $\begingroup$ 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). $\endgroup$ – DanZimm Feb 1 '15 at 21:31
  • $\begingroup$ why induction is not useful here? $\endgroup$ – Saravanan Dec 17 '19 at 4:39
4
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ @ I asked for the definition in the comments, you can find it there. $\endgroup$ – user2345215 Jan 30 '15 at 16:22
  • $\begingroup$ with induction isn't possible proceed without axiom of choice? $\endgroup$ – Saravanan Dec 17 '19 at 4:38
  • $\begingroup$ @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. $\endgroup$ – cody Dec 19 '19 at 22:06
  • $\begingroup$ See also: en.wikipedia.org/wiki/Axiom_of_countable_choice $\endgroup$ – cody Dec 19 '19 at 22:28
-2
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ 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. $\endgroup$ – Lord_Farin Feb 1 '15 at 20:23
  • $\begingroup$ What in the OP suggests what definition used? $\endgroup$ – Dan Christensen Feb 1 '15 at 20:26
  • $\begingroup$ My edit does, now, but it was based on the comment thread. $\endgroup$ – Lord_Farin Feb 1 '15 at 20:27
  • $\begingroup$ The OP has just now specified his definition (8 minutes after my initial posting). $\endgroup$ – Dan Christensen Feb 1 '15 at 20:28
  • 1
    $\begingroup$ 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. $\endgroup$ – Lord_Farin Feb 1 '15 at 20:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.