Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have: $$\prod_{i\in I}{X_i}=\left\{f:I\to\bigcup_{i\in I}{X_i}~\Big|~ (\forall i\in I)\big(f(i)\in X_i\big)\right\}$$

Is it true: $$\left|\prod_{i\in I}{X_i^2}\right|=\left|\left(\prod_{i\in I}{X_i}\right)^2\right|$$

and can we assume: $$\prod_{i\in I}{X_i^2}=\left(\prod_{i\in I}{X_i}\right)^2$$

share|improve this question
    
Can you prove that in general $|AB|=|A||B|$? –  Gerry Myerson Feb 13 '13 at 5:02
    
@GerryMyerson: if $AB=A\times B$ that's true. –  user59671 Feb 13 '13 at 5:13
    
So, can you use it to answer the questions? –  Gerry Myerson Feb 13 '13 at 5:19
add comment

3 Answers 3

up vote 2 down vote accepted

It is not literally true that

$$\prod_{i\in I}{X_i^2}=\left(\prod_{i\in I}{X_i}\right)^2\;:$$

elements of the lefthand side are functions with domain $I$ such that $f(i)\in X_i\times X_i$ for each $i\in I$, while elements of the righthand side are ordered pairs of functions with domain $I$ such that $f(i)\in X_i$ for each $i\in I$. However, there is a natural bijection between the two sets, and the existence of that bijection proves that they have the same cardinality.

Specifically, for any

$$\langle f,g\rangle\in\left(\prod_{i\in I}{X_i}\right)^2$$

we define a unique $$h_{f,g}\in\prod_{i\in I}{X_i^2}$$

by

$$h_{f,g}(i)=\big\langle f(i),g(i)\big\rangle\;.$$

I leave it to you to verify that the map

$$\varphi:\left(\prod_{i\in I}{X_i}\right)^2\to\prod_{i\in I}{X_i^2}:\langle f,g\rangle\mapsto h_{f,g}$$

is a bijection.

share|improve this answer
    
I can't believe that I didn't see this sooner. Yes, I guess that working all night gets to me at some point (usually when there's sunlight...). You made me question my decision to sit and write the details of a new idea right now... I think I'll choose sleep instead. –  Asaf Karagila Feb 13 '13 at 5:24
    
@Asaf: Sleep tight, don’t let the bedbugs bite! :-) –  Brian M. Scott Feb 13 '13 at 5:26
add comment

In the context where the variables in the question stand for sets, one way to prove the equality of cardinalities will be to construct a bijection. This approach will be a bit messy, but not too much. Another approach will be to recall that the categorical product in $Set$, the category of sets, is the product construction at hand. As in any category, the categorical product is associative and commutative up to isomorphism (and even coherently, though this is not important for this answer). That means that you can rearrange the terms in each product to get the other and be assured that there is an isomorphism between the two. Viewed this way, the equality of cardinalities is a by-product of a much stronger property of the cartesian structure of $Set$, which in turn is automatic from the universal property of cartesian products.

share|improve this answer
    
Bijections are almost usually are messy. But finding injections is simpler. –  Asaf Karagila Feb 13 '13 at 5:20
1  
It isn’t at all messy: there’s an obvious, canonical bijection. (And from my point of view the category theory is the reverse of illuminating.) –  Brian M. Scott Feb 13 '13 at 5:25
1  
Well, I can't really argue with this, but I am sure that you are aware that even canonical arguments have to be reversed. And if you write down the details (as one has to at least once) you end up with Brian's answer (or mine, if you're very tired); on the other hand appealing to universal properties is usually confusing and obfuscating the little structure carried by sets. –  Asaf Karagila Feb 13 '13 at 5:26
1  
@BrianM.Scott I did say "a bit messy" ;) + Asaf Karagile, using the definition of categorical products (which is just slightly more complicated than the definition of the cartesian products of a family of sets) you can prove a canonical bijection exists without building it at all. And while I'm advocating category theory more than I'd like already (since I don't want to start a fight, really) I must in a very friendly way disagree with the claim that universal properties are confusing. I honestly think there is nothing simpler than universality. E.g., proving associativity of tensor prdcts. –  Ittay Weiss Feb 13 '13 at 5:31
1  
It’s not that they’re confusing per se; they just don’t get into the guts of the machinery, so I consider them less fundamental and generally find them much less satisfying. (I also rather doubt that they’re generally likely to be useful to someone asking this particular question, though I’m sure that they sometimes are.) –  Brian M. Scott Feb 13 '13 at 5:42
show 3 more comments

As sets these are different sets. One set is a set of functions, and the other is a set of ordered pairs of functions.

To see that the cardinality is equal, note that:

  1. If $I$ is finite then this is really just by definition of cardinal multiplication.

  2. If $I$ is infinite (and without loss of generality no $X_i$ is a singleton or empty) then: $$\left|\prod_{i\in I}X_i\right|^2=\left|\prod_{i\in I}X_i\right|\leq\left|\prod_{i\in I}X_i^2\right|\leq\left|\left(\prod_{i\in I}X_i\right)^2\right|$$ To see the last inequality note that $f(i)=\langle a_i,b_i\rangle$ factors into $\langle a,b\rangle$ which are choice functions, and this is an injective function.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.