This problem is from Velleman p143 5.

Recall from Section 1.4 that the symmetric difference of two sets A and B is the set $ A \triangle B = (A \setminus B) \cup (B \setminus A) = ( A \cup B) \setminus (A \cap B) $. Prove that if $ A \triangle B \subseteq A $ then $ B \subseteq A $.

My strategy: The crux of this proof is to reduce $ ( A \cup B) \setminus (A \cap B) $ down to the fundamental logical form. $ (A \setminus B) \cup (B \setminus A) = (x \in A \land x \notin B) \lor (x \in B \land x \notin A) $. This gives us a disjunction where if either case is true, then $ x \in A $.

My proof:

Let x be an arbitrary member of B. Suppose that $ A \triangle B \subseteq A $. All the members of $ A \triangle B $ are in either A or B, but not both. The case where $ x \in A \land x \notin B $ is not applicable since $ x \in B $. That leaves the case where $ (x \in B \land x \notin A) $. Since $ x \in B $, we know that $ x \in A \triangle B $ and we're given this means that $ x \in A $. Therefore $ x \in B \to x \in A $. Since x was arbitrary, we assert that $ B \subseteq A $.

My issue: The proof seems OK, I think. The Velleman Proof Designer seems to jive with my argument. However, it's really bothering me that the logical decomposition involves $ (x \in B \land x \notin A ) \to x \in A $. How can x be a member of A and at the same time not be a member of A?

  • 1
    $\begingroup$ If $A \triangle B \subset A$, then you must have $B \setminus A = \emptyset$. Hence $B \subset A$. $\endgroup$ – copper.hat Jan 6 '15 at 23:43
  • $\begingroup$ That helps. A = {1, 2, 3, 4}. B = {4}. $ B \setminus A = \emptyset $. $ A \triangle B = \{1, 2, 3 \}\subseteq A$ is true. $B \subseteq A$ is also true. This all works. I guess I just need to accept $(x \in B \land x \notin A) \to x \in A$ as a strange consequence of the logic. $\endgroup$ – Marty B. Jan 7 '15 at 16:00
  • 1
    $\begingroup$ Think of it this way, $A \triangle B$ is made of two parts, (i) parts of $A$ that are not in $B$ and (ii) parts of $B$ that are not in $A$. If $A \triangle B \subset A$, then the (ii) parts must be empty or you have an immediate contradiction, and so $B \setminus A$ is empty. $\endgroup$ – copper.hat Jan 7 '15 at 19:04
  • $\begingroup$ Related : math.stackexchange.com/questions/344393/… $\endgroup$ – Arnaud D. Oct 26 '18 at 12:46

You are right that it is not possible for "$x$ [to be] be a member of $A$ and at the same time not be a member of $A$". That is in fact the point.

Assume $x\in B$. Then by the statement $(x \in B \land x \notin A ) \to x \in A$, if $x$ is not in $A$ then it is in $A$. That is a contradiction, so our hypothesis "$x$ is not in $A$" must be false. Therefore, $x\in A$.

That last paragraph shows $x\in B \implies x\in A$. Therefore, $B\subseteq A$. That is the very last statement of the argument.


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.