Infinite sets onto and one-to-one

[POtment]

Homework Statement

N is the set of natural numbers, Z is the set of all integers
Construct a function a : N -> Z that is both one to one and onto.
Construct a function b : Z -> N that is one to one but not onto.

The Attempt at a Solution

The only attempts have been very wrong - not even sure where to start since in both cases it doesn't seem that a solution is possible.

 

[Pere Callahan]

If your friend from Mars who doesn't know our strange number system, were to ask you to list all integers, so that she can see what kind of numbers we use on Earth.

Maybe you would start with zero because it lies somewhere in the middle, then you might go on to tell her about 1 and -1 because they are pretty nearby and often used...how could you continue?

When you've told her about ALL integers you will have found a function N-->Z. Do you see why this is one-to-one and onto?

 

[POtment]

I'm sorry I am having problems understanding how we have found a function once we have told her about all integers. Maybe I've been looking at the problem wrong for so long I'm not picking up the obvious...

 

[Pere Callahan]

We're looking for a function f: N-->Z. this means for each natural number n, f(n) must give an integer. f being one-to-one means, two different natural numbers give you different integers

<br /> m\neq n \Rightarrow f(n)\neq f(m)<br />

f being "onto" means for each integer z you have some natural number n such that f(n)=z.

So let's define the function by

f(n) = the n.th integer you told you friend about.



What would be f(1), f(2), f(3), f(4), f(5) ...?

 

[POtment]

How can the function be onto? There are not enough natural numbers for there to be a unique solution for all f(n) = z

 

[Pere Callahan]

well this is a very good point. there are infinitely many natural numbers and there are also infinetly many integers. I agree that intuitively it seems that there should be twice as many integers as natural numbers. This is not the case. The very fact there indeed IS a function N-->Z which is "onto" shows that you can count the integers, hence the name countable set.

Are you familar with the term "countable"?

Do you agree that the function f as I defined it, is onto? What are the first few values of this function f?

 

[POtment]

As you have defined it f(1) = 0, f(2) = 1, f(3) = -1, f(4) = 2, f(5) = -2, etc etc.
Is this correct?

Edit: I know I must seem dense, thank you for your help

 

[Pere Callahan]

This is indeed one - and most likely the most common - way to define a function f:N-->Z

Now it would be good to write down a general formula for this function because "etc" doesn't look good.
And you should convnce yourself that it is onto.
That means somebody picks an integer, say 3456, will there be a natural number n such that f(n)=3456?

 

[POtment]

Now things make sense and I do see why this function is onto.

So then f(n) = ceiling(-n/2) when n is odd, and f(n) = (n/2) when n is even.

 

[POtment]

Any help on "Construct a function b : Z -> N that is one to one but not onto."?

 

[morphism]

Take any subclass of N, like the even natural numbers for instance. Can you split this into two subclasses? Say, the ones that are divisible by 4, and the ones that aren't...

 

[POtment]

I'm waaay too tired tonight. Can you be a little more specific?

 

[morphism]

The most natural one-to-one function that maps Z into N is the one that sends the positive integers to the positive even natural numbers, the negative integers to the odd natural numbers, and 0 to 0. The problem is, this map is also onto. So my post was hinting at the idea of mapping Z to a suitable proper subset of N, one in which we can do something like the even-odd map again.

 

[POtment]

Sorry it took a while to get back. Thanks a lot for your help, I solved the problems.

 

[POtment]

I ended up getting this problem wrong and I was hoping you could give me another hint on: mapping Z to a suitable proper subset of N, one in which we can do something like the even-odd map again?

My teacher won't help me find the answer and I will probably need to understand this for the final.

 

[mutton]

What was your answer? Make sure that in addition to being not onto, your function is one-to-one. To show that a function f is one-to-one, you can show that either

m\neq n \Rightarrow f(n)\neq f(m) \quad \text{ or } \quad f(m) = f(n) \Rightarrow m = n

Pere mentioned the first option above.

 

[POtment]

My post was in response to morphism's post.
==================
The most natural one-to-one function that maps Z into N is the one that sends the positive integers to the positive even natural numbers, the negative integers to the odd natural numbers, and 0 to 0. The problem is, this map is also onto. So my post was hinting at the idea of mapping Z to a suitable proper subset of N, one in which we can do something like the even-odd map again.
==================

I'm not sure how to map Z to a proper subset of N that does something like the even-odd map again.