2

This is a natural follow-up to my previous question, here: Examples of two finite magmas which satisfy the same equations but not the same quasi-equations?. In the answer to that question, Keith Kearnes said that any two magmas on $\{0,1\}$ that satisfy the same equations are isomorphic. My question now is, is there a finite set $S$ and two binary operations $+$ and $*$ on $S$ such that the magmas $(S;+)$ and $(S;*)$ satisfy the same equations and also the same quasi-equations, but such that they are not elementarily equivalent, i.e, they do not have the same first-order theory? And if so, what is the smallest possible cardinality of $S$? It has to be at least $3$, that is for sure. If the exact answer is unknown, I would like to know very good upper and lower bounds.

user107952
  • 20,508
  • 5
    Why do you write "elementarily equivalent" instead of "isomorphic"? Finite structures are elementarily equivalent if and only if they are isomorphic. – Alex Kruckman Mar 28 '24 at 23:24
  • @AlexKruckman Well, yes that is true, but I wrote that because I am interested in two magmas which do not have the same first-order theory, but which satisfy the same quasi-equations. – user107952 Mar 29 '24 at 00:05

1 Answers1

5

There are two magmas (in fact semilattices) of order $3$ which satisfy the same quasi-identities (universal Horn sentences) but are not elementarily equivalent. Namely, let $A=\{1,2,3\}$ and $B=\{1,2,4\}$, both with the operation $x*y=\gcd(x,y)$. They satisfy the same quasi-identities because $A$ and $B$ are isomorphic to subalgebras of $C\times C$ where $C=\{1,2\}=A\cap B$. They are not elementarily equivalent because the sentence $\forall x\forall y(x*y=x\lor x*y=y)$ holds in $B$ but not in $A$.

The magma $B=(\{1,2,4\};*)$ is isomorphic to the magma $B'=(\{1,2,3\};\circ)$ where $x\circ y=\min(x,y)$.

bof
  • 78,265
  • Yeah, but I want a single set $S$ and two operations on it. You gave me two sets. – user107952 Mar 29 '24 at 16:28
  • 2
    So what? What difference does it make? If $S$ is a $3$-element set, then any magma of order $3$ is isomorphic to a magma whose underlying set is $S$. – bof Mar 29 '24 at 17:29
  • 4
    Let $B'=({1,2,3};+)$ where $x+y=\min(x,y)$. Then $B'$ is isomorphic to $B=({1,2,4};*)$, so $B'$ satisfies the same quasi-identities as $B$ which satisfies the same quasi-identities as $A$, and $B'$ is elementarily equivalent to $B$ which is not elementarily equivalent to $A$. – bof Mar 29 '24 at 17:34