- #1
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.
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.