How does one go about proving that the set-theoretic difference operation $\setminus$ cannot be defined through the operations $\cap$ and $\cup$?
My thoughts: I first assumed $A$ and $B$ are two non-disjoint non-empty sets since if they are disjoint and non-empty, then we have that $A\setminus B= A =A\cap A=(A\cap B) \cup A$. Therefore we have defined, in this case, $\setminus$ in terms of $\cap$ and $\cup$.
Next, I drew three Venn diagrams for $A\cap B $, $A\cup B $ and $A\setminus B $ and made the observation that $A \setminus B$ involves an exclusion of a part of $A$. When I looked at the definitions, I could see this clearer:
$$A\cap B = \{x\mid (x\in A) \land (x\in B)\}$$
$$A\cup B = \{x\mid (x\in A) \lor (x\in B)\}$$
$$A\setminus B = \{x\mid (x\in A) \land \mathbf{(x\notin B)}\}$$
From this, I decided to conclude that since the intersection and union operations have the condition that $(x\in B)$ whereas the set difference operation requires $(x\notin B)$, we cannot define set difference through the operations union and intersection only.
This is as far as I could go. How can I prove this formally?
Best Answer
The union and intersection operators are monotone. If $A\subseteq A'$ and $B\subseteq B'$ then $A\cup B\subseteq A'\cup B'$ and $A\cap B\subseteq A'\cap B'$. If $f(A,B)$ is a formal combination of $A$s and $B$s with unions and intersections, then it is monotone: $f(A,B)\subseteq f(A',B')$ under the above assumptions. But $A\setminus B$ is not a monotone operation.