The Residual Character of Finitely Generated Varieties of Unary Algebras and Groupoids, and Applications to the Restricted Quackenbush Problem by Jesse Mason B.Sc., University of Northern British Columbia, 2011 THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE IN MATHEMATICS UNIVERSITY OF NORTHERN BRITISH COLUMBIA April 2012 © Jesse Mason, 2012 1+1 Library and Archives Canada Bibliotheque et Archives Canada Published Heritage Branch Direction du Patrimoine de I'edition 395 Wellington Street Ottawa ON K1A0N4 Canada 395, rue Wellington Ottawa ON K1A 0N4 Canada Your file Votre reference ISBN: 978-0-494-87540-7 Our file Notre reference ISBN: 978-0-494-87540-7 NOTICE: AVIS: The author has granted a non­ exclusive license allowing Library and Archives Canada to reproduce, publish, archive, preserve, conserve, communicate to the public by telecommunication or on the Internet, loan, distrbute and sell theses worldwide, for commercial or non­ commercial purposes, in microform, paper, electronic and/or any other formats. L'auteur a accorde une licence non exclusive permettant a la Bibliotheque et Archives Canada de reproduire, publier, archiver, sauvegarder, conserver, transmettre au public par telecommunication ou par I'lnternet, preter, distribuer et vendre des theses partout dans le monde, a des fins commerciales ou autres, sur support microforme, papier, electronique et/ou autres formats. The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. L'auteur conserve la propriete du droit d'auteur et des droits moraux qui protege cette these. Ni la these ni des extraits substantiels de celle-ci ne doivent etre imprimes ou autrement reproduits sans son autorisation. In compliance with the Canadian Privacy Act some supporting forms may have been removed from this thesis. Conformement a la loi canadienne sur la protection de la vie privee, quelques formulaires secondaires ont ete enleves de cette these. While these forms may be included in the document page count, their removal does not represent any loss of content from the thesis. Bien que ces formulaires aient inclus dans la pagination, il n'y aura aucun contenu manquant. Canada Abstract The crux of this thesis is to study the Restricted Quackenbush Problem: if B is a finite algebra of finite type and V(B) is residually finite, must V(B) be residually < N, for some positive integer AT? We show that the Restricted Quackenbush Problem is answered affirmatively with re­ spect to unary algebras, a result first shown by Baldwin and Berman in 1975. Then we turn our attention to groupoids and show that all groupoids that generate residually finite varieties must satisfy an identity of the form k(x) » x*x, where k(x) is an identity of type {*} that is not equal to x*x. Due to this result, we focus on a particular class of idempotent groupoids, called absorbing groupoids. We show that if a certain property holds, with respect to absorbing groupoids, then the Restricted Quackenbush Problem is answered af­ firmatively. TABLE OF CONTENTS Table of Contents i List of Tables iii List of Figures iv 1 1 1 1 2 6 7 7 8 13 16 16 19 19 22 33 33 36 Introduction 1.1 The Problem 1.2 Background Material 1.2.1 Algebras, Terms and Identities 1.2.2 Obtaining New Algebras from Old Algebras 1.2.2.1 Direct Products 1.2.2.2 Subuniverses and Subalgebras 1.2.2.3 Congruences and Homomorphic Images 1.2.3 Subdirectly Irreducible Algebras 1.2.4 Varieties 1.2.4.1 Definition of a Variety 1.2.4.2 Essential Building Blocks of the Algebras in Varieties . . 1.2.4.3 Flavours of Varieties 1.2.4.4 Residual Character of a Variety 1.3 Origin and Evolution of the Problem 1.3.1 Quackenbush's Problem 1.3.2 The Reworded Quackenbush Problem 1.3.2.1 The Equivalence of the Quackenbush Problem and the Reworded Quackenbush Problem 1.3.2.2 Before the Reworded Quackenbush Problem 1.3.2.3 After the Reworded Quackenbush Problem 1.3.3 Dealing with the Destruction of Quackenbush's Problem 1.4 Restatement of the Problem 37 40 44 45 46 2 Unary Algebras and the Restricted Quackenbush Problem 2.1 Yoeli's Result 2.2 Connected, Pseudoconnected and Disconnected Unary Algebras 2.2.1 Subdirectly Irreducible Implies Connected or Pseudoconnected . . 48 49 54 57 2.3 2.4 2.5 2.6 2.7 2.2.2 Correspondence of Connected and Pseudoconnected Unary Algebras 59 Every Unary Algebra in a Finitely Generated Variety Has an Irredundant Basis 61 The Appearance of Connected Subdirectly Irreducible Unary Algebras ... 64 2.4.1 The Heart of a Unary Algebra 64 2.4.2 Veins of a Unary Algebra 71 Orientation 73 Subdirectly Irreducible Mono-Unary Algebras 76 Answering the Restricted Quackenbush Problem with Respect to Unary Algebras 78 3 A Property of Finite Groupoids that Generate Residually Finite Varieties 84 3.1 Groupoids that are Influenced by a Partial Order Relation 86 3.1.1 Subdirectly Irreducible Groupoids that are Influenced by a Partial Order Relation 89 3.1.2 Subdirectly Irreducible Groupoids that are Influenced by a Partial Order Relation of Height 3 100 3.2 An Identity that Residually Finite Varieties Generated by Finite Groupoids Must Satisfy Ill 3.3 Application: RS-Conjecture 115 3.4 A Strategy Concerning Groupoids and the Restricted Quackenbush Problem 116 4 Groupoids and the Restricted Quackenbush Problem 4.1 A Property of Idempotent Groupoids 4.2 Absorbing Groupoids 4.2.1 Absorbing Groupoids Do Not Necessarily Generate CongruenceModular Varieties 4.2.2 A Possible Approach to Deal with Absorbing Groupoids and the Restricted Quackenbush Problem 117 118 119 5 Future Work 5.1 Summary 5.2 Questions 129 130 131 Bibliography 131 ii 120 124 LIST OF TABLES 1.1 1.2 1.3 1.4 1.5 1.6 1.7 The Operation Table of The Operation Table of -Z4 The Operation Tables of Ei and E2 The Operation Table of *E3 The Operation Table of /E4, gE* and hE4 The Operation Table of *Es The Operation Table of *B, for a Finite Algebra B in V(E5) 3 3 6 15 15 23 23 The Operation Table of *El4 85 E The Operation Table of * 's 87 The Operation Table of *Eie 87 The Operation Table of a Finite Subdirectly Irreducible Member in a Vari­ ety Generated by a Groupoid Whose Binary Operation is Influenced by a Partial Order Relation 98 3.5 The Operation Table of *D*, Assuming K is a Finite Cardinal Number ... 103 3.6 Identities of Length (0,1) that each D* does not Satisfy 107 3.7 Identities of Length (1,1) that each D* does not Satisfy 108 3.8 Identities of Length (0,1) that B and each DK do not Satisfy 110 3.9 Identities of Length (1,1) that B and each D* do not Satisfy 110 3.10 Identities of Length (1,1) that B and each D* do not Satisfy 113 3.11 The Operation Table of *E17 114 3.1 3.2 3.3 3.4 4.1 4.2 The Operation Table of *E'9 The Operation Table of *M 119 122 iii LIST OF FIGURES 1.1 The Congruence Lattice of E3 1.2 The Congruence Lattice of E4 1.3 The Lattice N5 1.4 The Graphs ofthe Prime Cycles Pi, P2 and P4 15 15 21 32 2.1 2.2 2.3 The Graph of Hp« 53 The Graph of 53 A Connected Unary Algebra E6 and Associated Undirected Multi-Graph G(E6) 55 2.4 A Pseudoconnected Unary Algebra: E7 56 2.5 A Disconnected Unary Algebra: Eg 56 2.6 A Unary Algebra Without an Irredundant Basis: E9 61 2.7 A Connected Unary Algebra with a Heart: E10 65 2.8 A Connected Unary Algebra that is Heartless: En 67 2.9 A Unary Algebra that has a Heart and is not Subdirectly Irreducible: E12 . 70 2.10 A Connected Unary Algebra with a Heart that has Two Veins that have the Same Orientation with Respect to the Heart: E13 75 2.11 The Graph of H p , 77 + 2.12 The Graph of T 77 3.1 3.2 3.3 3.4 The Congruence Lattice of E14 The Partial Order Relation < that Corresponds to *E|5 The Partial Order Relation < that Corresponds to *E'6 How B l , S , K and K Interact 85 87 87 91 4.1 The Lattice of Subuniverses of E19 120 iv Chapter 1 Introduction 1.1 The Problem The Restricted Quackenbush Problem is a problem that originated in the seventies. An answer to this problem would yield a further understanding of the residual character of finitely generated varieties of finite type. Problem (Restricted Quackenbush Problem). Let Bbea finite algebra of finite type. If all subdirectly irreducible algebras in the variety generated by B have a finite universe, must there exist a finite bound on the cardinality of the universe of each subdirectly irreducible algebra in this variety? In this chapter, we start by looking at some necessary background material in Universal Algebra to understand the problem. This chapter concludes with a section that discusses the origin and evolution of the Restricted Quackenbush Problem. 12 Background Material To understand the problem, specific concepts and definitions are needed. The following background material is taken from either [2] or [13]. Unary algebras and groupoids will 1 be used extensively throughout this document. For a list of common and exotic algebras, see §1 of Chapter 2, and §1 and §2 of Chapter 3 in [2] or see Chapter 1.1 in [13]. 1.2.1 Algebras, Terms and Identities A set T is called a type of algebras or a language of algebras if T is a family of finitary operation symbols such that to each operation symbol there corresponds a non-negative in­ teger called the operation symbol's arity or rank. For each positive integer n,the symbol Tn denotes the set of n-ary operation symbols in T. Definition. An algebra B of type T is a non-empty set, called a universe or an underlying set B, together with a family of finitary operations F defined on the universe and indexed by members of T such that the arity of an operation agrees with the arity of the corre­ sponding symbol in F. That is, for each n-ary symbol / in T, there exists a unique finitary operation /B in F such that the arity of /B is n. The algebra B described in the above definition is often written as B = ( B \ F ) . If |F| is small then, often, t h e finitary operations a r e listed i n decreasing arity. Further, B = ( B ; T ) is often used to define an algebra, with the implicit understanding that there exists a set F of finitary operations as defined above. Similarly, if \T\ is small then, often, the finitary operation symbols are listed in decreasing arity. Example. The group with four elements and addition and subtraction modulo 4, Z4 = ({0,1,2,3};{+ZVZ4,0Z4}) or Z4 = ({0,1,2,3};+,-, 0), is an algebra of type {+, -,0}, where + is a binary operation symbol, - is a unary operation symbol and 0 is a nullary operation symbol. The set {0,1,2,3} is the universe of the group, while {+Z4, -z450Z4} is the family of fundamental operations. See Table 1.1 and Table 1.2 2 for the operation tables of +Za and -z4, respectively. The nullary operation O24 is defined tobeO. -Z4 +Z4 0 1 2 0 0 1 2 3 0 0 1 1 2 3 0 1 3 2 2 3 0 1 2 2 3 3 0 2 3 1 1 3 Table 1.1: The Operation Table of +2*4 Table 1.2: The Operation Table of -Z4 Definition. Let T be a language and X be a set of variables. Further, let T ( X ) denote the smallest set that contains X and all nullary operation symbols such that if p i, pi,.. .pn are in T{X) and / is in Tn, then f(p\,p2,...,pn)\s'mT(X). Each member of T(X) is called a term of type T over X. Alternatively, we can think of a term as a string that is a well defined concatenation of operation symbols and variables. When a term is realized in an algebra, it becomes a composition of operations. Example. Let J7 be the language of Abelian groups. That is, let T = {+,-,0}, where + is a binary operation symbol, - is a unary operation symbol and 0 is a nullary operation symbol. Further, let X = {xj,x2}. The strings 5I(XI,X 2)-(0+JTI ) + (-X 2), 52(*i) =0+(-0) and J3(*i,*2,*3) =*i+*i are all terms of type T over X. Alone, they are no more than a concatenation of symbols. 3 However, 5^(3) = O24 jf4 (1,2) = (O24 +z* 1) +Z4 (-^ (2)) (-^(O24)) = (0+ Z 4 l)+ Z 4 2 = 0+Z4(-Z4(0)) = 1+ Z 4 2 = 0+ Z 4 0 = 3, =0 and 5Z4(3,1,0) = 3+Z43 = 2. Definition. Let T be a language of algebras and let n be a positive integer. Further, let X = j denote an indexed set of n variables. An n-ary identity of type T over X is an expression of the form V JCI V * 2 V x 3 [ / I (*I ,.*2,*3>--M*II) «f2(xi,x2,x3,(1-0 where t\(xj ,JC2, and f2(xj ,x2,jC3,... ,xn) are terms of type T over X. Usually, an identity is written without the quantifiers. Sometimes, if the variables need not be explicitly defined, an identity is written without listing the variables. That is, often the identity in Statement (1.1) is written as t\ «f2. An algebra B of type T satisfies the n-ary identity given in Statement (1.1) if and only if tf(b1,b2,b3,...,bn)=tf(bi,b2,b3,...,bn). 4 This is denoted by If B does not satisfy the identity given in Statement (1.1), then we write B^<|« t2. Example. Returning to the example on page 2, since Z4 is an Abelian group, it satisfies the Abelian group identities. That is, BI= ( j t + y ) + z WJC+^ + Z), BI=X+0WJC, BI=X+-(X)«0, and Bt=Jt+;y »y+jc. When realized in Z4, the terms s\ and 52. defined in the example on page 3, correspond to compositions of the operations +Z4,-Z4 and O24. That is, s ^ ( xI , X 2 ) = X I + Z 4 ( - Z 4 { X 2 ) ) and s f * ( xi ) = 0 z \ In the previous definition, notice the use of = and «. They both mean equality to some extent. They are similar in meaning; but, are different in their utilization. In general, when dealing only with the language of an algebra and other logical devices, the symbol » is used; however, when a specific algebra is being looked at, with elements of the universe being used, the symbol = is used because actual equality of elements is intended. This distinction is very useful in switching from the class of all algebras of a similar type to a specific algebra in that class and vice versa, without formally stating the distinction. The next example illustrates the need for the distinction between = and «. Example. Consider the language of a monoid !F = {*, 1}, where * is a binary operation symbol and 1 is a nullary operation symbol. The terms 1 and 1 * 1 are not equal. Specifi5 *Ei 0 1 *E* 0 1 0 0 0 0 1 1 1 0 0 1 1 1 Table 1.3: The Operation Tables of Ej and E2 cally, 1 is the concatenation of one symbol while 1 * 1 is the concatenation of three. There­ fore, the term equality 1 * 1 = 1 is false. On the other hand, 1 * 1 » 1 is an identity that may or may not hold in an algebra. Consider the monoids Ei = ({0, l};*El, lEl) and E2 = ({0, 1};*E*, lEz} where 1E< = 1 and 1E2 = 1. The operation table for the binary operation corresponding to each monoid is given in Table 1.3. The monoid E2 satisfies the identity 1 * 1« 1, whereas the monoid Ei does not. Under these conditions, we may write lEz *e* 1e2 = lEz and lEl *El lEl * lEl. Let K denote a class of algebras of type T. The set of identities of type T over some set of variables X that hold true in K is denoted by Id^(X). Often, we are not too concerned with the set of variables and use Id* instead of Id* (X). 1.22 Obtaining New Algebras from Old Algebras There are three general ways of constructing new algebras from old algebras: direct prod­ ucts, subalgebras and homomorphic images. Their definitions are described formally. 6 122.1 Direct Products Let {Bi}iti denote an indexed set of algebras of type T. The algebra iel \ iel I is called the direct product of the B;'s and each B, is called & factor of the direct product. The universe of the direct product is the cartesian product of the universe of each factor. The finitary operations are defined coordinate wise. That is, for the positive integer n, if / is in Tn and {b/}"=\ £ n«.,then i€/ .,&„))(/) = (/),b2{i),...,b„(i)). For the remainder of this subsection, assume that B is an algebra of type T. If |fl| - 1, then B is called a trivial algebra of type T. Note that up to isomorphism, there exists only one trivial algebra of type T. Note that if the index 1 is empty, then ]~[B; is a trivial algebra. The universe of this i«/ direct product is the set containing only the empty tuple. 1222 Subuniverses and Subalgebras A subset M of B is called a subuniverse of B if for all / in T, the set M is closed under /B. The smallest subuniverse of B that contains M is denoted by SgB(M). Definition. Suppose that 5 9 B such that SgB(S) = B. Then S is called a generating set of B; the set S is said to generate B and the members of S are called generators. If for all s in S, the set 5\{s} does not generate B, then S is said to be a minimal generating set or an irredundant basis. Example. Consider the group Zio = {Z10;+z'0,-z'0,Oz'o), where +Zl° is addition modulo 10. The set {3,6,7} is a generating set; but, it is not a minimal generating set as {7} generates {0,1,...,9}. Also, {2,5} is an irredundant basis, as is {1}. Definition. An algebra M of type T is called a subalgebra of B if M is a subuniverse of B and the operations of M are the restrictions of the operations of B to M. That is, if M is a subalgebra of B, denoted by M < B, then M is a non-empty subuniverse of B and for all / in T, we have /M = /B \M- If M is a non-empty proper subuniverse of B, then M is a strict subalgebra of B and the notation changes to M < B. The main difference between a subuniverse and a subalgebra, aside from the former being a set and the latter being an algebra, is a subuniverse can be empty, while the uni­ verse of a subalgebra cannot. If the language of an algebra B does not contain any nullary operation symbols, then the subuniverse generated by 0 is 0. If a nullary operation symbol is present, then this cannot occur as every subuniverse must contain at least one member, the constant corresponding to the nullary operation symbol. 1223 Congruences and Homomorphic Images Let 0 denote a relation on B. The relation 6 satisfies the compatibility property if for all n > 0, for all / in Tn,and for all {a;}"=1 £ B and {bi}"=l c B such that ai 6 bi for all i € {1,..., n} we have /B(ai,a2, fB(bub2,...,bn). Definition. A congruence on B is an equivalence relation defined on B that satisfies the compatibility property. 8 Often, we want to discuss or use the smallest congruence that relates element b\ to element bi. This is denoted by CgB({(fci,&2)}) or just CgB((bi,£>2)) and is read as the congruence on B generated by relating b\ to bi- A congruence generated by relating two elements is called a principal congruence. For S, a non-empty subset of B, the smallest congruence that relates every member of S to every member of S is denoted by CgB(52). There always exist at least two congruences on B. They are the congruence obtained by relating every element in B to every element in B and the congruence obtained by relating every element in B to only itself. Respectively, these congruence are denoted by &B = { ( b , b ) \ b e B } and VB=B 2 . These congruences are sometimes referred to as the trivial congruences on B. Definition. A first order formula is a well defined concatenation of identities, relation symbols, propositional connectives and quantifiers. The propositional connectives are A (and), v (or), (not), -* (implies) and <->• (if and only if). The quantifiers are 3 (existential) and V (universal). Given a metric space (B,d), variables x, y and z, real addition +, and real less than or equal to <, the triangle inequality VxV;yVz[y(.t,;y)+*/(>>,z) >d(x,z)~], is a common first order formula found in the study of metric spaces. A principal congruence formula is an example of a first order formula that will be used in later sections and chapters of this document. Definition. A principal congruence formula is a first order formula jt(h>I,h>2,W3,h>4) of type T that is of the form 3K^WI *H(X U K)A /\ (^(YF^JW/I+I^I+I.FT)) A/„(Y n,J) «W 2 J, 9 (1.2) where n is a positive integer and the symbol k denotes a vector of variables distinct from wj, vt>2, W3 a n d W4. Further, f o r all 1 < i < n , w e have {*;,)>,•} = { W 3 , H > 4 } a n d t h e t e r m t t i s o f t y p e T over {xi,yt} and the variables in k. For b \ , b 2 , h and £4 in B , we may represent jr^4) holding in B using the following staircase diagram: b\ =ff(jq,e) t f ( y \ , e )= t f ( x 2 , e ) t2(y2,e)=tf(*3,e) t n - i ( y n - i , e )= t * { x n , e ) $(yn,e) = b2, where for all 1 < i < n , we have = {£3,64} and e is a vector of members from B . Theorem 12.1 (Mal'cev's Principal Congruence Formula Theorem). Let B be an algebra and {&i,&2,^3)^4} - B- Then, {b\,bi) is in CgB((^3,i>4)) if and only if, for some principal congruence formula n , t h e algebra B satisfies J t ( b i , b 2 , b i , b 4 ) . 10 Corollary 122. Let B be a unary algebra and b\, b2, 63 and £4 be members in B. If (b\,b2) is in CgB((bi,b4)) then there exists some set ofn unary terms realized in B, say {ti}"=i> such t^at b\=tf(x\) 'J-lfrn-l ) = *?(*!.) $(yn) = b2, where for all 1 ub2,...,bn)/oThe resulting algebra B / 6 - ( B / 6 ; J 7 ) is called the factor algebra or the quotient algebra of B by 6. The notation B/6 is read as B modulo d or just B mod d. 11 We may think of B / 6 as a collapsed copy of B. Further, we may think of 6 as a set of instructions that describe how to collapse B without forcing the operations to become multivalued. Definition. Let B and M be two algebras of the type T. For all positive integers n, if the function fcB->M satisfies the property for all / in Tn and {6,}"=1 £ B, then h is called a homomorphism. Given a homomorphism h: B -• M, the relation defined on B 2 , ker( h ) = { { b x , b 2 ) e B 2 : h ( b \ ) = h ( b 2 ) } , is called the kernel of h. This relation is denoted by ker (h) and can be shown to be a congruence on B. Theorem 123 (First Isomorphism Theorem). Let h\--B -*• M be a surjective homomor­ phism. Then, there is an isomorphism h2 from Bjker (hi) to M defined by h\ = /12 ° /13, where h-$ is the homomorphism from B to BJ ker (hi) obtained by mapping each element in B t o the congruence block that it i s a m e m b e r o f i n B f k e r ( h x ) . If h is surjective, then M is called a homomorphic image of B. If h is injective, then h is called an embedding of B and B is said to be embedded into M. If h is bijective, then h is called an isomorphism. If h is an isomorphism and B = M then h is called an automorphism. If M is a homomorphic image of B, then by the First Isomorphism Theorem, there exists a congruence 6 such that M = B/0. That is, all homomorphic images of B are collapsed copies of B with the elements in the universe of the collapsed copy relabelled. 12 To every congruence 6 on B there corresponds a surjective homomorphism, vg:B B/0 called the natural homomorphism,defined by vg(b) =b/6. To every surjective homo­ morphism of B corresponds a congruence, namely, ker (h). Thus, there exists a one-to-one correspondence between the set of congruences on B and the set of homomorphic images of B. In general, direct powers of an algebra (direct products where each factor is the same al­ gebra) yield an algebra with a larger universe, while subalgebras and homomorphic images of an algebra yield an algebra with a smaller universe. 123 Subdirectly Irreducible Algebras Subdirectly irreducible algebras play a large role in the Restricted Quackenbush Problem. For the following few definitions, let n be a positive integer and I be some index set such that B and each member of {B,};€/ are algebras of the same type. Let X denote a non-empty set. For each positive integer n and 1 < i < n, the i'h n-ary projection map is a function from Xn to X that maps each n-tuple in X" to the value in the ith coordinate of the n-tuple. The j'th n-ary projection map is denoted by the symbol xWhen the /th n-ary projection map is restricted to some proper subset of its domain, p, is used in place of TT, . The algebra B is said to be a subdirect product of the B, 's if for some index set /, BsnB, and for all tin/, p,(B) = B/. !€/ An embedding h from B to J~[B/ is a subdirect embedding if /i(B) is a subdirect product of (€/ the B,'s. Definition. The algebra B is subdirectly irreducible if for every subdirect embedding h:B-+HBi' IE/ 13 there exists j in / such that B = B7. Unfortunately, using the formal definition of subdirectly irreducible in practice is nettlesome. Luckily, a tool, given as an upcoming theorem, is available. Definition. Let B = {B\!F) be an algebra and let Con B denote the set of congruences on B. For 0i and 02 in Con B, let • 0i ACon B 02 denote 0j n02 and let • 0j vCon B 02 denote the least congruence on B containing 0i and 62. Then (Con B; A C o n B , v C o n B ) forms a lattice called the congruence lattice of B. The con­ gruence lattice of B is denoted by Con B. Theorem 12.4. Let B = (B;!F) be an algebra. The lattice Con B has a minimum non-As congruence or B is trivial if and only if B subdirectly irreducible. The minimum non-As congruence of a subdirectly irreducible is called the monolith of B. The two following examples demonstrate how to apply the above theorem to show that an algebra is subdirectly irreducible. Example. The commutative groupoid E3, whose single fundamental operation is described in Table 1.4, is subdirectly irreducible. The congruence lattice of E3, depicted in Figure 1.1, has a minimum non-A#, congruence, namely, {0,1}2 u AE3 . Example. The unary algebra E4, whose fundamental operations are described in Table 1.5, is not subdirectly irreducible. The congruence lattice of E4 is depicted in Figure 1.2. There are three minimal non-A£4 congruences, namely, {0,3}2UA £4, {1,3}2UA £4 and but, there does not exist a minimum non-Af4 congruence. 14 {2,3}2uA£4; *E3 0 12 3 0 0 10 1 1 10 0 2 0 0 11 3 1 1 {0,1,3}2uA£3 1 1 ,1}2uA£3 1 OA* Table 1.4: The Operation Table of *E3 Figure 1.1: The Congruence Lattice of E3 VE 4 /E4 g®4 hE4 0 3 0 0 1 1 1 3 2 2 3 2 3 3 3 3 {123}2uA£4 {2,3}2uA£4 Table 1.5: The Operation Table of /E4, g®4 and A®4 Figure 1.2: The Congruence Lattice of E4 Is the trivial algebra really subdirectly irreducible? The answer depends on whom this question is asked to. See §8 of Chapter 2 of [2]. For our purposes, we consider the trivial algebra to be subdirectly irreducible. 15 As we shall see in Theorem 1.2.8, in the next subsection, subdirectly irreducible alge­ bras are a key component in understanding varieties. 1.2.4 Varieties A class of objects that is of great interest in Universal Algebra is the class of varieties. In this subsection, the definition of a variety is given and the relationship between the variety and subdirectly irreducible algebras in the variety is explained. We then define many popular subclasses of varieties. This subsection is concluded with a tool that is useful in classifying varieties: the residual character of a variety. 12.4.1 Definition of a Variety Due to Birkoff and Tarski, there exist two very different views of a variety. We present both as, under certain conditions, one is easier to apply than the other and vice versa. Let K denote a class of algebras, all of the same type. • F ( K ) to be the class of all direct products of non-empty families of members in K , • § ( K ) to be the class of all subalgebras of each member in K , • H(£) to be the class of all homomorphic images of each member in K, • P S ( K ) to be the class of all subdirect products of non-empty families of members in K and • Pfin(^) to be the class of all direct products of non-empty finite families of members in K. Here, P,S, H, P$ and Pfin are operations acting on a class of algebras of the same type. In particular P, § and H play a critical role in the construction of a variety. 16 Definition. A non-empty class of algebras, all of the same type, that is closed under P, § and H is called a variety. If AT is a non-empty class of algebras, all of the same type, then denote V(A') as the smallest variety that contains K. The class of algebras V(K) is called the variety generated by K. The variety V is said to be finitely generated if V = ¥(A"), where K is a finite set of finite algebras. If K contains exactly one member, suppose B, then V(B) is commonly used in place ofV ( K ) or V({B}) to denote the variety generated by K . For K, a non-empty class of algebras of the same type, we may use Tarski's HSP Theorem to interpret ¥(K) as the class of all homomorphic images of all subalgebras of all possible direct products of members in K. Theorem 1.2.5 (Tarski's HSP Theorem). Let K denote a non-empty class of algebras, all of the same type. Then V(AT) = HSP(AT). We show that a finitely generated variety is equivalent to a variety generated by a single finite algebra, as these two constructions of a variety are often used interchangeably. Lemma 1.2.6. The variety V is finitely generated if and only if V is generated by a single finite algebra. Proof. For the forward implication, assume that V is a finitely generated algebra. That is, for a positive integer n, let {B,}"=1 denote a finite set of finite algebras, all of the same type such that V = V({B,}"=1). We show that (1.3) to obtain the desired result: the variety V is generated by a single finite algebra. Using Tarski's MSP Theorem, or Theorem 1.2.5 n JIB, € P({B,}»,,) cHSP({Bj}"=1) = V({B, 17 Hence, v(nB>)EV(«?,,). (i.4) Note that for all i between 1 and n, inclusive, is a surjective homomorphism. That is, each B, is a homomorphic image of n*. i= 1 Therefore, Thus, V({Bi}"=1)s vfpjBjj. (15) The subset relations in Statement (1.4) and Statement (1.5) yield the equality in State­ ment (1.3). The reverse implication is immediate. • Let K denote a class of algebras. If there exists a set of identities 2, of type T over some set of variables, such that K is equal to the class of all algebras of type T that satisfy each identity in 2, then K is called an equational class. Theorem 1.2.7 (Birkoff). Let K denote a class of algebras, all of the same type. The class K is a variety if and only if K is an equational class. Thus, there are two ways to interpret V(B): 1. the class of all homomorphic images of subalgebras of direct powers of B with a non-empty index, that is, HSP(B) or 2. the class of all algebras of type T that satisfy all of the identities in Id{B}. 18 12.42 Essential Building Blocks of the Algebras in Varieties The following Theorem explains the importance of determining what the subdirectly irre­ ducible algebras in a given variety are. Theorem 1.2.8 (Birkoff's Theorem). Let V be a variety. Every member in V is isomorphic to a subdirect product of subdirectly irreducible members in V. Therefore, the subdirectly irreducible members in a variety are, loosely speaking, the building blocks of the members in a variety. Their importance is that they yield a deeper understanding of the structure of varieties. 12A3 Flavours of Varieties We give a brief outline of a few popular subclasses of varieties. The first few subclasses require that we look at the congruence lattice of the algebras in a given variety. The algebra B is said to be congruence-distributive if Con B satisfies the distributive identities. That is, B is congruence distributive if Con B satisfies the identities XV(YAZ) RS (xvy) A(JCVZ ) and -*A(Y vz) * (XA>>)V(.*AZ). This means that for all 6\, 02 and 03 in Con B, 0! V CON B (02 A CON B 03) = (0! V CON B 0 2 ) A CON B (0! V CON B 0 3 ) and 01 A CON B ( 02 V CONB 03 ) = ( 01 A CON B 02 ) V CON B ( 0! A CON B 03 ). If Con B satisfies the meet-semidistributive formula VjtV_yVz[jcA)> «jEAz-»-.XA;y » jca (y vz)], 19 then B is said to be congruence-meet-semidistributive. Note that Con B satisfies the above first order formula if and only if for all Q\, 02 and 63 in Con B, 01 A 02 * 01 A 03 01" 01 A 02 = 01 A ( 02 V 03 ) Let o\ and 02 be two binary relations on the set B. The relational product of o\ and 02 is defined as { { a,c)| 3 b t B such that ( a , b ) e 0 \ and ( b , c ) e cr2} and is denoted by o \ 0 0 2 . The congruence lattice of B is said to be permutable if for all 0i and 02 in Con B 01 o 02 = 02 o 0j. If the congruence lattice of B is permutable, then B is said to be congruence-permutable. If the congruence lattice of B satisfies then Con B is said to be modular and B is said to be congruence-modular. Both congruence-distributivity and congruence-permutability imply congruencemodularity. Hence, if a variety is not congruence-modular, then that variety is neither congruence-distributive nor congruence-permutable. One can determine if a finite lattice, and hence a finite congruence lattice, is not modular by looking at the Hasse diagram that corresponds to the lattice. Let N5 be the lattice depicted by the Hasse diagram in Figure 1.3. Theorem 12S (Dedekind's Theorem). A lattice is not modular if and only if N5 can be embedded into the lattice. 20 0 Figure 1.3: The Lattice N5 The following definition is taken from [16]. An algebra B is said to be congruenceregular if and only if every congruence of the algebra is completely and uniquely deter­ mined by any equivalence class. Groups and rings are examples of congruence-regular algebras. Definition. If all algebras in a variety V are congruence-distributive, congruence-meetsemidistributive, congruence-permutable, congruence-modular or congruence-regular then V is said to be congruence-distributive, congruence-meet-semidistributive, congruencepermutable, congruence-modular or congruence-regular, respectively. A Mal'cev condition is an identity or set of identities, that involves a particular term, such that when satisfied by all algebras in a given variety, implies a particular property must hold for the variety. For example, there exist Mal'cev conditions that can be used to determine if a variety is congruence-distributive, if a variety is congruence-permutable or if a variety is congruence-modular. The next example shows how a Mal'cev condition can be used to show that all varieties of lattices are congruence-distributive. 21 Example. All varieties of lattices are congruence-distributive. It is known that for a vari­ ety V and ternary term t(x,y,z), if V satisfies t ( x , x ,y) « T (x, y, x ) M t (y,x, x ) X , (1.6) then V is congruence-distributive. The identities above form an example of a Mal'cev condition. If such a term exists, it is called a majority term for V. Let V be a variety of lattices, L be a lattice in V and t ( x , y , z ) = (*vy) A (x vz) A ( y v z ) . It can be shown, using the absorption identity, that for all 11 and £2 in L, «rL(€i,£2,^i) *h- Therefore, L satisfies the identities listed in Statement (1.6) and hence V satisfies the same identities. Thus, V is congruence-distributive. An algebra B is said to be locally finite if every finitely generated subalgebra of B is finite. A variety V is locally finite if every algebra in V is locally finite. As the next theorem states, every finitely generated variety is locally finite. Theorem 12.10. I f B i s a finite a l g e b r a , t h e n V(B) is a locally finite variety. 12.4.4 Residual Character of a Variety A method of classifying varieties is by the existence of or size of the minimum bound on the cardinalities of the subdirectly irreducible algebras in the variety. Definition. Let V be a variety. If there exists a least cardinal number K such that the cardinality of the universe of every subdirectly irreducible member in the variety is less than K, then K: is called the residual character or residual bound of V. 22 There also exist more general classifications of varieties that involve the residual bound. A variety V is said to be • residually large if no such cardinal number K exists, • residually small if the cardinal number JC exists, • residually finite if the cardinality of the universe of each subdirectly irreducible mem­ ber in V is finite and • residually < N if, for some fixed positive integer N, the cardinality of the universe of each subdirectly irreducible member in V is less than N. Determining the residual character of a given variety, or deciding if a given variety is residually finite, is generally extremely difficult. Example. Consider the groupoid e5, whose binary operation table is given in Table 1.6. The binary operation *Es is the first projection map on {0,1}2. What is the residual charac­ ter of V(E5)? n-1 n 0 0 0 1 1 1 1 2 2 2 2 : : n-1 n-1 n n 0 1 2 0 0 0 1 1 2 2 *ES 0 0 0 0 n-1 n-1 n-1 n-1 1 1 n n 1 1 •• •• : n n •• Table 1.6: The Operation Table 1.7: The Operation Table of *B, for a Finite Table of *Es Algebra B in V(E5) 23 As E5 satisfies the identity x * y < * x , every member in V(Es) satisfies the same identity. Therefore, for all finite B in V(Es), the operation table of *B looks like that given in Table 1.7. Let b\ and b2 in B and define Further, let r = &Bu{(bi,b2),(b2,bi)}. Certainly, t c d(h{ h2y Is there something in 0{bub2) that is not in r? To answer this, we need to note that r is the smallest reflexive, symmetric and transitive set containing {b\,b2). We verify that it is a subuniverse of B2 as this is tantamount to t satisfying the compatibility property. To see that T is a subuniverse of B2, note that if {t\,t2) and <^4) is in r then {*i>'2)*BxB{'3,^4) = (*i * B h , t 2 * V h ) = {h,h) eABu{{bub2),(b2M)}Hence, r is the smallest congruence on B that contains { b \ , b 2 } . That is, for all b{ and&2 in B, we have 0{bub2) = AB^{(bi,b2),(b2,bi)}. (1-7) Suppose that B is in V(Es) and |Z?|>2. Without loss of generality, assume that {b1,b2,£3} is a three element subset of B. Under this assumption, and using Statement (1.7), we have d ( b i , b 2 ) A C o n B e (b2,b3) = (A« u {<^1M , { h , b \ )}) n (A b u {<^2,^3), ( h , b 2 ) } ) = &Bu({(bi,b2),{b2,bi)}n{(b2,b3),(b3,b2}}) = Ab U0 = AB- 24 Neither 0^, ^ nor D {b2,b3) equals A B , but, their meet is AB - Thus, the algebra B cannot possible have a monolith and therefore is not subdirectly irreducible. We have just shown that if B is in V(Es) such that \B\ > 2 then B is not subdirectly irreducible. In fact, the only subdirectly irreducible algebras in V(Es), up to isomorphism, are E5 and the trivial algebra. That is, V(Es) is residually < 3. Must all residually finite varieties be residually < N, for some positive integer /V? The following example, taken from a footnote in [8], will show that the answer is no. A Pixley variety is a variety of finite type that is residually finite, but, is not residually < N, for any positive integer N. Note that a Pixley variety is not required to be finitely generated. Example. Consider the variety V of all bi-unary algebras over the language {/,g} that satisfy the following identities: (f°8)(x)"x and /)(*)«*. (1-8) In the remainder of this section, we show that V is a residually finite variety that is not residually < N, for any positive integer N, and that V is not finitely generated. Throughout the proofs of this claim, we make use of the fact, shown in the next lemma, that all unary algebras in V have at least one irredundant basis. Lemma 1.2.11. Every member of V has at least one irredundant basis. Proof. Let B be a member of V. Let GB denote the undirected multi-graph obtained by removing the labels from the edges and their direction, in the graph that corresponds to B. For all r\ and ri in B, say that (r\,ri) is in the relation R if and only if r\ and r2 are in the same component of gB- Thus, there exists a path from r\ to r2 in gB if and only if (n ,r2) is in R. That is, there exists a finite sequence {&'}"=0, of members in B such that b'Q = r\ 25 and b'n = ri and /B(^)=^+1, fB(b'j+l)=b'j, g B ( b 'j) = b ' J+l, or g B(b' j+l)=b'j for all 0 < j < n. Note that the path from r\ to ri must be finite. Since B satisfies the identities in Statement (1.8), for all 0 3, then B is not subdirectly irreducible. Sketch of Proof. For a positive integer m, given a term t = t\ °t2°---°tm, with ti in {/,g}, set t = tmotm..\ o--oFi where?,- is in {f,g}\{ti}. For example, if t = fogogofofofog then t=fogogogofofog. Note that (t o t)( x ) « x by Statement (1.8). Let si and 52 be in S such that si * S2. Note that for all terms t\ and ti of type {/,g}, we m u s t h a v e t f ( s \ ) *t f ( $ 2 ) a s o t h e r w i s e , t h e r e e x i t s a t e r m t o f t y p e { f , g } s u c h t h a t t B ( s \ ) = S2 and hence S is not an irredundant basis. To see this, assume that ($1) = tf fa). Let t = t2°ti and fB(*i) = ( ( J i ) B ° t f ) ( s i ) - ((5)®°*?)(*2) = s 2 . Therefore, forallsi and 52 in S,if si #52 then SgB({si})nSg ( { s 2 } ) = 0 . B (110) We require Lemma 2.2.2 on page 57, that will be proved in a later chapter. The lemma states that, for unary algebras, if Mi is a subalgebra of Bi and 6 is a congruence on Mi, then CgBl(0) = 0uAfil. 27 3 By hypothesis |S| > 3. Without loss of generality, let 1,52,^3,54} be a four element subset of S. Then, acknowledging that (SgB({,i})uSgB({,2})) and (SgB({s3}) u SgB({s4})) and SgB({s3}) uSgB({54}), are congruences on SgB({^i})uSgB({52}) respectively, and that both are subalgebras of B, we can apply Lemma 2.2.2 and utilize Statement (1.10) to obtain the following: CgB|(SgB({51})uSgB({j2 } ) ) 2 ) A ConBCgB|(SgB({53})uSgB({54} ) ) 2 j = ^(SgB({5i})uSgB({s2})) uABJn^(SgB({s3})uSgB({54})) uABj = |(sgB({*i})uSgB({s2})) n(SgB({53})uSgB({^4})) juAB = 0uAg = ABSince we obtained a meet of two non-trivial congruences that equate to AB , the congru­ ence lattice of B cannot possibly have a minimum non-trivial element. That is, B is not subdirectly irreducible, under the assumption that \S\ > 3. • We define an algebra called Q in V that plays a crucial role in the proof of an upcoming lemma. Let Q = {Q\ where Q is the set of integers and for all q in Q, f Q ( q ) = q+ 1 and using regular integer addition and subtraction. 28 gQ(q)=q~l, (1.11) Lemma 12.13. The algebra Q is not subdirectly irreducible. Proof. For each prime p, the equivalence relation modulo p, denoted by =p, is an equiv­ alence relation on Q because it is an equivalence relation on the integers with the usual operations. Since for all q\ and qi in Q and any prime p, qi=p<72_ the relation =p is a congruence on Q. Consider the congruence 0= (~1 =p • p is prime Suppose that ( q \ , q i ) is in Q . Then for any prime p , we have p| ( q \ - q i ) and <71 -qi is an integer. This can only occur if q\ = qi- Therefore, 6 = AQ. That is, 6 is a meet of non-Ag congruences that is equal to AQ. Hence, Q cannot have a monolith and is therefore not subdirectly irreducible. • Lemma 1.2.14. Let B be in V and S be an irredundant basis of B. If \B\>a> and \S\ < 3, then Q can be embedded into B. Proof. As |S| < 3 and |B| > co, there exists s in S such that SgB({j})| > co. Note that since / undoes g and vice versa, SgB({s}) = { h " ( s )|h is in {/B,gB} and n is a positive integer} u {5}. Since V satisfies the identities in Statement (1.8), for all hi and A2 in {/B,gB} and positive integers n\ and «2.we have hnx1 (5) t s and (1.12) if h."1 (5) = h ^ { s ) then h \ = h i and n \ = n i 29 as otherwise jSgB({s})| < to. Let D = (sgB(W);/D,sD), where f D = /B to and g D = g B \ D . It is easier to work with Q, defined on page 28, than it is to work with D. Since / undoes g and vice versa, for all positive integers n , define f ~ n to be g n . We show that a Q^D,defined by (fD)q(s) if <7*0 s if q = 0 a{q) is an isomorphism and continue onward using Q in place of D. Statement (1.12) implies that a is injective. From its definition, a is surjective. To show that a is a homomorphism, we look at 3 cases, dependent upon what q is. Case 1 Assume that q is in £?/{-l,0,1}. «(yQ(«))=<»(4+i) «(sQ(«)) = <*(«-!) =(/°r'w = (/")«-'W =/D((/>)»(J)) = SD((/D)'W) =/"(«(?)) = «"(«(«)) Case 2 Assume that q is in {1, -1}. a(/Q0)) = «(2) a(g«(l)) = a(0) =5 =/D(/D«) = SD(/D(*)) =A«(i» = 8°(a(l)) Use a similar idea when q = - 1 . 30 Case 3 Assume that q = 0. a(/<>(0)) = a(l) «(§Q(0)) = «(-1) = f%) = gD(-s) = / D (a(0)) = g D (a(0)) As, D is a subalgebra of B and Q is isomorphic to D, we have just shown that Q can be • embedded into B. Theorem 1.2.15. The variety V ofalibi-unary algebras satisfying the identities (f°g){x) and (g o f)(x) « x is residually finite. Sketch of Proof. Let B be an algebra in V and S be an irredundant basis of B. Recall Lemma 1.2.12: If |S| > 3, then B is not subdirectly irreducible. Further, recall Lemma 1.2.14: If |£| > to and |S| < 3, then Q can be embedded into B and Q is not subdirectly irreducible. To continue, we use Lemma 2.2.6 on page 59, that will be proved in a later chapter. The lemma states that if Mi is a subalgebra of Bj and Bj is a subdirectly irreducible unary algebra then Mi is subdirectly irreducible. The contrapositive of this Lemma applied to Lemma 1.2.14 yields the following: if |B| > to and |S| < 3 then B is not subdirectly irre­ ducible. This implication together with Lemma 1.2.12 imply that if |2?| > to, then B is not subdirectly irreducible. Finally, we have shown that V is residually finite. • Theorem 12.16. The variety V of all bi-unary algebras satisfying the identities (f°g)(x)*x and (g o /)(jc) « x is not residually < N,for any positive integer N. Proof. Suppose that B is a singly generated finite member in V. Under these assumptions, the graph of B can best be described as a cycle. In particular, for a prime number p, the prime cycles Pp = ({0,l,2,...,p-l};/p>,*p'), 31 where f V p ( x ) = x + l(mod p ) and g P p ( x ) = x - l(mod p ) , are of interest. See Figure 1.4 for the graphs of P2, p3 and p5. The prime cycles are of interest because they are simple and hence subdirectly irreducible. Thus, since there exist infinitely many primes and V contains all prime cycles, V is not residually < N, for any positive integer N. Figure 1.4: The Graphs of the Prime Cycles Pj, P2 and p4 • Theorem 1.2.17. The variety V of all bi-unary algebras satisfying the identities (f°g)(x)*x and (g°f)(x) » x is not finitely generated. 32 Sketch of Proof. Notice that all of the prime cycles are singly generated. We can use this fact to show that V is not finitely generated. To do this, we use Lemma 1.3.3 on page 37, that will be proved in a later chapter. The Lemma can be used to show the following: for the finite unary algebra W, where \W\ = w, if U is a singly generated algebra in V(W), then |I/| < ww. Since V contains all prime cycles, there can exist no finite algebra that generates V. Therefore, V is not finitely generated. • Thus, V is a residually finite variety; however, V is neither residually < N, for any positive integer N, nor is V finitely generated. 13 Origin and Evolution of the Problem The Restricted Quackenbush Problem started as a more general question posed to others in an article by Quackenbush. The crux of the problem is to determine if residually finite implies residually < N, for some positive integer N. Around the time of the problem's conception, "very little was known ... about [the] residual smallness of specific varieties" and posing the problem "nicely exposed our [everyones] ignorance and caused a lot of work to be done" (McKenzie, [10]). 13.1 Quackenbush's Problem The earliest precursor of the Restricted Quackenbush Problem appeared in 1971: " The example given below shows that an equational class K can have the following property: (*) fC has infinitely many finite subdirectly irreducible algebras but no infinite ones. In the example below, fC is not generated by a finite algebra. Does there exist a finite algebra such that the equational class it generates has (*)? Can the algebra be of finite type; can it be a groupoid, semigroup, or group? " (Quackenbush, [15]) 33 Note that when discussing the number or amount of subdirectly irreducible algebras, Quackenbush implicitly means up to isomorphism. Although written in 1969, the article [14], by A. Ju. Ol'sanskii, can be used to an­ swer Quackenbush's problem, with respect to groups. Specifically, Ol'sanskii proves the following Theorem, Theorem 13.1 (Theorem 2, [14]). I f V i s a v a r i e t y o f f i n i t e l y a p p r o x i m a b l e g r o u p s , i t contains a finite group B such that any other group in V is embedded in some full direct power of B. As is described in his paper, a finitely approximable group is a residually finite group. Thus, Ol'sanskii's result can be restated as follows: If V is a residually finite variety, then there exists a finite group B such that V = ISP(B). Projection maps can be used to show that, up to isomorphism, the subdirectly irreducible algebras in ISP(B) are all in §(B). Thus, up to isomorphism, there exist only a finite number of finite subdirectly irreducible algebras in ISP(B). Therefore, Ol'sanskii showed that if V is a variety of groups, and hence an equational class of groups, that contains no infinite subdirectly irreducible algebras then V contains, up to isomorphism, a finite number of finite subdirectly irreducible algebras. That is, Ol'sanskii's result can be used to answer Quackenbush's question negatively for groups. Not long after the Quackenbush's problem was posed to the public, a more succinct version appeared in [17], We will call this version of Quackenbush's problem the Quacken­ bush Problem. Problem (Quackenbush Problem). Does there exist a finite algebra B such that V(B) con­ tains infinitely many finite subdirectly irreducible members but no infinite subdirectly irre­ ducible members? 34 We will show in the next section that the Quackenbush Problem can be rephrased as follows: Does there exist a finite algebra B such that V(B) is residually finite and not residually 4)) if and only if, for some n in Ilo, the algebra B satisfies ^ ( 6 1 , 6 2 , 6 3 , 6 4 ) . With regard to the Quackenbush Problem, Baldwin and Berman show "that there is no such variety with definable principal congruences" (Baldwin and Berman, [1]). Specifi­ cally, they proved that the Quackenbush Problem is answered negatively if the variety has definable principal congruences (Theorem 4). They prove this under the assumption that the variety is only residually small and not necessarily residually finite. Further, they do not assume that the variety is finitely generated. As McKenzie showed that all directly representable varieties have definable principal congruences, the Quackenbush Problem is settled negatively for Boolean algebras. See Chapter 3 §13 of [2] for a definition of a directly representable variety. See Chapter 5 §3 of [2] for a proof showing that a given variety being directly representable implies that the same variety has definable principal congruences. Further, Baldwin and Berman prove that if a variety is locally finite and has the congru­ ence extension property, then that variety has definable principal congruences (Theorem 3). 35 See the set of exercises in Chapter 2 §5 of [2] for a definition of the congruence extension property. Hence, if B is a unary algebra, then the Quackenbush Problem is answered neg­ atively, as all finitely generated varieties are locally finite and all classes of unary algebras have the congruence extension property. A few years later, in 1979,Taylor answered the Quackenbush problem negatively when V(B) is congruence-permutable and congruence-regular. The central theorem in Taylor's article [17] is that if B is a finite algebra, with V(B) being congruence-regular and congruencepermutable, and V(B) containing arbitrarily large finite subdirectly irreducible algebras, then it contains an infinite subdirectly irreducible algebra. As all rings generate congruencepermutable and congruence-regular varieties, the Quackenbush Problem is answered neg­ atively if B is a finite ring. That is, there does not exist a finite ring B such that V(B) contains infinitely many finite subdirectly irreducible members and no infinite subdirectly irreducible members. 132 The Reworded Quackenbush Problem In 1981, the wording of the problem changed; but, the crux of the problem remained exactly the same. The following rewording of the Quackenbush Problem appeared in [4]: Problem (Reworded Quackenbush Problem). Does there exist a finite algebra B such that V(B) is residually finite and not residually < N,for any positive integer N? We show, in an upcoming theorem, that the Quackenbush Problem and the Reworded Quackenbush Problem are equivalent problems. First, we require a few technical lemmas. 36 132.1 The Equivalence of the Quackenbush Problem and the Reworded Quackenbnsh Problem The following Lemma makes use of the free algebra of type J7 over the set of variables X - {*}"=, in the variety V. This special algebra is denoted by Fy(X). Though much can be said of the free algebra, all we need to know is that Fy(X) is in V and that Fy(X) has the universal mapping property for V overX. That is, for all B in V and every map a-.X -*• B, there exists a homomorphism /3:Fy (X) -• B such that for all x in X , we have /3(3C) = a(x). Note that if a ( X ) generates B , then B is a homomorphic image of Fy(X). Another interesting property of the free algebra is stated as the following Lemma. Lemma 132. Let B be an algebra of type T. For any positive integer n, the free algebra of type T over a setX ofn variables FV(B)PO can be embedded into Blfll'X|. The previous Lemma is posed as an exercise on page 85 of §12, chapter 2 of [2]. For a complete description of the free algebra, see §10 and §11 of Chapter 2 in [2] or see Chapter 4.11 in [13]. Lemma 133. Let B = (B\T) be a finite algebra, where |B| = b, and let M be an algebra in V(B). IfM has a finite irredundant basis of size n then \M\ < bh". Proof Note that if B is trivial then every member in V(B) is trivial and the claim is true. Hence, we may assume that V(B) contains a non-trivial member. That is, we may assume that b > 1. For some positive integer n,let S = {si}"=] denote an irredundant basis of M and let Y = {yiljLi ^ a set n variables. Recall that fV(b)(5f) has the universal mapping property. 37 Define a - Y - * S by a(j,) = Si. By the universal mapping property, there exists a homomorphism /3:FV(B)(F)~M such that P (yi)= Si for all 1 < i < n . Note that as M is generated by 5, every member of M is equal to some term real­ ized in M and applied to members of S. That is, for all m in M, there exists at least one term tm(yx ,y2,.. .,y„) of type T over Y = {y,}"=1 such that t%(si,s2, ...,s„) = m. Therefore, for all m in M, we have P (fmV(B)(K) (5*1 J2> • • • Jn)) = f m ( P ( y i f a ) , •• •,P(Jn)) = tm(shs2,---,Sn) = m. Thus, /3 is a surjective homomorphism. Using Lemma 1.3.2, we obtain the following sequence of inequalities: Ni|fv(B)(F)U|B||S|l" = iB||fir=f^This proves the lemma. • Corollary 13.4. Let B = {B\T) be a finite algebra of finite type. For any positive integer n, there exists only a finite number of members inV(B),upto isomorphism, that are minimally generated by n elements. Proof. Let |B| = b. By hypothesis, we have |^| < co and b<(o. For each / in T , let r ( f ) denote the arity of /. Note that if K is a finite set that contains exactly k elements, then there exist kkP distinct p-ary operations that can be defined on K. Thus, up to isomorphism, there can exist at most ]~[ k ^ ( f ) algebras of type T (1.13) that have a universe with cardinality k. 38 Using Lemma 1.3.3, if M in V(B) is minimally generated by n elements then \M\ < bb". Therefore, using Statement (1.13), there can exist, up to isomorphism, at most k=lf& members of V(B) that are minimally generated by n elements. As all constants are finite, the claim is proven. • The next Lemma yields some insight into a finitely generated variety being residually < N, for some positive integer N. Lemma 135. Let B be a finite algebra of type T that generates a residually finite variety. The variety generated by B contains finitely many finite subdirectly irreducible members, up to isomorphism, if and only ifV( B) is residually < N,for some positive integer N. Proof. Since B generates a residually finite variety, all subdirectly irreducible algebras in V(B) are finite. If V(B) contains finitely many finite subdirectly irreducible members, up to isomorphism, then take the subdirectly irreducible member with maximum cardinality and add 1 to determine the residual character of the variety. Now suppose that ¥(B) is residually < N, for some positive integer N. Let |fi| = b and Y denote a set of N variables. Since FV(B)(^) has the universal mapping property, every algebra in V(B) with a universe of cardinality less than or equal to TV is a homomorphic image of FV(B)(y). Thus, by the assumption that V(B) is residually < JV, for some positive integer N, all subdirectly irreducible members in V(B) are members in H(FV(B)(JO)- By Lemma 1.3.3, we know that |/V(B)(*0I ^ ^• Hence, up to isomorphism, H(FV(B)(K)) contains a finite number of algebras. That is, V(B) contains finitely many finite subdirectly irreducible members, up to isomorphism, • We now have all that is needed to show that answering the Reworded Quackenbush Problem answers the Quackenbush Problem and vice versa. 39 Theorem 13.6. The Reworded Quackenbush Problem and the Quackenbush Problem are equivalent. Proof. If the Reworded Quackenbush Problem is answered no then there does not exist a finite algebra B that generates a variety that is residually finite and not residually < N, for any positive integer N. Therefore, for any finite algebra M, if the variety V(M) is residually finite, then V(M) residually < N, for some finite N. Thus, using Lemma 1.3.5, if V(B) contains no infinite subdirectly irreducible members, then it contains finitely many finite subdirectly irreducible algebras. That is, the Quackenbush Problem is answered no. If the Reworded Quackenbush Problem is answered yes, then there exists a finite alge­ bra B such that V(B) is residually finite and not residually < N. Using Lemma 1.3.5, there exists infinitely many finite subdirectly irreducible members in V(B), but, no infinite ones. That is, the Quackenbush Problem is answered yes. • Therefore, since the Quackenbush Problem and the Reworded Quackenbush Problem are equivalent, we may state them interchangeably. 1322 Before the Reworded Quackenbush Problem Although the Reworded Quackenbush Problem was asked in 1981, a paper published in 1964 by Foster and Pixley [3] can be used to answer the problem if V(B) is congruencedistributive, as pointed out by Kearnes and Willard in [8]. Specifically, Theorem 2.5 of [3] can be used. We state Theorem 2.5 without proof and proceed to show that this theorem can be used to answer the Reworded Quackenbush Problem if ¥(B) is congruence distributive. Theorem 13.7 (Theorem 2.5 of [3]). If B is congruence distributive and B is isomorphic to a subdirect product of algebras where n is a positive integer, then every homomorphic image of B is isomorphic to a subdirect product of homomorphic images of 40 the Bj. Notice that Foster and Pixley's theorem is only applicable to congruence-distributive algebras that are isomorphic to a subdirect product of a finite number of algebras. The following well known Lemma, will help to deal with this problem. Lemma 13.8. Suppose that B is a finite algebra. If M is a member in V(B) and |M| is finite, then M is a member in HSP^„(B). For the proof of the upcoming theorem, we will need to know what a directly inde­ composable algebra is. A directly indecomposable algebra is one that is not isomorphic to a direct product of two non-trivial algebras. They are related to subdirectly irreducible algebras in that all subdirectly irreducible algebras are directly indecomposable; but, the converse is not necessarily true. In the proof of the following Theorem, we make use of Foster and Pixley's Theorem 2.5 in [3], or Theorem 1.3.7, to show that Reworded Quackenbush Problem is answered nega­ tively with respect to congruence-distributive algebras. Theorem 135. The Reworded Quackenbush Problem is answered negatively with respect to congruence-distributive algebras. Proof. Let B be a finite algebra and assume that V(B) is residually finite and congruencedistributive. We show that, under this assumption, the variety generated by B is residu­ ally < N, for some positive integer N. Doing this implies that the Reworded Quackenbush Problem is answered negatively. If B is the trivial algebra then V(B) contains only trivial algebras. Thus, we may assume that B is not the trivial algebra. By Tarski's HSP Theorem, on page 17, we have V(B) = HSP(B) = H(S(P(B))). 41 As B is not trivial, the only algebra in P(B) that is possibly directly indecomposable is B. The contrapositive of subdirectly irreducible implies directly indecomposable yields the following: with the exception of possibly B, all algebras in P(B) are not subdirectly irreducible. Suppose that M is a subdirectly irreducible member in S(P(B)) and that M is not a member in P(B). For some index set I,the algebra M is a subalgebra of B7. As homomorphisms preserve subalgebras, for all i in I, we have p,(M) is a subalgebra of B, where pi is the ith projection map on M. Note that M M be this homomorphism. We have just shown that M = |a(p;(S))|<|p;(S) | < l 4 Thus, all subdirectly irreducible members in H^S(P(B)) j have universes with cardinality no greater than |5|. That is, V(B) is residually < |B|. • As all lattices can be shown to generate congruence-distributive varieties, using a Mal'cev condition, the Reworded Quackenbush Problem is answered negatively if B is a lattice. Fur­ ther, as all n-Post algebras, Boolean algebras and Heyting algebras can be shown to gener­ ate arithmetical varieties and hence congruence-distributive varieties, using a Mal'cev like condition, Quackenbush's problem is answered negatively if B is a n-Post algebra, Boolean algebra or a Heyting algebra. Even though the Quackenbush Problem has been dealt with by Foster and Pixley in 1964, a paper by Jonsson [7], written in 1967, can also be used to answer the Reworded Quackenbush Problem, with respect to algebras that generate congruence-distributive vari­ eties. In Jonsson's paper, Corollary 3.4 states that if B is finite and V(B) is congruencedistributive, then every subdirectly irreducible member in V(B) belongs to HS(B). There­ fore, V(B) is residually less than |fi|. This is a stronger result than that obtained by an­ swering the Reworded Quackenbush Problem. Specifically, J6nsson's result reveals that all congruence-distributive varieties that are generated by a finite algebra are residually < N, for some positive integer N. Not only this, Jonsson's result gives the location, with respect to the class operations H, § and P, of the subdirectly irreducible members. It is interesting to note that in [1], Berman and Baldwin define and utilize the residual character of a variety. For example, they define and use the terms residually < N and resid43 ually small. However, they do not use these terms when stating Quackenbush's Problem. That is, the tools to state the Reworded Quackenbush Problem were around in 1975; but, were not used to do so until 1981 in an article by Freese and McKenzie, [4], 1323 After the Reworded Quackenbush Problem Theorem 8 of [4] shows that for an algebra B of size m, if B is in a congruence-modular variety then V(B) is residually small if and only if V(B) is residually < ( £ + 1 ) \ - m + 1, where . In other words, the Reworded Quackenbush Problem is answered negatively if B generates a congruence-modular variety. As congruence-permutable implies congruence-modular and all varieties of quasigroups are congruence-permutable, the Reworded Quackenbush Problem is answered negatively for quasigroups. During the same year, McKenzie answered the Reworded Quackenbush Problem neg­ atively when B is a semigroup. See Theorem 30 of [9]. In this article, McKenzie does more than just answer the Reworded Quackenbush Problem, he determines conditions for a variety of semigroups to be residually small. In 1982, McKenzie proved that any locally finite and residually small variety of Kalgebras is residually < N, for some positive integer N. See Theorem 8.1 in [10]. For a definition of a A'-algebra, see [10]. An example of a finite algebra that generated a residually finite variety that was not residually < N, for any positive integer N, was found in 1996 by McKenzie in [12]. That is, McKenzie found an example of an algebra that could be used to answer the Reworded Quackenbush Problem affirmatively. In his own words, he "destroy[ed] the Quackenbush Conjecture" (McKenzie, [12]). 44 133 Dealing with the Destruction of Quackenbush's Problem Though the Reworded Quackenbush Problem, and hence the Quackenbush Problem, was answered by McKenzie, the examples used to achieve this answer were algebras of infinite type and "there is no obvious way to convert them into algebras of finite type with the same residual bound" (McKenzie [12]). Hence, a new problem can be asked. The following problem is taken from [8]: Problem (Restricted Quackenbush Problem). L e t B b e a finite a l g e b r a o f finite t y p e . I f Y ( B) is residually finite, must V(B) be residually < N.for some positive integer N? How is the Restricted Quackenbush Problem related to the Reworded Quackenbush Problem and hence the Quackenbush Problem? The following Lemma answers this ques­ tion. Lemma 13.10. If the Reworded Quackenbush Problem is answered negatively for a class of algebras then the Restricted Quackenbush Problem is answered affirmatively for that class of algebras. Proof. Suppose that the Reworded Quackenbush Problem is answered no for a class of algebras fC. That is, there does not exist a finite algebra B in K, such that V(B) is residually finite and not residually < N, for any positive integer N. Hence, for all B in K, if V(B) is residually finite then V(B) is residually < N, for some positive integer N. That is, the Restricted Quackenbush Problem is answered yes for the class of algebras K,. • Note the that the inverse of the previous Lemma is not necessarily true. Suppose that the Reworded Quackenbush Problem is answered yes for a class of algebras K. Un­ der this assumption, there exists a finite algebra B in K such that V(B) is residually fi­ nite and not residually < N, for any positive integer N. This finite algebra, like McKen45 zie's, may not be of finite type. That is, B may not satisfy the hypothesis of the Re­ stricted Quackenbush Problem and hence, an answer to the Restricted Quackenbush Prob­ lem with respect to the algebras in fC is not immediate. During 1999, in the article [8], Kearnes and Willard proved that the Restricted Quacken­ bush Problem is answered affirmatively when V(B) is congruence-meet-semidistributive. Specifically, they answer Pixley's Problem (Theorem 4.1). Pixley's Problem is similar to the Restricted Quackenbush Problem and can be used to answer it. The authors point out that due to meet-semidistributivity, the Restricted Quackenbush Problem is answered affir­ matively with respect to algebras that include a semilattice operation. 1.4 Restatement of the Problem The problem of interest is the Restricted Quackenbush Problem. Problem (Restricted Quackenbush Problem). Let B be a finite algebra of finite type. IfV(B) is residually finite, must V(B) be residually < N,for some positive integer N? This problem has been answered with respect to many popular algebras: groups, Heyting algebras, lattices, quasigroups, rings and semigroups. The problem has also been answered when V(B) satisfies certain properties: being congruence-distributive, being congruence-modular, being congruence-permutable or having definable principal congru­ ences. Even with all of this work done, the problem, to date, remains open when consider­ ing an arbitrary algebra. In Chapter 2, we give an explicit proof showing that the Restricted Quackenbush Prob­ lem is answered affirmatively with respect to unary algebras. Then our attention turns to groupoids. Specifically, in Chapter 3, we show that groupoids that generate a residually finite variety must satisfy an identity of a particular form. Then, in Chapter 4, we look at 46 absorbing groupoids and show that if a certain property holds then the Restricted Quackenbush Problem is answered affirmatively. Lastly, in Chapter 5, a summary of what was done in this thesis is given and some questions are posed to the reader. 47 Chapter 2 Unary Algebras and the Restricted Quackenbush Problem Amongst other results, Baldwin and Berman, in [1], show that for B, a finite unary alge­ bra of finite type, if V(B) is residually finite then V(B) is residually < N, for some positive integer N. That is, they show that the Restricted Quackenbush Problem is answered affirma­ tively, with respect to unary algebras. In Subsection 1.3.1 Quackenbush's Problem, on page 35, are details as to how Baldwin and Berman showed their result. In particular, Baldwin and Berman make use of all unary algebras having the Congruence Extension Property. In this chapter, we show that the Restricted Quackenbush Problem is answered affirma­ tively, with respect to unary algebras without the explicit use of the Congruence Extension Property. As an introduction to unary algebras, the first section of this chapter will present Yoeli's result on connected subdirectly irreducible mono-unary algebras. These algebras are easy to describe and have a nice visual representation. Since there are subdirectly irreducible mono-unary algebras that are not connected, Yoeli's result is not sufficient to answer the Restricted Quackenbush Problem for mono48 unary algebras. The remaining sections provide an explicit proof to show that the Restricted Quackenbush Problem is answered affirmatively for arbitrary unary algebras. 2.1 Yoeli's Result A 1967 article [19], by Yoeli, can be used to visually classify all connected subdirectly irreducible mono-unary algebras. To state Yoeli's result, we need to make use of his defini­ tions. Definition (Yoeli, [19]). A finite mono-unary algebra B is connected if the corresponding graph is connected. Alternatively, a finite mono-unary algebra B = ( B \ /B) is connected if for all b \ and b 2 in B there exists positive integers n\ and ni such that (/")"'(t 0 = ( / * ) " ' ( h ) Definition (Yoeli, [19]). A finite mono-unary algebra B is irreducible if whenever B can be embedded into a direct product of two other mono-unary algebras, suppose Bj and B2, then either B can be embedded into Bi or B can be embedded B2. We show that Yoeli's definition of irreducible and our definition of subdirectly irre­ ducible are equivalent properties of a finite mono-unary algebra. We need the following technical Lemma. Lemma 2.1.1. Let B and M be finite algebras of the same type. Suppose that B can be embedded into M1, for some infinite index set I. Then B can be embedded into MJ for some finite index J. 49 Proof. Suppose that \B\ = b and \M\ = m. Let a be the embedding of B into M7. Since B is finite, the algebra a(B) is also finite. Thus, |a(B)| = b. Enumerate the elements in a(B) by {cij}bj=l and consider the relation T={(a;(0)y 6/}- =ll' Note that |T | < mb < (o. Now define the relation a on / as follow: for all i\ and i2 in /, b b let { i \ , i i ) be in a if and only if (a;(i \ ))J=l = ( a j ( h ) ) ^ x • The relation r can be shown to be an equivalence relation. Then, since r is a finite relation, the collection I jo must also be finite. using the mapping /3: a(B) -*• M1/0 We will show that a(B) can be embedded into where for all aj in a(B), we have (/3(aj))(i/a) =aj(i). Then, since B = a(B) and //a is a finite collection, the claim will be proved. Thus, to complete the proof, we verify that /3 is well-defined and injective and is a homomorphism. Note that if for some a j in a ( B ) , and i \ j o and i i j o in I / o such that i \ / o = i i j a , then aj(i\) = aj(i2) and hence, ( (P(<*j))(ii/o) = aj(.h)=aj(i2) = P(aj))(i2/a). Thus, j3 is a well-defined map. Let ay, and a72 be in a ( B ) such that j3 (a,,) = /3 ( a j 2 ) . Hence, for all i j o m l j o , we have Thus, for all i / a in //a and hence all i in I , we have a/,(i) = a j 2 ( i ) . That is, a jx - a j 2 . Therefore, /3 is injective. Let / be an n-ary operation symbol in the language of B and M. Further, let ajx,..., ajn 50 be n-elements from a ( B ) . For all i / o in 7/cr, we have ( p ( / a ( B ) ( « / , , • • • ,a j n ) ) ) ( i / o ) = ( / a ( B ) ( a h , . . . , a j n ) ) ( i ) = (fM'(ajv-iajn))(i) = / M ( a yi(0,--->ay„(0) = f M ( { P ( a h ) ) ( ' / a ) » • • •» ( P ( a J n ) ) ( i / a ) ) = ( / M ' / a{ P ( a h ) , - i P ( a h ) ) ) ( i / ° ) Thus, /3 is a homomorphism. • Lemma 2.12. Let B = ( B ; f B ) d e n o t e a finite n o n - t r i v i a l c o n n e c t e d m o n o - u n a r y a l g e b r a . The algebra B is subdirectly irreducible if and only if B is irreducible. Proof. We start by showing that if B is subdirectly irreducible then B is irreducible. We do this by proving the contrapositive. Suppose that B is not irreducible. That is, there exists mono-unary algebras Mi and M2 such that B can be embedded into Mi x M2; but, B cannot be embedded into either Mi or M2. Assume that B is isomorphic to M, where M is a subalgebra of Mi x M2. For the first and second projection maps on M, denoted by p1 and p2 respectively, let 6 =ker(pi)nker(p2) and note that 6 is in Con M as 9 is the meet of two congruences. As M cannot be embedded into Mj or into M2, there does not exist an injective ho­ momorphism from M to Mi or from M to M2. Therefore, pi and P2 are not injective. Hence, ker(pi) does not equal AM and ker(P2) does not equal AMLet F = ((WI,W2>,{FFI3,M 4 )}. 51 be an element in 6. As / is an element in ker(pi), we have m\ = m3. Similarly, as t is an element in ker(p2), we have mi = m4. Therefore, 0 £ and hence 6 = AM. Thus, 8 is a meet of two non-A^ congruences that equates to AM- That is, no monolith can exist. Therefore, B is not subdirectly irreducible as M is not subdirectly irreducible. For the reverse implication, assume that B is irreducible. We want to show that B is subdirectly irreducible. That is, we want to show that, if for some index set/, if o r B - + ] ~ I B , id is a subdirect embedding then there exists i in / such that B = B / . Since a is a subdirect embedding, for all i in 7, the image of the ith projection map applied to a(B) is B/. Thus, each Bj is a homomorphic image of a(B). As a(B) = B and B is a finite algebra, there are at most a finite number of homomorphic images of a(B). For the positive integer n,let the members of {D }" 7 =1 denote the distinct homomorphic images of a(B). We have implicitly just shown that []B,s /€/ fl(Dy)^ 7=1 where I, = {i e /: B , s D , } . n n *s Hence, there exists an embedding from B to I~[(®/)/;and B is irreducible, 7=1 by repeated application of the definition of irreducible, we must have an embedding from B into (Dj)1' for some j between 1 and n, inclusive. By Lemma 2.1.1, there exists a finite subset I'j of Ij such that B can be embedded into (D ) >. Again by repeated application y 7 of the definition of irreducible, there must exist an embedding from B into D . Therefore, ; |B| < |D7|. Since Dj is a homomorphic image of B, we must have \B\ >\Dj\. Hence, the embedding from B into D is an isomorphism, as |B| = \Dj\. Thus, B is subdirectly irre­ y ducible. • Yoeli proved that the graph of a connected and irreducible mono-unary algebra is lim­ ited to a finite number of possible general shapes. To state Yoeli's result, we need to identify two classes of mono-unary algebras. Denote the mono-unary algebra of size p n 52 whose graph is in Figure 2.1 by , where p is a prime number and n is a positive integer, and denote the mono-unary algebra of size h whose graph is in Figure 2.2 by J/,, where h is a positive integer greater than 1. Figure 2.1: The Graph of Hp* Figure 2.2: The Graph of J/, Recall, from the previous lemma, that a finite mono-unary algebra is subdirectly irre­ ducible if and only if it is irreducible. We now state Yoeli's result. Theorem 2.13 (Yoeli, [19]). A finite connected non-trivial mono-unary algebra B is irre­ ducible if and only if B is isomorphic to Hp» or to J/,, where p is a prime number, n is a positive integer and h is a positive integer greater than 1. Notice that Yoeli's result only deals with connected mono-unary algebras. With respect to mono-unary algebras, Yoeli's result needs to be generalized to include algebras that are not connected, to be helpful in answering the Restricted Quackenbush Problem. In the following sections, we construct a model of what finite subdirectly irreducible 53 unary algebras look like. Loosely, their corresponding graphs look like part of a circulatory system. This model is then used to answer the Restricted Quackenbush Problem. 22 Connected, Pseudoconnected and Disconnected Unary Algebras The class of all finite unary algebras are partitioned into three subclasses, based on the appearance of each unary algebra's corresponding graph, to assist in determining which finite unary algebras are subdirectly irreducible. In this section, we define three subclasses of unary algebras, that union to the class of all unary algebras, and show that only one class needs to be explicitly considered, when answering the Restricted Quackenbush Problem. For the remainder of this subsection assume that B = (B\F) is a unary algebra of finite type. A unary algebra B can be viewed as a directed multi-labelled graph. Let G(B) denote the undirected multi-graph that is obtained by removing the direction and labels from the directed multi-labelled graph corresponding to B. Say that there is a walk from b\ to bz in B if and only if there is a path from b\ to bi in G(B), Example. Looking at the undirected multi-graph G(E6) that corresponds to E6, displayed in Figure 2.3, there exists a walk from 1 to 2. In fact, for all e\ and e2 in E$, there exists a walk from e\ to ei. We can use a walk, from one member of B to another, to define an equivalence relation that will later help in the classification of all finite subdirectly irreducible unary algebras of finite type. Define the equivalence relation UB on B by relating b\ to bi if and only if there exists a walk from b\ to bi. 54 Lemma 22.1. Each equivalence class oflZs is a subuniverse of B. Proof. Let T be an equivalence class of 7Z g . Further, let / be any operation symbol in T . To prove the Lemma, we must show that for all t in T, the element fB(t) is in T as well. Since there exists a path from t to fB(t) in G(B), the elements / and fB(t) must belong to the same equivalence class. Hence, fB(t) is an element in T . • Definition. If there is only one distinct equivalence class of 7ZB , then B is said to be con­ nected. If there are exactly two distinct equivalence classes on 7ZB, such that at least one equivalence class has unit cardinality, then B is said to be pseudoconnected. Otherwise B is said to be disconnected. Applying Lemma 2.2.1, if B pseudoconnected, then there exist two proper connected subalgebras, Bi and B2, such that B\ = B and at least one of Bi and B2 is trivial. Example. See Figure 2.3 for E6, an example of a connected algebra. See Figure 2.4 for E7, an example of a pseudoconnected algebra. See Figure 2.5 for Eg, an example of a discon­ nected algebra. Figure 2.3: A Connected Unary Algebra E6 and Associated Undirected Multi-Graph G(E6) 55 2 JL ' C0.: '% ' Figure 2.4: A Pseudoconnected Unary Algebra: E7 Figure 2.5: A Disconnected Unary Algebra: Eg 56 2.2.1 Subdirectly Irreducible Implies Connected or Pseudoconnected Of connected, pseudoconnected and disconnected unary algebras, which class contains subdirectly irreducible algebras? We show that all subdirectly irreducible unary algebras must either be connected or pseudoconnected. An understanding of congruences that are present in a disconnected unary algebra is necessary. Lemma 222. If M is a subalgebra of B and 6 is a congruence on M then CgB(0) = 0 u AB Proof. We show that 8 u Ag is a congruence on B. Then, since 8 u Ag is the the smallest binary relation on B that contains 8, we obtain the desired result. The binary relation 8 u Ag is certainly reflexive and symmetric. To complete the proof, we must show that 0 u Ag satisfies the transitive property and the compatibility property. Let ( b \ , b i ) and (62,^3) be elements in 0 u Ag. Suppose that both (61,^2) and {62,63) are in 6. Since 8 is transitive, we obtain the following: {bi,bi) 6 8 £ 8 uA#. Now, without loss of generality, assume that { b \ , b i ) is in AB - Then b \ = b i and hence ( b \ , 63) is in 0 u AB. Therefore, 8 u Ag is transitive. Let / be an operation symbol in T. Suppose that (b\, 62) is in 8, which implies that b\ and bj are in M and hence B. As 8 satisfies the compatibility property, we have (fB(bi),fB(b2)) = (fM(bi),fM(b2)) € 8 c 0uAB. Now suppose that ( b \ , b i ) is in Ag. As b \ = b j , we must have f B { b \ ) = /B(^2). Hence, {/B(^i),/B(M)eABc0uAB. Therefore, 8 uAg satisfies the compatibility property. 57 • In the proofs of the next few lemmas, we use the following set equality: for the sets A, B, C and D, (Anfl)x(CnD) = (AxC)n(BxD). (2.1) Lemma 223. If there exist at least two distinct equivalence classes in 71B such that neither have unit cardinality then B is not subdirectly irreducible. Proof. By Lemma 2.2.1, there exist two distinct connected subalgebras, Bj and B2, of B such that B\ nS2 = 0- Further, |fii| > 1 and \Bi\ > 1. By Lemma 2.2.2, we have CgB(Si2 ) A ConBCgB(fi22) = ( B l u A 2 fi)n(B2 2uAfl) = (B12nB22)uAfi = (fiin£2)2uAfl = 0 2 uA s = AB and neither CgB(fii2) nor CgB(S22) is Ag. Hence, B is not subdirectly irreducible. • Lemma 2.2.4. If there exists at least three distinct equivalence classes of 11% such that two of them have unit cardinality then B is not subdirectly irreducible. Proof. By hypothesis, there exist at least three distinct connected subalgebras, Bi, B 2 and B3, of B such that {61,^,63} is a mutually disjoint collection of subuniverses of B and two of the subalgebras are trivial. Without loss of generality, assume that Bi and B2 are trivial. Let B\ = {b\} and fi2 = {62}By Lemma 2.2.2, we obtain the following: CgB ((B! u f i ) ) A ConBCgB ((B 1 u f i ) ) = ( ( B i u B 2 ) 2 n ( B l U B 3 ) 2 )U A B . 2 2 3 58 2 By Statement (2.1), (fli u52)2 n(Si u B3)2 = ((Bi uB2)n(Bl uB3)f = B\2 Thus, C ^ ( ( B { u B 2 ) 2 ) AConBCgB((51 u B 3 ) 2 ) = A B . Since both CgB((Si UB2)2) and CgB((Z?i ufl3)2) are non-Ag congruences, but, meet to AB, we have shown that B is not subdirectly irreducible. • Theorem 225. If B is subdirectly irreducible, then B is connected or pseudoconnected. Proof. We prove the contrapositive of the claim. Assume that B is disconnected. We must show that, under this assumption, B is not subdirectly irreducible. As B is disconnected, there exist two possible cases. Either there exist at least two distinct equivalence classes in TZB, such that neither have unit cardinality, or there exist at least three distinct equiva­ lence classes in 11b, such that two of them have unit cardinality. Lemma 2.2.3 implies that the former case does not yield a subdirectly irreducible algebra while Lemma 2.2.4 implies that the latter case does not yield a subdirectly irreducible algebra either. • 2.22 Correspondence of Connected and Pseudoconnected Unary Al­ gebras We show that every pseudoconnected subdirectly irreducible unary algebra is the disjoint union of the trivial unary algebra and a connected subdirectly irreducible unary algebra. Lemma 22.6. Let M be a subalgebra of B. If B is subdirectly irreducible, then M is subdirectly irreducible. 59 Proof. We prove the contrapositive. Suppose that M is not subdirectly irreducible. We want to show that B is not subdirectly irreducible. Let T = (Con M)\{A M }As M is not subdirectly irreducible, no monolith can exist and hence A 0 = f l 0=AM. OiT BzT <2-2> Further, since M is not subdirectly irreducible, |F|>2. (2.3) Notice that for all 6 in T, we have 6 t AM - Thus, applying Lemma 2.2.2, we obtain the following: CgB(0)*Afl. (2.4) By Lemma 2.2.2 and Statement (2.2), ACgB(9)= MeuAB) OeT 8eT = d(0uaB) 8eT =(n ®)uAs = A^uAb = A BThus, the above meet of congruences equates to AB - By Statement (2.3), the above meet of congruences involves at least two non-trivial congruences. By Statement (2.4), none of these congruences are As. Thus, B cannot possibly have a monolith. Therefore, B is not subdirectly irreducible. • Suppose that B is pseudoconnected. Recall that under this assumption, there exist two proper connected subalgebras, Bi and B2, such that B\ uBj = B and at least one of Bj and B2 is trivial. Without loss of generality, assume that Bi is trivial. 60 Lemma 2.2.6 implies that if B is subdirectly irreducible, then B2 is a connected subdirectly irreducible subalgebra. Thus, if there exist, up to isomorphism, a finite number of subdirectly irreducible connected algebras in a variety, then there exist, up to isomorphism, a finite number of subdirectly irreducible pseudoconnected algebras in the variety. Hence, from here, we focus on connected unary algebras. 23 Every Unary Algebra in a Finitely Generated Variety Has an Irredundant Basis To continue looking at subdirectly irreducible unary algebras, we look at their irredundant bases. A problem arises: which unary algebras have at least one irredundant basis, finite or infinite? Example. Consider the mono-unary algebra E9= {E g \ f E 9), where E g is the set of nonpositive integers and e +1 if e * 0 0 if e = 0. f9(e) = - The algebra E9 is one of the subdirectly irreducible mono unary algebras looked at, by Wenzel, in [18]. The algebra E9 does not have an irredundant basis, finite or infinite. See Figure 2.6 for the graph of E9. Figure 2.6: A Unary Algebra Without an Irredundant Basis: E9 61 Showing that each member in a finitely generated variety has at least one irredundant basis will be enough for our purposes. Suppose that B is an algebra in some finitely generated variety. We show that each member in the universe of B belongs to at least one maximal singly-generated subuniverse, in the following sense: if b\ generates a maximal singly-generated subuniverse of B and b2 is in B such that b\ is in SgB({&2}) then SgB({fci}) = SgB({Z?2})- We do this by using Zorn's Lemma, which requires the definition of a chain. Definition (Burris and Sankappanavar, [2]). A chain of sets C is a family of sets such that for each set C\ and C2 in C either Ci Q C2 or C2 £ C\. We state Zorn's Lemma as it appears in [2], without proof. Lemma 23.1(Zorn's Lemma). I f F i s a n o n - e m p t y f a m i l y o f s e t s s u c h t h a t f o r e a c h c h a i n C of members ofF there is a member ofF containing [JC then F has a maximal member. Note that Zorn's Lemma is equivalent to the Axiom of Choice. Lemma 232. Let B be a unary algebra contained in some finitely generated variety of type T. For all members b in B, there exists a maximal singly-generated subuniverse of B that contains b. Proof Let K denote the set of all singly-generated subuniverses of B that contain b. The collection JC is non-empty as Sg®({6}) is in JC. To complete the proof, we will show that fC has a maximal element, using Zorn's Lemma. Let C be a chain of elements from K. By hypothesis, there exists an algebra M such that B is in V(M) and |M| = m, for some positive integer m. Note that for all C in C, the unary algebra (C; T) is a member in the variety generated by B and hence is a member in the variety generated by M. Hence, by Lemma 1.3.3, on page 37, all singly-generated subuniverses in C can contain at most mm elements. 62 (2.5) To complete the proof, we show that (J C is equal to one of the members in C. By CeC Statement (2.5), we obtain the following: max{|C| |CeC} ° = ({1,2,3,4,5,6,7};^) is the heart of Eio- A Figure 2.7: A Connected Unary Algebra with a Heart: Eio As we show in the following theorem, to determine what the heart of a unary algebra is, rather than finding all of the maximal singly-generated subuniverses, we may look at the subuniverses generated by each member in any irredundant basis. Theorem 2.4.1. Let B be a unary algebra that has a heart and for some index set I, let {M, }i€/ denote the set of members of B that generate maximal singly-generated sub- 65 universes. Further, for some index set J, let S = {sj} j 1. For all t in 5, we must have |SgB({f})| > 1 as otherwise, using Statement (2.12), W = nsgB(W)ESgB({<}) = M seS and hence t would be generated by each individual member of S, contradicting the assump­ tion that S is an irredundant basis that contains at least 2 elements. By Lemma 2.2.2 and Statement (2.12), we have /\CgB^(SgB({s})) ) = Q((SgB(W)) uAflJ =(n(ssB(w))2)'juAs =(nsgB(w)) uab ,2 = {h}2 uAfl = ABTherefore, since |S| > 1 and, for all 5 in 5, since SgB({s})| > 1, the algebra B cannot possibly have a monolith and hence is not subdirectly irreducible. • 2.42 Veins of a Unary Algebra The subalgebra generated by a single member of an irredundant basis, used in the proof of Theorem 2.4.2, turned out to be helpful. We generalize this concept in the following 71 definition. Definition. Let B = { B \ T ) be a unary algebra and M be a member of V(B). Call each maximal singly-generated subalgebra of M a vein. Further, define a vein of V(B) to be a vein of some member of V(B). Example. In the algebra Eio depicted in Figure 2.7 on page 65, the subalgebra (sgE'»({0});r) is a vein of EJO - In fact, up to isomorphism, it is the only vein of EioRecall that by the proof of Theorem 2.4.1, the subuniverse generated by any member of any irredundant basis is maximal, with respect to singly generated subuniverses. We show that each member in the universe of a unary algebra that is a member of a finitely gener­ ated variety is a member of some irredundant basis if and only if it generates a maximal subuniverse. Lemma 2.4.4. Let B = (B^J7) be a unary algebra that is a member of a finitely generated variety. For all b in B, we have |SgB({&});jr| is a vein of B if and only ifb is a member of some irredundant basis ofB. Proof. We start with the forward implication. Let |SgB({i});Jr| be a vein of B. Further, let 5 be an irredundant basis of B. We are guaranteed the existence of an irredundant basis by Theorem 2.3.3. There exists an s in 5 such that SgB({i>})gSgB(W). By assumption, Sg ({6}) is a maximal subuniverse of B, with respect to singly generated subuniverses. Hence, sgB({i>}) = sgB(w). 72 Thus, (S\{s}) u { b } is an irredundant basis of B . The reverse implication was proved in Theorem 2.4.1. • The following Corollary gives information regarding the size of veins in a finitely gen­ erated variety. Corollary 2.45. Let B be a finite unary algebra of finite type, |fi| = b and M be a member ofV( B). The following statements are true. 1. Every vein of M has a universe with a cardinality less than or equal to bh. 2. There exists only a finite number of veins, up to isomorphism, o/¥(B). Proof. Recall that Lemma 1.3.3, on page 37, states that for all Mi in V(B), if M\ has an irredundant basis of size n, then |Mj| < bh". Thus, to prove Part 1 of the Corollary, apply Lemma 1.3.3 and note that every vein of M is a subalgebra of M and is singly generated. Recall that Corollary 1.3.4, on page 38 states that for any positive integer n, there exists only a finite number of members in V(B) that are minimally generated by n elements, up to isomorphism. Thus, for Part 2 of the Corollary, apply Corollary 1.3.4 and let n = 1. • 2.5 Orientation What happens when two isomorphic veins of a unary algebra overlap each other? In this subsection, we define what it means for two veins to overlap each other and show that, if the overlap is in some sense nice, then the resulting unary algebra is not subdirectly irreducible. Definition. Let B = ( B \ T ) be a unary algebra. Suppose that distinct elements b i and b j generate isomorphic veins of B and the intersection N of the veins is non-empty. Let Q be 73 a subalgebra of N. If for each q i n Q and each term t ( x ) of type T , tB(bi) = q tB(bj) = q, if and only if then the two veins of B, ( S g a n d ( S g are said to have the same orientation with respect to Q in B. Example. Consider Eio, depicted in Figure 2.7 on page 65, the subalgebra generated by {0} and {8} do not have the same orientation with respect to the subalgebra generated by {1,2,3,4,5,6,7} because, for example, /Elo(0) =2 and /El0(8) = l. Example. In E13, depicted in Figure 2.10, the subalgebra generated by {0} and {1} have the same orientation with respect to the subalgebra generated by {2,3,4}. This algebra is not subdirectly irreducible as the congruence generated by collapsing the elements 0 and 1 has nothing in common, outside of elements in A£I3, with the congruence generated by collapsing everything in {2,3,4}. We show, in the next lemma, that if a unary algebra with a heart has 2 distinct veins that have the same orientation with respect to the heart of the algebra, then the algebra is not subdirectly irreducible. Lemma 2.5.1. Let B = (B\T) be a unary algebra. Further, suppose that M is in V(B) and that HM exists and is non-trivial. Ifm\ and mi generate distinct veins of M that have the same orientation with respect to HM in M, then M is not subdirectly irreducible. Proof. By hypothesis, \HM\ > 1. Therefore, CgM((//M)2)#AM. 74 (2.13) Figure 2.10: A Connected Unary Algebra with a Heart that has Two Veins that have the Same Orientation with Respect to the Heart: E13 By hypothesis, mi is not equal to m2. Hence, CgM({(m1,m2)})*AM. (2.14) Suppose that {m^^ma) is inCgM({{mi,/n2)}). Then, by the Corollary 1.2.2 on page 11, for some positive integer n,there exist terms {f/}"=1 of type T such that "13 = ^(^1) <2M(»)=<3Mfe) <"iOy»-i )=<"(**) where for all 1 < i < n , we have {*,•,)>,'} = { m \ , m 2 } . Suppose that m $ is in H M . Thus, m 3 = ^(*1) where x \ is in { m i , m i } . As m i and 012 generate subalgebras of M that have the same orientation with respect to HM, the follow­ 75 ing equation is derived: ^(mi) = ^(m2). Therefore, all 1 < i < n, we can show that = ^(y). Using induction, for = tf*(yj). Therefore, under the assumption that m3 is in Hm, we obtain m3 = m4. Using a similar idea, we can show that if W4 is in //M then m-i = m4. That is, if one of 013 and m4 is a member of HM, then W3 = m4. Therefore, CgM({{m,,m2)})n(//M)2 = A M . W Thus, using Lemma 2.2.2, we obtain the following: CgM ( {{HM, /?I2)} ) A CON M CgM ( (Hm )2) = CgM({{mi ,m2)}) n ((/fM)2 u = ^ g ({(mi,m )}) n (HMf j u ^Cg ({ ( a ( >1 ) ) = rc'((2). That is, for all h in H M , if r C l ( t \ ) = h , then rc2(/2) = h . We can use a-1 to get the converse. Therefore, Ci and C2 have the same orientation with respect to HM in M. Theorem 2.72. Let B = • be a finite unary algebra of finite type. IfV(B) is residually finite then V(B) is residually < N,for some positive integer N. 81 Proof. To prove the theorem, we show that, for some positive integer m, every connected subdirectly irreducible member in V(B) must have less than m generators. We then show that there exist, up to isomorphism, a finite number of subdirectly irreducible members in V(B). To complete the proof, we take the cardinality of the universe of a subdirectly irreducible member in V(B) that contains the most elements, add one, and call the resulting integer N. Recall that by Theorem 2.4.2, on page 68, every connected subdirectly irreducible mem­ ber of V(B) has a heart. The heart of a unary algebra, assuming that it exists, is a subalgebra of every vein of that algebra. By Lemma 2.7.1, if M is a connected non-trivial algebra in V(B) that has a heart isomorphic to Hj and, for some i in /, the algebra M has rriij dis­ tinct veins isomorphic to V, , then there exist two distinct veins of M that have the same orientation with respect to HM. If HM is non-trivial then by Lemma 2.5.1, on page 74, M is not subdirecdy irreducible. If HM is trivial, then by the contrapositive of Lemma 2.4.3, on page 69, M is not subdirectly irreducible. Thus, if M is a subdirectly irreducible connected non-trivial algebra in V(B) that has a heart isomorphic to H;, then M can have at most -1 veins isomorphic to V,. Now let m * =max{m,-j-l 11 54 = 5. Example. The operation table for the groupoid E^'s operator *El6 is given in Table 3.3. The groupoid E16 is influenced by the partial order relation < of height 3, displayed as a Hasse diagram in Figure 3.3. The groupoid Ej^ is associative due to the property that the product of any three elements is 11. 86 7 * E 1S 0 1 2 3 4 5 6 7 0 7 3 7 7 5 7 7 7 1 7 7 4 7 7 7 7 7 2 7 7 7 7 7 7 7 7 3 7 7 6 7 7 7 7 7 4 7 7 7 7 7 7 7 7 5 7 7 7 7 7 7 7 7 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 5 3 0 Figure 3.2: The Partial Order Relation < that Corresponds to *El5 Table 3.2: The Operation Table of *E'5 *E16 0 1 2 3 4 5 0 6 8 8 6 8 8 1 8 7 6 8 7 6 2 7 7 8 7 7 8 3 6 8 8 9 11 11 4 8 7 6 11 10 9 5 7 7 8 10 10 11 6 11 11 11 11 11 11 6 11 • • 11 • 11 • 0 11 11 11 11 11 11 11 11 •• Table 3.3: The Operation Table of *E>6 87 11 1 2 3 4 5 Figure 3.3: The Partial Order Relation < that Corresponds to *E'6 Definition. Let B = (Z?;*B,2 *B^4- Let M = (M; *M) be a reduct of B to a groupoid. That is, let M = B and *M = *B. Lastly, let h = max{|C|: (C; b(t2*s/et4)If t\ = t% and t$ = t4, then t\ *s/e = ti *ste Now, without loss of generality, assume that t\ * ti. That is, assume that there exists elements s\ and in t\ and ti, respectively, such that b < s\ and bb*ASie} and K = B'\K. Further, let 4>= AfckfK See Figure 3.4 for a visualization of how B ! , S , K and K interact. The constant mapping from I to {As}, in B1, plays an important role in the following proofs. Denote this element by kB. Lemma 3.1.2. The following are true: 1. The element kg is a member of S. 2. For all b in B1, such that fa = ASjQ, we have { s € S - b < s } £ X B/ 9 . 91 3. The set KnS is contained in Xb / 6 . 4. For all t in TGYIFTNK* 0, then t = XB/ 6 . 5. l f t \ a n d t2 a r e i n TQ such that t\ n K 1 0 and ti^ K + . Thus, for all k in K, the pair for all keK there exists e t\ such that is in 0*. Therefore, k < uk. (3.2) Pick si in t \ and r in t . We will show that si * s r is in Ag/0. By doing this, we are showing that tx *s'et=Ysie. Using a similar idea, we will also obtain t * s ^ e t i = Ab/& and thus the proof will be complete. 93 Now to see that si *s r is in KB/6 suppose, for a contradiction, that s\*srikslQ. (3.3) Recall from Part 3 of Lemma 3.1.2 that KnS £ Ag/0. Thus si * s r i K n S ; As both si and r are in S, we have si *s r in S and hence, sj *s r is in K. By upward multiplication, for all i in /, we have s \ ( i ) < s \ (i) * B r ( i ) . Thus, si < si * s r . B y S t a t e m e n t (3.2), t h e r e exists r \ i n t \ s u c h that s \ * s r < r i . T h u s , f o r all i i n I , si(i)<{si *Sr)(i) . If t\ nK = 0 and t2nk = 0, then either t\ = t2 or S/6 is not subdirectly irreducible. Proof. By assumption tjnK = 0 for j in {1,2}. By Part 6 of Lemma 3.1.2, we have tj*fa/e. 95 (3.4) Lemma 3.1.3 and Lemma 3.1.4 imply that both T\ and T2, defined below, are congru­ ences: tj = { ( t j , X B / d ) , < Ab I 9 , t j ) } v As / 0 . Note that by Statement (3.4), neither t\ nor T2 are equal to &s/6- Thus, two possibilities emerge. Either the congruence blocks t\ and ti are equal or they are not. With regard to the latter scenario, since x\ at2 = &s/q and neither t\ = ks/e nor t2 = the algebra S/0 is not subdirectly irreducible. • Lemma 3.1.6. Suppose that S /8 is subdirectly irreducible and that there exist elements t\ and ti in TQ such that (ti,tz) " i" tfh * 0 and tif\k - 0, then there exists a unique element AG in TQ such that for all t in TQ, we have t*s/e ag = a0 and ,(r,ae)}uAs/e are congruences on S/0. Therefore, as r is distinct from a g and p e then S / 6 cannot be subdirectly irreducible due to the presence of two non-trivial congruences that meet to Asjq. H e n c e , f o r S / 0 t o b e subdirectly irreducible, w e m u s t h a v e fig = t . U n i q u e n e s s o f f i e has been achieved. • We have all of the ingredients to state the Theorem central to this subsection. That is, we are able to provide a partial description of the subdirectly irreducible members in varieties generated by groupoids that are influenced by a partial order relation. Theorem 3.1.7. Let B = (B; *B) be a non-trivial groupoid that is influenced by a partial order relation and suppose that M is in V(B). If M is subdirectly irreducible, then the following statements are true. 1. There exists a unique element a\f in M such that for all m in M, m * M a M = aM and = and there exists a unique element PM in M\{a,v/} such that for all m in M, and 97 f$M *M nt = am• mi mi m3 ... m|A*|-2 PM mi ? ? ? ... ? CtM «J2 ? ? ? ... ? O-M m3 ? ? ? ... ? O.M ? : m\M\-2 ? ? Aw OM O-M V-M 9 ? CfM aw CtM aw ? OM OM O-M OM aw CtM aw aw Table 3.4: The Operation Table of a Finite Subdirectly Irreducible Member in a Variety Generated by a Groupoid Whose Binary Operation is Influenced by a Partial Order Relation 2. The monolith of M is HM= {(<*M,PM) ,(PM,<*M)}V AM- Before the proof is given, note that Part 1 of Theorem 3.1.7 states that, for 1 < \M\ < o), the operation table of *M must look like the operation table given in Table 3.4. Proof Of Lemma 3.1.7. We start with Part 1 of the Theorem. By Tarski's 1HESP Theorem, Theorem 1.2.5 on page 17, for each M in V(B), there exists an index I and subalgebra S, such that S < B7, and there exists a 0 in Con S such that M = S/0. Hence, for the remainder of the proof we focus explicitly on S/0. To simplify notation, let TQ = S/0. Recall from Part 3 of Lemma 3.1.2 that K n S £ As/0. Note that if K = 0 then S = K n S . Thus, S c As/0. This implies that 5 = As/0. Therefore, if K = 0 then S/0 is the trivial 98 algebra. Since we are assuming that S/0 is not the trivial algebra, this means that K + exists. Suppose that for t \ and t i in 5/0, we have { t \ , h ) in . There exist a few possibilities regarding how t\ and tj interact with K. They are as follows. Possibility 1: Suppose that t\ r\K 10 and tir\K + 0. By Part 5 of Lemma 3.1.2, we have t\ = hPossibility 2: Suppose that t\ nK = 0 and t2<~\k = 0. By Corollary 3.1.5, we have t\ = h or S/0 is not subdirectly irreducible. Possibility 3: Without loss of generality suppose that t\ n K10 and ti n£ = 0. By Lemma 3.1.6, there exists a unique element AG in 5/0 such that for all t in TQ, we have t *s/0 ag = ag and there exists a unique element t*s/e pe = ae With respect to all (*i,f2) in and ag *s^e t = ag in 7e\{ae} such that for all t in TQ, we have and *s/et = ae. if only Possibility 1 and Possibility 2 occur then ei­ ther O = ASje or S/0 is not subdirectly irreducible. Note that if 4> = A s / e then |Jf| 4-1 as by definition, for all k in K , we have fa * A s / e . Thus, if = As/e then 4> is a meet of at least two non-AS/0 congruences that equates to A5/0. That is, S/0 is not subdirectly irreducible. For S/0 to be subdirectly irreducible and non-trivial, there must exist a pair such that, with respect to t\ and ti,Possibility 3 occurs. This proves Part 1. 99 i ,*2) in For Part 2, assume that S / d is subdirectly irreducible and not trivial. Part 1 of the T h e o r e m a n d L e m m a 3 . 1 . 4 i m p l y t h a t T , defined below, i s a c o n g r u e n c e o n S / 6 : T = {{a 0 ,0e), 3. Therefore, as (d^ds) in 0, we obtain the following (p,a) = (di *D«d3,d2*l)Kd3)zd. By symmetry of a congruence, we obtain (a,/3) is in 0. Case 3 Suppose that {^1,^2} = {ce,/3}. Without loss of generality, assume that d \ = a and d2 = fi. Then, (a,p)= (dud2)eO. Thus, D k is subdirectly irreducible. • 103 The D K 'S each satisfy many identities. We use this property to show that a groupoid that is influenced by a partial order relation of height 3 generates a residually large variety. For the binary operation symbol *, let t be a term of type {*}. Define the length of the t e r m t a s t h e n u m b e r o f explicit occurrences o f t h e s y m b o l * i n t . Let t\ and t2 be terms of type {*} such that the length of t\ is n\ and the length of t2 i s n 2 . D e f i n e t h e length o f t h e identity t \ & t 2 a s t h e two-tuple { n ^ n j ) . Example. Let t2(x)xx*x FI(JC,Y)« JC, and t 2 ( x , y , z ) «(-**>0 * (**Z) be terms of type {*}. The lengths of ?i(x,y), of t 2 ( x ) and of t $ ( x , y , z ) are 0, 1 and 3, respectively. The lengths of the identities t\(x,y) «t2(x) and t2(x) «ti(x,y,z) are {0,1) and (1,3), respectively. Lemma 3.1.10. Let * denote a binary operation symbol. Using the variables w, x, y and z, the following are the only identities of type { * } and of length (1,1), up to relabelling the variables or swapping sides of the identity. 1. 5. W*X*W*X 9. w*jc«y*;t 2. V f * w s s w * x 6. 10. w*xvy*w 3. w*w«Jt*w 7. w * w Ri x * y 11. w*;t«;y*z 4. w*w*x*x 8. 104 Proof. We build all of the possible identities, up to relabelling and swapping, of length (1,1) using the variables w, x, y and z. There is only one identity of length (1,1) where one variable appears four times, namely equation 1. Of all identities, up to relabelling and swapping, of length (1,1) where one variable appears three times, only two are distinct, namely equations 2 and 3. The following are all identities, up to relabelling and swapping, of length (1,1) where two distinct variables appear two times: 4. H " * W > 5. wt-Xftsw*.* 6. The following are all identities, up to relabelling and swapping, of length (1,1) where exactly one variable appears two times: 7. 9. 10. wx-jfayt-H' 8. w*;c« There is only one identity, up to relabelling, of length (1,1), where four distinct vari­ ables appear, namely Equation 11. • Lemma 3.1.11. For each non-zero cardinal number K and p\ > 1 and pi > 1, the algebra D * satisfies e v e r y identity o f length { p \ , p i ) . Proof. Note that a product of any three or more elements in DK is a. Thus, for any integers p \ > 1 a n d p2 > 1 , e a c h D * satisfies e v e r y identity o f t y p e { * } a n d o f length { p \ , p i ) . • Lemma 3.1.12. Let K be any non-zero cardinal number. The algebra D* satisfies Identity 1, Identity 4, Identity 5 and Identity 6, defined in Lemma 3.1.10. 105 Proof. Recall the following identities listed from Lemma 3.1.10. Identity 1: w*w » w* w Identity 4: Identity 5: W*X«H>*X Identity 6: w *x « x * w Every groupoid satisfies Identity 1 and Identity 5. As the product of any element in DK with itself is a, the algebra DK satisfies Identity 4. As the product of two distinct elements in DK\{a,fi} is /3 and any product involving a or /3 is a, the algebra DK satisfies Identity 6. • Lemma 3.1.13. L e t X = {w,x,>>,z} u {xi,x2,x3, •••} b e a set o f distinct variables. Let K be a non-zero cardinal number. Assume that {y i, yi1J31 • • • > term t(yi,y2,yi,•. } £ X. For every n > I and every of length n, the algebra DK does not satisfy any of the following identities: Length (0,1): Length (1,1): Length (0,0): w * W » W *X W»JC W W *X w *w « x* w WRSX*X Vf*X»H>*;y W«X*;y W*X»y*H' Length ( 1 , n ) : w*x«;y*x Jc*y«/(yi,y2,y3.---iym) Length (0,n): X"t(y\,y2,y3,...,ym) H>*X«)>*Z 106 Proof. Each D* cannot satisfy the length (0,0) identity listed in the statement of the Lemma, as a and /3 are in each DK and a * /3. For each identity of length (0,1), Table 3.6 shows that appropriate choices of a, b and c in DK yield an instance that falsify that identity. For example, if f(W,x,y) « g(w,x,y) is the identity w « w* x then letting a = p , b = a a n d c b e a n y element i n D K yields / D , c ( a , b , c ) = fi and g°K (a,b,c) = a. Thus, D* cannot satisfy the identity wxw*x, otherwise /3 = a and a contradiction occurs. Therefore, each D* does not satisfy any identities of length (0,1). f(w,x,y)*g(w,x,y) a b c J°K(a,b,c) gD*(a,b,c) w w W* w 0 - - 0 a VfssW*X P a - P a WKX*W 0 0 - 0 a w*x*x 0 0 - 0 a wr*x*y P a a P a Table 3.6: Identities of Length (0,1) that each D* does not Satisfy For each identity of length (1,1) listed in the statement of the Lemma, Table 3.7 shows that appropriate choices of a, b, c and d in DK yield an instance that falsify that identity. Therefore, each D* does not satisfy any identities of length (1,1) listed in the statement of the Lemma. When the length of t ( x \ , x 2 , x $ , . . . , x m ) is at least 2, as the product of any three elements in DK is a, we have the following: for all ( d u d 2 , d 3 , . . . , d m ) in D£, tY>K(dx,d2,d^...,dm) = a. Thus, each D* does not satisfy any identity of the form Jt«f (y i, )>2, B, • • •, )>m) > as otherwise replacing x with |3 and the y('s with 0 yields ft = a. Similarly, each D* does not satisfy any 107 /(w,JC,y,z)«f(w,x,y,z) a b c d f°K (a,b,c,d) g°K(a,b,c,d) w * Vf « w * x 0 1 - - a P W*H> war* w 0 1 - - a P w*w * x * y 0 0 1 - a P w*x&w*y 0 0 1 - a P w*x&y*w 0 0 1 - a P w*xny*x 0 0 1 - a P w*x&y*z 0 0 0 1 a P Table 3.7: Identities of Length (1,1) that each D* does not Satisfy identity of the form x* y «t (yi ,y2,y$, • • • , y m ) , as otherwise replacing x with 0, y with 1 and the yCs with 0 yields /3 = a. Thus, each D* does not satisfy any identities of lengths (0,n) or (l,n), where n> 1. • Lemma 3.1.14. For every non-zero cardinal number tc, the algebra DK satisfies every identity not listed in Lemma 3.1.13. Proof. Every identity not listed in Lemma 3.1.13 is dealt with in either Lemma 3.1.11 or Lemma 3.1.12. • Theorem 3.1.15. If B = (B;*b) is a non-trivial groupoid that is influenced by a partial order relation of height 3 and there exists an element b in B such that b*Bb± KB then V(B) is residually large. Proof. For any non-zero cardinal number K and for any set of variables X, we will show that ld ) B ) (X)£ld { D l ( (X). 108 (3.5) Since V(B) is an equational class, this will imply that DK is in V(B). Therefore, by Lemma 3.1.9, the class of algebras V(B) is residually large. Explicitly, we will show that for an identity t\ «ti of type {*}, if I>K: fi«^2 then (3-6) The contrapositive of this implication yields Statement (3.5). It follows that B does not satisfy any of the identities listed in Lemma 3.1.13. The only algebra that satisfies a non-trivial length (0,0) identity is the trivial algebra. Thus, B does not satisfy the length (0,0) identity. Since there exists a b' in B such that b' *B b' * AB, we must have b'K(a,b,c) = AB- Thus, B cannot satisfy the identity w « x*x, otherwise b' - AB and a contradiction occurs. Therefore, B does not satisfy any identities of length (0,1), that each Die does not satisfy. Similarly, for each identity of length (1,1), that each DK does not satisfy, Table 3.9 shows that appropriate choices of a, b and c in B yield an instance that falsify that identity. Thus, B does not satisfy any length (1,1) identities that each DK does not satisfy. When the length of/(yi , y i , y s , . . • , y m ) is at least 2 and B is influenced by a partial order relation of height 3, we have the following: for all { b \ , b i , b ? „ . . . , b m ) inBm, tB(bub2,h,...,bm) = XB. If B satisfied any identity of the form x »/(yi , y i , y s , • • . , y m ) then replacing each variable 109 a b C fB(a,b,c) gB(a,b,c) b' - - b' b' *Bb' b< fa - V fa b' fa - b' fa w&x*x V fa - b' fa w&x*y V fa \B b' fa f(w,x,y)*g(w,x,y) W w w *JC Table 3.8: Identities of Length {0,1) that B and each D* do not Satisfy f(w,x,y,z)<*g(w,x,y,z) a b c d fB(a,b,c,d) gB(a,b,c,d) Wt-w W W*X b fa - - b*Bb fa W*W&X*W b fa - - b*Bb fa w*w&x*y b fa fa - b*Bb fa w*x&w*y b b fa - b* Bb fa w*x&y*w b b fa - b*Bb fa w*x*y*x b b fa - b*Bb fa w*x*y*z b b fa fa b*Bb fa Table 3.9: Identities of Length (1,1 > that B and each D* do not Satisfy 110 with b ' , yields b ' = Ag. Hence, for n > 1, the algebra B does not satisfy any identities of length (0,n) that each DK does not satisfy. If B satisfied any identity of the form x * y t ( y \ , y 2 , y 3 , . . . , y m ) then replacing each variable with b' yields b' *B b' = AB- Thus, for n > 1, the algebra B does not satisfy any identities of length {1 ,n) that each DK does not satisfy. Finally, we have shown that Statement (3.6) holds. • Although the previous Theorem does not answer the Restricted Quackenbush Problem, it can be used to tell us what groupoids to avoid. In the next section we alter the previ­ ous Theorem to derive an identity that all finite groupoids, that generate residually finite varieties, must satisfy. 32 An Identity that Residually Finite Varieties Generated by Finite Groupoids Must Satisfy We generalize Theorem 3.1.15 to show that the variety generated by a finite non-trivial groupoid is residually finite if the generating groupoid satisfies a particular kind of identity that is expressed in one variable. Theorem 3.2.1. Let B = (5; *B) be a non-trivialfinite groupoid. For the variable x, if V(B) i s n o t residually large then there exists s o m e t e r m k ( x ) o f type { * } , s u c h that k ( x ) t x * x a n d B satisfies k ( x ) « JC* x . Proof. We prove the contrapositive. Specifically, we show that if for all terms k(x)±x*x, we have B & k ( x ) «x * x (3.7) then V(B) contains all of the D^'s. We do this by showing that B does not satisfy any of the identities that each D* does not satisfy. Namely, B does not satisfy any of the identities 111 of length (0,0), (0,1), {0,n), (1,1) or (1 , n ) described in Lemma 3.1.13. In other words, each of the D^'s satisfy all of the identities that B satisfies. Thus, for any non-zero cardinal K and any set of variables X, Id (B }(X)Sld (D ,}(X) and hence, all of the D* are in V(B). That is, V(B) is residually large. The generating algebra B cannot satisfy the identity of length (0,0) as B is non-trivial. Under the assumption made at the beginning of the proof, B cannot be idempotent. Hence, there must exist an element b 'mB such that b*Bbtb. Hence, B cannot satisfy any identity of length (0,1) that each DK does not satisfy as otherwise for each such identity, e a c h variable could b e replaced with b yielding b = b * B b . By Statement (3.7), the algebra B does not satisfy the following identities: x*x<*x*(x*x) and x * x * ( x * x )* x . Thus, there must exist elements b\ and £>2 in B such that b i *B^i * b i * B ( b i * B b i ) and &2 *B£>2 * (^2 *B^2) *B^2- (3.8) For each identity of length (1,1) that each D* does not satisfy, Table 3.10 shows that appro­ priate choices of a, b, c and dinB yield an instance that falsify that identity. Therefore, B does not satisfy any of the identities of length (1,1) that each D* does not satisfy. Consider a term t (ji ,>'2,y3, • • • , y m ) of length n , where n > 1. If B did satisfy an identity of length (0,n), that each D* does not satisfy, then we may replace every variable with the variable x to obtain B T= JC « / (JC, JC, JC,..., JC) and hence B1= JC * JT«F(X,.X:, X , . . . ,* ) * t ( x , x , x , . . . , x ) . 112 f(w,x, y ,z)*g(w,x, y , z ) a b c d fB{a,b,c,d) gB(a,b,c,d) H>*W» W*JC b\ b\ *Bb\ - - b\ *Bb\ b\ *B {b\ *Bbi) b2 b2 *B b2 - - b2*Bb2 (b2*Bb2)*Bb2 b\ bi b\ *Bbi - b\ *Bb\ b\ *B{b\*Bb\) bi h b\ *Bb\ - b\*Bb\ b\ *B {b\ *B£i) b2 bi b2 *B b2 - b2*Bb2 ( b 2 * B b 2 )* B b 2 b2 b2 b2* B b 2 - b2*Bb2 { b 2 * B b 2 )* B b 2 b2 b2 bi *Bb2 b2 b 2* B b 2 ( b 2 * B b 2 )* B b 2 w*w»;c*;y w*;c«;y*jc Table 3.10: Identities of Length (1,1) that B and each D* do not Satisfy By the assumption described in Statement (3.7), the algebra B cannot satisfy an identity of length (0,n) that each D* does not satisfy. Similarly, B cannot satisfy an identity of (l,n), that each DK does not satisfy, as otherwise we may replace each variable with the variable x to obtain B l= jc * x « t ( x , x , x , . . . , jc) . Thus, the algebra B does not satisfy any of the identities that each DK does not satisfy. • Note that in the proof of Theorem 3.2.1, we showed that D* is in V(B), for any non­ zero cardinal number K. This leads into the following corollary. Corollary 322. Let B = (5; *B) be a finite groupoid and xbea variable. If for every term k(x) of type {*} such that k(x) tx*x, the algebra B does not satisfy k(x) S»JC*JC then 1. the class of algebras V(B) is residually large; and 113 *E17 0 12 3 ••• n 0 1 2 2 ? - ? 1 2 2 2 ? - ? 2 2 2 ? ••• ? 3 ? ? ? ? • • • ? 2 9 n ? ? ? ? ? ? Table 3.11: The Operation Table of *E|7 2. for any cardinal number y greater than 3, there exists a subdirectly irreducible mem­ ber M in V(B) such that \M\ = y. Proof. Part 1 of the Corollary is the contrapositive of Theorem 3.2.1. With regard to Part 2 of the Corollary, if 3 < y < a> then let M = Dy_3 and if y > co then let M = Dy. • We can use the previous Corollary to rig the construction of groupoids to yield groupoids that generate residually large varieties. Example. Let En = (En;*El7) be a groupoid whose partial operation table is described in Table 3.11. Even though a partial description is given, V(En) is residually large by Corollary 3.2.2. To see why, note that 0 *E'7 0=1 and ?E|7(0) = 2, for any term t(x) of type {*} that is at least of length 2. Thus, for all terms t(x) tx*x of type {*}, we have E17 £ t(x) fa***. Corollary 3.2.2 yields an immediate question: If B = is a non-trivial finite groupoid such that V(B) is residually finite, must *B be idempotent? If we consider con­ stant groupoids, that is, groupoids where the lone binary operation maps everything in the 114 universe to one particular element, then the answer is no. The following example demon­ strates this. Example. Let Ejg be a constant non-trivial groupoid. One can verify that V(Eis) is the class of all constant groupoids. This variety is residually finite as the only non-trivial constant groupoid that is subdirectly irreducible is the two element constant groupoid. If B = ( B \ *B) is a non-trivial finite groupoid such that V(B) is residually finite, must *B be idempotent? If we do not consider constant groupoids, then the answer to this question becomes less obvious. We conclude this section with the following question. Question. With regards to Corollary 3.2.2, does there exist a non-trivial and non-constant groupoid B = {B;*B) such that *B is not idempotent andV(B) is residually finite? Must such a groupoid be a reduct of a group? 33 Application: RS-Conjecture In 1988, Hobby and McKenzie posed the following problem in [6]: Problem (Problem 12). Prove or disprove: If B is a finite algebra such that V(B) admits no finite bound for the cardinals of its subdirectly irreducible algebras, then this class of cardinals is not bounded by any cardinal. In the same article [12] that McKenzie answered the Quackenbush Problem, he also answered Problem 12 and the RS-Conjecture. Recall the definition of the residual character of a variety on page 22. For a given variety V, if there exists a least cardinal number K such that the cardinality of the universe of every subdirectly irreducible member in V is less than K, then fc is called the residual character of V. 115 Conjecture (RS-Conjecture). Let B be an algebra. If the residual character o/V(B) is greater than or equal to co, then V(B) is residually large. Specifically, McKenzie disproved Problem 12 and showed that the RS-Conjecture is false in general. He did this by constructing an eight-element algebra of residual bound coi with just eight basic operations. From the work in the previous section, specifically Corollary 3.2.2 on page 113, we have shown that Problem 12 is proved and the RS-Conjecture is true when B is a finite groupoid that satisfies the following condition: for the variable x and all terms k(x) of type { * } s u c h that k ( x ) ± x * x , t h e algebra B d o e s n o t satisfy k ( x ) * x * x . 3.4 A Strategy Concerning Groupoids and the Restricted Quackenbush Problem Recall Theorem 3.2.1 on page 111. Theorem. Let B = (B;*B) be a non-trivial finite groupoid. For the variable x, if V(B) is not residually large then there exists some term k(x) of type {*}, such that k(x) ±x*x and B satisfies k ( x ) x x * x . This theorem implies that, with respect to the Restricted Quackenbush Problem, only groupoids that are almost idempotent need to be looked at, that is, groupoids that satisfy an identity of the form k(x) HX*X, where k(x) is a term of type {*} such that &(JC) ±x*x. The class of stricdy idempotent groupoids is a reasonable place to start. In the next chapter, we look at idempotent groupoids and attempt to answer the Restricted Quackenbush Problem. 116 Chapter 4 Groupoids and the Restricted Quackenbush Problem With respect to the Restricted Quackenbush Problem, one class of algebras that was specif­ ically asked about by Quackenbush, and still remains unanswered today, is the class of groupoids. Groupoids are of interest because, using the tools developed by McKenzie in [11], an­ swering the Restricted Quackenbush Problem with respect to groupoids answers the Re­ stricted Quackenbush Problem with respect to arbitrary algebras. Specifically, McKenzie constructed an isomorphism F from the variety of all algebras of an arbitrary type T to a particular variety of groupoids, dependent on T. In Theorem 2.18, he shows that, for each algebra B of type T, the congruence lattice of F(B) is isomorphic to the congruence lattice of B, with the addition of a new maximum element. Thus, B is subdirectiy irreducible if and only if F(B) is subdirectiy irreducible. Since F is an isomorphism, F(V(B)) = V(F(B)). That is, F preserves subvarieties. Lastly, by the first Lemma in the paper, isomorphisms between varieties preserve finite algebras. That is, B is residually finite if and only if F(B) is residually finite. Using all of these ingredients yields the following: answering the Re­ 117 stricted Quackenbush Problem with respect to F(B) answers the Restricted Quackenbush Problem with respect to B. In this chapter, we define a particular kind of idempotent groupoid and identify some properties that could be useful in showing that the Restricted Quackenbush Problem can be answered with respect to these kinds of groupoids. 4.1 A Property of Idempotent Groupoids Idempotent groupoids have a curious property; for an idempotent groupoid B, the congru­ ence blocks of any congruence on B, are subuniverses of B. In the following Lemma, we formalize this property and prove that it holds. Lemma 4.1.1. Let B = (B\ *B) be an idempotent groupoid and 6 be a congruence on B. There exists a family {S,•},-<=/ of subalgebras of B, such that (JS,- = B and the congruence ui blocks of Q are {S;},-6/. That is, B/ e = {b/d\beB} = {Si}ieI. Proof. We will show that each congruence block of 0 is a subuniverse of B. Then, because each member of B must belong to exactly one congruence block, B is equal to a disjoint union of subuniverses. Each block cannot be empty. Hence, each block together with *B yields a subalgebra of B. For b in B , let b \ and b i be elements in b / 6 . To show that b / 6 is a subalgebra, we must show that b\ *Bbi in b/6. Note that (b\,b\) and (b\,62) are members of 6. Therefore, due to the compatibility property of congruences, ( b \ * B b \ , b \ *b&2) € 0 and thus, (b\,bi*Bb2)£0. That is, b \ and b \ * B b 2 are in the same congruence block. Hence, b \ *B b j is in b / 6 . 118 • *E19 0 12 3 4 0 0 2 4 0 4 1 4 13 0 4 2 1 1 3 1 4 0 3 4 4 4 4 4 4 4 2 4 4 Table 4.1: The Operation Table of *E|9 42 Absorbing Groupoids We start this section with an example of an absorbing groupoid and then give its definition. Example. Consider the groupoid E19. The operation table for *E>9 is given in Table 4.1 and the lattice of subuniverses of E19 is given in Figure 4.1. Notice that every subuniverse of E19 that contains at least two elements also contains 4. Further, notice that E19 is not associative as 0*El9(l *Ei92) =0 and (0*El9 1) *El92 = 2. Let B be a groupoid. If for some dB in B and all b in B we have ds*Bb = &B and 6 *B 6B = SB then call 5b the zero of B or just the zero and say that B has a zero. Note that if a groupoid has a zero, then the zero of the groupoid is unique. Definition. Say that a finite groupoid B = (B; *B) is absorbing if 1. the operation *B is idempotent, 2. the algebra B has a zero, and 119 {0,1,2,3,4} \ / {0,4} {2,4} {1,4} {3,4} / {0} \ {1} {4} {2} {3} 0 Figure 4.1: The Lattice of Subuniverses of E19 3. the universe of every subalgebra of B that contains at least 2 elements also contains the zero of B. Note that not all absorbing groupoids are semigroups as the binary operation of an absorbing groupoid need not be associative. 4.2.1 Absorbing Groupoids Do Not Necessarily Generate CongruenceModular Varieties Is it worth looking at absorbing groupoids? That is, has the Restricted Quackenbush Prob­ lem been answered with respect to absorbing groupoids? The groupoid E19, defined on page 119, is an example of an absorbing groupoid that is not associative. Hence, E19 is not a semigroup. We show that E19 does not generate a congruence-modular variety. Hence, there exist varieties of absorbing groupoids that are not congruence-modular and thus nei­ ther congruence-distributive nor congruence-permutable. It is unknown whether all absorbing groupoids generate varieties that either have defin­ 120 able principal congruences or are congruence-meet-semidistributive or are residually large. This means previous techniques can not yet be used to answer the Restricted Quackenbush Problem for absorbing groupoids. To show that E19 does not generate a congruence-modular variety, we use tools devel­ oped by Freese and Valeriote in [5]. Call a quadruple {bi,b2,bi,b4) in an algebra B a Day quadruple if in the subalgebra M generated by {b\,biM^H}, we have the following: (bi,b2)tCgM{(h,b4))v(CgM{(bub2),(b3,b4})*CgM{(b\Mh{b2,b4)))In the language of a groupoid, Theorem 3.6 in [5] becomes the following: Theorem 4.2.1. Let B be an idempotent groupoid. Then V(B) fails to be congruencemodular if and only if there is a Day quadruple in B2. For the remainder of this subsection, we denote the 2-tuple { a \ , a 2 ) by a\a2. We explic­ itly show that ( b u b 2 M M ) = {00,01,40,41) (4.1) is a Day quadruple in E192. To show this, we must determine the following congruences: CgM({40,41)), CgM({00,01), (40,41)) and CgM«00,40), (01,41)). Note that SgB2({00,01,40,41}) = {00,01,02,03,04,40,41,42,43,44}. Denote this set by M and define M = (M; *M), where *M = *Ei*21M - See Table 4.2 for the operation table of *M. Recall that for an equivalence relation o, defined on the universe of a groupoid G to satisfy t h e compatibility property, t h e following condition m u s t b e satisfied: f o r all ( g i , g 2 ) and (gi,g4) in a, the element , ^ 3 ^4)) = CgM({00,01),(40,41)) = r2. The relation r3 = {00,40} 2 u{01,41} 2 u{02,42} 2 u{03,43} 2 u{04,44}2 is the congruence on M that is obtained from the second projection map on M. Since (00,40) and (01,41) is contained in T3, the following is true: CgM((00,40),(01,41»CT3. 123 (4.5) As (00,40) *M (02,02) = (02,42), (00,40) *M (03,03) = (04,44) and (01,41) *M (02,02) = (03,43), the elements 00, 01, 02, 03 and 04 are related to 40, 41, 42, 43 and 44, respectively, in CgM((00,40), (01,41)). Therefore, due to Statement (4.5), Cg ( ( ^ , f c 3 ) , ( & 2 , 6 4 ) ) = CgM((00,40),(01,41)) = r3. M Let {bub2MM) = (00,01,40,41). Using x\, T2 and t3, defined earlier, we obtain the following: C g M « ^ 3 ^ 4 ) ) v ( C g M ( ( f e i , f c 2 ) , (*>3,64)) A C g M ( ( & i , f c 3 ) ,{ b 2 M ) ) ) = TIV(T 2 AT 3 ) = ri vAm = TI. Thus, since (00,01) i {40,41,42,43,44} 2 u A M = x x , the quadruple listed in Statement (4.1) is a Day quadruple. Hence, by Theorem 4.2.1, the variety generated by E19 is not congruence-modular. 422 A Possible Approach to Deal with Absorbing Groupoids and the Restricted Quackenbush Problem For the remainder of this chapter, assume that B is an absorbing groupoid and S is a subalgebra of B7, for some index set I. Further, assume that 0 is a congruence on S. 124 Recall that the ith projection map on B1 restricted to S is denoted by p, instead of n Further recall, from Lemma 4.1.1, that each member of S/d is a subuniverse of S. Hence, w e denote t h e elements i n S / d b y t h e elements { S j } 7 e / , w h e r e J i s a n index set. F o r all i in /, define the binary relation fa on S/d as follows: for all Si and S2 in S/d, the 2-tuple (Si,S2) is in fa if and only if 1. the element 8b is in p,(5j) np,^) or 2. the congruence blocks Si and S2 are equal. Lemma 422. For all i in I, the relation fa is a congruence on S/d. Proof. To prove the Lemma, we show that fa is an equivalence relation on S/6 that satisfies the compatibility property. The relation fa is reflexive by definition and symmetry follows from the commutativity of set intersection and symmetry of equality. Suppose that Si, S2, S3 and S4 is in S/d. To show that fa is transitive, assume that {Si, S2) and (S2,S3) is in fa. Three cases emerge. Case 1 Suppose thatfifl is in bothpi(Si)npj(S2)andp,(S3)npi(S3). Then 8b is in p,(Si )n p;(S3) and hence {Si,S3) is in fa. Case 2 Without loss of generality, suppose that 8b is in p,(Si) np,(S2) and that S2 = S3. Then Pi(S1) n p,(S2) = p,(Si) n pi (S3) and hence (Si,S3) is in fa. Case 3 If Si = S2 and S2 = S3, then Si = S3 and hence (Si,S3) is in fa. Thus, fa is an equivalence relation. 125 To show that 0, satisfies the compatibility property, assume that (Si,S2) and (S3, S4) are in fa. Either Si = S2 and S3 = S4 or one of these equalities is not true. With respect to the former scenario, if Si = S2 and S3 = S4 then Si *s/e S3 = S2 *s/e S4 and hence (Si *s/e S3,S2 *s/e S4) 6 , not equal to As/e> then S/9 is not subdirectly irreducible. 126 Proof. By Lemma 4.2.2, the relation fa is a congruence on S/d. By hypothesis, for some positive integer n, we have 1 < |/| < n and for all i in 7, the congruence fa is not equal to As/fl- For Si and S2 in S / d , suppose that (Si,S2) is in / \ f a . Therefore, for all i in /, we i€l have (Si,52) in fa. Thus, either Si = S2 or, for all i in /, <5fi€Pi(Si)nPl(S2). Assume that the latter is true. Thus, for all i in /, we may pick t\ in Si and tl2 in Si such that t\(i)=ti2(i) = 6B. (4.6) For j in {1,2}, define T j ~ (""((*] * S ^ ) * S f y ) * s - - - *st". Lemma 4.1.1 yields Si and S2 being subuniverses of S. Hence, both Si and S2 are closed under *s. Thus, for all j in {1,2}, we have 7) in Sj. By Statement (4.6), we have both T\ and Ti equal to the n-tuple in B1 where every coordinate is 8B. Hence, Si nS2 * 0 and thus Si = S2. Therefore, /\ 2 satisfy the implication there exists i in I such that fa = A5/0 implies |S/0| < N 127 then V(B) is residually < N. Proof. Recall Lemma 1.3.8, on page 41: if B is a finite algebra then all finite members in V(B) are in HSPfin(B). Thus, each finite algebra in V(B) is a (0,/,S,B)-algebra. As V(B) is residually finite, each subdirectly irreducible algebra in V(B) is a (0,/,S,B)algebra. Let N be a fixed integer greater than |B| and let M be a subdirectly irreducible (0,/,S,B)algebra. If |/| = 1, then M is in HS(B) and hence \M\ < |fi|. Now assume |/| > 2. By Lemma 4.2.3, there must exist i in / such that ,• = &s/e then \S/6\ < N and hence |M| < N. Therefore, V(B) is residually less than max{|fi|,A^} = N. • The chapter is concluded with a question that asks if it is possible to use Theorem 4.2.4 to answer the Restricted Quackenbush Problem, with respect to absorbing groupoids. Question. Let B be an absorbing groupoid. What additional conditions can be imposed on B to force the existence of an integer N greater than |2?| such that all subdirectly irreducible (6,1, S,B)-algebras with |/| > 2 satisfy the following implication: if there exists an i in I such that , = As/e. The outcome of this attempt yielded the following theorem: Theorem. Let B be an absorbing groupoid that generates a residually finite variety and n be an integer greater than |S|. If all subdirectly irreducible (6,1,S,B)-algebras with |/| > 2 130 satisfy the implication there exists i in I such that , = As/d implies \S/d\ < N then V(B) is residually < N. The above theorem may be a step towards answering the Restricted Quackenbush Prob­ lem, with respect to absorbing groupoids. 5.2 Questions The following is a list of questions that were asked throughout this thesis. Question. With regards to Corollary 3.2.2, does there exist a non-trivial and non-constant groupoid B = (B\*B) such that *B is not idempotent and V(B) is residually finite? Must such a groupoid be a reduct of a group? Question. Let B be an absorbing groupoid. What additional conditions can be imposed on B to force the existence of an integer N greater than |fi| such that all subdirectly irreducible (9,1,S,B)-algebras with |/| > 2 satisfy the following implication: if there exists an i in I such that (f)i = A s / e t h e n \ S / d \ < N ? 131 Bibliography [1] J. T. Baldwin and J. Berman, The number of subdirectly irreducible algebras in a variety, Algebra Universalis 5 (1975), no. 1,379-389. [2] S. Burris and H. P. Sankappanavar, A course in universal algebra: Millenium edition, Graduate Texts In Mathematics, Springer-Verlag, 2000. [3] A. Foster and A. Pixley, Semi-categorical algebras. II, Mathematische Zeitschrift 85 (1964), 169-184. [4] R. Freese and R. McKenzie, Residually small varieties with modular congruence lat­ tices, Transactions of the American Mathematical Society 264 (1981), 419-430. [5] R. Freese and M. A. Valeriote, Maltsev conditions and relations on algebras, Interna­ tional Journal of Algebra and Computation 19 (2009), no. 1,41-77. [6] D. C. Hobby and R. McKenzie, Residually small varieties, Contemporary Mathemat­ ics, vol. 76, AMS, 1989. [7] B. Jonsson, Algebras whose congruence lattices are distributive, Mathematica Scandinavica21 (1967), 110-121. 132 [8] K. A. Kearnes and R. Willard, Residually finite, congruence meet-semidistributive varieties of finite type have a finite residual bound, Proceedings of the American Mathematical Society 127 (1999), no. 10,2841-2850. [9] R. McKenzie, Residually small varieties of semigroups, Algebra Universalis 13 (1981), no. 1,171-201. [10] , Residually small varieties of k-algebras, Algebra Universalis 14 (1982), no. 1,181-1%. [11] , A new product of algebras and a type reduction theorem, Algebra Universalis 18 (1984), no. 1,29-69. [12] , The residual bounds of finite algebras, International Journal of Algebra and Computation 6 (1996), 1-28. [13] R. N. McKenzie, G. F. McNulty, and W. F. Taylor, Algebras, lattices, varieties, Wadsworth & Brooks\Cole, 1987. [14] A. J. Ol'sanskii, Varieties of finitely approximable groups, Mathematics of the USSRIzvestiya 3 (1969), no. 4,867. [15] R. W. Quackenbush, Equational classes generated by finite algebras, Algebra Univer­ salis 1 (1971), no. 1,265-266. [16] J. W. Snow, Maltsev conditions and relations on algebras, Algebra Universalis 42 (1999), no. 4,299-309. [17] W. Taylor, Subdirectly irreducible algebras in regular, permutable varieties, Proceed­ ings of the American Mathematical Society 75 (1979), no. 2,196-200. 133 [18] G. H. Wenzel, Subdirect irreducibility and equational compactness in unary algebras (A; /), Archiv Der Mathematik 21 (1970), no. 1,256-264. [19] M. Yoeli, Subdirectly irreducible unary algebras, The American Mathematical Monthly 74 (1967), no. 8,957-960. 134