4
$\begingroup$

Can only a map $$*:S\times S\rightarrow S$$ be associative?

If I look at $$(a* b)* c=a* (b* c),$$ then it seems I have to rule out the more general case $$*:A\times B\rightarrow C.$$

But $A=B=C$ is really the only restriction for a binary operation to be a magma. Hence, if my assumption is true, for a relation to be associative is the exact same thing as being a semi-group. This redundancy in notation (one could just state that a relation together with its set is a semigroup) just surprised me.

(Here is a previous thread about a related point.)

3 Answers 3

6

Let me make a general philosophical point about definitions. A mathematical definition is much more than just its bare semantic content. A definition also carries an implicit intent which must be understood from the way it is used in practice.

For example, the mathematical definitions of directed (multi)graph and quiver are equivalent. So why do some people say directed (multi)graph and others say quiver? It is the intent behind the term: people who say directed (multi)graph want to do graph theory of some kind, whereas people who say quiver specifically want to study quiver representations, quiver varieties, etc.

There are also various examples in category theory of constructions which, on the level of category theory, are formally equivalent (e.g. pullback and fiber product) but which are named after special cases which occur in different contexts. Choosing to use one name over the other evokes a particular context and activates certain intuitions related to whatever you're going to use the construction for.


So, back to your question: strictly speaking the word "associative" is (in my experience) only used to describe a property of a map $S \times S \to S$, so saying "$f$ is associative" is formally equivalent to saying "$f$ defines a semigroup." But these two words occur in different contexts. When you want to talk about a given operation being associative, it is usually in the context of potentially several other operations (e.g. addition in the context of multiplication), whereas when you want to talk about a semigroup, you are usually only talking about the one operation. Failing to recognize this difference in intent will make it very difficult for people to understand you in practice even if you are, on a formal semantic level, saying the correct thing.

  • 0
    A related point is that there's no reason to be afraid of redundancy. Redundancy is useful. It keeps your mathematics robust from transmission errors (e.g. typos and misreading). Anything that helps you be understood is useful (assuming one of your goals is to be understood).2012-08-21
  • 2
    Occasionally, we talk about associativity in other cases, specifically, for example in map composition in category theory. More concretely, for example, matrix multiplication is associative even when not dealing with square matrices.2012-08-21
  • 0
    @ThomasAndrews: Okay I see, thanks. Is this then still a property of a relation in the set theoretic sense? Regarding rules about what kind of oder doesn't matter expressed in this kind of associativity, I'm not sure how evaluation of functions is understood. Mathematica has an "Evaluate" command, I don't know how this is formalized. When I try to think about it my heads wants to map two functions to one.2012-08-21
  • 0
    kk, thanks. I have no problem with redundancy, I just want to make sure when I can carry over theorems involving "associative" to theorems involving "semi-groups" and when not. E.g. I find the idea sad that category theorists from one corner prove theorems about things they work with and the people from the other corner are in need for results which are hidden in the other language. Btw. I like the new pic.2012-08-21
  • 0
    @Thomas: okay, but in that case I would still talk about associativity as a property of a map, only for composition of morphisms this map is composition itself, and it's only partially defined.2012-08-21
  • 0
    @QiaochuYuan Yeah, I just mean it isn't a map of the form $S\times S\to S$. You said "only used to describe a property of a map $S\times S\to S$. Multiplication of matrices is not of this form.2012-08-21
  • 0
    @NickKidman In category theory, in general, the collection of maps is not a set, so it is not really a relationship. But you can have some cases where the maps are a set - specifically, in "small categories." You can consider the of finite-dimensional matrices over a field with multiplication as the operation such a "set" case.2012-08-21
2

Supplementing Qiaochu's answer:

Formally, if $f:S\times S\to S$, then saying "$f$ is associative" and "$(S,f)$ is a semigroup" convey the same information.

However, if you say the "$(S,f)$ is a semigroup" then you set up the reader to expect that if you later speak about "homomorphisms" and/or "isomorphisms", then what you're talking about semigroup morphisms. If $S$ has some structure in addition to $f$ (for example, it might be a ring or a Boolean algebra or whatever), then once you mention two different structures on the same base set you'll be obliged to specify which of these structures you mean each time you mention a homomorpism/isomorphism/whatever. That get very tedious quickly.

Therefore it is extremely convenient to have a way to speak about associativity as a property of the operation, rather than a property of the entire structure the operation is part of.

2

All sorts of things are associative. If we have functions

$f:A \rightarrow B$

$g:B \rightarrow C$

$h:C \rightarrow D$

they satisfy $(f \circ g)\circ h = f\circ (g\circ h) $ where the operation is composition of functions. And this enables us to see that all sorts of constructions are associative. It can, for example, be used to prove the associativity of matrix multiplication.

In an Algebra, multiplication by a 'scalar' associates with with the Algebra multiplication.

  • 0
    Okay, right. The idea is clear. I wonder if the first and the second $\circ$ in $(f \circ g)\circ h$ is the same operation if the domains/codomains of the function are different.2012-08-21
  • 0
    Sorry, I missed that you were looking to restrict in that way. The usual definition for a semigroup is a set together with an associative binary operation. The more general concept "associative" is being applied to the case of a "binary operation" on a set, as you describe in your post.2012-08-21
  • 0
    Nah, it's okay, the answer was quite informative. Now I'm searching for a proper understanding of this other kind of associative Thomas Andrews mentioned in his comment. It seems to be the same as yours here. The explaination in terms of the string $(f\circ g)\circ h=f\circ (g\circ h)$ will suffice for now.2012-08-21
  • 0
    @NickKidman: You can view function composition as a _partial_ (class) function whose domain is all pairs of functions. It is still associative in the sense that if one of $(f\circ g)\circ h$ and $f\circ(g\circ h)$ exists, then the other one also exists and has the same value.2012-08-21