5
$\begingroup$

Let $\mathfrak{A}=(A;...)$ be an algebra in the sense of universal algebra. Say that a congruence $\sim$ on $\mathfrak{A}$ is parafinite iff there is an equivalence relation $E\subseteq A^2$ with finitely many classes such that $\sim$ is the largest $\mathfrak{A}$-congruence contained in $E$. It's a fun exercise (see e.g. this answer by Keith Kearnes) to show that every equivalence relation does indeed contain a largest congruence, and even when $A/E$ is finite the corresponding $\sim$ can be quite large; for example, the group of usual equivalence classes of finite combinatorial games is the quotient of an infinitely generated free commutative monoid by the largest congruence contained in a four-element equivalence class.

I'm generally trying to get a better sense of parafiniteness. One issue is that negative results seem hard to come by; I don't immediately know of any interesting examples of non-parafinite congruences. (For a trivial example, the parafinite congruences on a pure set are exactly the equivalence relations with finitely many classes.) My real question is whether there is an instructive nontrivial example of a non-parafinite congruence which I can use to build intuition. That's probably a bit too open-ended, though, so let me home in on a specific way to guarantee nontriviality in the hopes that it's not impossible:

Is there a countably infinite ring $\mathfrak{R}$ with a non-parafinite congruence?

EDIT: As the answers below show, this was a silly question. A better version seems to be for semigroups, which I've asked about separately.

$\endgroup$
2
  • 1
    $\begingroup$ I can give non parafinite congruences on semigroups but it is a bit too much to write on my phone so I'll need to wait until I'm at a computer $\endgroup$ Dec 1, 2023 at 20:12
  • $\begingroup$ @BenjaminSteinberg Ooh, that'd be great! I've asked a separate question for that, see the edit. $\endgroup$ Dec 1, 2023 at 20:18

3 Answers 3

6
$\begingroup$

In a ring, congruences are given by ideals: The elements congruent to $0$ form an ideal and two elements are congruent if and only if their difference lies in the ideal.

So one can just take an equivalence relation with two equivalence classes, one the ideal and ones its complement. The smallest congruence refining this equivalence relation corresponds to the smallest ideal that the equivalence relation is invariant under translation by.

The same argument works in any variety that consists of a group with extra operations and equations - congruences are always the cosets of some normal subgroup and one can take the equivalence class consisting of that normal subgroup and its complement.

$\endgroup$
5
  • 1
    $\begingroup$ We gave the same answer at the same time :) $\endgroup$ Dec 1, 2023 at 20:10
  • $\begingroup$ And oh dear the question turned out to be trivial. Do either of you happen to have a good suggestion for what a decent nontriviality hypothesis might be here? @BenjaminSteinberg $\endgroup$ Dec 1, 2023 at 20:12
  • $\begingroup$ @NoahSchweber The only thing that's clear to me is that the more operations your algebra has, the more difficult it is to make a non-parafinite congruence. With no operations it is easy and with a group law it is impossible - probably there is some intermedite operaton where this becomes interesting. Maybe monoids are the most natural place, but my first thought was to look at Mal'cev varieties. I think there are no non-parafinites for quasigroups and Heyting algebras, both with a variant of this proof, but I don't see how to make it uniform $\endgroup$
    – Will Sawin
    Dec 1, 2023 at 20:16
  • $\begingroup$ (for groups you can use any fixed congruence class and its complement to make the equivalence relation, but for Heyting algebras you need to choose the one congruence class carefully in a way I don't see how to generalize). $\endgroup$
    – Will Sawin
    Dec 1, 2023 at 20:18
  • 1
    $\begingroup$ @NoahSchweber "I don't see how to make it uniform" Agliano and Ursini have a number of papers from the 80's / 90's dealing with universal algebraic generalizations of the notion of an ideal. The common feature here is that in both Heyting algebras and rings, congruences are uniquely determined by an ideal in this sense (= a filter in the case of HA's), so each congruence arises as the largest congruence below an equivalence relation with two equivalence classes. (In the context of algebraic logic the largest congruence compatible with a subset in this sense is called the Leibniz congruence.) $\endgroup$ Dec 2, 2023 at 15:43
5
$\begingroup$

On a ring or group all congruences are parafinite. Partition into the kernel and the complement of the kernel.

$\endgroup$
4
$\begingroup$

I do not have an instructive example of a non-parafinite congruence, so this is not an answer per se but rather an extended comment. Let me suggest two things. Firstly, it is useful to think of this in terms of so-called Leibniz congruences. Secondly, already in the case of semilattices the problem may be quite non-trivial.

Let us say that a congruence $\theta$ on an algebra $\mathbf{A}$ is a Leibniz congruence if there is a set $F \subseteq A$ such that $\theta$ is the largest congruence below the two-element equivalence relation $E_{F}$ naturally associated with $F$. This congruence is studied extensively in algebraic logic, where it is denoted by $\Omega^{\mathbf{A}} F$. As Benjamin Steinberg points out in the comments, in the context of semigroups these are known as syntactic congruences.

Observation. Each congruence $\theta$ is an intersection of Leibniz congruences: $\theta = \bigcap_{a \in A} \Omega^{\mathbf{A}} (a / \theta)$.

Observation. Parafinite congruences are precisely the congruences of the form $\Omega^{\mathbf{A}} F_{1} \cap \dots \cap \Omega^{\mathbf{A}} F_{n}$ for some finite family of sets $F_{1}, \dots, F_{n} \subseteq A$.

Proof. Each parafinite congruence $\theta_{E}$ has this form, just take the finitely many equivalence classes of $E$. Conversely, let $F_{1}, \dots, F_{n} \subseteq A$ be a finite family of sets. Let $E = E_{F_{1}} \cap \dots \cap E_{F_{n}}$ and let $G_{1}, \dots, G_{m}$ be the equivalence classes of $E$. We have $\theta_{E} = \Omega^{\mathbf{A}} G_{1} \cap \dots \cap \Omega^{\mathbf{A}} G_{m}$, so it suffices to show that $\Omega^{\mathbf{A}} G_{1} \cap \dots \cap \Omega^{\mathbf{A}} G_{m} = \Omega^{\mathbf{A}} F_{1} \cap \dots \cap \Omega^{\mathbf{A}} F_{n}$. The left-to-right inclusion holds because each $F_{i}$ is a union of some subfamily of the family $G_{j}$ and in general $\Omega^{\mathbf{A}} X_{1} \cap \dots \cap \Omega^{\mathbf{A}} X_{k} \subseteq \Omega^{\mathbf{A}} (X_{1} \cup \dots X_{k})$. The right-to-left inclusion holds because each $G_{j}$ is a Boolean combination of the sets $F_{i}$ and in addition to the previous observation concerning unions we also have the observation $\Omega^{\mathbf{A}} X = \Omega^{\mathbf{A}} (A - X)$ concerning complements and $\Omega^{\mathbf{A}} X_{1} \cap \dots \cap \Omega^{\mathbf{A}} X_{k} \subseteq \Omega^{\mathbf{A}} (X_{1} \cap \dots \cap X_{k})$ concerning intersections.

Corollary. Each dually compact congruence is parafinite.

An interesting open problem posed by Josep Maria Font and my colleague Tommaso Moraschini here is the following.

Open problem. Is each congruence on a semilattice a Leibniz congruence?

This seems like it should be quite a simple problem, but it has not turned out that way so far. Leibniz congruences being a special case of parafinite congruences, it makes sense to ask the following variant question, which I suspect may also turn out to be quite non-trivial.

Question. Is each congruence on a semilattice parafinite?

In case you make any progress in this direction, I would certainly be interested in hearing about it. If I had to make a wild guess, I would guess that such a congruence will exist but might be quite complicated to construct.

$\endgroup$
2
  • 1
    $\begingroup$ These Leibniz congruences are called syntactic congruences in semigroup theory and the theory of regular languages in computer science $\endgroup$ Dec 2, 2023 at 17:43
  • $\begingroup$ @KeithKearnes Oops, thanks for the correction! That of course makes the observation a bit less useful... $\endgroup$ Dec 3, 2023 at 0:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.