Lemma The union of two countable sets is countableSolutionAn

Lemma: The union of two countable sets is countable

Solution

Ans-

We argue by contradiction. Suppose there is a nite set A that is equinumerous to
B A: So there is a bijection f : A 7! B.
A is nite so it is equinumerous to some n 2 ! and so there is a bijection g : a 7! n:
The function g f g
1
: n 7! n is an injection (being the composition of three injections). Yet
its range is g(B), which is not n, because there is a 2 A n B and g(a) 2= g(B):
This corollary gives us a nice way to characterise in nite sets and in fact allows us to prove f : n 7! n with ran(f) =6 n: We prove this is impossible and hence establish the claim by
contradiction.
We proceed by induction. Let
T = fn 2 ! : every injection f : n 7! n has ran(f) = ng:
We show T is inductive. It follows that T = ! and we are done.
- 0 2 T : the only function f : 0 7! 0 is f = ;; which satis es ran(f) = ; = 0:
- n 2 T =) n
+
2 T : let f : n
+
7! n
+
be an injection. we prove that ran(f) = n
+
. The key
is to \\break up\" f into fn [ ffng: There are two cases to consider.
Case I: n is closed under f, that is f[n] n: Then fn : n 7! n is an injection. By the induction
hypothesis that n 2 T we get that f[n] = ran(fn) = n:
Next we note that f(n) 2= n (as f is an injection) and so f(n) can only be n.
Putting these two observations together yields:
ran(f) = f[n
+
] = f[n [ fng] = f[n] [ ff(n)g = n [ fng = n
+
: