# How to express the cardinality of $∏_{1≤i≤n} A_i$ in terms of cardinalities $|A_1|, |A_2|, . . . , |A_n|$

I was given the problem:

For finite sets $A_1, A_2,\dotsc , A_n$ define their Cartesian product $\prod_{i=1}^n A_i$ as the set of all $n$-sequences $(x_1, x_2,\dotsc, x_n)$, where $x_i \in A_i$ for every $i = 1, 2, \dotsc, n$. Find a formula expressing the cardinality of $\prod_{i=1}^n A_i$ in terms of cardinalities $|A_1|, |A_2|,\dotsc , |A_n|$.

And I am struggling to understand what it is actually asking for, could someone explain it to me please, thanks. :)

• Do you know what the Cartesian product is? For instance, if $A_1 = \{1,2\}$ and $A_2 = \{3,4,5\}$ could you explicitly write down $\prod_{1 \leq i \leq 2} A_i$? – Mees de Vries Jan 19 '17 at 13:24
• @MeesdeVries This is all prossible combinations right? So for that example {(1,3), (2, 3), (1, 4) ....}, But I have never seen the notation: ∏ 1≤i≤n Ai before, what does that mean? – Alfie Jan 19 '17 at 13:27

$\prod_{1\le i\le n}A_i$ is the cartesian product, that is, all finite sequences $(a_1,\ldots,a_n)$ such that $a_i \in A_i$ for each $i=1,\ldots,n$. How many such sequences can you choose? $|A_1|$ choices for $a_1$, ..., $|A_n|$ choices for $a_n$. Therefore $$\left|\prod_{1\le i\le n}A_i\right|=\prod_{1\le i\le n}|A_i|.$$

• So is this question asking for a formula for the carnality of the cartesian product of $A_1, A_2,\dotsc , A_n$ ? – Alfie Jan 19 '17 at 13:51
• Yes. ____________ – Paolo Leonetti Jan 19 '17 at 13:52
• So $\prod_{1\le i\le n}|A_i|$= $|A_1| * |A_2| * \dotsc * |A_n|$ – Alfie Jan 19 '17 at 13:57
• @Bram28 Assuming the axiom of choice, multiplication of infinite cardinal numbers is not difficult. If either $\kappa$ or $\mu$ is infinite and both are non-zero, then $\kappa \cdot \mu= \max\{\kappa, \mu\}$. In particular, $\kappa^n=\kappa$ for all $n\ge 1$. See here: en.wikipedia.org/wiki/Cardinal_number – Paolo Leonetti Jan 19 '17 at 14:56
• @Bram28 Well, you can find the answer in every introduction about cardinal arithmetics. Take a look here math.uchicago.edu/~may/VIGRE/VIGRE2009/REUPapers/Murphy.pdf and here euclid.colorado.edu/~monkd/m6730/gradsets06.pdf – Paolo Leonetti Jan 19 '17 at 16:00

We know that $$|A\times B|=|A|\times|B|\qquad(1)$$.

We want to show $$\left|\prod_{i=1}^nA_i\right|=\prod_{i=1}^n|A_i|$$ is true for any natural number $n$, where $\prod_{i=1}^n|A_i|=|A_1|\times|A_2|\times\dotsc\times|A_n|$. So, we have use induction.

The base case $n=1$ ($|A_1| = |A_1|$) is trivial. Now suppose inductively that $\left|\prod_{i=1}^nA_i\right|=\prod_{i=1}^n|A_i|$. We want to show $$\left|\prod_{i=1}^{n+1}A_i\right|=\prod_{i=1}^{n+1}|A_i|.$$ Now we need to show $$\left|\prod_{i=1}^{n+1}A_i\right|=\left|\left(\prod_{i=1}^nA_i\right)\times A_{n+1}\right|\qquad(2),$$ i.e., the cardinality of the set $\prod_{i=1}^{n+1}A_i$ is equal to the cardinality of the set $\left(\prod_{i=1}^nA_i\right)\times A_{n+1}$. So \begin{aligned}\left|\prod_{i=1}^{n+1}A_i\right|&=&\left|\left(\prod_{i=1}^nA_i\right)\times A_{n+1}\right|&\qquad\text{by }(2)\\&=&\left|\prod_{i=1}^nA_i\right|\times |A_{n+1}|&\qquad\text{by }(1)\\&=&|A_1|\times|A_2|\times\dotsc\times|A_n|\times|A_{n+1}|&\qquad\text{by induction hypothesis}\\&=&\prod_{i=1}^{n+1}|A_i|.\end{aligned}

• This is exact, but I think the OP was asked a formula, but not asked to prove it. – Jean Marie Jan 19 '17 at 14:46
• @CristianGz Do you know if (1) also holds for infinities? If so, how am I to think about multiplying 'infinities'? Is there a definition for that? – Bram28 Jan 19 '17 at 14:52
• @JeanMarie: Agree. I deleted the answer. But I though it can be useful. – Cristhian Gz Jan 19 '17 at 14:53
• @Bram28, the statement is true to infinite sets. It is possible using bijective functions to state equal cardinality between two sets. Check en.m.wikipedia.org/wiki/Cardinality – Cristhian Gz Jan 19 '17 at 14:55