I was reading Rudin's "Principles of Mathematical Analysis, 3rd Ed." I don't quite follow the author's remark after stating and proving Theorem 2.8. Specifically, on page 26, we have
2.8 Theorem $\quad$ Every infinite subset of a countable set A is countable.
$\quad$ Proof $\quad$ Suppose $E \subset A$, and $E$ is infinite. Arrange the elements $x$ of $A$ in a seqeuence $\{x_n\}$ of distinct elements. Construct a sequence $\{n_k\}$ as follows: Let $n_1$ be the smallest positive integer such that $x_{n_1}\in E$. Having chosen $n_1, …, n_{k-1}$ $(k=1,2,3,…)$, let $n_k$ be the smallest integer greater than $n_{k-1}$ such that $x_{n_k}\in E$. Putting $f(k)= x_{n_k}\:(k=1,2,3,…)$, we obtain a 1-1 correspondence between $E$ ane $J$ (the set of positive integers).
(And then comes the following remark that I don't see how it is implied by the theorem above.)
The theorem shows that, roughly speaking, countable sets represent the "smallest" infinity: No uncountable set can be a subset of a countable set.
I can understand the theorem and its proof, but I don't quite see the connection between the theorem and the remark. I'd appreciate if someone can point it out for me.
Best Answer
There are two kinds of 'infinite': (1) countably infinite, and (2) uncountably infinite.
These are the only two kinds of infinite sets, since the second is simply "all infinite sets which aren't countable".
We have the implication $$\text{$A$ an infinite subset of countable set} \implies \text{$A$ is countable}$$ which is equivalent to $$\text{$A$ an infinite subset of countable set} \implies \text{$A$ not uncountable}$$ and the contrapositive of this is $$\text{$A$ uncountable} \implies \text{$A$ not infinite subset of countable set}$$ or simply $$\text{$A$ uncountable} \implies \text{$A$ not subset of countable set}$$