0

I'd like to prove that there is a bijection between the two sets $C^{A \times B}$ (the set of all functions from $A \times B$ to $C$) and $(C^B)^A$ (the set of all functions from $A$ to the set of all functions from $B$ to $C$) by showing one, without considering that this is immediate because they have the same cardinality.

Could anyone give me a hint of how to construct such a bijection?

mell_o_tron
  • 528
  • It's important that we don't just say "they have the same cardinality", because this construction is how we prove that they have the same cardinality! Just claiming the existence of the bijection here would be a circular argument – diracdeltafunk Dec 01 '20 at 19:17
  • Given $f(a,b)$, for fixed $a_0\in A$, take $F_{a_0}(b):=f(a_0,b)$ – Tito Eliatron Dec 01 '20 at 19:18
  • I was referring to a theorem that says "two finite sets have the same cardinality if and only if there is a bijection between them" – mell_o_tron Dec 01 '20 at 19:19
  • Ah well for finite sets there is a different proof that they have the same cardinality, but this bijection exists even if the sets are infinite :) – diracdeltafunk Dec 01 '20 at 19:20

2 Answers2

1

Map a function $f:A\times B\to C$ into a function $\phi:A\to C^B$ by setting, for all $a\in A$, that $\phi(a)$ maps $B$ to $C$ this way: $\phi(a)(b)=f(a,b)$ for all $b\in B$. That is all.

1

The bijection $\Phi : C^{A \times B} \to (C^A)^B$ is given by

$$\Phi(f)(b)(a) = f(a,b).$$

Now prove this works!

diracdeltafunk
  • 14,911
  • 2
    Note this direction is called currying; the reverse direction is called uncurrying. – Ian Dec 01 '20 at 19:22
  • For others who may be browsing this thread unaware of this connection: this map $\Phi$ is natural in $A$, $B$, and $C$, and exhibits the adjunction between $A \times ({-})$ (on the left) and $({-})^A$ (on the right), as endofunctors of $\mathsf{Set}$ – diracdeltafunk Dec 01 '20 at 19:24
  • 1
    I think you got $A$ and $B$ the wrong way around, but I got the idea, thanks a lot to you and the other user who answered :) – mell_o_tron Dec 01 '20 at 19:41
  • Ah yes, sorry about that! Of course you can switch $A$ and $B$ and get the bijection you actually asked for :) – diracdeltafunk Dec 01 '20 at 21:44