Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am not very well versed on set theory or syntax, but I thought I knew the basics.

However, in a book about databases I am reading now, the author uses "2^x" (where ^ is the exponent operator) to signify "a set of x."

For example, 2^dogs is a set of dogs. Etc. The author never really explained this or why he does it, I just picked up the meaning from context. I am not sure why the exponent operator is used, nor am I sure what the number 2 has to do with it. The sets being represented are NOT powers of 2 (in size)... they come in all sizes.

Is this a valid notation? I have not seen it anywhere before...

share|improve this question
1  
2^dogs is more likely to mean the set of all possible sets with dogs as elements (including the empty set and the set of all dogs) –  Henry Feb 1 '12 at 7:15

2 Answers 2

up vote 7 down vote accepted

The notation $2^S$ denotes the power set of S, i.e. the set of all subsets of S, also denoted $\mathcal P(S)$.

  • The notation is in fact well chosen, with regard to the notation $X^Y$ to denote the set of all functions $Y\to X$: if we let $X = 2 = \{0,1\}$, then a function $f:Y\to \{0,1\}$ corresponds uniquely to a subset $S \subseteq Y$ if we let $x\in S\iff f(x)=1$.
  • As a special case, when $S$ is finite the order of $\mathcal P(S)$ is in fact $|\mathcal P(S)| = 2^{|S|}$, a fact useful to remember what the notation means. (This generalizes to $|X|^{|Y|} = |X^Y|$ for arbitrary sets.)
  • The notation $\binom{S}{i}$ is also being used: it is the set of all subsets of $S$ that contain exactly $i$ elements. Here too, $\binom{|S|}{i} = \left|\binom{S}{i}\right|$.
share|improve this answer

If $X$ is a finite set, say, it has $n$ elements, then the power set of $X$ is the collection of all subsets of $X$ which has exactly $2^n$ numbers of elements. That's why people use $2^X$ to denote the power set of $X$.

For example, $X=\{1,2,3\}$, then the power set of $X$ is given by $$2^X=\Big\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},X=\{1,2,3\}\Big\},$$ which has $2^3=8$ elements.

However, for infinite set $X$, of course the power set of $X$, $2^X$ is also infinite.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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