Answer to Question #136823 in Discrete Mathematics for Promise Omiponle

Question

Show that if A, B, C, and D are sets with |A|=|B| and|C|=|D|, then |AxC|=|BxD|.

Answer 1

The Cartesian product of two sets $X$ and $Y$, denoted $X\times Y$, is the set of all ordered pairs $(x,y)$ where $x$ is in $X$and $y$ is in $Y$, that is ${\displaystyle X\times Y=\{\,(x,y)\mid x\in X\ {\text{ and }}\ y\in Y\,\}.}$

Since $|A|=|B|$, there exists a bijection $f: A\to B$. By analogy, the equality $|C|=|D|$ implies that there exists a bijection $g: C\to D$. Let us prove that the map $h: A\times C\to B\times D$, $h(a,c)=(f(a), g(c))$, is a bijection as well.

First prove that $h$ is an injection. Let $h(a_1, c_1)=h(a_2, c_2)$. So $(f(a_1), g(c_1))=(f(a_2), g(c_2))$. It follows that $f(a_1)=f(a_2)$ and $g(c_1)=g(c_2)$. Since $f$ and $g$ are injections, $a_1=a_2$ and $c_1=c_2$. Therefore, $(a_1,c_1)=(a_2,c_2)$, and $h$ is an injection.

Finally, prove that $h$ is a surjection. Let $(b,d)\in B\times D$. Since $f$ and $g$ are surjections, there exist $a\in A$ and $c\in C$ such that $f(a)=b$ and $g(c)=d$. Then $h(a,c)=(f(a), g(c))=(b, d)$, and consequantly, $h$ is a surjection.

It follows that $h: A\times C\to B\times D$ is bijection, and therefore, $|A\times C|=|B\times D|$.