Logic error in proving that $(A\times{B})\cap{(C\times{D})} = (A\cap{C})\times{(B\cap{D})}$

Question

I had a question about this proof, I sort of know intuitively how to do it but it's not aligning with my understanding of how logic works. My first part of the proof goes as followed...

($\longrightarrow$) Suppose that for some arbitrary $p$ that $p=(x,y)\in{(A\times{B})\cap{(C\times{D}})}$ then clearly $p\in{(A\times{B})}$ and $p\in{(C\times{D})}$, for some $x$, $x\in{A}$ and $x\in{C}$ and $y\in{B}$ and $y\in{D}$. It follows that $x\in{A\cap{C}}$ and $y\in{B\cap{D}}$. So, $p\in{(A\cap{C})\times{(B\cap{D})}}$ and $(A\times{B})\cap{(C\times{D}})\subseteq{(A\cap{C})\times{(B\cap{D})}}$

But, this breaks the rule of existential instantiation. How can I instantiate to $x$ both times (same with $y$)? Does it have something to do with $p$? I am saying this because the chapter states that "...$p\in{A\times{(B\cap{C})}}$ means that $\exists{x}\exists{y}({x\in{A}\land{y\in{B\cap{C}}\land{p=(x,y)}})}$" which means that I am existentially instantiating when I take the $x$ and $y$ of the cross product. So in my case wouldn't it be $\exists{x}\exists{y}({x\in{A}\land{y\in{B}\land{p=(x,y)}})} \land \exists{x}\exists{y}({x\in{C}\land{y\in{D}\land{p=(x,y)}})}$?

Answer 1

Did you notice that you introduced $x$ and $y$ before you “instantiated” them? That’s sloppy writing. If you really want to be careful about the instantiation and the like, you can’t be that sloppy: trying to be both careful and sloppy at the same time will make your head hurt.

Instead, if you want to be really, really careful there: take $p\in (A\times B)\cap (C\times D)$. Then $p\in (A\times B)$ and $p\in (C\times D)$.

By virtue of $p\in (A\times B)$ you know that there exists $a\in A$ and $b\in B$ such that $p=(a,b)$; couple of instantiations there.

By virtue of $p\in (C\times D)$ you know that there exists $c\in C$ and $d\in D$ such that $p=(c,d)$; different instantiations here.

By virtue of $(a,b)=p=(c,d)$, you conclude that $(a,b)=(c,d)$. Therefore, by the defining property of the ordered pair, we conclude that $a=c$ and $b=d$.

But then $a=c\in A\cap C$ (since $a\in A$ and $c\in C$ and $a=c$), and likewise $b=d\in B\cap D$. Thus, $(a,b)=(c,d)\in (A\cap C)\times (B\cap D)$. So $p=(a,b)=(c,d)\in (A\cap C)\times (B\cap D)$, as desired.

Alternatively, having decided that $p$ will be written a $(x,y)$ (though you would want to justify that), you can then conclude from $p\in A\times B$ that there exists $a\in A$, $b\in B$ with $(x,y)=(a,b)$, so $x=a\in A$, $y=b\in B$; do the same with $p=(c,d)$, and conclude that $x\in A$, $x\in C$, $y\in B$, $y\in D$, etc.

However, most of the time we just say that since $p\in (A\times B)$ and $p\in (C,D)$, we can write it as an ordered pair in which the first entry is in both $A$ and $C$, and the second entry is in both $B$ and $D$ (summarizing a couple of paragraphs above), and go from there. So most of the time your first paragraph is perfectly acceptable, because it is clear how the conclusions are being reached and it is a fairly standard “abuse of language” typical in a proof.