3
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – sss89 Jan 4 '16 at 11:36
  • $\begingroup$ :@sss89: good point, but you forgot to say "modulo choice of variable names". $\endgroup$ – Rob Arthan Jan 4 '16 at 17:26
  • $\begingroup$ 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. $\endgroup$ – Rob Arthan Jan 4 '16 at 18:09
  • $\begingroup$ @sss89: I am now wondering if the OP is allowing quantifiers. In which case your observation does not work. $\endgroup$ – Rob Arthan Jan 4 '16 at 18:13
  • $\begingroup$ @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 ;) ) $\endgroup$ – sss89 Jan 5 '16 at 15:29
1
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Meleagro di Gadara Jan 4 '16 at 18:15

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.