Cardinality of Set Union

From ProofWiki
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