# What does 2 to the power x mean in set theory

In a mathematics assignments i encounter the following statement:

We have a finite collection of combinatorial objects $S \subseteq 2^x$ (For example matchings or spanning trees)

What does this notation $S \subseteq 2^x$ mean (Especially the $2^x$ part)?

• It's the power set – Fakemistake Dec 16 '17 at 15:51
• See Power set: "the power set of any set $X$ is the set of all subsets of $X$, including the empty set and $X$ itself, variously denoted as $\mathcal P(X), ℘(S)$, or, identifying the powerset of $X$ with the set of all functions from $X$ to a given set of two elements, $2^X$. Any subset of $\mathcal P(X)$ is called a family of sets over $X$." – Mauro ALLEGRANZA Dec 16 '17 at 16:16
• Thus, $S⊆2^X$ means that $S$ is a family of sets over $X$, i.e. a set of subsets of $X$. – Mauro ALLEGRANZA Dec 16 '17 at 16:17

If $A$ and $B$ are sets then $A^B$ is the collection of functions from $B$ to $A$. When you see the notation $2^X$, where $X$ is a set, we're also considering $2$ as a set, in fact $$2=\{0,1\}.$$ So $2^X$ is the collection of all functions mapping $X$ to $\{0,1\}$.
It's been stated in a comment that $2^X$ is the power set of $X$, that is, the collection of all subsets of $X$. That's not literally true, but there's an obvious and standard one-to-one correspondence between $2^X$ and the power set of $X$, given by $f\mapsto\{x:f(x)=1\}$.
• I didn't know that $A^B = \{f \mid f:B \to A\}$! Where does one learn this? Until I read this post, I thought that $2^{\Omega}$ meant the power set of a sample space because people thought that $|2^{\Omega}| = 2^{|\Omega|}$ was "clean notation"! – Clarinetist Dec 16 '17 at 18:22
• @Clarinetist You should take it as an exercise to figure out how $A^2$, by this definition, is naturally equivalent to $A\times A$. Similarly for $A^3$, after you figure out what set $3$ should be... – David C. Ullrich Dec 16 '17 at 22:18