Proof

(related to Proposition: Counting the Set's Elements Using Its Partition)

From the rules of finite cardinals and the union set operation it follows for any finite sets \(X\) and \(U\) with \(X\cap U=\emptyset\)

\[|X\cup U|=|X|+|U|,~~~~~~~~~~~~~~~~~~~~( * )\]

By hypothesis \(S\) is a finite set, \(S_1,\ldots S_n\subset S\) are its subsets forming a partition of \(S\), i.e.

\[S=\bigcup_{i=1}^n S_i,~~~~~~S_i\cap S_j=\emptyset,\forall i\neq j.\]

and the cardinalities \(|S_i|\) are all known \(i=1,\ldots n\).

We observe that for \(1\le j\le n\) we have \[\left(\bigcup_{i=1}^{n-j}S_i\right)\cap \left(\bigcup_{i=n-j+1}^{n}S_i\right)=\emptyset.\] It follows from the rule \(( * )\) that \[\begin{array}{ccl} |S|=\left|\bigcup_{i=1}^n S_i\right|&=&\left|\bigcup_{i=1}^{n-1}S_i\right|+|S_n|\\ &=&\left|\bigcup_{i=1}^{n-2}S_i\right|+|S_{n-1}|+|S_n|\\ &\vdots&\\ &=&|S_1|+|S_2|+\ldots+|S_{n-1}|+|S_n|\\ &=&\sum_{i=1}^n |S_i| \end{array}\]

Hereby we have used the associativity and commutativity of set union and the associativity and commutativity of the addition of natural numbers. .


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs


References

Bibliography

  1. Kramer Jürg, von Pippich, Anna-Maria: "Von den natürlichen Zahlen zu den Quaternionen", Springer-Spektrum, 2013
  2. Aigner, Martin: "Diskrete Mathematik", vieweg studium, 1993
  3. Ebbinghaus, H.-D.: "Einführung in die Mengenlehre", BI Wisschenschaftsverlag, 1994, 3th Edition