Register to reply 
The Number Of Proper Subsets is 2^n  1 
Share this thread: 
#1
Jan1404, 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. 


#2
Jan1404, 02:30 AM

P: 658

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.....(n1) 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_{n1}+1(\mbox{ due to one null set})[/tex] To calculate the above use binomial Theorem 


#3
Jan1404, 05:46 AM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,502

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. 


#4
Jan1404, 05:55 AM

P: 658

The Number Of Proper Subsets is 2^n  1
And i have included the null set 


#6
Jan1404, 06:37 AM

P: 658

For induction what i think is that one should know the function here as it is 2^{n}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 


#7
Jan1604, 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. 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. 


#8
Jan1604, 05:48 AM

P: 658

substitute x=1 in above equation u will get [tex]2^n=1+C^n_1 + C^n_2+C^n_3+....C^n_{n1}+1\mbox{(note: C^n_0=1)}[/tex] so u have [tex]2^n1=C^n_1 + C^n_2+C^n_3+....C^n_{n1}+1[/tex] 


#9
Jan1604, 06:02 AM

Emeritus
Sci Advisor
PF Gold
P: 16,091

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


#10
Jan1604, 06:03 AM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,502

The empty set {} has only one subset: itself. 1=2^{0}
A set with one member: {a} has two subsets: the empty set and itself. 2= 2^{1}. A set with two members: {a, b} has 4 subsets: {}, {a}, {b}, {a,b}. 4= 2^{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^{3}. 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^{n} subsets: When n= 0, this is the empty set which has 1= 2^{0} 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? 


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 