# Set theory proof with empty set

Prove that if $A \times B = A \times (C \setminus B)$

$then: A \times (B \bigcup C) = \emptyset$

I get that $B=(C\setminus B)$ so that means either C is an empty set or C and B have no element in common. (Striked text is probably wrong)

What can I do from here on ?

Thanks.

## 2 Answers

We do not necessarily have $B=C\setminus B$, for example we might have $A=\emptyset$ and $B,C$ arbitrary!

Instead, just try a proof of the contraposition:

Assume $A\times (B\cup C)\ne \emptyset$. Then there exists an element $z\in A\times (B\cup C)\ne \emptyset$ and this is of the form $z=(x,y)$ with $x\in A$ and $y\in B\cup C$.

• If $y\in B$ then $y\notin C\setminus B$, so we have $(x,y)\in A\times B$ and $(x,y)\notin C\setminus B$.
• If $y\notin B$, then from $y\in B\cup C$ we have $y\in C\setminus B$, so $(x,y)\notin A\times B$, but $(x,y)\in A\times(C\setminus B)$.

In both cases $(x,y)$ witnesses that $A\times B\ne A\times (C\setminus B)$.

In summary, $A\times (B\cup C)\ne \emptyset$ implies $A\times B\ne A\times (C\setminus B)$. In other words, $A\times B= A\times (C\setminus B)$ implies $A\times (B\cup C)= \emptyset$.

Let's try to simplify what you are given:

\begin{align} & A \times B \;=\; A \times (C \setminus B) \\ \equiv & \qquad \text{"set extensionality; definition of $\;\times\;$, twice"} \\ & \langle \forall x,y :: x \in A \land y \in B \;\equiv\; x \in A \land y \in C \setminus B \rangle \\ \equiv & \qquad \text{"logic: extract common conjunct from $\;\equiv\;$"} \\ & \langle \forall x,y : x \in A \Rightarrow (y \in B \;\equiv\; y \in C \setminus B) \rangle \\ \equiv & \qquad \text{"definition of $\;\setminus\;$"} \\ & \langle \forall x,y : x \in A \Rightarrow (y \in B \;\equiv\; y \in C \land y \not\in B) \rangle \\ \equiv & \qquad \text{"logic: simplify -- keeping an equivalence to allow next step"} \\ & \langle \forall x,y : x \in A \Rightarrow (y \in B \lor y \in C \;\equiv\; \text{false}) \rangle \\ \equiv & \qquad \text{"logic: un-extract common conjunct; $\;x \in A \land \text{false} \;\equiv\; \text{false}\;$"} \\ & \langle \forall x,y : x \in A \land (y \in B \lor y \in C) \;\equiv\; \text{false}) \rangle \\ \equiv & \qquad \text{"definition of $\;\cup\;$; definition of $\;\times\;$; definition of $\;\emptyset\;$"} \\ & A \times (B \cup C) \;=\; \emptyset \\ \end{align}

This completes the proof, and also proves the other direction.