0
$\begingroup$

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!

$\endgroup$
6
  • 1
    $\begingroup$ What do you mean by it being similar to an upper bound property? (Are you just saying the cardinality of a set cannot be higher than of a superset?) Your example is not clear, since the real interval $[0,10]$ is uncountable. $\endgroup$ – smcc Jul 27 '16 at 19:56
  • $\begingroup$ By "equivalence relation" you mean a bijection, or "one-to-one correspondence". Your set $A$ is countable because it is finite. Your set $B$ is countable because you specifically chose rationals. They don't really have anything to do with each other, though I guess you could say $A \subseteq B$, so $A$ is countable. $\endgroup$ – JasonM Jul 27 '16 at 19:57
  • $\begingroup$ I mean a one-to-one correspondence.. it would seem that my understanding is inaccurate. Could someone please provide a simple example? $\endgroup$ – user316270 Jul 27 '16 at 20:02
  • $\begingroup$ You have it simply backwards. If A is countable and $Z \subset A$ then Z is countable. You are trying to claim if $A \subset B$ then B is countable. i.e. all supersets of countable sets are countable. Which is obviously absurd and $\mathbb N \subset \mathbb R$ is an obvious counterexample. $\endgroup$ – fleablood Jul 27 '16 at 20:07
  • $\begingroup$ And yes, it has everything to do with 1-1 (or less) corespondence. $\endgroup$ – fleablood Jul 27 '16 at 20:08
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy