Similarly, does the set operation union always increase (or not change) the cardinality of a set? I think it intuitively makes sense but how would I show this using maybe an inclusion-exclusion principle?
My attempt would be:
$\mid {A \cup B} \mid = \mid{A}\mid + \mid{B}\mid – \mid{A\cap B}\mid$
$\mid {A} \mid = \{\mid{A \cup B}\mid – \mid{B}\mid\} + \mid{A\cap B}\mid$
$\mid A \mid \quad \geq \quad \mid {A\cap B} \mid$ (since we have $\mid{A \cup B}\mid \geq \mid{B}\mid$)
and similarly, $\mid A \mid \quad \leq \quad \mid{A \cup B}\mid$ (since $\mid{B}\mid \geq \mid{A \cap B}\mid$).
But then I am using the result I want to prove. How can I show otherwise?
And if so, would the following be true with no assumption on the sequence of sets $\{A_n\}_{n=1}^\infty$ ?
- We get a decreasing sequence of sets $D_{n} = \bigcup_{k\geq{n}}^{\infty}A_k$ (by excluding one set by one set from the infinite union $\bigcup_{n=1}^{\infty}A_n$ )
- Similarly, we get an increasing sequence of sets $I_{n} = \bigcap_{k\geq{n}}^{\infty}A_k$ (by excluding one set by one from the infinite intersection $\bigcap_{n=1}^{\infty}A_n$ )
Best Answer
$(A\cap B)\subseteq A$, so that a trivial injection between both sets exists. This immediately implies $|A\cap B|\leq|A|$.
Similarly, $A\subseteq (A\cup B)$, so $|A|\leq|A\cup B|$.
And yes, your affirmations follow shortly from this.