Welcome to our community

Be a part of something great, join today!

Counting proof of the addition rule

MI5

New member
Sep 8, 2013
8
Let $ \left\{A_1, A_2, \cdots , A_n\right\}$ be a system of subsets of a finite set $A$ such that these subsets are pairwise disjoint and their union $A = \cup_{i=1}^{n}A_{i}$. Then

$ |A| = \sum_{i=1}^{n}|A_i|$. (1)

Proof: According to the hypothesis, each $a \in A$ belongs to exactly one of the subsets $A_{i}$, and therefore it counts exactly once on each side of equation 1.


Could someone explain the bold bit (what's meant by it counts exactly once on each side of the equation) and why that counts as proof.
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,493
If $A_1$ and $A_2$ are not disjoint, then we can't say that $|A_1\cup A_2|=|A_1|+|A_2|$. The right-hand side is greater because the elements from the intersection are counted twice: they are counted both as elements of $A_1$ and as elements of $A_2$. (Therefore, the correct formula is $|A_1\cup A_2|=|A_1|+|A_2|-|A_1\cap A_2|$.)

In contrast, in the statement you wrote each element is counted exactly once in both sides of the equation. It can't happen that some $x\in A_i$ and $x\in A_j$ if $i\ne j$, so $x$ will not be counted both in $|A_i|$ and $|A_j|$.

This fact is obvious to anybody who can count: e.g., the total number of children is the number of boys plus the number of girls. The only reason it is made into a proof is to create a contrast with the case where the sets are not necessarily disjoint and where counting is more complicated.
 

MI5

New member
Sep 8, 2013
8
Fantastic explanation. Thank you.