James Lobo

Posted on Saturday, 10 May, 2003 - 07:36 pm:

I was wondering if you could help me prove the following two propositions

1.Show that if A is a countable set and B is a finite set, then A union B is countable.

2.Let S be the set consisting of all finite subsets of the Natural numbers. Prove that S is countable.
Thanks

Steve Megson

Posted on Saturday, 10 May, 2003 - 09:01 pm:

To prove countability we need a bijection between the set and a countable set, usually the naturals.

For (1), we 'count' B first, then A. We map the first |B| naturals to the elements of B, then map |B|+1 to the first element of A, |B|+2 to the second and so on. Actually we must avoid counting elements of AÃ?????????? B twice, so we map the first |B-A| naturals to elements of B-A, then start mapping to elements of A.

A good approach to proving countability of a set of sets is to map each set to a set of prime numbers. We can then map each set of primes to a natural number and so get a bijection from our original set of sets to a subset of the naturals.

For (2), we can map a set of naturals to a set of primes by saying that if n is in the set then the nth prime is in the image set.

Steve

James Lobo

Posted on Saturday, 10 May, 2003 - 10:13 pm:

For question 1, once we have mapped the first |B-A| naturals to elements of B-A and start mapping to elements of A, what happens next?

For questions 2, how does the proof conclude once the nth prime is in the image set?

James

Steve Megson

Posted on Sunday, 11 May, 2003 - 12:44 am:

For (1), assume first that A and B are disjoint, to avoid worrying about counting elements twice. Assume also that A is the natural numbers. Label the elements of B as b₁ to b_n. Define a function f : N ® A ÈB by

f(i) =

ì
í
î

b_i

if i £ n

i - n

if i > n

This is a bijection, so A ÈB is countable.

If A is not N, we have a bijection from N to A since A is countable. We can extend this to a bijection from N \cupB to A ÈB by just mapping b_i to b_i. Now we've shown above that N ÈB is countable, so we have the result.

Now suppose that A and B are not disjoint. Then B-A is a finite set disjoint from A, and so we have proved above that A È(B-A) is countable. But A È(B-A) = A ÈB, so we have the result.

For (2), we define p_n to be the nth prime number, and define a function f: S ®N by

f(X) =
Õ
n Î X
p_n

(i.e. map X to the product of the primes corresponding to each element of X).

This is an injection since the prime factorisation of a number is unique, so only one set can map to agiven number. It isn't a surjection since, for example, no set maps to4. However, an injection is sufficient to prove that S is either finite or countably infinite. S is clearly not finite since { n } Î S for any n Î N. Steve

James Lobo

Posted on Sunday, 11 May, 2003 - 11:12 am:

Thanks Steve very much for your help.