Inequalities relating the cardinality of finite sets

692 Views Asked by At

Take $A$ and $A$ to be finite sets whose cardinalities are denoted $|A|$ and $|B|$ respectively. Are the follow two inequalities about the union and intersection of $A$ and $B$ true?

$$\mathrm{max}(|A|,|B|) \leq |A \cup B| \leq |A| + |B|$$ $$0 \leq |A \cap B| \leq \mathrm{min}(|A|,|B|)$$

If these inequalities are true are the upper and lower bounds optimal?

1

There are 1 best solutions below

4
On BEST ANSWER

Both inequalities are true for simple reasons:

$A$ and $B$ are subsets of $A \cup B$ thus $|A|, |B| \le |A \cup B|$. And $$\begin{align*}|A \cup B| &= |A \setminus B| + \underbrace{|B \setminus A| + |A \cap B|}_{\le |B|} \\ & \le |A| + |B| \end{align*}$$

Now, since $A \cap B \subseteq A, B$, we also get $$ |A \cap B| \le \min(|A|, |B|). $$

However, I don't know what you mean when you ask whether these bounds are 'optimal'. Do you mean that equality holds? If so, the answer is no and I'll leave it to you to find counterexamples (there are plenty easy counterexamples).