Let A and B be subsets of a set U and suppose that AB ie A a

Let A and B be subsets of a set U, and suppose that AB= (i.e. A and B are disjoint.) Prove that if both A and B are countable, then AB is countable.

Remember: a countable set can be finite or infinite - treat these cases separately.

Solution

We have three cases: A and B are finite, just one of them is finite, both of them are not finite

1. let n be the cardinality of A & m be the cardinility of B.

Then we have a bijection   :

f:{0,…,n1}A

and a bijection :

g:{0,…,m1}B.

Now build a function :

h:{0,…,n+m1}AB, i.e. h(x)=f(x) if xn1, h(x)=g(xn) otherwise. It is easy to check it is a bijection.

2. Now suppose A is finite and B not.

Then we have bijections :

f:{0,…,n1}A and g:NA.

Now we can patch this way : h:NAB with h(x)=f(x) if xn1 and h(x)=g(xn) otherwise. Then you check in the same way as above.

3. Now both of the sets are not finite.

Now we have f:NA and g:NB. Define h:NAB as follows: if x is even write x=2y and define h(2y)=f(y), if x is odd write x=2y+1 and define h(2y+1)=g(y).