# 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 \}$.

-
Maybe you can simplify your problem by creating a collection ${B_1,..,B_n}$ with $B_i \cap B_j$ is empty, and such that $\cup B_i= \cup A_j$ by defining: $B_1:=A_1$, then define $B_2:=A_2-A_1$, and , in general $B_n:=A_n-A_{n-1}$. At any rate, for the finite case, you can use inclusion-exclusion, or just use the very rough bound: $|A_1 \ cup A_2\cup... \cupA_n|\leq{ |A_1|+|A_2|+...+|A_n|}$. Or get an actual equality using the pairwise-disjoint $B_i$'s –  gary Jul 1 '11 at 2:15

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.

-

Spare yourself some notational annoyance by doing this for two sets, then use induction to finish.

-

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.

-
Say $x \in B_4$. Then $x$ gets mapped to $b_1+b_2+b_3+b_k$ where $k \in \{1, \dots, m \}$? –  Damien Jul 1 '11 at 2:30
@Damien: No, $x$ gets mapped to $b_1+b_2+b_3+\sigma_4^{-1}(x)$, and $\sigma_4^{-1}(x)$ will be some element of $\{1,\ldots,b_4\}$. –  Zev Chonoles Jul 1 '11 at 2:35

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}}$

-
I was not able to get {} on the target sets above. Could someone tell me how to do it? –  gary Jul 1 '11 at 2:48
To get a brace in LaTeX, \{ and \} are necessary. For example, \{a,b,c\} produces $\{a,b,c\}$, while {a,b,c} produces ${a,b,c}$. –  Zev Chonoles Jul 1 '11 at 2:52
Also, if you see a piece of LaTeX you want to know the code for on the site, you can right click on it and choose "Show Source" - this is a good way of picking up how to do things. –  Zev Chonoles Jul 1 '11 at 2:53
Thanks, Zev, just did it. –  gary Jul 1 '11 at 3:14