Is there an equational theory which has infinite models but no non-trivial finite models?

Question

Does there exist an algebraic signature $\Omega$ and an equational theory $T$ of $\Omega$ such that $T$ has infinite models, but no non-trivial finite models? Trivial means one-element models.

Answer 1

Yes, there does. There is a very elementary construction of such a theory consisting of three equations in a language consisting of four at-most-ternary functions. Moreover, there is even a single equation in a single binary function symbol which has nontrivial models but no finite nontrivial models.

---

First, a "naive" construction. Consider the set $E$ of the following three equations (with $0$ a nullary function, $p,s$ unary functions, and $t$ a ternary function):

$$p(s(x))=x$$

$$t(0,y,z)=y$$

$$t(s(x), y,z)=z$$

The first equation implies that $s$ is injective, while the second and third together imply that $0\not\in ran(s)$ ... if the domain has more than one element. Putting these facts together, we get that the only finite model of $E$ is the trivial algebra. On the other hand, $E$ clearly has infinite models (take e.g. $\mathbb{N}$ with $s$ being the usual successor operation, $0$ being $0$, $t$'s behavior being determined by the axioms, $p(a+1)=a$, and $p(0)=0$).

Note that Alex Kruckman's answer is based on similar considerations, but much more elegant.

---

A natural follow-up question is whether we can find a single equation which does the job. This was done quite impressively by Austin in 1964, the equation being the following: $$[y^3x][(y^2y^3)z]=x.$$

Here "$a^n$" is shorthand for the left-associating $n$th power of $a$, e.g. $a^3=(aa)a$), and as usual we abbreviate "$a*b$" by "$ab$" - in particular, note that this is a single equation in a single binary function symbol, which is as simple as one could hope (you can't really do much with a bunch of unary function symbols).

As a point of historical interest, the OP was first (so far as I know) answered by Stein in 1963. Stein used an infinite set of equations but only one (binary) function symbol, as opposed to my finitely many equations in four function symbols (and overall "high" arity).

Note that the above-linked papers use the term "groupoid" in its older meaning (= "magma" in modern jargon).

EDIT: I just learned of a much simpler one-equation example, due to Dudek in 1988 (A note on models of identities): $$(\star):\quad(x'y)z=y.$$ Here our language consists of a binary function (suppressed as usual) and a unary function $'$. (Dudek's example appears to build off of an example by Taylor from the latter's Some interesting identities, but I currently can't get access to that paper so I can't say more.)

The analysis of Dudek's example is completely elementary and much more transparent than Austin's example (although Austin's is still superior in terms of the complexity of the language used):

• To show that his equation has infinite models, take our carrier set to be $\mathbb{N}$, interpret $'$ as the constant function $a\mapsto 1$, and interpret $*$ as the binary function $$(a,b)\mapsto\begin{cases} a-1 & \mbox{ if }x>1,\\ b+1 & \mbox{ otherwise}.\\ \end{cases}$$

• To show that $(\star)$ has no nontrivial finite models, Dudek considers the function $$T_a: x\mapsto a'x$$ for $a\in A$ with $A$ a nontrivial model of the equation. The remaining argument is sufficiently cute that I'm hiding it so those who want to work it out themselves can do so without spoilers.

Each $T_a$ is injective, so if $A$ were finite they must all be surjective as well. But letting $T_a(b)=a'$ we would then get via $(*)$ that $$\forall x(T_a(x)=a'x=(a'b)x=b),$$ contradicting injectivity of $T_a$.

Answer 2

Here's another particularly elegant example. Consider the signature with one binary function $p$ and two unary functions $\pi_1$ and $\pi_2$. A Jónsson-Tarski algebra is an algebra satisfying the following equational axioms:

1. $\pi_1(p(x,y)) = x$.
2. $\pi_2(p(x,y)) = y$.
3. $p(\pi_1(z),\pi_2(z)) = z$.

An algebra $(X,p,\pi_1,\pi_2)$ is a Jónsson-Tarski algebra if and only if $p\colon X^2\to X$ is a bijection with inverse $(\pi_1,\pi_2)$. So $X$ is the domain of a Jónsson-Tarski algebra if and only if $|X| = |X|^2$. The only finite numbers satisfying $n = n^2$ are $n = 0$ and $n = 1$. On the other hand, for every infinite cardinal $\kappa$, $\kappa = \kappa^2$. So there are infinite Jónsson-Tarski algebras, but the only finite Jónsson-Tarski algebras are the empty algebra and the trivial (one-element) algebra. If you want to rule out the empty algebra, just add a constant symbol to the signature (which is not mentioned by the axioms).