9
$\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$
4
  • 7
    $\begingroup$ It's the power set $\endgroup$ Commented Dec 16, 2017 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$ Commented Dec 16, 2017 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$ Commented Dec 16, 2017 at 16:17
  • $\begingroup$ The following question answers it better. math.stackexchange.com/questions/104522/… $\endgroup$
    – nickalh
    Commented May 12, 2023 at 4:14

1 Answer 1

15
$\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
  • 5
    $\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
    Commented Dec 16, 2017 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$ Commented Dec 16, 2017 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
    Commented Dec 16, 2017 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$ Commented Dec 16, 2017 at 22:18
  • $\begingroup$ Woah, retweet (If this were Twitter.. ☺) @Clarinetist! The notation is a lot more judicious than I realized! $\endgroup$
    – user316769
    Commented Dec 16, 2017 at 23:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .