Can we derive associativity of symmetric difference from its simpler properties?

Question

The symmetric difference $Δ: (X)×(X) →(X)$ has a few obvious properties:

1. $∅$ acts as the neutral element, i.e. $SΔ∅ = S$
2. It is commutative
3. Every element is its own inverse.

The (imo) only non-obvious property, which demands a Venn diagram or direct calculation, is associativity. I was wondering whether what we have is already strong enough to deduce associativity.

Question 1 In the signature $Ω=((\circ, 2), (e, 0))$ do the equations \begin{align*} x \circ e &≈ x\\ x\circ y &≈ y \circ x\\ x \circ x &≈ e \end{align*} already imply $$ x\circ(y\circ z) ≈ (x\circ y)\circ z\:?$$ If not, what is an example of a non-associative $Ω$-algebra satisfying those equations?

Edit 1: I found Answer 1. The set $\{e, x, y\}$ with the operation defined as $xy:= yx := y$ (and the other combinations following the axioms) satisfies $(xy)y = yy = e$, but $x(yy) = xe = x$.

So we need another axiom, and I think $AΔ(AΔB) = B$ is a good intuitive candidate for another property.

Question 2 Does associativity follow when we add the equation $ x\circ (x\circ y) ≈ y$?

Edit 2: I think this should also not be enough, since we might be able to get a “free” model of this theory by choosing a linear order on terms and representing terms as the subset of terms (which visually are binary trees) for which we forbid structures of the form $t₁(t₂ t₁)$ and $t₁(t₁ t₂)$. The neutral element $e$ would just be the empty tree (empty word).

Then the action of a (nonempty) tree $t$ is defined by $t₁\ t ↦ t₁$, $t\ t₁ ↦ t₁$ (cutting of an existing branch) to satisfy the involutive property, and $t₁\ t₂ ↦ t\ (t₁\ t₂)$ whenever $t₁, t₂ \neq t$ and $t ≤ t₁\ t₂$, and $t₁\ t₂ ↦ (t₁\ t₂)\ t$ in case of $≥$. Discovering that $x (yz)$ and $(xy) z$ are different would then be evident because these are just different terms.

Question 3 Is the above idea feasible, i.e. is there a precise definition of terms and a linear order on these terms such that we can define this “free model” over a generator set $S$?

Answer 1

Here is one way to implement the free structure you propose. Fix a set $S$ of generators and let $T$ be the set of all finite strings on the alphabet $S\sqcup\{e,(,)\}$. Fix some total order $\leq$ on $T$. Define a binary operation $\circ$ on $T$ as follows. Given $x,y\in T$, define $x\circ y$ using the first entry in the list below whose hypothesis is true.

• If $x=e$, then $x\circ y=y$.
• If $y=e$ then $x\circ y=x$.
• If $x=y$ then $x\circ y=e$.
• If $x=(ay)$ for some $a\in T$ then $x\circ y=a$.
• If $x=(ya)$ for some $a\in T$ then $x\circ y=a$.
• If $y=(ax)$ for some $a\in T$ then $x\circ y=a$.
• If $y=(xa)$ for some $a\in T$ then $x\circ y=a$.
• If $x\leq y$ then $x\circ y=(xy)$.
• If $y\leq x$ then $x\circ y=(yx)$.

Now let $A\subset T$ be the closure of $S\sqcup\{e\}$ under this operation $\circ$. The following properties are then easy but tedious to verify by induction. Every element of $A$ is either an element of $S\sqcup\{e\}$ or else has the form $(xy)$ where $x,y\in A$, $x<y$, $x$ does not have the form $(ay)$ or $(ya)$, and $y$ does not have the form $(ax)$ or $(xa)$. In the latter case, $x$ and $y$ are moreover uniquely determined. Finally, $A$ satisfies all the axioms $x\circ e=x$, $x\circ y=y\circ x$, $x\circ x=e$, and $x\circ(x\circ y)=y$. However, if $x,y,z\in S$ are distinct then $x\circ (y\circ z)$ and $(x\circ y)\circ z$ will be distinct, so $\circ$ is not associative on $A$.

Let me further remark that these axioms imply all equational axioms which hold in a power set and involve at most two variables. Indeed, these axioms suffice to compute the entire operation $\circ$ on any set of the form $\{e,x,y,x\circ y\}$ (given two elements $s,t\in \{e,x,y,x\circ y\}$, you can always use the axioms to reduce $s\circ t$ down to another element of $\{e,x,y,x\circ y\}$, and it is always the element you would get if $\circ$ were actually symmetric diference). It follows that the subalgebra generated by $x$ and $y$ is in fact isomorphic to the power set of some set with $\circ$ as symmetric difference.

So, in order to get associativity, it is necessary to add some axiom which involves at least three variables.

Answer 2

EDIT: The following does not provide a counterexample, as I had overlooked the requirement of commutativity.

Consider the set $\{e,x,y\}$ with the operation defined by $xy=y$ and $yx=x$, and following the given axioms. Then $$e(ex)=ex=x$$ $$e(ey)=ey=y$$ $$x(xe)=xx=e$$ $$y(ye)=yy=e$$ $$x(xy)=xy=y$$ $$y(yx)=yx=x$$ But $x(yx)=xx=e$ whereas $(xy)x=yx=x$.