1

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

https://proofwiki.org/wiki/Cardinality_of_Cartesian_Product

k9b
  • 319
  • 1
  • 11
  • The existence of $A\times B$ does not imply $|A| = |B|$. The Cartesian product $A\times B $ is well-defined in the case $|A|\neq |B|$, – amWhy Nov 11 '14 at 16:53

2 Answers2

2

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.

Cameron Buie
  • 102,994
1

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

Matt Samuel
  • 58,164