Maltsev Filters - ULisboalfsequeira/math/... · 2013. 6. 5. · The Maltsev ﬁlters of the lattice of interpretability types correspond, in a natu-ral way, to the so-called Maltsev

Faculdade de Ciências da Universidade de Lisboa

Maltsev FiltersLuı́s Sequeira

Tese de Doutoramento

Orientador: Professor Walter Taylor

2001

Resumo

Os filtros de Maltsev do reticulado dos tipos de interpretabilidade correspon-dem, de modo natural, às chamadas condições de Maltsev, que estão associadasa muitas propriedades importantes de variedades. As classes das variedades cujasálgebras têm reticulados de congruências permutáveis, distributivos ou modularesconstituem filtros de Maltsev. A conjectura de que o filtro de Maltsev das varieda-des congruente-modulares seja um filtro primo está há muito em aberto.

Introduz-se, associado a cada filtro de uma classe significativa de filtros deMaltsev, um novo conceito de compatibilidade com projecções. Se todas as varie-dades que não pertencem a um dado filtro de Maltsev satisfazem a correspondentecompatibilidade com projecções, então não é posśıvel construir termos simples (numsentido bem determinado) que estabeleçam a não primalidade do filtro. São estu-dados exemplos significativos, verificando-se que a ocorrência da propriedade decompatibilidade com projecções aparece sempre associada a filtros que se sabe ousupõe serem primos, falhando claramente nos casos de filtros não primos. Demons-tra-se, em particular, que esta propriedade ocorre associada ao filtro das variedadescongruente-modulares.

Prova-se que o filtro das variedades com termo de quasi-unanimidade é decom-pońıvel. A propriedade de compatibilidade com projecções é usada para estabele-cer facilmente a modularidade de uma das parcelas da decomposição deste filtro; omesmo se passa com o filtro das variedades congruente-distributivas.

Propriedades algébricas válidas numa variedade impõem restrições às álgebrastopológicas dessa variedade: um resultado clássico é o de que, numa variedadecongruente-permutável, toda a álgebra topológica T0 é necessariamente Hausdorff.São apresentados resultados que generalizam ou melhoram teoremas deste tipo. Porexemplo, a implicação T0 =⇒ T2 é válida para álgebras topológicas em qualquervariedade que seja modular e k-permutável, para algum k. Demonstra-se que, sendoP uma de várias condições deste tipo, as variedades cujas álgebras topológicassatisfazem P constituem um filtro de Maltsev.

Summary

The Maltsev filters of the lattice of interpretability types correspond, in a natu-ral way, to the so-called Maltsev conditions, which have been associated with manyimportant properties of varieties. The classes of all varieties whose algebras havecongruence lattices which are permutable, or distributive, or modular, constituteMaltsev filters.

The conjecture that the filter of congruence-modular varieties is prime has beenoutstanding for some time.

Associated with each of a large class of Maltsev filters is a new concept of com-patibility with projections. If all varieties outside a given Maltsev filter satisfy thecorresponding compatibility condition, then it is shown that the failure of primenessof that filter cannot be witnessed by terms which are simple (in a specified sense).Significant examples are studied, and it emerges that the property of compatibilitywith projections always occurs associated with filters that are prime or strongly sus-pected of being prime, and that this property is conspicuously absent when dealingwith nonprime filters. In particular, it is shown that the property of compatibilitywith projections does occur in association with the filter of congruence-modularvarieties.

It is shown that the filter of the varieties possessing a near-unanimity termis decomposable. The property of compatibility with projections yields an easyproof that one the joinands of this decomposition is modular; and similarly for thedecomposition of the filter of congruence-distributive varieties.

Algebraic properties holding in a variety may impose restrictions on the topolo-gies occurring in topological algebras in that variety: a classic result is that, in acongruence-permutable variety, each T0 topological algebra is Hausdorff. Some re-sults which improve or generalize theorems of this flavor are presented. For example,the implication T0 =⇒ T2 holds for all topological algebras in any variety that isboth congruence-modular and k-permutable, for some k. It is shown that, for Pone of a handful of properties of this kind, the varieties all of whose topologicalalgebras satisfy P constitute a Maltsev filter.

Contents

Resumo iii

Summary v

Introduction ix

Acknowledgements xi

Chapter 0. Preliminaries 11. Algebras, subalgebras, homomorphisms and congruences 12. Terms, satisfaction and free algebras 33. Lattices, semilattices 44. Topological basics 65. Categorical basics 8

Chapter 1. Interpretability types and clones of varieties 111. Maltsev type conditions 112. The lattice of interpretability types 143. The clone of a variety 164. Free product of clones 18

Chapter 2. Compatibility with projections and the primeness of some Maltsevfilters 21

1. Congruence-permutability 232. Congruence-k-permutability 253. Congruence-modularity 284. Concluding remarks on compatibility with projections 34

Chapter 3. Some Maltsev filters that are not prime 351. Congruence distributivity 352. Near unanimity 363. k-modularity 40

Chapter 4. Hausdorff properties of topological algebras 451. k-permutable varieties satisfy T0 ⇒ H⌊ k

2⌋ 49

2. Not all k-permutable varieties satisfy T0 ⇒ H⌊ k2⌋−1 51

3. Congruence modular, k-permutable varieties satisfy T0 ⇒ T2 544. Topological properties definable by Maltsev conditions 575. Concluding remarks 60

Appendix A. On the word problem for Pk 61

Bibliography 65

Index 67

vii

Introduction

In 1954, A. I. Maltsev proved that the permutability of congruences for allalgebras in a variety is equivalent to the existence of a ternary term satisfyingtwo simple identities. Other important properties of varieties have since then beenshown to be equivalent to similar Maltsev-type conditions. Foremost among thoseare congruence distributivity (Jónsson, 1967), congruence modularity (Day, 1969)and congruence k-permutability (Schmidt, 1972; Hagemann, Mitschke, 1973). Thusthe study of Maltsev conditions became an important part of the theory of varieties.All of these results are stated, usually without proof, in Chapter 1.

The lattice L of interpretability types of varieties was introduced by W. D. Neu-mann in 1974. It provides the right environment in which questions about Maltsevconditions can be adequately formulated in terms of filters of this lattice. Thisis also introduced in Chapter 1. The definition and notation for this is as in themonograph of Garcia and Taylor [16]. Maltsev conditions are seen to correspondto filters in L of a special kind; these have thus become known as Maltsev filters.

Some of the problems concerning Maltsev filters can be better dealt with byusing the concept of clone of a variety. This concept is introduced and the corre-spondence between interpretability of varieties and the existence of certain clonehomomorphisms is established. Our exposition of this matter essentially followsthe work of Steven Tschantz [36]. The correspondence between joins in L andcoproducts of clones is discussed and a construction, also due to Steven Tschantz,of a special form for these coproducts, which is akin to the free product of groups,is presented. Chapter 1 contains no original results.

Chapter 2 deals with a new concept, that of compatibility with projections,which is intimately related to the primeness of Maltsev filters of a certain restrictedform, which is, nevertheless, general enough to include many relevant cases, such aspermutability, k-permutability for each particular k, distributivity and modularity.The concept of compatibility with projections is introduced and its relevance tothe study of properties of the Maltsev filters is discussed. It is seen that thiscondition holds for all varieties outside each of those filters which are known tobe, or strongly suspected of being prime, while it conspicuously does not hold inthe cases where the filters are not prime. The condition of compatibility withprojections was introduced in the hope that it might lead to the settlement of anoutstanding conjecture by Garcia and Taylor [16], namely that the filter composedof congruence modular varieties is prime. While it has not been possible to provethe validity of this conjecture yet, it is proved that it cannot be falsified exceptpossibly by terms of great complexity, in a way that is made precise.

In Chapter 3, several Maltsev filters which fail to be prime are considered.The first of these filters, that of those varieties which are congruence-distributive,has long been known to be the intersection of two larger Maltsev filters. The factthat one of these filters is contained in the filter of congruence-modular varieties(as predicted by the congruence modularity conjecture) is new. That the filterof varieties possessing a near-unanimity term is also the intersection of two largerfilters is new. We also prove that one of these filters is congruence-modular, again in

ix

x INTRODUCTION

accordance with the congruence modularity conjecture. In both cases, two proofs ofthe modularity of the appropriate filters are presented: an easy argument applyingthe compatibility of projections introduced in Chapter 2, and a direct proof by wayof showing concrete terms satisfying the well known identities of Alan Day [10].The final section of Chapter 3 deals with the filters of k-modular varieties, whichare seen not to be prime if k ≥ 4. This fact seems to have been known to a numberof people for some years, but to my knowledge has not appeared in print. I presentan indirect proof of this result and a new direct proof, describing actual Day terms.

Chapter 4 is dedicated to the study of separation properties in topological alge-bras. It has been known for a long time that some algebraic properties of topologicalalgebras, such as k-permutability of congruences, may strongly restrict the class oftopological spaces which may occur as the underlying spaces of those algebras. Thistopic seems to go back to Taylor [34] and Gumm [19]. It got further developmentthrough the work of J. P. Coleman [8, 9]. Coleman introduced a family of separa-tion conditions Hn, for n ≥ 1, which are strictly stronger than T1, and showed thateach T0 topological algebra in a k-permutable variety satisfies Hk−2 (provided thatk ≥ 3). A new approach to the formulation of these separation conditions led meto consider yet another family of separation conditions sHn which, although weakerthan Hn for general spaces, are shown to be equivalent for topological algebras ink-permutable varieties. This equivalence leads to a proof of a much stronger versionof Coleman’s theorem, namely that each T0 topological algebra in a k-permutablevariety satisfies H⌊ k

2⌋ . The figure ⌊

k2 ⌋ given by this result cannot be improved,

for a new construction is given, which yields, for each k, a topological algebra in ak-permutable variety which satisfies H⌊ k

2⌋ but does not satisfy H⌊ k

2⌋−1.

Given that 2- and 3-permutability entail modularity and also imply that eachT0 topological algebra is Hausdorff, Coleman raised the following question: “Arek-permutability and modularity together necessary and/or sufficient to have T0 ⇒T2?”. A positive answer to the sufficiency of these conditions is provided.

Some of the results of this chapter were obtained in collaboration with KeithKearnes, during my stay at the University of Colorado at Boulder, in February2001, and will also appear in a joint paper, which has been accepted for publicationin Algebra Universalis.

Acknowledgements

So many people made this thesis possible that I cannot thank them all here. Ihope anyone whose name should be included here and isn’t will forgive me.

First, I must thank Professor Walter Taylor, my advisor, for his continuoussupport and insightful advice.

I also wish to thank all the people at the University of Colorado at Boulder whohelped make my several visits there both pleasant and fruitful. First and foremost,Professor Stash Świerczkowski; and also Professors Keith Kearnes, Jan Mycielski,Alejandro Spina, George McNulty.

Many thanks to all the people at Departamento de Matemática, Faculdade deCiências da Universidade de Lisboa who have provided me with a friendly work en-vironment over the years. I particularly want to thank Professor Gabriela Bordalofor introducing me to Professor Taylor and for her continuing encouragement, Pro-fessors Mário Figueira and Elisa Simões for making possible Professor Taylor’s visitto Portugal in 1998, which kickstarted this work, and Professor Gracinda Gomesfor helping me secure financial support for one of my visits to Boulder.

I also want to thank Professor Margarita Ramalho for her support and forher wise suggestions, and my fellow project members at Centro de Álgebra daUniversidade de Lisboa.

I gratefully acknowledge the financial support from several institutions. Myvisits to the University of Colorado at Boulder were made possible by fundingfrom Fundação Luso Americana para o Desenvolvimento, Fundação Calouste Gul-benkian, Centro de Álgebra da Universidade de Lisboa and Fundação para a Ciênciae Tecnologia (project Praxis XXI). Professor Taylor’s visit to Portugal was madepossible by funding from Fundação para a Ciência e Tecnologia, Departamento deMatemática da Faculdade de Ciências da Universidade de Lisboa and Centro deÁlgebra da Universidade de Lisboa.

Last, but not least, I thank my family, especially my sister Margarida, myfather, my wife and my children, without whom this work would not even havebeen started.

xi

To Virǵınia, Diana, Inês, Miguel

CHAPTER 0

Preliminaries

In this chapter, we collect some definitions and results that will be used later.Most of these are supposedly well known, and so the proofs are omitted.

We assume the reader is familiar with the basics of universal algebra and latticetheory. For a more detailed exposition of the basic concepts and results of universalalgebra, the reader is referred to [25], [15] or [5].

The knowledge of topology and category theory which we require is elementary,as described in sections 4 and 5 below. For more on general topology, we refer thereader to [22]; for a good introduction to category theory, see, for example, [1].

1. Algebras, subalgebras, homomorphisms and congruences

A type, or similarity type, is a set τ equipped with a function ar : τ → ω. Theelements of τ are called function symbols, or operation symbols, and the functionar associates which each function symbol a nonnegative integer, called its arity.Usually, it is more convenient notationally to regard a type as an indexed setτ = (fi)i∈I , leaving the arity function implicit. We will adhere to this convention.

For each nonnegative integer n, an n-ary operation on a set A is a mapf : An → A. The number n is also called the arity of f . An operation of ar-ity 0 is called nullary. For other small arities, words such as unary, binary, ternary,quaternary will be used, instead of 1-ary, 2-ary, etc.

An algebra of type τ = (fi)i∈I is a structure A = 〈A; (fAi )i∈I〉, where A isa nonempty set (called the universe of A) and, for each i, fAi is an ar(fi)-aryoperation on A. We will usually drop the superscripts, writing fi for f

Ai when

there is no cause for confusion.

A subalgebra of an algebra A = 〈A; (fAi )i∈I〉 is an algebra B = 〈B; (fBi )i∈I〉 of

the same type such that B ⊆ A and, for each i, fBi agrees with fAi on B

ar(fi).A subset B ⊆ A is called a subuniverse ofA if it is closed under the operations of

A (the empty set being a subuniverse if and only if there exist no nullary operationsin the type of A). A nonempty subuniverse of A is thus the universe of a uniquesubalgebra ofA. The intersection of a nonempty family of subuniverses ofA is againa subuniverse. Thus, for any X ⊆ A, the subuniverse generated by X , defined asthe smallest subuniverse of A that contains X , always exists and may be describedas

Su(X) :=⋂

{B | X ⊆ B, B a subuniverse of A}

If ∅ 6= X ⊆ A, the subalgebra generated by X is the subalgebra with universe Su(X).

A reduct of an algebra A = 〈A; (fi)i∈I〉 is an algebra 〈A; (fi)i∈J 〉, for someJ ⊆ I, i. e., an algebra with the same universe but fewer operations.

The direct product of a family of algebras (Aj)j∈J , all of the same type τ , isthe algebra of type τ whose universe is the cartesian product

∏

j∈J Aj and whereeach operation is defined coordinatewise. The algebras Aj are called the factors ofthe direct product. If all factors coincide, e. g., Ai = A, then we speak of a directpower of A and denote it as AJ . A finite direct product, or direct power, is one

1

2 0. PRELIMINARIES

in which the index set J is finite. Finite direct products are usually denoted asA1 × . . .×An and finite direct powers as An, for some nonnegative integer n.

A map φ : A → B is a homomorphism from the algebra A = 〈A; (fAi )i∈I〉 tothe algebra B = 〈B; (fBi )i∈I〉 of the same type if

φ(fAi (a1, . . . , aar(fi)) = fBi (φ(a1), . . . , φ(aar(fi)))

holds for each i ∈ I and a1, . . . , aar(fi) ∈ A. We write φ : A → B if φ is ahomomorphism from A to B.

An isomorphism between algebras A and B of the same type is a bijectivehomomorphism φ : A → B. Two algebras A and B of the same type are isomorphic,and we write A ∼= B, if there exists an isomorphism φ : A → B.

A homomorphism φ : A → A is called an endomorphism of A.

A congruence on an algebra A is an equivalence relation on A which is also(the universe of) a subalgebra of A2. The set of all congruences on an algebra Awill be denoted by Con(A).

If θ is a congruence on A, then the quotient A/θ is the algebra of the samesimilarity type, with universe A/θ and with operations defined by

fA/θ(a1/θ, . . . , aar(f)/θ) := fA(a1, . . . , aar(f))/θ

and the canonical map A → A/θ is an onto homomorphism from A to A/θ.Conversely, given any onto homomorphism φ : A → B, the kernel of φ, definedas ker(φ) := { (a, b) ∈ A2 | φ(a) = φ(b) }, is a congruence on A and A/ ker(φ) isisomorphic to B.

A congruence θ on an algebra A is fully invariant if it is compatible with everyendomorphism of A, i.e., if, for every endomorphism φ : A → A and any a, b ∈ A,(a, b) ∈ θ implies (φ(a), φ(b)) ∈ θ.

The intersection of an arbitrary family of (fully invariant) congruences on Ais again a (fully invariant) congruence on A. Thus, given any set C ⊆ A2, the(fully invariant) congruence generated by C, denoted by Cg(C) (Cgfi(C)), is theintersection of all (fully invariant) congruences containing C.

For θ, ϕ ∈ Con(A), their relational product, defined as

θ ◦ ϕ := { (x, z) ∈ A2 | ∃y ∈ A, (x, y) ∈ θ, (y, z) ∈ ϕ }

is not necessarily a congruence on A; as is well known, θ ◦ ϕ is a congruence if andonly if θ and ϕ permute, i.e., if and only if

θ ◦ ϕ = ϕ ◦ θ

and, in this case, it is the smallest congruence containing them, i. e., Cg(θ ∪ ϕ) =θ ◦ ϕ. Occasionally, we may write θ ◦k ϕ to denote the k-fold relational productθ◦ϕ◦. . . with alternating factors θ and ϕ. We say θ and ϕ k-permute if θ◦kϕ = ϕ◦kθ.If this is the case, then Cg(θ ∪ ϕ) = θ ◦k ϕ. In general, the smallest congruencecontaining two given congruences θ, ϕ may be described by

Cg(θ ∪ ϕ) =⋃

n≥1

θ ◦n ϕ

An algebra A is congruence (k-)permutable if all pairs of congruences of A(k-)permute. A class of algebras is congruence (k-)permutable if all its membersare.

2. TERMS, SATISFACTION AND FREE ALGEBRAS 3

2. Terms, satisfaction and free algebras

Given a nonempty set X and a similarity type τ , Tτ (X) is the smallest set suchthat:

(i) X ⊆ Tτ (X);(ii) If f ∈ τ and t1, . . . , tar(f) ∈ Tτ (X), then f(t1, . . . , tar(f)) ∈ Tτ(X).

Elements of Tτ (X) are called terms. Elements of X are called variables.

The term algebra (also called absolutely free algebra) of type τ = (fi)i∈I , gen-

erated by a set X , is the algebra Tτ (X) = 〈Tτ (X), (fTτ(X)i )i∈I〉, such that

fTτ (X)i (t1, . . . , tar(fi)) = fi(t1, . . . , tar(fi))

In the following, we will suppose X is a fixed countably infinite set X ={ x0, x1, . . . } of variables. A term t ∈ Tτ (X) is called n-ary if all the variablesthat occur in t belong to { x0, . . . , xn−1 }.

Let A = 〈A; (fAi )i∈I〉 be an algebra of type τ . For any n ≥ 0, each n-ary termt determines an n-ary term operation tA: 1

xAi (a0, . . . , an−1) = ai

(f(t1, . . . , tar(f)))A(a0, . . . , an−1) = f

A(tA1 (a0, . . . , an−1), . . . , tAar(f)(a0, . . . , an−1))

If B ⊆ A, then Su(B), the subuniverse generated by B, may also be describedby

Su(B) = { a ∈ A | a = tA(b0, . . . , bn−1) for some n-ary term t and b0, . . . , bn−1 ∈ B }

An identity of type τ is an element of Tτ (X) × Tτ (X), i.e., a pair of terms oftype τ . As usual, we will write an identity (s, t) as s ≈ t.An equational theory of type τ is a fully invariant congruence of the term algebraTτ (X). A set Σ0 of identities is an axiomatization of an equational theory Σ if

Σ = Cgfi(Σ0)

Remark. The above definition of equational theory may not be the most com-mon, but it is easy to check that it is equivalent to the standard one (being closedunder logical consequence). Our definition is more in line with the general approachthat is taken to these matters in the thesis, where logical consequence or equiva-lence are dealt with under the hood by essentially algebraic devices (namely freealgebras and clones — see below).

An algebra A of type τ satisfies an identity t ≈ s, in symbols A |= t ≈ s, ift and s induce the same term operation on A, i. e., if tA = sA. If Σ is a set ofidentities, then we say that A satisfies Σ, or is a model of Σ, if A satisfies everymember of Σ. A class K of algebras of type τ is said to satisfy an identity t ≈ s(or set of identities Σ) if every algebra in K does; and then we write K |= t ≈ s (orK |= Σ).

For any set Σ of identities of type τ , Mod(Σ) is the class of all models of Σ.For any class K of algebras, Id(K) is the set of all identities satisfied in all membersof K. For a set Y of variables, we will also write IdY (K) to denote the set of thoseidentities holding in K and whose variables belong to Y .

1It may be shown by an easy induction that each t ∈ Tτ (X) can be represented asf(t1, . . . , tar(f)), with f ∈ τ and t1, . . . , tar(f) ∈ Tτ (X) in a unique way; thus each term op-

eration is well defined.

4 0. PRELIMINARIES

It is well known that Mod and Id determine a Galois connection between setsof identities and classes of algebras. The closed sets of identities, i.e. those sets Σsuch that

Σ = Id(Mod(Σ))

are the equational theories; the closed classes K of algebras, i.e., such that

K = Mod(Id(K))

are called varieties:

A class V of algebras of type τ is called a variety, or equational class, ifV = Mod(Σ) for some equational theory Σ (and thus V = Mod(Id(V))). Anaxiomatization of a variety V is an axiomatization of Id(V).

A famous theorem by Birkhoff [4] asserts that a class of algebras is a variety ifand only if it is closed under direct products, subalgebras and homomorphic images;often this characterization is used as a definition of variety, whereas equational classis defined as above (and Birkhoff’s theorem can thus be formulated as the statementthat varieties and equational classes coincide).

In this thesis, we will almost always be interested in varieties qua equationalclasses, i.e., as the classes of all models of certain equational theories.

If the similarity type of the algebras in a variety V has only finitely manyoperation symbols, we say V is of finite type; and we say V is finitely based if it hasa finite axiomatization, i. e., if it can be described by finitely many identities.

Let V be a variety. An algebra A ∈ V is freely generated (as a V-algebra) by aset Y ⊆ A if the following universal property holds:

For each algebra B ∈ V and each map φ : Y → B, there exists aunique homomorphism φ̂ : A → B such that φ̂|Y = φ.

If an algebra A ∈ V is freely generated by some subset Y , then we say A is a freealgebra.

A variety V is said to be trivial if it contains only one-element algebras; other-wise, V is nontrivial.

It is well known that, given a nontrivial variety V , of type τ , and any nonemptyset Y , there exists a free algebra in V freely generated by Y . This free algebra maybe realized, up to isomorphism, as Tτ (Y )/ IdY (V).

Remark. Of course, one can define free algebra, in terms of the universalproperty above, with respect to any class of algebras, not necessarily a variety; forour purposes, the above definition is all that is required. For arbitrary classes, freealgebras need not always exist (but they always exist for classes which are moregeneral than varieties, namely quasi-varieties, i.e., classes which are closed undersubalgebras and direct products — see [15, page 167]).

3. Lattices, semilattices

Let τ be a similarity type with two operation symbols, ∨,∧, both of arity 2.As is customary, we will write these symbols as infix binary operators, and oftenrefer to them as join and meet, respectively. A lattice is an algebra L = 〈L;∨,∧〉such that the following identities hold in L:

x ∨ x ≈ x x ∧ x ≈ x (idempotency)

x ∨ y ≈ y ∨ x x ∧ y ≈ y ∧ x (commutativity)

x ∨ (y ∨ z) ≈ (x ∨ y) ∨ z x ∧ (y ∧ z) ≈ (x ∧ y) ∧ z (associativity)

x ∨ (y ∧ x) ≈ x x ∧ (y ∨ x) ≈ x (absorption)

3. LATTICES, SEMILATTICES 5

The lattice L is said to be distributive if

x ∨ (y ∧ z) ≈ (x ∨ y) ∧ (x ∨ z)

holds and is said to be modular if

x ∨ (y ∧ (x ∨ z)) ≈ (x ∨ y) ∧ (x ∨ z)

holds.

From the above definition, it is clear that the class of lattices is a variety,as are the classes of distributive lattices and of modular lattices; and that everydistributive lattice is modular.

The congruences on any algebra A form a lattice Con(A) = 〈Con(A);∨,∧〉with the operations defined by θ ∧ ϕ := θ ∩ ϕ, θ ∨ ϕ := Cg(θ ∪ ϕ).

Another variety which will be considered is the variety of semilattices, i. e., of allalgebras S = 〈S; ·〉 where · is a binary operation which is associative, commutativeand idempotent. Each semilattice operation induces an order relation, defined byx ≤ y ⇔ x · y = y.

Thus every lattice L = 〈L;∨,∧〉 has a natural order, given by

x ≤ y ⇔ x ∨ y = y

which is the semilattice order associated to its semilattice reduct 〈L;∨〉.

Remark. To each semilattice S = 〈S; ·〉, one might as well associate the dualorder, given by x ≤∗ y ⇔ x · y = x. For a lattice 〈L;∨,∧〉, the dual order is thesame as the order associated to its dual lattice 〈L;∧,∨〉, for it is easy to check that,for any elements x, y ∈ L, x ∨ y = y if and only if x ∧ y = x.

Lattices may also be viewed as special partially ordered sets. A partial order≤ on a set L is said to be a lattice order if any two elements have a least upperbound (lub) and a greatest lower bound (glb). If this is the case, then often theposet (L,≤) is said to be a lattice-ordered set or, more colloquially, a lattice.

A lattice (L,≤) is complete if all subsets of L have a lub and a glb.A filter2 F of a lattice L is a nonempty subset of L such that, for all a, b ∈ L,

the following two conditions hold:

1. If a ∈ F and a ≤ b, then b ∈ F ;2. If a, b ∈ F , then a ∧ b ∈ F

A filter is proper if it is not the whole lattice. For any nonempty subset Xof L, the filter generated by X , denoted [X), is the intersection of all filters of Lcontaining X . It may be described as

[X) = { a ∈ L | ∃n > 0 ∃x1, . . . , xn ∈ X : ∧ni=1xi ≤ a }

A principal filter is a filter generated by a one-element subset.

A filter F of a lattice L is prime if F is proper and, for any a, b ∈ L,

a ∨ b ∈ F =⇒ a ∈ F or b ∈ F

An ultrafilter is a maximal proper filter. If I is a set, then by an ultrafilter onI is meant an ultrafilter of the lattice 〈P(I);∪,∩〉, where P(I) is the powerset of I.

Let A =∏

i∈I Ai be a product of sets, and a,b ∈ A; then

[[a = b]] := {i ∈ I | ai = bi}

2The dual notion is that of an ideal. Some authors use the expression dual ideal as a synonymfor filter.

6 0. PRELIMINARIES

denotes the set of coordinates where a and b are equal. If U is an ultrafilter on I,then the binary relation θU defined on A by

a θU b :⇐⇒ [[a = b]] ∈ U

is an equivalence relation. The quotient A/θU is called an ultraproduct (over U)of the Ai, i ∈ I, and is often denoted by

∏

U Ai. If A =∏

i∈I Ai is a product ofalgebras, then θU defined as above is a congruence on A and the quotient algebra∏

U Ai := A/θU is called an ultraproduct (over U) of the algebras Ai, i ∈ I.

4. Topological basics

A topology on a set X is a subset τ of the powerset of X such that the followingconditions hold:

• ∅, X ∈ τ ;• if U, V ∈ τ , then U ∩ V ∈ τ ;• if Ui ∈ τ for each i ∈ I, then

⋃

i∈I Ui ∈ τ .

A topological space is a pair (X, τ), where τ is a topology on X . Often we leavethe topology implicit, and refer to the topological space X , rather than (X, τ). If(X, τ) is a topological space, and U ⊆ X , then U is called open if U ∈ τ and closedif X \U is open. Thus arbitrary intersections of closed sets are closed, so the closureof any subset Y of X ,

cl(Y ) :=⋂

{C | Y ⊆ C, C closed }

is well defined and is the smallest closed set containing Y . We will write cl(y) as ashorthand for cl({ y }).

A common method for describing a topology is by way of a basis (of open sets).A basis for a topology τ is a subset B of τ such that the members of τ are preciselythe sets which can be obtained as unions of members of B. A member of B is thencalled a basic open set.

A function f : X → Y , where X and Y are topological spaces, is continuous iff−1(U) is an open set in X , for each (basic) open set U in Y . A homeomorphismis a bijection f : X → Y such that both f and its inverse f−1 : Y → X arecontinuous.

A metric on a set X is a map d : X × X → [0, +∞[ such that the followingconditions hold, for all x, y, z ∈ X :

d(x, x) = 0

d(x, y) + d(y, z) ≥ d(x, z) (triangle inequality)

d(x, y) = d(y, x) (commutativity)

d(x, y) = 0⇒ x = y

A metric space is a pair (X, d), where d is a metric on X . If (X, d) is a metricspace, x ∈ X and ε is a positive real number, the open ball of center x and radiusε is defined to be the set

Bε(x) := { y ∈ X | d(x, y) < ε }

Every metric determines a topology in a natural way, by taking the set

B = {Bε(x) | x ∈ X, ε ∈]0, +∞[ }

as a basis of open sets.

4. TOPOLOGICAL BASICS 7

A topological space X is said to be T0 if, whenever a and b are distinct points ofX , there is a closed subset of X containing one of the points that does not containthe other. Equivalently, X is T0 if, for any a, b ∈ X ,

a ∈ cl(b) & b ∈ cl(a) =⇒ a = b

X is T1 if, for each a ∈ X , the singleton set {a} is closed. Equivalently, X is T1 if,for any a, b ∈ X ,

a ∈ cl(b) =⇒ a = b

A subset N of a topological space X is a neighborhood of a point a ∈ X if it containsan open set containing a, i. e., if there exists an open set U such that a ∈ U ⊆ N .A topological space X is T2, or Hausdorff, if, for each a ∈ X , the intersection of

the closures of the neighborhoods of a is⋂

cl(N) = {a}; or, equivalently, if, given

any b 6= a, there exist disjoint open sets U , V with a ∈ U and b ∈ V .

The implications T2 =⇒ T1 and T1 =⇒ T0 follow immediately from thesedefinitions: if X is T2 then each singleton set {a} is the intersection of closed sets,hence is closed (so T2 =⇒ T1); if X is T1 and a, b ∈ X are distinct then { a } is aclosed set containing one of the points and not containing the other (so T1 =⇒ T0).

It is not true that T0 =⇒ T1, for it can be easily checked that the 2-elementŚierpinski space ({ 0, 1 }, { ∅, { 0 }, { 0, 1 } }) is T0 but not T1; nor is it true thatT1 =⇒ T2, for any infinite space with the cofinite topology (where the nonemptyopen sets are precisely the cofinite sets) is T1 but not T2.

Every topological space X whose topology is induced by a metric is T2: for,given a 6= b ∈ X , we have d = d(a, b) > 0, and hence Bε(a), Bε(b) are disjoint opensets containing a, b as long we pick ε ≤ d2 .

The product of a family ((Xi, τi))i∈I of topological spaces is the space (X, τ)where X =

∏Xi is the direct product of the Xi and τ is the product topology : a

basis for τ is

B = {∏

Ui | Ui ∈ τi, Ui = Xi for all but finitely many i }

If (X, τ) is a topological space and θ is an equivalence relation on X , an openset U ∈ τ is θ-saturated if U is a union of θ-classes or, equivalently, if x ∈ U impliesx/θ ⊆ U . The quotient set X/θ is naturally topologized by the quotient topology:

τ/θ := {U/θ | U ∈ τ, U θ-saturated}

The space (X/θ, τ/θ) is called a quotient space.

If U is an ultrafilter on a set I, then the ultraproduct (over U) of the spaces(Xi, τi), i ∈ I, is the space (

∏

U Xi, τ), where τ is called the ultraproduct topology

on∏

U Xi, and is the topology generated by the sets of the form(∏

i∈I Oi)/θU

where Oi ∈ τi.The ultraproduct of (Xi, τi), i ∈ I, can be constructed in two steps, as fol-

lows: first give the product∏

i∈I Xi the box topology (whose basis is∏

i∈I τi); thengive the quotient set

∏

U Xi the quotient topology induced by the natural map

ν :∏

i∈I Xi →(∏

i∈I Xi)/θU : x 7→ x/θU .

8 0. PRELIMINARIES

5. Categorical basics

A category is a structure C comprising

• a class Obj(C) of objects ;• for any two objects A, B a set HomC(A, B) of arrows, or morphisms, from

A to B;• a law of composition of morphisms

◦ : HomC(B, C) ×HomC(A, B)→ HomC(A, C)(α, β) 7→ α ◦ β

such that the following conditions are satisfied:

(associativity) For any objects A, B, C, D and arrows α ∈ HomC(A, B),β ∈ HomC(B, C), γ ∈ HomC(C, D),

γ ◦ (β ◦ α) = (γ ◦ β) ◦ α

(identity arrow) For each object A, there exists an arrow 1A ∈ HomC(A, A)such that 1A ◦ α = α, β ◦ 1A = β whenever these compositions are defined,i.e. whenever α ∈ HomC(C, A), β ∈ HomC(A, B), for some objects B, C.

We may drop the subscript and write Hom(A, B) instead of HomC(A, B) when itis safe to leave C implicit; if α ∈ HomC(A, B), we say α is an arrow (in C) from Ato B, A is called the domain of α and B is its codomain. Any of the expressions

α : A→ B Aα→ B B

α← A

has the same meaning as α ∈ Hom(A, B). An arrow α : A→ B is an isomorphismif there exists an arrow β : B → A such that α ◦ β = 1B and β ◦ α = 1A. If thereis an isomorphism α : A→ B, we say A and B are isomorphic and write A ∼= B.

Remark. In many instances, it is somewhat irrelevant what the actual objectsof a category are. This should be readily apparent in the definition of abstract clone,in Chapter 1, where we specify how many objects there should be, but do not carewhat they actually are, because we are only interested in the arrows.

In fact, one can easily give an equivalent definition of category in terms of thearrows alone; we won’t pursue this path further.

The category Set has all sets as objects and ordinary maps between sets asarrows. Identity arrows and composition are defined in the obvious way.

By a category of algebras we mean a category whose objects are algebras (ofsome fixed similarity type τ) and whose arrows are (all) the morphisms of algebrasof type τ between those algebras. Associativity is clear and the identity arrows are,of course, the identity homomorphisms. Isomorphisms in the sense just definedcoincide with the usual algebraic isomorphisms (i.e. bijective homomorphisms).

Varieties, in particular, may be viewed as categories of algebras, in this sense.

The class of topological spaces may also be viewed as a category, with objectsall topological spaces and arrows all continuous maps. The isomorphisms in thiscategory are the homeomorphisms.

A category D is a subcategory of a category C if Obj(D) is a subclass of Obj(C)and, for D-objects A and B,

HomD(A, B) ⊆ HomC(A, B) (1)

and composition of two morphisms in D coincides with their composition as mor-phisms in C. If equality in (1) holds for all A, B ∈ Obj(D), we say the subcategoryD is full.

5. CATEGORICAL BASICS 9

The dual of a category C is a category Cop with the same objects but with arrows(and composition) reversed, i.e, Obj(Cop) = Obj(C) and, for A, B ∈ Obj(Cop),HomCop(A, B) = HomC(B, A), i.e. α is an arrow from A to B in Cop if and only ifα is an arrow from B to A in C.

For any notion defined in terms of arrows, its dual is the notion obtained byreversing the arrows; thus any property so defined holds in a category C if and onlyif its dual holds in Cop.

A coproduct of a family Ai of objects of a category C is an object A of Ctogether with a family of arrows αi : Ai → A (called injections) such that thefollowing universal property is satisfied:

• For any B ∈ Obj(C) and any family βi : Ai → B of arrows, there is a uniquearrow γ : A→ B such that, for each i,

βi = γ ◦ αi

The dual notion is that of a product.Coproducts, as well as products, are determined only up to isomorphism.

A functor F from a category C to a category D, written F : C → D, consistsof an object map F : Obj(C) → Obj(D) and, for each A, B ∈ Obj(C), an arrowmap F : HomC(A, B)→ HomD(F (A), F (B)) such that the following conditions aresatisfied:

1. For each A ∈ Obj(C), F (1A) = 1F (A);2. For each A, B, C ∈ Obj(C) and α : A→ B, β : B → C,

F (β ◦ α) = F (β) ◦ F (α)

Thus a functor preserves identity arrows and composition.The identity functor 1C : C → C is a functor such that its object map and arrow

maps are identity maps.Functors are composed in the natural way, i. e., if F : C → D, G : D → E , then

G ◦ F is defined by composing the object maps and arrow maps of G and F .A functor F : C → D is an isomorphism (of categories) if there exists a functor

G : C → D such that G◦F = 1C and F ◦G = 1D. Categories C and D are isomorphicif there exists an isomorphism F : C → D.

By a concrete category we mean a category C equipped with a forgetful functorUC : C → Set. Categories of algebras, as well as the category of topological spaces,may be viewed as concrete categories in an obvious way: the forgetful functorassigns to each algebra (or topological space) its universe (forgetting the additionalstructure, hence the name). One also refers to these as categories of sets withstructure, for their objects are sets with some additional structure (either algebraicor topological) and the arrows are the maps that preserve that structure.

A concrete functor F : C → D, where C and D are concrete categories is afunctor which commutes with the forgetful functors, i.e., such that UD ◦ F = UC .

CHAPTER 1

Interpretability types and clones of varieties

The lattice L of interpretability types was introduced by W. D. Neumann [28].It provides an adequate context in which questions involving so-called Maltsevtype conditions may be conveniently addressed. Closely related to the notion ofinterpretability is the notion of the clone of a variety.

In this chapter we put together these concepts and the results which we willrequire later in the thesis. We begin by recalling a number of well known resultswhich describe important properties of varieties by way of (necessary and suffi-cient) conditions that stipulate the existence of some terms obeying prescribedidentities; conditions of this kind are referred to as Maltsev conditions, in honor ofA. I. Maltsev. Later on in this chapter, we will see how these conditions may bestbe understood by considering the filters of L to which they naturally correspond.These filters are appropriately called Maltsev filters.

1. Maltsev type conditions

A. I. Maltsev’s Theorem 1.1 below shows that permutability of congruences isequivalent to the existence of a special ternary term. This was the first of a series ofresults which characterize a number of properties of varieties, such as distributivityor modularity of the congruence lattices, by way of conditions which postulate theexistence of terms obeying some prescribed identities.

Conditions of this kind have thus become known as Maltsev conditions. I willnot provide a formal definition of Maltsev condition. Instead, I prefer to workwith Maltsev filters, which render the subject into a nice algebraic setting. Maltsevfilters will be formally introduced in the next section.

Congruences on free algebras play a crucial part in the proofs of these theo-rems. One very useful observation that comes out of these theorems is that someproperties, such as modularity of the congruence lattice, hold for all algebras in avariety if and only if they hold for one appropriate free algebra in that variety.

We now present Maltsev’s Theorem and a few others of the same flavor, whichwe will use throughout this thesis.

Theorem 1.1 ([24]). All algebras in a variety V have permutable congruencesif only if there exists a ternary V-term p such that

V |= p(x, z, z) ≈ x, p(x, x, z) ≈ z

Before we prove Theorem 1.1, we pause to note a property of free algebraswhich is often used, sometimes without mention, and plays a relevant part in theproof of this theorem, as well as in the (omitted) proofs of other theorems of thissection (namely, Theorems 1.3, 1.4 and 1.7).

Lemma 1.2. Let V be a variety, X a nonempty set and let F be the free V-algebra freely generated by X. Let θ be the congruence on F generated by a pair(x, y) of distinct free generators, and let G be the subalgebra of F generated byX \ { x }. Then θ|G is the identity congruence of G.

11

12 1. INTERPRETABILITY TYPES AND CLONES OF VARIETIES

Sketch of Proof. The reader may check that θ is the kernel of the uniquehomomorphism φ : F → G such that φ(x) = φ(y) = y and φ leaves the rest of thefree generators fixed. Thus θ|G is the kernel of φ|G , which is clearly the identitymorphism of G.

Proof of Theorem 1.1. Suppose p is a term satisfying the identities above.Let A ∈ V , θ, φ ∈ Con(A), and suppose that (a, b) ∈ θ ◦ φ. Take c such that aθcφb.Then

a = pA(a, c, c)φpA(a, c, b)θpA(c, c, b) = b

Thus θ ◦ φ ⊆ φ ◦ θ, so θ and φ commute. Conversely, suppose that all congruencesin all algebras of V commute. Let F be the free V-algebra on three generators x,y, z. Let α = Cg(x, y) and β = Cg(y, z). Clearly, (x, z) ∈ α ◦ β. By assumption,there must exist p ∈ F such that

xβpαz

Let p be a ternary V-term such that p = pF(x, y, z). Clearly, xβp(x, y, z)βp(x, z, z).But β restricted to the subalgebra of F generated by { x, z } is the identity, byLemma 1.2. Thus x = p(x, z, z). Analogously, we have z = p(x, x, z). Since theseequalities hold on a free algebra, they hold in V .

Theorems of the same flavor have been established by different authors for anumber of other properties. Very noteworthy are the characterizations of congru-ence distributivity and congruence modularity, which are given below. We omit theproofs here; they can be obtained from the given references.

Theorem 1.3 ([21]; or see Theorem 4.144 of [25] ). All algebras in a varietyV have distributive congruence lattices if and only if there exists an integer n andternary V-terms d0, . . . , dn such that the following identities hold in V:

d0(x, y, z) ≈ x

di(x, y, x) ≈ x (0 ≤ i ≤ n)

di(x, x, z) ≈ di+1(x, x, z) (0 ≤ i ≤ n− 1, i even)

di(x, z, z) ≈ di+1(x, z, z) (0 ≤ i ≤ n− 1, i odd)

dn(x, y, z) ≈ z

Theorem 1.4 ([10]; or see Theorem 2.2 of [13]). All algebras in a variety Vhave modular congruence lattices if and only if there exists an integer n and qua-ternary V-terms m0, . . . , mn such that the following identities hold in V:

m0(x, y, z, w) ≈ x

mi(x, y, y, x) ≈ x (0 ≤ i ≤ n)

mi(x, x, w, w) ≈ mi+1(x, x, w, w) (0 ≤ i ≤ n− 1, i even)

mi(x, y, y, w) ≈ mi+1(x, y, y, w) (0 ≤ i ≤ n− 1, i odd)

mn(x, y, z, w) ≈ w

Definition 1.5. For each k ≥ 2, we let Mk denote a variety with quaternaryfundamental operations m0, . . . , mk obeying the equations of Theorem 1.4.

Theorem 1.6 ([17]; see [23] for a different proof). All algebras in a variety Vhave modular congruence lattices if and only if there exists an integer n and ternary

1. MALTSEV TYPE CONDITIONS 13

V-terms q0, . . . , qn−1, p such that the following identities hold in V:

q0(x, y, z) ≈ x

qi(x, y, x) ≈ x (0 ≤ i ≤ n− 1)

qi(x, x, y) ≈ qi+1(x, x, y) (0 ≤ i < n− 1, i even)

qi(x, y, y) ≈ qi+1(x, y, y) (0 ≤ i < n− 1, i odd)

qn−1(x, y, y) ≈ p(x, y, y)

p(x, x, y) ≈ y

The following theorem, due to E. T. Schmidt, generalizes Theorem 1.1 tok-permutable varieties, for any given k. It can be proved by an entirely similarargument.

Theorem 1.7 ([30]). All algebras in a variety V have k-permutable congru-ences if and only if there exist (k+1)-ary V-terms q0, . . . , qk such that the followingidentities hold in V:

q0(x0, . . . , xk) ≈ x0

qi(x0, x0, x2, x2, . . . ) ≈ qi+1(x0, x0, x2, x2, . . . ) (0 ≤ i ≤ k − 1, i odd)

qi(x0, x1, x1, x3, . . . ) ≈ qi+1(x0, x1, x1, x3, . . . ) (0 ≤ i ≤ k − 1, i even)

qk(x0, . . . , xk) ≈ xk

Another characterization of k-permutable varieties was obtained by Hagemannand Mitschke. Their characterization manages to depend only on ternary terms,rather than (k + 1)-ary terms. Thus it does not seem surprising that it has becomevery popular. In fact, it appears that Schmidt’s characterization above has falleninto oblivion. Nevertheless, both will be of great use in this thesis.

Theorem 1.8. [20] All algebras in a variety V have k-permutable congruencesif and only if there exist ternary V-terms p0, . . . , pk such that the following areidentities of V:

p0(x, y, z) ≈ x

pi(x, x, z) ≈ pi+1(x, z, z) (0 ≤ i ≤ k − 1)

pk(x, y, z) ≈ z

Sketch of proof. Terms pi can be defined from the qj and vice versa. Forone direction, let

pi(x, y, z) := qi(x, . . . , x︸︷︷︸

i

, y, z, . . . , z︸︷︷︸

k−i

)

For the other direction, define

q0(x0, . . . , xk) := x0

qi(x0, . . . , xk) := pi(xi−1, xi, xi+1)

qk(x0, . . . , xk) := xk

Definition 1.9. For each k ≥ 2, Pk denotes the variety with k + 1 ternaryfundamental operations p0, . . . , pk obeying the identities of Theorem 1.8.


2. The lattice of interpretability types

Definition 1.10. Let V and W be varieties, of types τ = (Ft)t∈T and σ =(Gs)s∈S .

(i) In case no Ft operation symbol is nullary, we say V is interpretable or de-finable in W if there exists a family (αt)t∈T of W-terms such that, for eachW-algebra A, the algebra 〈A; (αAt )t∈T 〉 belongs to V .

(ii) If V has nullary operations, then we will allow them to be replaced by(constant) unary operations. We take V ′ to be a variety identical to V exceptthat the nullary operations of V are replaced by constant unary operationsin V ′. Then we will say V is interpretable in W if V ′ is.

We write V ≤ W to mean V is interpretable in W .

Remarks.

• A variety may fail to have a nullary operation in its type, and yet mayhave a definable constant. For example, the variety of division groups hasonly one binary operation “/”, and thus has no nullary term operations;still, it may be shown that x/x ≈ y/y holds identically and, thus, there is aunary constant term. In fact, groups are interpretable in division groups andconversely. This is one reason why the above definition is stated so fussily.(For the definition of division groups and the interpretation just mentioned,see, for example, [25, page 244].)• In Definition 1.10 (ii), V ′ is intended to be the same as V , except that nullary

operations are replaced by constant unary operations. Specifically, supposeV has nullary operations, and let Σ be an axiomatization of V . We let τ ′

be a new similarity type, identical with τ except that the arity of nullarysymbols is changed to be 1, and we let V ′ be a variety of type τ ′ axiomatizedby Σ′, consisting of the following identities: all of the identities occurring inΣ, modified so that each occurrence of nullary Ft is replaced by Ft(z), fora fixed variable z; plus an identity Ft(x) ≈ Ft(y), for each nullary Ft ∈ τ(where x and y are two distinct variables; this, of course, makes Ft a constantfunction on every algebra of V ′).

It is clear that the above definition makes ≤ a quasi-order on the class of allvarieties. Thus the following concept is quite natural.

Definition 1.11. Let V andW be varieties. If V ≤ W ≤ V , we will say that Vand W are equi-interpretable or that V and W have the same interpretability type.Occasionally, we will denote by [V ] the class of all varieties equi-interpretable withV , and refer to [V ] as the interpretability type of V . It is clear that the class ofinterpretability types is endowed with a partial order if we declare that [V ] ≤ [W ]if and only if V ≤ W . We will denote this class by the letter L.

Example. We have [P2] = [M2]. To show that P2 ≤ M2, we may define thefollowing ternary M2-terms:

p0(x, y, z) := x, p1(x, y, z) := m1(x, x, y, z), p2(x, y, z) := z

To see that M2 ≤ P2, we define the following quaternary P2-terms:

m0(x, y, z, w) := x, m1(x, y, z, w) := p(x, p(x, y, z), w), m2(x, y, z, w) := w

Remark. The attentive reader may have noticed that there is an apparentabuse here, as an interpretability type is a class whose members are themselvesproper classes. This difficulty may be overcome by a number of technical devices,such as replacing a variety by its clone (which we will describe in Section 3).

2. THE LATTICE OF INTERPRETABILITY TYPES 15

L turns out to be a proper class, i. e., a class which is not a set (see [16, page32]). The partial order just described makes L a complete lattice, in the sense thatarbitrary subsets of L have joins and meets in L.

We are now going to describe the joins of arbitrary subsets of L; if L were aset, the existence of arbitrary joins would, by a standard argument, imply also theexistence of meets, and thus would have shown L to be a complete lattice. Thatindeed meets of arbitrary subsets do exist in L can be shown by a clever argumentdue to Jan Mycielski. Since we won’t be using the meet operation in L here, we donot include that proof. The interested reader is referred to [16, page 19].

When working on L, we find it convenient to drop the brackets denoting inter-pretability types, and use the same letter to denote a variety and its interpretabilitytype. Thus we often deal with interpretability types by taking (any) one suitablerepresentative variety in that type.

Proposition 1.12. Let I be any set and let (Vi)i∈I be a family of varietiesindexed by I, taken with disjoint similarity types τi = (Ft)t∈Ti . Also, for each i ∈ I,let Σi be an axiomatization of Vi.Then the join in L of (the interpretability typesof) the Vi is

[V ] =∨

[Vi]

where V is the variety with type τ = (Ft)t∈∪Ti and axiomatized by ∪i∈IΣi.

Proof. It is clear that Vi ≤ V , for all i. On the other hand, if Vi ≤ W , forall i, with terms (αt)t∈Ti witnessing this inequality for each i, then it is clear that(αt)t∈∪Ti affords an interpretation of V in W , so V ≤ W , as required.

Definition 1.13. A strong Maltsev filter in L is a principal filter generated by(the interpretability type of) a finitely based variety of finite type. A Maltsev filterin L is a filter generated by a countable chain of finitely based varieties of finitetype.

From Theorem 1.4 and Definition 1.5 above, it is clear that the interpretabilitytypes of congruence-modular varieties constitute a Maltsev filter, generated by (theinterpretability types of) the varieties Mk, for k ≥ 2.

Similarly, the interpretability types of congruence-distributive varieties consti-tute a Maltsev filter, by Theorem 1.3. Neither of these two is a strong Maltsevfilter, by the results of Fichtner [12].

By Theorem 1.8, the interpretability types of k-permutable varieties, for eachk ≥ 2, constitute strong Maltsev filters. Also of interest is the Maltsev filter ofthose varieties which are k-permutable for some k (which is not a strong Maltsevfilter [31]).

More generally, the notions of Maltsev condition and Strong Maltsev condition,which used to be described in a somewhat cumbersome manner, are completely andnicely recaptured by working with Maltsev filters and strong Maltsev filters.

The question of whether a given Maltsev condition can be implied by, or equiv-alent to, a conjunction of weaker Maltsev conditions translates directly into thecorresponding Maltsev filter failing to be prime, or indecomposable. This topic isconsidered in Chapters 2 and 3 of this thesis.

The one outstanding conjecture which has drawn my attention to this topicand which, through my efforts to settle it, led to the development of the materialin Chapter 2, is the following

Conjecture 1.14 (O. Garcia and W. Taylor [16]). The filter of congruence-modular varieties is prime.


Whether this conjecture is actually correct still remains open. Nevertheless, theresults in Chapter 2 show that if it were false, then the nonprimeness of the filterof congruence modular varieties could not possibly be witnessed by building Dayterms for a join of interpretability types in the same simple way as those for Jónssonterms or for near unanimity terms (both of these are described in Chapter 3; theterms for the filter of congruence-distributivity are due to Garcia and Taylor andthose for near-unanimity to the present author). This, albeit small, progress isperhaps the single most tangible advance toward establishing this long outstandingconjecture since it was published, back in 1984. To actually prove this conjectureseems to be as hard as ever, though. It will probably require a long and difficultwork along similar lines to those pursued by Steven Tschantz, who proved that thestrong Maltsev filter of congruence-permutable varieties is prime, but, as Tschantzpointed out, one should expect this one to be much harder still.

3. The clone of a variety

Our exposition in this section follows closely that of Steven Tschantz in [36,Section 2].

Definition 1.15. An abstract clone is a category C with distinguished objectsAn, for integer n > 0, and distinguished arrows π

ni , for each n > 0 and 0 ≤ i < n,

such that each object of C is one of the An and each An is an n-th direct powerof A1 via the morphisms π

ni , 0 ≤ i < n. The distinguished morphisms will also be

called projections.

The arrows of a clone are often called clone elements. As we are about to see,these will correspond to the terms of a variety (or terms modulo the identities ofthe variety).

If f is a morphism of C with domain Am and codomain An, then the fact thatAn is a power of A1 entails that f is completely determined by the compositionsπn0 f , . . . , π

nn−1f and, conversely, for any tuple (f0, . . . , fn−1) of morphisms from

Am to A1, there is one (and only one) morphism f from Am to An such thatπni f = fi, for all 0 ≤ i < n; thus it is convenient to identify each such f with thetuple (πn0 f, . . . , π

nn−1f). Henceforth we will assume this identification; i. e., for all

practical purposes, a morphism with domain Am and codomain An is an n-tupleof morphisms with domain Am and codomain A1.

A clone element f with domain Am and codomain A1 is said to be m-ary.

A trivial clone is one with a single morphism between any pair of objects. IfC is a nontrivial clone, then it may be shown that all the distinguished morphismsπnt , for n ≥ 1 and 0 ≤ t < n, are distinct.

We fix, once and for all, a set of distinct symbols πnt , for each n ≥ 1 and0 ≤ t < n. These will be the distinguished morphisms of every clone we work with.1

We now make a small extension to our notation, to allow the use of the symbolsπnt as formal projections :

Definition 1.16. Let n be an integer, with n ≥ 1. Let (x0, . . . , xn−1) be ann-tuple of (not necessarily distinct) symbols.

1. For each 0 ≤ t < n, we let

πnt (x0, . . . , xn−1)

1Clearly, we can identify each distinguished morphism of a clone C with the appropriatemember of this fixed set of symbols; or, put another way, every clone is isomorphic, in an obviousand natural way, to a clone where the distinguished morphisms are the symbols we have fixed —see below for the (natural) notion of clone isomorphism.

3. THE CLONE OF A VARIETY 17

denote the symbol xt.2. Let 0 ≤ t1, . . . , tl < n and let α be the tuple (πnt1 , . . . , π

ntl

). Then we let

α(x0, . . . , xk−1)

denote the tuple (xt1 , . . . , xtl).

We will refer to each πnt in this sense as an n-ary formal projection.

We note that, for appropriate n and t, the symbol πnt may, depending on thecontext, represent a formal projection or a distinguished clone element (also calledan (n-ary) projection) of some clone. By Definition 1.15 and the observations thatfollow it, it may be easily checked that both uses of this symbol are compatible 2,so this does not cause any problem.

Definition 1.17. A clone homomorphism from a clone C to a clone D is afunctor F from C to D which respects the distinguished objects and arrows, i. e.,such that F (ACn) = A

Dn and F ((π

ni )

C) = (πni )D. A clone isomorphism from a clone

C to a clone D is a clone homomorphism which is also a categorical isomorphismbetween C and D.

The category of clones, denoted Clone, has all clones as objects and all clonehomomorphisms as arrows.

To each variety V , there corresponds a clone, called the clone of V :

Definition 1.18. For each variety V , the clone of V , denoted Clo(V), is thedual of the full subcategory of V whose objects are An = FV(x0, . . . , xn−1), i. e.the objects of Clo(V) are finitely generated free algebras in V . Each distinguishedmorphism πni is the dual of the unique homomorphism of V-algebras from A1 toAn which takes the generator x0 to xi.

We will be working extensively with clones in Chapter 2. It is important torealize that the clone elements of Clo(V) naturally correspond to V-terms, or termsmodulo the identities of V , i.e., two m-ary terms t, s of the type of V give rise tothe same clone element of Clo(V) if and only if they yield the same term operationon every algebra of V , that is, if and only if V |= t ≈ s.

Conversely, given an abstract clone C, we can take a variety V having, for eachn and each t ∈ HomC(An, A1), an n-ary basic operation f [t]. The defining identitiesof this variety are

f [πni ](x0, . . . , xn−1) ≈ xi

and

f [t(s0, . . . , sn−1)](x) ≈ f [t](f [s0](x), . . . , f [sn−1](x))

for each n-ary term t, sequence of m-ary terms s0, . . . , sn−1 and m-tuple of distinctvariables x.

It is not hard to check that C and Clo(V) are isomorphic objects in the categoryClone.

Given varieties V and W , we have V ≤ W in L if and only if there existsa clone homomorphism from Clo(V) to Clo(W); thus V and W have the sameinterpretability type if and only if there exists a clone homomorphism from Clo(V)

2In a clone C, the fact that the distinguished arrows πnt , with 0 ≤ t < n, are the projec-tions that realize An as a product of n copies of A1 entails that, for any f = (f0, . . . , fn−1) ∈HomC(Am, An), we have the following composition of arrows in C:

πnt (f0, . . . , fn−1) = πnt f = ft ∈ HomC(Am, A1)

Thus the distinguished arrows of C behave, under composition of arrows in C, as formal projections.


to Clo(W) and one from Clo(W) to Clo(V). It is not necessarily the case that theclones be isomorphic in this situation, though.

Given two varieties V and W , it is clear that Clo(V ∨ W) is a coproduct inClone of the two clones Clo(V) and Clo(W).

Since one of our main interests is to discern the primeness of Maltsev filters, itis useful, given the clones of V and W , to have a good description of Clo(V ∨W).Steven Tschantz gave just such a description in [36]. He constructed this coproductin a manner which is analogous to the free product of groups. We present hisconstruction in the next section.

4. Free product of clones

Given two clones C0, C1, we will construct a clone C0 ⋆ C1, which is called thefree product of C0 and C1 and will be shown to be a coproduct of C0 and C1 in thecategory Clone.

Although the construction below can be done at a purely abstract level, it maybe helpful to think of the clones C0, C1 as being the clones of certain varieties, sayC0 = Clo(V0), C1 = Clo(V1); then the coproduct C0 ⋆ C1 we mean to construct willnaturally be intended as Clo(V0 ∨ V1).

If one of C0, C1 is trivial, then C0 ⋆ C1 is defined to be the trivial clone.We will henceforth assume that C0, C1 are nontrivial clones, with the same set

{An | n > 0 } of objects and no common morphisms except the projections.

For each n, we say f is n-ary and f ∈ C0 ∪ C1 if f ∈ HomC0(An, A1) ∪HomC1(An, A1).

Write C = C0 ⋆ C1. This C will, of course, have distinguished objects An, forn > 0. The elements of HomC(An, A1) will be equivalence classes of terms, to be pre-cisely described below. Then HomC(An, Am) will be simply HomC(An, A1)

m, i.e.,the elements of HomC(An, Am) will be all m-tuples of elements of HomC(An, A1).

Take the fixed set of distinct symbols πni , for each n > 0 and each i with0 ≤ i < n; these will be the distinguished morphisms of C.

The terms we are looking for will be built from the πni by formal applicationsof morphisms of C0 and C1. We let f · t denote a formal application of an m-aryf ∈ C0 ∪ C1 to an m-tuple of terms t. Then the set of n-ary terms for C = C0 ⋆ C1is naturally defined recursively:

Definition 1.19. For each n > 0, the set Tn of n-ary terms for C0 ⋆ C1 is thesmallest set such that

• for 0 ≤ i < n, πni ∈ Tn;• for any m > 0, m-ary f ∈ C0∪C1 and m-tuple t ∈ T mn , the formal application

f · t is in Tn.

T (π) will denote the set of all terms which are one of the symbols πni , T (C0) willdenote the set of all terms of the form f · t with f ∈ C0, and T (C1) is similarlydefined.

Terms which always induce the same operations in a variety ought to be identi-fied as clone elements. So clone elements are in fact described as equivalence classesof terms. The detailed constructions of [36] will not be reproduced here. We giveonly a very brief overview of those, one that is enough for our work in the nextchapter.

If σ is a permutation of { 0, . . . , m − 1 }, then we will let πmσ be a shorthandfor (πmσ(0), . . . , π

mσ(m−1)).

Definition 1.20. For each n > 0, define a binary relation ∼ on Tn as thesmallest equivalence relation such that:

4. FREE PRODUCT OF CLONES 19

1. (fπmσ ) · t ∼ f · πmσ (t), for all m-ary f ∈ C0 ∪ C1, t ∈ T

mn and permutation σ

of { 0, . . . , m− 1 }. [Note that πmσ is viewed on the left side as an element ofHom(Am, Am) (in the same clone as f) and on the right as a tuple of formalprojections.]

2. if t = (t0, . . . , tm−1) and t′

= (t′0, . . . , t′m−1) are tuples in T

mn such that

ti ∼ t′i, and f ∈ C0 ∪ C1 is m-ary, then f · t ∼ f · t′.

Terms which are ∼-related will be called similar. m-tuples of terms will be calledsimilar if their components are.

Further identification of terms is necessary. To that end, a confluent and finitelyterminating rewriting system was described on [36], which produces (up to similar-ity) a normal form for each term. Terms is normal form may also be called reducedterms. Thus we will consider the clone elements of C0 ⋆ C1 as the reduced terms,determined only up to similarity. Similar terms will be treated as equal, so we takeany suitable representative of the similarity class of a reduced term.

We are now in position to describe the clone C = C0 ⋆ C1, by indicating whatits morphisms are and how composition is defined. This is done in the next twodefinitions.

Definition 1.21. For each n > 0, we let HomC(An, A1) be the set of similarityclasses of reduced n-ary terms. We also take πni to denote the similarity class ofthe term πni (which can be seen to contain only π

ni ); these will, of course, be the

distinguished morphisms of C.For each n, m > 0, we let HomC(An, Am) := HomC(An, A1)

m, i. e. the morphismsfrom An to Am are m-tuples of morphisms from An to A1.

Having defined the morphisms of the clone, we must define the compositionoperation. Let ρ(t) denote the normal form of a term t, as described above.

Definition 1.22. For s a k-ary term or m-tuple of k-ary terms and u ∈ T kn ,we define s ◦ u to be an n-ary term or m-tuple of n-ary terms, as follows:

If s = (s0, . . . , sm−1) is an m-tuple of k-ary terms, let

s ◦ u := (s0 ◦ u, . . . , sm−1 ◦ u)

If s = πki , for some i < k, then s ◦ u is the i-th component of u;Otherwise, s = f · t, for some m-ary f ∈ C0 ∪ C1 and m-tuple t ∈ T mk ; then

s ◦ u := f · (t ◦ u)

We let su := ρ(s ◦ u) and call su the composition of s and u.

Theorem 1.23 ([36]). The morphisms given by Definition 1.21 and the com-position given by Definition 1.22 make C a clone. Furthermore, C is a coproduct ofC0 and C1 in the category Clone.

We need only a small but most important observation concerning the normalforms of terms:

Theorem 1.24 ([36]). Let e ∈ { 0, 1 } and let t = f · (t0, . . . , tm−1) ∈ T (Ce) bea reduced n-ary term in C0 ⋆ C1. Then, for each i ∈ { 0, . . . , m− 1 },

1. ti is reduced;2. ti ∈ T (C1−e) ∪ T (π).

Thus, from the previous Theorem, reduced terms can be seen to be headed byelements from one clone, with arguments headed by operations from the other, soalternating until projections occur at the leaves. Thus a natural notion of depth,defined below, indicates how deeply elements from both clones are applied to eachother:


Definition 1.25. For reduced terms in C0 ⋆ C1, we define a notion of depthrecursively as

depth(πni ) := 0;depth(f · (t0, . . . , tm−1)) := 1 + max{ depth(t0), . . . , depth(tm−1) }

Let h be an n-ary clone element of C0 ⋆ C1 (thus h is a similarity class of reducedn-ary terms). The depth of h is defined to be the depth of any representative termin the similarity class h.

A reduced term of depth 1 in C is, up to similarity, just f · πmσ for some m-ary f ∈ Ce and σ the identity permutation. Thus reduced terms of depth 1 in Cnaturally correspond to elements in either C0 or C1. A reduced term of depth 2 hasthe form f · (t0, . . . , tm−1), for some f ∈ Ce and t0, . . . , tm−1 ∈ T (C1−e) ∪ T (π),where all ti have depth at most 1, and thus do not involve any more terms fromCe. Thus these ti act as variables, as far as the Ce term operation associated withf is concerned.

Keeping in mind that the clone elements of C0⋆C1 are intended to represent theterms of a join of varieties, we will feel free to denote the reduced terms of C0 ⋆ C1less formally; so we will allow ourselves to drop the dot in an expression such asf · (t0, . . . , tm−1) and write f(t0, . . . , tm−1) instead.

CHAPTER 2

Compatibility with projections and the primeness

of some Maltsev filters

In this chapter we take a closer look at some Maltsev filters, and consider therelation between the primeness of these filters and the occurrence of a condition,which, to our knowledge, has not been studied before. This condition we callcompatibility with projections.

Our approach to terms and identities in this Chapter is via the clones of vari-eties, introduced in Chapter 1. We recall from Chapter 1 that the clone elementsof Clo(V) were seen to represent V-terms, or terms modulo the identities of V .

Definition 2.1. Let C be a clone. Let (t1, . . . , tn) be a sequence of m-aryelements of C, and let (α1, . . . , αr) be a sequence of m-tuples of k-ary projections.We say that the sequence (t1, . . . , tn) is compatible with projections over (α1, . . . , αr)if there exists a sequence (t′1, . . . , t

′n) of m-ary projections such that the following

two conditions hold, for any i, j ∈ { 1, . . . , n } and l ∈ { 1, . . . , r }:

(i) Whenever tiαl is a projection1, then t′iαl = tiαl;

(ii) Whenever tiαl = tjαl, then also t′iαl = t

′jαl.

We say that C has compatibility with projections over (α1, . . . , αr) if every se-quence of m-ary elements of C is compatible with projections over (α1, . . . , αr).

We say that a variety W has compatibility with projections over (α1, . . . , αr) ifClo(W) has.

As will be seen throughout this chapter, compatibility with projections appearsto go hand in hand with prime filters: in all of the cases we have studied, those filterswhich are known to be or strongly suspected of being prime turn out to be exactlythe ones for which we can establish the validity of an appropriate compatibilitycondition.

Definition 2.2. Let C be a clone. We will say that two m-ary clone elementst1, t2 of C agree on an m-tuple θ of k-ary elements of C if t1θ = t2θ. We will saythat t1 and t2 agree on a set X of m-tuples if they agree on every member of X .

Remark. With the terminology introduced in Definition 2.2, the two condi-tions of Definition 2.1 can be restated thus:

(i′) Whenever tiαl is a projection, then t′i and ti agree on αl;

(ii′) Whenever ti and tj agree on αl, then also t′i and t

′j agree on αl.

In order to make the following arguments clearer, we introduce some notationand terminology:

Definition 2.3. Let α be an m-tuple of k-ary projections. We will say thata clone element t of a clone C satisfies a vertical α-obligation if tα is a projection.We will say that clone elements t1, t2 of a clone C satisfy a horizontal α-obligationif t1α = t2α is not a projection. We represent this pictorially as in Figure 1. When

1Since ti is m-ary and αl is an m-tuple of k-ary elements, tiαl is a well defined k-ary elementof C.

21

22 2. COMPATIBILITY WITH PROJECTIONS

t↓α

πks

t1α— t2

Figure 1. Vertical and horizontal α-obligations

dealing with a sequence (t1, . . . , tn), we will say that a clone element ti satisfiesa horizontal α-obligation if there exists j 6= i such that ti, tj satisfy a horizontalα-obligation.

It is useful to note that, loosely speaking, a compatible sequence of projectionsis one whose members satisfy at least the same obligations as the elements in theoriginal sequence. 2

We will show, for a number of Maltsev filters of a special form, which are goingto include the filters of congruence-permutable, of congruence-distributive and ofcongruence-modular varieties, that those which are prime are precisely those forwhich all varieties outside the filter satisfy compatibility with projections (withrespect to the appropriate tuples, in each case).

To put things into perspective, we are going to define rigorously the type offilters to which our concept of compatibility with projections may usefully be ap-plied.

Definition 2.4. Let α1, . . . , αr be m-tuples of k-ary formal projections.

(i) A finitely based variety V of finite type is called homogeneously determinedby {α1, . . . , αr } if it satisfies the following two conditions:

(a) The type of V consists only of m-ary operation symbols h1, . . . , hn;(b) there exists a finite axiomatization Σ of V such that all members of

Σ are either of the form

hiαl(x0, . . . , xk−1) ≈ hjαl(x0, . . . , xk−1)

or of the form

hiαl(x0, . . . , xk−1) ≈ xt

for some i, j ∈ { 1, . . . , n }, l ∈ { 1, . . . , r } and t ∈ { 0, . . . , k − 1 }.(ii) A Maltsev filter is called homogeneously determined by {α1, . . . , αr } if it

is generated by a chain of varieties V1 ≥ V2 ≥ . . . all homogeneously deter-mined by {α1, . . . , αr }.

Remark. Suppose V is a variety satisfying the conditions of Definition 2.4 (i).Then there exist m-ary elements h1, . . . , hn of Clo(V) such that, for every identity

hiαl(x0, . . . , xk−1) ≈ hjαl(x0, . . . , xk−1) ∈ Σ

we have in Clo(V)

hiαl = hjαl

and for every identity

hiαl(x0, . . . , xk−1) ≈ xt ∈ Σ

we have in Clo(V)

hiαl = πkt

2Technically, this is not exactly true, because, according to our definition, projections cannotsatisfy any horizontal obligations; but, of course, if two elements satisfy a horizontal obligationwhere, say, t1α = t2α, then the corresponding projections t′1, t

′2 do satisfy t

′1α = t

′2α.

1. CONGRUENCE-PERMUTABILITY 23

More generally, if α is any tuple of k-ary formal projections, a variety V has termsh1, h2 satisfying an identity

h1α(x0, . . . , xk−1) ≈ h2α(x0, . . . , xk−1)

if and only if there exist elements h1, h2 of Clo(V) such that

h1α = h2α

is valid in Clo(V) (with α viewed as an element of Clo(V)). Thus one can easilytranslate between identities of V and equations that hold in Clo(V).

The most natural examples of Maltsev filters, such as the filter of congruence-permutable varieties, or the filter of congruence-modular varieties, are homoge-neously determined (by appropriate tuples, in each case), as we will see throughoutthis chapter.

Definition 2.5. Let C be a clone. For a set T = { t1, . . . , tn } of m-ary cloneelements of C and a sequence (α1, . . . , αr) of m-tuples of k-ary projections, we definethe (α1, . . . , αr)-graph of T to be the simple graph whose vertices are t1, . . . , tnand which has an edge between two distinct vertices tj , tl if and only if they satisfya horizontal αi-obligation, for some i.

Compatibility with projections has a direct impact on the way a filter may failto be prime: specifically, it rules out the possibility of building relatively simpleterms to witness nonprimeness. In effect, we have the following

Theorem 2.6. Suppose F is a Maltsev filter homogeneously determined by{α1, . . . , αr } and that all varieties outside F have compatibility with projectionswith respect to (α1, . . . , αr). If V ∨W ∈ F is witnessed by elements of Clo(V ∨W)of depth not greater than 2, each headed by a clone element of Clo(V), then eitherV ∈ F or W ∈ F .

Proof. Suppose that V ∨ W ∈ F is witnessed by the clone elements hi =fi · (t1, . . . , tl), where each fi ∈ Clo(V) and t1, . . . , tl ∈ Clo(W). Suppose W /∈ F .ThenW satisfies compatibility with projections with respect to (α1, . . . , αr); choosea sequence (t′1, . . . , t

′l) of projections compatible with (t1, . . . , tl). Then, since the

W-terms act as variables with respect to the V-operations, it follows that the cloneelements h′i = fi · (t

′1, . . . , t

′l) satisfy at least the same equations as the hi. Since

the elements h′i have depth 1, we can identify them with elements of Clo(V); thusV ∈ F .

In all the examples we know of homogeneously determined filters which arenot prime, their nonprimeness is witnessed by elements of depth 2, all headed byoperations from the same clone. In fact, we have no knowledge of a nonprimeMaltsev filter whose nonprimeness can only be witnessed by terms of depth greaterthan or equal to 3.

1. Congruence-permutability

Notation. Throughout this section, the letters α, β will always denote thefollowing 3-tuples of ternary projections:

α := (π30 , π32 , π

32)

β := (π30 , π30 , π

32)

By the remark following Definition 2.4, it is clear that Maltsev’s Theorem 1.1can be restated as


Theorem 2.7. A variety V is congruence-permutable if and only if there existsa ternary element p of Clo(V) such that

pα = π30 , pβ = π32

A ternary element p satisfying the conditions of Theorem 2.7 will be called aMaltsev element.

The following was proved by Steven Tschantz [36]:

Theorem 2.8. The filter of interpretability types of congruence-permutable va-rieties is a prime filter of L.

This filter is homogeneously determined by (α, β). We proceed to show thatvarieties outside this filter do satisfy compatibility with projections with respect to(α, β).

Theorem 2.9. Let V be a variety which is not congruence-permutable. ThenV has compatibility with projections with respect to (α, β).

Proof. Let V be a variety which is not congruence-permutable. We will show,by induction on n, that, for each sequence (t1, . . . , tn) of ternary elements of Clo(V),there exists a compatible sequence (t′1, . . . , t

′n) of projections.

First, consider the case n = 1: let (t1) be a sequence composed of a singleternary clone element. Since the sequence has length 1, there are no horizontalobligations involved and at most two vertical obligations, and that only in caseboth t1α and t1β are projections. The possible values of t1α and t1β, and thechoice of the projection t′1 for each case, are shown in the following table. In casethere are fewer obligations, there may be more than one choice for t′1.

t1βt1α

π30 π32

π30 π30 ×

π32 π31 π

32

Now let n > 1 and suppose the result holds for sequences of length smaller than n.Take a sequence (t1, . . . , tn).

We may assume that

a) The (α, β)-graph of { t1, . . . , tn } is connected;b) Each element in this sequence has both an α- and a β-obligation (and then,

by the previous assumption, at least one of them must be horizontal);c) Each pair of elements in the sequence is separated by {α, β };d) There is at least one vertical obligation.

for if any of these conditions fails it is fairly trivial to produce a sequence of pro-jections, as required.

We will assume, without loss of generality, that t1 satisfies a vertical α- anda horizontal β-obligation. 3 Let (t′2, . . . , t

′n) be a sequence of projections which is

compatible with (t2, . . . , tn). We will write B1 := { i ∈ { 2, . . . , n } | tiβ = t1β }.Note that, by our assumptions, B1 6= ∅; so we may as well suppose that 2 ∈ B1.Our proof proceeds by cases.

Case 1. t1α = π32 : then we take t

′1 to be either π

31 or π

32 , so as to have t

′1β = t

′2β.

3Note that the order of the members of the sequence is irrelevant and that there is a symmetrybetween α and β.

2. CONGRUENCE-k-PERMUTABILITY 25

Case 2. t1α = π30 : this forces t

′1 to be π

30 . In case t

′2 is π

30 or π

31 , the required

obligations are met. If t′2 = π32 , then all t

′i, for i ∈ B1, must be π

32 . But

then replacing each of these t′i by t′′i = π

31 does not violate any obligation,

since the β-obligations are horizontal and π32α = π31α = π

32 . After this

replacement, choosing t′1 = π30 meets all the required obligations.

From Theorem 2.9 and Theorem 2.6, we immediately derive

Corollary 2.10. If V ∨ W is congruence permutable, then either all Malt-sev elements of Clo(V ∨ W) have depth at least 3, or one of V, W is congruencepermutable.

This result is, of course, weaker than Tschantz’s Theorem 2.8. Nevertheless, itseems worthy to present it here, for two reasons: first, because this proof is quitesimple (while Tschantz’s proof is exceptionally difficult), and still lets us know that,given the clones of two non-permutable varieties, there can be no Maltsev elementsof depth 2 in their coproduct; second, because this is really a poster case wherecompatibility with projections holds. The examples described in the next sectionslend credence to the idea that compatibility with projections provides a viable wayto distinguish among many Maltsev filters those that are prime and those that arenot.

Remark. For the specific case of the filter of congruence-permutable vari-eties, we can in fact establish compatibility with projections by describing, for anon-permutable variety V , an explicit function from ternary elements of Clo(V) toprojections: for any ternary t in Clo(V), let

f(t) :=

π30 if tα = π30

π32 if tβ = π32

π31 otherwise

Thus, for any sequence (t1, . . . , tn) of ternary elements of Clo(V), we have thecompatible sequence (f(t1), . . . , f(tn)) of projections.

In the other cases we discuss in this chapter, it does not seem to be possible topresent such a simple function, but the argument we use is similar, although slightlymore complicated. Thus it seemed worthwhile to apply the general argument inthe simplest case first, rather than just proving Theorem 2.9 directly by presentingthis function.

2. Congruence-k-permutability

As in the previous section, it can be shown that, for each k, the filter of inter-pretability types of varieties with k-permutable congruences satisfies an appropriatecondition of compatibility with projections.

We recall that Theorem 1.8, due to Hagemann and Mitschke, offers the simplestMaltsev type description of k-permutability:

Theorem 2.11 ([20]). All algebras in a variety V have k-permutable congru-ences if and only if V ≥ Pk, where Pk is a variety with fundamental operationsp0, . . . , pk, of arity 3, and defining equations

p0(x, y, z) ≈ x

pi(x, x, z) ≈ pi+1(x, z, z) (0 ≤ i ≤ k − 1)

pk(x, y, z) ≈ z


This characterization, although simpler in that only ternary terms are involved,does not satisfy our requirements because in the identities pi(x, x, z) ≈ pi+1(x, z, z)terms on the left and right hand sides are applied to different tuples. An oldercharacterization, due to E. Schmidt, does satisfy our requirements, although it usesterms of arity k + 1, rather than a mere 3. We now recall this result

Theorem 2.12 ([30]). All algebras in a variety V have k-permutable congru-ences if and only if V ≥ P ′k, where P

′k is a variety with fundamental operations

p0, . . . , pk, of arity k + 1, and defining equations

p0(x0, . . . , xk) ≈ x0

pi(x0, x0, x2, x2, . . . ) ≈ pi+1(x0, x0, x2, x2, . . . ) (0 ≤ i ≤ k − 1, i odd)

pi(x0, x1, x1, x3, . . . ) ≈ pi+1(x0, x1, x1, x3, . . . ) (0 ≤ i ≤ k − 1, i even)

pk(x0, . . . , xk) ≈ xk

Theorem 2.12 is the natural generalization of Maltsev’s. That k-permutabilitycan be described by terms of arity 3, as in Theorem 2.11, is somewhat incidental:while a variety is k-permutable if and only if its free algebra with k+1 free generatorsis, no such claim is true for a free algebra with less than k + 1 free generators. Ofcourse, Theorem 2.11 is enormously useful in many contexts, just not in our presentone (we will use it intensively in Chapter 4).

In order to avoid clutter, we present most of our arguments for the case of3-permutability. It should be readily apparent that the same arguments can bepresented for arbitrary k, at the expense of a heavier notation and some additionaldetail.

Notation. Throughout the remainder of this section, the letters β, γ willalways denote the following 4-tuples of quaternary projections:

β := (π40 , π40 , π

42 , π

42)

γ := (π40 , π41 , π

41 , π

43)

The following is obvious

Theorem 2.13. All algebras in a variety V have 3-permutable congruences ifand only if there exist quaternary elements p1, p2 of Clo(V) such that

p1γ = π40

p1β = p2β

p2γ = π43

(2)

Elements p1, p2 of Clo(V) satisfying (2) will called Schmidt elements.

Theorem 2.14. Let V be any variety which is not 3-permutable. Then V hascompatibility with projections with respect to (β, γ).

Proof. We will prove by induction on n that, for any sequence (t1, . . . , tn) ofquaternary elements of Clo(V), there exists a compatible sequence (t′1, . . . , t

′n) of

projections. Actually, we will prove something a little stronger: that this sequencecan be chosen so that, for each i, t′i is one of the two middle projections, π

41 or π

42 ,

except in the cases where it is forced otherwise by a vertical γ-obligation, that isin case tiγ = π

40 or tiγ = π

43 .

Suppose n = 1; let t1 be a quaternary element of Clo(V). Since there is onlyone element, no horizontal obligations are involved and there can be at most twovertical obligations, and that only in case both t1γ and t1β are projections. Thepossible values of t1γ and t1β, and the choice of the projection t

′1 for each case, are

2. CONGRUENCE-k-PERMUTABILITY 27

shown in the following table. In case there are fewer obligations, there may be morethan one choice for t′1, and this choice can clearly be made to respect our strongerrequirement.

t1βt1γ

π40 π42

π40 π40 (A)

π41 π41 π

42

π43 (B) π43

In each of the cases marked (A) and (B), we would be able to define a Maltsevelement for Clo(V), which of course does not exist; so these cases cannot arise forany t1. We illustrate case (A); the other case is entirely similar and left to thereader. So suppose t1 satisfies case (A): then p := t1(π

30 , π

31 , π

32 , π

32) is a Maltsev

element in Clo(V), implying that V is congruence-permutable, a contradiction.Now let n > 1 and suppose the result holds for sequences of length smaller than

n. Take a sequence (t1, . . . , tn).We may assume that

a) The (β, γ)-graph of { t1, . . . , tn } is connected;b) Each element in this sequence has both a β- and a γ-obligation (and then,

by the previous as

Documents

Maltsev Filters - ULisboalfsequeira/math/... · 2013. 6. 5. · The Maltsev ﬁlters of the lattice of interpretability types correspond, in a natu-ral way, to the so-called Maltsev