1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.