Chapter 6, Problem 1RE

Suppose A and B are nonempty finite sets and $\left|A\cup B\right|<\left|A\right|+\left|B\right|$. Show that $A\cap B\ne \varnothing$.

To determine

To prove: $A\cap B\ne \varnothing$.

Explanation of Solution

Given Information:

Suppose A and B are nonempty finite sets and $\left|A\cup B\right|<\left|A\right|+\left|B\right|$.

Explanation:

Proof:

By Principle of Inclusion-Exclusion,

A finite set, $A_1,A_2,\mathrm{..........},A_n$, the number of element in the union $A_1\cup A_2\cup \mathrm{.....}\cup A_n$ is,

$\left|A_1\cup A_2\cup \mathrm{.....}\cup A_n\right|={\displaystyle \sum _i\left|A_i\right|-{\displaystyle \sum _{i<j}\left|A_i\cap A_j\right|}}+{\displaystyle \sum _{i<j<k}\left|A_i\cap A_j\cap A_k\right|}-\mathrm{...}+{\left(-1\right)}^{n+1}\left|A_1\cap A_2\cap \mathrm{....}\cap A_n\right|$

Where the first sum is over all i, the second is over all pairs i, j with $i<j$, the third sum is over all triples i, j, k with $i<j<k$, and so forth.

By the Principle of Inclusion-Exclusion we have,

$\begin{array}{l}\left|A\cup B\right|=\left|A\right|+\left|B\right|-\left|A\cap B\right|\\ \left|A\cap B\right|=\left|A\right|+\left|B\right|-\left|A\cup B\right|\end{array}$

Since,

$\left|A\cup B\right|<\left|A\right|+\left|B\right|$

Thus,

$\left|A\right|+\left|B\right|-\left|A\cup B\right|>0$

Therefore,

$\left|A\cap B\right|>0$

Hence,

$A\cap B\ne \varphi$