The problem asks to show that the cardinality of the set $B^A$, which is the set of all functions mapping a set $A$ to $B = \{0, 1\}$, is the same as the cardinality of the power set $\mathcal{P}(A)$, the set of all subsets of $A$.

Defining the Function

To do this, we will define a bijection between $B^A$ and $\mathcal{P}(A)$. Here's the idea:

• Each function $f \in B^A$ maps elements of $A$ to either 0 or 1.
• We can interpret the function $f$ as selecting a subset of $A$ by choosing those elements of $A$ that are mapped to 1.

Thus, we can define a function $\varphi: B^A \to \mathcal{P}(A)$ in the following way:

Defining $\varphi$:

For any function $f \in B^A$, define the corresponding subset $S \in \mathcal{P}(A)$ by: $\varphi(f) = \{a \in A \mid f(a) = 1\}$ In words, $\varphi(f)$ is the subset of $A$ consisting of all elements that are mapped to 1 by the function $f$.

Example:

• Suppose $A = \{1, 2, 3\}$, and let $f \in B^A$ be a function such that: $f(1) = 0, \quad f(2) = 1, \quad f(3) = 1$ Then, the corresponding subset $\varphi(f)$ would be: $\varphi(f) = \{2, 3\}$

Inversely defining the function:

To show that this is a bijection, we also need the inverse map $\varphi^{-1}: \mathcal{P}(A) \to B^A$. Given any subset $S \in \mathcal{P}(A)$, we can define a function $f_S \in B^A$ by:

\begin{cases} 1, & \text{if } a \in S, \\ 0, & \text{if } a \notin S. \end{cases}$$ In other words, $$f_S$$ is the characteristic function of the subset $$S \subseteq A$$. ### Conclusion: The function $$\varphi: B^A \to \mathcal{P}(A)$$ is a bijection, meaning that $$|B^A| = |\mathcal{P}(A)|$$, so the cardinalities of $$B^A$$ and $$\mathcal{P}(A)$$ are the same. Would you like further details on any part of this proof? --- Here are 5 related questions for further exploration: 1. How can we generalize this idea to sets other than $$\{0, 1\}$$? 2. What is the cardinality of the power set $$\mathcal{P}(A)$$ if $$A$$ is finite? 3. How does this result relate to binary strings representing subsets? 4. Can you show that the characteristic function of a subset is indeed a bijection? 5. How would this change if $$A$$ were infinite? What would be the cardinality of $$\mathcal{P}(A)$$ then? **Tip**: A characteristic function is a very useful tool in set theory; it helps transform set-theoretic questions into function-theoretic ones.