Prove that |A⊕B|≥|A−B||A \oplus B| \geq |A-B|

Let AA and BB be finite sets. Prove that |A⊕B|≥|A−B|.|A \oplus B| \geq |A-B|.

I first found that A⊕B=(A∪B)−(A∩B)=(A∪B)∩(¯A∪¯B)=((A∪B)∩¯A)∪((A∪B)∩¯B)=((¯A∩B)∪∅)∪((¯B∩A)∪∅)=(¯A∩B)∪(¯B∩A)\begin{align*}A \oplus B &= (A \cup B)-(A \cap B)\\&=(A \cup B) \cap (\overline{A} \cup \overline{B})\\&=((A \cup B) \cap \overline{A}) \cup ((A \cup B) \cap \overline{B})\\&=((\overline{A} \cap B) \cup \emptyset) \cup ((\overline{B} \cap A) \cup \emptyset)\\&=(\overline{A} \cap B) \cup (\overline{B} \cap A)\end{align*} and so |A⊕B|≥|(A∩¯B)|=|A−B||A \oplus B| \geq |(A \cap \overline{B})| =|A-B|.

Is there a simpler way of thinking about it or is this the correct way?



1 Answer


If you want to prove it algebraically like you did, there is (I am pretty sure) no essentially simpler way. However, it is trivial to show directly from the definitions
A – B =\{a \mid a \in A \land a \notin B\} \qquad\qquad A \oplus B = \{a \mid (a \in A \land a \notin B) \lor (a \notin A \land a \in B)\}

that A−B⊆A⊕BA – B \subseteq A \oplus B; namely, if a∈A−Ba \in A – B, then a∈Aa \in A and a∉Ba \notin B, whence a∈A⊕Ba \in A \oplus B.