# Thread: Survey of Mathmatics Question

1. ## Survey of Mathmatics Question

Hi everyone. I am a newbie here. I am taking an online math class, so I am pretty much on my own. It is Survey of Mathmatics. I hope someone can help me with this one problem.

Calculate the number of subsets for the set, then calculate the number of proper subsets,
{x l x e N and x lies between 8 and 12}

The e should be a sign for element but I can't make that.
Mirage20

2. Originally Posted by mirage20
Hi everyone. I am a newbie here. I am taking an online math class, so I am pretty much on my own. It is Survey of Mathmatics. I hope someone can help me with this one problem.

Calculate the number of subsets for the set, then calculate the number of proper subsets,
{x l x e N and x lies between 8 and 12}

The e should be a sign for element but I can't make that.
Mirage20
first, let's write out the elements of the set. there's not that much

the set is {9,10,11}

now the number of subsets of a set is given by $\displaystyle 2^n$, where $\displaystyle n$ is the number of elements in the set.

the number of proper subsets is given by $\displaystyle 2^n - 1$

Can you take it from here?

3. Originally Posted by mirage20
Hi everyone. I am a newbie here. I am taking an online math class, so I am pretty much on my own. It is Survey of Mathmatics. I hope someone can help me with this one problem.

Calculate the number of subsets for the set, then calculate the number of proper subsets,
{x l x e N and x lies between 8 and 12}

The e should be a sign for element but I can't make that.
Mirage20
Originally Posted by Jhevon
first, let's write out the elements of the set. there's not that much

the set is {9,10,11}

now the number of subsets of a set is given by $\displaystyle 2^n$, where $\displaystyle n$ is the number of elements in the set.

the number of proper subsets is given by $\displaystyle 2^n - 1$

Can you take it from here?
What Jhevon says is correct but he provides no explanation. The reason that there are $\displaystyle 2^n$ subsets of a set with $\displaystyle n$ elements is that each element of the set may be in or out of a sunset, so we may label each element with a $\displaystyle 1$ if it is in the sunset or $\displaystyle 0$ if it is out. Thus these are two possible labellings for each element and so $\displaystyle 2^n$ possible different labellings for the elements of the set and so $\displaystyle 2^n$ different subsets.

There are $\displaystyle 2^n-1$ proper subsets because all but one of the subsets are proper (only the subset which is the set itself is not a proper subset).

RonL

RonL

4. We can also prove this by induction.
Say that $\displaystyle \{1,2,...,n\}$ has $\displaystyle 2^n$ subsets. Then we will show use this to show that $\displaystyle \{1,2,...,n,n+1\}$ has $\displaystyle 2^{n+1}$ subsets.
----

Given, $\displaystyle \{1,2,...,n,n+1\}$. Included in all the subsets of this set are all the subsets of $\displaystyle \{1,2,...,n\}$ which is $\displaystyle 2^n$ by the induction step.
Now it remains to count the number of subsets having $\displaystyle n+1$. We can have have the following:
$\displaystyle \{ \{ n+1 \} \} = {n\choose 0}$
$\displaystyle \{ \{ n+1, 1 \} , \{ n+1, 2 \} , \{ n+1, 3\} ,,, \{ n+1,n \} \} = {n\choose 1}$

$\displaystyle \{ \{n+1,1,2\}, \{n+1,1,3\}, ... ,\{n+1,n-1,n\} = {n\choose 2 }$.
.....
$\displaystyle \{\{1,2,...,n,n+1\}\} = { n\choose n}$

So in total we have,
$\displaystyle {n\choose 0} + {n\choose 1} + .... + {n\choose n} = 2^n$

Thus, in overall total we have,
$\displaystyle 2^n + 2^n = 2\cdot 2^n = 2^{n+1}$
And induction is complete.