Subalgebras and Homomorphic Images
An algebra consists of a non-empty set A and a collection of finitary operations defined on this set Specifically, an n-ary operation on A, where n is greater than 1, is a function f: A^n → A that maps from the n-th Cartesian power of A to A.
We let On(A) be the set of all n-ary operations defined on A and
00 let O(A) := U On(A) be the set of all finitary operations defined n = l on A
Remark 1.1.1 1 Any n-ary operation f on A can be regarded as an ( n + 1)-ary relation defined on A, called the graph of f This re- lation is defined by {(al, , a,+l) € An+' I f ( a l , , a,) = an+l}
2 If B c A is a non-empty subset of A, then the restriction f A l B of f A t o B is defined by f A I ~ ( a l , ,a,) := f A ( a l , ,a,) for all a l , , an E B
3 The definition of an n-ary operation can be extended in the fol- lowing way to the special case that n = 0, for a nullary operation
A nullary operation on the set A, defined as A0 := (8), is a function f : (0) + A, uniquely determined by the element f(0) ∈ A For each element a ∈ A, there exists a unique mapping fa : (0) + A such that fa(@) = a, which means a nullary operation effectively selects an element from the set A However, if A = 0, then no nullary operations can exist on A.
Algebra can be understood in two distinct ways: first, as a non-indexed form represented by a pair A := (A; FA), which includes a set A alongside a collection of operations FA defined on that set; and second, as an indexed algebra.
Definition 1.1.2 Let A be a non-empty set Let I be some non- empty index set, and let (ft)i,l be a function which assigns t o
An indexed algebra is defined as a pair A = (A; (f:)i,I), where A is the base set or universe and (f:)iE1 represents the sequence of fundamental operations on A Each element i of I corresponds to an ni-ary operation ft defined on A Additionally, the sequence r := (ni)iE1, which outlines the arities of the fundamental operations, is referred to as the type of A.
We use the name Alg(r) for the class of all algebras of type r
In our definition, we specify that the base set A of an algebra cannot be the empty set, as we generally exclude the case of an empty algebra with the empty set as its universe, unless there are no nullary operations involved In indexed cases, fundamental operations are organized in a sequence, allowing for repetitions We will provide examples to illustrate our definition.
A groupoid is defined as an algebraic structure (G; ) of type r = (2), characterized by a single binary operation denoted by “.”, which can also be represented as z y When this binary operation is associative, the structure is referred to as a semigroup Furthermore, a semigroup that includes an additional nullary operation e becomes a monoid, represented as M = (M; 0, e), where e serves as the identity element This means that for every element x in M, the equations x e = e x = x hold true Thus, monoids are classified as algebras of type r = (2, 0).
A group G = (G; a ) is a semigroup, which satisfies the axiom ' d a , b ~ G 3 x , y ~ G ( a x = b a n d ~ a = b ) (invertibility)
A group can also be regarded as an algebra G = (G; , - I , e) of type (2, 1, 0), where the associative law and the axioms and
An algebra R = (R; +, ) of type r = (2,2) is called a semiring if both these binary operations are associative and the distributive laws
I 1 Subalgebras and Homomorphic Images and are satisfied
Rings are semirings with commutative and invertible addition and a commutative ring K = ( K ; +, 0 ) is called a field if ( K \ (0); 0 ) is a group, where the zero element 0 is the neutral element with respect t o addition
An algebra V = (V; A , V ) of type (2,2) is called a lattice, if the following equations are satisfied by its two binary operations, which are usually called meet and join:
If in addition the lattice satisfies the following distributive laws,
'dx, y, x E V (xV(yAx) = (zVy)A(xVx)), then the lattice is said t o be distributive
Lattices play a crucial role in algebra, serving as key examples and being integral to the study of various algebraic structures, as every algebra is associated with specific lattices A lattice can be defined as a partially ordered set (V; I), where I represents a binary, reflexive, anti-symmetric, and transitive relation on V The relationship between lattices and partially ordered sets is further emphasized by established theorems in the field.
Theorem 1.1.3 Let (V; 5) be a partially ordered set in which for all x, y E V both the i n f i m u m A{x, y) and the supremum V{x, y) exist T h e n the i n f i m u m and supremum operations make (V; A , V)
4 1 Basic Concepts a lattice Conversely, every lattice defines a partially ordered set i n which for all x, y the i n f i m u m A{x, y } and the s u p r e m u m V{x, y } exist
Proof: Let (V; 5) be a partially ordered set, in which for any two- element set {x, y ) & V the infimum A{x, y ) and the supremum V{x, y ) exist We define x A y := A{x, y ) and x V y := V{x, y )
Then the required identities are easy t o verify
If conversely (V; A , V ) is a lattice, then we define and see that this gives a partial order relation on V It is easy to check that A{x, y ) = x A y and V{x, y ) = x V y are satisfied
A lattice C in which for all sets B & L the infimum B and the supremum V B exist is called a complete lattice
Obviously, any finite lattice is complete
A bounded lattice (V; A , V , 0 , l ) is an algebra of type (2, 2, 0, 0) which is a lattice, with two additional nullary operations 0 and 1, which satisfy
An algebra B = (B; A, V, l , O , 1) is called a Boolean algebra, if (B; A, V, 0 , l ) is a bounded distributive lattice with an additional unary operation 1 satisfying and
Boolean algebras play a crucial role in mathematics and computer science, with notable examples including the two-element Boolean algebra, which consists of the elements (0, 1) and operations such as conjunction (meet), disjunction (join), and negation Another significant example is the power set algebra, represented as P(A), which incorporates operations like intersection, union, and complements These structures are fundamental for understanding logical operations and set theory.
A with intersection, union, complementation, the empty set and A as operations
An algebra S = ( S ; 0 ) of type (2) is called a semilattice, if the operation is an associative, commutative, and idempotent binary operation on S This means that a semilattice is a particular kind of semigroup
For a given algebra B = ( B ; ( f ? ) i E I ) of type r we obtain new algebras using certain algebraic constructions The first algebraic construction we want to mention, is the formation of subalgebras
Definition 1.1.4 Let B = ( B ; (f?)i,I) be an algebra of type r
Then an algebra A is called a subalgebra of B, written as A c B, if the following conditions are satisfied:
(i) A = ( A ; ( f , i ' ) i , ~ ) is an algebra of type r ;
(iii) 'v'i E I, the graph of f ) is a subset of the graph of f?
The subalgebra property can be checked in the following way:
The Subalgebra Criterion states that if B is an algebra of type r and A is a subset of B such that the operations f_i restricted to A yield the same results as those in B, then A forms a subalgebra of B For A to qualify as a subalgebra, it must be closed under all operations f_i for each index i in the set I, meaning that applying any operation f_i to elements of A will result in elements that are also within A In this context, we say that the operations f_i preserve the subset A of B.
Clearly, the subalgebra relation is transitive, that is, if A C B C C then A c C
If B = ( B ; ( f ? ) i , ~ ) is an algebra of type r and if {Aj I j E J) is a family of subalgebras of B with the non-empty intersection
The intersection of the family {Aj | j ∈ J} forms a subalgebra of B, denoted as nA, which highlights the relationship between the universe A and its corresponding j-th universe, Aj This concept enables a deeper understanding of the structure and properties of the subalgebra within the broader framework of B.
A generating system of an algebra B is defined by a subset X, which is a part of the universe The process of generating subalgebras from this subset adheres to three essential closure properties, classifying it as a closure operator This topic will be explored in greater depth in Chapter 2.
Theorem 1.1.6 Let B be a n algebra For all subsets X and Y of
B , the following closure properties hold:
When the intersection of two subalgebras of B is non-empty, it forms a subalgebra of B This property allows us to establish a binary operation on the set Sub(B), which encompasses all subalgebras of B Consequently, a binary operation A on Sub(B) is defined based on this intersection.
The operation in question is not universally applicable to the set S u b ( B ) due to its inability to address instances where the intersection Al n A2 results in an empty set This issue can be resolved by either treating the empty set as a valid algebraic element or by introducing a new element to the set S u b ( B ) In this latter approach, the operation Al A A2 would be defined as this new element whenever Al n A2 equals the empty set.
In general, the union of two subalgebras, A1 and A2, of a larger algebra B, does not form a subalgebra of B However, it is possible to map the pair (A1, A2) to the subalgebra of B that is generated by their union, A1 ∪ A2.
Theorem 1.1.7 For every algebra B , the algebra ( S u b ( B ) ; A , V ) is a lattice, called the subalgebra lattice of B
Our second important algebraic construction is the formation of homomorphic images
A homomorphism h: A → B between two algebras A and B of the same type is defined such that for every index i in the set I and for all elements a1, , an in A, the function h preserves the operations of the algebras Specifically, when the operation is nullary (ni = 0), it follows that h(fk(0)) = fiB(0), indicating that the element produced by the nullary operation in algebra A is mapped to the corresponding element in algebra B.
If h is surjective (onto), then B is called homomorphic image of A
If the function h is bijective, that is both one-to-one (injective) and
"onto" (surjective), then the homomorphism h : A + B is called an isomorphism from A onto B An injective homomorphism from
A into B is also called an embedding of A into B
A homomorphism h : A + A of an algebra A into itself is called an endomorphism of A, and an isomorphism h : A + A from A onto A is called an automorphism of A
It is easy t o see that the image B1 = h(A1) of a subalgebra Al of
A under the homomorphism h is a subalgebra of B and that the preimage hpl(B') = A' of a subalgebra B' of h(A) C B is a sub- algebra of A
If X c A is a subset of the universe of an algebra A of type 7 , if (X)A is the subalgebra of A generated by X and if h : A + B is a homomorphism, then
If especially X is a generating system of A and if h : A + B is surjective, then h ( X ) generates B since
Direct and Subdirect Products
Later on we need the sublattice Coni,,(A) of all fully invariant congruence relations on A
Definition 1.1.15 Let A be an algebra of type 7 A congruence re- lation 8 E C o n ( A ) is called fully invariant if for all endomorphisms cp : A + A we have
The congruence relations AA and VA are always fully invariant
Proposition 1.1.16 T h e set Coni,,(A) of all fully invariant con- gruence relations of A forms a sublattice of C o n ( A )
This section explores the significant concept of product algebras, highlighting that subalgebras or homomorphic images of a given algebra cannot exceed its cardinality In contrast, the formation of products can result in algebras with greater cardinalities than the original We begin by examining the direct product of a family of algebras.
Definition 1.2.1 Let be a family of algebras of type r The direct product n Slj of the Slj is defined as an algebra with
12 1 Basic Concepts and the operations for a,, , ant in P ; that is,
In mathematical notation, if for every element j in set J, the set Aj is equal to A, we typically denote this as AJ instead of using n 4 When J is an empty set (J = 0), A0 is defined as the trivial one-element algebra of type r Additionally, for a finite set J = {1, , n}, the direct product of the algebras can be expressed as A1 × A2 × × An.
The projections of the direct product n A j are the mappings j t J pk : n Aj + Ale defined by (aj) j t J ah- j t J
It is easy to check that the projections of the direct product are in fact surjective homomorphisms
We recall the definition of the product (composition) Q1 o Q2 of two binary relations Q1, 82 on any set A:
Two binary relations Q1,Q2 on A are called permutable, if
In examining the direct product of two factors, we identify two projection mappings, \( p_1 \) and \( p_2 \), each possessing a kernel that represents a congruence relation on the product As homomorphisms, \( p_1 \) and \( p_2 \) exhibit unique properties within their respective kernels.
Lemma 1.2.2 Let A1, A 2 be two algebras of type T and let A l x A2 be their direct product Then:
(ii) ker pl o ker p2 = ker p2 o ker pl;
This lemma motivates the following definition:
Definition 1.2.3 A congruence 8 on A is called a factor congru- ence if there is a congruence 8' on A such that
The pair (8,8') is called a pair of factor congruences on A
Theorem 1.2.4 If (8,Q') i s a pair of factor congruences, t h e n A i s isomorphic w i t h t h e direct product A/8 x A/8' (A " A/8 x A/V) u n d e r t h e i s o m o r p h i s m given by a H ([ale, [ale!)
Definition 1.2.5 An algebra A is called directly indecompos- able, if whenever A " B1 x B2, either lBll = 1 or IB21 = 1
There is only one non-trivial directly indecomposable Boolean algebra, which is the two-element Boolean algebra Cardinality considerations indicate that a countably infinite Boolean algebra cannot be isomorphic to a direct product of directly indecomposable algebras However, this restriction does not apply to finite algebras.
Theorem 1.2.6 E v e r y finite algebra A i s isomorphic t o a direct product of directly indecomposable algebras
This can be proved by induction on the cardinality of A Our con- sideration shows that directly indecomposable algebras are not the
"general building blocks" in the study of universal algebra There- fore, we define another kind of products
Definition 1.2.7 Let (Aj)j,J be a family of algebras of type T A subalgebra B c n Aj of the direct product of the algebras Aj is
I € J called a subdirect product of the algebras Aj, if for every projection mapping pk : n Slj + Ak we have jeJ pk(B) = Ak
Subdirect products include examples such as the diagonal AA = {(a, a) | a ∈ A} and any direct product The Hasse diagram illustrates the lattice structure formed by the direct product of the two-element lattice C2 and the three-element lattice C3.
The sublattice C C C2 x C3 which is described by the diagram l ( 4 3 ) is obviously a subdirect product of C2 and Cj
It can easily be checked that for the subdirect product B = Aj j E J of the family ( A j ) j E J the projection mappings p k : n Aj + Ak j E J
Direct and subdirect products are defined by the equation n k e r ( p j I B) = AB This characteristic of the kernels in projection mappings is instrumental in defining subdirect products, as any set of congruences on an algebra that possesses these properties can be utilized to represent the algebra as a subdirect product.
Theorem 1.2.8 Let A be a n algebra Let { Q j I j E J } be a family of congruence relations o n A, which satisfy the equation n Q j =
AA T h e n A i s isomorphic t o a subdirect product of the -algebras A/Bj, for j t J I n particular, the mapping ~ ( a ) := ( [ a ] Q i ) j t J de- fines a n embedding cp : A + n ( A / Q j ) , whose image p(A) i s a j € J subdirect product of the algebras A / Q j
The converse of this theorem holds true; if A is isomorphic to a subdirect product of a family of algebras (A_j), then there exists a set of congruence relations on A whose intersection results in the relation AA.
Algebras which cannot be expressed as a subdirect product of other smaller algebras, except in trivial ways, are called subdirectly irre- ducible
An algebra A of type r is defined as subdirectly irreducible if, for any family of congruences {Qj | j ∈ J} on A, where none of the congruences equals the universal congruence AA, the intersection of these congruences is not equal to the universal congruence.
AA In this case, the conditions of Theorem 1.2.8 are not satisfied, and no representation of A as a subdirect product is possible
An algebra A is classified as subdirectly irreducible if and only if its congruence lattice Con(A) contains precisely one upper neighbor or cover in the relation AA Consequently, the structure of the congruence lattice can be represented as illustrated in the accompanying diagram.
Subdirect products do have the right property to act as the "general building blocks" in the study of universal algebra, as the following result of G Birkhoff ( [ 8 ] ) shows
Theorem 1.2.10 Every algebra is isomorphic to a subdirect prod- uct of subdirectly irreducible algebras.
Term Algebras, Identities Free Algebras
To effectively describe classes of algebras using logical expressions, an appropriate formal language is essential This language comprises variables from an n-element set X = {x₁, , xₙ}, where n > 1, referred to as the alphabet Additionally, a set of operation symbols {fᵢ | i ∈ I} is required, with the stipulation that the sets X and {fᵢ | i ∈ I} remain disjoint Each operation symbol fᵢ is assigned a natural number nᵢ > 1, known as its arity, and the sequence r = (nᵢ)ᵢ∈I defines the type of the language Consequently, we can establish the terms of our type r, which represent the "words" of our language.
Definition 1.3.1 Let n > I The n-ary terms of type r are defined in the following inductive way:
(i) Every variable xi E X, is an n-ary term
(ii) If t l , , tni are n-ary terms and fi is an ni-ary operation symbol, then fi (tl, , tni) is an n-ary term
(iii) The set W,(X,) = W,(xl, , x,) of all n-ary terms is the smallest set which contains x l , , x, and is closed under fi- nite application of (ii)
It follows immediately from the definition that every n-ary term is also k-ary, for k > n
Our current definition excludes nullary terms; however, we could modify it by introducing a fourth condition to the inductive definition, which would specify that each nullary operation symbol within our framework is considered an n-ary term.
We could also extend our language t o include a third set of symbols, to be used as constants or nullary terms
1.3 Term Algebras, Identities, Free Algebras 17
Our definition of terms is inductive, based on the number op(t) of occurrences of operation symbols in a term The operation symbol count op(t) is also inductively defined by
(i) op(xi) := 0, if xi EX,,
(ii) op(fi(t1, ,t,%)) := C op(tj) + 1 j=1
To determine op(t) is one of the methods t o measure the complexity of a term Another common complexity measure is the depth of a term defined by the following steps:
(ii) depth(fi(t1, , t,,)) := max{depth(tl), , depth(t,,)} + 1
In a similar way the mindepth of a term can be defined if we replace the second step of the definition of depth by mindepth(fi(tl, , t,,)) := min{depth(tl), , depth(t,%)} + 1
Terms can be illustrated by tree diagrams, also called semantic trees The semantic tree of the term t is defined as follows:
(i) If t = xi, then the semantic tree of t consists only of one vertex which is labelled with xi, and this vertex is called the root of the tree
In a semantic tree where t is defined as f i (t l, , t n), the root vertex is labeled with f i and is connected by ni edges Each edge corresponds to the root of a tree associated with one of the terms t l through t n, arranged in order from 1 to ni, starting from the left.
As an example we show the diagram of the term
18 1 Basic Concepts where f 2 is a binary and f l is a unary operation symbol
In the diagram mindepth(t) is the length of the shortest path from the root to a leaf and depth(t) is the length of the longest path from the root t o a leaf
Additional complexity measures include the length of the shortest path from the root to a leaf labeled by variable \( z_j \) and the length of the longest path to a leaf labeled by \( x_j \) These metrics, referred to as \( depth_j(t) \) and \( mindepth_j(t) \), are defined inductively.
(i) depthj(t) = mindepthj(t) := 0, if t = xi or x j does not occur in t ,
(ii) depthj (fi(t17 , k t ) ) := max{depthj (tl), , depthj (tni)} + 1 mindepthj (fi(t1, , t,,)) := min{depthj ( t l ) , , depthj (t,,)) + I if zj occurs in fi(tl, , t,,)
We also use the following subset of W,(X,):
Definition 1.3.2 Let n > 1 and let s : ( 1 , , n ) + ( 1 , , n ) be a mapping on { I , , n) Then n-ary full terms of type r are defined as follows:
(i) For every function s the term f i ( ~ , ( ~ ) , , x,(,)) is full (ii) If t l , , t,, are full terms, then fi (t l , , t,,) is full
1.3 Term Algebras, Identities, Free Algebras 19
In the context of n-ary terms, if 's' represents the identity mapping, the terms are classified as strongly full; conversely, if 's' is a permutation, they are termed permutationally full We denote the sets of all full, strongly full, and permutationally full n-ary terms of type 'r' as W(Xn), WSF(Xn), and WFF(Xn), respectively.
Let r represent a fixed type, and let X denote the union of all variable sets, expressed as X = {x1, x2, } We define W_r(X) as the collection of all terms of type r constructed over the countably infinite alphabet X.
This set W,(X) can be used as the universe of an algebra, of type r when for every i E I we define an ni-ary operation f , on W,(X), with fi : W,(X)n2 + W,(X) with ( t l , , tni) H f i ( t l , , tn,)
Definition 1.3.3 The algebra F,(X) := (W,(X); is called the term algebra, or the absolutely free algebra, or the anarchic algebra of type r over the set X
The term algebra F,(X) is generated by the set X and has the so- called "absolute freeness" property, meaning that for every algebra
A E Alg(r) and every mapping f : X + A, there exists a unique homomorphism f : F,(X) + A which extends the mapping f and such that f o y = f , where 9 : X + F,(X) is the embedding of X into F,(X) This can be illustrated by the following diagram:
Absolutely free algebras F(X) and F(Y) are isomorphic when X and Y share the same cardinality, allowing us to utilize different symbols for our variables.
2 0 1 Basic Concepts x, y , we may also use X I , 2 2 , In the case of the finite alphabet
In algebra FT(X), we explore all n-ary terms of type r, where operation symbols are utilized to define operations f on W(X) Additionally, there exists an alternative method to define operations within this set.
Definition 1.3.4 Let W,(X,) be the set of all n-ary terms of type
7 Then the ( n + 1)-ary superposition operation Sn (for terms) is inductively defined by the following steps:
(i) If x j E X, is a variable and t l , , t, E W, (X,), then
Instead of S n ( t , tl , , t,) we also write t ( t l , , t,)
Selecting the variable terms x l , , x, for the nullary operations, we form the algebra n - clone r := (W,(X,); S n , x l , ,x,), which is an example of a unitary Menger algebra of rank n and will be considered later
An algebra with similar properties can be obtained if we define a superposition operation for n-ary operations on a set A We consider the set O(A) of all finitary operations on A
Definition 1.3.5 Let On(A), n > 1, be the set of all n-ary oper- ations defined on the set A Then the (n + 1)-ary superposition operation (for operations) SnlA : On(A),+l + On(A) is defined by
S n l A ( f A , g f , , g t ) ( a 1 , ,a,) := f (g1 ( a , 7 a,), , g:(al, , a,)) for every ( a l , , a,) E An Here g p , , g, A , as well as f A are n-ary This can be generalized t o an operation
1.3 Term Algebras, Identities, Free Algebras
The set O(A) is closed under these operations Particular operations on On(A) are the projections eyl", mapping each n-tuple of elements from A t o the i-th component, that is, with e:lA (al, , a n ) := a,
A clone of operations aims to comprehend a subset of O(A) that remains closed under all operations S2A, where m and n belong to W+ (the set of positive integers) This subset also encompasses all projections The term O(A) refers to the full clone of operations defined on the set A For brevity, we will denote SzA as s">A.
Definition 1.3.6 Let C c O(A) be a set of operations on a set
A Then the clone generated b y C, denoted by (C), is the smallest subset of O(A) which contains C, is closed under composition, and contains all the projections e:'" : An + A for arbitrary n > 1 and l < i < n
Terms are formal expressions on our formal language of type r
To determine the truth value of equations within a specific algebraic structure A, we must evaluate the variables in the equations using elements from the set A and interpret the operation symbols as concrete operations applicable to this set This process is analogous to constructing a rational function n from a polynomial f(x) = C aixi over a ring R by substituting each variable x with elements from an overring S that contains R.
In the context of algebra, if A is an algebra of type r and t is an n-ary term of the same type over the set Xn, then the term t induces an n-ary operation, denoted as tA, on the algebra A This operation is referred to as the term operation induced by the term t on the algebra A.
(ii) If t = fi(tl, , tni) is an n-ary term of type 7 , and t f , , ttt are the term operations which are induced by t l , , t n i , then tA = s n i , A ( f A t k , i f t )
We denote by w,(x,)* the set of all n-ary term operations of the algebra A, and by w,(x)* the set of all (finitary) term operations
In the study of algebraic structures, the clone generated by the fundamental operations of a given algebra A is denoted as w(x)~, which corresponds to the notation T(A) This clone, referred to as the clone of term operations of A, encompasses all possible operations that can be derived from the basic operations of A Additionally, we define the set Tn(A) to represent a specific subset of these term operations.
On(A) n T(A) of all n-ary term operations on A
The fundamental operations of an algebra A share several properties with term operations Specifically, for a homomorphism h: A + B and any n-ary term t of the appropriate type, the relationship h(tA(a1, , an)) = tB(h(a1), , h(an)) holds true.
In the context of a congruence relation on algebraic structure A, the implications outlined in Definition 1.1.9 hold true for any n-ary term operations of A Moreover, the universes of subalgebras are preserved by all fundamental operations and term operations of A.
An equation s = t, where s and t are terms from W,(X), is defined as an identity in an algebra A of type r if the term operations induced by s and t on A are equal, denoted as sA = tA In this context, the equation is considered satisfied or modeled by the algebra A, represented as A ⊨ s = t If the equation holds true for every algebra A within a class K of algebras of the same type r, we denote this as K ⊨ s = t Additionally, let I_d(A) represent the set of all identities satisfied in the algebra A, and if K is a subset of Alg(r), it indicates a specific class of algebras.
I d K denotes the set of all equations which are identities in every algebra of K
The Galois Connection ( I d Mod)
The satisfaction of an equation by an algebra gives us a fundamental relation between the two sets Alg(7) and W , ( X ) 2 For any subset
C c W , ( X ) 2 and any subclass K c A l g ( r ) we consider
Then the pair ( I d , Mod) where Id maps from the power set of
W , ( X ) 2 into the power set of Alg(7) and Mod maps conversely from the power set of Alg(7) into the power set of W , ( X ) 2 sa'tisfies the following conditions
Theorem 1.4.1 (i) For all subsets C and C' of W , ( X ) x W , ( X ) , and for all subclasses K and K' of A l g ( r ) , we have
(ii) For all subsets C of W , ( X ) x W , ( X ) and all subclasses K of
(iii) The maps IdMod and ModId are closure operators on
The sets that are closed under ModId correspond precisely to those of the form ModC, where C is a subset of W, while the sets closed under IdMod are specifically of the form IdK, for some K.
A pair of mappings which satisfies (i) and (ii) is called a Galois connection
An equational class, denoted as K C Alg(7), is defined by the existence of a set C of equations such that K equals ModC Additionally, a set C within W,(X) x W,(X) is referred to as an equational theory if there exists a class K within Alg(r) for which C is equivalent to Id K.
According to Theorem 1.4.1 (iv), equational classes correspond to the fixed points of the closure operator ModId, while equational theories represent the closed sets or fixed points of the closure operator IdMod These collections of closed sets are organized into complete lattices.
Theorem 1.4.3 states that the collection of all equational classes of type T forms a complete lattice denoted as C(T), while the collection of all equational theories of type 7 forms another complete lattice represented as &(7) These two lattices are dually isomorphic, meaning there exists a bijection ϕ: C(7) → &(7) that satisfies the conditions ϕ(K1 ∨ K2) = ϕ(K1) ∧ ϕ(K2) and ϕ(K1 ∧ K2) = ϕ(K1) ∨ ϕ(K2).
The theorem's proof is detailed in [37], and the Galois connection (Id, Mod) provides an equational framework for describing algebra classes By introducing the operators H, S, and P, which represent homomorphic images, subalgebras, and direct products respectively, we establish an equivalent algebraic perspective.
Definition 1.4.4 We define for any class K C Alg(7) the follow- ing operators on the class Alg(r) of all algebras of type T
S ( K ) is the class of all subalgebras of algebras from K ,
H ( K ) is the class of all homomorphic images of algebras from K ,
P ( K ) is the class of all direct products of families of algebras from
I ( K ) is the class of all algebras which are isomorphic t o algebras from K ,
P s ( K ) is the class of all subdirect products of families of algebras from K
Definition 1.4.5 A class K C Alg(r) is called a variety if K is closed under the operators H, S and P; that is, if H ( K ) C K ,
For any class K of algebras of type r , the class V ( K ) : = H S P ( K ) is the least variety which contains K If K = {A) consists only of one algebra we write V(A) := HSP({A))
With these definitions we can formulate the main theorem of equa- tional theory, also called Birkhofl's Theorem
T h e o r e m 1.4.6 (Main Theorem of Equational Theory) A class K of algebras of type r is equationally definable if and only if it is a variety
To thoroughly describe all members of a variety, two key methods can be employed The first method involves utilizing all subdirectly irreducible algebras within the variety, highlighting that every algebra in a variety V can be represented as a subdirect product of these subdirectly irreducible algebras.
The second way uses all relatively free algebras F v ( X n ) for arbi- trary natural numbers n > 1 and the fact that
Here the question arises whether the free algebras F v ( X n ) are finite
A variety V is said to be locally finite if every finitely generated algebra in V is finite This is the case iff all free algebras F v ( X n ) are finite
All equational classes of algebras of the same type \( r \) form a complete lattice, denoted as \( C(r) \), which encompasses all varieties of type \( r \) as established by Theorem 1.4.6 Notably, these lattices are algebraic in nature, with the variety \( Alg(7) \) representing the greatest element of the lattice \( C(r) \), comprising all algebras of type \( r \).
7 Clearly, Alg(r) = Mod{x = x) The least element in the lattice
The trivial variety C(r) is defined as the variety T, which comprises all one-element algebras of type r, represented by the equation T = Mod{x = y} In contrast, the greatest element within the lattice I(r), which encompasses all equational theories of type r, plays a significant role in understanding the structure of these theories.
1.4 The Galois Connection ( I d , Mod) 27 equational theory generated by {x = y}, and the least element in
I ( r ) is the equational theory generated by {x = x} Clearly, the first one consists of all equations of type r
A subclass W of a variety V that is also a variety is termed a subvariety of V A variety V is considered minimal or equationally complete if it is nontrivial and the only subvariety of V that is not equal to V itself is the trivial variety It can be demonstrated that every nontrivial variety possesses this property.
If V is a given variety of type r, then the collection of all subva- rieties of V forms a complete lattice C(V) := {WI W E C ( r ) and
W c V) This lattice is called the subvariety lattice of V One of the aims of this book is to present new methods t o study the lattice L(r) or lattices of the form L(V)
Equational theories are defined as sets of equations C that satisfy the condition IdModC = C According to Theorem 1.4.l(iv), a set C qualifies as an equational theory of type r if there exists a class K of algebras of type r such that C equals Id K Additionally, sets of equations represented as Id K are fully invariant congruence relations on the absolutely free algebra F T (X) of type r, as established in Theorem 1.3.10.
A fully invariant congruence relation establishes the algebraic consequence relation, which provides a formal method for deriving new equations from a given set of identities in a class of algebras We denote this relationship as C ⊢ s = t, meaning "C yields s = t," indicating that there is a formal deduction of s = t based on the identities in C This deduction utilizes five fundamental rules of consequence, derivation, or deduction.
(4) {tj = t i 1 1 5 j 5 ni) t f i ( t l , , tn,) = fi(t;, , t i i ) , for every operation symbol fi ( i E I) (the replacement rule)
(5) Let s, t , r E W,(X) and let 5, t" be the terms obtained from s, t by replacing every occurrence of a given variable x E X by r Then {s = t} t 5 = t" (This is called the substitution rule.)
The rules (I) - (5) define a fully invariant congruence relation, with the first three rules representing the properties of an equivalence relation, the fourth outlining the congruence property, and the fifth emphasizing the fully invariant aspect Equational theories C consist of sets of equations that remain closed under the finite application of these rules.
In the context of a set C within W,(X)2, the equation C + s = t indicates that s = t holds true as an identity across all algebras A of type T, where every equation from set C is also satisfied as an identity.
The connection between these approaches is given by the Com- pleteness and Consistency Theorem of equational logic: For C C
The "+"-direction of this theorem is usually called completeness, since it means that any equation which is "true" is derivable; the
"en -direction is called consistency, in the sense that every derivable equation is "true"
The complete lattice formed by all varieties of a specific type is crucial in Universal Algebra and its applications, yet studying these lattices can be challenging To facilitate this study, we seek new approaches and tools, one of which involves examining smaller sections of the complex lattice By focusing on complete sublattices that share the same algebraic structure, we can gain valuable insights into the overall properties of the complete lattice.
Closure Operators and Kernel Operators
In the previous chapter, we explored two examples of operators characterized by closure properties Specifically, we examined how the creation of subalgebras from subsets X of the carrier set A of a given algebra A defines a distinct operator.
( ) A : ?(A) + ? ( A ) on the power set of A, which is extensive, monotone and idempo- tent The generation of congruence relations by a binary relation defines an operator
( ) C ~ A : ?(A2) + ?(A2) which also has these three properties We define:
Definition 2.1.1 Let A be a set A mapping C : ?(A) + ?(A) is called a closure operator on A, if for all subsets X, Y c A the following properties are satisfied:
Subsets of A of the form C ( X ) are called closed (with respect to the operator C ) and C(X) is said to be the closed set generated by
An operator K : P ( A ) + P ( A ) is said t o be a kernel operator on A, if it is monotone and idempotent and if instead of (i) the condition
Closure and kernel operators are closely related t o complete lattices Indeed, if C : P ( A ) + P ( A ) is a closure operator, then the set
Cc := {X I X c A and C(X) = X ) (1) is a complete lattice with respect to the operations defined by for arbitrary sets X , Y E Cc since X n Y E LC whenever X, Y E LC and v : LC x LC + LC defined by
In the context of arbitrary families of elements from LC, both A X j and V X j belong to LC Each closure operator C on A thus defines a subset of ?(A), which forms a complete lattice Conversely, if C is a complete lattice within P(A), then for every subset Y in A, a closure operator CL can be established from P(A) to P(A) The closed sets defined by CL correspond precisely to the elements of C, establishing a one-to-one relationship between complete lattices.
P ( A ) and closure operators on A Altogether we have the following well-known theorem.
Complete Sublattices of a Complete Lattice
Theorem 2.1.2 establishes that if C is a complete lattice within P(A) and C serves as a closure operator on the set A, then Cc, defined by a specific equation, forms a complete lattice with operations outlined in additional equations Furthermore, CL, defined by another equation, acts as a closure operator on A Notably, the closed sets associated with CL correspond precisely to the elements of C, while the elements of Cc represent the closed sets of C.
CL, = C and LC, = C are satisfied
There is a similar connection between kernel operators on A and complete lattices in P ( A ) In this case instead of (4) we have to define
The image CL(Y) represents the infimum of all elements in C that contain Y, while K L(Y) denotes the supremum of all elements from C that are contained within Y The partially ordered set (?(A); c) forms a complete lattice based on the intersection and union of arbitrary families of subsets of A However, as demonstrated by the examples Sub(A) and Con(A), the complete lattices Cc are generally not complete sublattices of (P(A); C) since the join operation does not equate to the set-theoretical union In the following section, we will present a condition that characterizes complete sublattices within a complete lattice.
2.2 Complete Sublattices of a Com- plete Lattice
This section outlines a method for generating complete sub-lattices from a specified complete lattice by examining the fixed points of particular closure operators defined within the lattice.
In 2.1 we showed that the fixed points of a closure operator
In the context of complete lattices, the relationship between a complete lattice C and the power set lattice P(A) illustrates that C can be represented as a closure operator on the set A Furthermore, this concept can be extended to include any arbitrary complete lattice C, demonstrating that each complete lattice in P(A) uniquely defines a closure operator on A.
3 2 2 Closure Operators and Lattices any closure operator p : C + C 7 we get the complete lattice
S, := F i x (p) := {T I cp (T) = T} of all fixed points of p; and for any complete lattice S C C we have the closure operator ps defined by
(Here < denotes the partial order of C 7 A is the infimum and V the supremum with respect to 5.) Moreover, for any complete lattice
S in C and any closure operator p, we have S,, = S and ps,, = p
The set S, is also called a closure system
There is also a dual 1-1 correspondence between kernel operators and complete lattices in C For a kernel operator $ : C + C and a complete lattice C, we set
Then we have Fix($) = S$ and $sy = $, for any complete lattice
S and any kernel operator $ on C These results date back t o A Tarski ([97])
Theorem 2.2.1 Let C be a complete lattice
(i) If p is a closure operator o n C which satisfies for every index set J , then the set of all fixed points under p,
S, = {T E C I p(T) = T), is a complete sublattice of C and cp(C) = {p(T) I T E C} = s,
(ii) Conversely, if S is a complete sublattice of C, then the func- tion cps which is defined by is a closure operator o n C with ps(C) = S , and ps satisfies condition (*) Moreover, S,, = S and cps,, = p
2.2 Complete Sublattices of a Complete Lattice
(iii) If $ is a kernel operator o n C which satisfies for every index set J , then the set of all fixed points under $, is a complete sublattice of C and $(C) = S$
(iv) Conversely, if S is a complete sublattice of C then the function which is defined by
$s(T) := V{T' t S 1 T' 5 T} for T t C, is a kernel operator o n C with $S(C) = S, and $ satisfies the condition (**) Moreover, S+, = S and qs, = $
To demonstrate that the set of all fixed points under the closure operator cp on C forms a complete sublattice, we need to establish that it satisfies the necessary conditions for any index set J This proof hinges on the properties of cp, particularly its adherence to the specified condition (*), which ensures that the fixed points maintain the structure required for a complete sublattice within C.
It is clear that p(A{Tj t S, I j E J)) > i { T , E S, 1 j t J ) For
L each j t J we have T, = cp(Tj) > cp(l\{T, E S, I j E J)), and
L L from this we obtain A{T, E S, I j E J) > cp(A{T, t S, I j t J ) )
Altogether this gives equality, and A{Tj L E S, I j E J) E S,
The fact that cp satisfies the join condition (*) gives V{Tj L E S, I j t J) t S, Thus we have a sublattice of C Clearly, S, c cp(C)
Since cp is idempotent, cp(T) is in S, for all T E C This shows that cpK> = s,
(ii) It is easy t o see that cps is a closure operator We need only show that this closure operator satisfies condition (*) and that cps(C) =
S We prove the latter fact first Since S is a complete sublattice of
L, we have cps(L) C S For the opposite inclusion, we see that for any T E S
Thus S C cps (L), and altogether we have S = cps (L) Since for each j t J we have T, < cps(Tj) and cps(T,) E S, the set is an upper bound of the set {Tj I j E J} Therefore
The right hand side is an element of S By application of cps on both sides we get
Since V{Tj I j E J) > T', we have cps(V{Tj I j E J)) > cps(T,) for
L C all j E J Thus also cps(V{T, I j E J)) > V{cps(Tj) I j E J), giving the required equality
(iii) and (iv) can be proved similar to (i) and (ii)
The equations are also easy to realize.
Galois Connections and Complete Lattices
In Chapter I, we explored the Galois connection between identities and model classes, represented as (Id, Mod) This concept is further generalized by examining Galois connections as pairs of mappings that possess unique properties between the power sets of two distinct sets.
Definition 2.3.1 A Galois connection between the sets A and B is a pair (p, L ) of mappings between the power sets P ( A ) and P(B), p : P ( A ) + P ( B ) and L : P ( B ) + P ( A ) ,
2.3 Galois Connections and Complete Lattices 3 5 such that for all T, T' C A and all S, St C B the following condi- tions are satisfied:
Galois connections are also related t o closure operators, as the fol- lowing proposition shows
Theorem 2.3.2 Let the pair ( p , L ) with p : P ( A ) + P ( B ) and L : P ( B ) + P ( A ) be a Galois connection between the sets A and B Then:
(ii) ~p and p~ are closure operators o n A and B respectively;
(iii) The sets closed under ~p are precisely the sets of the form
L(S), for some S C B; the sets closed under p~ are precisely the sets of the form p ( T ) , for some T C A
The proof begins with the assertion that T A, which leads to the conclusion that T C L ~ ( T ) based on the second Galois connection property By applying the first property, we derive that p ( T ) is greater than p ~ p ( T ) Additionally, it follows from the second Galois connection property applied to the set p ( T ) that p ( T ) is contained within p ~ ( p ( T ) ) Consequently, we establish that p ~ p ( T ) equals p ( T ) A similar approach can be utilized to prove the second claim.
The extensivity of the operations ~p and p~ is derived from the second Galois connection property It is evident that p(T) and p(Tt) are subsets of B, leading to the conclusion that ~L(S) is included in p(St) based on the relationship S ⊆ St By applying p to the equation L~ = LL from the first property, we establish the idempotency of p~, which similarly applies to ~p.
(iii) This is straightforward to verify
Galois connections are " induced " by relations A relation between the sets A and B is simply a subset of A x B Any relation R
3 6 2 Closure Operators and Lattices between A and B induces a Galois connection, as follows We can define the mappings
We confirm that the pair (pR, L) constitutes a Galois connection Specifically, if T is a subset of T1 and y belongs to pR(T1), meaning that for every x in T1, the relation (z, y) is in R, then for all z in T, the relation (x, y) also holds in R, which implies that y is in pR(T) This demonstrates that pR(T1) is a subset of pR(T) A similar proof can be applied to establish the second condition from Definition 2.3.1 (i).
It is easy to see that T C L R ~ R ( T ) and S ~ R L R ( S )
If conversely (p, L ) is a Galois connection between A and B then we construct the relation
T L A and the Galois connection (pn , p , L ) , LR(,,,,, ) defined by
It turns out that (pn(,,,,, , Ln (p,,)) = (p, L) Therefore, there is a one- to-one correspondence between relations between A and B and Ga- lois connections between A and B
We need also the following well-known proposition (see e.g [37], exercise 2.4.2):
Lemma 2.3.3 Let R C A x B be a relation between the sets A and
B and let ( p , L ) be the Galois connection between A and B induced by R T h e n for any families {T, C A I j E J) and {Sj B I j E
Galois Closed Subrelations
In section 2.2 we developed a method to produce complete sublat- tices of a given complete lattice If R C A x B is a relation between two sets A and B and if (p, L) is the Galois connection induced by
In the context of a relation R, the fixed points of the closure operators p~ and ~p establish two complete lattices that are dually isomorphic By examining a subrelation R' of R, we can derive a new Galois connection and corresponding complete lattices A key characteristic of the subrelation R', known as the Galois closed subrelation property, ensures that these new complete lattices will be complete sublattices of the original lattices Furthermore, it is demonstrated that all complete sublattices of the original lattices can be generated through this process.
Definition 2.4.1 Let R and R' be relations between sets A and
B, and let (p, L ) and (p', L') be the Galois connections between A and B induced by R and R', respectively The relation R' is called a Galois closed subrelation of R if:
The following equivalent characterizations of Galois closed subrela- tions can easily be derived (see e.g [45], [4])
Proposition 2.4.2 Let R' c R be relations between sets A and B
(i) R' is a Galois closed subrelation of R;
(ii) For any T c A, if L ' ~ ' ( T ) = T then p ( T ) = p t ( T ) , and for any S C B , if ~ ' L ' ( S ) = S then L(S) = L'(S);
(iii) For all T C A and for all S C B the equations L ' ~ ' ( T ) =
Proof: (i) + (ii) Define S to be the set pt(T) Then from L ' ~ ' ( T ) =
T, i.e L'(S) = T and p' (T) = S by the definition of a Galois closed subrelation we obtain p ( T ) = S and L(S) = T, i.e p ( T ) = pt(T)
3 8 2 Closure Operators and Lattices and L(S) = L'(S) The claim for subsets S of B can be proved sim- ilarly
(ii) + (iii) From p'~'p'(T) = p t ( T ) and L'~'L'(S) = L'(S) (Propo- sition 2.3.2) using (ii) we obtain ~ L ' ( S ) = ~ ' L ' ( S ) and L ~ ' ( T ) =
(iii) + (i) If p t ( T ) = S and L'(S) = T, then there follows:
Then by condition (iii) we get p ( T ) = p t ( T ) = S and L(S) = L'(S) = T
This shows that R' is a Galois closed subrelation of R
In this article, we explore the complete lattices generated by the Galois connection (p, L), denoted as 'Ft,, and 'Ft,, We demonstrate that any Galois closed subrelation R' of the relation R results in a lattice of closed subsets of A, forming a complete sublattice of the corresponding lattice E L for R Additionally, we establish that any complete sublattice of the lattice can be derived from this framework, highlighting the interconnectedness of Galois relations and lattice structures.
E L , occurs as the lattice of closed sets induced from some Galois closed subrelation of R Dual results of course hold for the set B
Theorem 2.4.3 Let R C A x B be a relation between sets A and B , with induced Galois connection (p, L) Let E,, be the corresponding lattice of closed subsets of A
(i) I f R' c A x B is a Galois closed subrelation of R, t h e n the class URl := ' F t L 1 , t i s a complete sublattice of 'Ft,,
(ii) If U is a complete sublattice of EL,, t h e n the relation i s a Galois closed subrelation of R
(iii) For a n y Galois closed subrelation R' of R and a n y complete sublattice U of 'Ft,,, we have
To demonstrate that any subset of A closed under the operator ~ ' p ' is also closed under ~ p, we establish that the lattice E,I,I is a subset of EL Specifically, if T belongs to E,I,I, then it follows that this closure property holds.
L ' ~ ' ( T ) = T, then by Proposition 2.4.2, we have
L p (T) = L p' (T) = ~ ' p ' (T) = T and therefore, E,I,I C EL, Since by 2.1 the infimum in a com- plete lattice which is included in the power set lattice of a set is the set-theoretical intersection we have l\ {T, I j E J) = 0 Tj =
X L U I ~ J l\ {Tj I j t J} and this means, is closed under the infimum
Now we consider the join By repeated use of Lemma 2.3.3 and Proposition 2.4.2, we see that V {T, I j E J) = LIP'( U Tj) =
% / L J j E J j E J) and therefore K,I,I is closed under the supremum operation of EL,
(ii) Now let U be any complete sublattice of EL, We consider the relation
Ru := U {T x p ( T ) 1 T E U), which we will prove is a Galois closed subrelation of R First, for each non-empty T E U we have p ( T ) = {s E B I V t E T((t, s) E
To demonstrate that the second condition for a Galois closed subrelation is satisfied, we consider the Galois connection (p', L') established between sets A and B through Ru We assume that p'(T) equals S and that L'(S) corresponds to T for certain elements This relationship confirms the necessary criteria for the Galois closed subrelation.
T c A and S c B Our goal is to prove that p ( T ) = S and L(S) = T
Let T E U By definition we have
This means that p f ( T ) is the greatest subset of B with T x p f ( T ) C
Ru Now from the definition of Ru we have T x p ( T ) C Ru
Therefore, p ( T ) C p r ( T ) The opposite inclusion also holds since
Ru C R Altogether we have p f ( T ) = p ( T ) If p f ( T ) = S, then L(S) = L ~ ' ( T ) = L ~ ( T ) = T since T E U C EL,
For any complete sublattice U of 'FI,,, and any Galois closed subrelation R' of R, it holds that UR, = U and RuR, = R' This establishes that UR, corresponds to the lattice of subsets EL"/, demonstrating the relationship between sublattices and Galois closed subrelations.
A closed under the closure operator ~ ' p ' induced from the relation
In the context of Galois theory, if we let T be an element of the set U, we can demonstrate that T is also an element of the closure URu, as indicated by the relationship L' ~ ' (T) = T Furthermore, for any set S defined as p r (T), we find that L'(S) equals T Since Ru is recognized as a Galois closed subrelation of R, it follows that p(T) is equivalent to S, confirming that L(S) also equals T This establishes that U is contained within URu.
If T = 0 then T t U, and for T # 0 for each t E T we define
We can show that T = U Dt But now T = L ~ ( T ) = L P ( U D t ) = t € T t € T
U{Dt I t E T} E U This shows the other direction URu C U
Let R' be a Galois closed subrelation of R , and set
We will show that Ru,, = R' First, if (t, s) E R' then s E pf({t)) Setting S := pr({t)), we have s E S and L'(S) = ~'p'({t)) NOW tak- ing T : = ~'p'({t)), we have L ' ~ ' ( T ) = T, SO T t URt, p' (T) = S and L'(S) = T Therefore p ( T ) = S and L(S) = T Since t t ~'p'({t)) =
T and s E S = p ( T ) , we get (t, s) E T x p ( T ) and T E URl Hence (t, s) E RuR,, and we have shown that R' C RuR,
To show the opposite inclusion, let T t URI, and let S = p ( T ) Then we can prove p' (T) = p ( T ) = S and L'(S) = L(S) = L p ( T ) = T
Therefore T x p ( T ) c R', and Ru,, c R' Altogether, we have RuR, = R' This completes the proof of (iii), and of our theorem.
Conjugate Pairs of Additive Closure Operators
2.5 Conjugate Pairs of Additive Clo- sure Operators
In section 1 we saw that any closure operator y defined on a set A gives us a complete lattice, the lattice IFt, of all y-closed subsets of
In a lattice structure, the meet operation represents the intersection, while the join operation does not typically equate to the union However, there are specific conditions under which the join operation can be considered equivalent to the union.
Definition 2.5.1 A closure operator y defined on a set A is said to be completely additive if y ( T ) = U ?(a) for all T C A (Here a t T we write y ( a ) for y ({a)).)
When y is an additive closure operator, the least upper bound operation on the lattice IFt aligns with the upper bound (U B) This is due to the extensivity of y, which ensures that U B is a subset of y(U B) Furthermore, if an element a belongs to U B, it implies that a is part of some set B within B Given that B is an element of 'Ft, we establish that y(a) is a subset of U B, leading to the conclusion that y(U B) equals U y(a), which in turn equals U B.
In this context, U B is identified as y-closed, with V B equating to U B This indicates that when y serves as a completely additive closure operator on set A, the resulting closure system constitutes a complete sublattice within the lattice of all subsets of A, denoted as (P(A); 0, u) We will now explore scenarios involving two closely related completely additive closure operators, with relevant findings documented in sources [36] and [19].
Definition 2.5.2 Let yl be a closure operator defined on the set
A and let 7 2 be a closure operator defined on the set B Let R C
A x B be a relation between A and B Then yl and 7 2 are called conjugate with respect t o R if for all t E A and all s E B we have y ~ ( t ) x {s) c R iff {t) x y,(s) c R
When two operators are entirely additive, we can broaden the definition from individual elements to sets of elements Therefore, when (y1, y2) represents a pair of additive closure operators, this extension becomes applicable.
42 2 Closure Operators and Lattices yl on A and 7 2 on B, and they are conjugate with respect t o a relation R C A x B , then for all X C A and all Y C B we have
In this section, we will explore the general theory of conjugate pairs of additive closure operators, focusing on two sets, A and B Examples of these operators will be provided in the following chapter.
In the context of a relation R between sets A and B, a Galois connection (p, L) is established, where the mappings p~ and L,U function as closure operators Additionally, the pair (p~, ~p) is consistently conjugate to the original relation R.
L,LL need not be completely additive in general
Definition 2.5.3 Let y := (yl, y2) be a conjugate pair of com- pletely additive closure operators, with respect to a relation R C
A x B Let R, be the following relation between A and B:
Now we have two relations and Galois connections between A and
The relation R establishes a Galois connection (p, L) between sets A and B, while the new relation R creates an additional Galois connection, referred to as (p,, L,) The subsequent theorem outlines key properties that link these two Galois connections.
Theorem 2.5.4 Let y = (yl, y2) be a conjugate pair of completely additive closure operators w i t h respect t o R C A x B T h e n for all
2.5 Conjugate Pairs of Additive Closure Operators
Proof: We will prove only (i)-(v), the proofs of the other proposi- tions are dual
(ii) Since yl is a closure operator, we have T c y l ( T ) ; and thus, since p reverses inclusions, p(T) > p ( y l ( T ) ) Using (i) we obtain P,(T) C 4 9
(iii) Extensivity of y2 implies p,(T) C y2(p,(T)) Now let S C p, (T) Then for all s E S and for all t E T, (t, s) E R,, and by definition of R, we get {t} x y2(s) C R Idempotency of y2 gives {t} x y2(y2(s)) R and thus y2(s) C p,(T) for all s E S
By additivity of y2 we get y2(S) = U y2(s) c p,(T); and taking
S = p,(T) we obtain y2(p,(T)) C p, (T) Altogether we have the equality P, (TI = 7 2 (P, (T) )
The next theorem gives for sets T C A which are closed under ~ p , i.e with L ( ~ ( T ) ) = T four equivalent characterizations
Theorem 2.5.5 establishes the Main Theorem for Conjugate Pairs of Additive Closure Operators, focusing on a relation R between sets A and B, which is associated with a Galois connection (p, L) It states that for a conjugate pair of completely additive closure operators, denoted as y = (y1, y2), and for all subsets T of A where L(¬(T)) = T, specific properties hold true.
44 2 Closure Operators and Lattices propositions (i) - (iv) are equivalent; and dually, for all sets S C B with ~ ( L ( S ) ) = S , propositions (i') - (iv') are equivalent:
Proof: We prove the equivalence of (i), (ii), (iii) and (iv) ; the equiv- alence of the four dual statements can be proved dually
(i) + (ii) We always have T C y l ( T ) , since yl is a closure operator Since ~p is a closure operator we also have y l ( T ) C ~ p ( y ~ ( T ) ) = Lr(pr(T)) = T, by Theorem 2.5.4 (v')
(ii) + (iii) We have p ( T ) = p ( y l ( T ) ) = p,(T) by (ii) and Theorem 2.5.4 (i)
(iii) + (iv) We have 7 2 ( p ( T ) ) = 7 2 (p, (T)) = p, (T), using Theorem 2.5.4 (iii)
(iv) + (i) Since the ~,p,-closed sets are exactly the sets of the form
L ~ ( S ) , we have to find a set S C B with T = L ~ ( S ) But we ham l y ( p ( T ) ) = ~ ( 7 2 ( p ( T ) ) ) = L ( ~ ( T ) ) = T, by Theorem 2.5.4 (i7) and our assumption that T is ~p-closed
Before using this Main Theorem t o produce our complete sublat- tices, we need the following additional properties
Theorem 2.5.6 Let R be a relation between sets A and B , with Galois connection (p, L) Let y = (yl,y2) be a conjugate pair of
2.5 Conjugate Pairs of Additive Closure Operators 45 completely additive closure operators with respect to R T h e n for all sets T C A and S C B , the following properties hold:
Proof: We prove only (i7) and (ii'); the others are dual
(i') Suppose that y2(S) C ~ ( L ( S ) ) Since p~ is a closure operator we have P(@)) = P(L(P(L(S)))) 2 P(L(YZ(S))) = P,(L,(S)), by Our assumption and by Theorem 2.5.4 (v) Also S c y2(S), and hence we have ~ ( L ( S ) ) C p ( ~ ( y ~ ( S ) ) ) = p , ( ~ , ( s ) ) , again by Theorem 2.5.4 (v) For the converse we have y2(S) C p ( ~ ( y ~ ( S ) ) ) = p , ( ~ , ( s ) ) =
~ ( L ( S ) ) , using the extensivity of p ~ , Theorem 2.5.4 (v) and our as- sumption
Y ~ ( P ( L ( Y ~ ( S ) ) ) ) We also have 7 2 ( ~ ( ~ ( 7 2 ( S ) ) ) ) = ~ ~ ( P ( L , ( S ) ) ) by Theorem 2.5.4 (i'), and y 2 ( p ( ~ ( y 2 ( S ) ) ) ) = p ( ~ , (S)) by Theorem 2.5.4 (iv') In addition, ~ ( L , ( S ) ) = p ( ~ ( y ~ ( S ) ) ) C p ( ~ ( p ( ~ ( s ) ) ) ) =
~ ( L ( S ) ) Altogether we obtain y 2 ( p ( ~ ( S ) ) ) C ~ ( L ( S ) ) The opposite inclusion is always true, since y2 is a closure operator Conversely,
S c ,u(L(S)) implies y2(S) C y 2 ( p ( ~ ( S ) ) ) = ~ ( L ( S ) ) , by the exten- sivity of p ~ , the monotonicity of 7 2 and our assumption
We are now prepared to produce our complete sublattices, derived from the original relation R and the Galois connection (p, L) This leads to the formation of two dually isomorphic complete lattices of closed sets, denoted as 'FI,, and 'FI,, Additionally, we obtain two complete lattices of closed sets from the new Galois connection (p,, L,) induced by R, Our key finding is that each new complete lattice serves as a complete sublattice of its corresponding original complete lattice.
Theorem 2.5.7 Let R be a relation between A and B , with induced Galois connection ( p , L) Let y = (yl, y2) be a conjugate pair of completely additive closure operators with respect to R T h e n the
46 2 Closure Operators and Lattices lattice 'FI,,,, of sets closed u n d e r p,~, i s a complete sublattice of the lattice 'FI,,, and dually the lattice 'FI,,,, i s a complete sublattice of the lattice EL,
Proof: As a closure system 'FI,,,, is a complete lattice, and we have to prove that it is a complete sublattice of the complete lattice 'FI,,
We begin by showing that it is a subset Let S E 'FI,,,,, so that
S E 'FI,, This shows 'Ft,,,, c 'Ft,, Since every S in 'Ft,,,, satisfies
~ ( L ( S ) ) = S, we can apply Theorem 2.5.5, to get
The additive closure operator 7 2 indicates that the corresponding closure system forms a complete sublattice within the lattice (P(B); n, U) of all subsets of B In this lattice 'Ft,,,,, the meet operation aligns with standard set-intersection, while the join operation corresponds to union Since we have established that the meet operation in 'FI,, aligns with intersection, it remains to demonstrate that 'FI,,,, is also closed under the join operation.
'FI,, Let ( S k ) k E J be an indexed family of subsets of B Then by Theorem 2.5.4 (iv'); and then using Lemma 2.3.3 we have
Conjugate pairs of additive closure operators provide a method for constructing complete sublattices within a closure lattice Additionally, we can establish an order relation among all conjugate pairs of additive closure operators, defined as follows: for pairs \( a = (y_1, y_2) \) and \( b = (y_3, y_4) \), we can compare their properties accordingly.
When a < P, it can be shown that the lattice 'FI,,,, is a sublattice of 'FI,,,,, and dually that 'FI,,,, is a sublattice of 'FI, ,.,,
2.5 Conjugate Pairs of Additive Closure Operators
The following additional properties may also be verified:
Sr Arworn has extended the theory of conjugate pairs of additive closure operators to encompass conjugate pairs of extensive, additive operators Additionally, an alternative proof of Theorem 2.5.7 can be established by demonstrating that R, functions as a Galois closed subrelation.
R and then by using of Theorem 2.4.3
Proposition 2.5.8 Let R C A x B be a relation and let ( p ~ ) be the Galois connection induced by R Let y := (yl, y2) be a conjugate pair of completely additive closure operators defined o n A and o n
B , repectively Let R, be the relation defined in Definition 2.5.3 and assume that (p,, L,) is the Galois connection induced by R, T h e n
R, is a Galois closed subrelation of R
Proof: By Definition 2.5.3 the relation R, is a subrelation of R
We apply Proposition 2.4.2 (iii) Let T c A and S c B Then by
In a similar way by Theorem 2.5.4 (iii') and (i) we have
This proves that R, is a Galois closed subrelation of R
This chapter explores the application of conjugate pairs of completely additive closure operators within the lattice of all varieties of a specific type We focus on a fixed type of operation symbols, denoted as r, and examine the sets A = W T ( X ) 2, which encompass all identities (pairs of terms) associated with type r.
The relationship R of satisfaction connects the set of identities with the algebras of type r, where a pair (s = t, A) is included in R if algebra A satisfies the identity s = t This establishes a Galois connection (Id, Mod) between sets of identities and classes of algebras On one side, closed sets represent equational classes or varieties, forming the complete lattice C(r) of all varieties of type r Conversely, closed sets on the identity side correspond to equational theories, resulting in the complete lattice &(r) of all equational theories of type r Both lattices C(r) and &(r) are dually isomorphic and exhibit significant complexity, highlighting the necessity to explore smaller portions, such as complete sublattices, for more manageable analysis.
Our goal is to introduce two new closure operators on our sets
A and B constitute a conjugate pair of additive closure operators, leading to complete sublattices within our two lattices, as demonstrated in Section 2.5 These innovative operators are grounded in the idea of hypersatisfaction of an identity by a variety We will start by defining hypersubstitution, as originally presented in [32].