2
$\begingroup$

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. :)

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Mees de Vries Jan 19 '17 at 13:24
  • $\begingroup$ @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? $\endgroup$ – Alfie Jan 19 '17 at 13:27
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So is this question asking for a formula for the carnality of the cartesian product of $A_1, A_2,\dotsc , A_n$ ? $\endgroup$ – Alfie Jan 19 '17 at 13:51
  • $\begingroup$ Yes. ____________ $\endgroup$ – Paolo Leonetti Jan 19 '17 at 13:52
  • $\begingroup$ So $\prod_{1\le i\le n}|A_i| $= $|A_1| * |A_2| * \dotsc * |A_n|$ $\endgroup$ – Alfie Jan 19 '17 at 13:57
  • 1
    $\begingroup$ @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 $\endgroup$ – Paolo Leonetti Jan 19 '17 at 14:56
  • 1
    $\begingroup$ @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 $\endgroup$ – Paolo Leonetti Jan 19 '17 at 16:00
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is exact, but I think the OP was asked a formula, but not asked to prove it. $\endgroup$ – Jean Marie Jan 19 '17 at 14:46
  • $\begingroup$ @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? $\endgroup$ – Bram28 Jan 19 '17 at 14:52
  • $\begingroup$ @JeanMarie: Agree. I deleted the answer. But I though it can be useful. $\endgroup$ – Cristhian Gz Jan 19 '17 at 14:53
  • $\begingroup$ @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 $\endgroup$ – Cristhian Gz Jan 19 '17 at 14:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.