# Homework Help: Even More Induction

1. Jun 27, 2008

### Moridin

1. The problem statement, all variables and given/known data

Show with induction that a set with n elements have 2n subsets.

3. The attempt at a solution

I assume this should only be for all natural numbers, but I cannot even show that it applies to n = 1. Let's say we have a set S = {x(1)}. That has 1 element, but only 1 subset, not 2? I'm confused. Have I missed something from basic set theory?

2. Jun 27, 2008

### Dick

It has two subsets. {x(1)} and the empty set {}.

3. Jun 27, 2008

### Moridin

Of course. Thanks a bunch. Here is another go at it.

3. The attempt at a solution

(1) Show that it is true for n = 1:

A set S contains the element x(1). S can form two subsets S' and S'', where S' = {x(1)} and S'' = {}.

(2) Show that if it is true for n = p, then it is true for n = p + 1

Assume that if a set P contain p elements, then 2p subsets can formed from it.

P = {x(1), x(2),..., x(p)}
Q = {x(1), x(2),..., x(p), x(p+1)}

So P contains 2p subsets. Naturally, Q must contain 2p + C number of subsets, where C is a unknown constant. For (2) to be true 2p + C must be equal to 2p+1. This seems to mean that the power set P' contains 2p elements. So this means that I should attempt to figure out exactly how many elements are added to P' to form the power set Q' if you add an element to P? I'm not entire sure how to do this.

4. Jun 27, 2008

### rock.freak667

How many subsets are there that don't contain x(p+1)? (inductive hypothesis)

then count how many have x(p+1) in it....add those two together.

5. Jun 28, 2008

### Kurret

How many new possible subsets can you create, when you have one more element to pick?

6. Jun 28, 2008

### HallsofIvy

Every subset of Q (with x(p+1) added) is of two kinds: those that do not have x(p+1) in them and those that do not. How many subsets of Q do NOT have x(p+1) in them (remember that those would also be subsets of P)?

And every subset of Q that does contain x(p+1) is a subset of P union {x(p+1)}.

7. Jun 28, 2008

### Moridin

That would be 2p?

Too hard question.

The first subset would be {x(p+1)}.
Then we have the {x(n), x(p+1)} subsets, where n goes from 1 to p and so on with more elements added.

I know no general principle or line of thought to answer your question.

8. Jun 28, 2008

### Dick

Let be concrete here. Take P to be the set of {1,2,3...p}. Take Q to be the set of {1,2,3...p,p+1}. All of the subset of P are also subsets of Q. And there are 2^p of them by the inductive hypothesis. All of the subsets of P are also subsets of Q. The only new subsets consist of a subset S of P that contains also contains p+1. Right? So there are 2^p new subsets. What's 2^p+2^p?

9. Jun 29, 2008

### Moridin

That's 2p+1, which proves that if it is true for n = p, it is also true for n = p+1. I understand that all subsets of P are also subsets of Q. However, I do not understand how the text in bold follows. How can you show how many more subsets can form when you add another element?

10. Jun 29, 2008

### Dick

You have 2^p sets without that element. If you add that new element to each of the 2^p sets, you get 2^p additional sets. If you put them all together you get all sets made from p+1 elements. For a total of 2^(p+1).

11. Jun 30, 2008

### Moridin

Of course. That makes sense. Thanks a bunch.