1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: What does it mean to define an operation?

  1. Jan 12, 2013 #1
    I'm currently enrolled in a course covering semigroups (as an undergrad), and it's the first "abstract" math class I've taken so far. The assignment is to "Define a binary operation on [itex]\mathbb{N}[/itex] which is associative but not commutative," as well as other variations of the associativity/commutativity.

    My question is, what does it mean to define an operation? What's the procedure here? My prof didn't give any examples, so I don't know what to do here.

    The definition for binary operation (which I think I have a grasp on) given by our textbook is:
    "Given a set [itex]S[/itex], a binary operation [itex]\bullet[/itex] on [itex]S[/itex] is a function from [itex]S\times S[/itex] into [itex]S[/itex]. The image under [itex]\bullet[/itex] of an element [itex](s_1,s_2) \in S\times S[/itex] is denoted by [itex]s_1 \bullet s_2[/itex]; that is, [itex]s_1 \bullet s_2 \in S[/itex]."
  2. jcsd
  3. Jan 12, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Informally, you can think up anything you want to do with two positive integers that results in a positive integer for your operation. You obviously don't want to use the usual operations. Here are some random things you could try for your operation, which I will call @:

    n@m = max(n,m)
    n@m = |m-n|+1
    n@m = least common multiple of m and n
    n@m = n@m = n^m

    on and on. Surely you can think of some that aren't "nice" in the way you need.
  4. Jan 12, 2013 #3
    Ah, I see. Thanks for the breakdown!
  5. Jan 12, 2013 #4
    Ok, so I came up with a possible operation that I think is commutative but not associative.

    Define [itex]\# : \mathbb{N}\times\mathbb{N} \to \mathbb{N}[/itex] to be a binary operation on [itex]\mathbb{N}[/itex] such that [itex]\forall a,b \in \mathbb{N}, a \# b = |a-b|[/itex].

    I hope the structure's right and that it's easy to understand.

    How do I check for (non-)associativity in this particular case?
    I know that I have to show [itex]\forall a,b,c \in\mathbb{N}, a \# (b \# c) \not= (a \# b) \# c [/itex], but I'm a bit confused as to how the left hand side, for example, would translate.

    I'm thinking it's something like
    [itex]a \# (b \# c) = |a - (b \# c)| = |a - |b - c||[/itex]. Is this right?
  6. Jan 12, 2013 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Your Original Post said the operation should be "associative but not commutative".

    The operation here is the other way around.
  7. Jan 12, 2013 #6
    Yes, I know. I have a set of exercises like this one with minor variations (which I also mentioned in the same post), like "associative but not commutative," "commutative but not associative," both, and neither. Here I'm addressing the second exercise.

    Does the operation work, though? And is the syntax okay, especially the translation from a#(b#c) to |a-|b-c||?
  8. Jan 12, 2013 #7
    Associativity means ##\forall a,b,c \in\mathbb{N}, a \# (b \# c) = (a \# b) \# c##. That means that the criterion for non-associativity is actually ##\exists a,b,c \in\mathbb{N}, a \# (b \# c) \not= (a \# b) \# c##. That is, you only need a single example in which your operation isn't associative to demonstrate its non-associativity. Indeed, your operation is associative for certain cases like a,b, and c are equal, so you won't be able to prove what you're trying—but it doesn't associate for all numbers which is enough to be "non-associative".
    Last edited: Jan 12, 2013
  9. Jan 12, 2013 #8
    I get the feeling there's been a slight misunderstanding here. I'm showing that this operation is "commutative but not associative", and not "associative but not commutative." Sorry for the mix-up from the first post to the one I'm quoting here.

    I've already shown commutativity and non-associativity on paper (tinkering with the definition of |a-b| for commutativity and using a = 1, b = 2, and c = 3 to show non-associativity), but I'm not sure if I translated the operation properly from a#(b#c) to |a-|b-c||, and that's my concern.
  10. Jan 12, 2013 #9
    You haven't been misunderstood, I understand you are doing a different example. You are misunderstanding (at least in one part of your earlier comment) what it means to be non-associative. Read what I said very carefully. To be called "non-associative", there must exist a set of numbers it's not associative for. It doesn't need to be non-associative for all numbers. Indeed, non-associative operators usually are associative for certain examples (such as the one I gave).

    You said that to show non-associativity, you thought you had to prove ##\forall a,b,c \in\mathbb{N}, a \# (b \# c) \not= (a \# b) \# c##. That is wrong (and impossible). You just have to show there exists such an a,b,c.

    Your counterexample by itself is fine—I just want to make sure you're clear on what it is you have to show to demonstrate something does not have a particular property.
  11. Jan 12, 2013 #10
    And yes, you translated the operation correctly.
  12. Jan 12, 2013 #11
    Oh, I see. I was already aware of the fact that the negation of a "for all ..." is "there exists...", it just didn't quite register for whatever reason. Thanks for pointing out the mistake, though!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook