# Cartesian product and intersection

Suppose that $A_1 \subset M_1$ and $A_2 \subset M_2$.

How to formally prove that $A_1\times A_2 = (A_1 \times M_2 )\cap(M_1\times A_2)$? It's easy to justify informally, I can see why it's true, but I have troubles with proving it rigorously.

Let's say $(x,y)\in A_1 \times A_2$. We need to show it belongs to $(A_1 \times M_2 )\cap(M_1\times A_2)$. And then consider $(x,y) \in (A_1 \times M_2 )\cap(M_1\times A_2)$ to show that $(x,y)\in A_1 \times A_2$.

So the first question that needs to be answered - what is $(A_1 \times M_2 )\cap(M_1\times A_2)$? It's the set of elements that are in both sets. A single element is actually a tuple $(x,y)$.

$(A_1 \times M_2 )=(A_1 \times A_2)\cup (A_1 \times M\setminus A_2)$.

$(M_1 \times A_2 )=(A_1 \times A_2)\cup (M_1\setminus A_1 \times A_2)$.

The intersection of two sets above is $A_1 \times A_2$. Not sure if that's rigorous enough. Maybe you could prove it in a more elegant way?

$A_1\subset M_1$ implies that $A_1\times A_2\subset M_1\times A_2$
$A_2\subset M_2$ implies that $A_1\times A_2\subset A_1\times M_2$
Combining this we find: $$A_1\times A_2\subset (A_1\times M_2)\cap (M_1\times A_2)$$
Conversely if $\langle x,y\rangle\in (A_1\times M_2)\cap (M_1\times A_2)$ then we find that $x\in A_1$ and $y\in A_2$ so that $\langle x,y\rangle\in A_1\times A_2$.
From this we conclude that also: $$(A_1\times M_2)\cap (M_1\times A_2)\subset A_1\times A_2$$