Finite Sets and Unions I came across the following problem on finite sets:

If $A_1, \dots, A_m$ is a finite list of finite subsets of a set, show that $A_1 \cup \dots \cup A_m$ is also finite.

By definition, for each positive integer $j=1, \dots, m$ there is a positive integer $r_j$ and a surjection $\sigma_j: \{1, \dots, r_j \} \to A_j$. Let $r = r_1 + \cdots + r_m$. Then we want to construct a surjection $\sigma: \{1, \dots, r \} \to A$. Now if $x \in A$, then $$x \in A_1 \ \text{or} \ x \in A_2 \ \text{or} \ \dots \ \text{or} \ x \in A_m$$
Note that the or is inclusive. So perhaps we can construct the surjection by saying that if $x \in A_i$ and only one $A_i$ for $i = 1, \dots, m$ then use the "individual surjections" pertaining to $A_i$. For example, if $x \in A_3$ only then there is a number $f$ in $\{1, \dots, r_3 \}$ such that $\sigma_3(f) = x$.
How do we get to the case where $x$ is in an intersection of sets? For example if $x \in A_1 \cap A_2$ then we would have to consider a surjection that involved $\{1, \dots , r_1\}$ and $\{1, \dots, r_2 \}$.
 A: Several people have suggested modifying the $A_i$s to get a family that is disjoint, and working with that. Here's another way of doing the same thing. The key is to "paint" each $A_i$ a different color so that they are disjoint, and then use the following:
Lemma. If $X$ and $Y$ are sets, $X$ is finite, and $f\colon X\to Y$ is surjective, then $Y$ is finite.
Proof. Since $X$ is finite, there is natural number $n=\{0,1,\ldots,n-1\}$ and a surjection $g\colon n\to X$. The composition of surjective functions is surjective, so $f\circ g$ is a surjection from a natural number to $Y$, hence $Y$ is finite. QED
Now, let $A_1,\ldots,A_m$ be a finite list of finite sets. Let $C_i = A_i\times\{i\}$. Then $C_i\cap C_j=\emptyset$ if $i\neq j$. (We have "painted" each set a "different color" by using the indices to identify the sets; this is a useful trick, and common in defining the sum of cardinalities). 
Given surjections $f_i\colon n_i\to A_i$, define $f\colon n_1+\cdots+n_m\to \cup C_i$ the "obvious way". This proves that the union of the $C_i$ is finite.
Finally, let $g\colon \cup C_i \to \cup A_i$ by projecting onto the first component of each ordered pair, and apply the Lemma.
A: Spare yourself some notational annoyance by doing this for two sets, then use induction to finish.
A: Let $B_k=A_k\setminus\left(\bigcup_{i=1}^{k-1}A_i\right)$. Then the $B_k$ are disjoint, and 
$$A_1\cup\cdots\cup A_m=B_1\cup\cdots\cup B_m.$$
Note that $B_k\subseteq A_k$ for each $k$. Now prove that any subset of a finite set is finite, so that there are bijections $\sigma_k:\{1,\ldots,b_k\}\rightarrow B_k$ for each $k$. Then define the function
$$\sigma:B_1\cup\cdots\cup B_m\rightarrow \{1,\ldots,\textstyle\sum_{i=1}^m b_i\}$$
by $$\sigma(x)=\sigma_k^{-1}(x)+\textstyle\sum_{i=1}^{k-1}b_i$$
where $k$ is the unique element of $\{1,\ldots,m\}$ for which $x\in B_k$ (this is unique because the $B_k$ are disjoint). Now prove that $\sigma$ is a bijection.
A: You can create a pairwise disjoint sequence $B_1,...,B_n$ such that $ \cup{B_i}$=$\cup{A_j}$ , by defining $A_1$:=$B_1$, and $B_k:=A_k-A_{k-1}$. Then you can do a couple of things:
1)Since the $B_i$ are pairwise-disjoint:
|$B_1 \cup{B_2} \cup.... \cup{B_n} |=|B_1|+|B_2|+.....+|B_n|$
Or, using that the $B_i$ are finite, you can do an injection, for each $B_i$:
$f:B_1\rightarrow\{ {{1,2,...,n_{B_1}}}\}$
$f:B_2\rightarrow\{ {n_{B_1},n_{B_1}+1,.....,n_{B_1}+|B_2|-1}\}$
and call the last element on the right $n_{B_2}$, and continue with the construction until you get to $B_n$. Then you have a bijection between:
$\{A_1\cup A_2\cup.....\cup A_n\} \rightarrow\{{1,2,...,n_{B_1},n_{B_1}+1,...,n_{B_2},....,n_{B_k}}\}$
where the right hand side is the segment ${x:x<n_{B_k}}$
