distinct subsets. Induction
Problem: If S is a finite set with n elements, then S has
distinct subsets.
Proof:
Basis Step: If n = 0, then 
. Hence it has exactly one
subset, namely 
. Since 
, the statement holds for n = 0.
Induction: Assume that a set with n elements has distinct subsets.
----- Induction Hypothesis
To prove that this holds for n+1, first try to express the number of subsets of
S of size n+1 in terms of that of a set of size n
so that the induction hypothesis can be used.
For that we use the following claim without a rigorous proof.
Claim: | 
(T) |
= 2 * | (S) | , if T is obtained from S
by adding one more element, where
(A)
denotes the powerset of a set A .
Let us
illustrate the basic idea of this claim with a simple example.
Let 
. Then the subsets of S are , 
, 
,
and 
. These subsets can be grouped into two groups: and
in one group, and and in the other. The sets in the
first group do not contain 2 while the ones in the second group contain 2.
Also there is an obvious bijection between these two groups: Adding the element 2
to each
set in the first group produces a unique set in the second group, and deleting 2 from
each set of the second group produces a unique set in the first group.
Furthermore the sets of the first group are the subsets of that is
. Thus the subsets of S have been expressed in terms of the subsets of
and
S can be seen to have twice as many subsets as .
The proof of the inductive step is a straightforward application of this
claim.
Let S be a set with n+1 elements and let x be an arbitrary element of S.
(T)
denote the set of subsets of a set T .
Then a set in (S) not containing x is a member of
,
and conversely,
a member of
is a member of (S) that does not contain x.
Also
a set in (S) containing x is a member of
with x
and conversely,
a member of
plus x
is a member of (S) that contains x.
Thus altogether there are twice as many sets in
(S)
as in
.
But by the induction hypothesis
has elements. Hence S has 
subsets.
End of Proof