Constructing Compatible Operations

Recently in my ring theory class I heard about the theorem that if a ring satisfies $x^{n} = x$ for some constant $n$ , then it must be commutative. Now, note that this statement is made entirely in terms of multiplication. Thus, going off of the theme discussed in my post The Unreasonable Effectiveness of Definitions in Mathematics, we can wonder: is this in fact true for all monoids? If not, then what “data” is needed in the monoid to ensure that we can construct a compatible addition operation turning it into a ring? For such a monoid, we would be able to conclude commutativity.

So more precisely, the question is: for what monoids $M$ does there exist an operation $+$ on $M$ turning it into a ring?

Actually, we can generalize this much more, to arbitrary algebraic structures. Or we could even extend it to model theory later on, but for now let’s stick with algebras. Let’s devise a universal algebraic formulation of our goal. We can generally call this theory “constructed compatibility theory.”

Let $A$ and $A^{'}$ be algebraic structures, or collections of operation symbols and axioms involving those symbols, such that $A \subseteq A^{'}$ ( $A^{'}$ contains all the operation symbols of $A$ , and also contains all the axioms of $A$ .) For which models $M$ of $A$ can we define operations on $M$ for the remaining operation symbols in $A^{'}$ , such that $M$ is a model of $A^{'}$ ?

Actually, we can express this with standard language more generally and just as simply in model theory. Let $L_{1} \subseteq L_{2}$ be languages, and let $A_{1} \subseteq A_{2}$ be sets of axioms, with each $A_{i}$ in the language of $L_{i}$ . For which models $m$ of $A_{1}$ can we define operations and relations corresponding to the symbols in $L_{2} - L_{1}$ such that $m$ is a model of $A_{2}$ ?

Our motivating example then concerns constructed compatibility from monoids to rings. We can see that the idempotent monoid $\left\{ a,b,c \right\}$ with $a,b,c$ distinct, $a$ the identity, and $bc = b,cb = c$ isn’t commutative. Hence, not all monoids can be turned into rings, as I was initially wondering. But for which monoids is constructed compatibility to rings possible?

Let’s start with more general theory. Let $L$ be a language, $A$ be a set of axioms in the language of $L$ , and $m$ be a model of $A$ . Define $C(m)$ to be the class of all language-axiom pairs $\left( L^{'},A^{'} \right)$ with $L \subseteq L^{'}$ and $A \subseteq A^{'}$ such that $m$ can be “augmented” to a model of $A^{'}$ (we define “augmentation” to mean that operations/relations can be defined for the symbols in $L^{'} - L$ such that $m$ is a model of $A^{'}$ .) Actually, the unboundedness of this can probably cause set-theoretical issues; instead, let $U$ be a “universal” language (a language that we call “universal,”) and then define $S(m)$ to be the set of all language-axiom pairs $\left( L^{'},A^{'} \right)$ with $L \subseteq L^{'} \subseteq U$ and $A \subseteq A^{'}$ such that $m$ can be augmented to a model of $A^{'}$ . What can we say about $S(m)$ ?

Well, we have one property: for language-axiom pairs $a,b,c$ , if $a$ can “have constructed compatibility” to $b$ and $b$ can have constructed compatibility to $c$ , then $a$ can have constructed compatibility to $c$ . Written out for $S(m)$ , this means that: if $\left( L^{'},A^{'} \right) \in S(m)$ , and if there exists $\left( L^{''},A^{''} \right)$ such that for every model $m^{'}$ of $A^{'}$ we have $\left( L^{''},A^{''} \right) \in S\left( m^{'} \right)$ , then $\left( L^{''},A^{''} \right) \in S(m)$ .

Actually, a cleaner way to study this may be to stop focusing on individual models and focus instead on language-axiom pairs that define classes of models: for which language-axiom pairs do we have constructed compatibility of all their models to other language-axiom pairs? We can then recover individual models by just looking at which axioms guarantee constructed compatibility. For example, determining which class of monoids has constructed compatibility to rings is the same as determining for which individual monoids $m$ do we have constructed compatibility to a ring. This subclass of monoids would be defined by the same language as monoids but additional axioms, and we can then say that monoids satisfying those axioms are the ones that can have constructed compatibility to a ring.

Thus, say we have a language-axiom pair $(L,A)$ and a universal language $U \supseteq L$ , then we define $S(L,A)$ to be the set of all language-axiom pairs $\left( L^{'},A^{'} \right)$ such that $L^{'} \subseteq U$ and $(L,A)$ can have constructed compatibility to $\left( L^{'},A^{'} \right)$ .

We have some immediate properties:

If $\left( L^{'},A^{'} \right) \in S(L,A)$ and $\left( L^{''},A^{''} \right) \in S\left( L^{'},A^{'} \right)$ , then $\left( L^{''},A^{''} \right) \in S(L,A)$ . (This is the expression of the property previously mentioned in the individual-models framework above.)

Equivalently:

If $x \in S(L,A)$ , then $S(x) \subseteq S(L,A)$ .

Actually, let’s modify this setup again: really, the axioms themselves contain the data about which language they’re in. Thus, we can just consider sets of axioms in languages that are subsets of $U$ . We can denote the set of all such axiom sets by $A(U)$ . For any set of axioms $A$ , we can get its language via $L(A)$ . Also, this looks suspiciously close to an order relation: for any axiom sets $A,B$ , we can define $A \rightarrow B$ to mean that $A$ can have constructed compatibility to $B$ (which in particular entails $L(A) \subseteq L(B)$ .) Then, we have that $\rightarrow$ is transitive:

If $a \rightarrow b$ and $b \rightarrow c$ then $a \rightarrow c$ .

It is obviously reflexive: $a \rightarrow a$ . Is it anti-symmetric? In other words, do we have that $(a \rightarrow b) \land (b \rightarrow a)$ implies $a = b$ ? Well, every model of $a$ can have constructed compatibility to a model of $b$ . But we have that every such model of $b$ can have constructed compatibility to $a$ . So a model of $a$ can be turned into … a model of $a$ ?

Instead of syntactic form necessarily being equal, we would want to show that the axiom sets $a,b$ are logically equivalent. Thus, actually, we should be working on equivalence classes of $A(U)$ by logical equivalence (we can rename $A(U)$ to actually be the set of equivalence classes, to make notation in the future easier.) Is the $\rightarrow$ relation then well-defined on $A(U)$ ? Say $a$ is equivalent to $b$ (which we’ll denote by $a \equiv b$ ) and $c \equiv d$ , then do we have that $a \rightarrow c$ if and only if $b \rightarrow d$ ? Well, any model of $a$ must be a model of $b$ by equivalence, and this can be compatibly constructed to a model of $c$ , which in turn is a model of $d$ . Thus, $a \rightarrow c$ entails $b \rightarrow d$ . This shows (as expected) that things are indeed well-defined, as they should be since we just divided out by logical equivalence and the concepts we’re working with are semantic in nature.

So we have a $\rightarrow$ relation on $A(U)$ , which is reflexive and transitive. We want to show it’s anti-symmetric. Well, assume $a \rightarrow b$ and $b \rightarrow a$ ; we want to show that $a$ and $b$ are equivalent. Saying that $a$ and $b$ are equivalent (and by the way, we assume that for two things to be equivalent, they must be in the same language — if we have translations between operation symbols then we could theoretically define equivalence on different languages, but we don’t do that here) is the same as saying that $a$ and $b$ must have the same models. Well, any model of $a$ can be constructed to a model of $b$ , and similarly vice versa. Thus, these are equivalent. This yields that $\rightarrow$ is anti-symmetric too.

Consequently, $\rightarrow$ is an order relation, turning $A(U)$ into a poset. The set $S(a)$ defined above, of all axiom sets that $a$ can be constructed to, is just $\left\{ s:s \geq a \right\}$ , the set of all elements greater than or equal to $a$ . (Here, we interpret $\leq$ as $\rightarrow$ , not subset inclusion $\subseteq$ .) Let’s rename this to $G(a)$ , to emphasize the connection to “greater than.” We can similarly define $Le(a)$ to be $\left\{ s:s \leq a \right\}$ — this is the set of all axioms that can be constructed to $a$ . (Then, we can rename the function that gets the language of $a$ to $Lang(a)$ , and we can for greater clarity rename $G(a)$ to $Gr(a)$ .)

On second thought: while this is clean, is this the setup we want? If we want to investigate whether something like a monoid could be constructed to a ring, then since rings are trivially monoids this really entails in our framework whether or not monoids and rings are equivalent. But if we only operate on equivalence classes and not the axiom sets in them, then we can never get at this. In hindsight, this makes sense: we don’t just care about semantics, since in fact we’re trying to compare the semantics of syntactically different things. So we should focus on the axiom sets too. But if we view $\rightarrow$ as a relation on axiom sets, then we don’t have that $\rightarrow$ is an order relation anymore; we only have that $a\rightarrow b$ and $b\rightarrow a$ imply $a$ and $b$ must be logically equivalent.

We continue this discussion in the next post.

Share and like (need WordPress account to like):

Leave a comment Cancel reply