Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Sum principle proof: discrete mathematics

  1. Oct 8, 2016 #1

    Math_QED

    User Avatar
    Homework Helper

    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.
     
  2. jcsd
  3. Oct 8, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  4. Oct 8, 2016 #3

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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?
     
  5. Oct 8, 2016 #4

    Math_QED

    User Avatar
    Homework Helper

    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.
     
  6. Oct 8, 2016 #5

    fresh_42

    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.
     
  7. Oct 8, 2016 #6

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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##
     
  8. Oct 8, 2016 #7

    Math_QED

    User Avatar
    Homework Helper

    Thanks all, those answers helped a lot.
     
  9. Oct 8, 2016 #8

    Math_QED

    User Avatar
    Homework Helper

    Just to be sure, ##j \leq k## is always true here? And the j is there to indicate the set ##A_j## ?
     
  10. Oct 8, 2016 #9

    fresh_42

    Staff: Mentor

    Yes. And the ##f_j \; : \; [n_j] \rightarrow A_j##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Sum principle proof: discrete mathematics
  1. Discrete mathematics (Replies: 2)

  2. Discrete Mathematics? (Replies: 0)

  3. Mathematical proof (Replies: 1)

Loading...