0
$\begingroup$

Given four sets: $A, B, C, D$, suppose that $$A \triangle B \subseteq D \ \land \ B \triangle C \subseteq D $$ Prove: $A \triangle C \subseteq D$

[As $\triangle$ means symmetric difference]

My Attempt:

Notice that $A \triangle B = (A \setminus B) \cup (B \setminus A) = (A \cup B)\setminus (A\cap B)$

Therefore: $\left((A\cup B)\setminus(A\cap B)\right) \text{ and } \left((B\cup C)\setminus (B\cap C)\right) \subseteq D$

EDIT:

I'd like to prove: $(A \triangle C) \subseteq (A\triangle B)\cup(B\triangle C)$ $$\left((A\triangle B)\cup(B \triangle C)\right)=(A\cup B)\setminus(A\cap B)\cup(B\cup C)\setminus(B\cap C)$$ $$ =(A\cup B)\cup(B\cup C)\setminus(A\cap B)\cup(B\cap C)$$ $$=B\cup(A\cup C)\setminus B\cap(A\cup C)$$

$ \ $

Now -- can I say that $(A\cup C)\setminus(A\cap C) \subseteq (B\cup(A\cup C)\setminus B\cap(A\cup C)$?

my previous attempt:

Notice that $A \triangle B = (A \setminus B) \cup (B \setminus A) = (A \cup B)\setminus (A\cap B)$

Therefore: $\left((A\cup B)\setminus(A\cap B)\right) \text{ and } \left((B\cup C)\setminus (B\cap C)\right) \subseteq D$

I'll divide into cases:

I. let $x \in (A\triangle B) \land x\notin C \to x\in (A\setminus C) \subseteq (A \triangle C)$

Notice that $A\triangle B \subseteq D \to x\in D$, therefore $x \in A\triangle C \land x\in D$

II. let $x'\in (B \triangle C) \land \ x'\notin A \ $, then $x'\in (C\setminus A) \subseteq (A\triangle C)$ as $(B\triangle C) \subseteq D \to \ x'\in D$

III. Let $x'' \in (B\cap C) \land x\notin A$ Then $x\in (B\setminus A)\subseteq (A \triangle B) \subseteq D$, Hence $x'' \in D$

Notice that $x'' \in (C\setminus A) \subseteq (A \triangle C)$ , so $x'' \in D \land x''\in (A\triangle C)$.

I don't know if I covered all possible cases (and can't find a way to do so. using contradiction didn't helped). What can be done at such case?

$\endgroup$
3
  • 1
    $\begingroup$ Verify that $(A\Delta C) \subset (A\Delta B) \cup (B\Delta C)$. $\endgroup$ – Kavi Rama Murthy Jul 4 '19 at 12:27
  • 1
    $\begingroup$ When showing that $X\subseteq Y$, you usually start with "Let $x\in X$", and end with "and therefore, $x\in Y$.", with some reasoning in-between. In this case, you therefore ought to start with "let $x\in A\Delta C$". $\endgroup$ – Arthur Jul 4 '19 at 12:29
  • $\begingroup$ @KaviRamaMurthy but the problem is I can't prove that as I'm not sure how to cover all possibilities $\endgroup$ – Jneven Jul 4 '19 at 13:04
3
$\begingroup$

The proof is possibly good, but once you know associativity of symmetric difference, you can realize that $$ (A\mathbin{\triangle}B)\mathbin{\triangle}(B\mathbin{\triangle}C)= A\mathbin{\triangle}(B\mathbin{\triangle}B)\mathbin{\triangle}C= A\mathbin{\triangle}\emptyset\mathbin{\triangle}C=A\mathbin{\triangle}C $$ Thus you only need to show that $X\subseteq D$ and $Y\subseteq D$ implies $X\mathbin{\triangle}Y\subseteq D$, which is clear because $$ X\mathbin{\triangle}Y\subseteq X\cup Y $$

A lower level proof. Let $x\in A\mathbin{\triangle}C$. Either “$x\in A$ and $x\notin C$” or “$x\in C$ and $x\notin A$”.

First case: $x\in A$ and $x\notin C$. If $x\in B$, then $x\in B\mathbin{\triangle}C$. If $x\notin B$, then $x\in A\mathbin{\triangle}B$.

Second case: similar.

$\endgroup$
0
$\begingroup$

This is actually a very easy proof. I think you are getting lost among all those fancy math symbols

Let $x \in A\triangle C$. Therefore $x \in A$ and $x \notin C$ are both true.

If $x \in B, x \in B \triangle C \subseteq D$

Otherwise, $x \notin B$. This implies $x \in A \triangle B \subseteq D$

$\endgroup$
2
  • 5
    $\begingroup$ From $x\in A\triangle C$ it does not follow that $x\in A$ and $x\notin C$. $\endgroup$ – Christian Blatter Jul 4 '19 at 15:03
  • 2
    $\begingroup$ yes, regarding @ChristianBlatter comment -- $x \in A$ and $x \notin C \to x\in A\triangle C$, but the other direction isn't necessarily true $\endgroup$ – Jneven Jul 5 '19 at 16:49

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.