Cardinality with Cartesian Cross Product problem

$\begingroup$

A and B are finite sets

Prove that |AxB| = |A||B|.

I need a solution/hint.

I suspect that the answer has to do with the fact that the we can say that |A| = |B| and then from that say = |AxB|. I think I have a solution for it, but I just wanted to make sure I am understanding the proof right

$\endgroup$ 1

2 Answers

$\begingroup$

Note that for each $a\in A,$ the set $\{a\}\times B$ has cardinality $|B|.$ (Why?) Further note that the sets $\{a\}\times B$ (where $a\in A$) comprise a partition of $A\times B.$ Hence, since there are $|A|$ elements of $A,$ we have $$|A\times B|=\left|\bigcup_{a\in A}\{a\}\times B\right|=\sum_{a\in A}\bigl|\{a\}\times B\bigr|=\sum_{a\in A}|B|=|A||B|.$$

Observe that this never assumes that $|A|=|B|,$ and applies for any sets $A,B,$ regardless of cardinality. An example for you to consider is when $A=\{x,y\}$ and $B=\{1,2,3\}.$ You should be able to find $A\times B$ explicitly, and see that it has $6$ elements.

$\endgroup$ $\begingroup$

Suppose $A$ has $m$ elements and $B$ has $n$. For ordered pairs $(a,b)$ there are $m$ possibilities for $a$, and for each of these there are $n$ possibilities for $b$. Summing over all $a$ we get the result is $mn$.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy