Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

What are some simple non-associative binary operations?

  1. Jul 28, 2013 #1

    Stephen Tashi

    User Avatar
    Science Advisor

    Suppose we are given a binary operation on a finite set of abstract symbols in terms of a multiplication table such as:

    [tex]
    \begin{array}{c|ccc}
    * & A & B & C \\ \hline
    A & A & B & C \\
    B & B & A & B \\
    C & C & B & A \\
    \end{array}
    [/tex]

    Suppose we want to represent the operation in some concrete way as a binary operation on some fairly simple mathematical objects. What are some good ways to do this? For example, are there simple binary operations on elements of a set or a group that are versatile enough to implement any multiplication table?

    Since the abstract binary operation need not be associative, commutative, have an identity etc, we need a concrete binary operation that need not be any of those things. But we would want to leave open the possibility that on a particular set of objects, the operation might have those properties since some multiplication tables have them.
     
  2. jcsd
  3. Jul 28, 2013 #2

    mathman

    User Avatar
    Science Advisor
    Gold Member

    I don't know what you are looking for. However the operation you described (table) is non-associative.
    BBC
    B(BC) = BB = A
    (BB)C = AC = C
     
  4. Jul 28, 2013 #3

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    For the thread title, some natural examples of non-associative operations are subtraction and division. For example

    (5-1)-1 = 3, 5-(1-1) = 5

    (5/2)/2 = 5/4, 5/(2/2) = 5

    Your more general question doesn't seem to be very well motivated - why do you need a more complicated way of constructing arbitrary binary operations than the one of 'just fill in the table however you want'
     
  5. Jul 28, 2013 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    On the contrary, "representation" is a well known theme in mathematics. For example, there is a representation theory for groups. The theory of group representations isn't general enough to represent arbitrary binary operations since anything that represents an abstract group on a concrete way is, of course, an associative operation that has an identity. So what are some ways to represent arbitrary binary operations?
     
  6. Jul 28, 2013 #5

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper

    http://www.proofwiki.org/wiki/Cross_Product_Not_Associative [Broken]
     
    Last edited by a moderator: May 6, 2017
  7. Jul 29, 2013 #6

    lurflurf

    User Avatar
    Homework Helper

    I take it you are thinking a group is often represented an a permutation or linear operator (matrix). A magma has very little structure so there is not much to represent. Usually we need to restrict ourselves to magma with additional structure like Power associativity, alternativity, or N-ary associativity before much can be done.
     
  8. Jul 29, 2013 #7

    Stephen Tashi

    User Avatar
    Science Advisor

    Yes, a general view of those methods is that a group can be represented as a set of 1-to-1 functions on the same space using the the composition of functions as the group operation. That general view only involves very simple mathematical objects. ( I think a semi-group is also representable in that manner.) The problem with representing a general binary operation as set of functions is that the composition of functions (when it is defined) is associative. Perhaps some generalization of the concept of composing functions would work.

    If it is true that "not much can be done" then I think the cause of this must be that it is impossible to find a simple binary operation that doesn't have a lot of structure. That may be true. For example, a simple operation like taking the union of sets is associative and commutative. I don't know what varieties of behavior can be exhibited by a binary operation that is defined in terms of some compound operation on two sets that involves, union, intersection, taking complements etc. I dont' know what varieties of behavior can be exhibited by short expressions that involve modular arithmetic. I consider using expressions involving modular arithmetic to be a rather complicated way of doing things compared to the simple way that groups are represented.

    It would be ironic if the only way to define a binary operation that doesn't have much structure is to form some complicated expression out of simple binary operations.
     
  9. Jul 29, 2013 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    It is simple to find that. Just fill the multiplication table randomly.
    It might be tricky to find a "nice" representation of this operation (easier to remember than the full table), but that really depends on the way you define "nice". In general, this "nice" representation would need as much freedom as your multiplication table, so it has to get messy...
     
  10. Jul 29, 2013 #9

    Stephen Tashi

    User Avatar
    Science Advisor

    In case the idea of a "representation" of groupoids isn't clear, it would consist of a single binary operation on a certain type of mathematical object and various multiplication tables could be represented by varying the particular objects selected, not by varying the binary operation. So filling out one table does not define the binary operation.

    I agree that there is a surprising amount of freedom. I recall reading somewhere that the number of semigroups of order 7 is more than 800,000. (I think this was in documentation for a program that generated them.) I don't know any result for the number of non-isomorphic groupoids of order 7.

    However, there are relatively simple mathematical objects that have many "degrees of freedom". For example, n by n matrices whose entries are 0's or 1's can be used to represent finite groups where the operation of the group is represented by multiplication of matrices. I think all the 800,000 plus semigroups of order 7 can be represented that way. The problem with trying represent groupoids by matrix multiplication is that matrix multiplication is associative.

    Office_Shredder suggested subtraction and division as non-associative operations. What kinds of groupoids can be reprsented by taking a finite set of integers and doing subtraction and division modulo M, where M is not necessarily a prime?
     
    Last edited: Jul 29, 2013
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: What are some simple non-associative binary operations?
  1. Non-Associative groups (Replies: 3)

Loading...