Results 1 to 9 of 9

Math Help - Cardinality

  1. #1
    Senior Member Danneedshelp's Avatar
    Joined
    Apr 2009
    Posts
    303

    Cardinality

    Let A be a non-empty set. Consider F = {f : A → {0, 1}}, the set of all functions on A with values in {0, 1}. Consider the function g : P (A) → F , B → X_B , where X_B is the characteristic function of the subset B ⊆ A: X_B(a) = 1, if a∈B, and X_B(a) = 0, if a∉B. Show that g is a bijection. As a consequence show that the number of subsets of a set with n elements is 2^n . This may justify the notation {0, 1}^A used for F.

    Where P represents the power set of A.

    I am very lost. We just started the chapter on cardinality and I am already struggling . I don't really know how to begin the question, so some direction would be nice. I tried to work out the one-to-one portion of the proof, but I am not sure if I am using the characteristic function correctly. Will I need to use it to show 1-1 and onto?

    Here is my stab at 1-1:
    Here is an attempt at a 1-1 proof:
    So, I choose elements X_B1=X_B2∈P(A) where X_B1 and X_B2 are functions with same domain A and try to show g(X_B1)=g(X_B2). So, then ∃a∈A such that X_B1(a)=X_B2(a). I can then assume X_B1(a)=X_B2(a)=1. So, we know a∈B for both functions. So, g(X_B1)=g(X_B2). Therefore, g is one-to-one.

    Is that how I use the characteristic equations? I am having a harder time with the onto proof.

    Thanks for your help

    --Dan
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,801
    Thanks
    1691
    Awards
    1
    Here is some material I wrote several years ago.
    I hope it helps.
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Danneedshelp's Avatar
    Joined
    Apr 2009
    Posts
    303
    Thanks for that. I followed most of it.

    I think I have the first part of the proof down (that the function g is bijective). Although, I am still not sure how to do the second part of the proof:

    "As a consequence show that the number of subsets of a set with n elements is 2^n . This may justify the notation {0, 1}^A used for F."

    The way it's written it sounds like the afore proof should have guided me to some kind of answer, but I'm not seeing it.

    Thanks for the help
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Apr 2009
    Posts
    13

    Wink

    Quote Originally Posted by Plato View Post
    Here is some material I wrote several years ago.
    I hope it helps.
    Nice work!

    Anyway, I think 2^M is not a proper notation for a set since 2 is not a set.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,801
    Thanks
    1691
    Awards
    1
    Quote Originally Posted by HiLine View Post
    Nice work!
    Anyway, I think \color{red}2^M is not a proper notation for a set since 2 is not a set.
    But 2 is a set.
    \begin{gathered}<br />
  0 = \emptyset  \hfill \\<br />
  1 = \left\{ \emptyset  \right\} \hfill \\<br />
  2 = \left\{ {0,1} \right\} = \left\{ {\emptyset ,\left\{ \emptyset  \right\}} \right\} \hfill \\<br />
   \vdots  \hfill \\ <br />
\end{gathered}
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Apr 2009
    Posts
    13

    Wink

    Quote Originally Posted by Plato View Post
    But 2 is a set.
    \begin{gathered}<br />
  0 = \emptyset  \hfill \\<br />
  1 = \left\{ \emptyset  \right\} \hfill \\<br />
  2 = \left\{ {0,1} \right\} = \left\{ {\emptyset ,\left\{ \emptyset  \right\}} \right\} \hfill \\<br />
   \vdots  \hfill \\ <br />
\end{gathered}
    Is it? I thought \begin{gathered}\left\{ {0,1} \right\}\end{gathered} is a set and 2 is a cardinal number. Is that what you mean in the argument?

    Or it could be a new notation to me. Sorry if that is the case.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,801
    Thanks
    1691
    Awards
    1
    Quote Originally Posted by HiLine View Post
    Is it? I thought \begin{gathered}\left\{ {0,1} \right\}\end{gathered} is a set and 2 is a cardinal number. Is that what you mean in the argument? Or it could be a new notation to me. Sorry if that is the case.
    From those remarks, it appears that you may not have studied an axiomatic construction of the natural numbers.
    Herbert Endertonís book ELEMENTS OF SET THEORY does a good job of that construction.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Apr 2009
    Posts
    13
    That is the case then. I'm sorry, Plato. My bad.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by Plato View Post
    Here is some material I wrote several years ago.
    I hope it helps.
    Infectivity ? Nice mathematical concept
    Blood Analysis showed we're infected by mathematics
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 11th 2010, 07:08 AM
  2. Cardinality of R, [0,1], R^2, [0,1] x [0,1]
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: March 18th 2010, 02:20 PM
  3. Cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 03:56 PM
  4. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 11th 2009, 05:36 PM
  5. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 8th 2009, 02:23 PM

Search Tags


/mathhelpforum @mathhelpforum