# cardinality of finite sets

• Jan 6th 2010, 04:18 PM
pseudonym
cardinality of finite sets

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

Any help would be greatly appreciated!! Thank you!
• Jan 6th 2010, 04:39 PM
tonio
Quote:

Originally Posted by pseudonym

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

Any help would be greatly appreciated!! Thank you!

Prove it by induction on $|X|$ (hint: if A is any subset of a set $\{x_1,\ldots,x_{n-1}\}$ with n-1 elements, how many subsets of $\{x_1,\ldots,x_{n-1},x_n\}$ can be formed out of it ?)

Tonio
• Jan 6th 2010, 04:46 PM
Drexel28
Quote:

Originally Posted by pseudonym

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

Any help would be greatly appreciated!! Thank you!

Let $f(n)$ denote the number of subsets of $\left\{1\cdots,n\right\}$. Consider the power set of $\left\{1,\cdots,n,n+1\right\}$. Partition set into two blocks $B_1=\left\{A\in\wp\left(\left\{1,\cdots,n+1\right\ }\right):n+1\in A\right\}$ and $\wp\left(\left\{1,\cdots,n+1\right\}\right)-B_1=B_2$. Clearly, we have that $\left|B_2\right|=f(n)$. And, with the exception of $\{n+1\}$ we may (and can) only put $\{n+1\}$ into each of the subsets of in $B_1$. Thus, we have that $f\left(n+1\right)=f(n)+f(n)+1$...almost...we double counted one thing (what is it??). So $f(n+1)=f(n)+f(n)+1-1=2f(n)$. Thus, it follows by induction that the recurrence relation $f(n+1)=2f(n)$ has solution $f(n)=C\cdot 2^n$ for some $C$. Noting though that $f(0)$ is the number of subsets of the empty set we may conclude that $f(0)=1=C\cdot 2^0=C$. The conclusion follows.

EDIT: I am sorry tonio. I didn't see your post!
• Jan 6th 2010, 06:36 PM
Bruno J.
Why so complicated? Just notice that if you want to construct a subset $S$ of $X$, you have two possibilities for every element of $X$: either you include it, or you exclude it. So in total you have $2^{|X|}$ possibilities.

Another proof : clearly the number of subsets of $X$ is

${n \choose 1} + {n \choose 2} + \dots + {n \choose n} = (1+1)^n = 2^n$
• Jan 6th 2010, 06:39 PM
Drexel28
Quote:

Originally Posted by Bruno J.
Why so complicated? Just notice that if you want to construct a subset $S$ of $X$, you have two possibilities for every element of $X$: either you include it, or you exclude it. So in total you have $2^{|X|}$ possibilities.

Another proof : clearly the number of subsets of $X$ is

${n \choose 1} + {n \choose 2} + \dots + {n \choose n} = (1+1)^n = 2^n$

I feel as though what I said is exactly what you said.
• Jan 6th 2010, 06:43 PM
Bruno J.
Which of the two proofs is exactly like yours?
• Jan 6th 2010, 06:45 PM
Drexel28
Quote:

Originally Posted by Bruno J.
Which of the two proofs is exactly like yours?

I didn't mean exactly exactly :D. I only meant that the first one is the exact point of my proof. I just did it in a slightly different way.
• Jan 6th 2010, 06:50 PM
Bruno J.
Your proof relies on induction whereas my proof relies on a combinatorial argument... I don't think they're similar at all! (Giggle)
• Jan 6th 2010, 06:53 PM
Drexel28
Quote:

Originally Posted by Bruno J.
Your proof relies on induction whereas my proof relies on a combinatorial argument... I don't think they're similar at all! (Giggle)

The induction is merely the formality of it. The point was that if you fix an element in $\left\{1,\cdots,n+1\right\}$ it only has two places to go. I really do think we are saying the exact same thing, just the means of conveyance is different.
• Jan 6th 2010, 07:03 PM
Bruno J.
I'm just teasing you at this point. (Angel)
• Jan 6th 2010, 07:08 PM
Drexel28
Quote:

Originally Posted by Bruno J.
I'm just teasing you at this point. (Angel)

(Smirk)
• Jan 6th 2010, 07:47 PM
tonio
Quote:

Originally Posted by Bruno J.
Why so complicated? Just notice that if you want to construct a subset $S$ of $X$, you have two possibilities for every element of $X$: either you include it, or you exclude it. So in total you have $2^{|X|}$ possibilities.

Another proof : clearly the number of subsets of $X$ is

${n \choose 1} + {n \choose 2} + \dots + {n \choose n} = (1+1)^n = 2^n$

The "another proof" is not so unless you first prove that there are $\binom{n}{k}$ subsets with k elements out of a set with n elements, $k\le n$, and also you forgot the number $\binom{n}{0}$ 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