Countability of SetsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/