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:

\(\displaystyle \card {S_1 \cup S_2 \cup S_3}\) \(=\) \(\displaystyle \card {S_1} + \card {S_2} + \card {S_3}\)
\(\displaystyle \) \(\) \(\, \displaystyle - \, \) \(\displaystyle \card {S_1 \cap S_2} - \card {S_1 \cap S_3} - \card {S_2 \cap S_3}\)
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \card {S_1 \cap S_2 \cap S_3}\)


General Case

Let $S_1, S_2, \ldots$ be sets.

Then:

\(\displaystyle \card {\bigcup_{i \mathop = 1}^n S_i}\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n \card {S_i}\)
\(\displaystyle \) \(-\) \(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop \le n} \card {S_i \cap S_j}\)
\(\displaystyle \) \(+\) \(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop < k \mathop \le n} \card {S_i \cap S_j \cap S_k}\)
\(\displaystyle \) \(\cdots\) \(\displaystyle \)
\(\displaystyle \) \(+\) \(\displaystyle \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:

$\displaystyle \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:

\(\displaystyle \card {A_1}\) \(=\) \(\displaystyle 10\)
\(\displaystyle \card {A_2}\) \(=\) \(\displaystyle 15\)
\(\displaystyle \card {A_3}\) \(=\) \(\displaystyle 20\)
\(\displaystyle \card {A_1 \cap A_2}\) \(=\) \(\displaystyle 8\)
\(\displaystyle \card {A_2 \cap A_3}\) \(=\) \(\displaystyle 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.


Sources