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?
Best Answer
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.