Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

4 Answers 4

up vote 4 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
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}}$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.