Register to reply

The Number Of Proper Subsets is 2^n - 1

by wubie
Tags: number, proper, subsets
Share this thread:
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
Fungus deadly to AIDS patients found to grow on trees
Canola genome sequence reveals evolutionary 'love triangle'
Scientists uncover clues to role of magnetism in iron-based superconductors
himanshu121
#2
Jan14-04, 02:30 AM
himanshu121's Avatar
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.....(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
#3
Jan14-04, 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.

himanshu121
#4
Jan14-04, 05:55 AM
himanshu121's Avatar
P: 658
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
#5
Jan14-04, 06:29 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,091
Try induction.
himanshu121
#6
Jan14-04, 06:37 AM
himanshu121's Avatar
P: 658
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
#8
Jan16-04, 05:48 AM
himanshu121's Avatar
P: 658
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
#9
Jan16-04, 06:02 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
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...
HallsofIvy
#10
Jan16-04, 06:03 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,502
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