Cardinality of power set of $A$ is determined by $2^n$, where n is the number of elements in Set $A$. How does this formula work?
I was taught that there are $n$ elements in Set $A$ and each element has a choice of either being in the power set or not i.e., $2$ choices. Hence $\underbrace{ 2\times 2\times 2\times 2 \cdots}_{n\; times} $.
But I don't understand why the element's choice of either being in the power set or not helps us in determining the cardinality of the power set.
Answer
I was taught that there are n elements in Set A and each element has a choice of either being in the power set or not i.e., 2 choices.
By definition, the power set of $A$ is the set of all subsets of $A$. The power set of $A$ does not contain elements of $A$, it contains subsets of $A$.
In how many ways can you choose a subset (say, $X$) of $A$? Well, every element in $A$ has a choice of either being in $X$ or not, i.e. $2$ choices. Thus there are $2^n$ ways you can form a subset $X$. Thus the total number of subsets is $2^n$.
To summarize: your mistake seems to be that you have swapped "choice being in $X$" (where $X$ is a subset) to "choice being in the power set".
No comments:
Post a Comment