# Strange set notation (a set as a power of 2)?

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$ to signify "a set of $x$."

For example, $2^{\text{dogs}}$ is a set of $\text {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...

-
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

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

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.

-