# 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$

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.

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$$