Logic Laws and Sets

Question

Is $(A∩B)×C=(A×C)∩(B×C)$ true for all sets $A$, $B$ and $C$? If so, prove it. If not, give an example of sets $A$, $B$ and $C$ for which it is false.

Use laws of logic to show that they do/do not have exactly the same elements?

Not really sure how to apply laws of logic to sets...

Answer 1

Definitions: $${X\cap Y:=\{z: z\in X\wedge z\in Y\}\\X\times Y := \{(x,y):x\in X\wedge y\in Y\}}$$ Alternatively (and equivalenetly) $${\forall z~(z\in X\cap Y\leftrightarrow ( z\in X\wedge z\in Y))\\\forall x~\forall y~((x,y)\in X\times Y \leftrightarrow (x\in X\wedge y\in Y))}$$

So, your task is to use the laws of logic to demonstrate whether $(A\cap B)\times C$ and $(A\times C)\cap( B\times C)$ have exactly the same contents.

$$\begin{align}(A\cap B)\times C &=\{(u,v): u\in (A\cap B)\wedge v\in C\} \\&~\ddots\\[3ex](A\times C)\cap( B\times C) &=\{(u,v): (u,v)\in (A\times C)\wedge (u,v)\in (B\times C)\} \\&~\ddots\end{align}$$

Answer 2

For sets $X$ and $Y$, $X=Y\iff \forall z.(z\in X\Leftrightarrow z\in Y)$. So the equation in your question holds if for all $z$, $$z\in (A\cap B)\times C\iff z\in(A\times C)\cap(B\times C)$$

This is the logical statement that you need to either prove or refute. You can use the defining equivalences of the set-theoretic operations, like $z\in A\cap B\iff z\in A\land z\in B$, to further reduce this. Eventually all set-theoretic constructions will be reduced away and you'll have a formula consisting only of propositions like $z\in A$ for an arbitrary set $A$. You can just treat those as atomic propositions and your question will be a propositional formula in terms of these atomic propositions. If you can prove the resulting propositional formula, then the original equation holds. If you can refute it, then you can actually use that refutation to build a counter-example, but it may be easier to just intuitively think up a counter-example, and then verify that it is indeed a counter-example.