7
$\begingroup$

Prove that a set of size $n$ contains $2^n$ subsets without the binomial expansion. (Suppose you were starting out with only knowledge of set theory). This has been bugging me for a while so help is appreciated.

  • 0
    @TrevorWilson Fortunately none of them use the binomial theorem, but I had been presented a proof with it and thought it was not satisfactory. This is why I initially requested for people not to consider it (if they were previously inclined to do so) so as to not waste people's time. I am sorry if I am erred in thinking that it was the standard way to prove it. Again, it was merely the only proof I had seen.2012-09-12

6 Answers 6

9

Consider the tuples in $2^n$ to represent subsets of the set $X$ of $n$ objects in the following way.

Interpret a 1 in the $n$th position as "object number $n$ is in this set," and a 0 in the $n$th position as "object number $n$ is not in the set."

Clearly this forms a bijection between $\mathcal{P}(X)$ and $2^n$.

  • 1
    Oh ok, this seems to be satisfactory (at least to me). This is greatly appreciated.2012-09-12
7

The empty set has only itself as a subset. Obviously a set with 1 element has $2^1$ subsets, itself and the empty set.

Assume that a set $A$ with $n$ elements has $2^n$ subsets. Let $A'=A\cup\{x\}$ (with $x\not\in A$). This new set has $n+1$ elements. All the subsets of $A$ are also subsets of $A'$. In addition each subset of $A$ with $x$ added is also a subset. In other words, for each $B\subseteq A$ both $B\subseteq A'$ and $B\cup\{x\} \subseteq A'$. Therefore $A'$ has $2\cdot 2^n = 2^{n+1}$ subsets.

4

To define a subset, you need to know exactly which elements of the set are in the subset. That is, for each element of the set, is it in the subset or not? So the subset is the answer to a series of $n$ yes-or-no questions. There are $2^n$ ways to answer.

1

The proof becomes obvious if considering a "set" of $n$ binary digits.

The trivial case is the empty set (no bits); there is one such set which is its own subset. With a maximum of one unique bit, that bit may be present or it may be not, thus there are two possible subsets of the set of one bit (the set of that one bit and the empty set). For increasing numbers of bits, each of those bits may be present or it may be not. We can (and most commonly do) identify these bits by their "place" in the set of all bits; $1,2,3... n$. We may then (and most commonly we do) assign a zero-based power of two to each bit: the bit in place 1 represents $2^0$, the bit in place 2 $2^1$, and so on, such that the $n$th bit has the power value $2^{n-1}$.

Now, every unique subset of bits can be summed in terms of their powers. If no bits are present, we have the empty set. If we have only one bit, no matter which bit, the "value" of the set is the value of the power of two assigned to that bit. if we have multiple unique bits, we sum those values to produce a unique value. The maximum possible set value, that is, the sum of the values of each bit in the set of all bits, is $2^0 + 2^1 + 2^2+...+2^{n-1} = 2^n-1$. Adding the empty set (value 0), the cardinality of the set of all sets of $n$ elements is $2^n$.

0

Okay so think of the elements of your set as being numbers 1,2,...,n.

To define a subset you have to tell me which elements (if any) you are gonna include in your subset. Now, a refined way to point fingers is to mark the chosen elements as 1 and to mark the discarded ones as 0. So, our problem is to count how many different sequences, of length n, of zeros and ones can be constructed.

Starting from the left, you have two independent choices at every place (choose zero or one) so you have $2^{n}$ such sequences.

0

Let be $ A_n=\{a_1,a_2,...,a_n\}$ a n-set and $P(A_n)$ the set of all subsets of set $A_n$ For each subset $B$ of $A_n$ we defines a number

$g_B=\sum_{a_{j}\ in B} 2^j$

that is called binary code of subset and this number may take values from 0 for empty subset to $2^{n-1}$ for entire set $A_n$. In that manner we realize a bijection from set of all subsets of $A_n$ into set $\{0,1,2,...,2^{n-1}\}$ that obviousley has $2^n$ elements