PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série tome 67(81) (2000), 7–13

RELATIVE COMPLEMENTS IN THE WEAK CONGRUENCE LATTICE

Branimir Šešelja and Andreja Tepavčević

Communicated by Žarko Mijajlović

Abstract. Necessary and sufficient conditions under which a weak congruence lattice of an algebra is relatively complemented are given. Consequences concerning other kinds of complementedness are also presented. Finally, we investigate which of the main algebraic constructions preserve the relative complements in the weak congruence lattice.

1. Introduction

Weak congruences have been extensively investigated over the last decade. The lattice of these relations on an algebra turns out to be a useful tool for understanding connections among congruences of subalgebras and subalgebras themselves. Thus it is possible to characterize algebras and varieties by properties of weak congruence lattices (e.g., [1, 9, 11, 8]). Another direction in these investigations are descriptions of weak congruence lattices for particular classes of algebras (e.g., [5, 6, 7]). Finally, problems of representations of algebraic lattices by weak congruences were also discussed (e.g., [2, 10]). Generalizations of weak congruences by a wider class of compatible relations were given in [3].

The aim of the present paper is to characterize algebras having relatively complemented lattices of weak congruences. We give necessary and sufficient conditions under which an algebra satisfies this property. In addition, complementedness of this lattice is investigated, and improvements of the results from [9] are obtained.

2. Preliminaries

We advance some basic notions concerning weak congruences, and also some relevant lattice-theoretic properties of special elements in a lattice. For more details and other properties of weak congruences lattices, we refer to the list of papers, given in References.

1991 Mathematics Subject Classification. Primary 08A30; Secondary 06C15.

A weak congruence ρ of an algebra A = (A, F) is a symmetric and transitive relation on A, which is also compatible with all fundamental operations (where compatibility with nullary operations is also assumed—for a nullary operation c, c ρ c is satisfied). Obviously, a nonempty weak congruence on A is an ordinary congruence on a subalgebra of A. By the definition, ∅ is also a weak congruence if and only if there are no nullary operations in F. A set of all weak congruences of an algebra A is an algebraic lattice under inclusion and is denoted by Cw A [11].

We denote the diagonal relation of a set A by Δ_{A}, or simply by Δ when there is no danger of confusion. The diagonal relation Δ is always a codistributive element in a weak congruence lattice, i.e., for all ρ, θ ∈ Cw A, the following holds:

Δ ∧ (ρ ∨ θ) = (Δ ∧ ρ) ∨ (Δ ∧ θ).

Obviously, the filter ↑Δ is the congruence lattice Con A. The ideal ↓Δ is isomorphic with Sub A (the lattice of subuniverses of A).

An algebra A satisfies the Congruence Extension Property (the CEP) if every congruence of any subalgebra of A is a restriction of a congruence of A. An algebra A satisfies the Congruence Intersection Property (the CIP) if for each ρ ∈ Con B, θ ∈ Con C, B, C ∈ Sub A, the following holds:

(ρ ∩ θ)_{A} = ρ_{A} ∩ θ_{A},

where ρ_{A} is the smallest congruence of A containing ρ. In particular, if θ ∈ Con A, then the above equality becomes

(ρ ∩ θ)_{A} = ρ_{A} ∩ θ,

and we say that an algebra A satisfying this condition has the weak CIP (the wCIP). An algebra A satisfies the CEP if and only if the diagonal relation Δ is a cancellable element in Cw A, i.e., if and only if for all ρ, θ ∈ Cw A,

ρ ∧ Δ = θ ∧ Δ and ρ ∨ Δ = θ ∨ Δ imply ρ = θ.

An algebra A satisfies the CIP if and only if Δ is a distributive element in Cw A, that is if and only if for all ρ, θ ∈ Cw A, the following equality holds:

Δ ∨ (ρ ∧ θ) = (Δ ∨ ρ) ∧ (Δ ∨ θ).

Consequently, an algebra A has the wCIP if and only if for every congruence ρ of a subalgebra of A and a congruence θ of A, the following is satisfied:

Δ ∨ (ρ ∧ θ) = (Δ ∨ ρ) ∧ θ.

If an algebra A satisfies the wCIP and the CEP, then for every subalgebra B of A, Con B is isomorphic to the interval [Δ, B^{2} ∨ Δ] in Cw A, under ρ ↦ ρ ∨ Δ.

In addition to distributive, codistributive and cancellable elements, the following lattice-theoretic notions are also used throughout the paper (see e.g., [4]). An element a in a lattice L is neutral if for all x, y ∈ L, the following equality holds:

(x ∨ y) ∧ (y ∨ a) ∧ (a ∨ x) = (x ∧ y) ∨ (y ∧ a) ∨ (a ∧ x).

An element a in a lattice L is standard if for all x, y ∈ L, we have that

x ∧ (a ∨ y) = (x ∧ a) ∨ (x ∧ y).

An element a is a neutral element of a lattice L if and only if it is distributive, codistributive and cancellable if and only if it is standard and codistributive. It follows that an algebra A satisfies CEP and CIP if and only if Δ is a neutral element in Cw A.

The center of a bounded lattice L is a set of all neutral elements from L which have complements. If L is a bounded lattice, and a ∈ L belongs to its center, then

L ≅ ↑a × ↓a, under x ↦ (x ∨ a, x ∧ a).

3. Results

Main properties of the weak congruence lattice of an algebra usually depend on its diagonal relation. Therefore, we begin with algebraic conditions under which there is a complement of the diagonal relation Δ in this lattice.

Proposition 1. The diagonal relation Δ has a complement in the weak congruence lattice Cw A of an algebra A if and only if A has at least one nullary operation and no congruence of A has a block which is a proper subalgebra of A.

Proof. Observe that the smallest subuniverse of A is not empty, since there are constants in A. If Δ has a complement in the lattice Cw A, then the smallest subuniverse B_{m} of A has more than one element. Indeed, every complement Δ′ of Δ belongs to Con B_{m}, since Δ ∧ Δ′ = Δ_{B_{m}} (B_{m} is the subalgebra corresponding to B_{m}). Therefore, Δ′ ≤ B_{m}^{2}, and since Δ ∨ Δ′ = A^{2}, B_{m}^{2} is also a complement of Δ. An algebra A is not trivial, hence |B_{m}| > 1. Now, if ρ is a congruence of A (≠ A^{2}) with a block which is a subalgebra C of A, then B_{m}^{2} ∨ Δ ≤ C^{2} ∨ Δ < A^{2}, which contradicts the (proved) fact that B_{m}^{2} is a complement of Δ. Finally, A must have nullary operations, otherwise the empty set would be the smallest subuniverse.

Conversely, suppose that A has nullary operations and that no congruence of A has a block which is a proper subalgebra of A. By the first assumption the smallest subuniverse B_{m} of A is nonempty, and if there is no complement of Δ in Cw A, then B_{m}^{2} ∨ Δ = θ < A^{2}, and [B_{m}]_{θ} is a proper subalgebra of A. This contradicts the second assumption, and thus Δ must have a complement. □

We proceed with conditions under which the lattice of weak congruences of an algebra is relatively complemented (which means that every interval in this lattice is a complemented lattice itself).

Theorem 1. The lattice of weak congruences of an algebra A is relatively complemented if and only if all of the following conditions are satisfied:

(1) A has at least one nullary operation,

(2) no nontrivial congruence of A has a block which is a subalgebra of A,

(3) A satisfies the CEP and the CIP, and

(4) both Sub A and Con A are relatively complemented lattices.

Proof. If Cw A is relatively complemented, then the principal ideal ↓Δ is standard, and hence Δ is a standard element of this lattice. Being also codistributive, Δ is a neutral element of Cw A, so A satisfies both the CEP and the CIP. Since Δ has a complement, by Proposition 1 there are nullary operations in A and no congruence has a block which is a subalgebra. Obviously, Sub A and Con A are relatively complemented, as interval sublattices of Cw A.

Conversely, if A has nullary operations and no congruence has a block which is a subalgebra, then Δ has a complement in the weak congruence lattice. Further, by the CEP and the CIP, Δ is a neutral element in the lattice Cw A. Thus, Δ is in the center of this lattice, which is therefore isomorphic with Sub A × Con A. These two lattices are relatively complemented, hence Cw A has the same property. □

Complementedness of weak congruence lattices was characterized in [9], as follows.

Proposition 2. [9] An algebra A has the CEP, the CIP and a complemented weak congruence lattice if and only if it satisfies the following conditions:

(i) for every subalgebra B, Con B is isomorphic with Con A under ρ ↦ ρ_{A} and (ii) Sub A and Con A are complemented lattices. □ The following proposition is closely connected to Theorem 2 below. Proposition 3. If the weak congruence lattice of an algebra A is comple-

mented, then Sub A is a complemented lattice. If, in addition, A satisfies the wCIP, then also Con A is complemented.

Proof. Suppose that Cw A is complemented, then by Proposition 1 the smallest subuniverse B_{m} of A is nonempty. Let C ∈ Sub A. The corresponding diagonal relation Δ_{C} has a complement ρ in Cw A, hence Δ_{C} ∨ ρ = A^{2} and Δ_{C} ∧ ρ = Δ_{B_{m}}. If D is a subalgebra of A and ρ ∈ Con D, it follows that Δ_{C} ∨ Δ_{D} = Δ and Δ_{C} ∧ Δ_{D} = Δ_{B_{m}}.

Hence, in the lattice Sub A, we have C ∨ D = A and C ∧ D = B_{m}, which proves that Sub A is complemented.

Suppose now that A has the wCIP, and that the complement of θ ∈ Con A in Cw A is θ′. We prove that θ has a complement in Con A as well. Note that θ ∧ θ′ = Δ_{B_{m}}. Now, the complement of θ in Con A is Δ ∨ θ′. Indeed,

θ ∨ (Δ ∨ θ′) = (θ ∨ Δ) ∨ θ′ = θ ∨ θ′ = A^{2}.

Further, by the wCIP and by properties of θ′

(Δ ∨ θ′) ∧ θ = Δ ∨ (θ′ ∧ θ) = Δ ∨ Δ_{B_{m}} = Δ.

Hence, Con A is a complemented lattice. □

Proposition 4. If an algebra A has the CIP, Δ has a complement in the lattice Cw A, and both Con A and Sub A are complemented lattices, then also Cw A is complemented.

Proof. Let ρ be an arbitrary weak congruence of A, such that ρ ∈ Con B, for a subalgebra B of A. If θ = ρ∨Δ in Cw A, then by the assumption (complementedness of Con A), there is θ′ ∈ Con A, such that θ ∨ θ′ = A^{2} and θ ∧ θ′ = Δ.

Let B′ be a complement of B in Sub A, which exists by the assumption, and let ρ′ := θ′ ∧ B′^{2} (in Cw A). Note that ρ′ ∈ Con B′, and that the fact that Δ has a complement (which is, by Proposition 1, B_{m}^{2}), implies:

Δ ∨ ρ′ = Δ ∨ (B′^{2} ∧ θ′) = (Δ ∨ B′^{2}) ∧ θ′ = A^{2} ∧ θ′ = θ′.

We prove that ρ′ is a complement of ρ in the lattice Cw A. Since B ∨ B′ = A in Sub A, we have that ρ′ ∨ ρ ∈ Con A. Therefore, ρ′ ∨ ρ = (ρ′ ∨ Δ) ∨ (ρ ∨ Δ) = θ′ ∨ θ = A^{2}. Further, by the CIP Δ ∨ (ρ′ ∧ ρ) = (Δ ∨ ρ′) ∧ (Δ ∨ ρ) = θ′ ∧ θ = Δ. Hence, ρ′ ∧ ρ is a diagonal relation, and since it belongs to Con B_{m}, it follows that ρ′ ∧ ρ = Δ_{B_{m}}, which completes the proof. □

Summing up, we have proved.

Theorem 2. Let A be an algebra which satisfies the CIP. Then the lattice of weak congruences of A is complemented if and only if the following conditions are all satisfied:

(1) A has at least one nullary operation;

(2) no congruence of A has a block which is a proper subalgebra of A;

(3) Con A and Sub A are complemented lattices. □ The following example illustrates the previous proposition. Example 1. We present an algebra which has the CIP (but not the CEP),

and whose lattice of weak congruences is complemented. Let A = {a, b, c, d} and A = (A, ∗, a, b, c), where a, b and c are nullary operations and ∗ is a binary operation defined by the table below. The only subuniverse is B_{m} = {a, b, c}. The algebra A has no nontrivial congruences while B_{m} has only one: ρ = {{a, b}, {c}}. The lattice Cw A is represented in Figure 1. □

\begin{matrix}∗ & a & b & c & d \\ a & b & b & c & c \\ b & b & a & c & d \\ c & c & c & a & c \\ d & c & d & c & d \end{matrix}  [figure: Δ; A^{2}; B_{m}^{2}; ρ; B_{m}; Figure 1]

The following consequence of Theorem 1 characterizes algebras having Boolean lattices of weak congruences. This characterization is different from the corresponding result in [9].

Corollary 1. The weak congruence lattice of an algebra A is Boolean if and only if A has nullary operations, satisfies the CEP and the wCIP, no congruence of A has a block which is a proper subalgebra of A, and Sub A and Con A are Boolean lattices.

Proof. Directly by Theorem 1, since algebras with Boolean lattices of weak congruences satisfy the CEP and the CIP, and hence the wCIP. □

To complete this investigation, we answer the following problem.

Problem 1. Is relative complementedness of weak congruence lattices hereditary for the main algebraic constructions: subalgebras, homomorphic images and direct products?

Proposition 5. If the lattice of weak congruences of A is relatively complemented, then the same property has the weak congruence lattice of any subalgebra of A.

Proof. The lattice Cw B of a subalgebra B of A is an interval sublattice of Cw A, namely, it is the principal ideal ↓B^{2}. Hence, it is relatively complemented if Cw A is. □

As the next assertion shows, homomorphisms preserve relative complements in the weak congruence lattice only under certain conditions.

Proposition 6. If the weak congruence lattice of an algebra A is relatively complemented, then the weak congruence lattice of A/θ, θ ∈ Con A, is relatively complemented if and only if Sub A/θ is a relatively complemented lattice.

Proof. Suppose that Cw A is relatively complemented and θ ∈ Con A. Then Cw A/θ is isomorphic to the following part of Cw A:

⋃{[B^{2} ∧ θ, B^{2}] | B ∈ Sub A and B[θ] = B},

where B[θ] := {x ∈ A | x θ b for some b ∈ B}. It is straightforward to prove that we indeed obtain a sublattice of Cw A. The smallest subuniverse of A/θ is nonempty, since A also has this property. Its diagonal relation corresponds in Cw A to C_{m}^{2} ∧ θ, for an appropriate subalgebra C_{m} of A. It is straightforward that C_{m}^{2} is a complement of θ in Cw A/θ. Hence, by Proposition 1, A/θ has nullary operations and has no congruence with a class which is its proper subalgebra. The algebra A has the CEP and the CIP. We prove that A/θ has the same properties. Let ρ, σ ∈ [B^{2} ∧ θ, B^{2}] (this interval in Cw A represents a congruence lattice of a subalgebra of A/θ), and suppose ρ ∨ θ = σ ∨ θ. We also have ρ ∧ θ = σ ∧ θ, and ρ ∧ Δ = σ ∧ Δ. Now, since Δ ∨ ρ ≥ θ, we have Δ ∨ ρ = θ ∨ ρ, and similarly Δ ∨ σ = θ ∨ σ. Hence, since A has the CEP, Δ is cancellable and ρ = σ. Thus A/θ has the CEP. To prove the CIP for A/θ, by the similar arguments as above, since A has the CIP, we have that for any ρ ∈ [B^{2} ∧ θ, B^{2}], τ ∈ [C^{2} ∧ θ, C^{2}], θ ∨ (ρ ∧ τ) = Δ ∨ (ρ ∧ τ) = (Δ ∨ ρ) ∧ (Δ ∨ τ) = (θ ∨ ρ) ∧ (θ ∨ τ), and the CIP holds. Finally, Con A/θ is isomorphic to the principal filter in Con A and hence in Con A/θ, which proves that it is relatively complemented. Now it is obvious that relative complementedness of Sub A/θ implies the same property of Cw A/θ.

The converse is obvious. □

In order to examine whether relative complementedness is preserved under taking direct products, consider, for an algebra A, the lattice Cw A^{2}. Denote by D a subalgebra of A^{2} whose underlying set is the diagonal Δ of A. If θ = {((x, y), (z, t)) | x = z}, and Δ_{Δ} = {((x, x), (x, x)) | x ∈ A}, then the interval [Δ_{Δ}, θ] in Cw A^{2} is not complemented. Indeed, Δ_{A^{2}} belongs to that interval, and does not have a complement in this interval. If Δ′ were such a complement, then we would have Δ′ ∈ Con D and Δ′ ≠ Δ_{Δ}. But θ ∧ Δ^{2} = Δ_{Δ}, hence no element from Con D, except Δ_{Δ}, is less than θ, i.e., no element which could be a complement of Δ belongs to the interval [Δ_{Δ}, θ].

We have thus proved that relative complementedness of weak congruence lattices is not hereditary for direct products of algebras.

4. Acknowledgement

We would like to express our gratefulness to the referee for his suggestions which improved the style and the presentation of the article.

References

[1] I. Chajda, B. Šešelja, A. Tepavčević, On weak congruence modular varieties, Filomat 9:3 (1995), 633–638.

[2] I. Chajda, B. Šešelja, A. Tepavčević, Weak congruences in algebras having restricted similarity types, Discussiones Math. 18 (1998), 27–38.

[3] I. Chajda, B. Šešelja, A. Tepavčević, Lattices of compatible relations satisfying a set of formulas, Algebra Universalis 40 (1998), 51–58.

[4] G. Grätzer, General Lattice Theory, Akademie-Verlag, Berlin, 1978.

[5] B. Šešelja, A note on UCEP, in “Proc. of the International Conference General Algebra and Ordered Sets”, Olomouc, 1994, pp. 131–137.

[6] B. Šešelja, A. Tepavčević, On a characterization of Rees varieties, Tatra Mountains Math. Publ. 5 (1995), 61–69.

[7] B. Šešelja, A. Tepavčević, Infinitely distributive elements in the lattice of weak congruences, General Algebra, 1988, North Holland 1990, pp. 241–253.

[8] B. Šešelja, A. Tepavčević, A note on CIP varieties, Algebra Universalis (to appear).

[9] B. Šešelja, G. Vojvodić, On the complementedness of the lattice of weak congruences, Studia Sci. Math. Hungar. 24 (1989), 289–293.

[10] A. Tepavčević, On representation of lattices by weak congruences and weak tolerances, in: A.G. Pinus and K.N. Ponomaryov (Eds), Algebra and Model Theory, Novosibirsk, 1997, pp. 173–181.

[11] G. Vojvodić, B. Šešelja, On the lattice of weak congruence relations, Algebra Universalis 25 (1988), 121–130.

Institut za matematiku (Received 03 02 1999) Trg D. Obradovića 4 (Revised 28 01 2000) 21000 Novi Sad Yugoslavia

etepavce@eunet.yu