# How many subsets are there in a set of size $n$? No combinatorics

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.

• Try induction, perhaps. – akkkk Sep 12 '12 at 16:28
• Look her for induction:math.stackexchange.com/questions/44908/… – Lucien Sep 12 '12 at 16:32
• Actually, if you only know set theory, you will define $m^n$ to be (the cardinality of) the set of maps from your favorite $n$-element set to your favorite $m$-element set. With $m=2=\{0,1\}$ you can identify $A\subseteq n$ with the map $f:n\to2$ such that $f(x)=1\iff x\in A$. – Hagen von Eitzen Sep 12 '12 at 16:34
• @Dario - I'm still puzzled by the question. You are trying to count something. One of the cornerstones of combinatorics is counting. I think Hagen's comment is exceptional in its clarity and succinctness, but it uses (elementary) counting to get the result. Is this OK with you? You cannot avoid counting entirely, I don't think. – Chris Leary Sep 12 '12 at 16:46
• @DaríoVerta None of the answers given uses the binomial theorem, and I don't think it would be standard to prove it that way. – Trevor Wilson Sep 12 '12 at 17:00

## 6 Answers

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

• Thanks but I don't understand how you got to the bijection. – Casquibaldo Sep 12 '12 at 16:52
• @DaríoVerta Given the tuple, you can write down the set it corresponds to by noting where the 1's are in the tuple. Conversely, given the set with numbered elements, you can write down the tuple by putting 1's in the spots corresponding to the objects you have. – rschwieb Sep 12 '12 at 16:57
• Oh ok, this seems to be satisfactory (at least to me). This is greatly appreciated. – Casquibaldo Sep 12 '12 at 17:00

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.

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.

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

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.

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