# I Sum principle proof: discrete mathematics

Tags:
1. Oct 8, 2016

### Math_QED

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?

2. Oct 8, 2016

### andrewkirk

It means that $f_i$ is a function whose domain is the set $\{1,2,...,n_i\}$ and range is $A_i$. I haven't seen the notation $[n_i]$ before but it can be inferred from the context what it means and I like it.

The part to which your second question refers is written wrongly. I've gotta rush off now but I'll explain why when I get back if somebody else has not already done so.

3. Oct 8, 2016

### PeroK

This is perhaps a case where it's obvious what the proof is doing but the notation gets messy. My suggestion is to try to work out the strategy of the proof for yourself and then map that strategy back to the proof you are given.

For example, you could label the elements of these sets:

$A_1 = \{ a_1, \dots , a_{n_1} \}$

etc.

I wonder whether the proof given stands up if some of the sets can be empty?

4. Oct 8, 2016

### Math_QED

But do you have any idea what the j could stand for though? And you are right, I should think about what happens when some sets are empty but first I need to understand the proof. Thanks for your answer.

5. Oct 8, 2016

### Staff: Mentor

You may write $f=(f_1, \dots , f_k)$ where $f(i+\sum_{m=1}^{m=j-1}n_m):=f_j(i)$ iff $i \in [n_j]$. It is all about extending all the $f_j$ to a function $f$.
$f(i)=f_1(i)$ for $1 \leq i \leq n_1$
$f(i)=f_2(i-n_1)$ for $n_1+1 \leq i \leq n_1+n_2$
$f(i)=f_3(i-n_1-n_2)$ for $n_1+n_2+1 \leq i \leq n_1+n_2+n_3$
etc.
The index $j$ is needed to distinguish the different components of $f$.
(However I haven't checked the formula you typed and what Andrew refers to.)

Edit: corrected a formula, and I like the notation [n_j], too.

6. Oct 8, 2016

### PeroK

The proof is just trying to select the jth set that $i$ belongs to.

It seems to me it's easier just listing the elements of the union.

Also, like Andrew, I inferred the meaning of the notation by working out what the proof was trying to do.

The same with what $j$ is. I worked backwards from what the proof must be trying to do.

I think it should be something like:

where sum of the n's to $j-1 < i \le$ sum of the n's to $j$

7. Oct 8, 2016

### Math_QED

Thanks all, those answers helped a lot.

8. Oct 8, 2016

### Math_QED

Just to be sure, $j \leq k$ is always true here? And the j is there to indicate the set $A_j$ ?

9. Oct 8, 2016

### Staff: Mentor

Yes. And the $f_j \; : \; [n_j] \rightarrow A_j$.