1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\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.