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 ?



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.


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.