Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

Thanks for taking the time to read the post. Thanks in advanced for your feedback.

share|cite|improve this question
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.

share|cite|improve this answer
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)$.

share|cite|improve this answer

$(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).$

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.