$P(A)$ and $2^A$ are numerically equivalent

Question

Whilst reading some notes on the cardinality of infinite sets, I got to this question which has been bugging me for a while. Help would be greatly appreciated!

For every nonempty set A, the sets $P(A)$ and $2^A$ are numerically equivalent.

My current intuition/thoughts:

If the two sets are indeed numerically equivalent such that $|P(A)|$ = $|2^A|$, then there must exist a bijection, say $f$ from $P(A)$ to $2^A$. Right?

However this is where I get lost. How can $|2^A|$ be a function? Isn't it just a number? For example, the cardinality of a function with 2 elements would be $2^2$ $=$ $4$.

$4$ isn't a function however so I am lost as to how I can solve this problem.

Thank you very much! Also please explain in simple English as I am not a Math major (Stats/Econ major) :)

Thank you!!!

Answer 1

ADD I'm concerned about the fact you think $|2^A|$ should be a function. The set $2^A$ consists of functions, and $|2^A|$ counts how many such functions there are. Intuitively, the fact that $|\wp(A)|=|2^A|$ is the following: take the whole set $A$, and put it in a list. To obtain a subset of $A$, you'll have to eliminate some amount of elements. Let's agree to mark those elements that have been eliminated with a $0$, and mark with a $1$ those that have been kept. For example, if no element is eliminated (so no amount is eliminated), we obtain $A$. If all of them are eliminated, we obtain $\varnothing$. The idea is that each subset will produce a list of $0$s and $1$s, coupled with an element that will let you know exactly which subset we were talking about.

---

The notation $2^A$ has another nice interpretation when $A$ is finite, say it has $n$ elements. In such case, to produce a subset of $A$ you must decide for each element of $A$, whether or not to put it in the subset. Thus, you have $2$ choices for each element of $A$; which gives you $2\times 2\times\cdots \times 2=2^n$ choices to make, which amounts to $2^n$ possible subsets.

---

In set theory, one usually defines "the number $2$" precisely as the set $$\{0,1\}$$

Given two sets $A,B$, the set of all functions $f:A\to B$ is usually noted by $$B^A$$

Thus, you should read $$2^A$$ as "the sets of all functions $f:A\to \{0,1\}$".

Let $A$ be a set, and let $S$ be a subset of $A$. Define the function $${\bf 1}_S:A\to \{0,1\}$$ as $${\bf 1}_S(x)=\begin{cases} 1\text{ ; if } x\in S\\ 0 \text{ ; if }x\in A-S\end{cases}$$

Then it is clear every subset of $S$ of a defines function $f\in 2^A$ which is unique, for if ${\bf 1}_S={\bf 1}_{S'}$ this means $S$ and $S'$ have the same elements, which means $S=S'$. Conversely, every function $f:A\to\{0,1\}$ defines a subset of $A$ by $$S_f=\{x\in A:f(x)=1\}$$

so this is a bijection: it is one-one and onto.

Answer 2

Perhaps you might want to think about it as this: $$2^A = \{0, 1\}^A$$

Where $2^A$ is the set of all such functions $f: A \rightarrow \{0, 1\}$.

Note: $2^{|A|} = |2^A|$ IS a number. $2^A$ IS NOT a number; rather, it is the set of functions mapping each element of $A$ to one of two elements in $\{0, 1\}$.

Answer 3

$\left|2^A\right|$ is indeed a number: it’s the number of functions from $A$ to the two-element set $\{0,1\}$. The bijection that you want takes a set $S\subseteq A$ to its indicator (or characteristic) function $\chi_S$, which is defined as follows:

$$\chi_S:A\to\{0,1\}:a\mapsto\begin{cases} 1,&\text{if }a\in S\\ 0,&\text{if }a\notin S\;. \end{cases}$$

It’s pretty easy to see that if $S,T\subseteq A$, then $S=T$ if and only if $\chi_S=\chi_T$, so the map

$$\varphi:\wp(A)\to 2^A:S\mapsto\chi_S$$

is injective (one-to-one). It’s also pretty clear that if $f$ is any function from $A$ to $\{0,1\}$, we can let $S=\{a\in A:f(a)=1\}$, and we’ll have $\varphi(S)=\chi_S=f$, so that $\varphi$ is also surjective (onto) and therefore a bijection. This bijection establishes that $|\wp(A)|=\left|2^A\right|$.