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.

Possible Duplicate:
How to show $(a^b)^c=a^{bc}$ for arbitrary cardinal numbers?

Let $A,B,C$ be sets. Proof that $\left(A^{B}\right)^{C}\sim A^{\left(B\times C\right)}$ . I found the bijection between two sets, but the proof that it is actually a bijection is too long and complicated to understand. Is there easier way to prove the statement, for example by playing with sets' cardinalities? I know that the equality seems quite obvious, but the sets may also be infinite or empty...

Same question about proof of $A^{\left(B\cup C\right)}\sim A^{B}\times A^{C}$. This statement might be not true (the question was prove or give сounter example. Thanks.

share|improve this question
add comment

marked as duplicate by Asaf Karagila, Micah, rschwieb, Did, Martin Argerami Dec 5 '12 at 19:02

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

up vote 3 down vote accepted

If your argument is really all that long and involved, it’s probably unnecessarily complicated. We have

$$\varphi:\left(A^B\right)^C\to A^{B\times C}:f\mapsto\varphi_f\;,$$

where $$\varphi_f\big(\langle b,c\rangle\big)=f(c)(b)\;.$$

Suppose that $f,g\in\left(A^B\right)^C$ and $f\ne g$; then there is some $c\in C$ such that $f(c)\ne g(c)$. Now $f(c)$ and $g(c)$ are functions from $B$ to $A$, so there must be some $b\in B$ such that $f(c)(b)\ne g(c)(b)$. But then $\varphi_f\big(\langle b,c\rangle\big)\ne\varphi_g\big(\langle b,c\rangle\big)$, so $\varphi_f\ne\varphi_g$, and it follows that $\varphi$ is injective.

Now let $F\in A^{B\times C}$ be arbitrary. For each $c\in C$ let $F_c=\left\{\left\langle b,F\big(\langle b,c\rangle\big)\right\rangle:b\in B\right\}\in A^B$, and let

$$f:C\to A^B:c\mapsto F_c\;;$$

it’s entirely straightforward to verify that $\varphi_f=F$ and hence that $\varphi$ is also surjective.

By the way, it’s not just that these two sets have the same cardinality that’s important: this specific bijection is important in its own right.


The natural bijection from $A^B\times A^C$ to $A^{B\cup C}$ is defined as follows:

$$\varphi:A^B\times A^C\to A^{B\cup C}:\langle f,g\rangle\mapsto\varphi_{f,g}\;,$$

where $$\varphi_{f,g}:B\cup C\to A:x\mapsto\begin{cases} f(x),&\text{if }x\in B\\ g(x),&\text{if }x\in C\;. \end{cases}$$

Note: It’s important to assume here that $B\cap C=\varnothing$.

The details will be quite different, but if you mimic the pattern of the argument that I gave above, you should be able to prove reasonably efficiently that this $\varphi$ is a bijection.

share|improve this answer
    
Thanks Brian! I edited the question 2: This statement might be not true (the question was prove or give сounter example, sorry for my inadvertence/ –  Denis Turov Dec 5 '12 at 2:08
    
So, I assume the statement is not true and the example is to take sets that doesn't fulfill the condition you mentioned in Note. –  Denis Turov Dec 5 '12 at 2:10
    
@Denis: Yes, you should be able to construct a counterexample that way. Try $A=\{0,1\}=C$ and $B=\{0\}$ and compare cardinalities. –  Brian M. Scott Dec 5 '12 at 2:18
add comment

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