- #1

- 3

- 0

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

Thanks.

Thanks.

You should upgrade or use an alternative browser.

- Thread starter orcarus
- Start date

- #1

- 3

- 0

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

Thanks.

Thanks.

- #2

arildno

Science Advisor

Homework Helper

Gold Member

Dearly Missed

- 10,025

- 135

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

- 370

- 0

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.

- #4

arildno

Science Advisor

Homework Helper

Gold Member

Dearly Missed

- 10,025

- 135

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

- 370

- 0

Besides, you don't need to show that a number is bounded to be finite. Any number is bounded.

- #6

matt grime

Science Advisor

Homework Helper

- 9,420

- 4

- #7

- 90

- 0

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

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:

- #8

- 3

- 0

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

JasonRox

Homework Helper

Gold Member

- 2,323

- 3

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.

- #10

- 370

- 0

- #11

matt grime

Science Advisor

Homework Helper

- 9,420

- 4

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.

Last edited:

- #12

HallsofIvy

Science Advisor

Homework Helper

- 41,847

- 969

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

Last edited by a moderator:

- #13

- 370

- 0

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

- #14

StatusX

Homework Helper

- 2,571

- 2

- #15

- 249

- 0

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

- #16

- 3

- 0

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: