Power set of a finite set

[orcarus]

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

 

[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.

 

[ZioX]

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.

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.

 

[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.

 

[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.

 

[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.

 

[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.)

 

[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.

 

[JasonRox]

direct set-theoretical proof that doesn't require the
development of natural number exponenentiation

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.

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.

 

[ZioX]

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

 

[matt grime]

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).

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.

 

[HallsofIvy]

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.

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 2ⁿ 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!".

 

[ZioX]

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

 

[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.

 

[Thrice]

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.

You don't 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.

 

[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.