How to find the number of subsets in a set without writing all of them out?
How can you find the number of subsets in any set like $\{2, 4, 6, 8\}$ without writing out the subsets first including the empty set and the set itself?
I seriously need the shortcut to finding the number of subsets in a set without writing out every subset so I can find out the answers immediately.
$\endgroup$ 63 Answers
$\begingroup$Hint: An element is either in a subset or not. Now, given a finite set of $n$ elements, consider how many ways you can arrange a subset.
$\endgroup$ 1 $\begingroup$As probably hinted by now, perhaps you could prove your conjecture using induction? (was not sure if you needed a proof, not enough reputation to add onto an existing comment)
$\endgroup$ $\begingroup$Base case: We have the empty set as the set. The only subset of the empty set is itself. So, we have 1 subset for the empty set.
Recursion schema: Suppose that for for a set with n elements, the number of subsets it has is 2$^n$. Then for a set with (n+1) elements, we have one more choice for whether or not an element belongs to a subset or not. Since each element gives us 2 choices, we have twice the choices we had for all of the subsets of a set with n elements. Thus, for a set with (n+1) elements we have 2$^{(n+1)}$ subsets.
Therefore, for a set with a crisp indicator function, it has 2$^n$ possible subsets.
$\endgroup$ 1
