$\begingroup$

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)?

$\endgroup$ 3

1 Answer

$\begingroup$

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\}$.

$\endgroup$ 5

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy