the Nature of Associative Property of Algebra
yesterday i had a revelation, on algebra's associative property.
the commutative property:
a+b == b+a
is intuitive, that either order matters or not.
but associative property:
(a+b)+c == a+(b+c)
is not so intuitive. Seems something artificial about this property. What's the nature of associative property?
associative property appears to be related to order, but not in some clear way.
what i realized yesterday, is that both commutative and associative properties are about order of operation.
it will be more clear if we write associativity in function notation:
f[f[a,b],c] == f[a,f[b,c]]
so, first of all, it IS clearly about order, of some sorts.
and also, note, associative means:
((a+b)+c)+d == (a+b)+(c+d) == (a+(b+c))+d == a+((b+c)+d) == a+(b+(c+d))
that is, if you have a ordered sequence of things and you want to “multiply” them all together, then, the grouping doesn't matter.
Combinatorial Listing of Binary Operation in a Set
then, i thought, if commutative and associative properties are 2 necessary items about order of operations, then, perhaps there's a logical system that can derive this.
if you think about this, it's not hard to see they are 2 of the most basic properties about order of operation.
start by having a set of just 2 elements. That is, we have a set of just 2 elements {a,b}, and a function of 2 args f[x,y].
What is all possible ways to apply the function to the set?
We have {f[a,b], f[b,a]}. There, we see the question of commutative property showing up. That is, whether f[a,b] == f[b,a].
but once you have 3 elements, associativity shows up.
Now let's start with a set with just 3 elements {a,b,c}, and again with a function f[x,y]. We list all possible ways to apply the function to all elements of the set, repeatedly, so that all element are used once. (but not twice).
We have:
a*(b*c) a*(c*b) b*(c*a) b*(a*c) c*(a*b) c*(b*a) (b*c)*a (c*b)*a (c*a)*b (a*c)*b (a*b)*c (b*a)*c
(for clarity, we write f[x,y]
as x*y
)
Now, if we look at the list, and try to organize them. First we can see commutative situation, such as in {a*(c*b)
, a*(b*c)
} , because we saw that when the set has just 2 elements. Now, if we remove items that are commutative equivalent, we just got this:
a*(b*c) b*(c*a) c*(a*b)
rearrange them using commutative property, we have:
a*(b*c) (a*b)*c b*(a*c)
The first 2 items, we see the associative property.
Ternary Operations and Possible Order in Algebra
Now, if we consider ternary operations, more strange properties about order of operation will come up. For example:
f[a,b,c] == f[a,c,b] f[a,b,c] == f[b,a,c] f[a,b,c] == f[b,c,a] f[a,b,c] == f[c,a,b] f[a,b,c] == f[c,b,a]
so, now you can see, this is a more complex version of the idea of commutativity.
Commutativity is about the order of arguments.
Similarly, we have:
f[f[a,b,c],d,e] == f[a,f[b,c,d],e] f[a,f[b,c,d],e] == f[a,b,f[c,d,e]] f[a,b,f[c,d,e]] == f[f[a,b,c],d,e]
and we can see that this is a more complex version of associativity.
Associativity is about nesting order.
Whence Distributive Law Came From?
another thing that's not intuitive is distributive law.
a+(b*c) == (a+b)*(a+c)
or, in function notation:
f[a,g[b,c]] == f[g[a,b],g[a,c]]
Now, it's easy to understand it. It's simply one of the possible situation when you have 2 binary operations on 3 arguments.
Visually Understanding Commutative and Associative Properties
if you plot the multiplication table, of a binary operation on a set, you can clearly see it if the operation is commutative. If so, its multiplication table will be symmetric alone the diagonal.
is there similar visual quality about associative groupoid?
Generalization and Summary
Here is a summary of what's going on.
- We have a set of n things
- we have a set of m operations, which we'll call functions. We will write f[1] as first function, f[2] the second function.
- Each function has arity. That is, number of arguments. We'll denote it as Arity[f[n]].
- Let v be the level of nesting allowed. For example
f[a,f[b,c]]
would be 1 level of nesting.
The problem here is to enumerate them, and see when concept of commutativity and associativity and distributive law turns up, and what other perhaps unnamed property turns up.