Even More Induction: Showing 2n Subsets in n Element Set

[Moridin]

Homework Statement

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

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?

 

[Dick]

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

 

[Moridin]

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

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 2^p 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 2^p subsets. Naturally, Q must contain 2^p + C number of subsets, where C is a unknown constant. For (2) to be true 2^p + C must be equal to 2^p+1. This seems to mean that the power set P' contains 2^p 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.

 

[rock.freak667]

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

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.

 

[Kurret]

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

 

[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)}.

 

[Moridin]

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

That would be 2^p?

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

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.

 

[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?

 

[Moridin]

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? [bb]So there are 2^p new subsets.[/b] What's 2^p+2^p?

That's 2^p+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?

 

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

 

[Moridin]

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

Of course. That makes sense. Thanks a bunch.