# 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
show 6 more comments

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
show 1 more comment

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
show 8 more comments