The Boundary Between Universal Algebra and Model Theory

We know that model theory is at least a non-strict generalization of universal algebra. Indeed, we can consider model theory to be “universal algebra, but with relations instead of operations.” We can actually replicate the main definitions of model theory with an exact replacement of “operation” by “relation” in the universal algebra definitions, which yields more generality since every $n$ -ary operation is just a special $(n + 1)$ -ary relation. (Some formulations define signatures that contain operation and relation symbols, but since every operation is a relation, this does not carry any more generality. More precisely, every operation is a relation with extra conditions, so by adding suitable axioms we can remove all operation symbols without loss of generality.)

Recently, however, I was working with preorders and algebraic structures, and I was able to express the axioms of a preorder as an algebraic structure. My method inspires the question: are model theory and universal algebra actually equivalent? Can every model be written equivalently as a corresponding algebra?

—

First, a note on the removal of operation symbols from the signature in model theory: say we formulated model theory without the term “operation” in our vocabulary. We would then have to add non-equational axioms to express that a given relation is in fact an operation, e.g. if we have a binary relation $R$ that in fact represents a unary operation, then we would need the axiom “for all $a$ there exists $b$ such that $R(a,b)$ .” This is anyway par for the course in model theory, where the idea is to generalize beyond equational classes (at least in a non-strict way, based on appearances), so it can be customary for some of the axioms to not be equational.

Now, let’s turn to the question at hand. We replicate the method from the previously linked-to article. Given an $n$ -ary relation $R$ , we may define an equivalent $n$ -ary operation $O$ , adding the following axiom to the algebra:

For all $a_{1},\ldots,a_{n}$ , we have $O\left( a_{1},\ldots,a_{n} \right) = a_{1}$ or $O\left( a_{1},\ldots,a_{n} \right) = a_{n}$

The equivalency comes from defining $O\left( a_{1},\ldots,a_{n} \right) = a_{1}$ if $R\left( a_{1},\ldots,a_{n} \right)$ , and $O\left( a_{1},\ldots,a_{n} \right) = a_{n}$ otherwise.

Actually, I don’t think that works, in the case that $a_{1} = a_{n}$ .

Let’s come up with a basic specific counterexample. Say we have a ternary relation $R$ on $\mathbb{R}$ , where $R(a,b,c)$ if and only if $a + c = b$ . Thus, $R(1,2,1)$ , but $\neg R(1,3,1)$ . From the equivalency condition, we would define $O(1,3,1) = 1$ (using $a_{n}$ ) since $\neg R(1,3,1)$ , but then given $O$ we can’t reconstruct $R$ from it (we wouldn’t be able to tell whether $R(1,3,1)$ is true or not.) Thus, $O$ isn’t equivalent to $R$ .

Hmm … is there a way of defining a uniquely corresponding operation to a given relation $R$ ? That is the question that is important to determining whether universal algebra and model theory can be considered equivalent.

Well, actually, we can express this equivalency quite easily if we consider a different underlying set: just multiply it by $\left\{ 0,1 \right\}$ !

Let’s write this out for completeness. We start with formally writing out the definition of a model (which is helpful for my own learning.)

Definition (Model.) Let $\Sigma$ be a signature consisting of arbitrary-arity operation and relation symbols. (For now, we just deal with finite arities; I don’t think it changes the discussion.) Let $A$ be a set of (syntactically valid) logical statements involving primitive logical symbols as well as symbols from $\Sigma$ . A model of $\Sigma$ and $A$ is a set $M$ together with a mapping of each relation or operation symbol in $\Sigma$ to a relation or operation respectively on $M$ of the same arity, such that the statements in $A$ are true over $M$ , substituting symbols in statements in $A$ with the corresponding relation or operation on $M$ .

Definition (Corresponding Algebra.) Let $\Sigma,A,M$ be given satisfying the previous definition. The corresponding algebra consists of:

A signature $\Sigma^{'}$ that consists of all operation symbols in $\Sigma$ as well as, for each $n$ -ary relation symbol $r$ in $\Sigma$ , an $n$ -ary operation symbol $o(r)$
The set $A^{'} = A \times \left\{ 0,1 \right\}$

Actually, on second thought … this looks harder than it first appeared.

My preorder case might have worked because it was part of the preorder axioms that $a \leq a$ , thus we wouldn’t be able to construct a counterexample like we did for the ternary relation above. Indeed, say we had any binary relation $R$ . The idea was that we can define a corresponding binary operation $O$ , defined by $O(a,b) = a$ if $R(a,b)$ and $O(a,b) = b$ otherwise. Does this work? Well, given $R$ , $O$ is uniquely defined. However, given $O$ , say that $O(a,a) = a$ . We couldn’t tell then whether $R(a,a)$ or not. Thus, it is really the preorder axiom $a \leq a$ that allows equivalent reformulation of preorders as an algebraic structure with operations.

It remains to see whether a corresponding operation can be defined some other way, or whether the viability of such can be actually disproved in some way. I’d need to learn more model theory and universal algebra to see what people say about this already and whether I can find answers to this question based on what is already there in the literature.

EDIT (January 2023): Model theory encompasses not just first-order model theory, which is what I was focusing on, but also model theory based on any logic. Thus, more work would need to be done to equate general model theory to universal algebra, beyond just finding corresponding equivalent operations for relations. In fact, if this could be done, then all mathematical structures could be reduced to universal algebra. From what I’ve read, it seems that this is infeasible, as currently formulated here. However, some explorations I’m working on can nevertheless help apply universal algebra to a much wider range of mathematical structures.

Share and like (need WordPress account to like):

Leave a comment Cancel reply