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

• October 11th 2008, 12:03 PM
Jen
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.

Attachment 8144

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. (Doh)

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.
• October 11th 2008, 01:14 PM
Laurent
Quote:

Originally Posted by Jen
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: $f:(x_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.
• October 11th 2008, 05:23 PM
Jen
Awww, thank you!

You made it look much prettier than I would have! (Happy)