The Number Of Proper Subsets is 2^n - 1


by wubie
Tags: number, proper, subsets
wubie
#1
Jan14-04, 01:16 AM
P: n/a
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.
Phys.Org News Partner Science news on Phys.org
Better thermal-imaging lens from waste sulfur
Hackathon team's GoogolPlex gives Siri extra powers
Bright points in Sun's atmosphere mark patterns deep in its interior
himanshu121
himanshu121 is offline
#2
Jan14-04, 02:30 AM
himanshu121's Avatar
P: 661
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

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

To calculate the above use binomial Theorem
HallsofIvy
HallsofIvy is offline
#3
Jan14-04, 05:46 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,879
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
himanshu121 is offline
#4
Jan14-04, 05:55 AM
himanshu121's Avatar
P: 661

The Number Of Proper Subsets is 2^n - 1


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 2n just and i believe he wants the proof for it

And i have included the null set
Hurkyl
Hurkyl is offline
#5
Jan14-04, 06:29 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
Try induction.
himanshu121
himanshu121 is offline
#6
Jan14-04, 06:37 AM
himanshu121's Avatar
P: 661
For induction what i think is that one should know the function here as it is 2n-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
#7
Jan16-04, 01:31 AM
P: n/a
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
himanshu121 is offline
#8
Jan16-04, 05:48 AM
himanshu121's Avatar
P: 661
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).
[tex](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[/tex]

substitute x=1 in above equation u will get

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

so u have
[tex]2^n-1=C^n_1 + C^n_2+C^n_3+....C^n_{n-1}+1[/tex]
Hurkyl
Hurkyl is offline
#9
Jan16-04, 06:02 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
I mentioned induction becuase, 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
HallsofIvy is offline
#10
Jan16-04, 06:03 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,879
The empty set {} has only one subset: itself. 1=20
A set with one member: {a} has two subsets: the empty set and itself. 2= 21.
A set with two members: {a, b} has 4 subsets: {}, {a}, {b}, {a,b}. 4= 22.
A set with three members: {a, b, c} has 8 subsets: {}, {a}, {b}, {a,b} and {c}, {a,c}, {a, b, c}. 8= 23.

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 2n subsets:

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

Assume that a set with N elements has 2N 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?


Register to reply

Related Discussions
set contains elements that are *themselves* sets Set Theory, Logic, Probability, Statistics 2
Are these subsets subspaces? Calculus & Beyond Homework 8
subsets of R^n Calculus & Beyond Homework 26
Spanning and subsets Calculus & Beyond Homework 1
closed subsets Calculus & Beyond Homework 5