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

1. ## 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.

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.

That's exactly it, but a more formal description seems to be expected, like: $fx_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.