Countability of Sets

Date: 10/20/2004 at 10:55:32
From: Zaman002
Subject: Countability

The set Q of all rational numbers and the set N2 of all ordered pairs
of natural numbers are countable.  Show that the following sets are
countable:

  (a) Q^2;
  (b) The set of all subsets of N of size 2;
  (c) The set of all subsets of N of size n, for some fixed (but 
      arbitrary) n E N;
  (d) The set of all finite subsets of N.

I'm completely stuck!  I'm not sure I fully understand the idea of
countability.

Date: 10/21/2004 at 11:41:56
From: Doctor Vogler
Subject: Re: Countability

Hi Zaman,

Thanks for writing to Dr. Math.  Our archives have several entries
about countability, which you can find by searching our archives for
"countable" or something similar.  For example, there is

  Infinities
    http://mathforum.org/library/drmath/view/59138.html 

  Aleph Null
    http://mathforum.org/library/drmath/view/52415.html 

  Countability
    http://mathforum.org/library/drmath/view/52830.html 

  Sizes of Infinities
    http://mathforum.org/library/drmath/view/53352.html 

  Orders of Infinity
    http://mathforum.org/library/drmath/view/51863.html 

You can find some interesting ideas there, such as how to show that Z
and Q are countable, but R is not.

That said, in my personal opinion, one of the easiest ways to show
that a set is countable is to write it as a countable union of finite
sets.  (Some prefer to write it as a countable union of countable
sets, but the first is easier to understand.)  So let's suppose that
a countable union of finite sets is countable for now, and I'll show
you how to use that to prove your sets are countable.

The idea is to create some kind of "height" N so that every element
has a finite height and there are only finitely many elements whose
height is smaller than or equal to N.  For example, for rational
numbers, we might use

  height(a/b) = max(|a|, |b|).

For a pair of rational numbers--that is, an element of Q^2--we might use

  height(a/b, c/d) = max(|a|, |b|, |c|, |d|).

For a subset of N of size n, we might use

  height(k_1, k_2, ... k_n) = max(k_1, k_2, ... k_n).

For a finite subset of N, we cannot use the same thing, but we can use

  height(k_1, k_2, ... k_n) = max(n, k_1, k_2, ... k_n).

I will leave it up to you to show that, in each case, this gives a
(finite) natural number, and (more importantly) there are only 
finitely many elements of the set in question whose height is less
than or equal to N for any N.  Can you explain why we can't change the
"max" in the above heights to "min"?  Can you explain why we have to
use the absolute values when we don't already know the numbers are
positive?  That is, why can't we use

  height(a/b) = max(1, a, b) ?


Now I'll get on to proving that a countable union of finite sets is
countable.  The idea is that we have finite sets

  s_1, s_2, s_3, s_4, ...

and you should think of s_N as the elements with height equal to N. 
For simplicity, let's assume that the s_n are disjoint (have no
elements in common, which they will in our height methods) although
the theorem is still true (and the proof is not much different) even
if they have elements in common.  Let's write

  k_n

for the number of elements in the set s_n.  Now we need to count them.
So let's start at the beginning.  We count all of the elements in s_1
from 1 up to k_1.  Then we count all of the elements in s_2 from 1+k_1
up to

  k_2 + k_1.

And similarly all of the elements in s_n from

  1 + k_1 + k_2 + k_3 + ... + k_(n-1)

up to

  k_n + k_1 + k_2 + k_3 + ... + k_(n-1).

This gives us a bijection or a correspondence between the natural
numbers and the union of all of our sets s_n.

In order to prove this using sets that might not be disjoint, all you
do is skip all of the elements in s_n that were already counted
before.  This is equivalent to simply replacing s_n by s_n minus all
those elements in the union of s_1 up to s_(n-1) to make the sets
disjoint.

You can also use this to prove that a countable union of countable
sets is countable.

Suppose that s_n is countable for every natural number n.  Let's call
the union S (the set of all elements that are in any of the sets s_n).
We only need to define a height on S.  Well, since each s_n is
countable, its elements are

  s_n = {a_1n, a_2n, a_3n, a_4n, ...}

where the subscript kn means the two numbers (k, n) and not the
product of k times n.  Now pick an element a of S.  That means it must
be in some set s_n.  It might be in more than one of those sets, so
let n be the smallest index so that a is in s_n, and then we have

  a = a_kn

for some k, and then we define

  height(a) = height(a_kn) = max(k, n).


You can use this to prove that some of your sets are countable too. 
For example, you can write Q as the union of

  Z/n = {-3/n, -2/n, -1/n, 0, 1/n, 2/n, 3/n, 4/n, ...}

for all natural numbers n.  Since Z is countable, this is a countable
union of countable sets, so Q is countable.  Similarly, you can write
Q^2 as the union of

  Q x q = {(r, q): r is a rational number}

for all rational numbers q.  Since Q is countable, this is a countable
union of countable sets, so Q^2 is countable.  Exactly the same proof
will show that the Cartesian product of two countable sets R x S is
countable.

And you can write your set (ii) as the union of

  {{1, n}, {2, n}, {3, n}, ... {n-1, n}, {n, n+1}, ... }

for all natural numbers n.  (Note that we have to skip {n} because
this does not have two elements.)  Since N is countable, this is a
countable union of countable sets, and therefore also countable.

Does that help you understand how to deal with these countable sets
and showing that a set is countable?

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/