The Number Of Proper Subsets is 2^n - 1

[wubie]

Hello,

I am supposed to show that the number of proper subsets of S = {a1, a2, ... an} is 2^n - 1.

I know that the number of subsets of S is 2^n. And I know also know that the number of proper subsets of S is 2^n - 1 since S is not a proper subset of itself.

But how do I show that? I could show this by brute force. But I can't seem to think of a way to show it in a more efficient way.

 

[himanshu121]

i don't know whether u know Combinations So here it is

A set would not contain elements greater than n
So the set can have 0,1,2,3,4...(n-1) elements for it to be proper so u have total no of possible set as

$$=C^n_1 + C^n_2+C^n_3+...C^n_{n-1}+1(\mbox{ due to one null set})$$

To calculate the above use binomial Theorem

 

[HallsofIvy]

If you know the number of subsets is 2^n, then the number of proper subsets depends on the definition of "proper" subset doesn't it?

If it is true that there is only one subset that is not proper (the entire set itself), then, of course, you just subtract 1!

The only thing that seems confusing to me is that many authors consider the empty set to be not a proper set.

 

[himanshu121]

Originally posted by HallsofIvy
If you know the number of subsets is 2^n, then the number of proper subsets depends on the definition of "proper" subset doesn't it?

If it is true that there is only one subset that is not proper (the entire set itself), then, of course, you just subtract 1!

The only thing that seems confusing to me is that many authors consider the empty set to be not a proper set.

Halls I think Probably he knows it is 2ⁿ just and i believe he wants the proof for it

And i have included the null set

 

[Hurkyl]

Try induction.

 

[himanshu121]

For induction what i think is that one should know the function here as it is 2ⁿ-1 is known What if a person doesn't know it

So i believe the above reply which i posted is general which takes all the combination possible

 

[wubie]

Hello,

I am still having trouble with this. First I will post the question - it is question 24, page 13 of Schaum's Outlines: Modern Abstract Algebra by Frank Ayres Junior.

Show that the number of proper subsets of S = {a1, a2,..., an} is 2^n - 1.

Now I haven't done combinatrics for a long, long time. And when I was taking combinatorics I never did very well. But I still experimented with himanshu121's summation with combinations. I could see given a specific number of elements how the number of proper subsets was equal to 2^n - 1. But I still don't know how to express number of proper subsets for n elements.

Some notes:

At this point induction has not been introduced - it is introduced later on. So I would think that induction is not part of the solution. As well, there has been no mention of combinatorics. I would think the use of the binomial theorem is not part of the solution either. (Note: I wasn't able to see how to solve the above summation using the binomial therom anyway. If someone would like to show/guide me I would be very interested in seeing its application).

The only way I can think of solving this question is by using what was given:

The number of subsets of a set S with n elements is 2^n.

So using this information, knowing that the subset S ( S is a subset if itself) is not a proper subset, I can deduce that the total number of proper subsets is 2^n - 1 since all other subsets are not equal to S and therefore must be proper subsets by definition. (Yes, I know, this is pretty weak).

Any help on the above question is appreciated. I couldn't care less whether I hand it in or not. But it's frustrating not knowing how to do it. Especially since I have worked on it for some time and I won't get an answer for over a week at least. I am probably over analyzing the answer anway. But I would like to know a more formal way of doing it regardless.

 

[himanshu121]

Originally posted by wubie
As well, there has been no mention of combinatorics. I would think the use of the binomial theorem is not part of the solution either. (Note: I wasn't able to see how to solve the above summation using the binomial therom anyway. If someone would like to show/guide me I would be very interested in seeing its application).

$$(1+x)^n=C^n_0 + C^n_1x + C^n_2x^2+C^n_3x^3+...C^n_{n-1}x^{n-1}+C^n_nx^n$$

substitute x=1 in above equation u will get

$$2^n=1+C^n_1 + C^n_2+C^n_3+...C^n_{n-1}+1\mbox{(note: C^n_0=1)}$$

so u have
$$2^n-1=C^n_1 + C^n_2+C^n_3+...C^n_{n-1}+1$$

 

[Hurkyl]

I mentioned induction because, IMHO, it's the easiest way to solve this with full rigor.


The easiest proof to understand is to count subsets by looking at individual elements; there are two possibilities for each element, it's either in the subset or it's not, and since there are n elements...

 

[HallsofIvy]

The empty set {} has only one subset: itself. 1=2⁰
A set with one member: {a} has two subsets: the empty set and itself. 2= 2¹.
A set with two members: {a, b} has 4 subsets: {}, {a}, {b}, {a,b}. 4= 2².
A set with three members: {a, b, c} has 8 subsets: {}, {a}, {b}, {a,b} and {c}, {a,c}, {a, b, c}. 8= 2³.

Notice that in the last example I have first listed 4 sets that do not containing c and then the same 4 sets except that I have included c.

To prove, by induction, that a set containing n members has 2ⁿ subsets:

When n= 0, this is the empty set which has 1= 2⁰ subsets.

Assume that a set with N elements has 2^N subsets and calculate the number of subsets of a set, A, with N+1 elements as follows:

Choose a specific member of A (call it a).

(i) How many subsets are there that do not contain a?
(Hint: how many subsets does A-{a] have?)
(ii) How many subsets are there that do contain a?
(Hint: add a to each of the subsets in step (i).)
(iii) How many subsets are there altogether?