I don't understand this exercise of mathematical induction. I also have the answer but I still don't get it. The exercise says the following:
Use mathematical induction to show that if $S$
is a finite set with n elements, then $S$ has $2^{n}$ subsets.
And the answer is:
BASIS STEP: $P(0)$ is true, since a set with zero elements, the empty set, has exactly
$2^0 = 1$ subsets, since it has one subset, namely, itself.INDUCTIVE STEP: Assume that $P(k)$ is true, that is, that every set with $k$ elements has $2^k$ subsets. It must be shown that under this assumption $P(k + 1)$, which is the statement that every set with $k + 1$ elements has $2^{k+1}$ subsets, must also be true.
To show this, let $T$
be a set with $k + 1$ elements. Then, it is possible to write $T = S ∪ \{a\}$ where $a$ is one of the elements of $T$ and $S = T – \{a\}$. The subsets of $T$ can be obtained in the following way. For each subset $X$ of $S$ there are exactly two subsets of $T$, namely, $X$ and $X ∪ \{a\}$. These constitute all the subsets of $T$ and are all distinct. Since there are $2^k$ subsets of $S$, there are $2 · 2^k$ = $2^{k+1}$ subsets of $T$.
I understand everything up to 'which is the statement that every set with k+1 elements has $2^{k+1}$ subsets, must also be true'. I know that we start by evaluating the first element P(0) to see if it's true and we try to show that P(k) is true to then show that P(k+1). But I don't get the part in which T is the union of S and {a} and so on.
Does anyone understand this? Thank you.
Best Answer
Let $A=\{Y\subset T \}$ and $B=C\cup D$ where $C=\{X\cup \{a\}:X\subset S\}$ and $ D= \{X\subset S\}$
$A=B$, and $C$ and $D$ are disjoint and contain the same number of elements, which is $2^k$ by induction.