Let * be an operation on two ordered lists of numbers, where each list has no duplicates. The operation concatenates them and then removes any adjacent identical values recursively.
I want to know if this operation on the set is associative.
For example, (1, 2, 3) * (3, 1, 2) = (1, 2, 1, 2).
I have looked at trying to find a counterexample but have struggled. I've written a program to iterate through quite a few examples and it's found nothing so I believe that it is associative, but am not sure how to go about proving it!
Does anyone know where I could start? I keep getting stuck with the thought of possible edge cases, e.g. where operating on lists X and Y removes some value that means something from Z isn't cancelled but would be if we operated on Y and Z first.
I pointed out in the comments that, in order for associativity to make sense, we really need a binary operation. Given a set $X$, a binary operation on $X$ is a function from $X \times X$ to $X$. That is, it takes two points in $X$, and produces another point that lies in $X$. This is important, so that $(x * y) * z$ makes sense. The operator $*$ will only work with two elements of $X$, so if $x * y \notin X$, then we are in trouble.
What we can do is broaden the set of strings we'll work with. Fix an alphabet $A$. We will start by defining our operation $*$ on the set of all strings $A^*$, and later restrict it to the set of pair-free strings i.e. strings that do not contain substrings of the form $\alpha \alpha$ for some symbol $\alpha$. We wish to define a binary operation $x * y$ on $A^*$ by concatenating $xy$, and "recursively removing pairs". The result of this will always be a pair-free string (and definitely will be contained in $A^*$).
All that said, regardless of whether we consider strings with pairs or not, there is a lot of hidden stuff to prove here. When we say "recursively remove pairs" what do we mean, precisely? If given a choice of which pair to remove, which do we do first? And, importantly, does it matter? Will we always end up at the same result, or do we have to commit to some kind of order in which we remove pairs, and will changing that affect associativity?
Essentially, I raise these issues to validate the seemingly excessive length of this answer. You're in for quite a read. That's the bad news, but the good news is, as CyclotomicField points out, this stuff is the bread and butter of people who study free groups (and other free structures), so this stuff is well-known. We will borrow the standard approach in order to prove associativity.
Let's start with the set of general strings $A^*$, and equip it with concatenation. This operation is clearly associative. Instead of restricting $A^*$ to pair-free strings, or defining $x * y$ as above, let's instead build an equivalence relation. Even defining this equivalence relation will take some time. To start, define the relation $\to$ on $A^*$: $$x \to y \iff \exists u,v \in A^*,\exists\alpha \in A:(x=u\alpha\alpha v, y=uv).$$ In other words, $x$ contains a pair $\alpha \alpha$, which, if we eliminate, produces $y$. This doesn't mean $y$ contains no pairs, or that $x$ contains no other pairs. For example $123322 \to 1222$, $123322 \to 1233$, and $1222 \to 12$, but $123322 \not\to 12$ (so it isn't transitive).
We can then define $\leftrightarrow$ to be the symmetrisation of this relation: $$x \leftrightarrow y \iff x \to y \text{ or }y \to x.$$ We will denote $x \leftarrow y$ to mean $y \to x$.
Further, we can let $\sim$ be the transitive (and reflexive) closure of $\leftrightarrow$, which we can call $\sim$. We will say that $x \sim y$ if and only if there exists some sequence $x_0, x_1, \ldots, x_n$ (for some $n \ge 0$), where $x_0 = x$ and $x_n = y$ such that $x_{i-1} \leftrightarrow x_i$ for all $i = 1, \ldots, n$. Note that $x \sim x$, as we can have $n = 0$. I won't prove it explicitly, but hopefully it's sufficiently clear that $\sim$ is an equivalence relation.
We will call this sequence $x_0, x_1, \ldots, x_n$, following the above condition, a path from $x$ to $y$. We may denote it by $$x_0 \leftrightarrow x_1 \leftrightarrow x_2 \leftrightarrow \ldots \leftrightarrow x_n.$$ If we know that one of the $\leftrightarrow$ symbols is a $\to$ or a $\leftarrow$, we might write that instead. For example, we could write: $$123322 \leftrightarrow 1222 \leftrightarrow 12 \leftrightarrow 3312,$$ and hence $123322 \sim 3312$, or we could write: $$123322 \to 1222 \to 12 \leftarrow 3312.$$
For example, $123322 \sim 3312$, taking $x_0 = 123322$, $x_1 = 1222$, $x_2 = 12$, $x_3 = 3312$, for example. Other choices of $x_i$ could produce equally valid paths from $12322$ to $3312$.
We need to prove two lemmas. Let's start with the easier one: that $\sim$ respects concatenation.
Proof. Let us first prove the following smaller claim: for any $x, y, z \in A^*$: $$x \to y \implies xz \to yz.$$ If we have $x \to y$, there exist $u, v \in A^*$ and $\alpha \in A$ such that $x = u\alpha\alpha v$ and $y = uv$. But then, $xz = u\alpha\alpha(vz)$ and $yz = u(vz)$, which implies $xz \to yz$, as required. Note that we can reverse this to get: $$x \leftrightarrow y \implies xz \leftrightarrow yz.$$ If we have $x \sim y$, there exists a path $$x = x_0 \leftrightarrow x_1 \leftrightarrow x_2 \leftrightarrow \ldots \leftrightarrow x_n = y,$$ and so $$xz = x_0z \leftrightarrow x_1 z \leftrightarrow x_2 \leftrightarrow \ldots \leftrightarrow x_nz = yz,$$ hence $xz \sim yz$. That is $$x \sim y \implies xz \sim yz.$$ Note that, similarly, $x \sim y \implies zx \sim zy$.
Now, if $x \sim x'$ and $y \sim y'$, then the former implies $xy \sim x'y$. The latter implies $x'y \sim x'y'$. As $\sim$ is an equivalence relation (transitive, in particular), we have $xy \sim x'y'$ as required, and the lemma is proven.
The next lemma is the meat of the proof. It will show that $*$ is well-defined and the order of reduction does not affect the outcome of $x * y$, which is vital for associativity.
Proof. Suppose we have an equivalence class $[x] \in A^*/\sim$. Fix $y \in [x]$ of minimal length. Clearly $y$ is pair free, i.e. $y \not\to z$ for any $z$, otherwise $z \in [x]$ and is two shorter than $y$.
Suppose $z \in [x]$. We then get a path: $$z = x_0 \leftrightarrow x_1 \leftrightarrow x_2 \leftrightarrow \ldots \leftrightarrow x_n = y.$$ Let us assume that it is of minimal length, and use this assumption to show there are no $x_{i-1} \leftarrow x_i$ steps.
Suppose there is an $x_{j-1} \leftarrow x_j$ step, and $j > 1$ is the maximum such index. The remaining steps to $x_n = y$ are all forward steps, i.e., $$x_{j-1} \leftarrow x_j \to x_{j+1} \to x_{j+2} \to \ldots \to y.$$ Note that $j \neq n$, because then $x_{n-1}$ would be two shorter than $x_n = y$, the minimum length string in $[x]$.
Our general plan of attack is to argue that the $x_{j-1} \leftarrow x_j$ step is an inefficiency. It introduces a pair $\alpha\alpha$ which must be eventually removed at some later $x_k \to x_{k+1}$ step. The moves made in the meantime, connecting $x_j$ to $x_k$, could be applied without having added $\alpha\alpha$ first, making a shorter path, and contradicting our shortest path hypothesis.
Let us define $u_j = u$ and $v_j = v$. If it is possible to express $x_{j+1}$ in the form $u'\alpha \alpha v'$ where, either $u \to u'$ and $v = v'$, or $u = u'$ and $v \to v'$, then fix one such choice of $u', v'$, and let $u_{j+1} = u'$ and $v_{j+1} = v'$.
Continue recursively in this fashion: given definitions of $u_j, \ldots, u_m$ and $v_j, \ldots, v_m$ such that $x_i = u_i \alpha \alpha v_i$, where $u_{i-1} \to u_i$ and $v_{i-1} = v_i$, or $u_{i-1} = u_i$ and $v_{i-1} \to v_i$, holds for all $i$ from $j+1$ to $m$, define, if possible, $u_{m+1}$ and $v_{m+1}$ to continue this pattern.
Eventually, this procedure must terminate. We cannot have $y = x_n = u_n \alpha \alpha v_n$, because then $y$ is not square-free. Thus, we must terminate at some index $j \le k < n$.
Let's look at what happens when we terminate. We know that $x_k \to x_{k+1}$, so there exist $p, q \in A^*$ and $\beta \in A$ such that $x_k = p \beta \beta q$ and $x_{k+1} = pq$. We also have $x_k = u_k \alpha \alpha v_k$. We look at five cases (note: in the final three cases, we must have $\beta = \alpha$):
Option 1 is not possible. If this is the case, then $u_k = p \beta \beta r$ for some $r \in A^*$, making $x_k = p \beta \beta r v_k$, forcing $q = r v_k$. Thus, $x_{k+1} = pq = prv_k$, where $u_k = p \beta \beta r \to pr$. We can set $u_{k+1} = pr$ and $v_{k+1} = v_k$, and thus we can continue the pattern, and so we did not need to terminate at $k$, against assumption.
A similar argument works to show option 2 is not possible. We can find $v_{k+1}$ and $u_{k+1}$ such that $u_k = u_{k+1}$ and $v_k \to v_{k+1}$. Thus, neither option 1 or 2 is possible, and we must have one of the options 3, 4, 5. I claim that, in any of these options, we have $x_{k+1} = u_kv_k$.
In option 5, this follows immediately. We have $x_k = pq$, which is simply $u_k v_k$; the $\beta\beta$ removed was the $\alpha\alpha$ from $u_k \alpha \alpha v_k$.
Let's suppose option 3 is the case. Then, $\alpha = \beta$, and we can express $u_k = p \alpha$ and $q = \alpha v_k$. We then have $x_{k+1} = pq = p\alpha v_k = u_k v_k$. A similar argument works for option 4. In any possible case, we have $x_{k+1} = u_k v_k$, as required.
We now have our index $k$ where the $x_{j-1} \leftarrow x_j$ move is undone. We now can construct a shorter path that removes this inefficiency. We consider: $$z = x_0 \leftrightarrow \ldots \leftrightarrow x_{j-1} = u_jv_j \to u_{j+1}v_{j+1} \to \ldots \to u_kv_k = x_{k+1} \to \ldots \to x_n = y.$$ This path is of length $n - 2$, which contradicts our hypothesis that $n$ was the shortest possible length.
Thus, our assumption that there must be a $x_{i-1} \leftarrow x_i$ step was incorrect. In the shortest possible path, all $\leftrightarrow$s must be $\to$s. We therefore see that every $z \in [x]$ must reduce directly to this element $y$, and this lemma is proven.
After all this, what do we have? We know that any string in $[x]$ must reduce directly down to the shortest element in $[x]$, which must be pair-free. The fact that any other element can reduce at all implies that this shortest string is the unique pair-free string in $[x]$.
In this way, we can uniquely identify an equivalence class $[x]$ with its unique pair-free element. The procedure of concatenating pair-free strings $x$ and $y$ and recursively removing pairs is, by claim 2, precisely the process of finding the unique pair-free string in $[xy]$.
We can now show that the operation $*$, if we consider it on the set of pair-free strings in $A^*$, is associative. Let $x*y$ be the unique pair-free element of $[xy]$. Then $x * y \sim xy$. By Lemma 1, $(x * y)z \sim (xy)z = xyz$. So, $(x * y)z$ and $xyz$ share the same unique pair-free element, by Lemma 2. That is, $(x * y) * z$ is the unique pair-free element of $[xyz]$. Similar logic shows that $x * (y * z)$ is also the unique pair-free element of $[xyz]$, so $$(x * y) * z = x * (y * z).$$ That is, the operation is (finally!) associative.