Bijection between $P(E)^F$ and $P(E*F)$

Question

Here * means the cartesian product, and P(X) is the set of all subsets of $X$. $E^F$ is the set of all applictions from $F$ to $E$. The question is contained in the title : i wish to find a natural bijection between those sets. Here is my try :

Let $f:F \rightarrow P(E)$ be a random function of $P(E)^F$. We call $F_0=\{x\in F, f(x)\neq \emptyset\}$. Then using the axiom of choice, we can define a function that associates, to every $x\in F$, some $y_x\in f(x)$ and get a pair $(x,y_x)$.

Let's call $X_f=\bigcup_{x\in F_0}\{(x,y_x)\}$ for every function $f$. It is clearly a subset of $E*F$.

My idea would be to consider after that the application $g:P(E)^F\rightarrow P(E*F)$ such that : $\forall f\in P(E)^F$, $g(f)=X_f$.

Now i get stucked because i cannot prove that $g$ is bijective. To do so, i would have to make further suppositions about the choices of the $y_x$ that were made for every function $f$, in order to get both surjectivity and injectivity. My idea to get surjectivity was to consider the size of $F_0$ (in order to control the size of $X_f$ by controlling the elements of $F$ that i could put into a pair that is in $X_f$). However, i feel like this is not the right method. Could anyone give me a hint about this ? I would be delighted if you could ! :)

Answer 1

Your $g$ is not bijective indeed, and constructing the desired bijection needs no axiom of choice. Simply define $$g:P(E)^F\to P(E\times F)$$ by $$g(f)=\{(x,y)\mid y\in F,x\in f(y)\},$$ and check that $h\circ g={\rm id}_{P(E)^F}$ and $g\circ h={\rm id}_{P(E\times F)},$ where $$h:P(E\times F)\to P(E)^F$$ is defined by $$h(X)(y)=\{x\in E\mid(x,y)\in X\}.$$

Answer 2

Currying is normally written like this(this is known to be bijection): $$ hom(A,hom(B,C)) == hom(A \times B,C) $$

This can be written more conveniently like this: $$ A\rightarrow B \rightarrow C = (A \times B) \rightarrow C$$

Now if we use $C=2$, $A=E$, $B=F$ we arrive at: $$ E \rightarrow F \rightarrow 2 = (E \times F) \rightarrow 2$$

Now using $E\rightarrow X = X^E$ We can get: $$(F\rightarrow 2)^E = (E \times F) \rightarrow 2$$

Now the last thing is to notice that $P(X) = X\rightarrow 2$, and we'll have the desired property: $$P(F)^E = P(E\times F)$$

NOTE: The question asked for $P(E)^F$, but we arrived at $P(F)^E$, so either the question is wrong or we don't have all the necessary steps available.