Saturday, 28 May 2016

elementary set theory - Union of countable sets is countable.

is my proof that the union of countable sets is countable correct ?



If A1,A2,A3,,An is a collection of countable sets, then the union
A1A2A3An


is countable as well.



Proof. Base case: Consider the set
B=A2A1


Clearly, BA2(B is countable) and A1B = A1A2.




If B is finite, then
B={b1,b2,b3,b4,,bj}jN0


and so we can construct a bijection
f(n)={bnnjanjn>j

If B is infinite, then we can construct a bijection
f(n)={bn2n evenan+12n odd

Now, suppose the statement holds for n=k2, that is,
A1A2A3Ak
is a countable set. Observe that
(A1A2A3Ak)Ak+1

is a union of two countable sets which, by the base case, is also countable. Thus, by induction, the statement holds for all nN.

No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...