1
$\begingroup$

I haven't managed to find this problem here. If this has already been asked, please let me know.

I need to find an injective function:

$f:\mathbb{Z}\times\mathbb{Z}\to \mathbb{N}$

The solution I'm provided with:

$f(x,y)=2^{sgn(x)+1}3^{|x|}5^{sgn(y)+1}7^{|y|}$

My first question is whether there is another way to solve this. It does make sense when I look at the solution, since it turns out that:

$sgn(x_1)=sgn(x_2), |x_1|=|x_2|$ (same for y)

Where it's obvious that the function is injective, but I'm not sure how I could have thought of this myself. From what I saw in my book, there wasn't any "general" approach to solving these types of problems. If anyone could explain it here, thank you in advance.

$\endgroup$

4 Answers 4

3
$\begingroup$

Another way is to look at an infinite array ($\mathbb Z×\mathbb Z$), and put the elements in a list by winding your way back and forth starting from the upper left hand corner. Not sure how to explicitly write the rule for this, but someone here probably knows how. Btw, there are $2$ variations on this...

Oops, you said $\mathbb Z×\mathbb Z$. First you would have to put each copy of $\mathbb Z$ in a list...

$\endgroup$
2
$\begingroup$

The basic idea of determining functions like this just lies with the infinitude of the primes and the unique factorization of integers. Finding ways to combine these two pieces of information lets you handle a lot of problems similar to this one. An explanation for the current problem is below:

Since you have $2$ copies of $\Bbb Z$, you can take any four primes (the first four primes, in this case). You have two primes that take into account the sign of the integer (positive or negative, a positive value for $x$ includes a unique prime, while a negative value for $x$ excludes it), and you have two more primes to take into account the actual inputs (using absolute values since you've already addressed whether the inputs are positive or negative). So, for a given $(x,y)$, you've addressed whether $x<0$ or $x\geq0$, and the same for $y$, and introduced unique primes that multiply together to determine a positive integer. By the fundamental theorem of arithmetic (unique factorization), this function is injective.

$\endgroup$
2
$\begingroup$

The underlying idea behind the answer you mention is that over $\mathbb{N}$ we have the fundamental theorem of arithmetic. And also, the two quantities $\text{sgn}(x)$ and $|x|$ determine $x$ uniquely.

EDIT: If you want another function, you can simply draw $\mathbb{Z}\times\mathbb{Z}$ in the plane. Then draw a rectangular spiral starting in $(0,0)$ which goes through every point in the grid. Then define the function $f :\mathbb{Z}\times\mathbb{Z}\rightarrow \mathbb{N}$ by saying $f(a,b)=n$ if $(a,b)$ is the $n$'th number your spiral goes through. This $f$ will even be bijective.

$\endgroup$
1
$\begingroup$

The trick here is that prime factorizations are unique. You could replace $2,3,5,7$ by any other quadruple of primes and it would still work. You can also multiply your injective function with a factor $m$ such that $m$ is not divisible by the 4 primes you used, to get a new injective function.

but I'm not sure how I could have thought of this myself.

Don't worry, sometimes there is just a trick to it. Cantor was the first one to use the diagonal Argument and it was repeatly used in other contexts after that, because it was simply clever.

From what I saw in my book, there wasn't any "general" approach to solving these types of problems. If anyone could explain it here, thank you in advance.

If by "these types of problems" you mean "find a function with certain properties" then yes, there is no general approach. Don't worry, that way math is way more interesting :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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