# Showing a binary operation is injective

1. Apr 14, 2013

### SithsNGiggles

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

The objective was to think of a binary operation $*:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ that is injective. A classmate came up with the following operation, but had trouble showing it was injective:

$a*b=a^3+b^4$.

2. Relevant equations

3. The attempt at a solution

Here's my thought process. I denote $a*b$ and $c*d$ by $f(a,b)$ and $f(c,d)$, respectively. The usual procedure to show a function is injective is by using the definition:

A function $f$ is injective if $f(a,b)=f(c,d)~\Rightarrow~(a,b)=(c,d)$. Alternatively, $f$ is injective if $(a,b)\not=(c,d)~\Rightarrow~f(a,b)\not=f(c,d)$.

I figure the second (contrapositive) statement would be easier to prove. I assume $(a,b)\not=(c,d)$; that is, I assume $a\not=c$ OR $b\not=d$.

Suppose $a\not=c,b=d$.
\begin{align*} a&\not=c\\ a^3&\not=c^3\\ a^3+b^4&\not=c^3+b^4\\ a^3+b^4&\not=c^3+d^4\\ a*b&\not=c*d\end{align*}

Suppose $a=c,b\not=d$.
\begin{align*} b&\not=d\\ b^4&\not=d^4\\ a^3+b^4&\not=a^3+d^4\\ a^3+b^4&\not=c^3+d^4\\ a*b&\not=c*d\end{align*}

Now, I'm under the impression that this is all I have to show in order to conclude that $*$ is injective. Am I right in thinking this way?

2. Apr 14, 2013

### Dick

No, you have to also show a≠c and b≠d. That's the hard case, and I'm not sure how you would show it, if it's even true. You could pick a much easier example to try to show. Try to think of one using unique prime factorization.

Last edited: Apr 14, 2013
3. Apr 14, 2013

### SithsNGiggles

Hmm, unfortunately I'm not familiar with that technique. So what you're saying is, my reasoning stands, but it does not (and would be hard to) prove anything?

4. Apr 15, 2013

### Dick

What you have is correct, but you are only doing completely trivial cases. I'm suggesting you try thinking about things like a*b=(n^a)(m^b). Can you think of some choices for m and n that would make it easy to prove '*' is an injection?

5. Apr 15, 2013

### HallsofIvy

Staff Emeritus
To prove that f(x,y) is injective, you have to prove that "if f(a,b)= f(c,d) then a= c and b= d".

Here, f(x,y)= x3+ y4.

if f(a,b)= f(c,d) means that a3+ b4= c3+ d4
That leads to a3- c3= d4- b4
(a- c)(a2+ ac+ c2= (d- b)(d3+ bd2+ b2d+ b3).

6. Apr 15, 2013

### SithsNGiggles

@HallsofIvy, how do I use that to show a = c and b = d? I see if they are equal, then I get the identity 0 = 0, but I don't think that proves anything. Could it be that $(a-c)(a^2+ac+c^2)\not=(d-b)(d^3+bd^2+b^2d+b^3)$ if $a\not=c$ and $b\not=d$?

Thanks

7. Apr 15, 2013

### SithsNGiggles

$n=1$ and $m>1$ come to mind. Beyond that, I'm not sure. I'll put some more thought into it.

8. Apr 15, 2013

### Dick

n=1 wouldn't be injective, would it? f(1,1)=f(2,1)=f(3,1)=....=m. Yes, think about it a little more.

9. Apr 15, 2013

### Bacle2

One way of seeing your relation is not injective in your domain-codomain is that you can find

x,y , so that $x^3=y^4$ . Say $x=2^4 ,y=2^3$ . Then take (x,y)=($2^4,1$)

and (x',y')= $(1,2^3)$ we then get , for (x,y) , $x^3 + y^4=2^{12}+1$ ;

for (x',y') , we get $(1+2^{12})$. You can see that there are infinitely-many

values where your function is not 1-1.

Last edited: Apr 15, 2013
10. Apr 19, 2013

### SithsNGiggles

Hey, that's a pretty neat observation! It got me wondering: perhaps if the powers of a and b were odd, then the operation might be injective? I'll see if that gets me anywhere.

Thanks again to everyone else as well for the replies.

11. Apr 19, 2013

### Dick

Hint. Think prime numbers in f(n,m)=a^n*b^m.

12. Apr 19, 2013

### SithsNGiggles

Thanks, I noticed my mistake a few moments ago.

For this particular operation (a*b = a^3 + b^4), would it suffice to say something along the lines of:

(as per Bacle2's observation)

If there's anything wrong with the syntax, please let me know. Thanks

13. Apr 20, 2013

### Bacle2

Well, no, the problem is that, if the powers are both integers, they will have an LCM
(least common multiple) so that , given a^n and b^m :

(b^m)^n +(a^n)^m =(b^n)^m+ (a^m)^n .

Unless you want to spend a lot of time with this approach --nothing wrong with it; just

pretty time-consuming -- Dick's idea is your best bet. It is an interesting problem to try

to figure out necessary --let alone sufficient -- conditions for a map from R^n into R^m

(m>1 ) to be onto. Please let me know if you find them!

If you get are interested, look up Gelfond-Schneider:

http://en.wikipedia.org/wiki/Gelfond–Schneider_theorem

Last edited: Apr 20, 2013