Let $A,B,X$ be finite sets. Prove that $|A \triangle X| + |X \triangle B| = |A \triangle B| \iff A \cap B \subseteq X \subseteq A \cup B$

Question

I'm trying to do the following exercise:

Let $A,B,X$ be finite subsets of a set $U$. Prove that $|A \triangle X| + |X \triangle B| = |A \triangle B| \iff A \cap B \subseteq X \subseteq A \cup B$

I am allowed to assume that the cardinality of the symmetric difference of finite sets is a metric. So I can use the following properties without proving them:

Let $A,B,C$ be finite subsets of a set $U$, then:

P.1) $|A \triangle B| \ge 0$

P.2) $|A \triangle B| = 0 \iff A=B$

P.3) $|A \triangle B| = |B \triangle A| $

P.4) $|A \triangle C| \le |A \triangle B| + |B \triangle C|$

This is how I tried to prove the implication $A \cap B \subseteq X \subseteq A \cup B \implies |A \triangle X| + |X \triangle B| = |A \triangle B|$

I'm assisting myself with the following two lemmas:

Lemma 1: $A \cap B \subseteq X \subseteq A \cup B \implies (A \triangle X) \cap (X \triangle B) = \emptyset$

Proof:

Let $A,B,X$ be finite sets such that $A \cap B \subseteq X \subseteq A \cup B$

Let's assume there exists an element $t \in (A \triangle X) \cap (X \triangle B)$

There are four possible cases:

i) $t \in (A-X) \ \land \ t \in (X-B)$

ii) $t \in (A-X) \ \land \ t \in (B - X)$

iii) $t \in (X-A) \ \land \ t \in (X-B)$

iv) $t \in (X-A) \ \land \ t \in (B-X)$

Assuming i):

$t \in (A-X) \ \land \ t \in (X-B) \implies (t \in A \ \land \ t \notin X) \land (t \in X \ \land t \notin B) \implies t \notin X \land t \in X$ , which is a contradiction.

Assuming ii):

$t \in (A-X) \ \land \ t \in (B - X) \implies (t \in A \ \land t \notin X) \land (t \in B \ \land \ t \notin X)$

$\implies (t \in A \ \land \ t \in B) \land t \notin X \implies t \in A \cap B \ \land \ t \notin X$, which contradicts the hypothesis $A \cap B \subseteq X$.

Assuming iii):

$t \in (X-A) \ \land \ t \in (X-B) \implies (t \in X \ \land \ t \notin A) \land (t \in X \ \land \ \ t \notin B)$

$\implies t \in X \ \land \ t \notin A \ \land t \notin B \implies t \in X \ \land \ t \notin A \cup B$, which contradicts the hypothesis $X \subseteq A \cup B$.

Assuming iv):

$t \in (X-A) \ \land \ t \in (B-X) \implies (t \in X \ \land \ t \notin A) \land (t \in B \ \land \ t \notin X) \implies t \in X \land t \notin X$ , which is a contradiction.

We get a contradiction in all four cases, so there does not exist an element $t$ such that $t \in (A \triangle X) \cap (X \triangle B)$.

Therefore $(A \triangle X) \cap (X \triangle B) = \emptyset$

$ \blacksquare$

Lemma 2: If $A,B,X$ are finite subsets of $U$ then $(A \triangle X) \cup (X \triangle B) = (A \cup X \cup B) - (A \cap X \cap B)$

Proof:

By definition of symmetric difference we have:

$(A \triangle X) \cup (X \triangle B) = [(A \cup X) \cap \overline{(A \cap X)}] \cup [(X \cup B) \cap \overline{(X \cap B)}]$

Applying the distributive laws of union and intersection:

$(A \triangle X) \cup (X \triangle B) = [((A \cup X) \cap \overline{(A \cap X)} \ ) \cup (X \cup B)] \cap [((A \cup X) \cap \overline{(A \cap X)} \ ) \cup \overline{(X \cap B)}]$

$= [((A \cup X) \cup (X \cup B)) \cap ( \ \overline{(A \cap X)} \ \cup (X \cup B))] \cap [((A \cup X) \cup \overline{(X \cap B)} \ ) \cap ( \ \overline{(A \cap X)} \ \cup \ \overline{(X \cap B)} \ )]$

By de Morgan laws and idempotence and associativity of union and intersection:

$(A \triangle X) \cup (X \triangle B) = [(A \cup X \cup B) \cap ( ( \ \overline{A} \cup \overline{X} \ ) \cup (X \cup B))] \cap [((A \cup X) \cup ( \ \overline{X} \cup \overline{B} \ )) \cap ( \overline{A} \cup \overline{X} \cup \overline{B})]$

$ = [(A \cup X \cup B) \cap ( \ \overline{A} \cup ( \overline{X} \ \cup X ) \cup B)] \cap [(A \cup (X \cup \ \overline{X}) \cup \overline{B} \ ) \cap ( \overline{A} \cup \overline{X} \cup \overline{B})]$

By complementation and absorption laws:

$(A \triangle X) \cup (X \triangle B) = [(A \cup X \cup B) \cap ( \ \overline{A} \cup U \cup B)] \cap [(A \cup U \cup \overline{B} \ ) \cap ( \overline{A} \cup \overline{X} \cup \overline{B})]$

$= [(A \cup X \cup B) \cap U] \cap [U \cap ( \overline{A} \cup \overline{X} \cup \overline{B})]$

$= (A \cup X \cup B) \cap ( \overline{A} \cup \overline{X} \cup \overline{B})$

$= (A \cup X \cup B) \cap ( \overline{A \cup X \cup B} )$

$= (A \cup X \cup B) - ( A \cup X \cup B )$

$\blacksquare$

Now, going back to the original implication we have:

$A \cap B \subseteq X \subseteq A \cup B \implies A \cup B \cup X = A \cup B \ \land \ A \cap B \cap X = A \cap B$

$\implies (A \cup B \cup X ) - (A \cap B \cap X) = (A \cup B) -(A \cap B)$

$\implies (A \cup B \cup X ) - (A \cap B \cap X) = A \triangle B$

So, applying lemma 2:

$(A \triangle X) \cup (X \triangle B) = A \triangle B \implies |(A \triangle X) \cup (X \triangle B) | = |A \triangle B|$

$\implies |(A \triangle X)| + |(X \triangle B) | - |(A \triangle X) \cap (X \triangle B)|= |A \triangle B|$

And finally, by lemma 1:

$|(A \triangle X)| + |(X \triangle B) | - |\emptyset|= |A \triangle B|$

$|(A \triangle X)| + |(X \triangle B) | - 0= |A \triangle B|$

$|(A \triangle X)| + |(X \triangle B) |= |A \triangle B|$

$\blacksquare$

Is this part of the proof correct? And how do I prove that $|A \triangle X| + |X \triangle B| = |A \triangle B| \implies A \cap B \subseteq X \subseteq A \cup B$ ?? I don't know what to do on that part.

Answer 1

I have not checked your proof/effort, but reach unto you an alternative route.

---

In the first place draw a Venn-diagram.

Discern the following $7$ sets:

• $S_{1}=A\cap B\cap X$
• $S_{2}=A\cap B\cap X^{\complement}$
• $S_{3}=A\cap B^{\complement}\cap X$
• $S_{4}=A\cap B^{\complement}\cap X^{\complement}$
• $S_{5}=A^{\complement}\cap B\cap X$
• $S_{6}=A^{\complement}\cap B\cap X^{\complement}$
• $S_{7}=A^{\complement}\cap B^{\complement}\cap X$

The sets are disjoint and:

• $A\Delta X=S_{2}\cup S_{4}\cup S_{5}\cup S_{7}$
• $X\Delta B=S_{2}\cup S_{3}\cup S_{6}\cup S_{7}$
• $A\Delta B=S_{3}\cup S_{4}\cup S_{5}\cup S_{6}$

So the equality $\left|A\Delta X\right|+\left|X\Delta B\right|=\left|A\Delta B\right|$ can be written as:

$$\left|S_{2}\right|+\left|S_{4}\right|+\left|S_{5}\right|+\left|S_{7}\right|+\left|S_{2}\right|+\left|S_{3}\right|+\left|S_{6}\right|+\left|S_{7}\right|=\left|S_{3}\right|+\left|S_{4}\right|+\left|S_{5}\right|+\left|S_{6}\right|\tag1$$

Equivalent with $(1)$ are the following statements:

• $\left|S_{2}\right|+\left|S_{7}\right|=0$
• $S_{2}=\varnothing=S_{7}$
• $A\cap B\subseteq X\subseteq A\cup B$