# Understanding the proof of: If $|A| = \kappa$, then $|\mathcal{P}(A)|=2^{\kappa}$.

I don't quite understand the part where the author writes that $f$ is a one-to-one correspondence between the power set of $A$ and the set of all mappings from $A$ into $\{0, 1\}$. Isn't the function $f$ mapping only $X$ onto $\mathcal{X}_X$?

• $f:\mathcal{P}(A)\to \{0,1\}^A$ defined by $f(X)=\chi_X$ – Hamou Aug 12 '14 at 9:59
• Please avoid the word "help" in the title; it's clear that you'd like help, since you are posting a question. – user147263 Aug 12 '14 at 12:46
• It is probably just a matter of notation. It would have been better to write as Hamou suggests in the comment above. Another common way to avoid ambiguity is to write $f: X\mapsto \chi_X$. – Andrés E. Caicedo Aug 12 '14 at 19:42

Injectivity: if $f(X)=f(Y)$ then $\chi_X=\chi_Y$ so it is clear that $X=Y$. Surjectivity: Let $\varphi\in \{0,1\}^A$, $i.e$ $\varphi:A\to \{0,1\}$, put $X=\varphi^{-1}(\{1\})$, we have $\varphi=\chi_X=f(X)$.

That is a mistake then. It should be: the function $f:\mathcal P(X) \to 2^X$ given by $f(X)=\chi _X$ is a bijection.

• I wouldn’t call it a mistake. I think the author uses “$f\colon X → χ_X$” for “$f\colon X ↦ χ_X$”. – k.stm Aug 12 '14 at 10:12

Just try to spell it out.

The power set of $A$ contains all the subsets of $A$.

The set of all mappings from $A$ into $\{0, 1\}$ contains $n$-tuples of $1$s and $0$s with $n = |A|$, e.g. for $n=5$ it would contain: $$(0,0,0,0,0)$$ $$(0,0,0,0,1)$$ $$(0,0,0,1,0)$$ $$(0,0,0,1,1)$$ $$...$$ $$(1,1,1,1,1)$$ This is a one-to-one correspondence because you can characterize every subset by labeling the elements of $A$ with $a_i$ ($i=1,...,n$) and mapping it to an $n$-tuple of of $1$s and $0$s such that you put $1$ on the $i$-th place if $a_i$ is an element of that subset and $0$ otherwise.

Visual aid: