Can someone please help me prove this:

Show that |P(X)| = 2 ^ (|X|) for all finite sets X

Any help would be greatly appreciated!! Thank you!

Printable View

- January 6th 2010, 04:18 PMpseudonymcardinality of finite sets
Can someone please help me prove this:

Show that |P(X)| = 2 ^ (|X|) for all finite sets X

Any help would be greatly appreciated!! Thank you! - January 6th 2010, 04:39 PMtonio
- January 6th 2010, 04:46 PMDrexel28
Let denote the number of subsets of . Consider the power set of . Partition set into two blocks and . Clearly, we have that . And, with the exception of we may (and can) only put into each of the subsets of in . Thus, we have that ...almost...we double counted one thing (what is it??). So . Thus, it follows by induction that the recurrence relation has solution for some . Noting though that is the number of subsets of the empty set we may conclude that . The conclusion follows.

EDIT: I am sorry**tonio**. I didn't see your post! - January 6th 2010, 06:36 PMBruno J.
Why so complicated? Just notice that if you want to construct a subset of , you have two possibilities for every element of : either you include it, or you exclude it. So in total you have possibilities.

Another proof : clearly the number of subsets of is

- January 6th 2010, 06:39 PMDrexel28
- January 6th 2010, 06:43 PMBruno J.
Which of the two proofs is exactly like yours?

- January 6th 2010, 06:45 PMDrexel28
- January 6th 2010, 06:50 PMBruno J.
Your proof relies on induction whereas my proof relies on a combinatorial argument... I don't think they're similar at all! (Giggle)

- January 6th 2010, 06:53 PMDrexel28
- January 6th 2010, 07:03 PMBruno J.
I'm just teasing you at this point. (Angel)

- January 6th 2010, 07:08 PMDrexel28
- January 6th 2010, 07:47 PMtonio

The "another proof" is not so unless you first prove that there are subsets with k elements out of a set with n elements, , and also you forgot the number in the sum and also, and perhaps most important, this another proof relies on "hidden induction": after all, we need to show that's true for all n, just like the formal proof of Newton's binomial theorem is usually, and as far as I am aware uniquely, done by induction.

Tonio