#### Math_QED

Science Advisor

Homework Helper

- 1,084

- 354

**Theorem**: Let ##A_1, A_2, ..., A_k## be finite, disjunct sets. Then ##|A_1 \cup A_2 \cup \dots \cup A_k| = |A_1| + |A_2| + \dots + |A_k|##

I will give the proof my book provides, I don't understand several parts of it.

**Proof:**

We have bijections ##f_i: [n_i] \rightarrow A_i## for ##i \in [k]##

Notice: ##[\sum\limits_{i=1}^{k}n_i] = [1..n_1]\cup[(n_1 + 1)..(n_1 + n_2)]\cup\dots\cup[(\sum\limits_{i=1}^{k-1} n_i)+ 1 ..\sum\limits_{i=1}^{k}n_i]##

Define:

##f: [\sum\limits_{i=1}^{k}n_i] \rightarrow A_1 \cup A_2 \cup \dots \cup A_k##

by

##f(i) = f_j(i - \sum\limits_{i=1}^{j-1}n_i)## if ##i \in [(\sum\limits_{l=1}^{j-1}n_l) + 1.. \sum\limits_{l=1}^{j}n_l]##

Verify yourself that f is a bijection. Don't forget that the sets are disjunct. QED.

I know that the notation [n] = [1..n] = {1,2,3, ...} means and also ##[n_1..n_2]## = {##n_1, n_1 +1, ... n_2##}

**Questions**

1) What does the notation ##f_i: [n_i] \rightarrow A_i## for ##i \in [k]## mean? Does it mean that if f is a bijection, then ##A_i## has ##n_i## elements?

2) Where does the ##j## in ##f(i) = f_j(i - \sum\limits_{i=1}^{j-1}n_i)## if ##i \in [(\sum\limits_{l=1}^{j-1}n_l) + 1.. \sum\limits_{l=1}^{j}n_l]## come from? What are the restrictions on j? j can't be a random number right?

Thanks in advance.