Register to reply

One-to-one Correspondence Questions

by kolssi
Tags: correspondence, onetoone
Share this thread:
kolssi
#1
Mar17-10, 11:24 PM
P: 2
1. The problem statement, all variables and given/known data
I haven't taken a math class for a few years now (since calc. II), and I am currently enrolled in a cryptology/math history course that has posed me a few challenges. I am not sure, but I am guessing that one of the reasons to show a one-to-one correspondence between two sets (I'm not sure 'set' is the right term) is to show that both sets are the same size? I think what I need to do is show that each element in the first set corresponds to another element in a second set.

I have read the sticky posts, and I understand that this website does not provide solutions to problems, but any hints or assistance would be greatly appreciated.

OK... so the questions.

1. Find a one-to-one correspondence between the set of natural numbers and the positive whole number powers of 10.

2. Find a one-to-one correspondence between the set of natural numbers and the whole number powers of 10.

3. Find a one-to-one correspondence between the numbers in the closed interval [0,1] and the numbers in the closed interval [3,8]. A word on notation: the closed interval [a,b] is the set of numbers x such that a <=x <= b; it includes the numbers a and b.

4. Find a one-to-one correspondence between the set A of reciprocals of the positive integers and the set B consisting of 0 and the reciprocals of the positive integers.

5. Find a one-to-one correspondence between the numbers in the closed interval [0,1] and the open interval (0,1). Notation: the open interval (a,b) is the set of numbers x such that a < x < b; it excludes both a and b.

2. Relevant equations



3. The attempt at a solution


1. I was able to figure out 1.
The two sets are 1 2 3 4 5 ... n and 10^1 10^2 10^3 ... 10^n
So the 1-to-1 correspondence is n <----> 10^n

2. The two sets here are 1 2 3 4 5 .... n and .... 10^-1 10^0 10^1 10^2 ...
I am not sure how to address the second set (whole number powers of 10) Since it does not have a defined beginning or end...

3. So these two sets are [0,1] and [3,8]
I found that for each x in [0,1] there is a 5x+3 in [3,8], but I am not sure as to the correct way to express this as a 1-to-1 correspondence.

4. So the two sets here are:
A: 1/1 1/2 1/3 1/4 ... 1/n?
B: 0 1/1 1/2 1/3 1/4...

I am not sure how to show these two sets relate. At first I thought set B was 1/(n-1) but that would result in dividing by zero for the first element in the set... So I am not sure where to go from here.

5. Upon discussion with my professor, this is the advice I have so far gathered.

So the numbers in (0,1) come in two flavors: there are those numbers of
the form 1/n where n is a whole number greater than 1 (that is, , 1/3,
,) and those numbers not of this form. Let C be the numbers not of
the form , 1/3, ,..).

Then the numbers in [0,1] also come in two flavors: flavor one are those
of the form 0,1, 1/2 , 1/3, , and flavor two consists of exactly those
numbers in C.

So I have learned that to get the desired one-to-one correspondence between (0,1) and [0,1], I must first
pair up the numbers , 1/3, ,1/ 5, with the numbers 0,1,1/2, 1/3,
,1/5, and then pair up each number in C with itself).

I am not sure how to pair up these numbers and I am also unsure what it means to pair C with itself, so any advice here would also be appreciated.




I apologize for the rather long series of questions. Thank you in advance!
Phys.Org News Partner Science news on Phys.org
Bees able to spot which flowers offer best rewards before landing
Classic Lewis Carroll character inspires new ecological model
When cooperation counts: Researchers find sperm benefit from grouping together in mice
vela
#2
Mar18-10, 12:50 AM
Emeritus
Sci Advisor
HW Helper
Thanks
PF Gold
P: 11,690
Quote Quote by kolssi View Post
2. The two sets here are 1 2 3 4 5 .... n and .... 10^-1 10^0 10^1 10^2 ...
I am not sure how to address the second set (whole number powers of 10) Since it does not have a defined beginning or end...
You've confused the whole numbers with the integers. The whole numbers are 0, 1, 2, ....
3. So these two sets are [0,1] and [3,8]
I found that for each x in [0,1] there is a 5x+3 in [3,8], but I am not sure as to the correct way to express this as a 1-to-1 correspondence.
You want to give a one-to-one function f:[0,1]->[3,8]; that is, just write it as you normally would write a function.
4. So the two sets here are:
A: 1/1 1/2 1/3 1/4 ... 1/n?
B: 0 1/1 1/2 1/3 1/4...

I am not sure how to show these two sets relate. At first I thought set B was 1/(n-1) but that would result in dividing by zero for the first element in the set... So I am not sure where to go from here.
You don't have to use a single formula to describe the correspondence. It's perfectly fine to say: f(1/n)=1/(n-1) when n is not equal to 1 and f(1/1)=0.

5. Upon discussion with my professor, this is the advice I have so far gathered.

So the numbers in (0,1) come in two flavors: there are those numbers of
the form 1/n where n is a whole number greater than 1 (that is, , 1/3,
,) and those numbers not of this form. Let C be the numbers not of
the form , 1/3, ,..).

Then the numbers in [0,1] also come in two flavors: flavor one are those
of the form 0,1, 1/2 , 1/3, , and flavor two consists of exactly those
numbers in C.

So I have learned that to get the desired one-to-one correspondence between (0,1) and [0,1], I must first pair up the numbers , 1/3, ,1/ 5, with the numbers 0,1,1/2, 1/3,
, 1/5, and then pair up each number in C with itself.

I am not sure how to pair up these numbers and I am also unsure what it means to pair C with itself, so any advice here would also be appreciated.
Hint: Part of problem 5 is very similar to problem 4.
kolssi
#3
Mar18-10, 08:19 PM
P: 2
OK so I made some attempts at solutions. If someone could tell me if I am going in the right direction, that would be great.

I have done some reading and I found the Schroder-Bernstein theorem that I think states that for two sets A and B, if injective functions A-->B and B-->A exist, then A and B have one-to-one correspondence (bijection). I hope this can apply to my homework. I just wanted to know if I am going about this in a correct manner.
------------------------------------------------------------------------------------
Find a one-to-one correspondence between the set of natural numbers and the whole number powers of 10. (my professor said that by "whole numbers" he means all integers)



Set A: 1,2,3,4,5,6.....

Set B: ...10^-2 , 10^-1 , 10^0 , 10^1 , 10^2...



A-->B

f(1) = 10^0

f(2n) = 10^n for n >= 1

f(2n+1) = 10^-n for n >= 1



B--->A

f(10^0) = 1

f(10^n) = 2n for n>=1

f(10^-n) = 2n+1 for n>=1



I tried to match all even numbers in set A with the positive whole number powers of 10 and the odd numbers with the negative whole number powers of 10. 1 from A and 10^0 from B were left over, so I matched those two together.

---------------------------------------------------------------------------

***** Find a one-to-one correspondence between the numbers in the closed interval [0,1] and the numbers in the closed interval [3,8]. A word on notation: the closed interval [a,b] is the set of numbers x such that a <=x <= b; it includes the numbers a and b.



A: [0,1]

B: [3,8]



A-->B

f(x) = 5x+3



B-->A

f(x) = (x-3)/5

----------------------------------------------------------------------------------
******* Find a one-to-one correspondence between the set A of reciprocals of the positive integers and the set B consisting of 0 and the reciprocals of the positive integers.



A: 1/1, 1/2, 1/3...

B: 0, 1/1, 1/2, 1/3...



A-->B

f(1) = 0

f(1/n) = 1/(n-1) for n>1



B-->A

f(0) = 1

f(1/n) = 1/(1+n)
----------------------------------------------------------------------------------

*******Find a one-to-one correspondence between the numbers in the closed interval [0,1] and the open interval (0,1). Notation: the open interval (a,b) is the set of numbers x such that a < x < b; it excludes both a and b.



A: [0,1]

B: (0,1)



C: {0, 1, 1/2, 1/3,...,1/n,...}



A-->B

f(0) = 1/2

f(1/n) = 1/(n+2) for n >=1

f(x) = x for x in [0,1] that do not belong to C





B-->A

f(1/2) = 0

f(1/n) = 1/(n-2) for n>2

f(x) = x for x in (0,1) that do not belong to C

vela
#4
Mar18-10, 09:21 PM
Emeritus
Sci Advisor
HW Helper
Thanks
PF Gold
P: 11,690
One-to-one Correspondence Questions

Looks good!


Register to reply

Related Discussions
GR correspondence to reality Special & General Relativity 13
Continuity of correspondence? Quantum Physics 2
Galois correspondence Calculus & Beyond Homework 3
1-1 Correspondence Introductory Physics Homework 2
Rule of Correspondence Calculus 2