# Question about the fact that the power set $P(A)$ of the set $A$ is equinumerous with the set $2^A$ of all functions from $A$ to $2$

Consider the set $$A =\{3,4\}$$. Its power set is $$P(A) = \{\varnothing, \{3\}, \{4\}, \{3,4\}\}$$. $$2^A$$ is defined as the set of all functions from $$A$$ to $$2$$. Letting $$2 = \{\varnothing, \{\varnothing\}\}$$, we have the cartesian product $$A \times 2 = \{\langle 3, \varnothing \rangle, \langle 3, \{\varnothing\}\rangle,\langle4,\varnothing\rangle,\langle4,\{\varnothing\}\rangle\}$$ Finally, we know that $$f \in 2^A \iff f \in P(A \times 2)$$ and $$f$$ is a function.

Notice that the power set $$P(A\times2)$$ will have the singleton of each element in $$A\times2$$ (which will be functions in the set-theoretical sense), and other combinations like $$\{\langle3,\varnothing\rangle, \langle4,\varnothing\rangle\}$$. But this will mean that there are more than 4 elements of $$P(A \times 2)$$ that are functions (in the set-theoretical sense of a relation), and that therefore $$P(A)$$ and $$2^A$$ aren't equinumerous.

Clearly I'm doing something very wrong here, would anyone have a hint?

• Your description of $f\in2^A$ is incorrect. you need $f$ to be a set-theoretic function and have domain equal to $A$. Aug 16, 2021 at 4:38
• The bijection is trivial: given a function $f\colon A\to 2$, define the subset $A_f=\{a\in A\mid f(a)=1\}$. The inverse of this correspondence maps a subset $B\subseteq A$ to its indicator function $\xi_B\colon A\to 2$, $\xi_B(x) = 0$ if $x\notin B$, and $\xi_B(x)=1$ if $x\in B$. Aug 16, 2021 at 4:39
• ah, that's what I was missing! thank you so much for the tip! Aug 16, 2021 at 4:40

The $$4$$ members of $$2^A$$ are $$\{(3,0)(4,0)\},\{(3,0)(4,1)\}\{(3,1)(4,0)\}\{(3,1)(4,1)\}.$$ These are subsets of $$A\times 2$$ but there are $$12$$ other subsets of $$A\times 2$$. A member of $$P(A\times 2)$$ is a member of $$2^A$$ iff it is the characteristic (indicator) function of a subset of $$A.$$