1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Showing a binary operation is injective

  1. Apr 14, 2013 #1
    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. jcsd
  3. Apr 14, 2013 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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
  4. Apr 14, 2013 #3
    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.
     
  5. Apr 15, 2013 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  6. Apr 15, 2013 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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).
     
  7. Apr 15, 2013 #6
    @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
     
  8. Apr 15, 2013 #7
    ##n=1## and ##m>1## come to mind. Beyond that, I'm not sure. I'll put some more thought into it.
     
  9. Apr 15, 2013 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  10. Apr 15, 2013 #9

    Bacle2

    User Avatar
    Science Advisor

    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
  11. Apr 19, 2013 #10
    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.
     
  12. Apr 19, 2013 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Hint. Think prime numbers in f(n,m)=a^n*b^m.
     
  13. Apr 19, 2013 #12
    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
     
  14. Apr 20, 2013 #13

    Bacle2

    User Avatar
    Science Advisor

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Showing a binary operation is injective
  1. Binary operation (Replies: 5)

  2. Binary operations (Replies: 1)

Loading...