2
$\begingroup$

The problem I am given is:

Let $Y$ and $Z$ be subsets of $X$. Prove that

$(X \setminus Y)\cap Z=Z \setminus(Y \cap Z)$

Things I have tried:

  1. Drew pictures.

  2. Looked up how to show set equality and it said the standard way is to show that each side is a subset of the other. The source I have been using is: https://www.people.vcu.edu/~rhammack/BookOfProof/SetProofs.pdf

Proof:

We must show that:

  1. $(X \setminus Y)\cap Z \subset Z \setminus(Y \cap Z)$

  2. $Z \setminus(Y \cap Z) \subset (X \setminus Y)\cap Z$

First, showing that $(X \setminus Y)\cap Z \subset Z \setminus(Y \cap Z)$:

Suppose $x \in \left( (X \setminus Y) \cap Z\right)$.

Then $x \in X, x \notin Y, $ and $x \in Z$. (This is where I get stuck. Not sure what to do next.)

$\endgroup$
  • 2
    $\begingroup$ One thing that may help: $Z\setminus (Y\cap Z)=Z\setminus Y$. $\endgroup$ – Clayton Jan 19 '18 at 19:18
  • $\begingroup$ @Clayton , How do you know that $Z\setminus (Y\cap Z)=Z\setminus Y$? $\endgroup$ – LovesPeanutButter Jan 26 '18 at 22:31
2
$\begingroup$

I know the other answers are shorter, but I wanted to finish it the same way you started.

Assume $x\in (X\setminus Y)\cap Z$. Then $x\in X,x\notin Y,x\in Z$. Now, since $x\notin Y$ we have that $x\notin Y\cap Z$. Since $x\in Z$ and $x\notin Y\cap Z$, it is clear that $x\in Z\setminus (Y\cap Z)$.

Therefore $(X\setminus Y)\cap Z\subseteq Z\setminus (Y\cap Z)$.

Assume $x\in Z\setminus (Y\cap Z)$. Then $x\in Z$, and either $x\notin Y$ or $x\notin Z$. But we already know $x\in Z$, so $x\notin Y$. Since $Z\subseteq X$ and $x\in Z$, we know $x\in X$. Since $x\in X$ and $x\notin Y$, we know $x\in X\setminus Y$. Since $x\in Z$ and $x\in X\setminus Y$, we have $x\in (X\setminus Y)\cap Z$.

Therefore $Z\setminus (Y\cap Z)\subseteq (X\setminus Y)\cap Z$.

And so we conclude $(X\setminus Y)\cap Z= Z\setminus (Y\cap Z)$

$\endgroup$
  • $\begingroup$ When you say "Assume $x\in Z\setminus (Y\cap Z)$. Then $x\in Z$, and either $x\notin Y$ or $x\notin Z$." Since it's the intersection of $Y$ and $Z$, would it be the case that $x\notin Y$ AND $x\notin Z$? Instead of or? $\endgroup$ – LovesPeanutButter Jan 22 '18 at 18:31
  • 1
    $\begingroup$ No. By definition of set subtraction, we know that $x\notin (Y\cap Z)$. Then $x\in (Y\cap Z)'$ and applying DeMorgan's Law gives us $x\in (Y'\cup Z')$. Therefore, $x\in Y'$ or $x\in Z'$, i.e. $x\notin Y$ or $x\notin Z$. $\endgroup$ – Riley Jan 22 '18 at 19:14
  • $\begingroup$ What do you mean by "Then $x\in (Y\cap Z)'$"? $\endgroup$ – LovesPeanutButter Jan 26 '18 at 22:51
  • $\begingroup$ $(Y\cap Z)'$ is the complement of $Y\cap Z$. Perhaps you learned a different notation. $\endgroup$ – Riley Jan 27 '18 at 0:50
3
$\begingroup$

I like to element chase.

$x \in X\setminus Y \cap Z$ means $x \in X; x \not \in Y; x \in Z$. So $x \not \in Y\cap Z$ but $x \in Z$ so $x \in Z\setminus (Y\cap Z)$.

So $X\setminus Y \cap Z\subset Z\setminus (Y\cap Z)$

Likewise if $x \in Z\setminus (Y\cap Z)$, then $x \not \in Y\cap Z$ and $x \in Z$. If $x \in Y$ then $x \in Y\cap Z$ which it is not. So $x \not \in Y$ So $x \in X\setminus Y$. And $x \in Z$ so $x \in X\setminus Y \cap Z$

So $Z\setminus (Y\cap Z)\subset X\setminus Y \cap Z$.

=====

Also not sure why pictures didn't help:

This is the picture of $X\setminus Y$ (in pink):

enter image description here

And this is the picture of $(X\setminus Y) \cap Z$ (in lavender):

enter image description here

And this is a picture of $Z\cap Y$ (in yellow):

enter image description here

And this is a picture of $Z \setminus (Y\cap Z)$ (in lavender):

enter image description here

$\endgroup$
  • $\begingroup$ How did you generate these venn diagrams? $\endgroup$ – LovesPeanutButter Jan 19 '18 at 19:54
  • $\begingroup$ I used photoshop. $\endgroup$ – fleablood Jan 20 '18 at 17:04
2
$\begingroup$

$(X \backslash Y) \cap Z = \{a \in X : a \notin Y\} \cap Z = \{a \in X : a \in Z, a\notin Y\}$

$Z \backslash (Y \cap Z) = \{a \in X : a \in Z, a \notin (Y \cap Z)\} = \{a \in X : a \in Z, a \notin Y\}$

The last transition uses the fact that $a \in Z$ and $a \notin Y \cap Z$ is equivalent to $a \in Z$ and $a \notin Y$.

$\endgroup$
  • $\begingroup$ On the second line: $Z \backslash (Y \cap Z) = \{a \in X : a \in Z, a \notin (Y \cap Z)\} = \{a \in X : a \in Z, a \notin Y\}$ How do you know that $a \in X$? $\endgroup$ – LovesPeanutButter Jan 19 '18 at 20:08
  • 1
    $\begingroup$ @LovesLinearAlgebra $Z$ is a subset of $X$. $\endgroup$ – idok Jan 19 '18 at 22:44
1
$\begingroup$

$Z\setminus (Y\cap Z)=Z\cap(Y\cap Z)'=Z\cap (Y'\cup Z')=(Z\cap Y')\cup (Z\cap Z')=Z\cap Y'=Z\cap(X\setminus Y)$

$\endgroup$
1
$\begingroup$

You just need to continue reasoning. From $x\notin Y$, you can conclude that $x\notin Y\cap Z$. Now you know that $x\in Z$ and $x\notin Y\cap Z$, which precisely means that $x\in Z\setminus(Y\cap Z)$.

For the inverse direction, either start again, or look at the solution above to see if all logical connections can be treated as "if and only if". (I'm not saying that that's the case; just giving some ideas to think about.)

$\endgroup$
1
$\begingroup$

In order to show that $$(X \setminus Y)\cap Z \subset Z \setminus(Y \cap Z)$$ We pick an arbitrary element of the left side and show that it is as element of the right side.

If $x$ is such an element, then $x$ is in $Z$ and $x$ is not in $Y$. Since it is not in $Y$ it is not in $ (Y \cap Z)$ thus it is in $ Z \setminus(Y \cap Z)$

In order to show $$ Z \setminus(Y \cap Z) \subset (X \setminus Y)\cap Z$$

We pick an arbitrary element of the left side and show that it is as element of the right side.

If $x$ is such an element , then $x$ is in $Z$ and $x$ is not in $(Y \cap Z)$, therefore $x$ is not in $Y$ which makes it an element of $(X\setminus Y)$.

Since it is in $Z$ and it is in $(X\setminus Y)$, it is in the intersection of the two sets which is exactly $(X\setminus Y)\cap Z$

$\endgroup$

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.