Dtjytyk

I know this seems like a repeated question, but what I find the other answers laking is how they are dealing with the fact that our sets aren't mutually disjoint. If anyone could explain how the inductive proof ( or if there is another way to prove this) handles this fact it would be greatly appreciated.

Proposition: Let $A$ be a countable family of sets. Assume that each set in $A$ is countable. Prove that the set $U$ = $A : A in$ the family of sets also countable.

As long as it is a countable family, we don't require them to be pairwise disjoint. To see how to generalize the answers in the other posts, suppose that $$mathcalA=A_n:ninBbb N,$$ and consider the family $$mathcalB=B_n:ninBbb N$$ with the sets $B_n$ defined recursively as follows:

• 
  $B_1:=A_1$ (or $B_0:=A_0$ if $0inBbb N$ for you),


• $B_n+1:=A_n+1smallsetminusbigcup_kle nA_k.$

This is known as a "disjointification." The union of the sets in $mathcalB$ is the same as the union of the sets in $mathcalA,$ but the sets of $mathcalB$ are pairwise disjoint.

In many cases, if we can prove something about a union of (countably-many) disjoint sets, each of which has some property/properties (such as countability or measurability), this trick will allow us to generalize the proof to unions of (countably-many) arbitrary sets with said property/properties.

Hint: Suppose
$$mathcalA = bigcup_n=1^infty A_n$$
where each $A_k$ is countable. If these $A_k$ are not disjoint then, by setting $B_k = A_k backslash cup_j=1^k-1 A_j$ you can write $mathcalA$ as a countable disjoint union in the following way,
$$mathcalA = bigcup_n=1^infty B_n.$$
The $B_k$ are countable because the $A_k$ are (can you prove this?).

This shows that you can assume that the countable union is disjoint - the other arguments that you've seen can now be applied. I hope this helps!

Given a sequence $(A_n)_ninmathbb N$ of countable sets, the usual proof defines a map from $mathbb N$ onto $bigcup_ninmathbb NA_n$. In fact, if the $A_n$'s are not disjoint, then this map will not be injective. But that's not a serious problem, because any infinite set $A$ for which there is a surjective map from $mathbb N$ onto $A$ is countable.

Let $A_n$ be a countable set for each $nin mathbb N$. We'll show how to construct a surjective map $f:mathbb Ntobigcup_n=1^infty A_n$ to prove that $bigcup_n=1^infty A_n$ is countable. Note that since each $A_n$ is countable, we may put $A_n$ into one-to-once correspondence with $mathbb N$ and so be able to refer to the $j^textth$ element of the set.

To construct our $f$, we'll rely on the fact that there are infinitely many prime numbers in $mathbb N$, call these $p_1<p_2<cdots$. The idea, then, will be to send $p_i^jmapsto a_i,j$ where $a_i,j$ is the $j^textth$ element in $A_i$. This forms a surjection from the powers of primes to $bigcup_n=1^infty A_n$ since every element is the $j^textth$ element of some $A_i$. Thus, we define $$f(n)=begincases a_i,j &: n=p_i^j\ a_1,1 & :text otherwiseendcases.$$

Not if it's an uncountably infinite union.

Since you have a countable family of sets, you can label them $A_i$, with $iinmathbbN$. Now you can "pad" the elements and create new sets:
$tilde A_i = ~ain A_i$. Each padded set is isomorphic its original version, but all the padded sets are pairwise disjoint.

Since the padded sets are disjoint, you can believe the proof that $tilde U = cup_i tilde A_i$. Now you just have to convince yourself that there is an injection from the union on the original sets to $tilde U$.