# Thread: Cardinality Proof Help Needed

1. ## Cardinality Proof Help Needed

Let P(X) denote the set of all subsets (including Ø and X) of a set X. Write out the elements of P(Ø), P({a}), and P({r,s,t}). If #X=n, a finite number, what is #P(X)? Prove your assertion.

Any help would be appreciated. Thanks.

2. ## Re: Cardinality Proof Help Needed

Originally Posted by clintonh0610
Let P(X) denote the set of all subsets (including Ø and X) of a set X. Write out the elements of P(Ø), P({a}), and P({r,s,t}). If #X=n, a finite number, what is #P(X)? Prove your assertion.
$\mathcal{P}(\emptyset)=\{\emptyset\}$ that is one set.

$\mathcal{P}(\{r,s\})=\{\emptyset,\{r\},\{s\},\{r,s \}\}$ that is $2^2$ sets.

You should complete this.

3. ## Re: Cardinality Proof Help Needed

Plato, I disagree with $P(\phi)= \{\phi, \{\phi\}\}$. $\{\ph\}$ is NOT a subset of $\phi$.

It is true that [tex]P(\{\phi\})= \{\phi, \{\phi\}\}[tex]. Did you misread the problem?

4. ## Re: Cardinality Proof Help Needed

To show how many subsets an n-element set has, consider each element of the n-element set. For a particular subset, each element is either in the subset or it is not. Hence, there are two possibilities for each element. Since each element may belong or not belong to a subset independent of any other elements that may or may not be part of the subset, you can apply the product principle to count how many subsets there are.

5. ## Re: Cardinality Proof Help Needed

Okay, I understand why the number of subsets is 2^n, but how would I go about proving that? If I use induction, I'm confused as to how to prove that the statement is true for n=k+1. Thanks.

6. ## Re: Cardinality Proof Help Needed

Show that $2^{[n]}\subseteq 2^{[n+1]}$. Then show that $2^{[n+1]} = 2^{[n]}\cup \bigcup_{A\in 2^{[n]}}\{A\cup \{n+1\}\}$. Show that is a disjoint union of sets (since no set in $2^{[n]}$ contains $n+1$ and is just twice the number of elements in $2^{[n]}$.

7. ## Re: Cardinality Proof Help Needed

Originally Posted by clintonh0610
Okay, I understand why the number of subsets is 2^n, but how would I go about proving that? If I use induction, I'm confused as to how to prove that the statement is true for n=k+1. Thanks.
This about the same a the reply just above. The notation is simpler.
$\mathcal{P}(\{1\})=\{\emptyset,\{1\}\}$ That is two sets, or $2^1=2$

Suppose we know that $\mathcal{P}\{1,2,\cdots,n\}$ contains $2^n$ sets.

It should be clear to you that $\mathcal{P}\{1,2,\cdots,n\}\subset\mathcal{P}\{1,2 ,\cdots,n,n+1\}$. Right?

The only 'new' sets on the right look like $G\cup\{n+1\}$ where $G\in\mathcal{P}\{1,2,\cdots,n\}$.
We get one new set for each $G$ on the left.
So we now have $2^n+2^n=2(2^n)=2^{n+1}$ sets on the right.

8. ## Re: Cardinality Proof Help Needed

A variation on that theme (proof by induction). If n= 0, then the set is empty and has only one subset, the empty set. Now, suppose that, for some positive integer, k, P(A)= 2^k whenever A has k members. Let B be a set containing k+ 1 members. Since k+1> 0, B has at least one member. Choose one and call it "b". No consider the collection of all subsets of B that do NOT contain b. That is the same as the set of all subsets of B\{b} which has k members and so 2^k subsets. But if any subset, C, of B [b]does[b] contain b, the assignment C-> C\{b} is one-to-one and onto. That is, there is a one-to-one correspondence between subsets of B which contain a and those that do not. Since there are 2^k sets that do not contain b and 2^k subsets of B that do contain b. There are a total of 2^k+ 2^k= 2(2^k)= 2^{k+1} subsets of B.

9. ## Re: Cardinality Proof Help Needed

And if you are looking for a more combinatorial argument, you can make a counting argument.

You want to count the number of subsets of $X$ which has $n$ elements. For each $x\in X$ a subset which contains $x$ is distinct from a subset that does not. So, each element gives 2 possibilities that are independent for each element of $X$. By the product principle, the number of subsets would be...

Can you finish the proof?