Options

Azimuth Math Review - Blog

[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

  • 1.

    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? :).

    Comment Source: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? :).
  • 2.
    edited February 15

    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|}\]

    Comment Source: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|}\\]
  • 3.

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

    Comment Source: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\\).
  • 4.

    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.

    Comment Source: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.
  • 5.
    edited February 15

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

    Comment Source: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\\).
  • 6.
    edited February 15

    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.

    Comment Source: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.
  • 7.
    edited February 15

    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.

    Comment Source: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.
  • 8.
    edited February 17

    END-ARTICLE

    Comment Source:END-ARTICLE
Sign In or Register to comment.