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.

Printable View

- Nov 4th 2013, 04:29 PMclintonh0610Cardinality 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. - Nov 4th 2013, 04:43 PMPlatoRe: Cardinality Proof Help Needed
- Nov 4th 2013, 06:45 PMHallsofIvyRe: Cardinality Proof Help Needed
Plato, I disagree with $\displaystyle P(\phi)= \{\phi, \{\phi\}\}$. $\displaystyle \{\ph\}$ is NOT a subset of $\displaystyle \phi$.

It is true that [tex]P(\{\phi\})= \{\phi, \{\phi\}\}[tex]. Did you misread the problem? - Nov 4th 2013, 06:46 PMSlipEternalRe: 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.

- Nov 9th 2013, 09:44 AMclintonh0610Re: 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.

- Nov 9th 2013, 10:04 AMSlipEternalRe: Cardinality Proof Help Needed
Show that $\displaystyle 2^{[n]}\subseteq 2^{[n+1]}$. Then show that $\displaystyle 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 $\displaystyle 2^{[n]}$ contains $\displaystyle n+1$ and is just twice the number of elements in $\displaystyle 2^{[n]}$.

- Nov 9th 2013, 10:53 AMPlatoRe: Cardinality Proof Help Needed
This about the same a the reply just above. The notation is simpler.

$\displaystyle \mathcal{P}(\{1\})=\{\emptyset,\{1\}\}$ That is two sets, or $\displaystyle 2^1=2$

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

It should be clear to you that $\displaystyle \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 $\displaystyle G\cup\{n+1\}$ where $\displaystyle G\in\mathcal{P}\{1,2,\cdots,n\}$.

We get**one new set**for each $\displaystyle G$ on the left.

So we now have $\displaystyle 2^n+2^n=2(2^n)=2^{n+1}$ sets on the right. - Nov 9th 2013, 11:09 AMHallsofIvyRe: 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. - Nov 9th 2013, 11:11 AMSlipEternalRe: 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 $\displaystyle X$ which has $\displaystyle n$ elements. For each $\displaystyle x\in X$ a subset which contains $\displaystyle x$ is distinct from a subset that does not. So, each element gives 2 possibilities that are independent for each element of $\displaystyle X$. By the product principle, the number of subsets would be...

Can you finish the proof?