HW1 Problem 7

Return to Homework 1, Glossary, Theorems

Problem 7

(*) For any set $A$, infinite or finite, let $B^{A}$ be the set of all functions mapping $A$ into the set $B = \{0, 1\}$. Show that the cardinality of $B^{A}$ is the same as the cardinality of the set $\mathcal P(A)$. [Hint: Each element of $B^{A}$ determines a subset of A in a natural way.]

Solution

For any set $A$, infinite or finite, the cardinality of $\mathcal P(A)=2^{n}$ where n is the cardinality of the set $A$. This is determined by knowing that each element in $A$ is either in or not in each possible subset. That is, two options for each element, then $2^{n}$. Similarly, if each element of $A$ is either mapped to $0$ or $1$, then each element has two options, thereby making the cardinality of $B^{A}$ to be $2^{n}$. Essentially, if mapped to $0$ the element is "out", and if mapped to $1$ the element is "in". Then each function is just creating one of the possible subsets of $A$, and the set of all such functions is essentially the set of all subsets, the power set. Therefore the cardinality of $B^{A}$ is the same as the cardinality of the set $\mathcal P(A)$. $Q.E.D.$

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License