Defining associative law with less than $4$ binary function symbols

Let $L$ be a first order alphabet with only a binary function symbol, $*$.

I am aware that one can express the associative law formula $\phi$, defined by $a*(b*c)=(a*b)*c$, with less than $4$ occurrence of the symbol $*$.

Although, I can't seem to find any formula which uses less than $4$ symbols. Looks like there is even a way to express this using a single $*$.

Can any of you find these formulas, or give some kind of hint$?$

Thank you very much

EDIT: I forgot to mention that I allow for quantifiers to be used in the alternate such formula $\psi$. Thus, we can let $\phi$ be $\forall a \forall b \forall c(a*(b*c)=(a*b)*c)$.Just to be clear, one can use any quantity of any logical symbol in the language except for the function symbol $*$ which has to be used at most $3$ times. Sorry for the mistake.

• There are only finitely many formulas with less than 4 occurrences of *. You can just go through them (preferably with computer program) and check if they define associativity. – sss89 Jan 4 '16 at 11:36
• :@sss89: good point, but you forgot to say "modulo choice of variable names". – Rob Arthan Jan 4 '16 at 17:26
• Why do you think such formulas exist? See my answer for a proof that no quantifier-free formula (i.e. purely universal formula) can work. – Rob Arthan Jan 4 '16 at 18:09
• @sss89: I am now wondering if the OP is allowing quantifiers. In which case your observation does not work. – Rob Arthan Jan 4 '16 at 18:13
• @Rob: there is still finitely many such formulas. Indeed, the only non logical symbol in the language is *, thus any quantifier free formula with at most 3 occurrences of * has at most 4 free variables and thus, there are still finitely many formulas (modulo choice of variable names ;) ) – sss89 Jan 5 '16 at 15:29

Looks like a professor from my department found the answer.

An equivalent formula to the one I stated in the OP is:

$$\forall a \forall b \forall c \forall d \forall e \forall f \forall g \,(a*b=d \land d*c=e \land b*c=f \land a*f=g \Rightarrow e=g)$$

This is not actually necessary, it's just to better understand what happens next:

$$\forall a \forall b \forall c \forall d \forall e \forall f \forall g (\forall x \forall y \forall z \, ((x=a \land y=b \land z=d) \lor (x=d \land y=c \land z=e) \lor (x=b \land y=c \land z=f) \lor (x=a \land y=f \land z=g) \Rightarrow x*y=z) \Rightarrow e=g)$$

This last formula is equivalent to the associativity statement and uses only a single $*$ symbol.

Thanks to everyone who tried!

The following argument does not answer the general question (as now clarified), but I have left it here in case it is of help to anyone:

There is no equation with fewer than four occurrences of $*$ that characterizes associativity: to see this, let $F = A^+$ comprise non-empty strings with elements drawn from the set $A = \{X, Y, Z\}$ and consider the algebra $\mathbf{F} = (F, *)$ where $*$ is interpreted as concatenation. So, for example, you have $XYZ * XXY = XYZXXY$. $\mathbf{F}$ is associative so your formula defining associativity must hold in $\mathbf{F}$. Argue that a formula with less than 4 occurrences of $*$ must be equivalent to one of the form $x = t$, or $x * y = u$ (where $x$ and $y$ are variables). Then argue that in $\mathbf{F}$, the only valid formulas of these forms are the trivially valid formulas $x = x$ and $x * y = x * y$.

• I'm sorry I guiltily forgot to say I can use as many quantifiers as needed, although there would be no such formula. I'll edit the OP too, thanks for the hint anyway! – Meleagro di Gadara Jan 4 '16 at 18:15