Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Power set of a finite set

  1. Mar 24, 2007 #1
    How can we prove that the power set of a finite set is finite?
  2. jcsd
  3. Mar 24, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    Since the power set of a finite set with N elements has [itex]2^{N}[/itex] elements, set [tex]M=2^{N}+1[/tex]

    Thus, there exists a natural number M so that the number of elements in the power set is less than M. But that means the power set is finite.
  4. Mar 24, 2007 #3
    That's really beating around the bush. Assuming the power set has 2^n elements is equivalent to assuming that it is finite.

    If this be exercise related, and it probably is, it'll be better to prove that the power set has 2^n elements.
  5. Mar 24, 2007 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    No, I am not.

    As for proving that, I didn't bother to post the proof. OP can do it on his own as an exercise.
  6. Mar 24, 2007 #5
    You're basically doing the assuming on OP's part.

    Besides, you don't need to show that a number is bounded to be finite. Any number is bounded.
  7. Mar 25, 2007 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    No he's not. If S has n elements then the normal definition of P(S) has 2^n elements. Raising 2 to an integer gives an integer.
  8. Mar 25, 2007 #7
    Let |A| = n.
    If I were asked to show P(A) is finite, I'd go ahead and prove
    that |P(A)| = 2^n. Clearly, 2^n is finite. So you're done.

    |A| = n -> |P(A)| = 2^n is an assertion requiring proof (not a definition). There are a number of ways to prove it.

    1) by Mathematical Induction. This is an instructive approach
    because it causes you to think about the effect on P(A) when a single new
    element is added to A, which of course is what must be done in the induction step.

    2) by considering the set of characteristic functions defined on A, and how they might be related to the subsets of A.
    This is also instructive since it should cause you to think about maps
    f: A->B, where say |A| = n and |B| = m. Here the cardinality of the set of all such maps (B^A) is |B|^|A|. In the case of characteristic functions, B = {0,1}. I think you can see where this might lead.
    Note that I've "arm-waved" the |B|^|A| claim. So in your proof you'll have to demonstrate it. (It is of course a theorem in its own right, and not difficult to prove.)
    Last edited: Mar 25, 2007
  9. Mar 25, 2007 #8
    Hi, I'm the OP, and thanks for all the responses - glad to see this
    forum is so active.

    To clarify a little bit, I understand intuitively that if x ~ n then Px
    ~ 2^n and thus is obviously finite. But what I was wondering is whether
    there is a direct set-theoretical proof that doesn't require the
    development of natural number exponenentiation (with the associated
    complexity of recursive definitions and so on).

    Background: I have seen this problem as an exercise in a number of set
    theory books, but always as an exercise and never with a solution or as
    a theorem with proof. Usually it is given as an exercise after a number
    of other results are shown, such first showing that the subset of a
    finite set is finite, the union of two finite sets is finite, the
    cartesian product of two finite sets is finite, and so on (which while
    not terribly hard, I wouldn't call them "trivial"). A direct
    set-theoretical proof along these lines seems to be what the books
    intend, especially since the exercise is sometimes given before natural
    number exponentiation is even developed. I have wondering what such a
    proof would look like since taking a set theory course some years ago.
  10. Mar 25, 2007 #9


    User Avatar
    Homework Helper
    Gold Member

    They're always exercises because they're considered great basic questions for students to solve.

    You're making it way more complicated than it really is.
  11. Mar 25, 2007 #10
    This is really a combinatorics question. You have n elements, how many SETS can you make that would go in the power set?
  12. Mar 25, 2007 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Possibly, though bear in mind that to even define 'finite' one ought to define the natural numbers. And once one has it is trivial that the (normal) power set is in bijection with the cartesian product {0,1}x{0,1}x..x{0,1} which has cardinality 2x2x2..x2, which is a finite number and has nothing to do with exponentiation.

    Alternatively one must use the definition of dedekind infinite - a set is infinite if and only if there is an injection from it to itself which is not surjective. I wouldn't like to contemplate that idea as a way of proving it though.
    Last edited: Mar 25, 2007
  13. Mar 25, 2007 #12


    User Avatar
    Science Advisor

    Considering that there are no "infinite numbers", that's a very strange remark!

    The problem was not to prove that a NUMBER was finite, but that a set was.

    matt grime is saying that proving a set with cardinality n has power set with cardinality 2n is sufficient to prove that the power set of a finite set is finite. Everyone else is saying, "yes, and basically, the original question is how to prove that!".
    Last edited by a moderator: Mar 25, 2007
  14. Mar 25, 2007 #13
    I think I understand what the problem was, I have no idea what you're trying to clarify.
  15. Mar 25, 2007 #14


    User Avatar
    Homework Helper

    If you don't want to explicitly use the |P(X)|=2^|X| formula, you can borrow the main idea of its proof by induction to get the proof you want. Namely, the empty set clearly has a finite power set, and adding one element to a set doubles the size of the power set (there are those subsets with the new element and those without it), so since doubling a finite set gives another finite set, by induction the power set of any finite set is finite.
  16. Mar 25, 2007 #15
    You dont even need to show 2^n in the inductive step. You just need to show adding one doesn't suddenly make it infinite. Rather a trivial problem.
  17. Mar 26, 2007 #16
    Here is the proof I was looking for

    I found a proof in Suppes, Axiomatic Set Theory, pp. 104-105 that
    doesn't use natural number exponentiation, and this is what I was
    looking for. Here is an outline, using u = union and - = set difference.

    We use induction on the cardinality of x. The basis is obvious. For the
    induction step, we extend x to x u {y} with an element y not in x.
    Assume Px is finite. Consider the function f = {<c,c u {y}> : c in Px}.
    It can be shown that f maps Px onto P(x u {y}) - Px. Thus if Px is
    finite, so is P(x u {y}) - Px. Noting that
    P(x u {y}) = (P(x u {y}) - Px) u Px, if both P(x u {y}) - Px and Px are
    finite, so is their union. Therefore P(x u {y}) is finite.

    Thanks for the replies.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook