# How to prove $\forall Y \subset X \ \forall U \subset X \ (Y \setminus U = Y \cap (X \setminus U))$?

How to prove that $$\forall Y \subset X \qquad \forall U \subset X \qquad(Y \setminus U = Y \cap (X \setminus U))$$

Intuitively it has something to do with the way $2^X$ models Boolean algebra, but I can't make a precise argument. Any hint?

-

If $y \in Y \setminus U$, then $y \in Y$ but $y \notin U$, so $y \in Y$ and $y \in X \setminus U$.

Conversely, if $y \in Y$ and $y \in X \setminus U$, then $y \notin U$ so $y \in Y \setminus U$.

Better: draw a Venn diagram.

-

We want to establish the following equality:

$$\forall Y \subset X, \qquad \forall U \subset X, \qquad(Y \setminus U = Y \cap (X \setminus U))$$

To establish the equality of the sets on the LHS and RHS, it is sufficient to show that each set is a subset of the other. That is,

$$(Y\setminus U) \subset (Y \cap (X\setminus U)) \land (Y \cap (X\setminus U)) \subset (Y\setminus U) \implies (Y \setminus U) = (Y \cap (X \setminus U))$$

First inclusion:

Suppose $y \in Y\setminus U$. Then $y \in Y$ (so $y\in X)$ but $y \notin U.\quad$ (Note: $y \in X$ follows from $y \in Y \land Y\subset X.)\quad$ That is, $(y \in Y) \land (y \in X) \land (y \notin U).$ Since conjunction is associative, we have $y \in Y \land (y \in X \land y \notin U).\quad$ Equivalently, $y \in Y \cap (X \setminus U)$.
Therefore, $$(Y\setminus U) \subset (Y\cap (X\setminus U)).\qquad (1)$$

For the other inclusion:

Suppose $y \in Y\cap (X\setminus U)$. Then $y \in Y$, and $y \in X \setminus U$; that is, $y \in Y \land (y \in X \land y \notin U)$, and hence, given that $y \in Y \implies y \in X$ (since $Y\subset X$), the conjunct $y \in X$ is superfluous. Hence, $y \in Y \land y \notin U$. That is, $y \in (Y \setminus U)$. Therefore, $$(Y \cap (X \setminus U))\subset (Y\setminus U).\qquad (2)$$

By both inclusions (1) and (2), we have that $$(Y \setminus U) = Y \cap (X \setminus U))$$

Note: When one wants to prove the equality of two sets, e.g. for sets A and B, to show $A = B$, a good way to proceed is by showing that $A \subset B$, and that $B \subset A$.

I've simply made the establishment of those inclusions explicit.

-

Hint: what is the definition of $Y \setminus U$?

-

Since we're asked to prove $\;Y \setminus U = Y \cap (X \setminus U)\;$ under certain conditions, it seems simplest to try and simplify the right hand side to the left hand side. I find this is most easily done at the element level: for every $\;y\;$, \begin{align} & y \in Y \cap (X \setminus U) \\ \equiv & \;\;\;\;\;\text{"expand the definitions of $\;\cap\;$ and $\;\setminus\;$"} \\ & y \in Y \land y \in X \land y \not\in U \\ \equiv & \;\;\;\;\;\text{"using condition $\;Y \subset X\;$, which by definition is equivalent} \\ & \;\;\;\;\;\phantom{"}\text{to $\;y \in Y \Rightarrow y \in X\;$ for any $\;y\;$, which by logic is equivalent} \\ & \;\;\;\;\;\phantom{"}\text{to $\;y \in Y \equiv y \in Y \land y \in X\;$ for any $\;y\;$} \\ & \;\;\;\;\;\phantom{"}\text{-- since we want to remove $\;X\;$ which is not on the left hand side"} \\ & y \in Y \land y \not\in U \\ \equiv & \;\;\;\;\;\text{"reintroduce $\;\setminus\;$ using its definition"} \\ & y \in Y \setminus U \\ \end{align} By set extensionality (i.e., equal sets have the same elements) this completes the proof.

Note that the condition $\;U \subset X\;$ was not used in this proof.

-