18
$\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$ Commented Feb 1, 2012 at 7:15

4 Answers 4

Reset to default
26
$\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$ Commented 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$ Commented Jan 24, 2023 at 9:25

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.