I can prove the generalisation of commutativity and associativity of unions, but I do not understand how they are generalisations of commutativity and associativity. I think it would help me grok the explanation more, if I understand what it means to generalise commutativity and associativity for an arbitrary binary operation. To that end, I would describe below what my intuitions for generalising commutativity and associativity for an arbitrary binary operation are. I'd appreciate critiquing my intuitons (if they're wrong), and presenting a correct formulation of the generalisations of the properties in question as a first step.

Definitions and Notation

$\circ$ represents the binary operation of interest.
$S$ represents the set of interest $(S \neq \emptyset)$.
$S*$ is the set of all possible orderings of $S$.
$S_i = \langle{i_1, i_2 ..., i_k, ...}\rangle$ represents an arbitrary ordering of the elements of S.
$S_i \in S*$. $${\underset{i_k \in S\_i} \bigcirc{i_k}} = (...((i_1) \circ i_2)\circ ...)\circ i_k)\circ...)$$ The above may be abbreviated as $\bigcirc{S_i}$ for convenience.

It is possible to consider $S_i$ as a (non empty) string whose characters are the different elements of $S$ (the string as the unique feature that no character occurs more than once in the string) and I shall do so.
$s_a^i$ represents a (non empty) substring of $S_i$.
$s_a^i(start)$ indicates the index of the first element in $s_a^i$.
$s_a^i(end)$ indicates the index of the last element in $s_a^i$.
$s_a^i \cdot s_b^i$ represents the concatenation of $s_a^i$ and $s_b^i$.
Non Overlapping: Two substrings $(s_a^i \text{ and } s_b^i (s_a^i \neq \varepsilon \, \& \, s_b^i \neq \varepsilon))$ of a given superstring $S_i$ are said to be non overlapping if $(s_a^i(end) > s_b^i(start)) \text{ or } (s_b^i(end) > s_a^i(start))$.
Complementary: Two substrings $(s_a^i \text{ and } s_b^i (s_a^i \neq \varepsilon \, \& \, s_b^i \neq \varepsilon))$ of a given superstring $S_i$ are said to be complementary if $s_a^i \cdot s_b^i = S_i$.
It follows that two substrings can only be complementary if they are non overlapping.


The specific case of commutativity involving two variables is defined as follows:
$a \circ b = b \circ a$.
My intuition for what generalising commutativity to arbitrarily many operands would mean is as follows: $$\bigcirc{S_i} = \bigcirc{S_j} \, \forall \, S_i, S_j \in S*$$ I believe that the above formulation of generalising commutativity is correct and I think I understand the generalisation of commutativity for unions (prior to writing this out, my intuitions for what generalising commutativity meant were different, but writing it out made me realise that it was not a generalisation at all, and after some manipulation with three variables, the above seemed like the natural way to generalise commutativity to an arbitrary number of variables).


The specific formulation of associativity involving three variables is defined as:
$a \circ (b \circ c) = (a \circ b) \circ c$.
My intuitions for how to generalise associativity are as follows:
Let $s_a^i$ and $s_b^i$ be any two complementary substrings of $S_i$.
Let $f (f \neq \varepsilon)$ and $g (g \neq \varepsilon)$ represent any two complementary substrings of $s_a^i$ with $(f(start) < g(start))$ ($f$ precedes $g$).
$$\bigcirc{s_a^i} \circ \bigcirc{s_b^i} = \bigcirc{f} \circ \bigcirc{(g \cdot s_b^i)}$$ The above is my best intuition for how to formalise generalising associativity of a binary operation, but I am much less confident that it is correct.

Related Questions


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.