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!



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$



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.


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.