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

- All Categories 2.3K
- Chat 494
- ACT Study Group 5
- Azimuth Math Review 6
- MIT 2020: Programming with Categories 53
- MIT 2020: Lectures 21
- 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 64
- Azimuth Code Project 110
- Drafts 1
- Math Syntax Demos 15
- Wiki - Latest Changes 1
- Strategy 110
- Azimuth Project 1.1K

Options

[This is an experimental format.]

This is a "proto-blog" for the math review, intended for group participation. You can inline articles here, as a contiguous sequence of comments. To prepare articles, you can use category Drafts, which doesn't publish to the main display.

General conversation can take place in between the articles.

The first article here shows a convention for marking the start and end of an article.

## Comments

How would I know what number to assign to these "BEGIN-/END-ARTICLE" markers, what are they there for and how come your post above doesn't have them? :).

`How would I know what number to assign to these "BEGIN-/END-ARTICLE" markers, what are they there for and how come your post above doesn't have them? :).`

BEGIN-ARTICLE Tanzer.1 - The power set and its exponential notation

For a set \(S\), the power set \(2^S\) refers to the collection of all subsets of \(S\).

How big is \(2^S\)? Not surprisingly, if \(S\) has \(n\) elements, the power set has \(2^n\) elements:

\[|2^S| = 2^{|S|}\]

`BEGIN-ARTICLE Tanzer.1 - The power set and its exponential notation For a set \\(S\\), the power set \\(2^S\\) refers to the collection of all subsets of \\(S\\). How big is \\(2^S\\)? Not surprisingly, if \\(S\\) has \\(n\\) elements, the power set has \\(2^n\\) elements: \\[|2^S| = 2^{|S|}\\]`

There are a couple of ways to see why this holds.

Suppose \(S\) has \(n\) elements \(x_1, \ldots, x_n\). Let \(A\) be a subset of \(S\). Then \(A\) can be represented by a vector of \(n\) bits, where the kth bit is 1 if \(x_k\) belongs to \(A\), or 0 otherwise.

So each subset \(A\) is represented by a unique n-digit sequence in base 2.

Since there are \(2^n\) such sequences, it follows that power set has size \(2^n\).

`There are a couple of ways to see why this holds. Suppose \\(S\\) has \\(n\\) elements \\(x_1, \ldots, x_n\\). Let \\(A\\) be a subset of \\(S\\). Then \\(A\\) can be represented by a vector of \\(n\\) bits, where the kth bit is 1 if \\(x_k\\) belongs to \\(A\\), or 0 otherwise. So each subset \\(A\\) is represented by a unique n-digit sequence in base 2. Since there are \\(2^n\\) such sequences, it follows that power set has size \\(2^n\\).`

Another proof is by induction on n.

The base case is for n = 0. That means S = {}. So what must be shown here is that:

\[|2^{\lbrace \rbrace}| = 2^{|\lbrace \rbrace|} \]

Well \(2^{\lbrace \rbrace}\) is the set of subsets of the empty set, which just contains one member -- the empty set. So the left hand side of this equation is 1.

On the right hand side, since \(|\lbrace \rbrace|\) equals 0, we also get the value 1.

`Another proof is by induction on n. The base case is for n = 0. That means S = {}. So what must be shown here is that: \\[|2^{\lbrace \rbrace}| = 2^{|\lbrace \rbrace|} \\] Well \\(2^{\lbrace \rbrace\}\\) is the set of subsets of the empty set, which just contains one member -- the empty set. So the left hand side of this equation is 1. On the right hand side, since \\(|\lbrace \rbrace|\\) equals 0, we also get the value 1.`

The induction can be proven as follows.

All we need to do is to show that adding one element to the set \(S\) causes the size of \(2^S\) to double.

But that's easy to see, by the following argument. Let \(S'\) be the set obtained by adding a new element \(x\) to \(S\).

Now, for subset \(A\) of \(S\), we can uniquely associate two subsets in the powerset \(2^{S'}\). The first set is \(A\) itself, and the other is the union of \(A\) with \(\lbrace x \rbrace\).

This shows that the size of \(2^{S'}\) is double the size of \(2^S\).

`The induction can be proven as follows. All we need to do is to show that adding one element to the set \\(S\\) causes the size of \\(2^S\\) to double. But that's easy to see, by the following argument. Let \\(S'\\) be the set obtained by adding a new element \\(x\\) to \\(S\\). Now, for subset \\(A\\) of \\(S\\), we can uniquely associate two subsets in the powerset \\(2^{S'}\\). The first set is \\(A\\) itself, and the other is the union of \\(A\\) with \\(\lbrace x \rbrace\\). This shows that the size of \\(2^{S'}\\) is double the size of \\(2^S\\).`

Here's an alternative proof of the induction step. It's a bit more rigorous.

The induction hypothesis says that the claim holds true for all values of k less than n.

Let S be a set of size n. We will use the induction hypothesis to prove the claim holds for \(S\).

Write \(S = \lbrace x_1, \ldots, x_n \rbrace \).

Let \(T_1\) be all the subsets of \(S\) that contain \(x_n\), and \(T_0\) be all the subsets that don't contain it.

Observe that \(T_1\) and \(T_0\) can be put into one-to-one correspondence. That's because for every subset \(A\) in \(T_1\) - which means \(A\) contains \(x_n\) -- we can associate the set \(A'\) in \(T_0\) that is obtained by removing \(x_n\) from \(A\).

So \(T_0\) and \(T_1\) have the same size, and, since they partition \(2^S\), it follows that \(2^S\) is twice the size of \(T_0\).

Next, let \(S' = S - \lbrace x_n \rbrace\) be the set obtained by removing \(x_n\) from \(S\).

Since \(T_0\) is all subsets of \(S\) that don't contain \(x_n\), it follows that \(T_0\)

isthe power set of \(S'\).Moving along, we now apply the induction hypothesis to \(S'\), in order to infer that the size of the power set of \(S'\) is \(2^{n-1}\).

Putting it all together, we have:

\[|2^S| = 2 * |T_0| = 2 * |2^{S'}| = 2 * 2^{n-1} = 2^n\]

That completes the alternate proof.

`Here's an alternative proof of the induction step. It's a bit more rigorous. The induction hypothesis says that the claim holds true for all values of k less than n. Let S be a set of size n. We will use the induction hypothesis to prove the claim holds for \\(S\\). Write \\(S = \lbrace x_1, \ldots, x_n \rbrace \\). Let \\(T_1\\) be all the subsets of \\(S\\) that contain \\(x_n\\), and \\(T_0\\) be all the subsets that don't contain it. Observe that \\(T_1\\) and \\(T_0\\) can be put into one-to-one correspondence. That's because for every subset \\(A\\) in \\(T_1\\) - which means \\(A\\) contains \\(x_n\\) -- we can associate the set \\(A'\\) in \\(T_0\\) that is obtained by removing \\(x_n\\) from \\(A\\). So \\(T_0\\) and \\(T_1\\) have the same size, and, since they partition \\(2^S\\), it follows that \\(2^S\\) is twice the size of \\(T_0\\). Next, let \\(S' = S - \lbrace x_n \rbrace\\) be the set obtained by removing \\(x_n\\) from \\(S\\). Since \\(T_0\\) is all subsets of \\(S\\) that don't contain \\(x_n\\), it follows that \\(T_0\\) _is_ the power set of \\(S'\\). Moving along, we now apply the induction hypothesis to \\(S'\\), in order to infer that the size of the power set of \\(S'\\) is \\(2^{n-1}\\). Putting it all together, we have: \\[|2^S| = 2 * |T_0| = 2 * |2^{S'}| = 2 * 2^{n-1} = 2^n\\] That completes the alternate proof.`

The notation \(2^S\) is also consistent with the general exponential notation \(B^A\) for sets \(A\), \(B\). The expression \(B^A\) stands for the set of all functions from A to B.

So according to that, \(2^S\) would be these set of all functions from \(S\) into 2. Here, we'll take '2' to be a name for two-element set {0,1}.

What's a function from \(S\) into {0,1}? It can be viewed as a predicate, which assigns true or false to every member of S.

And that's equivalent to a subset of S -- the subset of all values in S that map to 1.

So, \(2^S\) as a set of functions is equivalent to \(2^S\) as a collection of subsets.

`The notation \\(2^S\\) is also consistent with the general exponential notation \\(B^A\\) for sets \\(A\\), \\(B\\). The expression \\(B^A\\) stands for the set of all functions from A to B. So according to that, \\(2^S\\) would be these set of all functions from \\(S\\) into 2. Here, we'll take '2' to be a name for two-element set {0,1}. What's a function from \\(S\\) into {0,1}? It can be viewed as a predicate, which assigns true or false to every member of S. And that's equivalent to a subset of S -- the subset of all values in S that map to 1. So, \\(2^S\\) as a set of functions is equivalent to \\(2^S\\) as a collection of subsets.`

END-ARTICLE

`END-ARTICLE`