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?
Is it possible for this to be an injective function?
-
0Think (for example) of prime numbers and unique factorisation. – 2012-11-05
-
0Are you giving me an assignment? It just happens that I gave *my* students such function and requested they prove it is a bijection. – 2012-11-05
-
0What 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. – 2012-11-05
-
0A 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. – 2012-11-05
-
2Anthony, 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. – 2012-11-05
-
0I wish that I could, I don't understand the question that was posted, I understand what an injective function is and I know what the set of all natural numbers are but I'm not sure how I would go about determining if it is possible, is there a way for me to come up with a specific number example to disprove it? Or am I way off? – 2012-11-05
-
0Then you should *say* that in your question. I don't want to just post an answer to your question, I want to help you *understand*. In order for me to help you understand I first need to know what it is about the problem that you don't understand. – 2012-11-05
-
0I'm sorry that I didn't I am new to the forum, my mistake, my main problem is that I don't understand what is meant by domain and codomain in the problem. – 2012-11-05
-
0Would I be correct in saying that it is possible for it to be injective because the function with domain NxN would all have values matching in the codomain N since all NxN are also natural numbers? – 2012-11-05
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...
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.
-
0This 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? – 2012-11-05
-
0You 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)$. – 2012-11-05