#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Options

# [section1] The powerset

edited February 2020

For a set $$S$$, the power set, which is written as $$P(S)$$ or $$2^S$$ refers to the collection of all subsets of $$S$$.

For example, $$2 ^ {\lbrace 10, 20 \rbrace} = \lbrace \lbrace \rbrace, \lbrace 10 \rbrace, \lbrace 20 \rbrace, \lbrace 10,20 \rbrace \rbrace$$.

How big is $$2^S$$? Well, if $$S$$ has $$n$$ elements, the power set $$2^S$$ has $$2^n$$ elements:

$|2^S| = 2^{|S|}$

Hence the notation.

• Options
1.
edited February 2020

Why?

Write $$S = \lbrace x_1, \ldots, x_n \rbrace$$.

Given this ordering for the elements, each subset $$A$$ corresponds to a vector of $$n$$ bits, with the ith bit saying whether or not $$x_i$$ belongs to $$A$$.

So each subset can be identified by an n-digit sequence in base 2.

Since there are $$2^n$$ of these sequences, that means the power set has size $$2^n$$.

Comment Source:Why? Write \$$S = \lbrace x_1, \ldots, x_n \rbrace\$$. Given this ordering for the elements, each subset \$$A\$$ corresponds to a vector of \$$n\$$ bits, with the ith bit saying whether or not \$$x_i\$$ belongs to \$$A\$$. So each subset can be identified by an n-digit sequence in base 2. Since there are \$$2^n\$$ of these sequences, that means the power set has size \$$2^n\$$.
• Options
2.
edited February 2020

Another proof is by induction on n.

The base case is for n = 0. That means S = {}. So the claim to be shown is:

$|2^{\lbrace \rbrace}| = 2^{|\lbrace \rbrace|}$

$$2^{\lbrace \rbrace}$$ is all subsets of $$\lbrace \rbrace$$, which just contains one member $$\lbrace \rbrace$$. So the left side equals 1. On the right, since $$|\lbrace \rbrace|$$ equals 0, we also get 1.

For the induction step, we'll show that increasing $$S$$ by one element doubles the size of $$2^S$$.

Let $$S' = S \cup \lbrace x \rbrace$$. To each subset $$A$$ of $$S$$ we can associate a pair of subsets of $$S'$$ -- $$A$$ itself, and $$A \cup \lbrace x \rbrace$$. And this mapping is unique, in that every subset of $$A'$$ gets hit by the mapping, and gets hit only once. So the number of subsets of $$A'$$ is exactly twice the number of subsets of $$A$$.

Comment Source:Another proof is by induction on n. The base case is for n = 0. That means S = {}. So the claim to be shown is: \$|2^{\lbrace \rbrace}| = 2^{|\lbrace \rbrace|} \$ \$$2^{\lbrace \rbrace\}\$$ is all subsets of \$$\lbrace \rbrace\$$, which just contains one member \$$\lbrace \rbrace\$$. So the left side equals 1. On the right, since \$$|\lbrace \rbrace|\$$ equals 0, we also get 1. For the induction step, we'll show that increasing \$$S\$$ by one element doubles the size of \$$2^S\$$. Let \$$S' = S \cup \lbrace x \rbrace\$$. To each subset \$$A\$$ of \$$S\$$ we can associate a pair of subsets of \$$S'\$$ -- \$$A\$$ itself, and \$$A \cup \lbrace x \rbrace\$$. And this mapping is _unique_, in that every subset of \$$A'\$$ gets hit by the mapping, and gets hit only once. So the number of subsets of \$$A'\$$ is exactly twice the number of subsets of \$$A\$$. 
• Options
3.
edited February 2020

The notation $$2^S$$ also agrees with the exponential notation $$B^A$$ for general sets $$A$$, $$B$$, which is defined as the set of all functions from A to B.

In this context, let's take 2 to mean the binary set $$\lbrace True,False \rbrace$$.

So $$2^S$$ means all functions going from $$S$$ into $$\lbrace True,False\rbrace$$. Each of these is a predicate, assigning $$True$$ or $$False$$ to every member of $$S$$. And each predicate is equivalent to the subset of values in $$S$$ which get mapped to $$True$$.

So as a set of functions $$2^S$$ is equivalent to the power set $$2^S$$.

Comment Source:The notation \$$2^S\$$ also agrees with the exponential notation \$$B^A\$$ for general sets \$$A\$$, \$$B\$$, which is defined as the set of all functions from A to B. In this context, let's take 2 to mean the binary set \$$\lbrace True,False \rbrace \$$. So \$$2^S\$$ means all functions going from \$$S\$$ into \$$\lbrace True,False\rbrace \$$. Each of these is a predicate, assigning \$$True\$$ or \$$False\$$ to every member of \$$S\$$. And each predicate is equivalent to the subset of values in \$$S\$$ which get mapped to \$$True\$$. So as a set of functions \$$2^S\$$ is equivalent to the power set \$$2^S\$$.
• Options
4.
edited February 2020

.

Comment Source:.