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

- All Categories 2.3K
- Chat 499
- Study Groups 17
- Petri Nets 8
- Epidemiology 3
- Leaf Modeling 1
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 339
- MIT 2019: Lectures 79
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 67
- Azimuth Code Project 110
- Statistical methods 3
- Drafts 2
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 147
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 707

Options

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.

## Comments

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

`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\\).`

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\).`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\\).`

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

`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\\).`

.

`.`