17
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ 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) $\endgroup$
    – Henry
    Feb 1, 2012 at 7:15

4 Answers 4

25
$\begingroup$

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|$.
$\endgroup$
1
  • $\begingroup$ $2 = \{0,1\}$ is a reference to von Neumann ordinals, for anyone else who has no idea what that means. $\endgroup$
    – endolith
    Feb 29, 2020 at 2:05
9
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

I just came across this notation and found an explanation in a book on set theory. Actually, 2^n is not a power set, but a set with a one-to-one correspondence with it: from SET THEORY CHARLES C. PINTER

P.s. 2 is a set of two elements {0,1}

$\endgroup$
0
$\begingroup$

This notation was also used in Chandra and Toueg's seminal paper Unreliable Failure Detectors in Reliable Systems on page 231, par. 2.1. It was used to denote a powerset.

The notation 2S, given that 2 ∈ ℕ0 and S is a finite set, appears to be mathematically aburd at first glance. The literal 2 here, by the way, is the von Neumann ordinal 2 = {0, 1}. Notice that |2S| = 2|S| = |2||S|, which aligns with cardinal arithmetic and is very convenient indeed.

$\endgroup$
1
  • $\begingroup$ More than a decade later. Does this answer add anything to the ones already given? $\endgroup$
    – Asaf Karagila
    Jan 24, 2023 at 9:25

You must log in to answer this question.

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