Does every infinite set have a denumerable subset? 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!
 A: 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$.
A: For an example, consider the set $\Bbb R$: it’s uncountable, and it has $\Bbb Q$, the rationals, and $\Bbb Z$, the integers, as countable subsets. If you remove either of these from $\Bbb R$, what’s left is still uncountable.
The claim that every infinite set has a countably infinite subset actually depends on the axiom of choice: without the axiom of choice it need not be true. I’ll sketch one of several possible proofs using the axiom of choice. First one proves that the axiom of choice implies that every set can be well-ordered. Now let $X$ be any infinite set. If $X$ is countably infinite, there’s nothing to prove, so suppose that $X$ is uncountable, and let $\preceq$ be a well-ordering of $X$. 
For each $x\in X$ let $\operatorname{pred}(x)=\{y\in X:y\prec x\}$, the set of predecessors of $x$. Let $I=\{x\in X:\operatorname{pred}(x)\text{ is infinite}\}$; then $I\ne\varnothing$, so let $x_0=\min I$; then $\operatorname{pred}(x_0)$ is a countably infinite subset of $X$.
