Countable Sets & Infinity

Question

Recently I've been reading "Principles of Mathematical Analysis" by Rudin, and have just begun the section on basic topology. The first theorem it presents is the following:

Theorem Every infinite subset of a countable set A is countable.

It then provides a proof, and at the end, generalizes by saying that, roughly speaking, countable sets represent the "smallest" infinity: No uncountable set can be a subset of a countable set.

Now, from my current understanding, a set being countable or not depends on if there is an equivalence relation between the set in question, and the set of all positive integers.

I'm wondering if this is similiar to an upper bound property..

Ex. Set A is defined on the interval [0,10] consisting of all natural numbers within that interval. It is finite, and countable. Now, take the [0,10] and define set B to be all rational numbers within the interval. It is infinite, but still countable, since set A is countable.

Is this what the theorem is stating, in essence? Also, could someone please give an example of where this is not true?

Thanks!

Answer 1

"Set A is defined on the interval [0,10] consisting of all natural numbers within that interval. It is finite, and countable. Now, take the [0,10] and define set B to be all rational numbers within the interval. It is infinite, but still countable, since set A is countable."

"Is this what the theorem is stating, in essence? Also, could someone please give an example of where this is not true?"

No not at all.

Counter example: set C = all real numbers in the interval. This is not countable even though A is finite.

However the reverse direction is true. $A \subset B$ so $A$ is countable. Other example $C = \{1/n\}$ or $D = \{n^2/m^3\}$ or any other where $C, D \subset B$ must be countable because $B$ is.

So for $E \subset A$. There are 2048 possible such subsets. All finite.

Answer 2

A set is countable if there is an injective function from the set into the natural numbers. This is more specific than "a relation", or even "a function".

In your example, you first consider $A=[0,10]\cap\Bbb N=\{0,1,2,3,4,5,6,7,8,9,10\}$ which is certainly a finite set, and $B=[0,10]\cap\Bbb Q$ is certainly an infinite subset of $\Bbb Q$. But $B$ is not a subset of $A$.

Moreover, since $A$ is finite, every subset of $A$ is in fact finite. What you want to appeal to is to the fact that $B\subseteq\Bbb Q$, and that $\Bbb Q$ is countable. That is the reason that $B$ is countable as well.