Equinumerousity of operations on cardinal numbers

Solution 1:

What I wrote below is, admittedly, a rather formal approach. I hope somebody will be able to post an answer which also gives some intuition behind this.

I will only answer the first question. (I have provided links to answers for the remaining two in the above comment.)

Let us denote by $\newcommand\Maps[2]{{}^{#1}#2}\Maps BA$ the set of all functions from $B$ to $A$

We want to show that there is a bijection between $\Maps C{A\times B}$ and $\Maps CA \times \Maps CB$.

Let us denote by $\pi_A \colon A\times B \to A$ the function $$\pi_A(a,b)=a$$ and by $\pi_B \colon A\times B \to A$ $$\pi_B(a,b)=b.$$ Notice that for any element $x=(a,b)\in A\times B$ we have $$(\pi_A(x),\pi_B(x))=(\pi_A(a,b),\pi_B(a,b))=(a,b)=x.\tag{*}$$ The functions $\pi_A$ and $\pi_B$ are usually called projections.

Then for any function $f \colon C\to A\times B$ we have $(\pi_A\circ f,\pi_B\circ f)\in \Maps CA \times \Maps CB$.

So we have a function $$ \varphi \colon \Maps C{A \times B} \to \Maps CA \times \Maps CB\\ \varphi(f) = (\pi_A\circ f,\pi_B\circ f) $$

On the other hand, for any $g\colon C\to A$ and $h\colon C\to B$ we can define the function $$\psi((g,h)) \colon C\to A\times B\\ \psi((g,h))(c) = (g(c),h(c)).$$ So this defines a function $\psi \colon \Maps CA \times \Maps CB \to \Maps C{A \times B}$.

If we show that $\varphi$ and $\psi$ are inverse to each other, we are done. (See, for example, Inverse of a Function exists iff Function is bijective.)

Let $f\in \Maps C{A \times B}$. We want to show that $\psi(\varphi(f))=f$. We have $$\psi(\varphi(f))=\psi(\pi_A\circ f,\pi_B\circ f).$$ This means that for every $c\in C$ we get $$\psi(\varphi(f))(c)=\psi(\pi_A\circ f,\pi_B\circ f)(c)=(\pi_A(f(c)),\pi_B(f(c)))\overset{(*)}=f(c).$$ So we see that the functions $\psi(\varphi(f))$ and $f$ have the same values at each $c\in C$, meaning that $\psi(\varphi(f))=f$.

Let $(g,h)\in \Maps CA \times \Maps CB$. We want to show that $\varphi(\psi(g,h))=(g,h)$. We have $$\varphi(\psi(g,h)) = (\pi_A\circ \psi(g,h), \pi_B\circ \psi(g,h)).$$ So it suffices to show that $\pi_A\circ \psi(g,h)=g$ and $\pi_B\circ \psi(g,h)=h$.

If $c\in C$ then we have $\psi(g,h)(c)=(g(c),h(c))$ and $$\pi_A(\psi(g,h)(c))=\pi_A((g(c),h(c)))=g(c).$$ So we see that the functions $\pi_A\circ \psi(g,h)$ and $g$ attain the same value for each $c$ from the domain $C$, meaning that $\pi_A\circ \psi(g,h)=g$.

The proof that $\pi_B\circ \psi(g,h)=h$ is very similar.