Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is it possible to define an injective function with domain N×N and codomain N. Where N is the set of all Natural Numbers. Must such a function be sujective?

share|improve this question
    
Think (for example) of prime numbers and unique factorisation. –  martini Nov 5 '12 at 22:31
    
Are you giving me an assignment? It just happens that I gave my students such function and requested they prove it is a bijection. –  Asaf Karagila Nov 5 '12 at 22:34
    
What exactly do you mean, I'm in a math class where I am in way over my head, hence the question. A more specific answer would be helpful. –  Anthony Nov 5 '12 at 22:34
    
A more pleasant phrasing of the question would be helpful. Some evidence that you have given it some thought, rather than just regurgitating it in an undigested form, would be helpful. –  Gerry Myerson Nov 5 '12 at 22:35
2  
Anthony, I don't owe you anything and you are not my teacher. You don't have to give me any homework assignment, nor you have the right to complain when you just paste your homework assignment and expect people to post solutions. Students have to study. Study. –  Asaf Karagila Nov 5 '12 at 22:37
show 4 more comments

2 Answers

It can be defined and it doesn't have to be surjective. Draw a corner of $\mathbb N\times\mathbb N$ and start mapping the elements to $\mathbb N$. Think about triangles...

share|improve this answer
add comment

Hint: If $f\colon A\to\mathbb N$ is both injective and surjective then $g\colon A\to\mathbb N$ defined as $g(a)=f(a)+2$ is injective but not surjective.

As for injective function from $\Bbb{N\times N}$ you may want to search for Cantor's pairing function. That is the classical solution, although there are other solutions as well.


Let us get the terminology correct at first.

The set of natural numbers, $\Bbb N$, is the set of non-negative integers, $\{0,1,2,3,\ldots\}$. In some courses zero is not considered a natural number, though, but that is of little importance now.

The set $\Bbb{N\times N}$ is the collection of all ordered pairs of integers.

If $f\colon A\to B$ is a function we say that:

  • $A$ is the domain of $f$, and for every $a\in A$ we have that $f(a)$ is defined.
  • $B$ is the co-domain of $f$ and $f(a)\in B$ for all $a\in A$.
  • If whenever $a\neq a'$ are two elements from $A$ we have $f(a)\neq f(a')$ we say that $f$ is injective.
  • If whenever $b\in B$ there is some $a\in A$ such that $f(a)=b$ we say that $f$ is surjective.
  • If $f$ is both injective and surjective we say that it is a bijection, or bijective.

The question, if so, asks you to find a function which takes a pair of integers and produces an integer. This function should map distinct pairs to distinct integers, and the additional part asks whether such function must produce every integer.

The answer, let me tell you in advance, is that there is such function which is injective, and there is one which is surjective, and there is one which is both injective and surjective.

share|improve this answer
    
This is very helpful I am afraid that I may need just a bit more of a nudge in the right direction, should I try and come up with a function that shows these properties? –  Anthony Nov 5 '12 at 23:06
    
You must, that is the only mathematical way to justify such argument. I gave one hint in the answer; another hint (towards the same direction) would be to consider triangular numbers; and to a whole other direction consider for each number the highest factor of $2$ in its prime decomposition, and that you can represent the remainder as $2^m-1$ for some $m$, namely every number can be written as $2^n(2^m-1)$. –  Asaf Karagila Nov 5 '12 at 23:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.