# Power set of a finite set

1. Mar 24, 2007

### orcarus

How can we prove that the power set of a finite set is finite?
Thanks.

2. Mar 24, 2007

### arildno

Since the power set of a finite set with N elements has $2^{N}$ elements, set $$M=2^{N}+1$$

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.

3. Mar 24, 2007

### ZioX

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.

4. Mar 24, 2007

### arildno

Assuming??
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.

5. Mar 24, 2007

### ZioX

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.

6. Mar 25, 2007

### matt grime

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.

7. Mar 25, 2007

### fopc

OP:
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
8. Mar 25, 2007

### orcarus

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.

9. Mar 25, 2007

### JasonRox

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.

10. Mar 25, 2007

### ZioX

This is really a combinatorics question. You have n elements, how many SETS can you make that would go in the power set?

11. Mar 25, 2007

### matt grime

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
12. Mar 25, 2007

### HallsofIvy

Staff Emeritus
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: Mar 25, 2007
13. Mar 25, 2007

### ZioX

I think I understand what the problem was, I have no idea what you're trying to clarify.

14. Mar 25, 2007

### StatusX

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.

15. Mar 25, 2007

### Thrice

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.

16. Mar 26, 2007

### orcarus

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.