Results 1 to 9 of 9

Math Help - Cardinality Proof Help Needed

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    United States
    Posts
    13

    Exclamation 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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,394
    Thanks
    1476
    Awards
    1

    Re: Cardinality Proof Help Needed

    Quote Originally Posted by clintonh0610 View Post
    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.
    Last edited by Plato; November 5th 2013 at 03:03 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,974
    Thanks
    1121

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,397
    Thanks
    519

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2012
    From
    United States
    Posts
    13

    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,397
    Thanks
    519

    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]}.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,394
    Thanks
    1476
    Awards
    1

    Re: Cardinality Proof Help Needed

    Quote Originally Posted by clintonh0610 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,974
    Thanks
    1121

    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,397
    Thanks
    519

    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof of cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: August 7th 2011, 05:45 AM
  2. cardinality proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: August 2nd 2010, 02:34 AM
  3. Proof: Cardinality Question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 13th 2010, 12:35 AM
  4. Cardinality Inequality Proof
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 3rd 2009, 07:41 PM
  5. cardinality proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: September 19th 2008, 08:52 PM

Search Tags


/mathhelpforum @mathhelpforum