Cardinality of Set Union
Jump to navigation
Jump to search
Theorem
Union of 2 Sets
Let $S_1$ and $S_2$ be finite sets.
Then:
- $\card {S_1 \cup S_2} = \card {S_1} + \card {S_2} - \card {S_1 \cap S_2}$
Union of 3 Sets
Let $S_1$, $S_2$ and $S_3$ be finite sets.
Then:
\(\ds \card {S_1 \cup S_2 \cup S_3}\) | \(=\) | \(\ds \card {S_1} + \card {S_2} + \card {S_3}\) | ||||||||||||
\(\ds \) | \(\) | \(\, \ds - \, \) | \(\ds \card {S_1 \cap S_2} - \card {S_1 \cap S_3} - \card {S_2 \cap S_3}\) | |||||||||||
\(\ds \) | \(\) | \(\, \ds + \, \) | \(\ds \card {S_1 \cap S_2 \cap S_3}\) |
General Case
Let $\sequence {S_n}_{n \mathop \in \N}$ be a sequence of sets.
Then:
\(\ds \card {\bigcup_{i \mathop = 1}^n S_i}\) | \(=\) | \(\ds \sum_{i \mathop = 1}^n \card {S_i}\) | ||||||||||||
\(\ds \) | \(\) | \(\, \ds - \, \) | \(\ds \sum_{1 \mathop \le i \mathop < j \mathop \le n} \card {S_i \cap S_j}\) | |||||||||||
\(\ds \) | \(\) | \(\, \ds + \, \) | \(\ds \sum_{1 \mathop \le i \mathop < j \mathop < k \mathop \le n} \card {S_i \cap S_j \cap S_k}\) | |||||||||||
\(\ds \) | \(\) | \(\ds \cdots\) | ||||||||||||
\(\ds \) | \(\) | \(\, \ds + \, \) | \(\ds \paren {-1}^{n - 1} \card {\bigcap_{i \mathop = 1}^n S_i}\) |
Corollary
Let $S_1, S_2, \ldots, S_n$ be finite sets which are pairwise disjoint.
Then:
- $\ds \card {\bigcup_{i \mathop = 1}^n S_i} = \sum_{i \mathop = 1}^n \card {S_i}$
Specifically:
- $\card {S_1 \cup S_2} = \card {S_1} + \card {S_2}$
Examples
Example: 3 Arbitrary Sets
Let $A_1, A_2, A_3$ be finite sets.
Let:
\(\ds \card {A_1}\) | \(=\) | \(\ds 10\) | ||||||||||||
\(\ds \card {A_2}\) | \(=\) | \(\ds 15\) | ||||||||||||
\(\ds \card {A_3}\) | \(=\) | \(\ds 20\) | ||||||||||||
\(\ds \card {A_1 \cap A_2}\) | \(=\) | \(\ds 8\) | ||||||||||||
\(\ds \card {A_2 \cap A_3}\) | \(=\) | \(\ds 9\) |
Then:
- $26 \le \card {A_1 \cup A_2 \cup A_3} \le 28$
Example: Examination Candidates
In a particular examination, there were $3$ questions.
All candidates attempted at least one of the questions.
- $40$ candidates attempted question $1$.
- $47$ candidates attempted question $2$.
- $31$ candidates attempted question $3$.
Also, it was apparent that:
- $9$ candidates attempted at least questions $1$ and $2$.
- $15$ candidates attempted at least questions $1$ and $3$.
- $11$ candidates attempted at least questions $2$ and $3$.
and:
- exactly $6$ candidates attempted all $3$ questions.
It follows that $89$ candidates sat the examination in total.
Example: Student Subjects
In a particular group of $75$ students, all studied at least one of the subjects mathematics, physics and chemistry.
All candidates attempted at least one of the questions.
- $40$ students studied mathematics.
- $60$ students studied physics.
- $25$ students studied chemistry.
Also:
- exactly $5$ students studied all $3$ subjects.
It follows that:
Mathematics and Physics
- at least $25$ students studied both mathematics and physics.
Physics and Chemstry
- at least $10$ students studied both physics and chemistry.
Mathematics and Chemistry
- no more than $20$ students studied both mathematics and chemistry.
Also see
Sources
- 1975: T.S. Blyth: Set Theory and Abstract Algebra ... (previous) ... (next): $\S 1$. Sets; inclusion; intersection; union; complementation; number systems: Exercise $8$