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

- November 4th 2013, 05: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. - November 4th 2013, 05:43 PMPlatoRe: Cardinality Proof Help Needed
- November 4th 2013, 07:45 PMHallsofIvyRe: Cardinality Proof Help Needed
Plato, I disagree with . is NOT a subset of .

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

- November 9th 2013, 10: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.

- November 9th 2013, 11:04 AMSlipEternalRe: Cardinality Proof Help Needed
Show that . Then show that . Show that is a disjoint union of sets (since no set in contains and is just twice the number of elements in .

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

That is two sets, or

Suppose we know that contains sets.

It should be clear to you that . Right?

The only 'new' sets on the right look like where .

We get**one new set**for each on the left.

So we now have sets on the right. - November 9th 2013, 12:09 PMHallsofIvyRe: 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. - November 9th 2013, 12:11 PMSlipEternalRe: 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 which has elements. For each a subset which contains is distinct from a subset that does not. So, each element gives 2 possibilities that are independent for each element of . By the product principle, the number of subsets would be...

Can you finish the proof?