1 Attachment(s)

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)

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.