# Reading, Writing, and Proving Math: Cartesian Product

The following is my attempt at one of my homework assignments.

Let A, B, and C be sets. If the statement below is true, prove it. If false, give a counter example.

A $\times$ (B $\cap$ C) = (A $\times$ B) $\cap$ (A $\times$ C).

I want to say this is true so I went about it as follows. To do this, I needed to show that they are subsets of each other.

Claim 1: A $\times$ (B $\cap$ C) $\subseteq$ (A $\times$ B) $\cap$ (A $\times$ C)

Let z $\in$ A $\times$ (B $\cap$ C) $\rightarrow$ z = (x,y) $\in$ A $\times$ (B $\cap$ C)

$\rightarrow$ x $\in$ A $\wedge$ y $\in$ (B $\cap$ C)

$\rightarrow$ x $\in$ A $\wedge$ (y $\in$ B $\wedge$ y $\in$ C)

$\rightarrow$ (x $\in$ A $\wedge$ y $\in$ B) $\wedge$ (x $\in$ A $\wedge$ y $\in$ C)

$\rightarrow$ (x,y) $\in$ A $\times$ B $\wedge$ (x,y) $\in$ A $\times$ C

$\rightarrow$ (x,y) $\in$ (A $\times$ B) $\cap$ (A $\times$ C)

Thus A $\times$ (B $\cap$ C) $\subseteq$ (A $\times$ B) $\cap$ (A $\times$ C)

Claim 2: (A $\times$ B) $\cap$ (A $\times$ C) $\subseteq$ A $\times$ (B $\cap$ C)

Let z $\in$ (A $\times$ B) $\cap$ (A $\times$ C) $\rightarrow$ z =(x,y) $\in$ (A $\times$ B) $\cap$ (A $\times$ C)

$\rightarrow$ (x,y) $\in$ (A $\times$ B) $\wedge$ (x,y) $\in$ (A $\times$ C)

Suppose (x,y) $\in$ (A $\times$ B)

$\rightarrow$ x $\in$ A $\wedge$ y $\in$ B

$\rightarrow$ x $\in$ A $\cap$ A $\wedge$ y $\in$ B $\cap$ C

$\rightarrow$ x $\in$ A $\wedge$ y $\in$ B $\cap$ C

$\rightarrow$ (x,y) $\in$ A $\times$ (B $\cap$ C)

Suppose (x,y) $\in$ (A $\times$ C)

$\rightarrow$ x $\in$ A $\wedge$ y $\in$ C

$\rightarrow$ x $\in$ A $\cap$ A $\wedge$ y $\in$ B $\cap$ C

$\rightarrow$ x $\in$ A $\wedge$ y $\in$ B $\cap$ C

$\rightarrow$ (x,y) $\in$ A $\times$ (B $\cap$ C)

Thus (A $\times$ B) $\cap$ (A $\times$ C) $\subseteq$ A $\times$ (B $\cap$ C)

Hence A $\times$ (B $\cap$ C) = (A $\times$ B) $\cap$ (A $\times$ C).

The only think I am not sure of is the second Claim. What makes me have doubts is the fact y can be in B but what if it is not in C. Then I thought, well doesn't y have to be in both to begin with. This is when I got confused.

-
By the way, I don't think it's a good idea to use the symbol "$\to$" ("implies") every time you want to say "therefore." The meaning of "Suppose $P \to Q$" is not the same as "Suppose $P$. Therefore $Q$" even if you put a period and a line break before the "$\to$". – Trevor Wilson Oct 26 '13 at 23:04

The first half of the argument is correct. The second isn’t quite correct as its written: the step from $x\in A\land y\in B$ to $x\in A\cap A\land y\in B\cap C$ needs to be justified, since up to that point you’ve not said that $y\in C$. I’d do it like this:

Let $z\in(A\times B)\cap(A\times C)$. Then $z=\langle x,y\rangle$ for some $x$ and $y$, and $\langle x,y\rangle\in A\times B$ and $\langle x,y\rangle\in A\times C$. Since $\langle x,y\rangle\in A\times B$, we know that $x\in A$ and $y\in B$; and since $\langle x,y\rangle\in A\times C$, we also know that $x\in A$ and $y\in C$. Since $y\in B$ and $y\in C$, we have $y\in B\cap C$, so $z=\langle x,y\rangle \in A\times(B\cap C)$, as desired.

Note that in general proofs are easier to read when written as prose — technical prose, to be sure, often with lots of mathematical symbols, but still prose — rather than as extended logical calculations.

-
Note that in general I definitely find calculations easier to read than prose. Note that I was taught by Dijkstra/Scholten/van Gasteren, Gries/Schneider, Back ("structured derivations" ), Hehner. – Marnix Klooster Oct 29 '13 at 5:52

You say "suppose $(x,y) \in A\times B$", but it's already in there by assumption if it's in $A\times B \cap A\times C$.

$→ x ∈ A ∧ y ∈ B \\ → x ∈ A ∩ A ∧ y ∈ B ∩ C$

This part here doesn't make sense.

What I would do is assume $(x,y) \in (A\times B) \cap (A\times C)$. Then $(x,y) \in A\times B$ and $(x,y) \in A\times C$. So $x \in A$ and $y \in B$ and $x\in A$ and $y \in C$ so $(x,y) \in A \times (B\cap C)$.

-

$(a,z)\in A\times (B\cap C)$ iff $a\in A$ and $z\in B\cap C.$

$z\in B\cap C$ iff $z\in B$ and $z\in C$.

$a\in A$ and $z\in B$ iff $(a,z)\in A\times B$.

$a\in A$ and $z\in C$ iff $(a,z)\in A\times C$.

$(a,z)\in A\times B$ and $(a,z)\in A\times C$ iff $(a,z)\in (A\times B) \cap (A\times C).$

-

This is not a comment on your proof but an alternative way to approach problems like this.

Here is yet another way to prove more easily, and more formally at the same time. Starting on the most complex side, we calculate which elements $\;p\;$ are in this set: just we expand the definitions and simplify, and then work back to our goal: \begin{align} & p \in (A \times B) \cap (A \times C) \\ \equiv & \;\;\;\;\;\text{"definition of $\;\cap\;$"} \\ & p \in A \times B \;\land\; p \in A \times C \\ \equiv & \;\;\;\;\;\text{"definition of $\;\times\;$, twice"} \\ & \text{ispair}(p) \land \text{fst}(p) \in A \land \text{snd}(p) \in B \;\land\; \text{ispair}(p) \land \text{fst}(p) \in A \land \text{snd}(p) \in C \\ \equiv & \;\;\;\;\;\text{"logic: simplify"} \\ & \text{ispair}(p) \;\land\; \text{fst}(p) \in A \;\land\; \text{snd}(p) \in B \land \text{snd}(p) \in C \\ \equiv & \;\;\;\;\;\text{"definition of $\;\cap\;$"} \\ & \text{ispair}(p) \;\land\; \text{fst}(p) \in A \;\land\; \text{snd}(p) \in B \cap C \\ \equiv & \;\;\;\;\;\text{"definition of $\;\times\;$"} \\ & p \in A \times (B \cap C) \end{align} By set extensionality this proves the original statement.

-