This question is answered with a mere "Yes" in the textbook (Theory of Sets by Joseph Breuer), but I'm not sure where the confidence comes from. For instance, if we have a non-denumerable set, then it seems to me that no matter what pattern we choose, we'll end up with a subset with the same cardinal number. Or won't we?
I guess what makes matters worse is that the question right after proving the theorem that "If a denumrable set is subtracted from a non-denumrable set, the resulting set is no-denumerable." I understood the proof, and can even reproduce it perfectly, but I have no idea I understand what it means. An example would make things clearer, I guess.
I'm thoroughly confused; please help!
Best Answer
Let $S$ be a non-denumerable set (uncountable is a more common term in English texts IMVHO). The set $S$ is not empty, so you can pick an element $s_1\in S$. The set $S\setminus\{s_1\}$ is non-empty (for otherwise the set $S$ had turned out to be finite and thus also countable), so you can pick $s_2\in S\setminus\{s_1\}$. You can continue this by recursively selecting an element $s_{k+1}\in S\setminus\{s_1,s_2,\ldots,s_k\}$ for all natural numbers $k$.
By construction the chosen elements $s_i,i\in\mathbf{N},$ are all distinct, so they form a countably infinite subset of $S$.