Show that if $S$ is a finite set with n elements, then $S$ has $2^n$ subsets by using mathematical induction

Question

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.

Answer 1

An example might help . . .

Suppose $k = 3$.

Let $T$ be a set of $4$ elements, say $T = \{a,b,c,d\}$.

Then $T = S \cup \{a\}$, where $S = \{b,c,d\}$ is a set of $3$ elements.

Suppose we've already shown that any set with $3$ elements has $2^3 = 8$ subsets. Thus, we know that $S$ has $8$ subsets.

Each subset of $S$ is also a subset of $T$, so $T$ has those $8$ subsets to begin with.

But for each of the $8$ subsets of $S$, there is a new subset of $T$ obtained by including the element $a$ as an additional element. That yields $8$ more subsets.

Thus, $T$ has $2^3 + 2^3 = 2\cdot 2^3 = 2^4$ subsets.

Answer 2

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.

Answer 3

Well that is because, you will use the inductive hypotesis.

So, if you want to prove $P(k+1)$, then the set must have $k+1$ elements.

They named that set $T$

So if you take $k$ elements of $T$ and build the subset $S$ with those $k$ elements, then $T = S \cup $ { $a$ } where $a$ is the element that was not among the chosen $k$