Hi
My question is
Prove by induction that if A has n elements, then has elements.
thanks
If we do it by induction, we have only number to consider, but Drexel suggested it by number of ways to partition, in which case the empty set must be added into consideration, which is why he said instead of .
If the empty set is not considered, we will end up getting , instead of .
By induction, we need to name the set. Let be the set such that
By induction, we can begin with the base case, n=0, where is the only member, i.e. When , contains members. The subscript denotes the number of elements in the set .
Next, assume it is true that the set containing members, written to have the Power set containing .
The prove contain members.
We know contains number of elements. Since , we need to introduce an element that is not in , say so that
The set will have additional members that look like this:
which gives an additional members to the original set, .
I just cannot see how this can be considered proof by induction. It seems to me that by partitioning we get to it by binomial theorem. I cannot see where the goes.
The only way I can think off is as follows:
Let be a set of elements, then in the Power set there are:
number of { }
number of singleton sets, {1}, {2}, {3}, ....{n}
number of doublets, {1,2}, {1,3}, {1,4}, ....{n}
number of triplets, {1,2,3}, {1,2,4}, {1,2,5}, ....{n}
.
.
.
number of { }
All together , where and
I know for sure that my method is not by induction.
Drexel, I am think of a different thing?
Theorem: For a finite set with we have that
Proof: Let be the number of subsets of . Consider the set . Partition into two cells where contains all subsets of such that
and . Evidently, we have that is the number of subsets one can form from which is . We have two choices for the elements , either
or it contains some element of . Clearly, the latter case tells us that there is an element of for each non-empty subset in which is . And, it clearly follows that the number
of elements of is the with the addition of so that . Thus, . But,
, so that . This is a simple linear homogeneous recurrence relation with solution for some constant. But, seeing that is the
number of subsets of which is zero we see that from where it follows that . The conclusion follows since any set of elements is, by definition, equipotent to
.
Remark: The induction was implicitly used in solving the recurrence relation.
We don't necessary have to make things overcomplicated:
Let
Step 1.
card is satisfied.
step 2. Fix some . Assume for all we have card( .
From we can construct . Namely by doing the following:
Let .
Let :
1. Add a copy of in .
2. Take another copy of and let and add it to .
We don't have to sit here and discuss for hours that we constructed .
Now evidently card card by the induction hypothesis.
step 3. By induction follows from step 1+step 2 that for all we have card
Well I clearly hold to the induction-procedure ;p
Aside from that, I took some extra unnecessary steps and construct an extra Set P.
However from the induction-hypothesis and the observation that for every element of we can choose to add or not add an extra element N+1, the conclusion follows.
I think that's clearly more straightforward approach.