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
An interesting glimpse into how future state-of-the-art electronics might work
Tissue regeneration using anti-inflammatory nanomolecules
C2D2 fighting corrosion
vela
#2
Mar18-10, 12:50 AM
Emeritus
Sci Advisor
HW Helper
Thanks
PF Gold
P: 11,732
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,732
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