Examples of natural algebraic irreflexive relations

Question

To motivate the question, consider the theory of rings. Define $x \parallel y$ to mean $\exists w \exists z .((x - y) z = w (x - y) = 1)$, or in words, "$x - y$ is a unit". Then $\parallel$ is a binary relation with the following properties:

• Naturality. For all homomorphisms $\phi$, $x \parallel y$ implies $\phi (x) \parallel \phi (y)$.

• Algebraic irreflexivity. $=$ and $\parallel$ are algebraically inconsistent, in the sense that: $$\forall x \forall y \forall z . (x \parallel x \text{ implies } y = z)$$

A natural algebraic irreflexive relation (for a one-sorted theory) is a binary relation with the two formal properties above. The word "algebraic" has a double meaning here: attached to "natural", it signals that we are talking about preservation by algebra homomorphisms rather than, say, elementary embeddings; and attached to "irreflexive", it signals that we are weakening the definition in order to accommodate algebraic examples.

Actually, we can generalise to any category $\mathcal{A}$ equipped with a functor $U : \mathcal{A} \to \textbf{Set}$: we are then talking about a functor $[{\parallel}] : \mathcal{A} \to \textbf{Set}$ equipped with a natural monomorphism $[{\parallel}] \hookrightarrow U \times U$ such that $$([{=}] \cap [{\parallel}]) \times U \times U \subseteq [{=}] \times [{=}]$$ as subfunctors of $U \times U \times U \times U$, where $[{=}]$ is the diagonal of $U \times U$. Furthermore, let us say $\parallel$ is representable (resp. weakly representable, multirepresentable, etc.) if the functor $[{\parallel}]$ is representable (resp. weakly representable, multirepresentable, etc.). The above example in the theory of rings is representable. In the logical picture, this is closely related to definability of $\parallel$ by formulae in various complexity classes.

Question. Are there any other interesting examples of natural algebraic irreflexive relations? Particularly, are there examples in algebraic theories that are not ring-like? (Here, by "ring-like" I mean having two unital binary operations where the unit for one of the binary operations is absorbing for the other.)

---

Note that there is a class of trivial examples obtained by defining $\parallel$ to be the empty relation. Another class of uninteresting examples is obtained when $U : \mathcal{A} \to \textbf{Set}$ factors through the subcategory of injective maps – in that case, the denial inequality $\ne$ has the naturality property. One way of getting such a category is to take a relational theory that already has an irreflexive relation – such as the theory of strict partial orders – but this too is not very interesting (other than for demonstrating that symmetry is not automatic).

Here is a non-trivial example, but still in the ring-like realm. In the theory of rigs (i.e. rings without negatives, also called semirings), define $x \parallel y$ to mean: $$\exists s \exists t \exists u \exists v. (s x + t y = x u + y v = 1 \text{ and } x y = y x = 0)$$ Then $\parallel$ is a natural algebraic irreflexive relation and is weakly representable in the sense that there is a representable functor $C$ and a natural transformation $C \Rightarrow U \times U$ whose image is the subfunctor $[{\parallel}]$.

The failure of representability in the above is essentially because the witnesses $s, t, u, v$ are not necessarily unique. In the theory of (bounded but not necessarily distributive) lattices, we can analogously define $x \parallel y$ by $$x \lor y = \top \text{ and } x \land y = \bot$$ to obtain a representable natural algebraic irreflexive relation.

Answer 1

Are there any other interesting examples of natural algebraic irreflexive relations?

Let $\mathcal{V}$ be an equationally definable class of algebras in a language that has at least two distinct constants $0$ and $1$. Let $\mathbf{F}_{\mathcal{V}}(x)$ be the $\mathcal{V}$-free algebra over the set $\{x\}$. If the pair $(0,x)$ belongs to the congruence on $\mathbf{F}_{\mathcal{V}}(x)$ that is generated by $(0,1)$, then the binary relation $\{(0,1)\}$ is a natural algebraic irreflexive relation in $\mathcal{V}$.

The condition that the pair $(0,x)$ belongs to the congruence on $\mathbf{F}_{\mathcal{V}}(x)$ that is generated by $(0,1)$ is witnessed by a finite sequence of identities of $\mathcal{V}$ involving the constants $0$ and $1$ and binary $\mathcal{V}$-terms $p_i(x,y)$, namely

1. $x=p_1(1,x)$,
2. $p_1(0,x) = p_2(0,x)$,
3. $p_2(1,x) = p_3(1,x)$,
4. $p_3(0,x) = p_4(0,x)$,
5. $\ldots$
6. $p_{n}(0,x) = 0$.

If $\mathcal{V}$ satisfies identities like these and $\mathbf{A}\in \mathcal{V}$, then for every $a\in A$ we have a homomorphism $\varphi_a\colon \mathbf{F}_{\mathcal{V}}(x)\to \mathbf{A}\colon x\mapsto a$. Applying $\varphi_a$ to the equations above, which witness that $(0,x)$ belongs to the congruence on $\mathbf{F}_{\mathcal{V}}(x)$ that is generated by $(0,1)$, we get that $(0,a)$ belongs to the congruence on $\mathbf{A}$ that is generated by $(0,1)$. Since $a\in A$ was arbitrary, we get that the pair $(0,1)$ of $\mathbf{A}$ generates the universal congruence on $\mathbf{A}$ for any $\mathbf{A}\in \mathcal{V}$. This is enough to show $\{(0,1)\}$ is a natural algebraic irreflexive relation.

The simplest special case of this is the one where there is only one binary term in the sequence. Let's write it as $x\ast y := p_1(x,y)$. In this case, the identities say that $x = 1\ast x$ and $0\ast x = 0$. That is, $1$ is a left unit and $0$ is a left zero with respect to $\ast$. This already includes the case of rings - take $\ast$ to be ring multiplication - and bounded (semi)lattices - take $\ast$ to be $\wedge$. It also includes other examples, like semigroups with $0$ and $1$.

---

Edit. Oct 7. Responding to a question in the comments:

I don't quite understand how you obtain a chain of identities of the form claimed.

I am using Maltsev's Congruence Generation Lemma, which appears as Theorem 4.19 of

Algebras, Lattices, Varieties, volume I
R. McKenzie, G. McNulty, W. Taylor
Wadsworth and Brooks/Cole, 1987.

In general, if $\mathbf{A}$ is an algebra generated by a set $G$ and $(a,b), (c,d)\in A^2$, then $(c,d)$ belongs to the congruence generated by $(a,b)$ if and only if there is a 'Maltsev chain' of 'polynomial images' of $\{a,b\}$ connecting $c$ to $d$, as in

1. $c=p_1(a,\mathbf{g})$,
2. $p_1(b,\mathbf{g}) = p_2(b,\mathbf{g})$,
3. $p_2(a,\mathbf{g}) = p_3(a,\mathbf{g})$,
4. $p_3(b,\mathbf{g}) = p_4(b,\mathbf{g})$,
5. $\ldots$
6. $p_{n}(b,\mathbf{g}) = d$.

Here, each $p_i(x,\mathbf{y})$ is a term in the language and $\mathbf{g}$ is a tuple of parameters, which may be assumed to be distinct and to come from the generating set $G$. In the answer above I took $(a,b)=(1,0)$, $(c,d)=(x,0)$ and $G = \{x\}$.