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