Cardinality Of A Cartesian Product

May 2011
181
2
Hello,

I am having difficulty understanding why the cardinality of a Cartesian Product is simply the product of the cardinality of the individual sets involved in the Cartesian Product. As an attempt in trying to understand this, I supposed the set A x A, where A has n elements: I understand that 1 goes to 1, 1 goes to 2,..., and 1 goes to n, which can be stated as (1,1),(1,2),...,(1,n); furthermore, 2 goes to 1, 2 goes to 2,..., and 2 goes to n, which can be stated as (2,1), (2,2),...,(2,n). However, this train of thinking did not do an adequate job in elucidating this concept. Could someone please help?
 

Plato

MHF Helper
Aug 2006
22,507
8,664
I am having difficulty understanding why the cardinality of a Cartesian Product is simply the product of the cardinality of the individual sets involved in the Cartesian Product.
First, I will assume that you are considering only finite sets.

Look at the definition: \(\displaystyle A\times B=\{(x,y):\;x\in A~\&~y\in B\}\).
How many pairs are possible?
If the cardinality of \(\displaystyle A\) is \(\displaystyle |A|=n\) then there are only ways \(\displaystyle n\) to pick the \(\displaystyle x\) value of the pairs.
Likewise, there are only \(\displaystyle |B|=m\) ways to pick the \(\displaystyle y\) values in the pairs.

Thus \(\displaystyle |A\times B|=|A|\cdot|B|=nm\).

Example: \(\displaystyle \{a,s,d,f,g\}\times\{1,2,3\}\) contains \(\displaystyle 15\) pairs.

Now for infinite sets, things are more complicated.
 
Aug 2010
961
101
If you associate a number with each element of A you can lay out the elements of AXA as:

11, 12, 13, 14, …..
21, 22, 23, 24,…
…………

And then start counting on a diagonal starting from upper left: 11,21,12,31,22,13…. (1,2,,3,…)

Just something I remembered from an analysis text. Not sure I’m convinced.

EDIT: The reason I am not convinced is that if you started counting by row, you would never get past the first row.
 
Last edited: