Sum principle proof: discrete mathematics

[member 587159]

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.

 

[andrewkirk]

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?

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 got to rush off now but I'll explain why when I get back if somebody else has not already done so.

 

[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?

 

[member 587159]

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?

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.

 

[fresh_42]

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.

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.

 

[PeroK]

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.

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$

 

[member 587159]

Thanks all, those answers helped a lot.

 

[member 587159]

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

 

[fresh_42]

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

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