Cardinality of a Power Set Discussion

(The following is/are the initial prompt(s) for an online discussion; students may have posted responses, and prompts for further discussion may have been added, but these things are not shown.)

In our April 2 class, we conjectured that the power set of set S has cardinality 2^|S|. Use this discussion to start sharing ideas about how you might prove it. For example, discussion in the class meeting suggested that induction might be a good way to prove this. Do you agree? If so, what would you do induction on (i.e., when you think of the proposition being proved as “P(n)”, like Sundstrom does, what would n represent)? How would you then proceed to do the induction? Alternatively, do you see another proof technique that might work better? Anything else you’d like to say?

Share your ideas or questions here, and we’ll pull them together in class on Monday.