0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @quasi Yes, thank you very much. $\endgroup$ – Arnau Nov 22 '17 at 17:34
  • $\begingroup$ About the part $T = S \cup \{a\}$, that's just saying that if $T$ has $k+1$ elements, then for any element $a \in T$, the set $T$ is a union of a $k$ element set $S$ and $\{a\}$. $\endgroup$ – quasi Nov 22 '17 at 17:36
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.