Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Math Help - proof by induction question involving power set

  1. #1
    Member
    Joined
    Sep 2005
    Posts
    84

    proof by induction question involving power set

    Hi

    My question is
    Prove by induction that if A has n elements, then P(A) has 2^{n}elements.


    thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by rpatel View Post
    Hi

    My question is
    Prove by induction that if A has n elements, then P(A) has 2^{n}elements.


    thanks
    Hint: Find a recurrence relation. Call p(n) the number of things in a set with n elements and then partition a set containing n+1 elements into two blocks. Those the contain n+1 and those that don't.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Drexel28 View Post
    Hint: Find a recurrence relation. Call p(n) the number of things in a set with n elements and then partition a set containing n+1 elements into two blocks. Those the contain n+1 and those that don't.
    Very clever!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    For every x\in P(n) we have 2 choices: Do we add n+1\in x or not.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2005
    Posts
    84
    how do i partition the set ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Dinkydoe View Post
    For every x\in P(n) we have 2 choices: Do we add n+1\in x or not.
    If we do it by induction, we have only n number to consider, but Drexel suggested it by number of ways to partition, in which case the empty set \emptyset must be added into consideration, which is why he said n+1 instead of n.



    If the empty set is not considered, we will end up getting 2^{n-1} - 1, instead of 2^n.

    By induction, we need to name the set. Let A be the set such that x \in A

    By induction, we can begin with the base case, n=0, where \emptyset is the only member, i.e. When n= 0, P(A_0) contains 2^n = 2^0 = 1 members. The subscript denotes the number of elements in the set A.

    Next, assume it is true that the set A containing n members, written A_n to have the Power set containing 2^n.

    The prove P(A_{n+1}) contain 2^{n+1} members.

    We know P(A_n) contains n number of elements. Since x \in A, we need to introduce an element that is not in A, say y \notin A so that

     <br />
P(A_{n+1}) = P(A_n \cup \{y\})<br />

    The set P(A_n \cup \{y\}) will have additional members that look like this:

    \{\{\emptyset \} \cup \{y\}, \{1\} \cup \{y\}, \{2\} \cup \{y\}, ......\{......(n-2),(n-1),n\} \cup \{y\}\} which gives an additional 2^n members to the original set, P(A) .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by rpatel View Post
    how do i partition the set ?
    If A = {a,b,c,d} and we want to partition it into 2 groups, it will look like {a|b,c,d} or {a,b|c,d}. To partition it into 3 groups, it will become {a|b|c,d} or {a,b|c|d} or {a|b,c|d} or {a,b|c|d}.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Drexel28 View Post
    Hint: Find a recurrence relation. Call p(n) the number of things in a set with n elements and then partition a set containing n+1 elements into two blocks. Those the contain n+1 and those that don't.
    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 n+1 goes.

    The only way I can think off is as follows:

    Let A be a set of  n elements, then in the Power set P(A) there are:


    \binom{n}{0} number of { \emptyset }
    \binom{n}{1} number of singleton sets, {1}, {2}, {3}, ....{n}
    \binom{n}{2} number of doublets, {1,2}, {1,3}, {1,4}, ....{n}
    \binom{n}{3} number of triplets, {1,2,3}, {1,2,4}, {1,2,5}, ....{n}

    .
    .
    .
    \binom{n}{n} number of { A}

    All together |P(A_n)| =\Sigma_{i=0}^n \binom{n}{i}a^i b^{n-i}= 2^n, where a = 1 and b=1

    I know for sure that my method is not by induction.
    Drexel, I am think of a different thing?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by novice View Post
    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 n+1 goes.


    I know for sure that my method is not by induction.
    Drexel, I am think of a different thing?
    Theorem: For a finite set E with \text{card }E=n we have that \text{card }\wp\left(E\right)=2^n

    Proof: Let p(n) be the number of subsets of \left\{1,\cdots,n\right\}. Consider the set \left\{1,\cdots,n,n+1\right\}=E'. Partition E' into two cells B_1,B_2 where B_1 contains all subsets S of \left\{1,\cdots,n,n+1\right\} such that

    n+1\notin S and B_2=E'-B_1. Evidently, we have that \text{card }B_1 is the number of subsets one can form from \left\{1,\cdots,n\right\} which is p(n). We have two choices for the elements S', either S'=\{n+1\}

    or it contains some element of \{1,\cdots,n\}. Clearly, the latter case tells us that there is an element of B_2 for each non-empty subset in B_1 which is p(n)-1. And, it clearly follows that the number

    of elements of B_2 is the p(n)-1 with the addition of \{n+1\} so that \text{card }B_2=p(n). Thus, \text{card}\{1,\cdots,n,n+1\}=\text{card }B_1+\text{card }B_2=p(n)+p(n)=2p(n). But,

    \text{card }\left\{1,\cdots,n,n+1\right\}=p(n+1), so that p(n+1)=2p(n). This is a simple linear homogeneous recurrence relation with solution p(n)=C\cdot 2^n for some constant. But, seeing that p(0) is the

    number of subsets of \varnothing which is zero we see that 1=p(0)=C\cdot2^0=C from where it follows that p(n)=2^n. The conclusion follows since any set of n elements is, by definition, equipotent to

    \left\{1,\cdots,n\right\}. \blacksquare

    Remark: The induction was implicitly used in solving the recurrence relation.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Drexel28 View Post
    Theorem: For a finite set E with \text{card }E=n we have that \text{card }\wp\left(E\right)=2^n

    Proof: Let p(n) be the number of subsets of \left\{1,\cdots,n\right\}. Consider the set \left\{1,\cdots,n,n+1\right\}=E'. Partition E' into two cells B_1,B_2 where B_1 contains all subsets S of \left\{1,\cdots,n,n+1\right\} such that

    n+1\notin S and B_2=E'-B_1. Evidently, we have that \text{card }B_1 is the number of subsets one can form from \left\{1,\cdots,n\right\} which is p(n). We have two choices for the elements S', either S'=\{n+1\}

    or it contains some element of \{1,\cdots,n\}. Clearly, the latter case tells us that there is an element of B_2 for each non-empty subset in B_1 which is p(n)-1. And, it clearly follows that the number

    of elements of B_2 is the p(n)-1 with the addition of \{n+1\} so that \text{card }B_2=p(n). Thus, \text{card}\{1,\cdots,n,n+1\}=\text{card }B_1+\text{card }B_2=p(n)+p(n)=2p(n). But,

    \text{card }\left\{1,\cdots,n,n+1\right\}=p(n+1), so that p(n+1)=2p(n). This is a simple linear homogeneous recurrence relation with solution p(n)=C\cdot 2^n for some constant. But, seeing that p(0) is the

    number of subsets of \varnothing which is zero we see that 1=p(0)=C\cdot2^0=C from where it follows that p(n)=2^n. The conclusion follows since any set of n elements is, by definition, equipotent to

    \left\{1,\cdots,n\right\}. \blacksquare

    Remark: The induction was implicitly used in solving the recurrence relation.
    Aha, I got it now after staring at it and pulling my hair.

    You are a genius! Wow!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    We don't necessary have to make things overcomplicated:
    Let A_n = \left\{1,\cdots ,n \right\}

    Step 1.

    card \mathcal{P}(A_0))= 2^0 = 1 is satisfied.

    step 2. Fix some N > 0. Assume for all n \leq N we have card( \mathcal{P}(A_n)) = 2^n.

    From \mathcal{P}(A_n) we can construct \mathcal{P}(A_{n+1}). Namely by doing the following:
    Let P = \emptyset .

    Let S \in\mathcal{P}(A_n):

    1. Add a copy of S in P.
    2. Take another copy of S and let n+1\in S and add it to P.

    We don't have to sit here and discuss for hours that we constructed P = \mathcal{P}(A_{N+1}).

    Now evidently card \mathcal{P}(A_{N+1}) = 2\cdot card \mathcal{P}(A_N) = 2\cdot 2^N = 2^{N+1} by the induction hypothesis.

    step 3. By induction follows from step 1+step 2 that for all n\in \mathbb{N} we have card \mathcal{P}(A_n) = 2^n
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Dinkydoe View Post
    We don't necessary have to make things overcomplicated:
    Let A_n = \left\{1,\cdots ,n \right\}

    Step 1.

    card \mathcal{P}(A_0))= 2^0 = 1 is satisfied.

    step 2. Fix some N > 0. Assume for all n \leq N we have card( \mathcal{P}(A_n)) = 2^n.

    From \mathcal{P}(A_n) we can construct \mathcal{P}(A_{n+1}). Namely by doing the following:
    Let P = \emptyset .

    Let S \in\mathcal{P}(A_n):

    1. Add a copy of S in P.
    2. Take another copy of S and let n+1\in S and add it to P.

    We don't have to sit here and discuss for hours that we constructed P = \mathcal{P}(A_{N+1}).

    Now evidently card \mathcal{P}(A_{N+1}) = 2\cdot card \mathcal{P}(A_N) = 2\cdot 2^N = 2^{N+1} by the induction hypothesis.

    step 3. By induction follows from step 1+step 2 that for all n\in \mathbb{N} we have card \mathcal{P}(A_n) = 2^n
    Not to be a combative Carl, but what you did doesn't look any simpler than what I did. Also, mine seems to be more descriptive. Any comment?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    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 \mathcal{P}(A_n) we can choose to add or not add an extra element N+1, the conclusion follows.

    I think that's clearly more straightforward approach.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Dinkydoe View Post
    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 ever element of \mathcal{P}(A_n) we can choose to add or not add an extra element N+1, the conclusion follows.

    I think that's clearly more straightforward approach.
    I mean, really, the only difference between mine and yours is that you went into less detail. Which is probably a good thing!
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    I mean, really, the only difference between mine and yours is that you went into less detail. Which is probably a good thing!
    Exactly! The questioner probably wants answers, no essays
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. [SOLVED] strong induction problem involving power set
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 8th 2011, 02:32 AM
  2. [SOLVED] Theorem involving delta function: proof by induction
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: December 16th 2010, 11:51 AM
  3. Help involving induction proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 3rd 2010, 08:47 PM
  4. proof involving power sets, and intersection
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 12th 2010, 03:29 PM
  5. Induction proof involving sums of consecutive powers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 2nd 2009, 07:01 AM

Search Tags


/mathhelpforum @mathhelpforum