What does $\{0,1\}^X$ mean?

Question

I got this notation in a question without prior explanation, I suspect it's something related to the power set but I am not sure.

Answer 1

As Angina said in the comments, $\{0, 1\}^X$ would be the set of all functions $f:X \to \{0, 1\}$. However, as you suspected, it is very closely linked to the power set of $X$ in the following manner.

---

Given a subset $U \subset X$, you have the function $\chi_U: X\to\{0, 1\}$ defined as $$\chi_U(x) := \begin{cases}0 & x \notin U\\1 & x \in U\end{cases}$$

---

Given a function $f:X \to \{0, 1\}$, you have a subset $U_f \subset X$ defined as $$U_f := \{x \in X \mid f(x) = 1\}.$$

---

The two correspondences are inverses in the sense that $$U_{\chi_U} = U; \quad \chi_{U_f} = f$$ for all $U \subset X$ and all $f \in \{0, 1\}^X$.

Thus, you could identify every subset of $X$ with a function $f: X \to \{0, 1\}$ and vice-versa and so you may as well consider $\{0, 1\}^X$ as the power set of $X$, also sometimes written as $2^X$.

Answer 2

In general you have $A^B:=\{f:B\longrightarrow A\}$.

In your case the set $\{0,1\}^{X}:=\{f:X\longrightarrow \{0,1\}\}=\{f:X \longrightarrow 2\}$.

An example of this notation could be the following: $P(\mathbb{N})\simeq2^{\mathbb{N}}\simeq \mathbb{R}$.