OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

§1 (setting): finite algebras, Con(A) and the property R(L): Congruences are the equivalence relations compatible with every operation, and R(L)R(L) says L≅Con⁡(𝑨)L \cong \operatorname{Con}(\mathbf{A}) for some finite algebra 𝑨\mathbf{A}

Finite algebras, their congruences and representable partial orders.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Every finite algebra has a finite congruence lattice. The question behind this item runs the other way: which finite lattices arise, up to isomorphism, as the congruence lattice of a finite algebra? Whether every finite lattice does is the finite lattice representation problem. This item defines the algebras and congruences of that question, and the property R(L)R(L) that a partially ordered set LL has when the answer for LL is yes.

The Definition

For partially ordered sets PP and QQ, P≅QP \cong Q means that there is an order isomorphism of PP onto QQ, a bijection that preserves and reflects the order; between lattices, an order isomorphism is a lattice isomorphism.

Definition 1. An algebra 𝑨\mathbf{A} on a set AA is AA together with a finite sequence of operations on AA, 𝑨=(A;f1,…,fm),fi:Aki→A(1≤i≤m),\mathbf{A} = (A;\, f_1, \dots, f_m), \qquad f_i \colon A^{k_i} \to A \quad (1 \le i \le m),(1)✦ where m≥0m \ge 0 and each arity ki≥0k_i \ge 0 is a natural number; an operation of arity 00 is a constant.

An equivalence relation θ\theta on AA is compatible with 𝑨\mathbf{A} when, for every ii and all a1,…,aki,b1,…,bki∈Aa_1, \dots, a_{k_i}, b_1, \dots, b_{k_i} \in A, (a1,b1),…,(aki,bki)∈θ⇒(fi(a1,…,aki),fi(b1,…,bki))∈θ.(a_1, b_1), \dots, (a_{k_i}, b_{k_i}) \in \theta \quad\Longrightarrow\quad \bigl(f_i(a_1, \dots, a_{k_i}),\, f_i(b_1, \dots, b_{k_i})\bigr) \in \theta.(2)✦

A congruence of 𝑨\mathbf{A} is an equivalence relation on AA that is compatible with 𝑨\mathbf{A}, and Con⁡(𝑨)\operatorname{Con}(\mathbf{A}) is the set of all congruences of 𝑨\mathbf{A}, partially ordered by inclusion: $$\operatorname{Con}(\mathbf{A}) = \{\theta \subseteq A \times A : \theta \text{ is an equivalence relation satisfying } \eqref{eq:claim2}\}, \qquad \theta \le \psi \iff \theta \subseteq \psi.$$(3)✦

For n≥1n \ge 1, a finite algebra on nn points is an algebra on the set {0,1,…,n−1}\{0, 1, \dots, n-1\}. A partially ordered set LL has the property R(L)R(L) when there is a finite algebra 𝑨\mathbf{A} on nn points, for some n≥1n \ge 1, with L≅Con⁡(𝑨).L \cong \operatorname{Con}(\mathbf{A}).(4)✦

In the paper, the definition reads: a finite algebra is a nonempty finite set AA with a finite list of total operations of finite nonnegative arity, the list possibly empty and the nullary operations being constants; Con⁡(𝑨)\operatorname{Con}(\mathbf{A}) is the lattice of all congruences of 𝑨\mathbf{A}; and for a nonempty finite lattice LL, R(L)R(L) holds if and only if LL is isomorphic to the entire congruence lattice Con⁡(𝑨)\operatorname{Con}(\mathbf{A}) of some finite algebra 𝑨\mathbf{A}.

What Is Checked

The definition is stated over algebras on a set with finitely many operations of finite arity, as in (1), over their congruences, the equivalence relations satisfying (2), and, for R(L)R(L), over order isomorphisms of LL onto the whole of Con⁡(𝑨)\operatorname{Con}(\mathbf{A}) for an algebra 𝑨\mathbf{A} on {0,1,…,n−1}\{0, 1, \dots, n-1\} with n≥1n \ge 1.