Results 1 to 3 of 3

Math Help - Aaaarrrrggghhhhhhh!!!!!! (i.e. Help me. :))

  1. #1
    Jen
    Jen is offline
    Member Jen's Avatar
    Joined
    Feb 2008
    From
    Corvallis, Oregon
    Posts
    157

    Aaaarrrrggghhhhhhh!!!!!! (i.e. Help me. :))

    Ok, so I have sat and stared at this problem for hours now. I can't seem to wrap my mind around it.

    Aaaarrrrggghhhhhhh!!!!!!    (i.e.  Help me.  :))-capture.jpg

    So I have written out the n=2 and the n=3 case. I can see that S and T will always have the same cardinality, which means that there exists a bijection between the sets. I am having a hard time showing that a one to one and onto function exists that follows this rule.

    I also don't exactly know how to "describe" it other than that it matches every binary n-string to the subset that it describes, i.e. the binary 3-string
    (0,1,0) would map to the subset {2} and the binary 3-string (1,1,1) would map to the subset {1,2,3}.

    I am having a hard time creating a rule to map each binary n-string to the subset in T that it describes.

    So I was thinking if I partition S into (i) partitions, where partition 1 is the binary n-string for 0 and partition 2 is the binary n-string for 1 and so on.

    I don't know what to do from there. Errrr, I'm lost.

    I think I am thinking about this all wrong!

    Give me a few hints or corrections. I really want to be able to think through it on my own but I need a little bump in the right direction maybe.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Jen View Post
    I also don't exactly know how to "describe" it other than that it matches every binary n-string to the subset that it describes
    That's exactly it, but a more formal description seems to be expected, like: x_1,\ldots,x_n)\mapsto \{i\in\{1,\ldots,n\}|x_i=1\}" alt="fx_1,\ldots,x_n)\mapsto \{i\in\{1,\ldots,n\}|x_i=1\}" /> from S to T. Once you have clarified things that way, you can write the formal proof of f being onto and one-to-one.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Jen
    Jen is offline
    Member Jen's Avatar
    Joined
    Feb 2008
    From
    Corvallis, Oregon
    Posts
    157
    Awww, thank you!

    You made it look much prettier than I would have!
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum