# Thread: cardinality of finite sets

1. ## cardinality of finite sets

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

Any help would be greatly appreciated!! Thank you!

2. 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 $\displaystyle |X|$ (hint: if A is any subset of a set $\displaystyle \{x_1,\ldots,x_{n-1}\}$ with n-1 elements, how many subsets of $\displaystyle \{x_1,\ldots,x_{n-1},x_n\}$ can be formed out of it ?)

Tonio

3. Originally Posted by pseudonym

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

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

EDIT: I am sorry tonio. I didn't see your post!

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

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

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

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

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

$\displaystyle {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.

6. Which of the two proofs is exactly like yours?

7. Originally Posted by Bruno J.
Which of the two proofs is exactly like yours?
I didn't mean exactly exactly . I only meant that the first one is the exact point of my proof. I just did it in a slightly different way.

8. Your proof relies on induction whereas my proof relies on a combinatorial argument... I don't think they're similar at all!

9. 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!
The induction is merely the formality of it. The point was that if you fix an element in $\displaystyle \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.

10. I'm just teasing you at this point.

11. Originally Posted by Bruno J.
I'm just teasing you at this point.

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

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

$\displaystyle {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 $\displaystyle \binom{n}{k}$ subsets with k elements out of a set with n elements, $\displaystyle k\le n$, and also you forgot the number $\displaystyle \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