Strings

[misosoup]

Assume T is the set of binary strings of length 30 with 10 1’s and 20 0’s. Let Xbe the set of the first 30 positive integers (X:= [30] = {1,2,3,...,30}). Let Y be the set of all subsets of X containing 10 numbers. Find a one-to-one correspondence between Tand Y.

Attempt: I wrote that I knew that each position in T will correspond to one of the corresponding positions in the subset of B. For example: T={101...1} maps to B={{1,3,...,30},...}. I know it has a one-to-one correspondence because each string in T has 10 1's and each subset in B has 10 elements. But I don't know to generalize and prove it's one-to-one and onto by the definitions since I only dealt with very simple functions (i.e. f(x)=2x).

 

[Deleted member 4993]

Assume T is the set of binary strings of length 30 with 10 1’s and 20 0’s. Let Xbe the set of the first 30 positive integers (X:= [30] = {1,2,3,...,30}). Let Ybe the set ofall subsets of X containing 10 numbers. Find a one-to-one correspondence between Tand Y.

What are your thoughts?

Please share your work with us ...even if you know it is wrong

If you are stuck at the beginning tell us and we'll start with the definitions.

You need to read the rules of this forum. Please read the post titled "Read before Posting" at the following URL:

http://www.freemathhelp.com/forum/th...Before-Posting

 

[misosoup]

I know that every one of the positions in T maps to one of the numbers in the subset of Y. I know there is a one-to-one correspondence but I don't know how to make it general and prove it (i.e. one-to-one and onto) because I always had some functions that are simple to prove. Could you guide me through the process?

 

[Steven G]

Ah, I got it! Cute little problem.
To the OP. Show us your attempt and you will get help.

 

[misosoup]

Ah, I got it! Cute little problem.
To the OP. Show us your attempt and you will get help.

I wrote that I knew that each position in T will correspond to one of the corresponding positions in the subset of B. For example: T={101...1} maps to B={{1,3,...,30},...}. I know it has a one-to-one correspondence because each string in T has 10 1's and each subset in B has 10 elements. But I don't know to generalize and prove it's one-to-one and onto by the definitions since I only dealt with very simple functions (i.e. f(x)=2x).

 

[Steven G]

I wrote that I knew that each position in T will correspond to one of the corresponding positions in the subset of B. For example: T={101...1} maps to B={{1,3,...,30},...}. I know it has a one-to-one correspondence because each string in T has 10 1's and each subset in B has 10 elements. But I don't know to generalize and prove it's one-to-one and onto by the definitions since I only dealt with very simple functions (i.e. f(x)=2x).

So you have it, what is the problem? Give the rule how to go from T to B and then the rule to go from B to T. Give it a try!

 

[misosoup]

So you have it, what is the problem? Give the rule how to go from T to B and then the rule to go from B to T. Give it a try!

What do you mean the rule? I don't know how to start the proof.

 

[Steven G]

What do you mean the rule? I don't know how to start the proof.

Given a string in T what does it map to in B? Given a string in B what is it mapped to in T? The answers will be the two rules.

 

[pka]

What do you mean the rule? I don't know how to start the proof.

I have read this entire thread. It appears that you never will "know how to start the proof."

In order to start, one must know where one is. Do you know?
Give us the exact description of the set T .

Give us the exact description of the set Y.

Write out one element in the set Y. Do not use shorts-cuts.

Write out the exact element in the set T that corresponds to the element of Y, you listed above. Do not use shorts-cuts.

 

[misosoup]

I have read this entire thread. It appears that you never will "know how to start the proof."

In order to start, one must know where one is. Do you know?
Give us the exact description of the set T .

Give us the exact description of the set Y.

Write out one element in the set Y. Do not use shorts-cuts.

Write out the exact element in the set T that corresponds to the element of Y, you listed above. Do not use shorts-cuts.

1. I would write that set T is a set of bit strings with 10 1's and 20 0's.
2. Then set Y is a set with subsets of X.
3. How do I write out one element in Y, in general form? (Like provide an example: {{2,3,5,...}}
4. How do I write an element that corresponds to T, in general form?
Can you help me out?