What Does the Associative Property Mean Intuitively Across All Notational Schemes?

You can find descriptions of associativity as intuitively meaning that the order of operations performed does not matter, e. g. such as that of Wikipedia. However, if you write what associativity means in terms of a formula in either prefix notation, that is that for some binary operation X, XXxyz=XxXyz, or suffix notation xyzXX=xyXzX, the intuitive description of associativity loses sense. So, what does associativity mean intuitively in a prefix or suffix scheme? I suppose one might say that in prefix and suffix notation, associativity means that one can push the second instance of the operation in as far as we can, or as far out as we can and still have an equivalent expression. But, this does not seem to fit with an intuitive description of associativity in an infix notation.

So, what does associativity mean across all notational schemes? Can we meaningfully talk about associativity across all notational schemes, or do intuitive descriptions only work as local to a particular notational scheme?

Addendum: I'm not quite sure if this belongs here or on Philosophy Stack Exchange. I would like it imported there, if it seems more fitting there.

-
This is sort of related to...Associativity is equivalent to left and right multiplication operators commuting. Define $L_x(y)=xy$ and $R_z(y)=yz$. Then $(xy)z=x(yz)$ is the same as $R_z(L_x(y))=L_x(R_z(y))$ so that $R_z \circ L_x = L_x \circ R_z$. In $XXxyz$ view $Xx$ like $L_x$ and $X(\cdots)z$ as $R_z$. Then $X(Xx\cdots)z=XxX(\cdots)z$. – Bill Cook Oct 27 '11 at 2:11
Maybe more relevant is "Good notation helps you see patterns." whereas "Bad notation obscures patterns." – Bill Cook Oct 27 '11 at 2:13
How could one possibly formulate an answer "for all possible notational schemes?" – Grumpy Parsnip Oct 27 '11 at 2:20
I've never seen this called "suffix notation" before. As far as I'm aware the usual terms are prefix notation and postfix notation. Interestingly, searching for "suffix notation" yields texts (even books) that seem to be using "suffix" as a synonym for "subscript", which is also a usage I hadn't come across before. – joriki Oct 27 '11 at 5:50
@Doug: Unlike a suffix like -ed, the operator isn't appended to anything in postfix notation, it's placed behind (Latin post) things. I was commenting on how this notation is usually referred to, not on how it should be referred to, but if you ask me, that's also how it makes sense to refer to it. – joriki Oct 28 '11 at 0:18

3 Answers

The nature of associativity can be best realized by realizing that a binary operator:

$$b:X\times X \rightarrow X$$

Has a natural adjoint (where $X^X$ is the set of functions from $X$ to $X$:)

$$b^*:X \rightarrow X^X$$

defined by: $b^*(x)(y)=b(x,y)$

A binary operation is then associative if and only if it corresponds to function composition on $X^X$. That is, there is a natural composition binary operator:

$$\circ: X^X \times X^X \rightarrow X^X$$

Then $b$ is associative if and only if for all $x,y\in X$:

$$b^*(b(x,y)) = b^*(x) \circ b^*(y)$$

So, in that sense, associativity is always represented as composition of functions.

Comment added much later:

As Joriki noted in comments, there is another adjoint, $^*b$, which is defined as $^*b(x)(y)=b(y,x)$.

In some sense, then, prefix notation, $Kxy$, can be thought of as representing $Kx=b^*(x)$ applied to $y$. And $xyK$ can be seen as the operation $^*b(y)$ to x. In that sense, the prefix notation represents the first adjoint, $b^*$, the infix represents the binary operator, $b$, and the suffix notation represents the second adjoint, $^*b$.

-
+1, this is a great point I'd never heard before! – Zev Chonoles Oct 27 '11 at 21:49
+1, very nice. There are actually two such adjoints, one for left multiplication (which you defined) and one for right multiplication, $^*b(y)(x)=b(x,y)$, with $^*b(b(x,y))=^*b(y)\circ ^*b(x)$. – joriki Oct 28 '11 at 0:07
I'm not following this "b*(x)(y)=b(x,y)" In the previous line, you indicated b* as having one input. So, I would expect b*(x) to equal a constant if we have a value for x. But, then I don't know what say 3(y) means. Can you clarify things here? – Doug Spoonwood Oct 28 '11 at 1:01
$b^*(x)$ is in $X^X$ - that is, it is a function from $X$ to $X$. We define $b^*(x)$ so as the function $f$ such that $f(y)=b(x,y)$. – Thomas Andrews Oct 28 '11 at 1:33
Yes, that's it exactly. – Thomas Andrews Oct 28 '11 at 2:36

I disagree with the premise implicit in the question that the meaning of associativity depends on the notational scheme used to denote operations. Associativity means that the order of operations doesn't matter (or that left and right multiplication commute, as Bill pointed out). What this description loses when you use prefix or postfix notation is not sense but visibility. The meaning of natural numbers as a universal counting device doesn't lose sense in Japanese just because it uses several dozen counting particles for different classes of things.

If, on the other hand, the question were how to describe syntactically how associativity manifests in various notational schemes, I'd say the answer is that in infix notation parentheses become unnecessary, in prefix notation you can write the operations as early as you want to (and no later than their operands) and in postfix notation you can write them as late as you want to (and no earlier than their operands). Whereas in infix notation there's no "canonical" form for a multiple operation (i.e. no reason to prefer one of $x\circ(y\circ z)$ and $(x\circ y)\circ z$ over the other), and the clearest way to write one is by dropping the parentheses, in prefix/postfix notation the canonical form would seem to be to have all the operators at the front/end.

-
(+1) for the really instructive distinction between sense and visibility. After this answer I've go a vague suspection the OP might have something more specific/deeper in mind, without getting it perfectly explicite. Perhaps more instructive were examples, where in fact associativity fails and to work out the problem besides of the pure visibility aspect. ...(continued) – Gottfried Helms Oct 27 '11 at 7:07
... I've come only once across lacking associativity: with the use of matrices of infinite size; here an example expression $\small V(x)*P^{-1}*S1=V(log(x))$ made sense if it was done as $\small (V(x)*P^{-1})*S1=V(log(x))$ but not if as $\small V(x)*(P^{-1}*S1)=V(log(x))$ because of occuring singularities, (where full associativity exists in the inverse operation $\small V(log(x))*S1^{-1}*P=V(x)$ . A more distinctive notation than the usual infix/prefix/postfix were something like $\circ(a,b,c)$ meaning the order of the operands is relevant and $\circ<a,b,c>$ meaning it is not. – Gottfried Helms Oct 27 '11 at 7:15
"Sense and visibility" sounds like the title of a lost Austen novel :) – Mariano Suárez-Alvarez Oct 27 '11 at 8:27
That reminds me rather of the phenomenon of creating long lists of specific "collective nouns" for every possible kind of element (which I think is an obsession specific to English, but doesn't mean that the concept of a set loses sense there). – Henning Makholm Oct 27 '11 at 13:18
@GottfriedHelms I don't quite follow you. If you pick an operation at random, on say an n-element set, where n indicates a natural number greater than 2, you're much more likely to have picked a non-associative operation than an associative operation (math.stackexchange.com/questions/45648/…). In other words, non-associative operations abound, and associative operations are very rare, in some sense. So, finding examples here isn't all that much of a problem, at least, in principle. – Doug Spoonwood Oct 28 '11 at 0:50

An alternative point on view of associativity is that it isn’t about binary operations at all.

An associative operation on a set is, intuitively, a way to aggregate any finite tuple of elements from the set into an element of the set — formally, a family of operations $\mu_n : X^n \to X$, for each $n>0$ (or possibly $n \geq 0$ — more on this later) — such that any way of combining these operations, without permutation, deletion, or duplication, is the same as the specified operation of that length.

For instance: given a list $(x,y,z,w)$, we could take $\mu_4(x,y,z,w)$ directly; or we could look at the composite operation $\mu_2(x,\mu_3(y,z,w))$. (Notice: no permutation, duplication, or deletion of the elements $(x,y,z,w)$.) Generalised associativity says that these are equal.

The classical associativity law, $\mu_2(\mu_2(x,y),z) = \mu_2(x,\mu_2(y,z))$ clearly follows from this (since both are equal to $\mu_3(x,y,z)$; and it so happens that given $\mu_2$ satisfying this, one can always reconstruct the rest of the operations. So one can get away with just working with binary operations and this single law. However, intuitively, I find it useful to think of associative operations as really being the whole family of $n$-ary operators, for all $n > 0$. (Taking $n \geq 0$ corresponds to associative and unital binary operations.)

In practice, for instance, if I want to check whether some operation is associative, the first thing I’ll do is to try writing down a formula for a generalised $n$-ary version; if this comes naturally, then the operation will almost always be associative.

For example, the convolution product for functions from a finite group into a ring is defined by $$(f \ast g)(x) := \sum_{yz = x} f(y) g(z)$$ Calculating associativity by hand takes maybe three lines and forty-five seconds — but you can see immediately, just by looking at it, that it generalises to a ternary version, $$(f \ast g \ast h)(x) := \sum_{yzw = x} f(y) g(z) h(w)$$ (and to $n$-ary versions for other $n$), and this gives a strong heuristic clue that it will be associative.

This viewpoint is formalised in the theory of operads, and is essential for generalising to subtler notions such as “up-to-homotopy-associative”.

-
I like this answer, but I think it has some problems. An associative binary operation will imply an aggregation operation as making sense. But, will an aggregation operation imply an associative binary operation? I doubt that an aggregation operation implies an associative binary operation as making sense "almost always" and even "mostly", with mostly meaning the majority of the time once we consider all n-ary operations. I don't know by any means though. – Doug Spoonwood Jun 12 '13 at 23:32
It does; this is a standard fact of operads, essentially the fact that the two descriptions of the associative operad given on Wiki agree — on the one hand, “generated by a single binary operation, satisfying [classical associativity]” and on the other, “exactly one $n$-ary operation for each $n$”. In terms of my description above, it follows from “any way of combining these operations […] is the same as the specified operation”, since that implies that μ2(μ2(x,y),z) and μ2(x,μ2(y,z)) are each equal to μ3(x,y,z). – Peter LeFanu Lumsdaine Jun 13 '13 at 1:53