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.

Let $\{B_i\}_{i\in I}$ and $\{C_i\}_{i\in I}$ be families of sets. If $B_i$ is in one-to-one correspondence with $C_i$ for each $i\in I$, $\prod B_i$ is in one-to-one correspondence with $\prod C_i$.

share|improve this question
1  
That's true. Do you have a question? –  Chris Eagle May 3 '12 at 16:40
add comment

2 Answers

up vote 2 down vote accepted

Let $f_i\colon B_i\to C_i$ be a one-to-one correspondence.

Recall that if $I$ is an index, and $\{A_i\}_{i\in I}$ is a family of sets, then $$\prod_{i\in I}A_i = \left.\left\{\strut f\colon I\to \cup A_i\,\right| f(i)\in A_i\text{ for each }i\in I\right\}.$$

Intuitively, you want to define $\mathbf{g}\colon\prod B_i\to\prod C_i$ by saying: "given $f\in\prod B_i$, let $\mathbf{g}(f)$ be the function that takes $i$, maps it to $f(i)$, and then uses $f_i$ to send $f(i)$ to $C_i$. This will give me a function from $I$ to $\cup C_i$, and since $f(i)\in B_i$ and $f_i$ sends things in $B_i$ to $C_i$, the resulting function will be an element of $\prod C_i$."

Try to write that down and see if $\mathbf{g}$ is a bijection.

share|improve this answer
    
I had problem with constructing g, now i proved thanks! –  Katlus May 3 '12 at 17:08
add comment

$\newcommand{\Zobr}[3]{#1\colon#2\to#3}$If we have a map $\Zobr {f_i}{A_i}{B_i}$ for each $i\in I$ then the Cartesian product of these functions is the function $\Zobr{g=\prod\limits_{i\in I}f_i}{\prod\limits_{i\in I}A_i}{\prod\limits_{i\in I}B_i}$, where $g(f)$ for $f\in \prod\limits_{i\in I}A_i$ is given by $$g(f)(i)=f_i(f(i)).$$

You should have look at the definition of Cartesian product of arbitrary system of sets at Wikipedia or in Arturo's answer. If you understand the definition of Cartesian product of a system of sets, you should be able to understand the definition of product of functions given above. (You should also try to compare this with the case when $I$ is finite, which is much easier.)

The proofs I wrote bellow are formal, they won't be very useful to you unless you acquire the intuition about these things - in my opinion it could be good if you try to understand the finite case first.

Lemma. Let $\Zobr {f_i}{A_i}{B_i}$ be functions for each $i\in I$.

  • (a) If $f_i$ is injective for each $i\in I$, then $\prod\limits_{i\in I} f_i$ is injective.
  • (b) If $f_i$ is surjective for each $i\in I$, then $\prod\limits_{i\in I} f_i$ is surjective.
  • (c) If $f_i$ is bijective for each $i\in I$, then $\prod\limits_{i\in I} f_i$ is bijective.

Proof. Denote $g:=\prod\limits_{i\in I}f_i$.

(a) Suppose that all $f_i$'s are injective. Let $f,f'\in \prod\limits_{i\in I}A_i$ and let $g(f)=g(f')$. This means that for each $i\in I$ we have $g(f)(i)=g(f')(i)$. By the definition of the function $g$ we get for each $i\in I$ the equality $f_i(f(i))=f_i(f'(i))$ and the injectivity of $f_i$ implies $f(i)=f'(i)$. Thus the functions $f$ and $f'$ are equal $g$ is indeed an injective map

(b) Let each $f_i$ be surjective and let $f\in\prod\limits_{i\in I}B_i$. Then for every $i\in I$ there exists $a_i\in A_i$ such that $f_i(a_i)=f(i)$. In the other words, $\{a\in A_i; f_i(a)=f(i)\}$ is a system of non-empty sets. Using Axiom of Choice we have that there exists a function $h$ defined on $I$ such that $h(i) \in \{a\in A_i; f_i(a)=f(i)\}$, i.e. $h(i)\in A_i$ a $f_i(h(i))=f(i)$ for each $i\in I$. The last equality means that $g(h)=f$. We have shown the each $f\in\prod\limits_{i\in I}B_i$ has a pre-image and thus $g$ is a surjective function.

(c) Follows easily from (a) and (b).


In case you haven't learned about Axiom of Choice yet, you can read that part as: we define $h(i)$ as an arbitrary element $a$ which fulfills $f_i(a)=f(i)$ (we know that at least one such element exists) and simply ignore the point that this axiom was used.


You only asked about the third part. You should be able to find a simpler proof of this, if you know that a function is bijective if and only if it has an inverse function. If you know that for each $f_i$ there is and inverse function $f_i^{-1}$, could you guess what is inverse to $g=\prod\limits_{i\in I}f_i$? Can you show that this function is indeed inverse to $g$?

share|improve this answer
add comment

Your Answer

 
discard

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

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