Showing a binary operation is injective

[SithsNGiggles]

Homework Statement

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

Homework Equations

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?

 

[Dick]

Homework Statement

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

Homework Equations

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?

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.

 

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

Thanks for the reply.

 

[Dick]

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?

Thanks for the reply.

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?

 

[HallsofIvy]

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)= x³+ y⁴.

if f(a,b)= f(c,d) means that a³+ b⁴= c³+ d⁴
That leads to a³- c^{3= d4- b4
(a- c)(a2+ ac+ c2= (d- b)(d3+ bd2+ b2d+ b3).}

 

[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

 

[SithsNGiggles]

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?

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

 

[Dick]

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

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.

 

[Bacle2]

Homework Statement

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

Homework Equations

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?

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.

 

[SithsNGiggles]

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.

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.

 

[Dick]

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.

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

 

[SithsNGiggles]

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

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:

Noting that, ##\forall~n\in\mathbb{N}\backslash\{1\},~(n^3)^4=(n^4)^3=n^{12}##, we can choose ##a=n^4,b=1,c=1,d=n^3## such that ##a*b=c*d##. It is thus apparent that ##*## fails to be injective for an infinite number of pairs ##(a,b)##.

(as per Bacle2's observation)

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

 

[Bacle2]

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.

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