I Sum principle proof: discrete mathematics

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.
 

andrewkirk

Science Advisor
Homework Helper
Insights Author
Gold Member
3,726
1,354
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 gotta rush off now but I'll explain why when I get back if somebody else has not already done so.
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,358
3,401
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?
 

Math_QED

Science Advisor
Homework Helper
1,084
354
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

Mentor
Insights Author
2018 Award
10,313
7,027
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

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,358
3,401
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##
 

Math_QED

Science Advisor
Homework Helper
1,084
354
Thanks all, those answers helped a lot.
 

Math_QED

Science Advisor
Homework Helper
1,084
354
Just to be sure, ##j \leq k## is always true here? And the j is there to indicate the set ##A_j## ?
 

Want to reply to this thread?

"Sum principle proof: discrete mathematics" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top