Many branches of mathematics can be described as “the study of sets with some kind of structure.” For example, groups are sets with a binary operation which satisfies the group axioms. Partially-ordered sets, or posets, are sets with a binary relation satisfying the partial ordering axioms.

When studying such objects it is common to encounter a similar concept many times across different contexts. One example of such a concept is the homomorphism.

A homomorphism can be loosely defined as a “structure-preserving map.” A homomorphism between two groups \((G,\circ), (H,*)\) is a map \(f : G \rightarrow H\) satisfying

\[f(a \circ b) = f(x) * f(y)\]

for all \(x,y \in G\). On the other hand, a homomorphism between posets \((P,\leq), (Q,\leqq)\) is a map \(g : P \rightarrow Q\) satisfying

\[x \leq y \Rightarrow g(x) \leqq g(y)\]

for all \(x,y \in P\).

These two definitions seem to have the same pattern. They both state that something about the first structured set remains the same after carrying the elements over to the second set via the map. This similarity is surprisingly deep and is generalised in several branches of mathematics, such as universal algebra, category theory and model theory. In this article I’m to going to give a rough overview of the model theory approach to unifying maps between groups and posets.

Formulas

Model theory is a branch of logic, and as such is steeped in formality and technicality. I will be using the same terminology used by logicians, however I will not be defining anything in nearly the same level of detail (for which we should probably both be thankful).

Firstly we must introduce formulas. A formula is a kind of logical statement that makes a claim about certain classes of objects. Given a specific example of such an object, we can then decide whether the formula is true or false for it. The kind of statements you can make in a formula depends on what kind of object you are studying.

For example, when talking about groups, a valid formula is \(\exists x (x \circ x = x)\). In words, this says “there is an element \(x\) such that \(x^2 = x\).” We can then take a group and decide whether this forumla is true for it. (In this case, the formula is true for all groups, as the identity element \(e = e^2\).)

Formulas can have gaps: consider the formula \(xy = yx\). Given a group, we can’t decide whether this is true or false because we haven’t quantified \(x\) or \(y\) with \(\forall\) or \(\exists\). We need to substitute \(x,y\) for elements in the group – then we can decide if it is true.

The class of object under consideration is called the language. Formulas in one language are not always valid in another. Neither of the formulas above are valid in the language of posets, for example, as we cannot apply elements together (like \(xy\)). Specific examples of objects in a certain class are called structures in that language.

Maps

Next we need to define what it means for a map \(f : M \rightarrow N\) between two structures in a given language to respect a formula.

\(f\) respects a formula when, if the formula is true in \(M\) after substituting elements \(a_1, \dots, a_n \in M\) into any “gaps,” the same formula is true in \(N\) after substituting in \(f(a_1), \dots, f(a_n) \in N\).

And finally, we need the concept of atomic formulas, which are those which consist of only a single relation, and no qualifiers (\(\forall\) or \(\exists\)). For example, \(x = y\) and \(x \leq y\) are atomic. \(\forall x (y \leq x)\) and \((x = z) \vee (x \leq y)\) are not.

We can now define a homomorphism between two structures \(M,N\) in a given language as a map \(f : M \rightarrow N\) which respects all atomic formulas.

Suppose we are in the language of posets. How does this definition of homomorphism agree with the one seen earlier? Well, consider the formula

\[x \leq y.\]

If it is true for given \(x=a,\, y=b\) in a poset \(M\), then a homomorphism \(g\) respects it, so the formula is true for \(x=g(a),\, y=g(b)\) in \(N\). In other words, since \(g\) respects the formula \(x \leq y\), for any \(a,b \in M\) we have \(a \leq b\) implies \(g(a) \leq g(b)\) in \(N\). This is exactly what we had in our earlier definition. As this is the only non-trivial atomic formula (\(x=y\) is respected by any map) then we know that our general definition of homomorphism agrees entirely with the specific one for posets.

The case for groups is a little different. The key formula to consider is

\[xy = z.\]

Let \(a,b,c\) be elements of a group \(M\) and assume \(ab = c\). As \(xy = z\) is an atomic formula, it is respected by a homomorphism \(f\), so we know \(f(a) f(b) = f(c)\). Hence, because \(c = ab\), we have \(f(a) f(b) = f(ab)\), which exactly matches our earlier definition for a group homomorphism.

In this way, group and poset homomorphisms can be unified into one definition!

Embeddings

Let’s lastly consider doing the same for embeddings. These are a more specific type of homomorphism that also appear in the study of both groups and posets.

For a group homomorphism to be a group embedding, it must be injective.

For a poset homomorphism \(g\) to be a poset embedding, it must also satisfy the ‘reverse’ of the homomorphism criteria, i.e.

\[x \leq y \Leftrightarrow g(x) \leq g(y).\]

Can we unify these concepts too?

We define an embedding between two structures \(M,N\) in a given language as a map \(f : M \rightarrow N\) which respects all quantifier-free formulas. So, in addition to being a homomorphism, an embedding must also respect formulas containing logical connectives (and, or, not, …) and multiple relations, but need not respect formulas containing \(\forall\) or \(\exists\).

To get back the definition of a group embedding, the key is the formula

\[\neg (x=y),\]

or written another way, \(x \neq y\).

A map respecting this is trivially a group embedding, because that is the definition of injective: \(x \neq y \Rightarrow f(x) \neq f(y)\).

The case for posets is similar. Consider the formula

\[\neg (x \leq y),\]

alternatively written \(x>y\). Suppose \(g\) respects this formula, ie. for all \(a,b \in M\), \(a>b \Rightarrow g(a)>g(b)\). The contrapositive of this is the statement \(g(a) \leq g(b) \Rightarrow a \leq b\), giving us the reverse implication needed for \(g\) to match our definition for a poset embedding. Note that, by the same argument in the case of groups, poset homomorphisms are injective.

Hopefully this has given you a deeper understanding of what these kinds of maps really are!