Question

Prove that the number of subsets of a set containing n distinct elements is 2ⁿ, for all n $\in$ N. [NCERT EXEMPLAR]

Answer 1

$$\begin{gathered} \mathrm{Let}\mathrm{the}\mathrm{given}\mathrm{statement}\mathrm{be}\mathrm{defined}\mathrm{as}\mathrm{P}\left(n\right):\mathrm{The}\mathrm{number}\mathrm{of}\mathrm{subsets}\mathrm{of}\mathrm{a}\mathrm{set}\mathrm{containing}n\mathrm{distinct}\mathrm{elements}=2^n,\mathrm{for}\mathrm{all}n\in \mathbf{N}. \\ \mathrm{Step}\mathrm{I}:\mathrm{For}n=1, \\ \mathrm{LHS}=\mathrm{As},\mathrm{the}\mathrm{subsets}\mathrm{of}\mathrm{a}\mathrm{set}\mathrm{containing}\mathrm{only}1\mathrm{element}\mathrm{are}:\mathrm{\varphi }\mathrm{and}\mathrm{the}\mathrm{set}\mathrm{itself}. \\ \mathrm{i}.\mathrm{e}.\mathrm{the}\mathrm{number}\mathrm{of}\mathrm{subsets}\mathrm{of}\mathrm{a}\mathrm{set}\mathrm{containing}\mathrm{only}1\mathrm{element}=2 \\ \mathrm{RHS}=2^1=2 \\ \mathrm{As},\mathrm{LHS}=\mathrm{RHS} \\ \mathrm{So},\mathrm{it}\mathrm{is}\mathrm{true}\mathrm{for}n=1. \\ \mathrm{Step}\mathrm{II}:\mathrm{For}n=k, \\ \mathrm{Let}\mathrm{P}\left(k\right):\mathrm{The}\mathrm{number}\mathrm{of}\mathrm{subsets}\mathrm{of}\mathrm{a}\mathrm{set}\mathrm{containing}k\mathrm{distinct}\mathrm{elements}=2^k,\mathrm{be}\mathrm{true}\mathrm{for}\mathrm{some}k\in \mathbf{N}. \\ \mathrm{Step}\mathrm{III}:\mathrm{For}n=k+1, \\ \mathrm{P}\left(k+1\right): \\ \mathrm{Let}A=\left\{a_1,a_2,a_3,...,a_k,b\right\}\mathrm{so}\mathrm{that}A\mathrm{has}\left(k+1\right)\mathrm{elements}. \\ \mathrm{So},\mathrm{the}\mathrm{subset}\mathrm{of}A\mathrm{can}\mathrm{be}\mathrm{divided}\mathrm{into}\mathrm{two}\mathrm{collections};\mathrm{first}\mathrm{contains}\mathrm{subsets}\mathrm{of}A\mathrm{which}\mathrm{don}\text{'}\mathrm{t}\mathrm{have}b\mathrm{in}\mathrm{them}\mathrm{and} \\ \mathrm{the}\mathrm{second}\mathrm{contains}\mathrm{subsets}\mathrm{of}A\mathrm{which}\mathrm{do}\mathrm{have}b\mathrm{in}\mathrm{them}. \\ \mathrm{i}.\mathrm{e}. \\ \mathrm{First}\mathrm{collection}:\left\{\right\},\left\{a_1\right\},\left\{a_1,a_2\right\},\left\{a_1,a_2,a_3\right\},...,\left\{a_1,a_2,a_3,...,a_k\right\}\mathrm{and} \\ \mathrm{Second}\mathrm{collection}:\left\{b\right\},\left\{a_1,b\right\},\left\{a_1,a_2,\right\},\left\{a_1,a_2,a_3,b\right\},...,\left\{a_1,a_2,a_3,...,a_k,b\right\} \\ \mathrm{It}\mathrm{can}\mathrm{be}\mathrm{clearly}\mathrm{seen}\mathrm{that}: \\ \mathrm{The}\mathrm{number}\mathrm{of}\mathrm{subsets}\mathrm{of}A\mathrm{in}\mathrm{first}\mathrm{collection}=\mathrm{The}\mathrm{number}\mathrm{of}\mathrm{subsets}\mathrm{of}\mathrm{set}\mathrm{with}k\mathrm{elements}\mathrm{i}.\mathrm{e}.\left\{a_1,a_2,a_3,...,a_k\right\}=2^k\left(\mathrm{Using}\mathrm{step}\mathrm{II}\right) \\ \mathrm{Also},\mathrm{it}\mathrm{follows}\mathrm{that}\mathrm{the}\mathrm{second}\mathrm{collection}\mathrm{must}\mathrm{have}\mathrm{the}\mathrm{same}\mathrm{number}\mathrm{of}\mathrm{the}\mathrm{subsets}\mathrm{as}\mathrm{that}\mathrm{of}\mathrm{the}\mathrm{first}=2^k \\ \mathrm{So},\mathrm{the}\mathrm{total}\mathrm{number}\mathrm{of}\mathrm{subsets}\mathrm{of}A=2^k+2^k=2\times 2^k=2^{k+1}. \end{gathered}$$

Hence, the number of subsets of a set containing n distinct elements is 2ⁿ, for all n $\in$ N.