Cardinalities of Power Sets

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

The third and fourth proofs from problem set 7.

For the third, induction seems a good way to do it.

Starting any induction proof by writing out the proposition you’re trying to prove (the “P(n)” in the textbook’s terminology) is a good start:

As soon as you decide to use induction, you know that the proof is going to involve a basis case and an induction step. The basis case shows that the proposition holds for the smallest relevant n, which in this case is 2 (since that’s where the product starts). If you expand out the product from 2 to 2 you just get 2, which agrees with the claim that the product should equal n:

For the induction step, recall that the goal is to prove that if the proposition is true when n = k, then it must be true when n = k + 1. As with any proof of a conditional, you can start by assuming the hypothesis, i.e., assuming the proposition is true of k:

Now we need to show that it’s true when n = k+1. Often it’s helpful in an induction proof to write out what you’re trying to show in terms of k+1, and see if it can break down into a part that is just P(k), with something else that leads to P(k+1). In this case, expanding out the product helps reveal “P(k),” in the form of a product from 2 to k that is then multiplied by the k+1 term:

Replacing the product from 2 to k with k then gives you an expression in which the k’s cancel, leaving just k + 1, which is what you needed:

The fourth proof is about n^th derivatives, and since an n^th derivative can be calculated from the (n-1)^th derivative, induction again seems like a good way to do this proof.

Once again, start by being sure the proposition is clear:

This should hold for all natural numbers n.

The first derivative, i.e., n = 1, is a good basis case, and follows from the chain rule:

Then for the induction step, calculate the (k+1)^th derivative as the derivative of the k^th:

Misc

Problem Set 8

Problem set 8 is officially available. (I announced it Friday, but mainly for people who wanted an early look at it. As of today, it’s the one you should be working on.)

Fall Course Ideas

As registration for the fall comes around, here are two possible courses (admittedly self-serving possibilities, since both are things I would teach):

Math 384, “Computational Graphics,” studies an approach to graphics called ray tracing, which is the gold standard for producing realistic images from completely artificial scenes, like this one:

It all comes from mathematically modeling the shapes of things in the world and how light interacts with them. TR 10:00 - 11:15, requires Math 230, Calculus 3, and Linear Algebra 1.

For other exposure to computing, especially computer graphics, I’m open to supervising directed studies. My research interests are in computer graphics, and particularly how to mathematically and computationally model and render images of natural objects such as trees, mountains, etc., and particularly at the moment crystal aggregates.

The Cardinality of the Power Set

Recall that the power set of set S is the set of all subsets of S.

For example, if S = { 1, 2 }, then the power set of S, P(S), is { {1}, {2}, ∅, {1,2} }.

In Friday’s class, we conjectured that the cardinality (i.e., size) of the power set of S is 2^|S|. We also thought that induction might be a good way to prove this.

Now I want to sketch the actual proof.

Start by reasonably formally stating what is to be proven. Note that I’m using a script “P” for “power set,” which is the technically proper way to write it.

Induction is in fact a good way to prove this. We started with a basis step of the empty set, i.e., a set of cardinality 0. In doing this, we were kind of intuitively picking a “small” value to use in the basis step without really saying what “n” is in this theorem. In fact, there isn’t as explicit an “n” here as there has been in past examples of induction. But we eventually realized that the size of the sets in question is “n” in this example. This brings up a piece of wording that is common in induction proofs, namely “induction on” something to identify the “n” for a particular proof. In this case, a formal proof would say something such as

The proof is by induction on the size of set S.

The empty set as a basis case works well, since it has 0 elements but 1 subset (the empty set itself), and 2⁰ = 1.

For the induction step, assume, as usual, that the proposition holds for all sets of cardinality k, and show that it must then hold for all sets of cardinality k+1. Since cardinalities are non-negative, we know k ≥ 0, and so k+1 ≥ 1; this means that any set of cardinality k+1, say A, has at least one element, which we can call x. Then we can think of the subsets of that set as forming 2 groups: those that don’t contain x, and those that do. The first group is just the power set of A - {x}, which has cardinality k, and thus the first group of subsets has 2^k members. Each member of the second group can be created by adding x to a set from the first group, so the second group also has 2^k members. The total is 2^k + 2^k = 2^k+1, showing that any set of cardinality k+1 has 2^k+1 subsets.

Next

Proving relationships between sets.

Please read section 5.2 in the textbook.

Please also practice the central idea in the reading by contributing to this discussion of element-chasing proofs.

Next Lecture