A set with n elements has 2^n subsets I don't understand why a set with n elements has 2^n subsets. How is this calculated? I realize that {123} has empty set - 1-2-3-1,2-1,3-2,3-1,2,3 but how is the formula derived?
 A: When choosing elements to be in a subset, they are in or they are not. So each element has 2 choices available to it. If you have n elements of a set $ \implies 2^n$ subsets.
In addition, the number of subsets is equal to the sum of the binomial coefficients, and it is well-known that $\sum^{n}_{k=0}\binom{n}{k}=2^n$
A: A n-sized set can have subsets of sizes anywhere from 0 to n.
So there are:
$\displaystyle \sum_{i=0}^n \binom{n}{i} = 2^n$ ways to make such subsets.
Alternatively think of it as either taking or not taking each of the n elements.
A: If you look at functions
$$f:S\to \{0,1\}$$
you see that $f^{-1}(1)$ is a unique subset completely determined by $f$. So the number of subsets is just the number of functions from a set with $n$ elements to a set with $2$ elements, i.e. $2^n$.
A: The key point here is that you can select any number of elements 
So to select one element we have C(n, 1) number of ways.
Similarly selecting two elements from the set can be done in C(n, 2).
..
..
..
Similarly selecting n elements from the set of n elements is C(n, n) ways.
Also you can select an empty set or a set with no elements and this can be done only in one way.
Now summing all these ways you can observe that these are summation of binomial coefficients whose sum is given by $(1+x)^ n$ where $x=1$ hence $2^n$.
Hope this helped.
A: Suppose your set's $n$ elements are the distinct points $x_0,x_1,\ldots,x_{n-1}$.
Think of all the $n$-digit binary numbers you can form, which will all be of the form $a_{n-1}a_{n-2}\cdots a_1a_0$, where each $a_i$ is zero or one. There are exactly $2^n$ distinct values representable by such $n$-bit numbers. That's because there are 2 choices for each bit, and $n$ bits to populate, giving a total of $\underbrace{2\cdot 2\cdot \cdots \cdot 2}_{n\textrm{ factors}}$ distinct values.
For example, if $n=2$, the binary numbers are 00, 01, 10, and 11, a total of $2^2=4$ distinct values.
Now just make a correspondence between these values and the subsets of your set by declaring the point $x_i$ to be in the subset if and only if the bit $a_i$ is one.
A: It's most intuitively proved using mathematical induction.
First, let's construct our base case. A set with n =1 elements, e.g $S_1 = \{x_1\}$
, clearly has only two subsets; $S_1$ and the empty set $\phi$. Thus it obeys our rule of $2^n$, as $2^1$ = 2.
To use induction, now we want to show if some given set with $n$ elements has $2^n$ elements, then a set with $n + 1$ elements has $2^{n+1}$ elements. The answer is pretty clear after some thinking.
Let $S_n = \{x_1, x_2, x_3, .... x_n\}$ with $2^n$ subsets, i.e $\{x_1, x_2\}$, $\{x_2, x_3\}$, $\{x_1, x_3\}$, $\{x_1\}$, $\{x_2\}$, $\phi$, $S_n$ .....
Now, $S_{n+1}$ contains one more element, $x_{n+1}$. That means that for every one of those $2^n$ subsets earlier, we have a "new version" of it which includes $x_{n+1}$. Since there are now 2 versions of each of the subsets in $S_n$, the new amount of subsets in $S_{n+1}$ is $2 \cdot 2^n = 2^{n+1}$
This together with our base case proves that a set $S$ with $n \in  \mathbb{N}$ elements contains $2^n$ distinct subsets.
