MHB Counting proof of the addition rule

AI Thread Summary
In the discussion on the addition rule, it is established that for a system of pairwise disjoint subsets of a finite set A, the total number of elements in A equals the sum of the elements in each subset. Each element in A belongs to exactly one subset, ensuring it is counted once on both sides of the equation. The contrast is drawn with non-disjoint sets, where elements can be counted multiple times, necessitating a correction in the formula. This clarity reinforces the proof's validity by highlighting the simplicity of counting in disjoint scenarios. The explanation emphasizes the foundational principle of counting distinct elements without overlap.
MI5
Messages
8
Reaction score
0
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.
 
Physics news on Phys.org
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.
 
Fantastic explanation. Thank you.
 
Back
Top