Thread: One-to-one Correspondence Questions

Here are the questions I have been struggling with. Any help would be greatly appreciated!

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.


My solution attempts:

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).



Thank you again for any help!

Originally Posted by kolssi

Here are the questions I have been struggling with. Any help would be greatly appreciated!

2. Find a one-to-one correspondence between the set of natural numbers and2. 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.


My solution attempts:

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).



Thank you again for any help!

It looks like understanding 5) will make the other four pretty straight forward exercises.

First, you might make a note that the easiest approach to 5) is to use the Schroder-Bernstein theorem.
But, clearly this is not what your professor is looking for at this point in time.
So let's take the hard road.

Notice the two sets differ only in their containment of the end points of the interval.

Let's make use of some of the advice you've gathered and define the following set:

A = {0, 1, 1/2, 1/3, ... , 1/n, ...}.

Now define the map f: [0,1] -> (0,1) by the rule:

f(0) = 1/2,
f(1/n) = 1/(n+2), for n>=1,
f(x) = x, for x in [0,1]-A.

What remains is to establish that f is bijective.

Thank you so far for the help. I was wondering about the definition of four terms (I looked them up online but I'm afraid I lack the mathematical knowledge to understand the defintions):

bijective
onto
surjection
injection


Also, how did you go about deriving these rules?
f(0) = 1/2,
f(1/n) = 1/(n+2), for n>=1,
f(x) = x, for x in [0,1]-A.


Thanks.

Originally Posted by kolssi

Thank you so far for the help. I was wondering about the definition of four terms (I looked them up online but I'm afraid I lack the mathematical knowledge to understand the defintions):

bijective
onto
surjection
injection


Also, how did you go about deriving these rules?
f(0) = 1/2,
f(1/n) = 1/(n+2), for n>=1,
f(x) = x, for x in [0,1]-A.


Thanks.

That's surprising, since in all the stated problems you wrote the phrase, "one-to-one correspondence", and apparently had no difficulty with it.
(Typically, this is just another way of saying, "one-to-one and onto".)
So after reading the definitions, I would expect that you made the connection with that phrase and the word, "bijection". But, I guess not.
Maybe writing out the definitions you're studying, and indicating where in them you're experiencing difficulty would be a good idea.

How to come up with a function that will work?
The primary difficulty here is figuring out what to do with the endpoints and still keep the map bijective.
I suppose the first thing to convince yourself of is that you're going to have to piece the function together.
Then, trial-and-error. Try one of your own.

Note also that this is a standard problem.
Most any book that covers infinite sets, with something on comparison of cardinal numbers, will have it either as an example or in the exercise set.
But, I suspect most often Schroder-Bernstein is introduced first, therby making it available for use.