Proving every infinite set $S$ contains a denumerable subset

real-analysis proof-writing proof-explanation elementary-set-theory proof-verification

Solution 1:

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).

Related

How to prove $\int_0^\infty e^{-x^2}cos(2bx) dx = \frac{\sqrt{\pi}}{2} e^{-b^2}$
Substitution for $\int \frac {dx} {ax^2 + bx + c}$
Choice function for collection of arbitrary finite sets. AC required?
Picturing the how the covariant derivative acts on vector fields
If $x_n \to 0$, show that $\sqrt{x_n} \to 0$
$p:X\to Y$ covering space if $q\circ p:X\to Z$ and $q:Y\to Z$ covering spaces and $Z$ locally path-connected.
Prove that $\sum\limits_{n=0}^{\infty}{(e^{b_n}-1)}$ converges, given that $\sum\limits_{n=0}^{\infty}{b_n}$ converges absolutely.
Numbers till 400 divisible by 2, 3, 5, 7
Prove that function is homeomorphism.
ASP.NET MVC shared web hosting recommendations? (Alternatively, good Windows VPS providers?) [closed]
SSDs for archival purposes?
Remote Desktop performance issues in Windows 2008