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.

One of the basic (and frequently used) properties of cardinal exponentiation is that $(a^b)^c=a^{bc}$.

What is the proof of this fact?

As Arturo pointed out in his comment, in computer science this is called currying.

share|improve this question
1  
I thought that this result appears quite frequently in various questions as an auxiliary computation, so it would be good to have something to refer to. I've asked moderator to make this community wiki. (Sorry if I have overlooked a similar question.) –  Martin Sleziak Aug 14 '11 at 11:50
1  
Computer scientists know this (though they perhaps are unaware of it) as currying. –  Arturo Magidin Aug 14 '11 at 19:25

2 Answers 2

Theorem: For arbitrary cardinal numbers the equality $(a^b)^c=a^{bc}$ holds.

Proof. It suffices to show that there is a bijection between $(A^B)^C$ and $A^{B\times C}$ for arbitrary sets $A$, $B$, $C$. We will try to find functions $\varphi:{(A^B)^C}\to{A^{B\times C}}$ and $\psi:{A^{B\times C}}\to{(A^B)^C}$ and show that they are inverse to each other.

We want to find a map $\varphi:{(A^B)^C}\to{A^{B\times C}}$. I.e., for any given map $f: C\to A^B$ we would like to get some map assigning elements from $A$ to pairs $(b,c)\in B\times C$. For arbitrary $c\in C$ we have the map ${f(c)}:B\to A$ -- so it is quite natural map the pair $(b,c)$ to $f(c)(b)$, i.e. $$\varphi(f):{B\times C}\to A$$ $$\varphi(f)(b,c)=f(c)(b)$$

Conversely, to each map $g:{B\times C}\to A$ we would like to assign a map ${\psi(g)}:C \to {A^B}$, i.e. a map which assigns to each element from $C$ some function from $B$ to $A$. If we are given a function from $B\times C$ to $A$, and if we fix $c\in C$ and change only the element $b\in B$ we see, that we get a map from $B$ to $A$. This can be written more precisely as $${(\psi(g))(c)}:B\to A$$ $$(\psi(g))(c)(b)=g(b,c)$$

This map is sketched in the figure bellow, where kde $A=\mathbb R$, $B=\langle 0,1\rangle$, $C=\langle0,\infty)$. The "cuts" marked on the graph of the given function are precisely the functions from $B$ to $A$ assigned to elements of $C$. (I've chosen the sets $A$, $B$ a $C$ to be different, so that we can see on the picture which set is which.)

Simply by composition we get that both $\varphi\circ\psi$ and $\psi\circ\varphi$ is identity. Let us first compute ${\varphi\circ\psi}:{A^{B\times C}}\to {A^{B\times C}}$. For arbitrary $g:{B\times C}\to A$ we would like to find out how the function ${\varphi(\psi(g))}:{B\times C}\to A$ looks. We get (directly using the definition of the maps $\varphi$ and $\psi$) that $$\varphi(\psi(g))(b,c)=\psi(g)(c)(b)=g(b,c).$$ Thus we have $\varphi(\psi(g))=g$ for each $g\in A^{B\times C}$, and thus $\varphi\circ\psi=id_{A^{B\times C}}$.

Now let us try to compute ${\psi\circ\varphi}:{(A^B)^C}\to {(A^B)^C}$. If we have a map $f:C\to {A^B}$, we would like to find out whether $\psi(\varphi(f))=f$. Using definitions of $\varphi$ and $\psi$ we get $$\psi(\varphi(f))(c)(b)=\varphi(f)(b,c)=f(c)(b).$$ Since this is true for any $b\in B$, we get the equality of the functions $$\psi(\varphi(f))(c)=f(c).$$ Again, this equality holds for each $c\in C$, hence $\psi\circ\varphi(f)=f$. The last equality (which holds for arbitrary $f\in (A^B)^C$) implies the equality of the functions $\psi\circ\varphi=id_{(A^B)^C}$.

We have found out that $\psi=\varphi^{-1}$, hence both maps $\varphi$ and $\psi$ are bijective.


Figure illustrating the proof. (I have used the function $f(x,y)=\frac32+\frac15\sin{\pi x}$:

Figure illustrating the proof. (I have used the function $f(x,y)=\frac32+\frac15\sin{\pi
x}$.)

share|improve this answer
1  
I've translated this from the notes I've made for my students in Slovak language - so maybe on some places the word order or formulation may feel a little clumsy. The picture is originally made in metapost. I did my best to show that the choice of the maps $\varphi$ and $\psi$ is very natural. –  Martin Sleziak Aug 14 '11 at 12:08
    
This seems like a very long answer for a very simple idea! But I've never tried to teach this to anyone, so perhaps it is necessary to have this much detail. –  Zhen Lin Aug 14 '11 at 12:50
    
@Zhen: In the course I TA during fall semesters we give this exercise as a standard exercise in cardinal arithmetic. The details are abundant in these sort of questions, especially on introductory level where you cannot make any skips. –  Asaf Karagila Aug 14 '11 at 13:14
    
Ahh I'm getting lost in this answer is there a simpler explanation? (not that I don't appropriate the effort) –  Jason Aug 14 '11 at 16:42
    
@Jason: I tried to give a general explanation with somewhat less details. I hope it will make things clearer. –  Asaf Karagila Aug 14 '11 at 18:45

Martin gave a complete and detailed answer, I will give a short proof that might be clearer.

Recall that $A^B = \{f\mid f\colon B\to A\}$, i.e. all the functions from $B$ into $A$.

Since we defined cardinality as equivalence classes, it suffices to show that $(A^B)^C$ is equinumerous with $A^{B\times C}$ for arbitrary sets.

First we need to understand these two sets. $(A^B)^C$ is a set of functions, whose domain is $C$ and their value is a function from $B$ into $A$. That is a typical function would take an element of $C$ and return a function from $B$ into $A$.

$A^{B\times C}$ is the set of all functions whose domain is $B\times C$, into $A$. These functions take ordered pairs (or two variables) from $B\times C$ and return an element of $A$.

The intuition of what we are going to do is similar to $f_n = \cos (nx)$ and $f(x,n) = \cos (nx)$. The former is a function from $\mathbb N$ into $\mathbb R^\mathbb R$ (namely $n\mapsto \cos(nx)$), while the latter is a function from $\mathbb R\times\mathbb N\to\mathbb R$.

The way we do it is by defining $\varphi\colon(A^B)^C\to A^{B\times C}$ defined as in a similar way. $\varphi(f)$ will be the function that when fixing $c$ we have $f(c)$.

Rigorously, this is defined as: $$\varphi(f)(b,c) = f(c)(b)$$

To check that this is one-to-one, if $g,f\in (A^B)^C$ are two different functions, take $c$ such that $f(c)\neq g(c)$ (remember that both of these values are functions from $A^B$). That means that for some $b\in B$ we have $f(c)(b)\neq g(c)(b)$.

Therefore at the pair $\langle b,c\rangle$ the function $\varphi(f)$ will have a different value than $\varphi(g)$.

To show that $\varphi$ is a surjection, we take a function $g\colon B\times C\to A$, and simply set $f\colon C\to A^B$ to be $f(c)(b) = g(b,c)$. We need, of course, to show that $f$ is well defined, and then we can easily show that $\varphi(f)=g$.

share|improve this answer
1  
Thanks so much :) This answer cleared up my mind at last :) –  Jason Aug 14 '11 at 19:14

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.