How to prove that the set-theoretic difference operation $\setminus$ cannot be defined through $\cap$ and $\cup$

Question

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?

Answer 1

All you need is a counterexample.

Let $A = B = \{ 0 \}$. Then all of the sets $$A,~ B,~ A \cup A,~ A \cap A,~ A \cup B,~ A \cap B,~ B \cup A,~ B \cap A,~ B \cup B,~ B \cup B$$ are equal to $\{ 0 \}$, and so any set built out of $A$, $B$ and the operations $\cup$ and $\cap$ is equal to $\{ 0 \}$.

But $B \setminus A = \varnothing \ne \{ 0 \}$, and so the set difference operator $\setminus$ can't be expressed in terms of $\cup$ and $\cap$ alone.

Answer 2

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.