The Strength of the Grätzer-Schmidt theorem

Katie Brodhead  Mushfeq Khan  Bjørn Kjos-Hanssen  William A. Lampe
Paul Kim Long V. Nguyen  Richard A. Shore

April 5, 2016

Abstract The Grätzer-Schmidt theorem of lattice theory states that each algebraic lattice is isomorphic to

the congruence lattice of an algebra. We study the reverse mathematics of this theorem. We also show that

1. the set of indices of computable lattices that are complete is Π_{1}^{1}-complete;

2. the set of indices of computable lattices that are algebraic is Π_{1}^{1}-complete;

3. the set of compact elements of a computable lattice is Π_{1}^{1} and can be Π_{1}^{1}-complete; and

4. the set of compact elements of a distributive computable lattice is Π_{3}^{0}, and there is an algebraic distributive computable lattice such that the set of its compact elements is Π_{3}^{0}-complete.

Keywords: lattice theory, computability theory.

Contents

1 Introduction  2
2 Computability-theoretic analysis of lattice theoretic concepts  2
2.1 Index set of complete lattices is Π_{1}^{1}-complete . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Compact elements of a lattice can be Π_{1}^{1}-complete . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Index set of algebraic lattices is Π_{1}^{1}-complete . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Lattices of equivalence relations  5
3.1 Congruence lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Principal congruences can be Turing complete . . . . . . . . . . . . . . . . . . . . . . . . . 6
4 Reverse mathematics  7
5 Compact elements in algebraic lattices of restricted kinds  7
5.1 Distributive lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5.2 Modular lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1 Introduction

The Grätzer-Schmidt theorem [?MR0151406], also known as the congruence lattice representation theorem, states that each algebraic lattice is isomorphic to the congruence lattice of an algebra. It established a strong link between lattice theory and universal algebra. In this article we analyze the theorem from the point of view of reverse mathematics and calibrate the strength of the special case of the theorem for distributive lattices. The question of the strength of the general case of the theorem remains open.

We use notation associated with partial computable functions, φ_{e}, φ_{e,s}, φ_{e,s}^{σ}, φ_{e}^{f} as in Odifreddi [?MR982269]. A Π_{1}^{1} subset of ω may be written in the form (see, for example, Sacks [?MR1080970], page 5)

C_{e} = {n ∈ ω | ∀f ∈ ω^{ω} φ_{e}^{f}(n) ↓}.

A subset A ⊆ ω is Π_{1}^{1}-hard if each Π_{1}^{1} set is m-reducible to A; that is, for each e, there is a computable function f such that for all n, n ∈ C_{e} iff f(n) ∈ A. A is Π_{1}^{1}-complete if it is both Π_{1}^{1} and Π_{1}^{1}-hard. It is well known that such sets exist. Fix for the rest of the paper a number e_{0} so that C_{e_{0}} is Π_{1}^{1}-complete. With each n, the set C_{e_{0}} associates a tree T′_{n} defined by

T′_{n} = {σ ∈ ω^{<ω} | φ_{e_{0},|σ|}^{σ}(n) ↑}.

Note that T′_{n} has no infinite path iff n ∈ C_{e}.

A computable lattice (L, ⪯) has underlying set L = ω and a computable lattice ordering ⪯ that is formally a subset of ω^{2}.

We will use the symbol ⪯ for lattice orderings, and reserve the symbol ≤ for the natural ordering of the ordinals and in particular of ω. Meets and joins corresponding to the order ⪯ are denoted by ∧ and ∨. Below we will seek to build computable lattices from the trees T′_{n}. Since for many n, T′_{n} will be finite, and a computable lattice must be infinite according to our definition, we will work with the following modification of T′_{n}:

T_{n} = T′_{n} ∪ {⟨i⟩ : i ∈ ω} ∪ {∅}

where ∅ denotes the empty string and ⟨i⟩ is the string of length 1 whose only entry is i. This ensures that T_{n} has the same infinite paths as T′_{n}, and each T_{n} is infinite. Moreover the sequence {T_{n}}_{n∈ω} is still uniformly computable.

2 Computability-theoretic analysis of lattice theoretic concepts

2.1 Index set of complete lattices is Π_{1}^{1}-complete

Definition 2.1. A lattice (L, ⪯) is complete if for each subset S ⊆ L, both sup S and inf S exist.

Example 2.2. In set-theoretic notation, (ω + 1, ≤) is complete. Its sublattice (ω, ≤) is not, since ω = sup ω ∉ ω.

Lemma 2.3. The set of indices of computable lattices that are complete is Π_{1}^{1}.

Proof. The statement that sup S exists is equivalent to a first order statement in the language of arithmetic with set variable S:

∃a[∀b(b ∈ S → b ⪯ a) & ∀c((∀b(b ∈ S → b ⪯ c) → a ⪯ c)].

The statement that inf S exists is similar, in fact dual. Thus the statement that L is complete consists of a universal set quantifier over S, followed by an arithmetical matrix.

Proposition 2.4. The set of indices of computable lattices that are complete is Π_{1}^{1}-hard.

Proof. Let L_{n} consist of two disjoint copies of T_{n}, called T_{n} and T_{n}^{∗}. For each σ ∈ T_{n}, its copy in T_{n}^{∗} is called σ^{∗}. Order L_{n} so that T_{n} has the prefix ordering

σ ⪯ σ^{⌢}τ,

T_{n}^{∗} has the reverse prefix ordering, and σ ≺ σ^{∗} for each σ ∈ T_{n}. We take the transitive closure of these axioms to obtain the order of L_{n}; see Figure 1.

Next, we verify that L_{n} is a lattice. For any σ, τ ∈ T_{n} we must show the existence of (1) σ ∨ τ, (2) σ ∧ τ, (3) σ ∨ τ^{∗}, and (4) σ ∧ τ^{∗}; the existence of σ^{∗} ∨ τ^{∗} and σ^{∗} ∧ τ^{∗} then follows by duality.

We claim that for any strings α, σ ∈ T_{n}, we have α^{∗} ⪰ σ iff α is comparable with σ; see Figure 1. In one direction, if α ⪰ σ then α^{∗} ⪰ α ⪰ σ, and if σ ⪰ α then α^{∗} ⪰ σ^{∗} ⪰ σ. In the other direction, if α^{∗} ⪰ σ then by the definition of ⪯ as a transitive closure there must exist ρ with α^{∗} ⪰ ρ^{∗} ⪰ ρ ⪰ σ. Then α ⪯ ρ and σ ⪯ ρ, which implies that α and ρ are comparable.

Using the claim we get that (1) σ ∨ τ is (σ ∧ τ)^{∗}, where (2) σ ∧ τ is simply the maximal common prefix of σ and τ; (3) σ ∨ τ^{∗} is σ^{∗} ∨ τ^{∗} which is (σ ∧ τ)^{∗}; and (4) σ ∧ τ^{∗} is σ ∧ τ.

It remains to show that (L_{n}, ⪯) is complete iff T_{n} has no infinite path. So suppose T_{n} has an infinite path S. Then sup S does not exist, because S has no greatest element, S^{∗} has no least element, each element of S^{∗} is an upper bound of S, and there is no element above all of S and below all of S^{∗}.

Conversely, suppose T_{n} has no infinite path and let S ⊆ L_{n}. If S is finite then sup S exists. If S is infinite then since T_{n} has no infinite path, there is no infinite linearly ordered subset of L_{n}, and so S contains two incomparable elements σ and τ. Because T_{n} is a tree, σ ∨ τ is in T_{n}^{∗}. Now the set of all elements of L_{n} that are above σ ∨ τ is finite and linearly ordered, and contains all upper bounds of S. Thus S has a supremum. Since L_{n} is self-dual, i.e. (L_{n}, ⪯) is isomorphic to (L_{n}, ⪰) via σ ↦ σ^{∗}, infs also always exist. So L_{n} is complete.

Figure 1: The lattice L_{n} from Proposition 2.4.

2.2 Compact elements of a lattice can be Π_{1}^{1}-complete

Definition 2.5. An element a ∈ L is compact if for each subset S ⊆ L, if a ⪯ sup S then there is a finite subset S′ ⊆ S such that a ⪯ sup S′. Thus, if a ⪯ sup S but for each finite subset S′ ⊆ S, a ⪯̸ sup S′, then S is a witness for the non-compactness of a.

Lemma 2.6. In each computable lattice L, the set of compact elements of L is Π_{1}^{1}.

Proof. Similarly to the situation in Lemma 2.3, the statement that a is compact consist of a universal set quantifier over S followed by an arithmetical matrix.

Example 2.7. Let L[a] = ω + 1 ∪ {a} be ordered by 0 ≺ a ≺ ω, and let the element a be incomparable with the positive numbers. Then a is not compact, because a ⪯ sup ω but a ⪯̸ sup S′ for any finite S′ ⊆ ω.

Figure 2: The lattice L[a] from Example 2.7.

Definition 2.8. A lattice (L, ⪯) is compactly generated if every element is the supremum of a set of compact elements. A lattice is algebraic if it is complete and compactly generated.

Proposition 2.9. There is a computable complete lattice L such that the set of compact elements of L is Π_{1}^{1}-hard. Moreover, L is not algebraic.

Proof. Let L consist of disjoint copies of the trees T_{n}, n ∈ ω, each having the prefix ordering; least and greatest elements 0 and 1; and elements a_{n}, n ∈ ω, such that σ ≺ a_{n} for each σ ∈ T_{n}, and a_{n} is incomparable with any element not in T_{n} ∪ {0, 1} (see Figure 3).

Suppose T_{n} has an infinite path S. Then a_{n} = sup S but a_{n} ⪯̸ sup S′ for any finite S′ ⊆ S, since sup S′ is rather an element of S. Thus a_{n} is not compact.

Conversely, suppose T_{n} has no infinite path, and a_{n} ⪯ sup S for some set S ⊆ L. If S contains elements from T_{m} ∪ {a_{m}} for at least two distinct values of m, say m_{1} ≠ m_{2}, then sup S = 1 = σ_{1} ∨ σ_{2} for some σ_{i} ∈ S ∩ (T_{m_{i}} ∪ {a_{m_{i}}}), i = 1, 2. So a_{n} ⪯ sup S′ for some S′ ⊆ S of size two. If S contains 1, there is nothing to prove. The remaining case is where S is contained in T_{m} ∪ {a_{m}, 0} for some m. Since a_{n} ⪯ sup S, it must be that m = n. If S is finite or contains a_{n}, there is nothing to prove. So suppose S is infinite. Since T_{n} has no infinite path, there must be two incomparable elements of T_{n} in S. Their join is then a_{n}, since T_{n} is a tree, and so a_{n} ⪯ sup S′ for some S′ ⊆ S of size two.

Thus we have shown that a_{n} is compact if and only if T_{n} has no infinite path. There is a computable presentation of L where a_{n} is a computable function of n, for instance we could let a_{n} = 2n. Thus letting f(n) = 2n, we have that T_{n} has no infinite path iff f(n) is compact, i.e. {a ∈ L : a is compact} is Π_{1}^{1}-hard.

It remains to show that L is not algebraic. Fix n such that T_{n} has an infinite path P, and also some nontrivial finite paths that do not extend to infinite paths. Let σ be on such a finite path. Then each element of P is compact. However, σ is below the supremum of P, but not below any join of finitely many elements of P, so σ is not compact. Moreover, σ is join irreducible, being located on the tree T_{n}. Thus σ is not a join of compact elements below it, and so L is not compactly generated.

From the proof of Proposition 2.9 we obtain the following corollary.

Corollary 2.10 (RCA_{0}). The following principle is equivalent to Π_{1}^{1}-CA_{0}: “For each countable lattice L, there is a set consisting of exactly the compact elements of L.”

Figure 3: The lattice L from Proposition 2.9.

Question 2.11. Is there a computable algebraic lattice such that the set of its compact elements is Π_{1}^{1}-complete?

2.3 Index set of algebraic lattices is Π_{1}^{1}-complete

Lemma 2.12. The set of indices of computable lattices that are algebraic is Π_{1}^{1}.

Proof. Let L be a computable lattice and C the set of its compact elements. L is algebraic if it is complete (this property is Π_{1}^{1} by Lemma 2.3) and each element is the supremum of its compact predecessors, i.e., any element that is above all the compact elements below a is above a:

∀a(∀b(∀c(c ∈ C & c ⪯ a → c ⪯ b) → a ⪯ b))

Equivalently,

∀a(∀b(∃c(c ∈ C & c ⪯ a & c ⪯̸ b) or a ⪯ b))

This is equivalent to a Π_{1}^{1} statement since, by the Axiom of Choice, any statement of the form ∃c ∀S A(c, S) is equivalent to ∀(S_{c})_{c∈ω} ∃c A(c, S_{c}).

Example 2.13. The lattice (ω + 1, ≤) is compactly generated, since the only noncompact element ω satisfies ω = sup ω. The lattice L[a] from Example 2.7 and Figure 2 is not compactly generated, as the noncompact element a is not the supremum of {0}.

Proposition 2.14. The set of indices of computable lattices that are algebraic is Π_{1}^{1}-hard.

Proof. Let the lattice T_{n}[a] consist of T_{n} with the prefix ordering, and additional elements 0 ≺ a ≺ 1 such that a is incomparable with each σ ∈ T_{n}, and 0 and 1 are the least and greatest elements of the lattice. Note that T_{n}[a] is always complete, since any infinite set has supremum equal to 1. We claim that T_{n}[a] is algebraic iff T_{n} has no infinite path.

Suppose T_{n} has an infinite path S. Then a ⪯ sup S, but a ⪯̸ sup S′ for any finite S′ ⊆ S. Thus a is not compact, and so a is not the sup of its compact predecessors (0 being its only compact predecessor), which means that T_{n}[a] is not an algebraic lattice.

Conversely, suppose T_{n}[a] is not algebraic. Then some element of T_{n}[a] is not the join of its compact predecessors. In particular, some element of T_{n}[a] is not compact. So there exists a set S ⊆ T_{n}[a] such that for all finite subsets S′ ⊆ S, sup S′ < sup S. In particular S is infinite. Since each element except 1 has only finitely many predecessors, we have sup S = 1. Notice that T_{n}[a]\{1} is actually a tree, so if S contains two incomparable elements then their join is already 1, contradicting the defining property of S. Thus S is linearly ordered, and infinite, which implies that T_{n} has an infinite path.

Figure 4: The lattice T_{n}[a] from Proposition 2.14.

3 Lattices of equivalence relations

Let Eq(A) denote the set of all equivalence relations on A. Ordered by inclusion, Eq(A) is a complete lattice. In a sublattice L ⊆ Eq(A), we write sup_{L} for the supremum in L when it exists, and sup for the supremum in Eq(A), and note that sup ≤ sup_{L}.

A complete sublattice of Eq(A) is a sublattice L of Eq(A) such that sup_{L} = sup and inf_{L} = inf. A sublattice of Eq(A) that is a complete lattice is not necessarily a complete sublattice in this sense. The following lemma is well known. A good reference for lattice theory is the monograph of Grätzer

[?MR2451139].

Lemma 3.1. Suppose A is a set and (L, ⊆) is a complete sublattice of Eq(A). Then an equivalence relation E in L is a compact member of L if and only if E is finitely generated in L.

Proof. One direction only uses that L is a sublattice of Eq(A) and L is complete as a lattice. Suppose E is not finitely generated in L. Let C_{(a,b)} denote the infimum of all equivalence relations in L that contain (a, b). Then E ⊆ sup_{L}{C_{(a,b)} : aEb}, but E is not below any finite join of the relations C_{(a,b)}. So E is not compact.

Suppose E is finitely generated in L. So there exists an n and pairs (a_{1}, b_{1}),…, (a_{n}, b_{n}) such that a_{i}Eb_{i} for all 1 ≤ i ≤ n, and for all equivalence relations F in L, if a_{i}F b_{i} for all 1 ≤ i ≤ n then E ⊆ F. Suppose E ⊆ sup_{L}{E_{i} : 1 ≤ i < ∞} for some E_{1}, E_{2}, … ∈ L. Since L is a complete sublattice of Eq(A), sup_{L} = sup, so E ⊆ sup{E_{i} : 1 ≤ i < ∞}. Note that sup{E_{i} : 1 ≤ i < ∞} is the equivalence relation generated by the relations E_{i} under transitive closure. So there is some j = j_{n} < ∞ such that {(a_{i}, b_{i}) : 1 ≤ i ≤ n} ⊆ ⋃_{i=1}^{j} E_{i} and hence E ⊆ ⋃_{i=1}^{j} E_{i}. Thus E is compact.

A computable complete sublattice of Eq(ω) is a uniformly computable collection E = {E_{i}}_{i∈ω} of distinct equivalence relations on ω such that (E, ⊆) is a complete sublattice of Eq(ω). We say that the lattice L = (ω, ⪯) is computably isomorphic to (E, ⊆) if there is a computable function φ : ω → ω such that for all i, j, we have i ⪯ j ↔ E_{φ(i)} ⊆ E_{φ(j)}.

Lemma 3.2. The indices of compact congruences in a computable complete sublattice of Eq(ω) form a Σ_{2}^{0} set.

Proof. Suppose the complete sublattice is E = {E_{i}}_{i∈ω}. By Lemma 3.1, E_{k} is compact if and only if it is finitely generated, i.e.,

∃n ∃a_{1}, …, a_{n} ∃b_{1}, …, b_{n} [⋀_{i=1}^{n} a_{i}E_{k}b_{i} & ∀j (⋀_{i=1}^{n} a_{i}E_{j}b_{i} → E_{k} ⊆ E_{j})] .

Here E_{k} ⊆ E_{j} is Π_{1}^{0}: ∀x∀y (xE_{k}y → xE_{j}y), so the formula is Σ_{2}^{0}.

3.1 Congruence lattices

An algebra 𝔄 consists of a set A and functions f_{i} : A^{n_{i}} → A. Here i is taken from an index set I which may be finite or infinite, and n_{i} is the arity of f_{i}. Thus, an algebra is a purely functional model-theoretic structure. A congruence relation of 𝔄 is an equivalence relation on A such that for each unary f_{i} and all x, y ∈ A, if xEy then f_{i}(x)Ef_{i}(y), and the natural similar property holds for f_{i} of arity greater than one.

The congruence relations of 𝔄 form a lattice under the inclusion (refinement) ordering. This lattice Con(𝔄) is called the congruence lattice of 𝔄.

The following lemma is well-known and straight-forward.

Lemma 3.3. If 𝔄 is an algebra on A, then Con(𝔄) is a complete sublattice of Eq(A).

Theorem 3.4 (Grätzer-Schmidt [?MR0151406]). Each algebraic lattice is isomorphic to the congruence lattice of an algebra.

Remark 3.5. Let A be a set, and let L be a complete sublattice of Eq(A). Then L is algebraic [?MR2451139], and so by Theorem 3.4 L is isomorphic to Con(𝔄) for some algebra 𝔄 on some set, but it is not in general possible to find 𝔄 such that L is equal to Con(𝔄). In fact, it suffices to take any finite lattice table that is not Malcev homogeneous in the sense of Definition 3.1 of [?Kjos-Hanssen:03].

3.2 Principal congruences can be Turing complete

Let 𝔄 be an algebra. The least congruence relation ∼ on 𝔄 with a ∼ b is denoted by C_{𝔄}(a, b) and is called the principal congruence relation generated by the pair (a, b).

Definition 3.6. We say that the algebra 𝔄 = {f_{n} | n ∈ ω} is computable if the set

{⟨⟨x_{1}, …, x_{k}⟩, y, n⟩ | f_{n}(x_{1}, …, x_{k}) = y}

is computable.

Theorem 3.7. There is a computable algebra 𝔄 and a, b ∈ A such that the Turing degree of C_{𝔄}(a, b) is 0′.

Proof. Let 0′ = {g(n) | n ∈ ω} where g is computable, and let the operations of 𝔄 be unary functions {f_{s}}_{s∈ω}. Let f_{s}(a_{0}) = a_{g(s)} and f_{s}(b_{0}) = b_{g(s)}, where A = {a_{n} | n ∈ ω} ∪ {b_{n} | n ∈ ω}, a union of two disjoint infinite sets; let f_{s} be the identity on A\{a_{0}, b_{0}}. Then for k > 0, (a_{k}, b_{k}) ∈ C_{𝔄}(a_{0}, b_{0}) iff k ∈ 0′. So we can let (a, b) = (a_{0}, b_{0}).

4 Reverse mathematics

We consider the following standard axiom systems of reverse mathematics [?Simpson]:

• RCA_{0} (recursive comprehension axiom);

• ACA_{0} (arithmetical comprehension axiom);

• Π_{1}^{1}-CA_{0} (Π_{1}^{1}-comprehension axiom);

• WKL_{0} (weak König’s lemma);

• RT_{2}^{2} (Ramsey’s theorem for pairs).

Definition 4.1. The axiom system GS (Grätzer-Schmidt) consists of RCA_{0} plus the following axiom: For each algebraic lattice L there exists

1. an algebra 𝔄,

2. a set {E_{i}}_{i∈ω} of congruences of 𝔄 such that each congruence of 𝔄 is one of the E_{i}, and

3. an isomorphism φ between L and {E_{i}}_{i∈ω}.

Remark 4.2. For this theorem to fall within the scope of reverse mathematics, for each countable lattice L, there must exist a countable algebra 𝔄 satisfying the properties above. That this is the case can be seen from Pudlák’s proof [?MR0429699] of the Grätzer-Schmidt theorem, which we discuss in more detail below.

Definition 4.3. Let GSD be the Grätzer-Schmidt theorem for distributive lattices: every distributive algebraic lattice is isomorphic to the congruence lattice of an algebra.

5 Compact elements in algebraic lattices of restricted kinds

5.1 Distributive lattices

As a contrast to the case of arbitrary lattices (Proposition 2.9), in the distributive case the complexity of the set of compact elements reduces from Π_{1}^{1} to Π_{3}^{0} (Theorem 5.3). This is also sharp (Theorem 5.5), which will enable us to show that WKL_{0} + RT_{2}^{2} does not imply GSD (Corollary 5.12). We first need a proposition.

Proposition 5.1 (ACA_{0}). If L is a countable algebraic lattice and a ∈ L is not compact then there is a witness C ⊆ {x | x < a}. Moreover, we can assume that C = {c_{i} | i ∈ ω} where the c_{i} are strictly increasing.

Proof. Let C = {d_{i}} witness the fact that a is not compact. Thus a ≤ sup C but for each finite C′ ⊂ C, a ≰ sup C′. By closing under finite joins of initial segments and thinning out the sequence, we can assume that the d_{i} are strictly increasing.

As L is algebraic, a is the join of the compact elements ≤ a. Since moreover a is not itself compact, a is the join of the compact elements c < a.

Since a ≤ sup_{i} d_{i}, each compact c ≤ a is below some d_{0} ∨ ⋯ ∨ d_{i} = d_{i}, and hence c ≤ d_{i} ∧ a < a. Thus a = ⋁_{i}(d_{i} ∧ a). Finally, let {c_{i}}_{i∈ω} be a strictly increasing subsequence of the sequence

{d_{i} ∧ a}_{i∈ω}.

Definition 5.2. We say that b is a coatom relative to a, written b ⊏ a, if

b < a and ¬∃y(b < y < a).

Theorem 5.3 (ACA_{0}). In an algebraic countable distributive lattice L, the set {a ∈ L | a is compact} has the Π_{3}^{0}(L) form

{a ∈ L | (∀x < a)(∃b)(x ≤ b ⊏ a)}.

Proof. Fix a ∈ L. Let B = {b_{j}} = {b | b ⊏ a}. We must show that a is compact if and only if

(∀x < a)(∃b)(x ≤ b ⊏ a).

Only if direction: Assume that there is an z < a with no b ∈ B above it. Let

D = {x < a | x is not below any b ∈ B} = {d_{i}}.

Note that D is nonempty by assumption and has no maximal elements by definition. We build an increasing sequence c_{j} ∈ D such that for each i, d_{i} ≠ ∨c_{j}. Again by our assumptions this guarantees that ∨c_{j} = a as required to show that it is not compact. Let c_{0} = z and suppose we have defined c_{k}. We want to choose c_{k+1} > c_{k} in D so as to guarantee that d_{k} will not be the join of all the c_{j}. If d_{k} ≱ c_{k} then d_{k} cannot be the join of the c_{j} and we can take any c ∈ D with c > c_{k} as c_{k+1}. If d_{k} ≥ c_{k} we can take any c ∈ D with c > d_{k} as once again we have guaranteed that d_{k} ≠ ∨c_{j}. If direction: We suppose that every x < a is below some b ∈ B and, for the sake of a contradiction, that a is not compact. Then by Proposition 5.1, some C = {c_{i}} (a strictly increasing sequence of elements below a) witnesses that a is not compact. If ∃j∀i(c_{i} ≤ b_{j}) then ∨c_{i} ≤ b_{j} < a for any such j contradicting our choice of C. Thus ∀j∃i(c_{i} ≰ b_{j}). If B is finite, there is an i such that ∀j(c_{i} ≰ b_{j}) as the c_{i} are increasing. This would contradict our case assumption.

Finally, we suppose that B is infinite. We build a nondecreasing sequence d_{n} of elements strictly below a with d_{0} = c_{0} which has no join in L below a for a contradiction to the completeness of L. Each d_{k+1} will be of the form b_{j_{1}} ∧ b_{j_{2}} ∧ … ∧ b_{j_{k}} ∧ c_{l_{k}} and its choice will guarantee that x_{k} is not the join of all the d_{n} where L = {x_{k}}.

Suppose we have d_{k} and want to define d_{k+1}. First ask if (∃b ∈ B)(b ≥ d_{k} & b ≱ x_{k}). If so, we let b_{j_{k+1}} be such a b and l_{k+1} = l_{k}. In this case d_{k+1} = d_{k} and, by the intended form of our d_{n}, we have guaranteed that b ≥ d_{n} for every n and so that b ≥ ∨d_{n}. As b ≱ x_{k}, x_{k} ≠ ∨d_{n} as required. Otherwise, for every b ∈ B with b ≥ c_{l_{k}}, b ≥ x_{k}. Choose one such b not equal to any b_{j_{m}}, m ≤ k, and a p > l_{k} such that b ≱ c_{p}.

Note that {j | b_{j} ≥ c_{i}} is nonempty for every i by our case assumption. Thus ∀i∃^{∞}j(b_{j} ≥ c_{i}) since otherwise (as the c_{i} are increasing) there would be a finite set F such that ∀i∀j ∈ F (b_{j} ≥ c_{i}) and so ∨c_{i} ≤ ∧{b_{j} | j ∈ F } < a contradicting our choice of C. Also note that ∀n∃i∀j ≥ i(c_{j} ≰ b_{n}) as otherwise ∀j(c_{j} ≤ b_{n}) and so ∨c_{i} ≤ b_{n} again contradicting our choice of C.

Now let j_{k+1} = j_{k} and c_{l_{k+1}} = c_{p}. As c_{p} ≥ c_{l_{k}}, d_{k+1} ≥ d_{k}. As b ≥ c_{l_{k}}, b ≥ x_{k}. On the other hand, b is not any of the b_{j_{m}} for m ≤ k + 1 and so is not above any of them. Moreover, it is not above c_{p} = c_{l_{k+1}}. Thus it is not above

d_{k+1} = b_{j_{1}} ∧ … ∧ b_{j_{k+1}} ∧ c_{l_{k+1}}

by distributivity, as we now show:

As b ∈ B, b ∨ b_{j_{m}} = a = c_{l_{k+1}} ∨ b for m ≤ k + 1. But if

b ≥ b_{j_{1}} ∧ … ∧ b_{j_{k+1}} ∧ c_{l_{k+1}}

then

b = (( ⋀_{i=1}^{k+1} b_{j_{i}}) ∧ c_{l_{k+1}}) ∨ b = (b ∨ b_{j_{1}}) ∧ … ∧ (b ∨ b_{j_{k+1}}) ∧ (b ∨ c_{l_{k+1}})

but as b ∈ B each of these terms (and so their join) is equal to a for the desired contradiction. Thus x ≠ ∨d_{n} as required.

Proposition 5.4 (Folklore). For every Π_{3}^{0} predicate P, there is a computable function h(x, y) such that for all x and y, W_{h(x,y)} is an initial segment of ω, and

P (x) ⇒ (∀y)(W_{h(x,y)} is finite)

and

¬P (x) ⇒ (∃!y)(W_{h(x,y)} = ω).

Proof. It is well-known (see, for example, Soare [?SoareBook], Theorem 4.3.4) that there is a function g(x, y) such that

P (x) ⇔ (∀y)(W_{g(x,y)} is finite).

We describe a uniform sequence {C_{i}}_{i∈ω} of c.e. sets. At each stage s of the enumeration of this sequence, for each y ≤ s, there is a designated “destination” i_{y,s} ∈ ω for W_{g(x,y)}. By a “new destination”, we mean the least n ∈ ω that has not yet been used as a destination.

At stage s, choose a new destination i_{s,s}. If it exists, let z < s be the least such that a new element has just entered W_{g(x,z)}. Then

• enumerate into C_{i_{z,s}} the least element not already in it, and

• choose new destinations for W_{g(x,y)} for all y such that z < y ≤ s.

This describes the enumeration of {C_{i}}_{i∈ω}.

We verify that this sequence has the desired properties. If there is a y such that W_{g(x,y)} is infinite, then let it be the least such. After some stage s, new elements will cease to appear in W_{g(x,y′)} for y′ < y, and i_{y,s} will never again be redefined. Thus C_{i_{y,s}} = ω. If j ≠ i_{y,s} is ever a destination for some W_{g(x,z)} for some z > y, it will cease to be so when a new element is enumerated into W_{g(x,y)}, hence C_{j} will be finite. On the other hand, if W_{g(x,y)} is finite for all y, C_{j} is finite for all j, since each such j is ever a destination for W_{g(x,y)} for exactly one value of y.

Finally, let W_{h(x,y)} = C_{y}.

Theorem 5.5. There is a computable distributive algebraic lattice for which the set of compact elements is complete Π_{3}^{0}.

Proof. Given a complete Π_{3}^{0} set P, let h be as in the proposition above. Our lattice shall contain elements a_{i} for each i < ω, and elements a_{i,j,k} for each triple (i, j, k) such that k ∈ W_{h(i,j)}. The plan is that a_{i} will be compact iff P (i) holds. Let

α_{i} = {a_{i,j,k} | k ∈ W_{h(i,j)} and j ∈ ω},

and Λ = {0, 1} ∪ ⋃_{i}{a_{i}} ∪ ⋃_{i} α_{i}.

The ordering among the elements of Λ is specified by

a_{i,j,k} ≤ a_{î,ĵ,k̂}  ⟺  i = î & j = ĵ & k ≤ k̂;
a_{i} ≤ aî ⟺  i = î;
a_{i,j,k} ≤ aî ⟺  i = î;

and no aî is below any a_{i,j,k}. The top element 1 is above all others in Λ, while 0 is below.

This determines joins betweens pairs of elements of Λ:

a_{i} ∨ aî = 1 for i ≠ î
aî ∨ a_{i,j,k} = \begin{cases}1 & for i ≠ î and \\ aî & if i = î; \end{cases}

a_{i,j,k} ∨ a_{î,ĵ,k̂} = \begin{cases}1 & if i ≠ î; \\ a_{i} & if i = î and j ≠ ĵ; and \\ a_{i,j,k} & if i = î, j = ĵ and k̂ ≤ k. \end{cases}

These relations extend to arbitrary joins as follows: Let Λ_{0} ⊆ Λ. If Λ_{0} contains a pair that join up to 1 then ⋁ Λ_{0} = 1. Otherwise, all elements of Λ_{0} have the same i. If there are two with different j (or a_{i} itself occurs) then ⋁ Λ_{0} = a_{i}. Otherwise, they are all of the form a_{i,j,k} for a fixed i and j. If sup{k | a_{i,j,k} ∈ Λ_{0}} = ω, then ⋁ Λ_{0} is again a_{i}. If it is k̂ ∈ ω, then ⋁ Λ_{0} = a_{i,j,k̂}. Thus, Λ is closed under arbitrary joins.

To each element x in Λ, we now associate a subset Γ(x) of ω. Let B and C be infinite uniformly computable sets such that B∪C = ω, and let {B_{i}}_{i∈ω} and {C_{i}}_{i∈ω} be partitions of B and C, respectively, into infinite computable pairwise disjoint sets. Let f_{i} : ω^{2} → C_{i} be a uniform family of computable bijections. Now let

Γ(0) = ∅
Γ(1) = ω
Γ(a_{i}) = A_{i} = ω \ B_{i}
Γ(a_{i,j,k}) = A_{i,j,k} = ω \ (B_{i} ∪ {f_{i}(j, k̂) | k̂ > k}).

The following claims are easily verified:

Claim 5.6. For all x, y ∈ Λ, x ≤ y ⇔ Γ(x) ⊆ Γ(y).

Claim 5.7. For any Λ_{0} ⊆ Λ, Γ(⋁ Λ_{0}) = ⋃_{x∈Λ_{0}} Γ(x).

Let L be the collection of sets obtained by closing the image of Γ under finite intersections. The distributivity of union and intersection ensures that L is also closed under finite unions. Thus L is a distributive lattice, and its order extends the ordering on Λ (which we identify with its image under Γ). The domain of our computable presentation of L will be ω: we can assume that only finitely many elements are enumerated into the uniformly c.e. sequence W_{h(i,j)} at every stage, and for each such element and the finitely many new intersections it gives rise to, we allocate as yet unused natural numbers while ensuring that every natural number will be eventually allocated. We must now verify that

1. the relations and operations on L are computable, and

2. L is algebraic.

To this end, we derive a normal form for the finite meets making up the lattice. Suppose x ∈ L is neither 0 nor 1. It is an intersection of finitely many elements of the form A_{i} and the form A_{i,j,k}. For each i, if any A_{i,j,k} appears, we may eliminate all terms of the form A_{i} and A_{i,j,k̂} except for the smallest k̂ so occurring. We now have a normal form of x given by

x = ⋀_{i∈F} A_{i} ∧ ⋀_{i∈G} ⋀_{j∈G_{i}} A_{i,j,k_{i,j}}

with F, G, G_{i} finite nonempty sets and F and G disjoint. We say that x is represented by ⟨F, G, ⟨G_{i} | i ∈ G⟩⟩. It can be verified that the normal form representation of an element is unique.

Claim 5.8. L is computable as a lattice.

Proof. Suppose we have

x = ⋀_{i∈F} A_{i} ∧ ⋀_{i∈G} ⋀_{j∈G_{i}} A_{i,j,k_{i,j}} and x̂ = ⋀_{i∈F̂} A_{i} ∧ ⋀_{i∈Ĝ} ⋀_{j∈Ĝ_{i}} A_{i,j,k̂_{i,j}}.

We claim that

x ≤ x̂ ⟺ F̂ \ F ⊆ G & Ĝ ⊆ G & (∀i ∈ Ĝ)(Ĝ_{i} ⊆ G_{i}) & (∀i ∈ Ĝ)(∀j ∈ Ĝ_{i})(k̂_{i,j} ≥ k_{i,j}). (∗)

The conditions on the right hand side guarantee that every term in the meet forming x̂ is greater than or equal to one of the terms whose meet is x, yielding the right-to-left implication. And if any of the conditions fails, then by the definitions of the sets A_{i} and A_{i,j,k}, there is some element n ∈ x such that n ∉ x̂, so x ≰ x̂. Next, note that

x < x̂ ⟺ x ≤ x̂ & x ≠ x̂ ⟺
(∗) and F̂ ≠ F or (F̂ = F and G \ Ĝ ≠ ∅) or (∃i ∈ Ĝ)(∃j ∈ Ĝ_{i})(k̂_{i,j} > k_{i,j}).

Thus the relations ≤ and < on L are computable from the normal forms of the elements of L. Meets can also be computed from the normal forms. Let

G′ = G ∪ Ĝ
F′ = (F ∪ F̂) \ G′

G′_{i} = \begin{cases}G_{i} & for i ∈ G \ Ĝ \\ Ĝ_{i} & for i ∈ Ĝ \ G \\ G_{i} ∪ Ĝ_{i} & for i ∈ G ∩ Ĝ \end{cases}

k′_{i,j} = \begin{cases}k_{i,j} & if k̂_{i,j} is undefined \\ k̂_{i,j} & if k_{i,j} is undefined \\ min(k_{i,j}, k̂_{i,j}) & if both are defined. \end{cases}

Then

x ∧ x̂ = ⋀_{i∈F′} A_{i} ∧ ⋀_{i∈G′} ⋀_{j∈G′_{i}} A_{i,j,k′_{i,j}}.

Joins can be computed by converting to a meet of joins of elements of Λ using distributivity, then applying the rules for joins of elements of Λ, and finally reducing the meet to normal form.

Claim 5.9. L is complete.

Proof. First, we consider an arbitrary (infinite) meet ⋀_{n} x_{n}. We may assume that x_{n+1} ≤ x_{n} and if the sequence is not eventually constant (and so its meet a finite one) that x_{n+1} < x_{n}. We claim any such meet is 0. Suppose x_{n} is represented by ⟨F^{n}, G^{n}, ⟨G_{i}^{n} | i ∈ G^{n}⟩⟩. If the F^{n} are not eventually constant then there is an infinite set of i that eventually appear in them and so the meet is below A_{i} for infinitely many i. The only such element is 0. Next, say the F^{n} are eventually equal to F. If after they have settled down the G^{n} are not eventually constant, and say equal to G, then there are infinitely many i eventually appearing in the G^{n} and so the meet is below some A_{i,j,k} for infinitely many i and so also below infinitely many A_{i}. Therefore, it is once again 0. So suppose F^{n} and G^{n} have stabilized by n_{0}. The only way x_{n+1} < x_{n} for n > n_{0} is for some k_{i,j}^{n+1} to be smaller than k_{i,j}^{n} for some i ∈ G. But this can happen only finitely often and so the meet eventually stabilizes, which is a contradiction.

Next, consider an infinite join ⋁_{n} x_{n}. Let

y = ⋀{z | ∀n(z ≥ x_{n})}

which exists by the argument above. Clearly, y is the least element of L above every x_{n}.

Claim 5.10. L is algebraic.

Proof. We determine the compact elements of L. It is easy to see that 1 and 0 are among them. If P (i) fails let j_{i} denote the unique witness such that W_{h(i,j_{i})} is infinite. Suppose x ≠ 0, 1 has the normal form

⋀_{i∈F} A_{i} ∧ ⋀_{i∈G} ⋀_{j∈G_{i}} A_{i,j,k_{i,j}}.

We claim that x is compact if and only if

(∀i ∈ F)(P (i)) and (∀i ∈ G)(P (i) or j_{i} ∈ G_{i}).  (†)

First, suppose that x is compact. If there is an i′ ∈ F such that P (i′) fails, then let y_{k} be obtained by replacing the term A_{i′} by A_{i′,j_{i′} ,k} in x, i.e.,

y_{k} = A_{i′,j_{i′} ,k} ∧ ⋀_{i∈F,i≠i′} A_{i} ∧ ⋀_{i∈G} ⋀_{j∈G_{i}} A_{i,j,k_{i,j}}.

It is clear that each y_{k} < x and so ⋁_{k} y_{k} ≤ x. On the other hand, if z is such that y_{k} ≤ z < x, then, by our characterizations of the relations ≤ and <, it must be some y_{k′} for k′ ≥ k. It follows that ⋁_{k} y_{k} = x, but no finite join suffices.

Next, suppose that P (i′) fails for some i′ ∈ G and j_{i′} ∉ G_{i′}. Let y_{k} = x ∧ A_{i′,j_{i′} ,k}. An argument similar to the one above shows that ⋁_{k} y_{k} = x while no finite join is x.

Next, we argue that if the condition (†) holds then x is compact. Consider any ⋁_{n} x_{n} ≥ x. We may assume that if the join is not achieved at any finite stage then the x_{n} are strictly increasing. Suppose

x_{n} = ⋀_{i∈F^{n}} A_{i} ∧ ⋀_{i∈G^{n}} ⋀_{j∈G_{i}^{n}} A_{i,j,k_{i,j}^{n}}.

It is clear from the characterization of < that the F^{n}, G^{n} and G_{i}^{n} must eventually stabilize, say to F̄, Ḡ and Ḡ_{i} for i ∈ Ḡ. After stabilization, for i ∈ Ḡ such that P (i) holds, or such that P (i) fails but j ∈ Ḡ_{i} is not equal to j_{i}, the k_{i,j}^{n} are also eventually constant (since in either case, there are only finitely many of them). However, there must be some i ∈ Ḡ such that P (i) fails and j_{i} ∈ Ḡ_{i}, and for at least one such i, the k_{i,j_{i}}^{n} must be unbounded. Let

H = {i | (∀m)(∃n > m)(k_{i,j_{i}}^{n} > m)} and K = H ∩ {i | Ḡ_{i} = {j_{i}}}.

It is not difficult to see that ⋁_{n} x_{n} is represented by ⟨F̄ ∪ K, Ḡ \ K, ⟨Ĝ_{i} | i ∈ Ḡ \ K⟩⟩, where Ĝ_{i} =

Ḡ_{i} \ {j_{i}} if i ∈ H and Ĝ_{i} = Ḡ_{i} if i ∉ H. Now,

• F̄ \ F ⊆ G, since ⋁_{n} x_{n} ≥ x, and so (F̄ ∪ K) \ F ⊆ G

\xymatrix{ & Π_{1}^{1} − CA_{0} \ar[d] \ar[dr] \\  & ACA_{0} \ar[d] \ar[dr] \ar[dl] & GS \ar[d] \\ RT_{2}^{2} \ar[dr] & W KL_{0} \ar[d] & GSD \ar[dl] \\  & RCA_{0}}

Figure 5: Reverse mathematics of the Grätzer-Schmidt theorem over RCA_{0}.

• Ḡ ⊆ G, since otherwise, there is an i ∈ K such that i ∉ G, which means that i ∈ F, contradicting (†)

• (∀i ∈ Ḡ \ K)(Ḡ_{i} ⊆ G_{i}), since if P (i) holds, then i ∉ H, and so Ĝ_{i} = Ḡ_{i} ⊆ G_{i}, and if j_{i} ∈ G_{i}, then Ḡ_{i} ⊆ Ĝ_{i} ∪ {j_{i}} ⊆ G_{i}

• (∀i ∈ K)(Ḡ_{i} ⊆ G_{i}), since for all i ∈ K, P (i) fails and therefore, by (†), j_{i} ∈ G_{i}, and Ḡ_{i} = {j_{i}}.

Therefore, for sufficiently large n, x_{n} ≥ x.

The above analysis shows that if x is not compact it is the join of the compact elements below it: Define y_{n} by replacing in the meet producing x each A_{i} (i ∈ F) such that P (i) fails by A_{i,j_{i},n} and, for each i ∈ G for which P (i) fails and j_{i} ∉ G_{i}, adding A_{i,j_{i},n} to the meet. Our characterization of the compact elements shows that each y_{n} is compact. Our analysis of the order shows that ⋁ y_{n} = x.

This completes the proof of the theorem.

Corollary 5.11 (RCA_{0}). The following principle is equivalent to ACA_{0}: “For each countable distributive lattice L, there is a set consisting exactly of the compact elements of L.”

Proof sketch. To prove ACA_{0} from this principle, use the following construction. Let L_{n} have a top element t_{n} preceded by a finite sequence if n ∈ 0′ and an ω-sequence if n ∉ 0′. Let L be the sum of the linear orders, so that t_{n} is compact iff n ∈ 0′. Then L is a linear order, and hence in particular a distributive lattice.

Corollary 5.12. WKL_{0} + RT_{2}^{2} |̸= GSD.

Proof. As the set of compact elements of a computable congruence lattice is Σ_{2}^{0}, the construction for Theorem 5.5 guarantees that any standard model of GSD includes a set C such that the complete Π_{3}^{0} set is Σ_{2}^{0} in C and so C′′ ≥_{T} 0′′′. There are, however, standard models of WKL_{0} + RT_{2}^{2} in which all sets are low_{2} [?CJS], so C′′ ≡_{T} 0′′.

Remark 5.13. Let L be a countable algebraic lattice and let K be the set of its compact elements, which is an upper semilattice. Pudlák’s proof [?MR0429699] of the Grätzer-Schmidt Theorem proceeds by constructing a “K-valued graph” (A, r, h), where A is a set of vertices, r a set of (undirected) edges, and h : r → K a surjective “coloring” of each edge by a compact element. A mapping f : A → A is said to be stable if it respects the coloring in the following sense: for every edge {a, b} ∈ r, either f(a) = f(b) or h({a, b}) = h({f(a), f(b)}). Then letting F be the family of all stable mappings on A, the unary algebra (A, F) satisfies the requirements of the theorem, i.e., Con(A, F) is isomorphic to L.

An inspection of this construction reveals that the K-valued graph (A, r, h) is computable in K. Further, it suffices to choose a countable subfamily {f_{n} | n ∈ ω} ⊆ F of stable mappings that are uniformly computable in K, so that Con(A, {f_{n} | n ∈ ω}) ≅ L.

For a, b ∈ A, let a ∼_{x} b if there is a path in (A, r, h) connecting a and b all of whose edges are colored with compact elements that are less than or equal to x. It can then be shown that the map φ : x ↦ ∼_{x} is an isomorphism between L and Con(A, {f_{n} | n ∈ ω}). Moreover, φ is Σ_{1}^{0}-definable in K. In particular, there is a presentation of Con(A, {f_{n} | n ∈ ω}) that is arithmetical in K.

Proposition 5.14. We have the following provability results:

1. Π_{1}^{1}-CA_{0} ⊢ GS.

2. ACA_{0} ⊢ GSD.

Proof. For (1), note that Π_{1}^{1}-CA_{0} guarantees the existence of the set K of compact elements in a given lattice L, and by the remark above, the congruence lattice and the isomorphism can be chosen to be arithmetical in K.

For (2), Theorem 5.3 shows that the set of compact elements of a computable algebraic distributive lattice is Π_{3}^{0}, and thus the congruence lattice and the isomorphism are, in this case, arithmetical.

5.2 Modular lattices

While we do not know whether the set of compact elements in a modular lattice must be Π_{3}^{0}, we do know that the characterization of compact elements in Theorem 5.3 does not extend from distributive to modular lattices.

The following fact is well-known:

Lemma 5.15. In an algebraic lattice, each element is the supremum of the compact elements below it.

Remark 5.16. An example to keep in mind: consider (ω + 1) × 2. Let a = (ω, 1). Then a is not compact.

Theorem 5.17. Let L be a modular algebraic lattice and a be in L. If a is compact, then for each interval (b, a), there is a c ∈ (b, a) such that the interval (c, a) is empty (we say that a covers c). However, the converse does not hold.

Proof. If a does not cover any element in (b, a), one can construct an infinite chain whose supremum is a but for any finite subchain, the supremum is strictly below a, contradicting compactness.

For a counterexample to the converse, consider the countably-infinite dimensional vector space V over ℤ/2ℤ consisting of all finite subsets of ℕ, viewed as finite characteristic functions, with mod-two addition or equivalently:

A + B = (A \ B) ∪ (B \ A).

Let V_{n} be the subspace of V consisting of subsets of {1, …, n}. Then the supremum of {V_{n} : n ∈ ω} is V but clearly the supremum of any finite subset of the V_{n} is contained in some V_{k}. On the other hand each proper subspace of V is contained in a codimension 1 subspace.

Acknowledgments

This paper is an extended and corrected version of the conference paper [?MR2545880]. The authors thank Bakh Khoussainov for useful suggestions. This work was partially supported by a grant from the Simons Foundation (#315188 to Bjørn Kjos-Hanssen). Paul K. L. V. Nguyen was partially supported by the National Science Foundation under Grant No. 0841223. Richard A. Shore was partially supported by NSF grants DMS-0852811 and DMS-1161175. Bjørn Kjos-Hanssen was partially supported by NSF grant DMS-0901020.