1
$\begingroup$

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.

1 Answers 1

4

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.

  • 0
    @Denis: Yes, you should be able to construct a counterexample that way. Try $A=\{0,1\}=C$ and $B=\{0\}$ and compare cardinalities.2012-12-05