Smallest possible cardinality of finite set with two non-elementarily equivalent magmas which satisfy the same $\forall$-theory?

Question

This is a follow-up to my previous question, here: Smallest possible cardinality of finite set with two non-elementarily equivalent magmas which satisfy the same quasi-equations?. My question now is, does there exist a finite set $S$ and two binary operations $+$ and $*$ on $S$ such that $+$ and $*$ satisfy the same $\forall$-sentences, but not the same full first-order theory? And if so, what is the smallest possible cardinality of $S$? And if not, is there at least an infinite set and two binary operations on it with this property?

Answer 1

I assume that $\forall$-sentence means a universal sentence.

Think of the operation $+$ as fixed and say $S$ has $n$ elements. Then the sentence "whenever $x_1, \dotsc, x_n$ are distinct elements, then there is some permutation of these elements that gives the same multiplication table as $(S, +)$" is a (pretty long) $\forall$-sentence$^\dagger$. So for finite $S$, the two operations automatically give isomorphic magmas.

However, there are examples of infinite magmas satisfying the same $\forall$-sentences but not having the same first-order theory. An important fact for finding an example is the one mentioned in the post I linked earler: if $M$ is a substructure of $N$, then every universal sentence that holds in $N$ also holds in $M$. So if we can find non-elementarily equivalent magmas each of which is isomorphic to a substructure of the other, we're done. This is a bit reminiscent of the negation of the Schroeder-Bernstein theorem, and in fact I will give an example which I know as an example demonstrating that the Schroeder-Bernstein theorem fails in the category of (abelian) groups.

Consider the direct sums $M = \Bbb Z/2\Bbb Z \oplus \Bbb Z/4\Bbb Z \oplus \Bbb Z/4\Bbb Z \oplus \Bbb Z/4\Bbb Z \oplus \dotsb$ and $N = \Bbb Z/4\Bbb Z \oplus \Bbb Z/4\Bbb Z \oplus \Bbb Z/4\Bbb Z \oplus \Bbb Z/4\Bbb Z \oplus \dotsb$. These are countable abelian groups, and clearly each is isomorphic to a subgroup of the other. However they are distinguished by the first-order sentence "there is an element of order $2$ which is not of the form $x + x$". Since both are countable, you can take them to have the same underlying set.

---

$^\dagger$: Choose an enumeration $y_1, \dotsc, y_n$ of $S$, and let $a(i, j)$ be the unique number such that $y_i + y_j = y_{a(i, j)}$. Then the sentence I'm talking about is \begin{equation*} \forall x_1 \dotsm \forall x_n \left( \left( \bigwedge_{i \ne j} x_i \ne x_j \right) \rightarrow \left( \bigvee_{\sigma \in S_n} \bigwedge_{i, j} x_{\sigma(i)} \ast x_{\sigma(j)} = x_{\sigma(a(i, j))} \right) \right) \end{equation*}