5
$\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)?

|cite|improve this question
$\endgroup$
  • 6
    $\begingroup$ It's the power set $\endgroup$ – Fakemistake Dec 16 '17 at 15:51
  • 3
    $\begingroup$ 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$." $\endgroup$ – Mauro ALLEGRANZA Dec 16 '17 at 16:16
  • 2
    $\begingroup$ Thus, $S⊆2^X$ means that $S$ is a family of sets over $X$, i.e. a set of subsets of $X$. $\endgroup$ – Mauro ALLEGRANZA Dec 16 '17 at 16:17
11
$\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\}$.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ "obvious and standard". And a big stumbling block for most students the first few times they see it. Might not be remiss to actually spell it out... or not. $\endgroup$ – fleablood Dec 16 '17 at 17:14
  • 2
    $\begingroup$ 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"! $\endgroup$ – Clarinetist Dec 16 '17 at 18:22
  • 5
    $\begingroup$ @Clarinetist, what you call "clean notation" is how powers of natural numbers are defined (or more precisely, cardinal numbers). It is set theory where you learn it. $\endgroup$ – Ennar Dec 16 '17 at 18:29
  • 2
    $\begingroup$ @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... $\endgroup$ – David C. Ullrich Dec 16 '17 at 22:18
  • $\begingroup$ Woah, retweet (If this were Twitter.. ☺) @Clarinetist! The notation is a lot more judicious than I realized! $\endgroup$ – user316769 Dec 16 '17 at 23:27

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.