I am trying to prove whether the following claim is true or false.
Given sets $X, Y, Z$, is the following equality of sets true or false.
$$(X - Y) - Z = (X - Z) - Y \quad\text{ (where '$-$' denotes set difference). }$$
I believe the claim is true.
My thinking is that the set on the LHS is simply all those elements of X that are not in Y and not in Z. The set on the RHS is also all those elements of X that are not in Z and not in Y. For example, if X = {1,2,3,4,5}, Y = {1,2,3} and Z = {3,4} then (X - Y) - Z = {5} and (X - Z) - Y = {5} as well.
I am having trouble proving the claim formally though (perhaps I am overthinking the question or missing something obvious). If anyone could help me out, that would be great!
Thanks!
2 Answers
Hint:
Just write the difference of two sets $A$ and $B$ as intersection:
- $A \setminus B = A \cap \bar B$, where $\bar B$ means the complement of $B$.
Then it will be easy for you to prove your claim.
Indeed, the equivalence is true. But remember, we cannot prove it is true for all sets $A, B, C$ by citing only one example in which the equivalence is true. (On the other hand, we can prove a theorem false if we can provide a counterexample.)
We seek to prove that: $$(X - Y) - Z = (X - Z) - Y$$
I'll proceed by "element-chasing". We show that if $x$ is an element of the set on the left-hand side, then x is an element of the set on the right-hand side, and vice-versa. In fact, we can do this strictly through bidirectional implications, so in the end, we can show that if $x$ is an element of the RHS, it is also an element of the LHS, as well.
\begin{align} x \in \Big((X-Y)-Z\Big) &\iff \Big(x \in (X-Y) \land x\notin Z)\Big)\tag{Def: setminus}\\ \\ &\iff \Big((x \in X \land x \notin Y) \land x\notin Z\Big) \tag{Def: setminus}\\ \\ &\iff \Big(x\in X \land (x \notin Y \land x\notin Z)\Big)\tag{associativity of $\land$}\\ \\ &\iff \Big(x \in X \land (x\notin Z \land x\notin Y)\Big)\tag{commutativity of $\land$}\\ \\ &\iff \Big((x\in X \land x\notin Z) \land x\notin Y\Big)\tag{associativity of $\land$}\\ \\ &\iff \Big( x\in (X-Z) \land x\notin Y\Big)\tag{Def: setminus}\\ \\ &\iff x \in \Big((X-Z)- Y\Big)\tag{Def: setminus} \end{align}
Hence, $(X-Y)-Z = (X-Z)-Y$
