SOME PROPERTIES OF COMPLETE CONGRUENCE LATTICES

ROBERTO GIACOBAZZI AND FRANCESCO RANZATO

Abstract. For a complete lattice C, we consider the problem of establishing when the complete lattice of complete congruence relations on C is a complete sublattice of the complete lattices of join- or meet-complete congruence relations on C. We first argue that this problem is not trivial, and then we show that it admits an affirmative answer whenever C is continuous for the join case and, dually, co-continuous for the meet case. As a consequence, we prove that if C is continuous then each principal filter generated by a continuous complete congruence on C is pseudocomplemented.

1. Introduction

Starting from the ’80s, there has been a growing interest in studying lattices of complete congruence relations on complete lattices. This has been mainly justified by the positive solution to a problem raised by Rudolf Wille in 1983 [18] on the possibility of representing every complete lattice as the lattice of complete congruences of a suitable complete lattice, e.g. see the representation theorem for finite lattices by S.-K. Teo [16] and the well-known representation theorems by G. Grätzer and H. Lakser [9] and G. Grätzer and E.T. Schmidt [10] for arbitrary complete lattices.

Given a complete lattice C, let us denote by Con(C) the complete lattice of complete congruences on C, and by JCon(C) and MCon(C) the complete lattices of, respectively, join- and meet-complete congruences on C. Recall that an equivalence relation Θ ⊆ C × C is a join-complete congruence if (∀i. x_{i}Θy_{i}) ⇒ (∨_{i}x_{i} Θ ∨_{i} y_{i}). Meet-complete congruences are dually defined. In this paper, we focus on the relationship between Con(C) and, JCon(C) and MCon(C). Since JCon(C) and MCon(C) are dually isomorphic, in what follows we just consider JCon(C). While Con(C) is always an obvious complete meet subsemilattice of JCon(C), it is not always true that it is a complete sublattice, as the following example shows. Let C be the complete lattice depicted below.

[figure: •; •; •; •; •; ⋮; x_{0}; x_{1}; x_{2}; x_{ω}; y]

Consider the family {Θ_{k}}_{k∈ℕ} ⊆ Con(C) defined as follows: For any k ∈ ℕ, Θ_{k} = {⟨c, c⟩ | c ∈ C} ∪ {⟨x_{i}, x_{j}⟩ | 0 < i, j ≤ k}. The set-union of {Θ_{k}}_{k∈ℕ} gives Θ = {⟨c, c⟩ | c ∈ C} ∪ {⟨x_{i}, x_{j}⟩ | 0 < i, j ≤ ω}. It turns out that Θ ∈ JCon(C), while Θ is not a complete congruence: In fact, x_{1}Θx_{ω} whereas x_{1} ∧ y = x_{0} is not congruent with x_{ω} ∧ y = y.

1991 Mathematics Subject Classification. 06B10 (06A15, 06A23, 06D15).

Key words and phrases. Complete lattice, complete congruence, join- and meet-complete congruence, closure operator, pseudocomplement, continuous complete lattice, meet-continuous complete lattice.

The main result of this paper gives a sufficient condition on the complete lattice C in order that Con(C) is a complete sublattice of JCon(C): It turns out that this is true whenever C is continuous (in the standard sense of the book by Gierz et al. [8]). From this result, by duality, we also get that if C is co-continuous then Con(C) is a complete sublattice of MCon(C). Notice that the above complete lattice C is not continuous, and therefore that example is coherent with this result. The problem of characterizing the class of all and only those complete lattices C such that Con(C) is a complete sublattice of JCon(C) remains open.

It is worth remarking that in order to demonstrate the aforementioned result, our proof strategy exploits the isomorphisms between JCon(C) and the complete lattice uco(C) of closure operators on C, and between Con(C) and the complete lattice of co-additive closure operators on C, i.e. closures on C which in addition are complete meet-morphisms. While the former isomorphism was already known, the latter appears to be new. Thus, our main result can be rephrased as follows: If C is continuous then Con(C) can be embedded into uco(C). It is also worth noting that our approach of dealing with a structure isomorphic to complete congruence lattices is somehow reminiscent of the work by Reuter and Wille [15], who, for proving their representation result, exploited a (dual) isomorphism between complete congruence lattices and complete lattices of closed subcontexts of certain concept lattices. While their isomorphism requires certain hypotheses, ours always holds.

The above isomorphisms turn out to be particularly useful for studying complete congruence lattices, because lattices of closure operators have been extensively investigated in the past, and many results on their structure are available, e.g. see [12]. Among the properties of interest that can be inherited from the lattice of closure operators, the property of pseudocomplementedness in complete congruence lattices is particularly important and, to the best of our knowledge, has not been studied yet. We exploit the relation between Con(C) and JCon(C), and a recent result by Giacobazzi et al. [7], to demonstrate that when C is a continuous complete lattice and Θ ∈ Con(C) is continuous (i.e. for any chain Y ⊆ C, ∨_{y∈Y} ∨ [y]_{Θ} = ∨ [∨Y]_{Θ}), then the principal filter generated by Θ is pseudocomplemented. In particular, if C is continuous then Con(C) turns out to be pseudocomplemented. Analogous results hold for JCon(C). Of course, we motivate these results by showing that general theorems with no hypothesis do not hold.

2. Notation and Preliminaries

An (upper) closure operator on a poset C is an operator ρ : C → C monotone, idempotent and extensive (i.e. ∀x ∈ C. x ≤ ρ(x)). Let uco(C) denote the set of all closure operators on the poset C. Morgan Ward’s basic theorem [17] states that when C is a complete lattice, uco(C) ordered pointwise is a complete lattice which is dually isomorphic to the complete lattice of all complete meet subsemilattices of C, ordered by set-inclusion. More in detail,^{1} ⟨uco(C), ⊑, ⊔, ⊓, λx.⊤, λx.x⟩ is a complete lattice, where for every ρ, η ∈ uco(C), {ρ_{i}}_{i∈I} ⊆ uco(C) and x ∈ C:

– ρ ⊑ η iff ∀x ∈ C. ρ(x) ≤ η(x), or, equivalently, ρ ⊑ η iff η(C) ⊆ ρ(C); – (⊔_{i∈I}ρ_{i})(x) = x ⇔ ∀i ∈ I. ρ_{i}(x) = x;

1Throughout the paper, we shall often use Church’s lambda notation for functions [1], so that a function f : X → Y is often denoted by λx.f(x).

– (⊓_{i∈I}ρ_{i})(x) = ∧_{i∈I}ρ_{i}(x);

– λx.⊤ is the top, whereas λx.x is the bottom. For any ρ, η ∈ uco(C) and Y ⊆ C, the following useful properties hold:

(i) ρ(∧_{y∈Y} ρ(y)) = ∧_{y∈Y} ρ(y); (ii) ρ(∨Y) = ρ(∨_{y∈Y} ρ(y)); (iii) ρ ⊑ η ⇒ ρ ∘ η = η = η ∘ ρ.

Lower closure operators are defined dually to upper closure operators: Given a poset C, φ : C → C is a lower closure operator if φ ∈ uco(C^{op}), where C^{op} denotes the dual poset of C. The set of all lower closure operators on C is denoted by lco(C). It turns out that lco(C) ordered pointwise is dually isomorphic to uco(C).

⟨JCon(C), ⊆⟩ and ⟨MCon(C), ⊆⟩ denote, respectively, the complete lattices of all join-complete and meet-complete congruence relations on a complete lattice C, while ⟨Con(C), ⊆⟩ denotes the complete lattice of all (join- and meet-) complete congruences on C. Given any equivalence Θ on C and x ∈ C, we denote the equivalence class of x by [x]_{Θ}.

A complete lattice C is continuous if for any subset {x_{j}^{i}}_{j∈J(i)}^{i∈I} ⊆ C (where I, and, for all i ∈ I, J(i) are sets of indices) such that {x_{j}^{i}}_{j∈J(i)} is a chain for any i ∈ I, the following identity holds:

∧_{i∈I} ∨_{j∈J(i)} x_{j}^{i} = ∨_{φ∈J^{I}} ∧_{i∈I} x_{φ(i)}^{i}

where J^{I} is the set of all the functions φ : I → ∪_{i∈I}J(i) such that for any i ∈ I, φ(i) ∈ J(i). It is well-known that replacing chains with directed subsets in the above formulation, one gets an equivalent definition [11]. Continuous complete lattices are usually defined by means of the well-known so-called “way-below” relation between elements (see the book [8] for an exhaustive treatment of continuous lattices). Alan Day [4] (see also [8, Theorem 2.3]) gave the above equational characterization for continuous complete lattices. A complete lattice C is meet-continuous if for any chain Y ⊆ C and x ∈ C, x ∧ (∨Y) = ∨_{y∈Y} x ∧ y. Trivially, meet-continuity is implied by continuity.

3. Complete Congruences and Closure Operators

In this section, we prove the isomorphisms mentioned in Section 1 between complete congruence and closure operator lattices.

As observed by J.B. Nation and Alex Pogel [13, Section 2], the following isomorphism can be viewed as an extension of an analogous finite version first given by Ralph Freese and J.B. Nation [5, Lemma 1]. Moreover, a bijection between JCon(C) and uco(C) was also observed by Patrick Cousot [2, Section 4.2.6]. We present here a full proof.

Lemma 3.1. If C is any complete lattice then JCon(C) ≅ uco(C).

Proof. For any ρ ∈ uco(C), we associate the kernel relation Θ_{ρ} = {⟨x, y⟩ ∈ C × C | ρ(x) = ρ(y)}, and for any join-complete congruence Θ ∈ JCon(C), we associate the map ρ_{Θ} = λx. ∨ [x]_{Θ}. It is easy to see that Θ_{ρ} ∈ JCon(C) (join-completeness: (∀i ∈ I. x_{i}Θ_{ρ}y_{i}) ⇒ ρ(∨_{i}x_{i}) = ρ(∨_{i}ρ(x_{i})) = ρ(∨_{i}ρ(y_{i})) = ρ(∨_{i}y_{i})), ρ_{Θ} ∈ uco(C), Θ_{ρ_{Θ}} = Θ, and ρ_{Θ_{ρ}} = ρ. Thus, let us show that for all ρ, η ∈ uco(C), ρ ⊑ η ⇔ Θ_{ρ} ⊆ Θ_{η}. (⇒) Assume that ρ(x) = ρ(y). Then, x ≤ ρ(x) = ρ(y) ≤ η(y), and therefore η(x) ≤ η(η(y)) = η(y). Dually, η(y) ≤ η(x). (⇐) Let x ∈ C. By idempotency of ρ, we get ρ(x) ≤ ∨{z ∈ C | ρ(z) = ρ(x)}, and therefore ρ(x) ≤ η(∨{z ∈ C | ρ(z) = ρ(x)}). Moreover, since, by property (ii) in Section 2, ρ(∨{z ∈ C | ρ(z) = ρ(x)}) = ρ(∨{ρ(z) | ρ(z) = ρ(x)}) = ρ(ρ(x)) = ρ(x), by hypothesis we get η(x) = η(∨{z ∈ C | ρ(z) = ρ(x)}), from which ρ(x) ≤ η(x).

Given a complete lattice C, let us denote by uco^{ca}(C) the subset of uco(C) consisting of all co-additive closure operators on C, i.e. closures which in addition are complete meet-morphisms. It is easily seen that uco^{ca}(C) is a complete meet subsemilattice of uco(C), and therefore it is a complete lattice ordered pointwise. The following result shows that uco^{ca}(C) is isomorphic to Con(C).

Theorem 3.2. If C is any complete lattice then Con(C) ≅ uco^{ca}(C).

Proof. With reference to the proof of Lemma 3.1, it is enough to show that for any Θ ∈ Con(C) and ρ ∈ uco^{ca}(C), (i) ρ_{Θ} is co-additive and (ii) Θ_{ρ} is meet-complete.

(i) For any {x_{i}}_{i∈I} ⊆ C, we have to show that ∨[∧_{i}x_{i}]_{Θ} = ∧_{i}(∨[x_{i}]_{Θ}): By hypothesis, ∧_{i}x_{i}Θ ∧_{i} (∨[x_{i}]_{Θ}); moreover, since ρ_{Θ} = λx. ∨ [x]_{Θ} is a closure, then, by property (i) in Section 2, ∧_{i}(∨[x_{i}]_{Θ}) = ∨[∧_{i}(∨[x_{i}]_{Θ})]_{Θ}, and therefore this concludes. (ii) If ∀i ∈ I. ρ(x_{i}) = ρ(y_{i}) then ρ(∧_{i}x_{i}) = ∧_{i}ρ(x_{i}) = ∧_{i}ρ(y_{i}) = ρ(∧_{i}y_{i}).

4. The Main Result

In this section, we prove that if C is a continuous complete lattice then Con(C) is a complete sublattice of JCon(C). In view of Lemma 3.1 and Theorem 3.2, our proof will consist in showing that if C is continuous then uco^{ca}(C) is a complete sublattice of uco(C). The first part of this proof has been split in a number of lemmata.

Let C be a complete lattice and f : C → C. For any ordinal α ∈ Ord and x ∈ C, the ordinal (upper) α-power f^{α}(x) of f in x is defined by transfinite induction as follows:

– if α = 0, then f^{0}(x) = x;

– if α is a successor, then f^{α}(x) = f(f^{α−1}(x));

– if α is a limit ordinal, then f^{α}(x) = ∨_{γ<α}f^{γ}(x).

The following lemma, due to Patrick and Radhia Cousot [3, Theorem 4.3], gives a constructive characterization for the lub ⊔ of closure operators.

Lemma 4.1 ([3]). Let {ρ_{i}}_{i∈I} ⊆ uco(C). Then, there exists δ ∈ Ord such that for any x ∈ C, (⊔_{i∈I}ρ_{i})(x) = ∨_{β<δ}(λy. ∨_{i∈I} ρ_{i}(y))^{β}(x).

The next lemma demonstrates that the lub of a nonempty family of closures {ρ_{i}}_{i∈I} ⊆ uco(C) is co-additive iff the following condition holds:

∀X ⊆ C. (⊔_{i∈I}ρ_{i})(∧X) = (⊔_{i∈I}ρ_{i})(∧{∨_{i∈I}ρ_{i}(x) | x ∈ X}).  (‡)

Lemma 4.2. Let {ρ_{i}}_{i∈I} ⊆ uco(C) with I ≠ ∅. Then, ⊔_{i∈I}ρ_{i} ∈ uco^{ca}(C) iff (‡) holds.

Proof. (⇒) Assume (⊔_{i∈I}ρ_{i}) ∈ uco^{ca}(C) and let X ⊆ C. Then,

(⊔_{i∈I}ρ_{i})(∧X)  ≤ (since ∀x. x ≤ ∨_{i∈I}ρ_{i}(x))
(⊔_{i∈I}ρ_{i})(∧{∨_{i∈I}ρ_{i}(x) | x ∈ X}) ≤ (since ∀x. ∨_{i∈I} ρ_{i}(x) ≤ (⊔_{i∈I}ρ_{i})(x))
(⊔_{i∈I}ρ_{i})(∧{(⊔_{i∈I}ρ_{i})(x) | x ∈ X}) = (by hypothesis)
(⊔_{i∈I}ρ_{i})((⊔_{i∈I}ρ_{i})(∧X))  = (by idempotency)

(⊔_{i∈I}ρ_{i})(∧X)

and therefore (‡) holds. (⇐) Assume (‡) holds. We prove by transfinite induction that for any α ∈ Ord and X ⊆ C:

(⊔_{i∈I}ρ_{i})(∧X) = (⊔_{i∈I}ρ_{i})(∧{(λy. ∨_{i∈I} ρ_{i}(y))^{α}(x) | x ∈ X}).  (⋆)

(α = 0): Trivial.

(α + 1): We have that:

(⊔_{i∈I}ρ_{i})(∧{(λy. ∨_{i∈I} ρ_{i}(y))^{α+1}(x) | x ∈ X})  = (by definition)
(⊔_{i∈I}ρ_{i})(∧{∨_{i∈I}ρ_{i}((λy. ∨_{i∈I} ρ_{i}(y))^{α}(x)) | x ∈ X}) = (by (‡))
(⊔_{i∈I}ρ_{i})(∧{(λy. ∨_{i∈I} ρ_{i}(y))^{α}(x) | x ∈ X})  = (by induction)

(⊔_{i∈I}ρ_{i})(∧X).

(α limit ordinal): First note that for any x ∈ X, {(λy. ∨_{i∈I} ρ_{i}(y))^{β}(x)}_{β<α} is an increasing chain, since, by extensivity of closures, x ≤ (λy. ∨_{i∈I} ρ_{i}(y))(x). Hence, by continuity of C:

∧_{x∈X} ∨_{β<α} (λy. ∨_{i∈I} ρ_{i}(y))^{β}(x) = ∨_{β<α} ∧_{x∈X} (λy. ∨_{i∈I} ρ_{i}(y))^{β}(x),

and therefore

∧{(λy. ∨_{i∈I} ρ_{i}(y))^{α}(x) | x ∈ X} = ∨_{β<α} ∧_{x∈X} (λy. ∨_{i∈I} ρ_{i}(y))^{β}(x).

Thus, the following equalities close the limit ordinal step:

(⊔_{i∈I}ρ_{i})(∨_{β<α} ∧_{x∈X} (λy. ∨_{i∈I} ρ_{i}(y))^{β}(x))  = (by (ii) in Section 2)
(⊔_{i∈I}ρ_{i})(∨_{β<α}(⊔_{i∈I}ρ_{i})(∧_{x∈X}(λy. ∨_{i∈I} ρ_{i}(y))^{β}(x))) = (by induction)
(⊔_{i∈I}ρ_{i})((⊔_{i∈I}ρ_{i})(∧X))  = (by idempotency)

(⊔_{i∈I}ρ_{i})(∧X).

Now, by Lemma 4.1, there exists δ ∈ Ord such that for any x ∈ X,

(⊔_{i∈I}ρ_{i})(x) = ∨_{β<δ}(λy. ∨_{i∈I} ρ_{i}(y))^{β}(x).

For any x ∈ X, consider {(λy. ∨_{i∈I} ρ_{i}(y))^{β}(x)}_{β<δ}, which is an increasing chain in C. By continuity of C,

∧_{x∈X} ∨_{β<δ} (λy. ∨_{i∈I} ρ_{i}(y))^{β}(x) = ∨_{β<δ} ∧_{x∈X} (λy. ∨_{i∈I} ρ_{i}(y))^{β}(x),

and therefore

∧_{x∈X}(⊔_{i∈I}ρ_{i})(x) = ∨_{β<δ} ∧_{x∈X} (λy. ∨_{i∈I} ρ_{i}(y))^{β}(x).

Thus,

∧_{x∈X}(⊔_{i∈I}ρ_{i})(x)  = (by property (i) in Section 2)
(⊔_{i∈I}ρ_{i})(∧_{x∈X}(⊔_{i∈I}ρ_{i})(x))  =
(⊔_{i∈I}ρ_{i})(∨_{β<δ} ∧_{x∈X} (λy. ∨_{i∈I} ρ_{i}(y))^{β}(x)) = (by (⋆))
(⊔_{i∈I}ρ_{i})((⊔_{i∈I}ρ_{i})(∧X))  = (by idempotency of ⊔_{i∈I}ρ_{i})

(⊔_{i∈I}ρ_{i})(∧X),

and this concludes the proof.

The next lemma proves that for finite subsets of uco^{ca}(C), property (‡) holds.

Lemma 4.3. If {ρ_{i}}_{i∈I} ⊆ uco^{ca}(C) and 0 < |I| < ℵ_{0}, then (‡) holds.

Proof. Let X ⊆ C. The inequality (⊔_{i∈I}ρ_{i})(∧X) ≤ (⊔_{i∈I}ρ_{i})(∧_{x∈X} ∨_{i∈I} ρ_{i}(x)) always holds. Then, we prove by induction on the cardinality |I| = n that

(⊔_{i∈I}ρ_{i})(∧_{x∈X} ∨_{i∈I} ρ_{i}(x)) ≤ (⊔_{i∈I}ρ_{i})(∧X).

(n = 1): Trivial, by co-additivity.

(n + 1): Assume that {ρ_{i}}_{i∈I} = {ρ_{i}}_{i∈Ī} ∪ {ρ̄}, for some Ī ⊂ I such that |Ī| = n. Let X ⊆ C. Then,

(⊔_{i∈I}ρ_{i})(∧_{x∈X} ∨_{i∈I} ρ_{i}(x)) = (⊔_{i∈I}ρ_{i})(∧{∨_{i∈Ī}ρ_{i}(x) ∨ ρ̄(x) | x ∈ X}).

Moreover, by monotonicity and extensivity, for any x ∈ X:

(∨_{i∈Ī}ρ_{i}(x)) ∨ ρ̄(x) ≤ (∨_{i∈Ī}ρ_{i}(x)) ∨ ρ̄(∨_{i∈Ī}ρ_{i}(x)) = ρ̄(∨_{i∈Ī}ρ_{i}(x)).  (∗)

Thus, we have the following inequalities:

(⊔_{i∈I}ρ_{i})(∧_{x∈X} ∨_{i∈I} ρ_{i}(x))  ≤ (by (∗))
(⊔_{i∈I}ρ_{i})(∧_{x∈X} ρ̄(∨_{i∈Ī}ρ_{i}(x)))  = (by co-additivity of ρ̄)
(⊔_{i∈I}ρ_{i})(ρ̄(∧_{x∈X} ∨_{i∈Ī} ρ_{i}(x)))  = (since (⊔_{i∈I}ρ_{i}) ∘ ρ̄ = ⊔_{i∈I}ρ_{i})
(⊔_{i∈I}ρ_{i})(∧_{x∈X} ∨_{i∈Ī} ρ_{i}(x))  = (since (⊔_{i∈I}ρ_{i}) ∘ (⊔_{i∈Ī}ρ_{i}) = ⊔_{i∈I}ρ_{i})
(⊔_{i∈I}ρ_{i})((⊔_{i∈Ī}ρ_{i})(∧_{x∈X} ∨_{i∈Ī} ρ_{i}(x))) ≤ (by inductive hypothesis)
(⊔_{i∈I}ρ_{i})((⊔_{i∈Ī}ρ_{i})(∧X))  = (since (⊔_{i∈I}ρ_{i}) ∘ (⊔_{i∈Ī}ρ_{i}) = ⊔_{i∈I}ρ_{i})

(⊔_{i∈I}ρ_{i})(∧X),

and therefore, (⊔_{i∈I}ρ_{i})(∧_{x∈X} ∨_{i∈I} ρ_{i}(x)) ≤ (⊔_{i∈I}ρ_{i})(∧X), as desired.

Lemma 4.4. If C is a continuous complete lattice then uco^{ca}(C) is a complete sublattice of uco(C).

Proof. Let {ρ_{i}}_{i∈I} ⊆ uco^{ca}(C). Let us show that ⊓_{i∈I}ρ_{i} ∈ uco^{ca}(C): If X ⊆ C then (⊓_{i∈I}ρ_{i})(∧X) = ∧_{i∈I}ρ_{i}(∧X) = ∧_{i∈I} ∧_{x∈X} ρ_{i}(x) = ∧_{x∈X} ∧_{i∈I} ρ_{i}(x) = ∧(⊓_{i∈I}ρ_{i})(X). Let us now turn to the lub. If I = ∅ then ⊔_{i∈I}ρ_{i} = λx. x ∈ uco^{ca}(C). Then, let us assume |I| ≥ 1. Thus, by Lemma 4.2, it is enough to show that (‡) holds. We write J ⊆_{ℵ_{0}} I when J ⊆ I and |J| < ℵ_{0}. Let X ⊆ C. For any J ⊆_{ℵ_{0}} I, we have:

(⊔_{i∈I}ρ_{i})(∧X)  = (since (⊔_{i∈I}ρ_{i}) ∘ (⊔_{j∈J}ρ_{j}) = ⊔_{i∈I}ρ_{i})
(⊔_{i∈I}ρ_{i})((⊔_{j∈J}ρ_{j})(∧X))  = (by Lemma 4.3)
(⊔_{i∈I}ρ_{i})((⊔_{j∈J}ρ_{j})(∧_{x∈X}(∨_{j∈J}ρ_{j}(x)))) = (since (⊔_{i∈I}ρ_{i}) ∘ (⊔_{j∈J}ρ_{j}) = ⊔_{i∈I}ρ_{i})

(⊔_{i∈I}ρ_{i})(∧_{x∈X}(∨_{j∈J}ρ_{j}(x))).

Hence,

(⊔_{i∈I}ρ_{i})(∨_{J⊆_{ℵ_{0}} I} ∧_{x∈X} (∨_{j∈J}ρ_{j}(x)))  = (by (ii) in Section 2)
(⊔_{i∈I}ρ_{i})(∨_{J⊆_{ℵ_{0}} I}(⊔_{i∈I}ρ_{i})(∧_{x∈X}(∨_{j∈J}ρ_{j}(x)))) =
(⊔_{i∈I}ρ_{i})((⊔_{i∈I}ρ_{i})(∧X))  = (by idempotency of ⊔_{i∈I}ρ_{i})

(⊔_{i∈I}ρ_{i})(∧X).

Moreover, note that for any x ∈ X, {∨_{j∈J}ρ_{j}(x) | J ⊆_{ℵ_{0}} I} is clearly a directed subset of C. Therefore, by continuity of C,

∧_{x∈X} ∨_{i∈I} ρ_{i}(x) = ∧_{x∈X} ∨_{J⊆_{ℵ_{0}} I} (∨_{j∈J}ρ_{j}(x)) = ∨_{J⊆_{ℵ_{0}} I} ∧_{x∈X} (∨_{j∈J}ρ_{j}(x)).

Thus,

(⊔_{i∈I}ρ_{i})(∧X) = (⊔_{i∈I}ρ_{i})(∧_{x∈X} ∨_{i∈I} ρ_{i}(x)),

which closes the proof.

Theorem 4.5. If C is a continuous complete lattice then Con(C) is a complete sublattice of JCon(C).

Proof. By Lemma 3.1 and Theorem 3.2, this is a consequence of Lemma 4.4.

By duality, one also gets the following result.

Theorem 4.6. If C is a co-continuous complete lattice then Con(C) is a complete sublattice of MCon(C).

Proof. Let us denote by lco^{a}(C) the complete lattice of all additive lower closure operators on C. By duality, from Lemma 3.1, Theorem 3.2 and Lemma 4.4, one respectively gets that MCon(C) ≅ lco(C), Con(C) ≅ lco^{a}(C) and lco^{a}(C) is a complete sublattice of lco(C), and therefore one gets the thesis.

5. Pseudocomplements of Complete Congruences

One can exploit Theorem 4.5 to prove results on the structure of complete congruence lattices inherited from those of lattices of closure operators: For any class 𝕂 of complete lattices closed under the formation of complete sublattices, one gets that if C is continuous and uco(C) belongs to 𝕂 then Con(C) is in 𝕂 as well. In the following, we present one such relevant example.

Following the terminology used by Giacobazzi et al. [7, Definition 2.1], given a meet semilattice L and x, y ∈ L such that y ≤ x, we say that x ⇝ y ∈ L is the weak relative pseudocomplement of x with respect to y, if x ∧ x ⇝ y = y and ∀z ∈ L. x ∧ z = y ⇒ z ≤ x ⇝ y. Clearly, if x ⇝ y exists, then it is necessarily unique. L is weakly relatively pseudocomplemented if such x ⇝ y exists for any x, y ∈ L such that y ≤ x. Equivalently, L is weakly relatively pseudocomplemented if any principal filter of L is pseudocomplemented. Note that x ⇝ ⊥, when it exists, is the pseudocomplement of x. We refer to the discussions in [6, 7] for the relationship occurring between this notion and the well-known notion of relative pseudocomplementation.

Dona Papert [14, Theorem 2] proved that the complete lattice of congruence relations on a join semilattice is weakly relatively pseudocomplemented. This is instead not true for join complete congruence relations. In fact, given a complete lattice C, by Lemma 3.1, JCon(C) ≅ uco(C), and Giacobazzi et al. [7, Examples 3.2 and 3.3] show that in general uco(C) is not weakly relatively pseudocomplemented. On the other hand, Giacobazzi et al. [7, Theorem 3.1] give the following result.

Lemma 5.1 ([7]). If C is a meet-continuous complete lattice then for every ρ, η ∈ uco(C) such that η ⊑ ρ and ρ is continuous (i.e. preserving the lub of any chain in C) there exists ρ⇝η.

Let us describe how to exploit this result on the complete congruence side. Given a complete lattice C, we say that an equivalence relation Θ ⊆ C × C is continuous if for any chain Y ⊆ C, ∨_{y∈Y} ∨ [y]_{Θ} = ∨ [∨Y]_{Θ}. The following result is then an easy consequence of Lemma 5.1.

Theorem 5.2. If C is meet-continuous then for every Θ, Ξ ∈ JCon(C) such that Ξ ⊆ Θ and Θ is continuous there exists Θ⇝Ξ.

Proof. This is a consequence of Lemmata 3.1 and 5.1, since it is immediate to note that the isomorphism between JCon(C) and uco(C) preserves the property of being continuous.

In particular, since the least join complete congruence is trivially continuous, we get that if C is meet-continuous then JCon(C) is pseudocomplemented.

Let us now turn to complete congruences.

Theorem 5.3. If C is continuous then for every Θ, Ξ ∈ Con(C) such that Ξ ⊆ Θ and Θ is continuous there exists Θ⇝Ξ.

Proof. This is a consequence of Theorems 4.5 and 5.2, and of the following observation: If M is a complete sublattice of a complete lattice L, and for some x, y ∈ M with y ≤ x, x⇝y exists in L, then the weak relative pseudocomplement of x with respect to y in M exists too.

Here again, we get the following interesting immediate consequence.

Corollary 5.4. If C is continuous then Con(C) is pseudocomplemented.

To conclude, it is worth presenting a simple example showing that Con(C) is not in general pseudocomplemented. Consider the complete lattice C depicted below, obtained as direct product of the 2-chain {0, 1} and the (ω + 1)-chain with the element 0_{ω} removed.

[figure: 0_{0}; 0_{1}; 1_{0}; 0_{2}; 1_{1}; 1_{2}; 1_{ω}; ⋮; ⋮; •; •; •; •; •; •; •]

Consider the following complete congruence Θ ∈ Con(C): Θ = {⟨x, x⟩ | x ∈ C} ∪ {⟨0_{i}, 1_{i}⟩ | 0 ≤ i < ω}^{s} ({·}^{s} denotes the symmetric closure). Further, consider the family {Ψ_{k}}_{k∈ℕ} ⊆ Con(C) defined as follows: For any k ∈ ℕ, Ψ_{k} = {⟨x, x⟩ | x ∈ C} ∪ {⟨0_{i}, 0_{k}⟩ | 0 ≤ i ≤ k}^{s} ∪ {⟨1_{i}, 1_{k}⟩ | 0 ≤ i ≤ k}^{s}. It is then clear that for any k ∈ ℕ, Θ ∧_{Con(C)} Ψ_{k} = {⟨x, x⟩ | x ∈ C}, while ∨_{Con(C)}{Ψ_{k} | k ∈ ℕ} = C × C, and therefore Θ does not admit pseudocomplement. This example is coherent with the above corollary, since C is clearly not continuous.

References

[1] A. Church. The calculi of lambda conversion. Annals of Math. Studies, Princeton Univ. Press, Princeton, 1941.

[2] P. Cousot.Méthodes Itératives de Construction et d’Approximation de Points Fixes d’Opérateurs Monotones sur un Treillis, Analyse Sémantique des Programmes. PhD thesis, Université Scientifique et Médicale de Grenoble, France, 1978.

[3] P. Cousot and R. Cousot.A constructive characterization of the lattices of all retractions, preclosure, quasi-closure and closure operators on a complete lattice. Portugal. Math., 38(2):185– 198, 1979.

[4] A. Day. Filter monads, continuous lattices and closure systems. Canad. J. Math., 27:50–59, 1975.

[5] R. Freese and J.B. Nation. Congruence lattices of semilattices. Pacific J. Math., 49(1):51–58, [6] R. Freese and J.B. Nation. Clarification to ‘Congruence lattices of semilattices’. Unpub-

lished manuscript, July 1995. Electronically available from Ralph Freese’s Home Page: http://www.math.hawaii.edu/∼ralph.

[7] R. Giacobazzi, C. Palamidessi, and F. Ranzato. Weak relative pseudo-complements of closure operators. Algebra Universalis, 36(3):405–412, 1996.

[8] G. Gierz, K.H. Hofmann, K. Keimel, J.D. Lawson, M. Mislove, and D.S. Scott. A Compendium of Continuous Lattices. Springer-Verlag, Berlin, 1980.

[9] G. Grätzer and H. Lakser. On complete congruence lattices of complete lattices. Trans. Amer. Math. Soc., 327(1):385–405, 1991.

[10] G. Grätzer and E.T. Schmidt.Complete congruence lattices of complete distributive lattices. J. Algebra, 170:204–229, 1995.

[11] G. Markowsky. Chain-complete posets and directed sets with applications. Algebra Universalis, 6(1):53–68, 1976.

[12] J. Morgado.Some results on the closure operators of partially ordered sets. Portugal. Math., 19(2):101–139, 1960.

[13] J.B. Nation and A. Pogel. The lattice of completions of an ordered set. Order, 14(1):1–7, 1997.

[14] D. Papert. Congruence relations in semi-lattices. J. London Math. Soc., 39:723–729, 1964.

[15] K. Reuter and R. Wille. Complete congruence relations of concept lattices. Acta Sci. Math. (Szeged), 51:319–327, 1987.

[16] S.-K. Teo. Representing finite lattices as complete congruence lattices of complete lattices. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 33:177–182, 1990.

[17] M. Ward. The closure operators of a lattice. Ann. Math., 43(2):191–196, 1942.

[18] R. Wille. Subdirect decompositions of concept lattices. Algebra Universalis, 17:275–287, 1983.

Dipartimento di Informatica, Università di Pisa, Corso Italia 40, 56125 Pisa, Italy

E-mail address: giaco@di.unipi.it

Dipartimento di Matematica Pura ed Applicata, Università di Padova, Via Belzoni 7, 35131 Padova, Italy

E-mail address: franz@math.unipd.it