# Proving every infinite set $S$ contains a denumerable subset

I have some trouble understanding this proof of every infinite set $S$ contains a denumerable subset contained in Charles Pugh's Real Analysis text.

Proof:

Since $S$ is infinite, it is nonempty and contains $s_1$. Then $S \backslash \{s_1\}$ is nonempty and there exists a $s_2 \in S \backslash \{s_1\}$

Since $S$ is infinite, $S \backslash \{s_1, s_2\}$ is nonempty and there exists a $s_3 \in S \backslash \{s_1,s_2\}$

Continuing this way gives a list $(s_n)$ of distinct elements of $S$. The set of these elements forms a denumerable subset of $S$

Three questions:

1. Continuing this way...wouldn't we end up with an infinite list $(s_n) = \{s_1, s_2, s_3, \ldots\}$ which is back to our set $S$?

2. Why don't we just stop at $\{s_1\}$? $\{s_1\}$ is in $S$, it is a singleton, it is countable, the end.

3. We already know that infinite sets are denumerable, meaning we can consturct a bijection $f(k) = s_k, \forall k \in \mathbb{N}$. Why is it even needed to show that $S$ contains a denumerable subset when itself is a denumerable subset of itself?

• Question 2: It depends on what you mean with ‘countable’. Question 3: ‘infinite’ does not mean ‘denumerable’. $\mathbf R$ is infinite and uncountable. – Bernard Jan 9 '16 at 20:14
• Question 1: What if $S=\mathbb{R}$ and $s_i=i$? Then $(s_n)=\{1,2,3,\ldots\}\neq \mathbb{R}=S$. – vadim123 Jan 9 '16 at 20:15
• If you mean Dedekind-infinite, there is a more intuitive proof: Suppose $S$ is Dedekind infinite. Then there exists an injective function $f:S\to S$ that is not surjective. Since $f$ is not surjective, for some $x_0 \in S$, we have $\forall a \in S: f(a)\neq x_0$. Then it can be shown that the set $\{x_0, f(x_0), f(f(x_0)),\cdots\}$ is order isomorphic to $\mathbb{N}$ and is therefore denumerable. – Dan Christensen Jan 9 '16 at 20:37
• I assume the question is really: show that every infinite $S$ contains a countably infinite subset. – BrianO Jan 10 '16 at 0:04

## 1 Answer

Great questions! Here are my answers:

1. You're right that we would end up with an infinite list -- a countably infinite list! But this doesn't have to equal the set $S$. For example, consider the infinite set $\Bbb Z$. Now, let $s_{1} = 2$, $s_{2} = 4$, $s_{3} = 6$, $\dots$. Then clearly $\{s_{n}\}$ is infinite, but does it equal our original set $\Bbb Z$? Of course not, since our new set is just the even natural numbers.

2. Some people consider the word "countable" to mean only "countably infinite". In that case, we would need to find a subset of $S$ that's infinite, and I think the author of your text considers "countable" as meaning "countably infinite".

3. Not all infinite sets are denumerable (i.e., countable). The real numbers $\Bbb R$ are not countable/denumerable. They are uncountable! So is the interval $[0,1]$. You should look up Cantor's diagonalization argument to see why these sets aren't denumerable (even though they are infinite).