MANY-VALUED GENERALIZATIONS OF TWO FINITE INTERVALS IN POST’S LATTICEByGraham Campbell DenhamB.Sc., University of Alberta, 1992A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE FACULTY OF GRADUATE STUDIESDepartment ofCOMPUTER SCIENCEWe accept this thesis as conformingto the required standardTHE UNIVERSITY OF BRITISH COLUMBIAJune 1994© Graham Campbell Denham, 1994In presenting this thesis in partial fulfillment of the requirements for an advanced degree at theUniversity of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarlypurposes may be granted by the head of my department or by his or her representatives. Itis understood that copying or publication of this thesis for financial gain shall not be allowedwithout my written permission.Computer ScienceThe University of British Columbia2366 Main MallVancouver, CanadaV6T 1Z4Date:3LM1 t9’-fabstractA study due to Emil Post shows that, although the lattice of clones in two-valued algebraic logicis countably infinite, th&e exist oniy finitely many clones that contain both constants, and onlyfinitely many that contain the negation function. There are, however, uncountably many k-valuedclones for all k > 2; in fact, it is known that uncountably many clones contain all constants.The constants of two-valued logic can also be regarded as the set of noninvertible, unary functions on a two element domain. It is shown here that, for values of k greater than two, there remainonly finitely many k-valued clones containing all such functions. Similarly, one can generalize theset of clones in Post’s lattice that contain the negation function to those k-valued clones that contain aM invertible, unary functions. Once again, there are only finitely many such clones, and theycan be described explicitly.These two generalizations of sets of two-valued clones are presented with an introduction to thestudy of the lattice of clones, and a survey of relevant results. We also note and discuss the factthat the latter result serves to give a description of all homogeneous relation algebras over a finiteunderlying set.11Table of ContentsAbstractList of Figures11iv1 Preliminaries1.1 Introduction1.2 Terminology for clone theory1.2.1 The algebra of functions .1.2.2 The algebra of relations .1.3 Functions with relations113911152 Properties of the Lattice of Clones2.1 The Structure of £(P2)2.2 Coatoms and completeness criteria2.3 Counting clones2.4 Finitely generated clones and coclones3 Two Intervals in £(Pk)3.1 Clones over3.2 Clones over Sk 414 The Intervals in Context4.1 Homogeneous algebras4.2 Homogeneous relation algebras4.3 as endomorphisms4.4 Concluding remarksBibliography 61202023262834345454565759‘IIList of Figures1.1 f(x,y)=et(vel(x,y),neg(et(x,yfl)=x+y.2.2 The lattice of clones of P2 2134404150523.33.43.53.63.7[Q2,P2][123, P3j[S2,P2][S3,P3][54,P]ivChapter 1Preliminaries1.1 IntroductionClone theory is an algebraic study of the composition of functions that provides a common abstraction of two disciplines: multiple-valued propositional logic, and universal algebra. The matterunder study is that of what functions of several variables, over a fixed universe, can be formedfrom other, given functions using composition operations. A set of functions that is closed undercomposition is called a clone.The problem is natural to state in the context of digital circuitry. A function of n variablesmodels a logic gate with n inputs and one output. An expression formed by composition of functionsrepresents a circuit without feedback. A clone, then, corresponds to the set of all circuits that canbe constructed solely from particular types of gates.xy f(x,y)et(x,y) 0 1 vel(x,y) 0 1 0 10 00 0 011 0 1 1 1 1 neg(x) 1 0Figure 1.1: f(x, y) = et(vel(x, y), neg(et(x, y))) = x + yAlgebraic operations, from the point of view of universal algebra, are simply functions of several variables, and terms are the formal composition of operations. The terms of an algebra canthemselves be interpreted as functions of several variables, by evaluation. The set of all functions1Chapter 1. Preliminaries 2that can be expressed as terms of a given algebra form a clone, and, conversely, every clone is theset of term functions for some algebra. The study of clones is thus also intimately related to thestudy of universal algebras.The remainder of this first chapter establishes notation and provides a collection of definitionsrelevant to clone theory, with the intent of keeping the presentation as self-contained as possible.The last section states and proves a fundamental correspondence theorem.Clones over a given domain form a lattice under set inclusion. The second chapter offers aselective introduction and survey of the known properties of this lattice when the domain is finite.Clones over a two-valued domain are completely understood, and their description is summarizedin Section 2.1. When the size of the domain exceeds two, the structure of the lattice is inherentlyfar more complex, and it is impossible to give a description of the same sort.The third chapter presents two parallel results. Both are a determination of all clones overa finite domain containing a given set of unary functions. The first generalizes a result due toJab1onski in order to find the clones containing the non-invertible unary functions, 12krn Thesecond begins with an analogous result due to Salomaa and expands upon a paper by Haddadand Rosenberg in order to treat those clones containing all invertible unary functions, Sk. In bothcases, the argument proceeds by proving and then combining a series of technical lemmata, mostof which are based on the results and methods of Salomaa and Jablonskir. The unary clones thatcontain k and Sk are respectively characterized, and the results are then extended to nonunaryclones. In both cases, there are only finitely many clones over a domain of finite cardinality thatcontain the given unary functions.We conclude by considering how these results generalize their two-valued instances. We indicatethat they also serve to characterize two classes of highly symmetric relation algebras, and leave thereader with some thoughts on further research.Chapter 1. Preliminaries 31.2 Terminology for clone theoryThe definitions and notation used here are, for the most part, drawn from Chapter 1 of Pöschel andKalunin [33] and the universal algebra references of Grätzer [16] or Burns and Sankappanavar [6].We begin with some definitions related to the fundamental objects of clone theory; that is, functions of one or more variables with domain and codomain equal to a fixed set. Let N = {1,2,3,..denote the natural numbers.For a given set A and n E N, let denote the set of all functionsf : Atm - A. LetPA U (1.1)nE NFor any F C PA and n E N, we define F() = F n p5) A function f is said to be of arity nif f E P. Since (1.1) is clearly a disjoint union, we may also define the arity or order functiono : PA —f N by o(f) = n if f e p5. Furthermore, suppose f e Then the ith variable of f,x, for 0 < i < n, is said to be essential if there exist a3 E A, for 0 < j < n, j i, and u, v A,for whichf(ai,a2,. . .,u,. . .,a) f(ai,a2,. . .,v,. .where the u and v are in the ith position. In alternate phrasing, f depends on the ith variable.If this is not the case, the ith variable is said to be fictitious. The essential arity of a function f e PA, denoted by Oe(f), shall then be defined to be the number of variables on which fdepends. If f depends on all of its variables, that is o(f) = oe(f), f itself is said to be essential. If o(f) = 1 or °e(f) = 1, f will be called a unary or essentially unary function, respectively.(n)We also write the range of a function f E asrng(f) = {a : x E Atm such that a = f(x)}.Chapter 1. Preliminaries 4By way of illustrating these definitions, let A = {0, 1}, and let(x1,23) f(xi,x2,3)000 0001 0010 1011 1100 1101 1110 1111 1Then f E p53) and o(f) = 3, but Oe(f) = 2, since f does not depend on its third argument.It wifi often be desirable to apply a function f to the rows of an m x n matrix. If e A for0 i <m and 0 j < n and f E P, we shall write f((a)) to abbreviate the m-tuple whichhas components f(ao,ai,.. .,ai,n_), for 0 i < m.There are several ways to write a function explicitly. In the example above, we made use of atable of values. In order to be somewhat more succinct and descriptive, one may use a generalizationof the familiar conjunctive and disjunctive normal forms from the two-element domain up to afinite domain of arbitrary size. Suppose A = {0, 1,. . ., k — 1} and, using the usual ordering of thenatural numbers, define x A y = mm {x, y}, and abbreviate x A y simply by xy, since the operationis associative. Also let xV y = max{x,y}, and define d E for i E A by(k—i ifx=idz(x)=j0 otherwise.Write d(x) also as xt. Then it is a simple matter to verify that, if f e p52),f(xo,xi,.. = V x°x’ .x’f(ao,ai,. .We can also represent a function f E as a polynomial over a field, if the cardinality ofthe underlying set is a prime power: one identifies A with the field GF(IAI), then writes f as aChapter 1. Preliminaries 5polynomial p E GF(IAI)[xo, xi,. . . , x_i]. This is sometimes called the representation by Zegalkinpolynomials. It will be of use in this document when Al is one of 2, 3, and 4.We shall regard the composition of any two functions in PA as an algebraic operation, in a waywhich the following definitions are intended to make precise. The language and basic concepts ofuniversal algebra provide a natural framework for discussing the composition of logic functions. Thefundamental objects of the discipline of universal algebra itself include the functions PA, and here,as in other areas of mathematics, we find that the objects comprising the theory’s tools are alsoadmissible as objects which the theory describes. Therefore, we shall now outline some conceptsfrom universal algebra, using the text by Burns and Sankappanavar [6] as a reference. The materialthat follows is not intended as an introduction, but rather as a compendium of definitions includedto minimize ambiguity in the chapters that follow, and to indicate explicitly some of the underlyingmathematical notions found in clone theory.We begin by defining partial orders and lattices. Let A be a set together with a binary relationpossessing the following properties for all x, y, z E A:1. x < x (reflexive property)2. x < y and y < z x z (transitive property)3. x < y and y < x =‘ x=y (antisymmetric property)Then the pair (A, <) is called a partial order on A. If, in addition, (A, <) has the further properties:1. There exists an element 0 E A for which Vx E A, 02. There is also an element 1 e A for which Vx e A, x 1,3. For every two elements x, y E A, there exists a unique element, denoted by x A y E A andcalled the meet of x and y, for which x A y < x, x A y < y, and Yz E A if z < x and z < y,then z < x A y.4. Similarly, there exists a unique element x V y e A, called the join of x and y, for which:x<xVy, y<xVy,andVzEAifx<zandy<z,thenxVy<z.Chapter 1. Preliminaries 6(A, <,A, v) is called a lattice. If it is also the case that, for any subset X c A, there exists a uniqueelement AX for which AX < x. Vx X, and if z E A for which z <x, Vx E X, then z AX,and the element V X exists correspondingly, then the lattice is said to be complete. AX is the joinof the set X, called also the infirnum of X. VX is the meet, or the suprernum, of X. An elementx E A is compact ifVXCA: x<VX finiteYCX,forwhichx<VY.A complete lattice in which every element is the supremum of compact elements is termed algebraic.If a pair of distinct poset elements x and y satisfy x y, and x z> y implies that z = x orz= y, we say that x covers y. A chain in a poset from x1 to x is a finite subset {x1,2..for which x covers xj1, for 2< i < n. The height of y over x, denoted by h(x,y), is the length ofthe shortest chain from x to y, or cc if there is no chain from x to y.In a lattice, an element x which covers 0 is called a minimal element, or atom. if every elementnot equal to 0 contains an atom, then the lattice is said to be atomic. Analogously, an elementcovered by 1 is called maximal, or a coatom. A lattice is coatomic if every element not equal to 1is contained in a coatom.A subset of a lattice which satisfies the lattice properties (1) through (4) itself is termed asublattice. One frequently-encountered instance of a sublattice of a lattice A is, for some elementsx,y e A, x <y, the interval[x,y} = {z E A: x <z < y}.The cartesian product of two lattices (A1, <1, A1,V1) and (A2, <2, A2,v2) is also a lattice, if wedefine(x1,2)<(y1,y2) x1 i hi and x2 2 Y2Another natural way to create a new lattice is to put the 0 element of one above the 1 elementof the other: assume that A1 and A2 are disjoint sets, and let (A1 . A2, <,A, v) be given byA1 . A2 = A1 U A2, and < = <1 U <2 U(A1 x A2). The lattice A1. A2 is called the ordinal sum ofA1 and A2.Chapter 1. Preliminaries 7We conclude our list of lattice-related definitions with another pair of important objects. Suppose B C A has the property that, for all x E B and y e A, y < x z y E B. Then B is termed anideal of A. Similarly, if for all x E Bandy A, x y = yE B, then B is afilterof A. Let usdenote the set of ideals and filters of A, respectively, by 1(A) and .F(A).We now introduce the notion of a universal algebra. Let A be a set, and F a subset of PA.That is, F is a set of functions for whichThen the pair (A; F) is called a (universal) algebra with universe or underlying set A and fundamental operations F. In particular, if F= {‘i . . , m}, for a finite collection of functions {j},then (A; F> is said to be of finite type, and is also written (A; ,q2,. .•, m).For example, any group G is a universal algebra (G; o, 1, 1), where o : G x G —f G is the binaryoperation in the group, G — G is the inverse operation, and 1: G —* G is a constant operationdistinguishing the identity element. Similarly, a lattice (A,,A, v) is an algebra (A; A, V), sincethe partial order < can be recovered from the operations A or V using the observation thatx<y xAy=x 4 xVy=y.It should be mentioned that it is sometimes convenient to use the word ‘algebra’ for the underlying set A of (A; F), when the set of operations F intended is understood from context.Let an algebra A = (A; F) be given. A congruence of A is art equivalence relation in theunderlying set A that each fundamental operation preserves, in the sense that for every f eif a, b, for 1 < i < n, then f(ai,. . .,a) f(b1,. . .,b,). An endomorphism of A is a functionA— A for which=f(jix,. .for all f E F(). An automorphism is an invertible endomorphism. We note that the endomorphismsof an algebra form a monoid under composition, as the automorphisms form a group. To continuethe first example above, a congruence of a group is the equivalence relation induced by the partitionof G into the cosets of a normal subgroup of G. An automorphism matches its conventionaldefinition for groups.Chapter 1. Preliminaries 8A set S C A is said to be (algebraically) closed if, for every e F, we have q(x) E A for allx S”, where n = o(b). Suppose that some collection of sets 5>, A for A E A are closed; thenone can see that the intersection flEA 5>, is also closed. It is a consequence that, for any S C A,the set [5] defined by[5]= fl {X C A : X D S and X is algebraically closed}is itself a closed set. [5] is called the algebraic closure of S, and we call the function [] : 2A ,the algebraic closure operator for the algebra A.The essential properties of the closure operator are worth stating explicitly. If X, Y C A, it iseasy to verify that1. X C [X] (extensive property)2. [X] = [[X]] (idempotent property)3. X C Y = [X] c [Y] (isotone property)(Interestingly enough, these properties are in fact equivalent to the single propertyxç[Y] [x]c[Y],for all X,Y C A — see De Witte [45].)If X c A and X is algebraically closed in A, then X is the underlying set of another algebra(X; Fig), where Fix is defined to equal : q F}, the restriction of the members of F to thedomain X. The restriction is usually implicit: one writes (X; F) in place of (X; Fig). Such analgebra is called a subalgebra of A. If, for some set Y, one has [Y] = X, the set Y is said togenerate X, and the elements of Y are called generators. If Y is also minimal in the sense that[Y\ {y}] C X for all y e Y, it is called an independent set, and a basis for X. X is said to be finitelygenerated if there exists a finite set Y which generates X. Let us also write Y I— y‘y E [Y], andx y {x} F- y and {y} F x. It is worth noting that is an equivalence relation on PA. Theexpression “Y F y” is easiest read as “y is derivable from Y.”[.1 imposes a lattice structure on the algebraically closed subsets of A:Chapter 1. Preliminaries 91.2.1 Proposition Let A = (A; X) be given. Then the algebraically closed subsets of A forman algebraic lattice £(A), ordered by inclusion, where A is set intersection, and V is defined byXvY=[XuY].1.2.1 The algebra of functionsThe next series of definitions is concerned with describing a universal algebra whose universe isthe set of functions PA. The operations are chosen to formalize the composition of functions andthe rearrangement of a function’s arguments. The subalgebras are thus closed under the intuitiverules for forming one function in PA out of others; that is, by composing functions and renamingvariables.1.2.2 Definition We define the operations (,r, z, V, and * on the set PA as follows. Let f eand g e where n, m e N. If n = 1, define (f rf = Lf = f. For n> 1, let((f)(xo, x1, . . . x_i) = f(xi, x2,. . ., x0),(Tf)(xo, x1,. . . , = f(xi, xo, x2,. . . ,(Af)(xo, xi,. . . , x) = f(xo, x0,x1,. . . ,Then both (f and rf are also functions of n variables, while Lf is a function of n — 1 variables.Let (Vf)(xo,xi,. . .,x,) = f(x1,x2.. .,x,). Let(*(f, g))(xo,. ., Xfl+m_2) = f(g(xo, X1,.. ., Xm_i), Xm, Xm+1,. . . Xm+n_2).We shall call (and T the permutation operations, and , V, and * the identification, cylindrification,and composition operations, respectively.We also define the projection functions e : A’ —* A by e(xo,xi,. . = zj1, andthen let e be a unary operation on PA defined by e : PA —* {ei}. Then the universal algebraPA = (PA;e,(,T,,V,*) obtained using these operations on PA is known variously as the fulliterative algebra over A, or the algebra of functions of A-valued logic.The algebraically closed sets of PA are known historically as iteratively closed classes of functions; here they shall be called clones, in accordance with modern terminology. Their importanceChapter 1. Preliminaries 10within universal algebra stems from the observation that, if F is a subset of PA, then A = (A; F>is an algebra, and [F] consists of exactly those functions on A which can be realized using only theoperations F. Here, the set [F] is called the term functions of A, or the set of polynomials of A.(The latter term generalizes the conventional definition of a polynomial over a ring (R; +, *, —, 0>.)If F, G c PA and [F] = [G], then the algebras AF = (A; F) and AG = (A; G) are equivalent,in the sense that all of the operations F can be expressed in terms of the operations G, and viceversa. In particular, S c A is a closed subset of AF if it is a closed subset of AG, which meansthat £(AF) = £(AG). Such algebras AF and AG are said to be polynornially equivalent. Thus wesee that there is a bijective correspondence between the clones of PA, and the equivalence classes,under polynomial equivalence, of algebras with universe A. Furthermore, finitely generated clonescorrespond to algebras of finite type.1.2.3 Proposition Let F ç PA be a clone. Then the following statements hold:(a) If f(xo, x1,. ..,x,) e F, and a is a permutation of[n]j, then f(xo, x,. . . ,x(1)) E Fas well.(b) eeFforall1<in.The proof of both parts is a matter of inspection.It is often of interest to consider the set of functions derivable from another set using only aparticular subset of the rules of formation listed above. For example, we may wish to consider a setof functions which we obtain only by reordering or identifying arguments. Formally, this amountsto considering the closed sets of algebras on PA whose fundamental operations are a subset of thoseof the algebra PA. The closure of a set X in the algebra (PA; , e, (, T> is just the set of functionsobtainable from X by any identification or permutation of variables. Let us write X — f if f isa member of [X] in this algebra. Similarly, we shall consider the set of operations V, e, , andT. The closure of X here is the set of functions obtained only by adding fictitious arguments andreordering. We shall write X-v f in this case. Note that the removal of some of an algebra’sfundamental operations decreases the size of its closed sets. In particular, then, if X H f orX 1—v f, it follows that X I— f.Chapter 1. Preliminaries 111.2.2 The algebra of relationsWe shall now give an analogous definition of the algebra flA, which will play an important role inthe upcoming discussion of PA. We begin with its underlying set.For any m E N, we call a set p ç A an m-ary relation on the set A. The elements of arelation p are called points. An m-tuple of points of p will frequently be written as an m x n matrix(a), the columns of which are (aid,a23,. . . , ai) E p: for short, we will write (a3) -•< p. Let= {p : p C Am}, and letRA= U R5), (1.2)meNthe set of all relations on A. As we did for sets of functions, if Q C RA, define Q(m) = Q n R.Once again, the equality (1.2) is a disjoint union, the arity function ö RA —÷ N given by- I’m ifpERandpø,o(p) =1. 0 otherwiseis well defined. In practice, we will use the symbol o for this arity function as well, where thereis no danger of ambiguity. The ith component of a relation p E is essential if there exista3 A, for 0 <j < n, and a A, for which (ai,a2,..., a) e p and (a1,a2,..., a,. . . ,a) p. Acomponent of p which is not essential is said to be fictitious. By identical components i j in p,we mean that a = a3 for all a p. A relation p will be called essential if all of its components areessential, and it will be called simple if, in addition, no two of them are identical.If Q C RA, the pair (A; Q) is called a relational algebra. A relation can be viewed as a predicateover the set A; thus, a relational algebra is a set of predicates, together with their domain. In thesame way PA formalizes the composition of functions, the algebra RA shall formalize the logicalconjunction of predicates.There are several equivalent ways to select a set of fundamental operations for RA. Let p Eand ci for m, m’ E N. The definitions of the operations (,r, , and V are analogous tothose for the function algebra. If m > 1, let(p={(x1,x2, . .., Xm_1, x0) : (x0,Xi,. .., Xm_1) E p},rp = {(x1,x0,x2,. ..,Xmi) : (xo, xl,. . .,sm_i) E p}Chapter 1. Preliminaries 12= {(x1,Xi, X2. , Xm_i) : (ro, Xi,. . ., Xm_i) E p} ,= {(x0,x1, . .., Xm_2) : (Xo, X1,. . . , Xm_i) E p}.For m < 1, define C = rp = = p, and irp = 0. LetVp = {(x0,x1.. .,Xm) :(xo,xi,. ..,Xm_i) E p}.Let c be the constant operation c : —* {A}. We also define the intersection of two relations:assume, without loss of generality, that m m’. Let & be the m-ary relation obtained by applyingV to a m — m’ times, let p fl a denote the set-theoretic intersection of p and &, and let afl p = p flu.Finally, let the cartesian product of relations p x a be given byp x a = {(x0,x1.. .,Xm+mi_i) : (xo,x1,.. .,m_i) e p and (Xm,Xm+i,. . .,Xm+m_i) E a}.Then the algebra RA = (RA; c, , T, , V, ir, n) is called the complete relational algebra on A. Inaccordance with the observations in the previous section, we may replace our choice of fundamentaloperations for RA with any other set of generators for the clone [{c, , T, , V, ir, n}] in RA andobtain a polynomially equivalent algebra. The following proposition thus gives two alternatives forthe set of fundamental operations.1.2.4 Lemma The following are true in the algebra PRA:(a) {, V, n} H x,(b) {(,r,x,ir,}Ffl,(c) {c, x} H V,(d) {(, i-, V, ir, n} I- z.1.2.5 Proposition RA = (RA;C,,T,A,7r,X), andflA = (RA;C,C,T,V,R,fl).Proof: The first equivalence is established using items (b) and (c) from the lemma. The secondis obtained from (d). IThe algebraically closed classes of the relational algebra are called coclones. They too forman algebraic lattice under inclusion: we shall denote the lattice operations and partial orderingChapter 1. Preliminaries 13by VR, AR, R, respectively. Similarly, let those operations in the lattice of function classes bewritten Vp, Ap, and <p, although the subscripts will be freely dropped when the lattice to whichwe refer is indicated clearly by context. The greatest element in the lattice of clones and coclonesis, respectively, PA and RA. Let us denote their least element by JA and DA, respectively. Thelatter shall be called the coclone of diagonal relatiolls.Although a significant portion of the theory discussed here generalizes to infinite underlying sets,the results of this investigation depend essentially on finiteness; we shall be hereafter restricting ourattention, then, to the case where IAI < cc. Since no properties are assumed of the actual elementsof the underlying set, we shall usually set A {O, 1,. . ., k — 1} for some k E N, in the interests ofuniformity. We shall adopt the notation {k]j = {O, 1,. . ., k — 1}, for k e N. It is conventional toabbreviate Pk,Pkl,Rjk, and Rk by Pk,Pk,l?k, and Rk, respectively.Let us now consider some additional operations that may be derived from the fundamentaloperations, in the interests of convenience. First, if p E R5 and g is a permutation of L[nj, onecan see that the relation p’ obtained from p by permuting its components with g is equivalent top, since the operations C and 7 generate all permutations of the components of p. More generally,if g : F[nj —* {lj is an injection, it is also true that if we letEg(p) {b e A1 :b = ag(j), 1< i < n, aEthen p g(p), since one can derive 9(p) from p by some sequence of (, r, and V, and one canalso obtain p from E9(p) using C T, and ir.If € is an equivalence relation on the set [nil, for some n e N, define the n-ary relation= {(xo,x1,...,xn_)E A : = xj if (i,j)E €},and define for p ELp = pfl.The latter is the relation obtained by identifying those components of p which are equivalent in E.We shall abbreviate L\{(,)} by A,.By analogy with our definition for functions, we shall define Q F- p to mean that p is containedChapter 1. Preliminaries 14in the closure of the set of relations Q under the operations , , r, and c. For example, if € is anequivalence relation on {n]j, then p H Lp.Let us define K = {k]jTh, called the full relation. It is easy to see that K e Dj for all n E N.More generally, define the relation l, = zXI(,, for an equivalence relation e on {n]j. Then we havethe following:1.2.6 Proposition(a) Jk isthe set {e:nENand1<i<n}.(b) Dk consists of the empty relation 0 and all relations 6, where c is an equivalence relationon the set {1, 2,. . ., m}, for some m E N.Proof: For both, one verifies that the set given is indeed closed, and then observes that it iscontained in every closed subset of Pk or Rk, respectively. See Proposition 1.2.3. ISeveral more special clones and coclones will now be named. Let CoflR(k) denote the coclonegenerated by the constant relations {{O},. . ., {k — 1}}. Analogously, let Conp(k) be the clonegenerated by all the constant-valued functions in Pk. Define Sk = [{f E : mg (f) = k}j , theclone generated by the set of permutations on {kj. Let k = [P’\Sk], the clone of noninvertible,essentially unary functions. Since a clone F of essentially unary functions consists just of unaryfunctions and those nonunary functions obtained from them by adding fictitious variables, we shallidentify such a clone with its unary subset. F is most natllrally viewed as a monoid whose operationis composition, (F; *, ei). If the members of F all happen to be invertible, (F; *,‘ , e’) is a group;for example, we shall regard Sk as the symmetric group on {k]1. Finally, let U = [Pl)], the cloneof all essentially unary functionsWe conclude this section with a pair of schemes for obtaining relations from functions. First,for a function f : D — {k}1 with D c {kr, define f E byf is called the graph of f. One defines the graph of a set X ç P, to be X = [{f’ f E X}j. Forexample, Conp(k) = ConR(k).Chapter 1. Preliminaries 151.2.7 Proposition Let X c Pk. If X I- f, then f E X.Proof: Omitted. IThe second construction adds new points to a given relation. For p e Rim) and A an n x mmatrix over k]j, we write A -< p if every column of A is an element of p. Put P0 = p, and for i> 0letPi+i = pj U {f(A) : A pJ. (1.3)Then we define F(p)= UEN p. The definition can be extended a set of functions F as well, byreplacing (1.3) withPi+1 = pj U {f(A) : A-p and f E F}.The two definitions relate conveniently:1.2.8 Proposition Let F < Pk be a clone, f E Pk, and p e Rk. Then(a) Ff(p)={g(A):fF-g andA-< p}, and(b) T’F(P) = {g(A) : F F g and A -< p}.Our use of this construction will be restricted to a specific relation, Xn. Let A be the k’ x kmatrix whose rows are the elements of {kr, in ascending lexicographic order. Then we define Xnto be the relation whose points are the columns of A. We call Xn the n-ary ordinate relation on{kj, and Ff(x) the n-ary orbit of f.1.3 Functions with relationsSince clones are infinite sets, it is desirable to be able to specify them more succinctly than bysimply enumerating their elements. We have already seen that one can designate a clone by listingits generators, which is a particularly satisfying representation if the clone is finitely generated.Following a quite different approach, one can also specify a clone by stating a condition which itsmembers must satisfy.For example, let F C P2 be the set of monotone functions, defined to be those functions f Ep), for some n, for which f(xo,x1,...,x_) f(yo,yi,...,y_i) if x < y for each 0< i < n.Chapter 1. Preliminaries 16We can restate this definition in the language of the last section by letting a denote the relation(0 o0 1then observing that F = {f P2 : A -< a = f(A) E a}. F is also a clone, since the property ofmonotomicity is preserved under composition and the other clone operations. Properties of functionsor sets of functions that are preserved under the clone operations are of particular interest, and weshall distinguish them with the adjective relational. While it is not hard to show that F is generatedby {et, vel, 0, 1}, our characterization of F by a relational property is, from some perspective, themore natural one.In order to elucidate the notion of a relational description of a clone, we require some definitions.Let f E P and Rim). Then f is said to preserve p if, for all A-p, f(A) E p. We define themapsmv :2Pk _*2Rk : InvX={pe Rk :VfeX, fpreservesp},Pol : ÷ 2’ : Po1Y = {f e Pk :Vp e Y, f preserves p}.mv and Pol are called the invariant operator and polyrnorph operator, respectively. mv gives theset of relations which are preserved by (that is, invariant under) a set of functions, while Pol is theset of all functions preserving each member of a set of relations. Iii the example above, a E mv F,and F C Pol {a}.The next proposition shows a connection between functions and coclones, and between relationsand clones. We saw that the functions F preserving a were closed under the clone operations. Moregenerally, it is the case that the property of “preserving” is hereditary under both the operationsof Pk, and the operations of Rk:1.3.1 Proposition If X ç Pk andY C Rk, InvX is closed in R.k, and Po1Y is closed in Pk.Proof: First, we would like to show that mv X is closed under the fundamental operations of Rq,;let us make use of the second characterization of R-k given in Proposition 1.2.5. Suppose p E InvX:then every f E X preserves p. That f also preserves Cp, rp, irp, and Vp is immediate. If fpreserves P1 and P2, where h = o(pj) for i = 1,2 and h1 > h2, then for any A -< p P2, X- P1,Chapter 1. Preliminaries 17so f(X) E p, and X -< VhI_h2p2,so f(X) e Vh1_h2p2,whence f(X) E Pi fl p2. Finally, everyfunction preserves the relation c = {L[kjJ}.The argument that Pol Y is closed in Pk is similar. The projection function e preserves allrelations. If a function f preserves a relation p E Po1Y, then clearly (f, rf, and 6f do as well.Similarly, (Vf)(A) E p if and oniy if the first o(f) columns of A are in p, which is certainlytrue when A -.< p, so Vf preserves p. If f and g preserve p, then so does f * g: Let n = o(f) and1 = o(g). Then if (AlA’)-p for submatrices A and A’ with n and 1 columns, respectively, g(A) e p,so (g(A)IA’)-< p, which implies in turn that (f * g)(AIA’) = f(g(A)IA’) E p. INote that the functions Inv and Pol both reverse the direction of the inclusion of sets: that is,if X1 C X2 C Pk, then Inv X1 D mv X2, and the analogous statement is true for Pol. Functionswith this property are said to be antiisotone.The proposition shows that the range of Pol is contained in the set of clones, and the range ofmv is contained in the set of coclones. In fact, a much stronger result holds: Pol and mv realizea bijection between the clones of Pk and the coclones of R,k. This fundamental observation is dueto Geiger [151 and Bodnarëuk, Kalunin, Kotov, and Romov [4]. Formally, we have1.3.2 Theorem If X Pk, PolInvX = [X]. If Y Rk, InvPolY = [Y].A lemma is required before proving the theorem. If for some D c [k]j, g is a function gD —* [k]], g is said to be a partial function on [k]j. Let domg C [k]jtm denote the domain of g. Thedefinition of functions preserving relations is extended to partial functions as follows: g preservesa relation p if, for every m x n matrix A -< p for which each row of A is a member of dom g, wehave g(A) e p.1.3.3 Lemma If a partial function g preserves a coclone Y in R, then there exists a functionf E Pk with f D g that also preserves Y.Proof: Since the domain of a given function is finite, it is sufficient to prove that if g is a partialfunction preserving Y, then there exists a function f with f g with dom fI = Idomgl + 1 whichalso preserves Y. For some x domg, then, let us define gj(x) = i for i E [k]J, and agreeing with gelsewhere. To show that at least one of the functions gj preserves Y, suppose the contrary. ThenChapter 1. Preliminaries 18there is a relation a, E Y for which g(A) a, for some A -< a, for each i. Since g preserves Y, itmust be the case that x is a row of each matrix A. Since a coclone is closed under the operationsof row permutations, we may assume that x is the first row of each. Form the relation a E Y, then,by(a) taking the product of the relations a,(b) identifying the first component of each factor a,(c) projecting out the first component of the factors a, a2,.. . ,a4.Let a’ e Y denote the relation obtained by projecting out the first component of a0 as well.For a m x n matrix A, let A denote the in — 1 x n matrix obtained from A by deleting the firstrow. LetxA0A=Ak_1By construction, A - a and A -< a’. We have assumed that g(A) ‘ a for any i E k]j. It follows bythe definition of projection that g() a’. Since a e Y for each i, though, we have 7r0a e Y andthus a’ Y, by the closure properties of coclones. However, g does not preserve a’, a contradiction.IWe may now prove the theorem.Proof: One shows first that for clones X1 and X2, mv X1 = mv X2 = X1 = X2: Suppose thatX1 X2 and assume, without loss of generality, that X1 X2. Choose a function f E X1\X2,andlet n = o(f). Then we claim that the relation FX2(Xn) is in mvX2\Inv X1: first, that every functionin X2 preserves FX2(Xn) follows directly from the construction of Fx2(). If it were true that fpreserved fx2(x), we would have, in particular, f(x) E x2(xn); however, Proposition 1.2.8indicates that there would exist an n-ary function g E X2 for which f(x) = g(xn). By thedefinition of,though, this would imply that f = g, contradicting f X2. We conclude thatPX2(Xn) ‘InvX1.Chapter 1. Preliminaries 19Similarly, if Y1 and Y2 are coclones, then Pol Y1 = Pol Y2 = Y1 = Y2. The argument is analogous:suppose that there is a relation p e Y1\Y2. Then we construct a function f E Po1Y2\Po1:that is,a function f which does not preserve p. To do so, we first produce a partial function g preservingY2 and not p, and then appeal to Lemma 1.3.3. Note that we may assume that p is simple. NowletJ= n .Since Y2 is closed under intersection, o E Y2. By assumption, then, p C u. For an arbitrary pointc E u\p and matrix A = p, let f(A) = c. Our assumption that p is simple implies that f iswell-defined, since A then contains no repeated rows. By construction, f does not preserve p. Tosee that f preserves Y2, however, suppose the contrary instead. Then E Y2 and S -.< for whichf(S) . Assume again, without loss of generality, that the rows of S are distinct. Then the rowsof S are also rows of A, so there is an injection g : —p f{o(o)jJ mapping rows of S to matchingrows of A. From the discussion on page 13, g() where g() p and f(A) = c g(). Bute Y2 = o C so c u, yielding a contradiction. ILemma 1.3.3 can be viewed as an analogue of Lagrange’s Theorem for clones. We may rephraseit to state that if a given set of values of a function on a subset of its domain preserve mv K forclone K, then there exists an interpolating polynomial in K for those values; the classical theoremof Lagrange states that, given n + 1 values of a function from a field into itself, there exists apolynomial of degree no more than n interpolating those values. For insight of this nature, see the1975 paper by Baker and Pixley [2].Chapter 2Properties of the Lattice of Clones2.1 The Structure of £(P2)The only clone of the algebra P1 is P1, the set of all functions.The structure of the lattice of clones of the algebra P2 was completely determined by 1941by Post [34]. The proof he gave is lengthy, and uses an independent argument to establish eachcovering relation in the lattice. In [20], Jablonskii’, Gavrilov, and Kudrjavcev give a somewhat moremodern presentation of Post’s result. A substantially refined argument can be found in a recentpaper by Ugol’nikov [43].The lattice £(P2) is as shown in Figure 2.2. Before describing what functions make up the elements of the lattice, the reader should be warned that our definition of a clone is somewhat differentfrom that used by Post, since he did not require the presence of the projection functions in eachclone, and he did not assume closure under the addition of fictitious variables. His classification,then, is of the subalgebras of (P2;,T, z, *), rather than P2. A consequence is that the names hegives to the clones are somewhat unnatural in our context. Since the clones that have analogues inPk for k > 2 do not have names which are easily extended, we shall employ Post’s nomenclatureonly for clones peculiar to P2, and within the description below of £(P2).The bilateral symmetry evident in Figure 2.2 has an immediate explanation. Every Booleanfunction has a dual obtained by completely exchanging the roles of 0 and 1 in its definition. Dualityis a relational property of pairs of functions, in the sense of Section 1.3; thus each Boolean clonehas a dual clone consisting of the duals of its elements. The clones on the axis of symmetry ofare their own duals.At the top, we have C1 = P2. C3 = Pol {0}= {f : f(0,0,...,0)= 0}. By duality, C2 =Pol {1}, and C4 = C2 fl C3. C2 and C3 are the classes of functions preserving 1 and 0, respectively.20Chapter 2. Properties of the Lattice of Clones 21(0 0 1Next, M1 = Pol , equal to the set of monotone functions introduced in Section 1.3.\0 11)(oOnce again, M2 = M1 flC2,M3 = M1 flC3, and M4 = M1 flC4. Then D3 = Pol L which“\1 0)is also equal toThe functions of D3 are called self-dual. D1 = D3 fl C4, and D2 = D3 fl M1.Figure 2.2: The lattice of clones of P2The classes L, consist of the linear functions:= f : f(zo,xi,...,x1)= c + for some c E 2r+lI iEI[n]j{f:f(xo,xi,...,x_i)=f(,...,)}.01Chapter 2. Properties of the Lattice of Clones 22Equivalently,000111011001L1=Pol101010110100L2,L3 and L4 are L1 intersected with C2,C3 and C4, respectively: they are the linear functionspreserving 1, preserving 0, and both, respectively. In addition, L5 = L1 fl D3.P1 = [{et(x, y)}], the functions which are a conjunction of a subset of their variables. P3 =[{et(x, y), O}], P5 = [{et(x, y), 1}], and P6 = P3 V P5. The clones 51, 53, 55, and 56 are their duals,obtainable by replacing et by vel, the disjunction operation.The sets 0, contain the essentially unary functions. 01 = J2: the clone of projections. 0 and06 are [{1}] and [{O}], respectively, while 08 = 0 V 06. 04 = [{}j, and 09 consists of all theunary functions.Finally, the lattice contains eight infinite chains of clones F > F > ... for 1 j 8, andtheir infima F3°= A1 F. We defineF= {f : if Vj, 1 j i, y3 : f(y1) = 1, then 1 : = 1, for all 1 <1 <In the interests of easier visualization, one may associate a function f E with a family of n-sets{S c L{n1 : f(xo,xi,. . .,xfl_l) = 1, where x = 1 i e S};in this framework, f e F if and only if Sj is a family of sets in which any i members havenon-empty intersection.It is also the case that F = Pol(K1\(1, 1,..., 1)). F80° consists of those functions which assumethe value 1 only if a given variable is 1. Equivalently, fl S 0.The other chains are similar, with F = F fl C4, F = F fl M4, and F. = F fl M1. The clonesfor j = 1, 2,3,4 are obtained by the duality principle.Post’s description of the lattice £(P2) afforded a complete answer to most questions about twovalued clones. As interest grew both in propositional logic of more than two values, and in cloneswith more general underlying sets, comparable results were sought for the clones of Pk, for k > 2.Here we outline some of the work in that direction.Chapter 2. Properties of the Lattice of Clones 232.2 Coatoms and completeness criteriaOne of the first questions that arises in clone theory is known as the completeness problem, andasks sets of functions in Pk are complete (that is, generate the clone Pk.) Its solution is closelyrelated to knowledge about the coatoms (maximal, proper subclones) of Pk: one may check to seeif a given collection of functions S= {f, f2,. . . , f,} is complete by testing the membership of eachf, in each of the coatoms of Pk. S is complete exactly when no coatom contains all of S’s members,in view of the isotone property of the closure operator (page 8.) Conversely, a clone K is a coatomif the set K U {f} is complete for any f ‘ K.In P2, the determination of £(P2) provides a solution to the completeness problem: P2 has fivecoatoms, each with an easily verified defining property. A set S is complete if not all of its membersare monotone, not all are linear, et cetera.Long before much progress was made towards a solution of the completeness problem in Pkfor k > 2, a solution to an important special case appeared. The result is known as the SlupeckiCriterion, and was presented by Slupecki [44] in 1939, then later rediscovered by Butler [7]. It givesnecessary and sufficient conditions for the completeness of a set of functions that includes all unaryfunctions:2.2.1 Theorem (Slupecki Criterion) Suppose k 3. Then for f E P, one has [{f} u p)j =Pk if and only if mg (f)I = k and oe(f)> 1.(An equivalent statement is that, if a set of functions contains the set of unary functions, thenit is complete if and only if it also contains some surjective function that depends on more thanone variable.)A natural weakening of the theorem’s conditions is to consider the clone [{f} u whenmg (f)I < k. Such clones have been studied by A. I. Mal’cev [26], Burle [5], and I. A. Mal’cev [25].It happens that all clones containing ‘) arise in this way, and that they are finite in number.Let us digress briefly in order to give them names. First let V= {f e Pj : mg (f)) < i} U Jk, for1 < i < k. It is not hard to see that each set T/ is, in fact, a clone; they are referred to as basic cells.For each 1 < i < k, let U = V U U. Recall that U is the clone of essentially unary functions. WeChapter 2. Properties of the Lattice of Clones 24define the quasilinear clone, L2, to be those functions that add their arguments modulo 2, subjectto an independent interpretation of each argument as a value mod 2. Specifically, L2 consists of allf p5, for some n e N, for which there exist functions qj : [k —* Z2, for 1 < i < n, and some‘/‘: Z2 —* [k]j, such thatf(x1,x2,. ..,x) = ((x)). (2.4)The addition takes place in Z2, the ring of integers modulo 2. Let us also take this opportunityto define L as the largest clone contained in L2 for which all of the maps çj have the additionalproperty thatis even, for a = 0 and 1. When k is odd, of course, we have L = Jk: just the projections.2.2.2 Theorem (Burle) Suppose k 3. Then the interval [U, Pk] consists of only the chainU= U1< L2 V U1< U2 ...< Uk_1< Uk = Pk.While it was known quite early that the number of coatoms of Pk is finite for each k, it wasalso observed that their number grew very rapidly with k, and several years passed before theircomplete classification (and its attendant solution to the completeness problem) appeared in print.Before discussing this classification, though, let us refer to Kuznecov [23] and Butler [7] for thefollowing:2.2.3 Proposition (Kuznecov) For k > 2, Pk has at most one coatom for each submonoid ofU.Proof: For any clone K < Pk, we define Tr K = K A U, called the trace of K. It is routine toverify that if TrK = TrK’ = M for some M < U, then Tr(K V K’) = M as well. Denote thecoatoms of Pk by {Kj for i E I, and suppose that TrK, = TrK3 = M for some M and K K.Then we have M = Tr(K, V K) = TrPk = U. Burle’s Theorem (2.2.2) shows, however, that Uis contained in at most one coatom. By contradiction, we conclude that no two coatoms have thesame trace. IChapter 2. Properties of the Lattice of Clones 25Since U contains no more submonoids than subsets, Pk can have no more than 2k’ coatoms.In fact, their classification proceeded by characterizing those submonoids which correspondedwith coatoms. This was completed by Rosenberg around 1970 [37], using partial results due toKuznecov [23], [24], Schofield [42], Jablonskii [21], and others. If K is a coatom of Pk, then theGalois Correspondence (Theorem 1.3.2) implies that mv K is an atom of Dk: that is, a minimal,nontrivial coclone in R-k. A minimal coclone is generated by any of its nondiagonal elements:mv K= [p] for any p e mv K\Dk. Therefore, the coatoms of Pk can all be expressed in the formK = Polp, for some relations p.Preparatory to stating Rosenberg’s Theorem, we need to introduce the defining properties forsome classes of such relations. First, an abelian group G is said to be p-elementary if it has exponentp. If G is finite and p-elementary, clearly IGI is a power of p.(h).Next, a relation p E Rk is called central if(a) there is some nonempty set C C f[k]j such thatforeveryo<j<h—1,(b) (x0,.. .,xh) e p = . .,Xg(h_1)) e p, for all permutations u E Sh, and(c) x = (xo,. ..,xh_i) E p, for every 0 i < h—i.By definition, then, all unary relations are central. The last two conditions can be regarded asgeneralizations of the symmetric and reflexive properties, respectively, of a binary relation.Last, for a fixed value of k> 2 and 2 < h < k, we define the relation= {(x0,. . . , Xhl) e : {x0, . . .,Xh_i} I < h}.A relation p e is said to be h-universal if there is a value m > 1 and a surjective mapA: [k]j — [h]jm such that for all x = (x0,. . . , xh_1) E k]j’, x E p if and only if(A(xo)i,. .., A(xh_i)) E th (Vi : 0 i < m).Chapter 2. Properties of the Lattice of Clones 26A trivial example of an h-universal relation is th itself. Alternatively, let A map L[4]J onto [[2] x [2jjviax A(x)0 (0,0)1 (0,1)2 (1,0)3 (1,1)from which we get the 2-universal relation(o 0 0 1 1 1 2 2 2 3 3 3i\ 0130121232302.2.4 Theorem (Rosenberg [37], [39]) The coatoms of Pk are exactly those clones of the formPolp, where p is a member of one of R1, . . ., R6:R1: Partial orders on fk]J with a least and greatest element.R2: Relations {(x, ax) : x E [k]J} where a e Sk is a product of cycles of equal, prime length.R3: Relations {(x0,.. . , x) L[k]4 : a0 + a1 = a2 + a3}, where ([k]]; +) is a p-elementary abeliangroup.R4: Non-trivial equivalence relations on Jk]j.R5: Non-diagonal central relations on [k]j.R6: Non-diagonal h-universal relations on [[k]].Consequently, a set of functions S is complete in Pk if, for every p E R1,. . . , R6 there exists anf E S not preserving p. While there exist some relations p and p’ in the list above for which p p’,one can account for all such duplications to obtain a list of relations in one-to-one correspondencewith the coatoms of Pk. [36]2.3 Counting clonesIn the previous chapter, we saw that £(P2) is countable, and that its elements can be describedexplicitly. However, Janov and Munik [22] laid to rest any hopes that a similar analysis could beChapter 2. Properties of the Lattice of Clones 27carried out for £(Pk) for k > 2 by showing that IL(Pk)I = 2°. That is, Pk contains as many clonesas it does subsets. It thus became apparent that qualitative differences distinguished £(P2) fromthe lattices £(Pk) for k > 2. Subsequent work has looked for properties shared by the lattices fork> 2, and has more fully shown the extent to which those lattices differ from L(P2).Let us begin with an example of an uncountable family of clones. Let Ic 4, and for n 1,define the function f E p) by(1 if (x0,x1,. . . , x?_) contains n — 1 2’s and one 3,f(x)=0 otherwise.These functions have the property that the composition of any two of them is the constant 0, whichmakes it easy to establish that:2.3.1 Proposition For a set SC {fl,f2,. . .}, we have[SJn{f1,f...}=S.Consequently, each subset of {fi, f2,.. .} generates a distinct clone. Therefore there are 2°clones contained in [{f, f2,. . .}j. We note in passing that this also shows that the Booleaii latticev, A), the lattice of subsets of a countable set, can be (order) embedded in the lattice £(Pk)when Ic > 4: another tribute to its structural complexity.We have seen that some regions of the lattice remain similar in character for Ic = 2 and k > 2.Recall from Section 2.1 that the interval [U, P2] is the three-element chain U < L1 < P2, andthat Burle’s Theorem (2.2.2) shows that the interval [U, Pk] is a finite chain as well for Ic 3.It is natural to wonder if this analogy extends any further. For example, note that the interval[Os, P2] has seven elements. Since 08 = Coiip(2), one might ask whether or not [Conp(k), PkJ isfinite in general: one asks, that is, how many clones contain all constant functions. The answer isnegative, though; an argument of Agoston, Demetrovics, and Hannák [1] shows that [Conp(k), Pk]is uncountable for values Ic > 2. In fact, one may readily construct a (countably) infinite family ofclones containing as follows. (I. A. Mal’cev, [27])We define the function q: k]j —* Z2 by10 ifxE{O,1};1 1 otherwise,Chapter 2. Properties of the Lattice of Clones 28and define : —* [k]j by (O) = 0, i/’(l) = 1. Then for each n E N, letf(xo,x1,...,x_)=($(x)).iE IllLet F= [{f,} U [k]j]. It is not hard to see that oe(f) < ii for all f e F; consequently, thecontainment F C F+1 is proper for each i E N. I. A. Mal’cev [27] established that [Jk, L2]I =(k 3), where L2 is the quasilinear clone. He also showed that one encounters an uncountableinterval by increasing L2 to U2: I[Jk, U2] = 2°. (See Proposition 2.3.1)If {fi, f2,.. .} is an independent subset of Pk, then the 2° clones generated by each of its subsetsare distinct, as in the example at the beginning of this section. Furthermore, a set of functionsis independent iff there exist relations 6, 62,... for which f, Po163 . i j. Demetrovics andHannk [12] used this observation in the construction of several independent sets in order to prove2.3.2 Theorem Let K be a coatom of Pk for some k 3. Thenfinite if mv K is of type R3 in Th. 2.2. and k is prime,I[Jk, A]I = o if mv K is of type R3 and k is not prime,2° otherwise.Finally, we say that F Pk is complete with constants if [F U Conp(k)] = Pk.1 Demetrovicsand Hannák [12] have also shown that when k > 2, there are uncountably many clones K Pk thatare complete with constants. These and other results seem to indicate that uncountable structuresare ubiquitous when k > 2, rather than confined to some easily delimited region of the lattice.2.4 Finitely generated clones and coclonesA noteworthy consequence of Post’s analysis [34] is that one can give an explicit, finite set ofgenerators for each two-valued clone; we saw using Proposition 2.3.1 that not all clones are finitelygenerated when k 3. [14], [29]. While the finite generation property is certainly valuable instudying any clone that possesses it, it is also closely related to the question of lattice cardinality.From the knowledge that all clones of P2 are finitely generated, we note that the countable set P2‘This is sometimes a more natural notion of completeness, within a purely algebraic context. For such a set F,the algebra (I{k]; F) is also called functionally complete; however, we shall avoid the use of this term.Chapter 2. Properties of the Lattice of Clones 29has only countably many finite subsets, and it follows directly that C(P2)I o. On the otherhand, a clone with an infinite basis has uncountably many subclones. In general, we have:2.4.1 Proposition Let A be an algebra, IAI o• Then(a) If S is a sublattice of £(A) for which all subalgebras X e S are finitely generated, thenISI o.(b) If [X, Y] is an interval, X is finitely generated, and there exists a Z E [X, Y] with aninfinite basis, then I [X, Y] = 2°.(c) If [X, Y] is an interval for which X is finitely generated and all Z E [X, Yj have finiteheight over X (see page 6), then all Z e [X, Y] are finitely generated.Proof: We have already given some justification for the first claim. In order to prove (b),suppose that S = {x1,x2,.. .} is an infinite basis. By hypothesis, there is a finite subset T of S forwhich X < [TI. Then for any sets U and V contained in 5, if [UI = [Vi then U = V; otherwise,[S\(U\V)I = [S\(U\V)I = [SI would contradict the basis property. Since there are uncountablymany subsets of S containing T, l[X, Yll l[X, [Sill = 2°.To establish the last claim, we observe that if Z e [X, Y] has generators {x1,. . ., x,} and andcovers Z, then Z’ is generated by {x1,. . . for any element E Z’\Z. Thus Z’too is finitely generated. When the height of any Z e [X, Y] is finite, one can proceed upwardsinductively from X to show that Z is finitely generated.In particular, the conditions of (c) are met if X is finitely generated, and l[X, Yll < c’o. IThe algebras A of interest here are, of course, Pk and 7?k. For economy of expression, a clonewhose image under mv is finitely generated in Rk will be called relationally finitely generated (rfg),in contrast to a functionally finitely generated (ffg) clone. Applied to 7k, the third claim abovestates that all members of a finite interval are ffg (rfg) if the bottom (top) of the interval is also ffg(or rfg, respectively). By taking the unions of the appropriate bases, one may also observe that ifK, K’ < Pk are ffg, so is K V K’. If K, K’ are rfg, then so is K A K’. Unfortunately, though, thefinitely generated subalgebras do not, in general, form a sublattice: for example, Haddad [171 hasshown there exist ffg clones K, K’ < P3 for which K A K’ is not ffg.Chapter 2. Properties of the Lattice of Clones 30The finite generation property is equivalent to a lattice condition. It is well known that2.4.2 Proposition A subalgebra X of A is finitely generated if and only if it is coatornic in £(A).That is, Xis finitely generated if and only if, for every Z <X, there exists a coatom Y of X suchthat Z < Y <X. Another equivalent condition is given by noting that X is coatomic if the unionof any ascending chain in X is properly contained in X. For example, the structure of the lattice£(1?2) (Figure 2.2) reveals that the coclones InvF°°, 1 < i < 8, are not finitely generated, sincethey are each the limit of an infinite, ascending chain, and hence are not contained in any coatom.P2, then, provides clones which are simultaneously ffg and rfg, or ffg and not rfg. One can alsoaccount for the remaining two combinations: Demetrovics and A. I. Mal’cev [13] have exhibited aclone which is rfg but not ffg for k 3, and the cardinality properties of Proposition 2.4.1 guaranteethe existence of uncountably many clones of the fourth type; Pöschel and Kaluiiin [33] constructan example.2.4.3 Definition For any F < Pk, let the order of F beo(F) = mm max{o(f)},[S1=F fESsetting o(F) = oo if none of the maxima exist. Define o(Q) for any Q < Rk analogously. ForF Pk, also letd(F) o(InvF),called the degree of F. We note that o(F) < oo if F is ffg, and d(F) < co if F is rfg.An elegant use of the Galois Correspondence furnishes a refinement of Proposition 2.4.2 for thealgebras Pk and Rk.2.4.4 Lemma Let f e Pk and p E Rk be given with f Polp.(a) There exists a relation o for which f Polu, p I- o, and o(u) < k°0.(b) There exists a function g for which g Polp, f [- g, and o(g) < k0() — 1.Chapter 2. Properties of the Lattice of Clones 31Proof: We prove (b). Set h = o(p); if o(f) < kh — 1, we are done. Otherwise, observe that pis not trivial, since f Polp; therefore, Il < k’ — 1. Let A-p be such that f(A) ‘ p. ClearlyA contains at most II distinct columns: let A’ consist of those columns in order of appearance.Let€ be the equivalence relation on [o(f)]J induced by equality amongst the columns of A, and letg=zf. Since€ has at most Il equivalence classes,o(g) II<and g(A’) = f(A) 0 p. Therefore g Polp. IThe following consequence refines the generic observation made in Proposition 2.4.2: we referto Jablonskii [21] or Pöschel and Kalunin [33].2.4.5 Proposition K Pk is ffg if and only if K is coatomic and has finitely many coatoms. Kis rfg if and only if K is atomic and has finitely many atoms.Proof: Omitted. IAnother interesting consequence is noted by Salomaa [40] and others. A basis S C Pk for aclone K is said to be simple if, for every f e S and 0 i <j < o(f),[S u {f} \ {f}] C K.That is, a simple basis is one which is minimal with respect to diagonalization. It is clear that onecan obtain a simple basis from any basis for K by diagonalizing its elements appropriately.2.4.6 Proposition If K Pk is ffg, there exist only finitely many simple bases for K.Proof: Let K be finitely generated; then K has coatoms K1,. . . K, for some finite n, by Proposition 2.4.5. For each 1 j < n, choose a relation p, E mv K\Inv K. Now let S be a simple basis forK. By virtue of generating K, it contains a function f E S\K, for each I n; that is, f Polp.Since S is a basis, S = {f}1,although the functions f need not all be distinct.By Lemma 2.4.4(b), there exist functions gj 0 Polp for which f [- gj and o(gj) < k°() — 1.Since gj E K\Kj, the set {gj}1 also generates K. Because S is simple, we must have gj = f foreach i.Chapter 2. Properties of the Lattice of Clones 32Now let h = max{o(pj) : 1 < i < n}. We have o(f) = o(gj) kh— 1 for each i. Since hdepends only on K, we have shown that the arities of functions comprising a simple basis arebounded; therefore, there are finitely many simple bases. IThe complementary theorem for Rk is also true. As a final application of Lemma 2.4.4, weinclude a result from Pöschel and Kalunin [33]. A clone K < Pk is said to have the expansionproperty /.h iffeK Vg: fFg, and o(g)<h=geK. (2.5)2.4.7 Proposition Let K Pk. Then for h e N,(a) If K has the expansion property h, then d(K) kh.(b) If d(K) < h, K has the expansion property (k’ — 1).By way of illustration, consider the clone F= U1 F, when k = 3, from the example on page 28.(n)..If a function f P3 is not a member of F, then it is not difficult to see that there must be threevectors x, y, z e L[3j for which f(x), f(y), and f(z) bear witness to this fact. Since there are atmost 33 distinct triples (xi, y, z), there must be some function g also for which g F, and f F- g,and o(g) 33, by identifying any components with repeated triples. This means that F has theexpansion property 27, so d(F) < We saw, though, that o(F) = 00; therefore, F is rfg, butnot ffg.To provide another example, we recall the comment on page 22 that a function was in the cloneF80° if and only if the family of sets Sf had fl S 0. For any h-ary function f E F’°, if A E Sj,we have A C hjj. Let T = Sf U {{h}}, adding on a singleton subset of [h + 1 so that flT = 0.Let fh be the h + 1-ary function associated with T. Now fh F°, but for any g fh for whichfh [- g, we have S, C S, whence fl Sg 0, and so g e F800. Therefore F80° does not have theproperty h, for any h. By the proposition above, F80° is not rfg.The corresponding proposition for R,k also holds if we define the expansion property for coclonesin the same way, replacing functions and clones with relations and coclones in expression (2.5).Chapter 2. Properties of the Lattice of Clones 332.4.8 Proposition Let Q <Rk. Then for h E N,(a) If Q is h, then o(Po1Q) < (k’ — 1).(b) If o(Po1Q) < h, then Q is Lkh.Proof: We prove oniy (a). Let Q R, be given with the property LSh. In order to show thato(Po1Q) < k’ — 1, we show Q = mv(p0lQ)(k’_1). The containment “C” is clear by the antiisotoneproperty of mv. To establish the other inclusion, pick p Q. We assume that o(p) h. By thecontrapositive of the expansion property, there exists a relation a Q for which o(u) = h andp F- a. Let f E Po1Q be a function not preserving a. By Lemma 2.4.4, there also exists a g forwhich f [—s g and g Pola with g e (Po1Q)(’). Since g Pola, it does not preserve p either,from which it follows that p Inv(Po1Q)(’). •Chapter 33.1 Clones overTwo Intervals in £(Pk)P2P6Figure 3.3: [Q2,P]From Post’s catalog [34], we see that the interval [Z2,P2] consists of seven classes, arranged asshown in Figure 3.3. (Recall that S6 is the clone generated by vel and the constants, and P6 is itsdual. M1 is the class of all monotone functions.)This section gives a description of the interval [Qk, Pk] for k > 3, which is equivalent to thetask of determining all clones containing k. The description reveals that the interval shares thefiniteness of [f22,P2] for all (finite) values of k.A result due to Jablonskll [21] gives from the outset some evidence of similarity between [U, Pk]and [ak. Pk]. He shows that i2 shares with U the Slupecki Criterion property, in that [Qk u {f}] =Pk when f 0 U is surjective or, equivalently, that the only coatom above k is Uk_i. Althoughthe interval [Jk, Uk_i] is uncountable (see Section 2.3), this condition considerably simplifies thesearch for members of [Qk,Pk].U34Chapter 3. Two Intervals in £(Pk) 35Our theorem states that the interval is lattice-isomorphic to the product of a chain of length kand lattice of subgroups of the symmetric group, Sk. For a fixed value of k 3, let us define theclone W1 = Vj V 11k for 1 < i k. Note that W = k, and Wk = Pk. We find that the interval[W,Wk_l] has the same structure as [U,Pk] (as given in Burle’s Theorem, 2.2.2).3.1.1 Theorem(a) [Ik,Pk] ([Wl,Wk_] x [Jk,Skl) {Wj}, and(b) [Wl,Wk_l] = {Wl,L2VW1,...,Wk_l}.Part (b) is a special case of a result due to I. A. Mal’cev [25]; however, we shall include acomplete proof here in an attempt to illuminate the mechanism of not only this theorem, but alsothose of Burle and Slupecki. The proof depends upon the following series of lemmata.3.1.2 Lemma If f,g E k, so that rng(f) < i and rng(g)I = i for some i < k, then there existfunctions u, T E k for which f = ogr.More specifically, if rng(f) C rng(g), then f = gr for some T E k.Proof: Let A= {j : f(j) = i}, for i e k]j, and choose b such that g(b) = i, for i e rng(g).Assume that mg (f) C mg (g). The sets A partition [k]j, and if IAI = 1 for all i E [k]j, it followsthat f is a permutation. Therefore there must be some 1 for which Au > 1. Define r(x) = b forx E A, i e [k]j. Then r e 1k, since T maps at least two elements of its domain to the value b1. Byconstruction, f = gr.Now consider the case when rng(f) rng(g). Since rng(f)I rng(g) < k, it is possible tochoose a function a e k which maps mg (g) onto mg (f). We apply the argument in the paragraphabove to the pair of functions f and ag to find a T for which f = J9T. IThe following three lemmata are due to Jablonskll [21]; see also [19].Chapter 3. Two Intervals in £(‘Pk) 363.1.3 Lemma Suppose mg (f)I 3, f is not essentially unary, and f depends on its first argurnent. Let n = o(f). Then there exist x,y E [ku and u,v [kr—1 for whichf(x,ui,u2,..= a,f(y,ui,u2,.. .,u_i) = b,f(x,vi,v2,..=for some three distinct values a, b, and c.3.1.4 Definition For n 2, four n-tuples in [[kr of the form(ui,. . . , u_1u, . . ,u_i, u, . . .(ni,...,uj_,vj,uj+i,...,uj_i,uj, j+i,...,u),(ui,...,uj_i,uj,uj+i,...,u_i,vj,uj+i,...,un),(u1,. . .,u_1v, . . . ,u_1v, . . , un),for which i <j, u v, and uj v, shall be called a quadrate.3.1.5 Lemma Suppose Irng(f)I 3, and oe(f) > 1. Let n = o(f). Then there exists a value inthe range off which f assumes on exactly one member of some quadrate in [[kr.3.1.6 Lemma (Jablonskil’s Climbing Lemma) For a given function f, let n = o(f). For anyvalue 1, 3 1 < mg (f)I, if f is not essentially unary, there exist subsets G1,G2,. . ., G, Chaving the properties that IGI < l for 1 <i < n andI{f(x) :x e G, 1 i n} = 1. (3.6)Proof: Without loss of generality, suppose that f depends on its first argument. By Lemma 3.1.3,there exist x, y e Jk]j and u, v jfk]j for which f assumes three distinct values on the n-tuples(x,u1,.. .,ui), (y,u1,.. .,ui), and (x,v1,.. .,vi). Let w [[kr, for 1 < 1—3, bearbitrary n-tuples on which f assumes some remaining 1 — 3 values of its range.Chapter 3. Two Intervals in £(Pk) 37Then we letG1 = {, y, w, w?,. . .,G2 =G3 =G = . .,w3}By construction, the requirement 3.6 is satisfied. We see also that IG 1 — 1 for each 1 i n,which completes the proof. IWe may now prove Theorem 3.1.1.Proof: Let us begin with part (b). It is clear that W1 C L V Wi C W2 C C Wk_1. Toshow that each containment is, in fact, a covering relation, suppose that W C K c Wk for someclone K. First, suppose K L2 V W1. For any f E K\W1, then, f is quasilinear, so there existç&j :— Z2 for i E [[nJ], and /‘ : Z2 — [{kJ] for whichf(xo, x1,. . . , =iEjnllSince f W1, f depends on at least two variables, so at least two of the functions {} areonto. Without loss of generality, assume that qo and are onto. Since the constant functionsare contained in W1, W1 U {f} I— f’(x,y), where f’(x,y) = f(x,y,0,0,.. .,0). Then f’(x,y) =b’(o(x) + q(y)), for some map sb’. Using Lemma 3.1.2, we see that W1 U {f’} I- g(x,y), whereg(x, y) = t(q(x) + q(y)), () = 0, i(1) = 1, and10 x=01 x>0.By composing g with itself m — 2 times, one obtains the m-ary functiongm(xo, Xi,. . . , Xm_i) i((x0)+ b(xi) + . . + q(xm_i)).We then make use of Lemma 3.1.2 once again: for any function h e Lm), there exist functionsa E Zk and T E k for i é {m]J for whichh(xo, Xi,.. , Xmi) = agm(roxo,T1X,. . . Tm_iXm_i).Chapter 3. Two Intervals in £(Pk) 38ThenWiU{g}FhforanyheL2,whichmeansthatK=KVWi=V i.To establish the next covering relation, suppose K ç W2 and K L2 V W1. For a functionf E K\(L2 V W1), assume without loss of generality that mg (f) = {2]j. Let n be the arity of f,and for u = (u1, . . . , un_i), set= {x : f(n1 ‘u_1,x, u, . , u_) = O}.We observe that f E L2 if, for any 0 < i n and u, v E {k]j’, either = or ={kJRA,.Since f 0 L2, there must be some i, u, and v for which this property does not hold. That is,0 {Ø, I[k]j}. Either or A,u; fix the notation so that A,Then there exist elements a€and b E Define the functions qj E k,for 0 <j n — 1, byI u ifx=0,( vj otherwise.Let E k be the analogous function mapping 0 i-4 a and {1, 2,. . ., k — 1} ‘—* b; then we may formthe binary functionf’(x, y) = f(i(y),. . . , (y), (x), j(y), . . ., qn-i(y)).Now if a e n we see that f’(x, y) = 1 when x > 1 and y 1, and f’(x, y) = 0 otherwise;f’ restricted to the domain {2j realizes the Boolean conjunction (et). The other case to consideris a e {k]j\(A, U A). Here, f’(x,y) = 0 only if x = 1 and y = 0; otherwise, f’(x,y) = 1. Inthis case, f’ realizes the Boolean “implication” (—f). Choose a function a e k that transposes theelements {0, 1}, and thereby realizes the neg function on the domain 2jJ. Either pair of functions{et, neg} or {—*, neg} is complete in P2; therefore W1 U {f’} I— et, vel. It follows that Wi U {f’} H gfor any g with mg (g) = {2]j, by expressing g in the generalized disjunctive normal form (see page 4).Consequently,W2 C [w1u{f’}] ç W1VK,and K = W2.Chapter 3. Two Intervals in £(Pk) 39Finally, we show that if 1 > 2 and W1_ C K c W1, then K = W1, again by selecting anyfunction f K\W1_.The cardinality of the range of f is exactly 1, and f is not unary; thereforeLemma 3.1.6 shows the existence of sets G, for 1 < i < n that satisfy the equation (3.6), and forwhichIGI < 1 — 1 (3.7)We assume once again, without loss of generality, that mg (f) = and we let g be any otherfunction for which rug (g) = [ljj as well. For each i, 1 i 1, choose an n-tuple u for whichu E G, and f(u1) = i. For each 1 j n, let g3 e be the function defined by g2(x) = u ifg(x) = i. In fact, g3 W1_,by (3.7), so W1_ u{f} I- f(gl,g2,. .. ,gn). However, that compositionis exactly the function g, so g E [W1 U {f}]. By virtue of Lemma 3.1.2, for any h E W1, there existsa e W1 such that h = ag. Therefore W1 C [W1_ u {f}J C K, from which it follows that K = W1.The proof of part (a) is now straightforward. Define the function : [W1,Wk_i] x [E, Ski[Wi,Uk_i] by 1J(X,Y) = Xv Y. To establish that is an injection, suppose that P(X,Y) =(X’, Y’). Observe that (X V Y) A Sk = Y, since X A Sk = [0] = Jk, and a composition of functionsf * g is in Sk if both f and g are in Sk It follows that(XVY)ASk = (XUY)ASk= (XASk)U(YASk)= JkUY=Y.Thus I(X,Y) = (X’,Y’) implies‘IJ(X,Y)ASk =from which Y = Y’. Now recall that U = W V Sk• It is easy to see that the set inclusionsU1 c L2 V U1 c U2 c ... C Uk_i are all strict. It follows that the inclusionsWVYCLWWYC... k_Yare also strict, and (X,Y) = (X’,Y) = X = X’, as required.Chapter 3. Two Intervals in £(Pk) 40One establishes that I’ is surjective by projecting any clone in [W1,Wk) onto the interval’sfactors. Given a clone F for which W1 < F < Wk, let Y = F A Sk, and let X = F A Wk_1. Thenclearly F = X V Y, and W is an isomorphism. Furthermore, it follows from the Slupecki Criterion(Theorem 2.2.1) that Wk covers Wk_1 V Sk• IFigure 3.4: P3]The statement of Theorem 3.1.1 is illustrated for [1, P3] in Figure 3.4. The symmetric groupS3 has four proper, nontrivial subgroups. The subgroups of order two are all indicated by C2 forthe sake of simplicity. The interval contains nineteen clones in all. A corollary of the theorem isthat the number of clones containing k equals k [Jk, Sk1 + 1, where I[Jk, Sk]I is the number ofsubgroups of the symmetric group Sk.P3A3 V W2C2 V W2L2V UA3vL2I 14’2C2 V L2UA3 V C2 V 23Q3Chapter 3. Two Intervals in £(Pk) 413.2 Clones over SkD3P2US2The unary functions are partitioned into permutations and non-permutations: that is, U 1k U Sk,and c2k fl S, = Jk. We now turn our attention to the interval of clones containing Sk. When k = 2,they consist of the six shown in Figure 3.5 (Post [34]). When k > 2, one can determine the structureof [Sk, Pk] using a method similar to that of the previous section, although the outcome here is asomewhat more involved description. One begins by characterizing the unary clones in the interval,then extending the characterization to to the entire interval. The result depends on whether k iseven or odd, and the cases in which k = 3 and k = 4 will need to be treated separately.During the preparation of this thesis, it was observed that Haddad and Rosenberg [18] haveshown that [Sk, Pk] is finite by determining its elements, for k 5, using an argument similar tothe one presented here. We differ, however, by determining the explicit structure of the interval,and resolving the special cases encountered when k = 3 or 4.Recall from the previous section that, when k 3, the only coatom containing 1k is Uk_i.Salomaa [41] has shown that the same is true of Sk when k is large enough (k> 5). Once again,one is led to expect some similarity with the interval [U, Pk].L2L2 A D3Figure 3.5: [52,P]3.2.1 Theorem (Salomaa [41]) If k 5, rng(f)l = k, and o€(f)>1, then [{f}USk] = Pk.Chapter 3. Two Intervals in £(Pk) 423.2.2 Definition Denote the set of all partitions of k by ilj:for somenEN}.Each partition is regarded as a multiset: elements may occur more than once, and order is neglected.Given a function f E let B {j : f(j) = i}, for i E [k]1. Let I = {i : B O}. Define11(f) = {IBil}IEI, and observe that 11(f) is a partition of k. In order to name to the set of functionsthat give rise to a particular partition A é 11k, definek,A = {f E : 11(f) = A}.Furthermore, for all F C 11k, define the cloneOF = [{lk,A : A E F}] V S,.The set 11k admits a partial ordering in the usual fashion: if A, B E 11k, write A < B if and onlyif A is a refinement of B. That is, suppose B = {b1,b2,. . ., b}. Then A is said to be a refinementof B if there exist sets B1,B2,.. . , Bm which partition B, and A = {ZEB, b : 1 <j <m}. Theminimum element of this poset is A0 = {1, 1,. . ., 1}, while the maximum is A1 = {k}. The setof filters .F(llk) form a lattice whose minimum and maximum elements are F0 = 0, and F1 =respectively.For filters F, G e .F(llk) and for each 1 < i < k, define the relation F j G to hold if and onlyif, for all A E 11k with Al > i, A E F A E G. It can be seen that j is an equivalence relationand, in fact, a congruence on the lattice .F(llk). The intuition here is that two filters are related ifthey are equal on all but partitions of small cardinality. In particular, note that F G if F = G.We shall introduce another congruence, EL, which has special properties when k is even. Apartition A E 11k is said to be even if all of its elements are divisible by 2, and odd otherwise. A setof partitions F is called even if A is even for all A E F. We define EL as follows: if F, G E F(llk)and either F or G is even, let F EL G hold if and only if, for all partitions A for which eitherAl > 2 or A is odd, A e F A E G. Otherwise, let F EL G F =2 G.3.2.3 Lemma 1ff E fk,A for some A E 11k, then Sk U {f} HChapter 3. Two Intervals in £(Pk) 43Proof: For any g e k,A, one can find permutations a, r E Sk for which g = afT. I3.2.4 Lemma For a set F c ilk, let F be the smallest filter in 11k for which F ç F. Then ifF {A0}, it is the case that°F O.Proof: Suppose that F {A0}, and let A E 11k be any partition for which there exists someB E F, B A0, with B 1 A. We shall prove the claim by showing that, for any f E 2k,A, OF I- f.It is sufficient to consider the case when A covers B. Begin by choosing ally function g E k,B,and let B,={j : g(j) = i}, and b = BI. Then B = {b : b O}, and A = (B\ {b,b})u{b + b},for some i j, since A covers B. In fact, the argument shall not depend on the values of i and j,so we shall assume that they are 0 and 1, in the interests of simplicity.Let m = IBI. For some 1 E [k]j, we must have b1 > 1, since B A0. Let c0 and c1 be distinctmembers of B1, and let c2,c3,. .., Cm_i be members of some m — 2 of the remaining m — 1 sets{B}. Now define a permutation a E Sk by setting a(i) = c, for 0 < i < m, and choosing a(i) inan arbitrary, bijective manner on the remaining k — m elements of its domain and range.Defining f’ = faf, one sees that f’(i) = f(i) for i ‘ B1, and f’(i) = 0 for i E B0UB1. Therefore11(f’) = A. With the help of Lemma 3.2.3, one obtains Sk U {f’} I- g, which completes the proof.I3.2.5 Lemma Let2 < i < k. 1fF e F(ilk) is afilter which contains all partitions A with Al i,then OF V Vj = OF U V.Proof: Let f be any member of OF V V,. If f is essentially unary, it is clear that OF U Vj I- f.Since our choice of F implies that V11 c OF, it follows that f E OF Otherwise, Oe(f) > 1. Inthis case, we make use of the observation that for any clone K < U1, if g e K V V and g is notessentially unary, then mg (g)) < i. Consequently, f E so OF V V1 c OF U Vj, as required. IThe preceding three arguments shall serve to classify the unary functions found in clones containing Sk. The remaining clones — that is, those which include functions that depend on morethan one variable— are determined for the most part by the cardinality of the range of eachfunction, very much as were their analogues in the interval over Qk, in the previous section. Thefollowing three lemmata will provide the necessary tools to elaborate this notion precisely.Chapter 3. Two Intervals in L(Pk) 443.2.6 Lemma Let f é L2\U. Then[Sku{f}]=2VSk iffeL,L2 V Sk otherwise.Proof: Since f L2, it can be written in the form of equation (2.4). It is easily determined thatall of the constant functions are in [Sk U {f}]. By substituting constants for the variables of f,we find that the functions j, are as well, for all i, 1 < i < n. f is not essentially unary; assume,without loss of generality, that f depends on its first two variables. That is, qo and 4 are notconstant, and is an injection. With the help of the permutations, we may assume that L’ is theinclusion map, and ignore it henceforth. Substituting constants again, one sees that Sk U {f} F f’,wheref’(x, y) = o(x) + i(y).Since is not constant, there exist a, b E {k]j for which bo(a) = 0 and qSo(b) = 1. For any functiongS: {kjj —* Z2, let o E Sk be some permutation mapping 0 i—* a and 1 b. Thenf’(a(q(x)), y) = (x) + i(y),which is to say thatSk U {f,,q’} F g(x) +‘(y)for arbitrary g and q’ mapping {k] into Z2.. So let o e Sk be a transposition of a and b, and considerthe function qo(x) + qSo(a(y)). Since ço and 0a agree on all values except {a, b}, the function(x) defined by identifying x and y assumes the value 1 on {a,b}, and 0 elsewhere. Thereforell() = {2,k— 2}.Using a similar argument, one can use to show that, for any function E [Sk U f] withll() = {l,k— l}, for! 2, there is also a ‘ with ll(’) = {l — 2,k —1 + 2}. If at least one ofl andk —1 is odd, it is not hard to see that one may obtain any function c/I that induces a partition of size2, using two-place addition and permutations. If instead both are even, one generates only thosefunctions with even partitions of size 2. The consequence is that, if f E L2\L, then k,A ç [Sk U f]for all A E 11k, Al = 2. If f E L instead, we add the restriction that A be even.Chapter 3. Two Intervals in £(Pk) 45To prove the claim, let us first consider the case f L. We show that L2 ç [Sk U {f}] in thesame manner as in the proof of Theorem 3.1.1: one constructs q(x) + q(y), where10 ifx=0çb(x)=1 otherwise,then composes this function with itself to form a quasilinear function of arbitrary arity. One thenconstructs an arbitrary function in L2 by further composition with appropriate functions {} andb, since the argument above concludes that all Sk U {f} I— for all q: 1[kjj —f Z2.When f E L, the argument is directly analogous. IThe next two lemmata are drawn from the proof given by Jablonskil [19] of Salomaa’s theorem (3.2.1).3.2.7 Lemma Suppose k > 3, and f é P,\U is a function for which 1mg (f)I = m, for somem 3. Then there exists a unary function [S, U {f}] for which 2 mg ()I <k.Proof: Let n = o(f). We shall prove the claim first for m 4.Lemma 3.1.6 provides sets G, G2,. . . , G,-, for which each IGI <m and for which also the rangeof f is unchanged when its domain is restricted to fl.1 G. If necessary, add elements to the sets{ Gj so that IGI = m — 1 for all i. Since we are free to compose f with the permutations Sk, weshall assume that each set G equals L[m — 1j.Set s0 = (m— 1, m — 1,. . ., m— 1), and c = f(so). We claim that there exist n-tuples s1 ands2 in [m— ir which do not equal each other in any component, and for which f(s2) f(si) = C:For any t E [m— ir for which f(t) = c, letIt={xeL[m—i]j’1Hi:x=t}.There are two cases to consider. First, suppose that there exists some u e L[m— lr\It for whichf(u) c. In this case, set s = t, and s2 = u.Otherwise, for each u E [m— 11jTh\It, f(u) = c. Then there must exist a v E I for whichf(v) c. It is not hard to see, given our hypothesis m— 1 3, that the set [m— lr\(It U I)cannot be empty; let w be a member of it. By assumption, f(w) = C; therefore we may set s = wand s2 = v.Chapter 3. Two Intervals in £(Pk) 46Now choose s arbitrarily, for 3 < j < k, subject to the restriction that for each i,j and 1 witho < i <j < k and 1 < 1 < n, the components sj and sj are distinct. For each 1 < 1 n, definethe permutation 1(i) = s,, and let(x) = f(c1(x),c2(x),. . (3.8)Since q(O) = (1) = c and (2) c, q has the desired properties.We complete the argument by considering what happens when m = 3. Suppose that no inthe clone has 2 < mg ()I < k. m is strictly less than k; hence every composition of the form (3.8)is a constant function. This means that, for any s e {kr, we have f(t) = f(s) for all t kr\I.Consider the following consequence of the definition of the sets Ix: for every u e either u I,or there exists a t 1s for which u I. We see that f(u) = f(s) for all u E I as well, whichmakes f a constant function. However, this contradicts our hypothesis concerning the range of f.I3.2.8 Lemma Suppose k > 3, f E Vm\ Vm_i, for 3 m < k, excluding m = k = 4, and Oe(f)> 1.Then Sk U {f} Vm.Proof: The proof is by induction. We begin by showing that Sk U {f} I— V2. First, we claim thatSk U {f} I- {et, vel}, where et and vel are the minimum and maximum functions, respectively, onthe domain {2]2:[SkU{f}] contains a unary function which is not a permutation; therefore it contains all constantfunctions, by Lemma 3.2.4. Using Lemma 3.1.5, we find a quadrate on which f assumes somevalue exactly once. Construct a binary function f’(x, y) from f with the same property throughthe substitution of constants. By composing f’ appropriately with permutations, we may obtainanother function g(x, y) for which g(O, 0) = 0, and g(x, y) 0 on the remaining values in ff2]j2.Let q be the singular function constructed in the previous lemma (3.2.7). From Lemmas 3.2.3and 3.2.4, we see that we can construct from it a function 4? whose range is of cardinality two. Ifone of the elements of 11(4?) equals 1, then we can construct a function 4” for which qY’(O) = 0 and= 1 for x 0. Then clearly 4?’g equals the function vel on {2]12. Otherwise, both elements of11(4/) are at least two. We assumed that k— mm {4, m}> 0; consequently, some value c E {k]j doesChapter 3. Two Intervals in £(Pk) 47not appear in g(2]j2). From ç’ we can construct a function qY’(x) that is 0 for x = 0 and c, and1 on the nonzero values of g(22). Then “g(0,0) = 0, and g(x,y) = 1 for (x,y) 22\(O,0).That is, vel = once again. Since the function neg on {2]j is simply a permutation, we can alsoform et by de Morgan’s law.It is clear that, from qY, vel, and the permutations, one can construct any unary function on[Ic of range 2. In particular, we may form the functions d(x) defined byIk—1 x=id(x)=0 otherwise,for each i E {k]j. Then any function g E V2 can be expressed in terms of et, vel, and the functionsd1, by writing g in generalized disjunctive normal form (page 4).It remains to show that if 3 < 1 m, thenSk U V1_ U {f} F V,from which our claim follows by induction. Let g be any member of V1. By Lemma 3.1.6, thereexist sets G for 1 < j < n for which IG < 1 — 1 and{f(x):xEG,1 in}I=l.Without loss of generality, assume that f assumes the values on fl G, and that mg (g) =as well. For each i, 1 < i < 1, choose an element & E fJL G, for which f(uz) i. For each1 <j < n, let gj be the function defined by 93(X) = u if g(x) = i. The range of each gj is containedin the set G, so g, E V4. Since f(g1,g2...,g) = g, we have shown that Sk U V U {f} I-g. IWe are now sufficiently prepared to state and prove the results at the heart of this section.3.2.9 Proposition Suppose k > 2. The interval [Sk,U] = [OF0, F,] = {OF : FE F(llk)}, ordered by inclusion.Proof: By definition, Sk = 0 = °F0, and U = °F1 The claim follows easily from Lemmas 3.2.3and 3.2.4: Suppose K E [OFO,0F1. For any function f E K\Sk, we have Sk U {f} I- k,I-I(f). LetF = {ll(f) : f E K\Sk}, from which we see K V Sk== where F E F(llk). That is, theChapter 3. Two Intervals in £(Pk) 48only clones in the interval [Sk, U] are of the form OF for some F E .T(lTk). Since clearly OF = OGif and only if F = G, there is, in fact, a distinct clone for each filter F. IThe main result depends on the parity of k. To keep its statement concise, let L be the classL if k is odd, and L2 otherwise.3.2.10 Theorem Jfk> 5, then[Sk,Pk] [OF0,U] x (V1,L,V2.. .,V)/ ,where (OF, K) (OG, K’) if and only if(a) either K = K’ = Vj for some i, and F j G, or(b) K=K’=L, andF=LG.Proof: We prove the claim by defining the map: [0F,U] x (V1,L,V2.. .,V,) —* [OF0,Pk],as (X, Y) = X V Y, then showing that it is surjective and has kernel exactly .First, we suppose a clone K is in the interval [OF0,Pk], and prove that K is in the image of .For each f e K, if f e U, then [OF0 U {f}] = OF, for some filter F, by the preceding proposition.Otherwise, f is not essentially unary. If f e L, then [Sk U {f}] L, by Lemma 3.2.6, and L is inthe image of . Otherwise f e Vj\Vi for i > 2 or f E V2\L, and so by the lemma to Salomaa’stheorem (3.2.8), it is the case that [Sk U {f}] = . Since the image of 4 is closed under the joinoperation, it follows that K itself is in the image.It remains to show thatOFVY=OGVZ (3.9)holds if and only if (OF,Y) (OG, Z). First, equation (3.9) implies that Y = Z:SupposeY=L. ThenOFVY=OGVZCLVUCU,fori>1. ThereforeZVfori>l,and clearly Z V, which leaves Z=L as well.Otherwise, Y = Vj and Z = Vj for some i and j. Let F’ and G’ be the filters obtainedby augmenting F and G by all partitions of size no greater than i and j, respectively. ThenOFVVi=OF’VVi,andOGVY=OGIVY,soi=j(Lemma3.2.5),andagainY=Z.Chapter 3. Two Intervals in £(Pk) 49Given Y = we show that (3.9) is equivalent to the conditions (a) and (b). First suppose thatY = Z = Vj, for some i, 1 i k. Let F’ be the smallest filter containing F and all A E 11k forwhich Al <i. ThenOFVVi = OF’VVi= OF’ U Vj, (by Lemma 3.2.5)and similarly for G’ containing G. Therefore(3.9) OF’UVi=OG’UViF’nG’.Since F j F’ and G j G’ as well, the condition is equivalent to F j G, as required.Finally, suppose that Y = Z = L. It is clear that if F EL G, then (3.9) must hold. To showthe converse, suppose first that F is not even. A filter which contains odd elements must containodd elements of size 2. Therefore the set{ll(f) : f e (OF V L) fl k} (3.10)contains all partitions of size 2, and so must the corresponding set for G. For any f with lll(f)I > 2,certainly f E OF V L f E OF, using Lemma 3.2.5 again, and F EL G.If F is instead even, the set (3.10) contains only even partitions, and the same argument appliesto show that F EL G.Consequently, the kernel of is , and the theorem is proven. IIt remains to consider the special case of k = 3 or k = 4. For small values of k, we shall givenames to specific clones OF by listing partitions which generate F: for example, let 013,22 denotethe clone in f2 for which F = {{1, 3} , {2, 2}}.We also need to describe two clones peculiar to k = 3,4. Identify {3]j with GF(3) in somemanner, and then define L3 as those functions f P for which there exist constants a, éand c e 3]j, for 1 <i < n, such thatChapter 3. Two Intervals in £(Pk) 50Similarly, identify f[4] with GF(4), and let L22 consist of f P for which there existe {4]j and c E {4]j, for 1 i n, such thatIt is implicit in these two definitions that one obtains the same clone no matter how one identifiesthe elements of 3] or L[4}j with those of the corresponding field. Indeed, this is equivalent to theobservation that S3 <L3, and S4 L2+.L3L2v UFigure 3.6: [S3,P]3.2.11 Theorem [53, P3] consists of the interval described for k = 3 in Theorem 3.2.10, with theaddition of the class L3 sitiated by 03 < L3 < U3.Proof: Let p C L[3]3 be the relation consisting of all triples (a, b, c) for which either {a, b, c} areall distinct, or all the same: it is easily shown that Poip = L3.For any function f E U3\U2,then, either there exists a unary function gin both U\03 and [S3U{f}], or there does not. If there does, then [S3u{g}J = U (3.2.4). By the Slupecki Criterion (2.2.1),we have [S3 U {f}] = P3.Otherwise, we claim that f preserves p. If not, for some A -< p and a b e 1f3]j, f(A) = (a, a, b)t.Clearly [53 U {f}] contains all permutations and constant functions. Each column of A is the imageof a permutation or constant function on the triple (0, 1, 2); therefore, by composing f with theU2U03S3Chapter 3. Two Intervals in £(Pk) 51appropriate permutation or constant for each column, we obtain a unary function f’ e [Sk U {f}]for which f’(O) = f’(l) = a and f’(2) = b. This is a contradiction, since f’ E U\03. Consequently,f E L3. This reasoning shows that the only two coatoms of P3 in the interval [53, P3] are U2 andL3.Suppose next that K is a clone in the interval [S3,U2]. If there exists a function f e K\L2,then Lemma 3.2.6 implies that K = U2. If not, but there exists f e K\U, previous argumentsshow that K D L2, and hence K = L2. Otherwise, K c U, and Proposition 3.2.9 shows that itmust be one of 53 < 03 < U.Finally, we observe that if f E L3\U, then the set f U Sk generates L3 in the same manner asfor L2. Since L3 contains 03 but not U, the lattice is as shown in Figure 3.6. IFigure 3.7: [S4,P]3.2.12 Theorem [S4,P4] consists of the lattice described in Theorem 3.2.10, with the addition ofthe clone L2+, situated between L and P4.S4Chapter 3. Two Intervals in £(Pk) 52Proof: Let€i, ..., E6 be the six equivalence relations on [4j with two equivalence classes of sizetwo, and let a€be the relation S U U 66• It is not hard to verify that L2+ = Pol a.We observe that the theorem above excludes the case where k = 4 because of a restriction of thehypotheses of Lemma 3.2.8; specifically, it does not follow when k = 4 that S4 U {f} F V4 wheneverf e V4\V3. Instead, we show that, for such an f, either S4 U {f} I- V4, or f preserves the relationa.Suppose that f E V4\(V3U U) does not preserve a. We claim, then, that 54 U {f} I- V4. Byhypothesis, there exists A - a for which f(A) = (a,b,c,d)twhere a {b,c,d}, and I{b,c,d}j < 3.(a is row-symmetric, so we may reorder the rows of A according to taste.) In fact, it is sufficientto consider the case where b = c = d (Lemma 3.2.4). Since a is symmetric in L[4j, we shall alsoassume that a = 1 and b = c = d = 0.Now each column of A contains either 1, 2, or 4 distinct elements. Let A1, A2, and A4 besubmatrices of A consisting of the columns of each respective number of elements. We permute thecomponents off to obtain a function f’ for which f’(A1(A24) f(A) =(1,o,o,o)t. [S4 U {f}]contains the constant functions: see Lemma 3.2.7. Construct a function f” by substitution forwhich f”(A21A4)= f(A).f is not essentially unary, and its range is 4jJ, so Lemma 3.1.5 asserts that there exists aquadrate on which f assumes some value exactly once. In fact, f assumes each value of its rangeon this quadrate: otherwise the argument used to prove Lemma 3.2.8 would hold for f as well, and54 U {f} F V4. Composing f with the appropriate permutations and identifying variables yieldsthe following function g:x g(x)00 001 110 211 3Using such a g, we can parameterize f” in such a way as to replace the columns A4 by columnsthat consist each of only two distinct values. We shall also use permutations to replace the columnsA2 by columns consisting only of {0, 1}. We obtain some function h€[S4 U {f”}] for whichChapter 3. Two Intervals in £(Pk) 53h(B) = f”(A21A4)= f(A) = (1,0,0,0), where001010B=100111From this it is clear that Ii, restricted to the domain [2]j, is not linear. That is, hIp P2.The P2 functions 0, 1, and neg are also in the restriction of [S4 U {f}] to If2]. Together with h,they constitute a complete set in P2: refer to Figure 3.5. It follows that 54 U {f} F V2, and theargument of Lemma 3.2.8 gives 54 U {f} I— V4, as claimed.Consequently, the coatoms of P4 are U3 and L2+. To establish that L2+ covers L, supposef eL22\L. The observation of importance is that f is surjective arid depends on more than onevariable; our familiar constructive technique then shows 54 U {f} I- +GF(4), and +GF(4), togetherwith 54, generates L2+2.The proof is completed by remarking that the only exception in the proof of the general theoremwhen k = 4 involved the functions in V4\V3. The structure of the interval [54, U3] follows the generalresult. IChapter 4The Intervals in Context4.1 Homogeneous algebrasThe objective of this section is to set Theorem 3.2.10 within the context of universal algebra. Analgebra that admits all permutations of its underlying set as automorphisms is said to be homogeneous. Homogeneous algebras are of interest because of their high degree of internal symmetry; infact, no finite algebra on five or more elements has an endomorphism monoid that properly containsthe set of all permutations. (See Birkenhead [3].) The homogeneous algebras have been analyzedcompletely within the last fifteen years. It will be shown here how Theorem 3.2.10 can be appliedto describe the finite, relation algebras with an analogous automorphism condition.A function f e Pk is called homogeneous if it admits all o E Sk as automorphisms, and a setof functions F is homogeneous if all of its members are or, equivalently, if the algebra (k]; F) is.We remark that homogeneity is a relational property: if F is homogeneous, so is [F].As before, the simplest case to consider is that of P2, in which the property coincides with self-duality, and hence the homogeneous clones are just those of the interval [J2,D3] (v. Figure 2.2).Homogeneity can thus be regarded as a generalization of the self-dual property of Boolean functionsand clones.Marczewski has characterized homogeneous functions in the following way.4.1.1 Definition (Quackenbush [35]) a,b [k are said to be of the same pattern if, for1 < i, j n,a=a3 ‘A function f E P is a pattern function if there exists a function s : [k —÷ 2H\ {O} for which,54Chapter 4. The Intervals in Context 55Va é {k and Vi E s(a),f(a) = a,and s(a) = s(b) when a and b are of the same pattern.That is, f is a projection when its domain is restricted to any subset of {k]jTh of the same pattern.It turns out that the homogeneous functions exhibit oniy slightly more diversity:4.1.2 Proposition (Marczewski [28]) A function f e p is homogeneous if and only if thereerists a function s : —÷ 2N for which(a) s(a) = s(b) when a and b are of the same pattern,(b) s(a) = 0 only if I{ai,...,an}I k—i, and(c) f(a)=a iffies(a).A moment’s reflection shows that, if clones K and K’ are homogeneous, then so are K A K’ andK V K’; hence, the homogeneous clones form a sublattice of £(Pk). In order to be more precise,let A be a k! x k matrix whose rows are the k! permutations of {kjj. Regard the columns of A asa relation in Rk. It is immediate from the definition that f E Pk is homogeneous if and only if fpreserves A and, in fact, it is not hard to see that A is equivalent to the relation0 1 2 •.. k—iPk= 1 0 2 k—ii23.• 0since the permutations in the second and third rows of p together generate the group Sk. Consequently, a clone K is homogeneous if and only if it is a member of the interval [Jk, Polpkj.Csákány has shown in [8] and [9] that when k > 5, all nontrivial homogeneous clones in Pkare complete with constants. That is, if K E (Jk,Polpk], then K V Conp(k) = Pk. He has alsodetermined the only six such clones that are not complete with constants, which are as follows:Chapter 4. The Intervals in Context 56= [1 + x] = 04,K2 =in P2 See Figure 2.2.A3 = L5,K4 =A5 [2x +3 2y] in P3, and‘(2 X A2 in P4, the four-element wierczkowski algebra.Subsequent investigations completely revealed the structure of the interval of homogeneous algebras for each k 2. Csákány and Gavalcová [101 first described its minimal elements. Marenkov[31] and [30] then gave a description of the remaining structure showing that there are finitelymany homogeneous algebras for each k 2. Their lattices are easily drawn for k > 3, with theexceptional clones K and 1(6 added to a general pattern when k = 3 and 4, respectively.4.2 Homogeneous relation algebrasIt is also possible to formulate the notion of a homogeneous relation: we refer to Pöschel [32]. Let apermutation 7 e Sk act on an m-tuple by the application of a to each component. Then a relationp E Rk is defined to be homogeneous if and only if, for each point r E p and u e Sk, it is the casethat ur e p. Correspondingly, a coclone R < Rk is homogeneous if every p E R is a homogeneousrelation. This definition is equivalent to writing that R is homogeneous if and only if the clone Skpreserves R; thus we see that the homogeneous coclones are exactly those comprising the interval[Dk, mv Ski.If K E Pk is a homogeneous clone, clearly I <Rj (the graph of K) is a homogeneous coclone.Furthering the analogy with the case of functions, we say that R is complete with constants ifR V ConR(k) = Rk. Pöschel [32] has proven that the only nontrivial, homogeneous coclones thatare not complete with constants are 1(, K,. . ., 1(6’. This is surprising in that there is no a priorireason to expect such a degree of correspondence.Chapter 4. The Intervals in Context 57We remark that the interval of homogeneous coclones, [Dk, mv Ski, is the image of [Sk, Pk] undermv operator. Application of the Galois Correspondence to the description of the interval [Sk, Pk]given for k 3 in Theorems 3.2.10—3.2.12, then, yields the relational analogue to Marëenkov’scharacterization of the homogeneous clones. In particular, we see that there are also only finitelymany homogeneous coclones. At this point, one might make the reasonable objection that thiscorrespondence gives no explicit description of the homogeneous coclones themselves, but only oftheir polymorphs. It is not difficult, though, to find generators for the invariants of each clonediscussed in Section 3.2; one might begin with Rosenberg’s observation [38] that mv U = [ti] in Rkfor 2 < i < k. (t is defined on page 25.)To illustrate the sort of information provided by this correspondence, we use it to rederivePöschel’s result that all homogeneous coclones except K and I( are complete with constantswhen k > 3. Suppose R < Rk is not complete with constants. That is, R V ConR(k) < Rk,which is equivalent to Jk < Po1R A PolConR(k). Clearly f E PolConR(k) if and only if Trf =consequently, if f E Pol R A Pol ConR(k) and f Jj, then f is surjective and not essentially unary.When k 5, Theorem 3.2.10 indicates that the only member of [Sk, Pki containing such a functionf is Pk, whence R = mv Pk = Dk, the trivial coclone. If k = 3 or 4, there remain the additionalpossibilities that Po1R = L3, or PolR = L2+. Thus the only nontrivial choices of R are InvL3and mv L22. By definition, K5 = [2x +3 2y]. From Proposition 1.2.7, K = [(2x +3 2y)], and000111222(2x+32y)= 0 1 2 0 1 2 0 1 2021210102which we noted in the proof of Theorem 3.2.11 was a generator of mv L3. In the same way, 1k6is generated by g(x, y, z) = x + y + z over GF(4), and we saw that g generates mvL2+; henceK = InvL22.4.3 k as endomorphismsEnquiries about homogeneous clones and coclones are part of a more general study of endomorphismmonoids. The interval of clones with given endomorphisms has been considered for monoids otherChapter 4. The Intervals in Context 58than Sk. For example, Marenkov [31] has determined the clones with automorphism group Ak,the alternating group, and Demetrovics and Hannák [11] have shown that uncountably many cloneshave a cyclic automorphism group, for k 5.Let us briefly reconsider Theorem 3.1.1 in this spirit. A coclone Q < R, admits the endomorphisms 1k if Zk Po1Q. We have shown that I[Ik,Pk1I < oo, so there are only finitely many suchcoclones. One might be motivated to seek an analogy with the case of Sk and ask if there are alsofinitely many clones admitting this monoid of endomorphisms.The answer is affirmative for k 3 and somewhat trivial; it turns out that the only functionswith the endomorphisms k are projection functions. Suppose f e pn1) is such a function. It isimmediate that f(a) e {ao,. . . , an_}, for any a E [kr. One can also show that f must be apattern function. The elements of [k of a given pattern induce an equivalence relation onin natural way, and equivalence relations form a lattice under the partial ordering of refinement:write E 1 c’ if c is a refinement of e’. For a E jJk, define s(a) = {i : f(a) = a}, and let p(a)denote the equivalence relation on n]j induced by equality amongst the components of a. Supposep(a) = p(b). We wish to show that s(a) = s(b). If not, choose c e [k equal to 1 on s(a), and 0elsewhere. Since p(a) <p(c) and p(b) <p(c), there exist functions r and ci in k, when k> 2, forwhich c = ra, and c = cib. Since T and ci are endomorphisms of f,f(c) = f(Ta)= rf(a)= ra = 1.On the other hand,f(c) = f(ub)= af(b)= Tb = 0,a contradiction. The argument above shows, more generally, that if p(a) 1 p(b), then s(a) Cwhich we may interpret as stating that f is a projection when it is restricted to any subset of fkFconstituting an ideal of patterns.Chapter 4. The Intervals in Context 59Now we continue to show that f must be a projection. Since f is a pattern function, there is afunction s as above. Let S {s(a) : a [kr}. If some two sets s(a) and s(b) are disjoint, thenone mimics the argument in the previous paragraph by choosing a c to show that f is not welldefined. For any two sets s(a) and .s(b) in 5, then, it is possible to choose some c for whichp(c) = {s(a)\s(b), s(a) fl s(b), j{n]J\s(a)},since k > 3. Also choose a’ so that p(a’) = {s(a), L{nj\s(a)}; then s(a’) = s(a), since p(a) 1 p(a’).Do the same for b to obtain a b’ for which s(b’) = s(b). Thenp(c) p(a’) = s(c) ç s(a’) =and, similarly, s(c) C s(b). It follows that s(c) = .s(a) fl s(b), from which s(a) fl s(b) e S. ThenS is closed under intersection, and no two members of S are disjoint; therefore S is nonempty.However, this is equivalent to the statement that f is a projection.The arguments above exclude the two-valued case. When k = 2, the only constraint is thatf(O,. . ., 0) = 0 and f(l,. . ., 1) = 1. Clones of this form make up the interval [J2,C4], as we saw inSection 2.1, and there are couritably many of them.4.4 Concluding remarksThis investigation was prompted, in part, by the lack of a satisfying explanation for the substantialdifference between £(22) and its higher-valued analogues. While the work here does not at allattempt such an explanation, one might hope that it contributes a mote of insight in that direction. We have extended existing results to show that specific regions of the lattice are finite andeasy to describe for all finite underlying sets. The intervals’ structure is regular for sufficientlylarge underlying sets, while the special properties of sets of fewer than five elements give rise toirregularities. In the two-valued case, almost nothing is left of the regular structure.Both intervals considered are expressed in terms of the product of an interval of unary clonesand Burle’s chain. While the description of [Sk, Pk] is subject to the added detail that not allelements of the product are distinct, one should note that [Sk, Pk] remains the simpler interval ina descriptive sense. Its structure reflects that of the lattice of filters of a well-known poset, whereasChapter 4. The Intervals in Context 60[Qk, Pk] contains the subgroup lattice of the symmetric group, which itself has a structure richenough to remain incompletely understood.The reader might observe that the arguments used to establish the structure of [Sk, Pk] do not,in most cases, require the presence of the entire symmetric group. Instead, it seems likely thatthe methods of Section 3.2 could be adapted to establish a similar result describing those clonescontaining a proper subgroup of Sk; a natural candidate would be Ak, the alternating group.The theorems of Chapter 3 indicate the structure of the intervals, and their finiteness. If one iswiffing to relinquish the quest to describe the structure, it seems probable that one could determinewhether or not other, related intervals are finite. In their book, Pöschel and Ka1unin pose theproblem of finding general criteria for [Jk, K] or [K, Pk] to be of finite cardinality. A reasonablerestriction might be to consider first the interval [K, Pk} for clones K that share with U, k, andSk the property that they are contained in Uk_i and no other coatom of Pk.Bibliography[1] I. Agoston, J. Demetrovics, and L. Hannák. On the number of clones containing all constants.In Lectures in Universal Algebra, pages 21—25. Colloq. Math. Soc. János Bolyai, 43, North-Holland, 1983.[2] K. A. Baker and A. F. Pixley. Polynomial interpolation and the Chinese Remainder Theoremfor algebraic systems. Mathematische Zeitschrift, 143:165—174, 1975.[3] R. Birkenhead. Endomorphism monoids containing all permutations. Algebra Universalis,13(1):268—269, 1981.[4] V. G. Bodnarëuk, L. A. Ka1unin, B. N. Kotov, and B. A. Romov. Galois theory for Postalgebras I-Il. Cybernetics, pages 243—252, 531—539, 1969. English trans. of B. F. Bo,rapqyK, JI. A. Ra3Iy>I<HLrn, B. H. hOTOB i B. A. POMOB, Teopin Fa3Iya ,znn a3lre6pHocTa Iii, J4TII. IepHeTMI<a 3 (1969), 1—10; 5 (1969), 1—9.[5] G. A. Burle (F. A. Bypne). KJIaccM k-3HatI.Ioii JIOPIflG!, co,riep>iaute BCeO,2JHOi nepeMeHHoii. C1CpeTHMi aHaJIL!3, 10:3—7, 1967.[6] S. Burns and H. P. Sankappanavar. A Course in Universal Algebra. Springer-Verlag, NewYork, 1981.[7] J. W. Butler. On complete and independent sets of operations in finite algebras. PacificJournal of Mathematics, 10:1169—1179, 1960.[8] B. Csákány. Homogeneous algebras. In H. Kautschitsch, W. Mflller, and W. Nöbauer, editors,Contributions to General Algebra, pages 77—81, Klagenfurt, 1978. Johannes Heyn.[9] B. Csákáiiy. Homogeneous algebras are functionally complete. Algebra Universalis, 11:149—158, 1980.[10] B. Csákány and T. Gavalcová. Finite homogeneous algebras I. Acta. Sci. Math., 42:57—65,1980.[11] J. Demetrovics and L. Hannák. The number of reducts of a preprimal algebra. AlgebraUniversalis, 16:178—185, 1983.[12] J. Demetrovics and L. Hannák. Construction of large sets of clones. Z. Logik und GrundlagenMath., 33:127—133, 1987.[13] J. Demetrovics and I. A. Mal’cev. On the depth of infinitely generated subalgebras of Post’siterative algebra P3. In Lectures in Universal Algebra, pages 85—96. Colloq. Math. Soc. JánosBolyai, 43, North-Holland, 1983.61Bibliography 62[14] G. P. Gavrilov. Inductive representations of Boolean functions and the finite generation of Postclasses. Algebra and Logic, 23(1):1—19, 1984. English trans. of I’. H. PaBpiinoB. l4H,2yl<-THBHM npe,Z1cTaB3IeHMI 6yJIeByx 4yHI<IJHii H I<oHe.IHai flOpOI<,ZIaeMocTb I<3ICCOBnocra. Arrrepa H .TIorina, 23(1):3—26, 1984.[15] D. Geiger. Closed systems of functions and predicates. Pacific Journal of Mathematics,27(1):95—100, 1968.[16] G. Grätzer. Universal Algebra. Springer-Verlag, New York, 1979.[17] L. Haddad. Intersections of finitely generated clones. Algebra Universalis, 27(2), 1990.[18] L. Haddad and I. Rosenberg. A note on finite clones containing all permutations. In Proceedings of the ISMVL, pages 34—41, Washington D.C., 1990. IEEE Computer Society Press.[19] S. V. Jablonskii. Einfiirung in die Theorie der Funktionen der k-wertigend Logik. In S. V.Jablonskii and 0. B. Lupanov, editors, Diskrete Mathemutik und Mathematische Fragen derKybernetik, pages 13—70. Birkhäuser Verlag, Basel, Stuttgart, 1980.[20] 5. V. Jablonskii, G. P. Gavrilov, and V. B. Kudrjavcev. Boolesche Funktionen und PostscheKlassen. Akademie-Verlag, Berlin, 1970. trans. R. Lindner of C. B. a IOHCICHiI, P.H. Papno, ri B. B. Ky,2p5IBueB. FyHKW?!H anre6pi ioriti it ijiaccii nocTa.HayKa, MocI<Ba, 1966.[21] S. V. Jablonskii(C. B. fl6noHcKi). YHI(IWOH3TEHM flOCTPOHHfl B k-3Hato*nore. Tpy,zu MaTeM. HHc’r. MM. B. A. CTeI<noBa, 51:5—142, 1958.[22] Ju. Janov and A. Munik (10. JIHOB H A. MyHHI<). 0 CyIIJeCTBOBaHMH k-3HaWHIIX3M1<HYTBIX I<3ICCOB He HMeIOI1HI< KOHCHOO 6a3Hca. .LLoi.n. Ai<a,zi. Hayi< CCCP,127:44—46, 1959.[23] A. V. Kuznecov (A. B. hy3HeI]oB). Anre6pa 3IOTMIH H ee o6o6rgeHHn. In MaTeMTHI B CCCP 3a 40 neT. T. 14, pages 102—115. Mocicna, 1959.[24] A. V. Kuznecov (A. B. hy3HeuoB). CTpyKTypu C 3MMRHHM H I<PHTMM cl3yHH-IJH0HaJmHOM flOiIHOThI. Ycn. MaT. Hayi, 16(98):201-202, 1961.[25] I. A. Mal’cev. Some properties of cellular subalgebras of a Post algebra and their basic cells.Algebra and Logic, 11(5):315—325, 1972. English trans. of 14. A. ManBrIeB. HeHoTopHeCBOiiCTBa I<flTOHbIX no,ziaire6p aire6p lloc’ra H MX OCHOBHMX I<iIeToK. Aiire6paH JTorr?ma, 11(5):571—587, 1972.[26] A. I. Mal’cev (A. 14. ManiiieB). 06 O,IHoM YCHflHHH eope Cnyneioro HJI6IOH-clioro. Anre6pa H JI0rHI<a, 6(3):61—75, 1967.[27] I. A. Mal’cev (14. A. ManIieB). HeRoTopue cBoiicTBa I<3ITOK anre6p HocTa.,T[HCIipeTHMi aHaJ1H3, 20:24-31, 1973.[28] E. Marczewski. Homogeneous algebras and homogeneous operations. Fund. Math., 56:81—103,1964.Bibliography 63[29] S. S. Marenkov. Existence of finite bases in closed classes of Boolean functions. Algebraand Logic, 23(1):66—74, 1984. English trans. of C. C. Mapem<oB. K CymeCTBoBaHItIoI(oHe-IHEIx 6a31!COB B 3MMIYTMX iiaccax 6yiIeBbIx ymgii. Anre6pa I’I JIoria,23(1):88—99, 1984.[30] S. S. Marenkov (C. C. MapeHKoB). 0 3MI<HThIX inaccax CaMO,ZJBO1CTBeHHMX4yHI<gMi MHOFO3HaHOi JIOFIThM. HpO6iIeMBI RMepHeTrn(M, 36:5—22, 1979.[31] S. S. Marëenkov (C. C. MapernioB). O,ziHopo,2HMe aJIrepbI. Hpo3IeMM FepHeTMI<I, 39:85—106, 1982.[32] R. Pöschel. Homogeneous relational algebras are relationally complete. In Finite Algebra andMultiple-Valued Logic, pages 587—601. Colloq. Math. Soc. János Bolyai, 28, North-Holland,1979.[33] IL Pöschel and L. Kalunin. Funktionen- und Relationenalgebren: Em Kapitel der DiskretenMathematik. Birkhuser Verlag, Basel, Stuttgart, 1979.[34] E. L. Post. The two-valued iterative systems of mathematical logic. Annals of Math. Studies 5,Princeton University Press, Princeton, 1941.[35] R. W. Quackenbush. Some classes of idempotent functions and their compositions. Colloq.Math., 29:71—81, 1974.[36] I. G. Rosenberg. IJber die Verschiedenheit maximaler Kiassen in Pk. Rev. Rournaine Math.Pures Appi., 14:431—483, 1969.[37] I. G. Rosenberg. Uber die functionale Vollständigkeit in den mehrwertigen Logiken. RozpravyCeskoslovenské Akademie Véd. Rada Mat. Piir. Véd., 80(4):3—93, 1970.[38] I. G. Rosenberg. Universal algebras with all operations of bounded range. Colloq. Math.,30:77—85, 1974.[39] I. G. Rosenberg. Completeness properties of multiple-valued logic algebras. In D. C. Rine,editor, Computer Science and Multiple- Valued Logic: Theory and Applications, pages 150—192.North-Holland, Amsterdam, 1984. revised ed.[40] A. Salomaa. On the number of simple bases of the set of functions over a finite domain. Ann.Univ. Turkuensis, Ser. A I, 52, 1962.[41] A. Salomaa. On basic groups for the set of functions over a finite domain. Ann. Acad. Sci.Fenn., Series A I Math., 339:3—11, 1963.[42] P. Schofield. Complete subsets of mappings over a finite domain. Proc. Camb. Phil. Soc.,63:597—611, 1966.[43] A. B. Ugol’nikov. Closed Post classes. Soviet Mathematics (Izvestiya VUZ), 32:131—142, 1988.[44] J. Slupecki. Kriterium pelnosci wielowartosciewych systemow logiki zdaii. C. R. Seanc. Soc.Sci. Varsovie, 32:102—109, 1939.[45] P. De Witte. A single axiom for closure operations. Algebra Universalis, 12:268—269, 1981.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Many-valued generalizations of two finite intervals...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Many-valued generalizations of two finite intervals in Post’s lattice Denham, Graham Campbell 1994
pdf
Page Metadata
Item Metadata
Title | Many-valued generalizations of two finite intervals in Post’s lattice |
Creator |
Denham, Graham Campbell |
Date Issued | 1994 |
Description | A study due to Emil Post shows that, although the lattice of clones in two-valued algebraic logic is countably infinite, there exist oniy finitely many clones that contain both constants, and only finitely many that contain the negation function. There are, however, uncountably many k-valued clones for all k > 2; in fact, it is known that uncountably many clones contain all constants. The constants of two-valued logic can also be regarded as the set of noninvertible, unary functions on a two element domain. It is shown here that, for values of k greater than two, there remain only finitely many k-valued clones containing all such functions. Similarly, one can generalize the set of clones in Post’s lattice that contain the negation function to those k-valued clones that contain all invertible, unary functions. Once again, there are only finitely many such clones, and they can be described explicitly. These two generalizations of sets of two-valued clones are presented with an introduction to the study of the lattice of clones, and a survey of relevant results. We also note and discuss the fact that the latter result serves to give a description of all homogeneous relation algebras over a finite underlying set. |
Extent | 1287029 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-02-28 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0051439 |
URI | http://hdl.handle.net/2429/5287 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 1994-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1994-0341.pdf [ 1.23MB ]
- Metadata
- JSON: 831-1.0051439.json
- JSON-LD: 831-1.0051439-ld.json
- RDF/XML (Pretty): 831-1.0051439-rdf.xml
- RDF/JSON: 831-1.0051439-rdf.json
- Turtle: 831-1.0051439-turtle.txt
- N-Triples: 831-1.0051439-rdf-ntriples.txt
- Original Record: 831-1.0051439-source.json
- Full Text
- 831-1.0051439-fulltext.txt
- Citation
- 831-1.0051439.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051439/manifest