# (Dis)prove there exists a binary operation on the natural numbers which is injective.

1. Jan 18, 2013

### SithsNGiggles

1. The problem statement, all variables and given/known data

Prove or disprove: $\exists$ a binary operation $*:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ that is injective.

2. Relevant equations

3. The attempt at a solution

At first, I was under the impression that I could prove this using the following operation. I define $*$ to be
$a*b=\begin{cases} 1, & \mbox{if } a=1 \mbox{ and } b=1 \\ 2, & \mbox{if } a=2 \mbox{ and } b=1 \\ 3, & \mbox{if } a=3 \mbox{ and } b=1 \\ \vdots \\ m, & \mbox{if } a=1 \mbox{ and } b=2 \\ m+1, & \mbox{if } a=2 \mbox{ and } b=2 \\ m+2, & \mbox{if } a=3 \mbox{ and } b=2 \\ \vdots \\ n, & \mbox{if } a=1 \mbox{ and } b=3 \\ n+1, & \mbox{if } a=2 \mbox{ and } b=3 \\ n+2, & \mbox{if } a=3 \mbox{ and } b=3 \\ \vdots \end{cases}$
where $m,n\in\mathbb{N}$.

The problem I have with this is that I think it breaks initial condition that $*$ maps $(a,b)\in\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}$ because the list of values of $a*b$ takes on every natural number for $b=1$ (so I have a set with the cardinality of the natural numbers), and then again for $b=2$, and so on.

Basically, and I'm not sure if I'm saying this properly, I (think) I have an operation that maps from $\mathbb{N}\times\mathbb{N}$ onto a set that has cardinality $|\mathbb{N}|^2$, and I'm not sure this helps me in proving the statement. I suppose one question would be if $|\mathbb{N}| = |\mathbb{N}|^2$?

Edit: Another would be, is it even true that $m,n\in\mathbb{N}$? It looks like they might already have been taken on for some combination of $a$ when $b=1$.

Last edited: Jan 18, 2013
2. Jan 18, 2013

### jbunniii

Re: (Dis)prove there exists a binary operation on the natural numbers which is inject

As written, your map is not well defined. Can you please clarify what happens in the sections indicated by "..."? For example, at what value of $a$ does this pattern end:
$$a*b=\begin{cases} 1, & \mbox{if } a=1 \mbox{ and } b=1 \\ 2, & \mbox{if } a=2 \mbox{ and } b=1 \\ 3, & \mbox{if } a=3 \mbox{ and } b=1 \\ \vdots \\ \end{cases}$$
If the pattern continues for all $a \in \mathbb{N}$ then there's no way this map can be injective. You will have repeats as soon as you start the $b = 2$ section.

Also, what are the values of $m$ and $n$?

It looks like you are trying to sequence through $\mathbb{N} \times \mathbb{N}$ one column at a time. Hint: I think you will have better success if you try sequencing diagonally.

Last edited: Jan 18, 2013
3. Jan 18, 2013

### SammyS

Staff Emeritus
Re: (Dis)prove there exists a binary operation on the natural numbers which is inject

How many ordered pairs of natural numbers are there whose sum is k ?

For k < 2. the answer is 0.

For k = 2 the only such ordered pair is (1, 1), so there's one.

For k = 3, the answer is 2; (1, 2) and (2, 1) .

For k = 4, the answer is 3; (1, 3), (2, 2) and (3, 1) .

For k = 5, the answer is 4; (1, 4), (2, 3), (3, 2) and (4, 1) .
...

For k > 2 in general (1, k-1), (2, k-2), (3, k-3), (4, k-4), ... , (k-3, 3), (k-2, 2), and (k-1, 1)

4. Jan 18, 2013

### SithsNGiggles

Re: (Dis)prove there exists a binary operation on the natural numbers which is inject

Oh, I guess it doesn't end. I can't end the pattern because the set of natural numbers is infinite, correct? As for m and n: like you said, the pattern will repeat, so they'd already be listed in first section before the "...".
I think I see what you're saying. I would have to define my operation as something along the lines of
$a*b = \begin{cases}1 & \mbox{if } a=1 \mbox{ and } b=1\\ 2 & \mbox{if } a=2 \mbox{ and } b=1\\ 3 & \mbox{if } a=1 \mbox{ and } b=2\\ 4 & \mbox{if } a=1 \mbox{ and } b=3\\ 5 & \mbox{if } a=2 \mbox{ and } b=2\\ 6 & \mbox{if } a=3 \mbox{ and } b=1\\ 7 & \mbox{if } a=4 \mbox{ and } b=1\\ 8 & \mbox{if } a=3 \mbox{ and } b=2\\ 9 & \mbox{if } a=2 \mbox{ and } b=3\\ 10 & \mbox{if } a=1 \mbox{ and } b=4\\ \vdots \end{cases}$, right?

(I've set up a partial array on paper in which I follow a diagonal pattern, and the above is what I get by using it. )
Sorry, I'm not seeing why the sum of the coordinates would matter. Could you clarify?

5. Jan 18, 2013

### Dick

Re: (Dis)prove there exists a binary operation on the natural numbers which is inject

Yes, your array is one right way to do it. SammyS was just trying to trying to give you hint to do what you just did. First assign integers to the pairs where a+b=2, then to the pairs where a+b=3, then to a+b=4, etc. It's a hint to follow the diagonals instead of the horizontals or verticals.

Last edited: Jan 18, 2013
6. Jan 18, 2013

### jbunniii

Re: (Dis)prove there exists a binary operation on the natural numbers which is inject

Yes, that's what I had in mind.

7. Jan 19, 2013

### SithsNGiggles

Re: (Dis)prove there exists a binary operation on the natural numbers which is inject

Alright then, thanks! I didn't quite see how it related until just now. Thanks to everyone else, too!

8. Jan 19, 2013

### SithsNGiggles

Re: (Dis)prove there exists a binary operation on the natural numbers which is inject

Actually, I do have another question. I'm fairly convinced that the operation is one-to-one, but I'm not sure how to go about proving it directly.

I know that a function is injective if $\forall \; x,y \in \mathbb{N}\times\mathbb{N}, \; f(x) = f(y) \Rightarrow x = y$, or equivalently, if $x \not= y \Rightarrow f(x) \not= f(y)$.

Would that mean that, in the case of this particular function, I have to show that $(a_1 * b_1 = a_2 * b_2) \Rightarrow (a_1 = a_2 \wedge b_1 = b_2)$?

Here's my thought process: With the way I've defined $*$, it looks like I pretty much guarantee that $f(x) \not= f(y)$ for $x \not= y$, and so I immediately have the contrapositive version of the injective definition. Is this correct?

9. Jan 19, 2013

### SammyS

Staff Emeritus
Re: (Dis)prove there exists a binary operation on the natural numbers which is inject

It is possible to find a formula which gives the same mapping you have.

The following will help with finding such a formula.

The sum of the natural numbers from 1 through n is given by $\displaystyle \ \ \frac{n(n+1)}{2}\ .$

10. Jan 19, 2013

### SithsNGiggles

Re: (Dis)prove there exists a binary operation on the natural numbers which is inject

I noticed that what I'm basically doing is proving that $\mathbb{N}\times\mathbb{N}$ is countable, and I distinctly recall having seen the formula you may be talking about in a previous class.

After looking through my notes from that class, I came upon the following formula:
$2^{m-1}(2n-1)$ (m and n can obviously be replaced with a and b).

I never really understood how the instructor or student (I can't remember who wrote the proof) obtained the formula. Does it use the sum of natural numbers $\dfrac{n(n+1)}{2}$ that you're referring to?

11. Jan 19, 2013

### SammyS

Staff Emeritus
Re: (Dis)prove there exists a binary operation on the natural numbers which is inject

The mapping you refer to here, $\ \ 2^{m-1}(2n-1)\,, \$ is perfectly valid, but it differs form the previous mapping you gave in post #4.

Let's define the binary operator, ⊗, by $\displaystyle \ \ m\otimes n=2^{m-1}(2n-1)\ .$

Let's investigate this operation. As it turns out, this mapping is not along the "diagonals" of $\ \mathbb{N}\times\mathbb{N}\ .\$
If m=1, then $\ 2^{m-1}=2^0=1\$ so that 1⊗n = 1, 3, 5, 7, … as n = 1, 2, 3, 4, … . (Odd numbers)

If m=2, then $\ 2^{m-1}=2^{2-1}=2\$ so that 1⊗n = 2, 6, 10, 14, … as n = 1, 2, 3, 4, … . (Odd multiples of 2)

If m=3, then $\ 2^{m-1}=2^{2-1}=2\$ so that 1⊗n = 4, 12, 20, 28, … as n = 1, 2, 3, 4, … . (Odd multiples of 4)

…​
This mapping is not only injective (one-to-one) it's also surjective (onto), and thus it's bijective.

It's also quite easy to decompose (invert): Give the result of m⊗n, you can easily recover both m and n as a unique pair. Do you see how to do that ?

My idea regarding the use of $\ \dfrac{n(n+1)}{2}\$ was to obtain an algebraic formula for a binary operation based on going along the "diagonals" of $\ \mathbb{N}\times\mathbb{N}\,,\$ although it was in a slightly different order than what you did. (I planned to always go along any diagonal in the same direction -- as the first number of the ordered pair increased, starting a 1.) I'm not so sure that either diagonal mapping is easy to decompose.

I think this ⊗ operation will work much better for you.

12. Jan 19, 2013

### SithsNGiggles

Re: (Dis)prove there exists a binary operation on the natural numbers which is inject

Yes, I think you're right about that. As for inverting: given any m⊗n, it looks like I can factor out a power of 2 (if it's even) or simply have 20 multiplied by an odd number (if it's odd).

But supposing I stick with my diagonal mapping, would this reasoning still work to show that the operation is one-to-one?

Thanks for the help, much appreciated!

13. Jan 19, 2013

### Dick

Re: (Dis)prove there exists a binary operation on the natural numbers which is inject

I don't think it's really profitable to try to write down a formula for the diagonal mapping to show it's invertible, though you probably could. It's the sort of mapping you draw a picture of then say that it's obvious that it is onto and injective.

14. Jan 20, 2013

### SithsNGiggles

Re: (Dis)prove there exists a binary operation on the natural numbers which is inject

Does showing the picture qualify as a proof, though? That's what I'm hoping for. The formula SammyS and I were discussing surely can be used in a proof, and I'm pretty confident that I'd be able to outline a proof using it.

Edit: The reason I'm asking is that in one of my proof-writing courses, when we were covering some set theory (simple union/intersection proofs), we weren't allowed to use Venn diagrams or anything.

15. Jan 20, 2013

### Dick

Re: (Dis)prove there exists a binary operation on the natural numbers which is inject

I would say yes. But I'd say Venn diagrams are proofs as well. The standards of the proof-writing course might say no. The (2^(m-1))*(2n-1) mapping might suit it better.

16. Jan 20, 2013

### SteveL27

Re: (Dis)prove there exists a binary operation on the natural numbers which is inject

Hint: Think about prime factorization in reverse.

Hint2: This is a trivially easy problem once you see the answer.

17. Jan 20, 2013

### SithsNGiggles

Re: (Dis)prove there exists a binary operation on the natural numbers which is inject

That standard was set by another professor, so I'll try submitting the diagonal mapping. If that doesn't work out, I'll work on the (2^(m-1))*(2n-1) mapping. Thanks.