alleryStart learning →The POWER SET of a set with $n$ elements has
A$n$ subsets
B$n^2$ subsets
C$2n$ subsets
D$2^n$ subsets
Answer & Solution
Correct answer: D. $2^n$ subsets
1. Power set $P(S)$: the set of ALL subsets of $S$ (including $\emptyset$ and $S$ itself).
2. Each element of $S$ has 2 choices for any subset: included or excluded.
3. So the total number of subsets is $2 \cdot 2 \cdots 2 = 2^n$.
4. Example: $S = \{a, b, c\}$ has $2^3 = 8$ subsets: $\emptyset, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}$. ✓
5. Other options are wrong counts.
_Source: Oscar Levin, "Discrete Mathematics: An Open Introduction", §0.4 (Sets — power set)._
Keep practising Discrete Mathematics
Browse all Discrete Mathematics questions for GATE CSE, or explore more Computer Science topics.
Related questions
A PREDICATE $P(x)$ isHow many ways to put 10 IDENTICAL balls into 4 DISTINCT boxes (each box can hold 0 or moreHow many DIFFERENT subsets of size 3 can be selected from a set of 7 elements?In how many ways can 7 people sit in a ROW?$\binom{n}{k} = \binom{n}{n-k}$. This identity reflectsHow many DIFFERENT 5-bit binary strings are there?A function $f: A \to B$ is INJECTIVE (one-to-one) if$|A \cup B|$ (size of union) equals