You are an expert at summarizing long articles. Proceed to summarize the following text: 
our results have impact on three fields : model theory , universal algebra , and theoretical computer science . we therefore have a three - fold introduction .      in model theory , reducts of a relational structure @xmath0 are usually considered _ up to first - order interdefinability_. to be more precise , one considers the reducts of the expansion of @xmath0 by all first - order definable relations , and two reducts @xmath1 and @xmath2 are considered to be the same if and only if there is a first - order definition of @xmath1 in @xmath2 and vice versa . it is well - known that there is a close connection between classifications of reducts up to first - order interdefinability and the theory of infinite ( closed ) permutation groups . in 1976 , cameron  @xcite showed that the highly set - transitive permutation groups are exactly the automorphism groups of the reducts of @xmath3 . he also showed that there are exactly five reducts of @xmath3 up to first - order interdefinability . recently , junker and ziegler gave a new proof of this fact , and showed that @xmath4 , the expansion of @xmath3 by a constant @xmath5 , has 116 reducts  @xcite . thomas showed that the first - order theory of the random graph also has exactly five reducts  @xcite and conjectured that every structure with quantifier elimination in a finite relational signature has a finite number of reducts , up to first - order interdefinability .    in this article , we initiate the systematic study of reducts up to _ primitive positive interdefinability_. a first - order formula is _ primitive positive _ if and only if it is of the form @xmath6 for atomic formulas @xmath7 . clearly , classifications up to primitive positive interdefinability are harder to obtain , compared to first - order interdefinability , since there are far more reducts to distinguish . the simplest structure where such a classification can be studied is the structure that has no structure at all except for the equality relation , which is considered part of first - order logic . our result classifies the reducts of the structure @xmath8 , where @xmath9 is a countably infinite set , up to primitive positive definability . while this might look trivial at first sight , we prove that the number of such reducts equals the continuum . it turns out that the partial order ( in fact , the lattice ) of these reducts is quite complex , but can be described reasonably well . we remark that the classification of the reducts of @xmath10 up to primitive positive interdefinability is the same as the classification for a structure of the form @xmath11 , where @xmath12 is a set of arbitrary infinite cardinality . to show our classification result , we use a concept that is called _ clone _ in universal algebra . clone _ is a set of operations on some fixed domain that is closed under compositions and contains all projections . the clones we are interested in are moreover _ locally closed _ , which means that they are , similarly to closed permutation groups used for the study of reducts up to first - order interdefinability , closed sets in the natural topology on the operations . for @xmath13-categorical structures @xmath0 , there is a one - to - one correspondence between the reducts of @xmath0 and the locally closed clones that contain the automorphisms of @xmath0 . in order to classify the reducts of @xmath10 , we thus classify those locally closed clones which contain all permutations of the domain . we believe that several of the results and techniques presented in this article can be used to also classify reducts of other @xmath13-categorical structures up to primitive positive definability . such future classifications are likely to combine existing results on first - order closed reducts , such as the above - mentioned results on the dense linear order and the random graph , with the results of the present paper .      for universal algebraists , the title of our paper could be `` the locally closed clones above the permutations '' . in fact , in this article we describe the lattice of all locally closed clones on a countably infinite set that contain all permutations of this set . traditionally , most work on clones was done for clones on a finite domain , and only occasionally clones on infinite sets were studied . however recently , the use of methods from mathematical logic , in particular from set theory , has allowed for the production of a considerable number of new results on clones over infinite sets . classical results on clones , mostly on finite domains , can be found in the books @xcite , @xcite , and @xcite , while the recent survey paper @xcite contains much of what is known on clones over infinite sets . the clones on a finite domain which contain all permutations were completely determined in @xcite ; it turns out that the number of such clones is finite . if one moves on to infinite domains , there are two possible clone lattices which can be considered : the lattice of local clones , which is closer to the clone lattice on a finite domain in both size and methodology that can be employed for its study , and the lattice of all clones , the investigation of which often involves set - theoretical constructions ( as in @xcite , for example ) .    in the full clone lattice over an infinite set , the interval of those clones which contain all permutations has been subject to investigation . for example , its dual atoms have been completely described on domains of regular cardinality ( @xcite , @xcite ) . moreover , its atoms were determined for all infinite domains in @xcite . however , the number of clones above the permutations has been shown to be huge ( @xcite , @xcite , @xcite ) , and it seems unlikely that all such clones on an infinite set will ever be classified . as our results will show , the situation is quite different for local clones which contain the permutations . these clones had not yet been subject to explicit investigation and were largely unknown except for a few implicit results , such as partial results on local clones containing all unary operations in @xcite . it turns out that although the lattice of locally closed clones which contain the permutations is uncountable , one can obtain a reasonable understanding of it . we remark here that the lattice of all local clones has been shown to be quite complicated ; in particular , already on a countably infinite base set , the class of lattices which are completely embeddable into it properly contains the class of all algebraic lattices with a countable number of compact elements ( @xcite , @xcite ) . the satisfiability problem for propositional logic is one of the most fundamental problems in computer science , and among the hardest problems in the complexity class np . many restrictions of this problem stay np - hard e.g. the problems not - all - equal-3sat and one - in-3-sat . in a groundbreaking paper in 1978 , schaefer studied a large class of natural restrictions of the satisfiability problem  @xcite . for a fixed structure @xmath0 over the boolean domain @xmath14 , the computational problem is to decide whether a given sentence of the form @xmath15 is true , where @xmath16 is of the form @xmath17 for a @xmath18-ary relation @xmath19 in @xmath0 . this problem is now known as csp@xmath20 , the _ constraint satisfaction problem _ for the _ constraint language _ @xmath0 . ( it is easy to see that 3sat , not - all - equal-3sat , and one - in-3-sat can be modelled as csp@xmath20 for appropriate boolean constraint languages @xmath0 . ) schaefer proved that for boolean constraint languages @xmath0 the problem csp@xmath20 can either be solved in polynomial time , or is np - complete , and he gave a complete description of the tractable and the hard boolean constraint languages . schaefer s theorem inspired many other complexity classification projects for computational problems that are ` parametrized ' by a constraint language , and similar results have been obtained not only for constraint satisfaction , but also for other computational tasks such as _ quantified constraint satisfaction _ , _ learning of propositional formulas _ , _ counting solutions _ , and the _ maximum solution problem_. it turns out that for all these computational problems the computational complexity does not change if we add relations to the constraint language @xmath0 that have a primitive positive definition in @xmath0 . this implies that the complexity of these problems only depends on the so - called _ clone _ consisting of all _ polymorphisms _ of the constraint language , i.e. , the set of those operations that preserve all relations in @xmath0 . the lattice of clones on a two - element set was determined already quite some time before schaefer , namely by post in 1941  @xcite . and indeed , schaefer s classification can be formulated in terms of post s lattice , see e.g.  @xcite . our result can be viewed as an analog of post s lattice for the logic of equality ( rather than for propositional logic ) . in this analogy , boolean relations correspond to relations that have a first - order definition in @xmath8 , where @xmath9 is an arbitrary infinite set . sets of such relations have been called _ equality constraint languages _  @xcite . hence , in this paper we study the lattice of polymorphism clones of equality constraint languages . note that equality constraint languages are exactly those constraint languages that are preserved by all permutations of the domain ; in this sense , we study those constraint languages up to primitive positive interdefinability that have the maximal possible degree of symmetry . the constraint satisfaction problem for equality constraint languages has been investigated in  @xcite . it was shown that csp@xmath20 is np - complete if the polymorphism clone of the constraint language is the smallest element in the lattice ; otherwise , it is polynomial - time solvable . the _ quantified constraint satisfaction problem ( qcsp ) _ for equality constraint languages @xmath0 has been investigated in  @xcite . we make the notions of the introduction precise , and fix some definitions and notation from logic and universal algebra . moreover , we explain how to translate our classification problem from logic to algebra and vice - versa : that is , we demonstrate in what way reducts correspond to local clones . consider the relational structure consisting of a countably infinite domain and the relation of equality only . for notational simplicity , we will assume that this domain is the set @xmath21 of natural numbers . by a _ reduct _ of @xmath22 we mean a structure @xmath23 , where @xmath24 is a set of finitary relations on @xmath21 all of which can be defined by a first - order formula in the language of equality . let @xmath25 be a first - order formula over the relational signature @xmath26 . then @xmath25 is called _ primitive positive _ or @xmath27 iff it is of the form @xmath28 , where @xmath29 are atomic @xmath26-formulas . for a set @xmath24 of relations on @xmath21 , we write @xmath30 for the set of all relations on @xmath21 which can be defined from @xmath24 by pp formulas ( over the signature appropriate for @xmath24 ) . we say that a structure @xmath31 is _ pp - definable _ from a structure @xmath32 iff @xmath33 . we say that @xmath34 are _ pp - interdefinable _ iff they are pp - definable from each other . the structure @xmath35 is _ pp - closed _ iff @xmath36 . the notion of pp - definability imposes a quasiorder on the reducts of @xmath37 , and the relation of pp - interdefinability is an equivalence relation on this order . we are interested in the partial order which is obtained by factoring the quasiorder of reducts by this equivalence relation . that is , we consider two reducts the same iff they are pp - interdefinable , or equivalently , we consider the partial order of pp - closed reducts . in fact , the pp - closed reducts form a complete lattice , where the meet of a family of structures @xmath38 is the structure @xmath39 , and the join is @xmath40 . fix a countably infinite base set ; for convenience , we take the set @xmath41 of natural numbers . for all @xmath42 , denote by @xmath43 the set @xmath44 of @xmath45-ary operations on @xmath41 . then @xmath46 is the set of all finitary operations on @xmath41 . a _ clone _ @xmath47 is a subset of @xmath48 satisfying the following two properties :    * @xmath47 contains all projections , i.e. , for all @xmath49 the operation @xmath50 defined by @xmath51 , and * @xmath47 is closed under composition , i.e. , whenever @xmath52 is @xmath45-ary and @xmath53 are @xmath54-ary , then the operation @xmath55 defined by @xmath56 also is an element of @xmath47 . since arbitrary intersections of clones are again clones , the set of all clones on @xmath41 , equipped with the order of inclusion , forms a complete lattice @xmath57 . in this paper , we are interested in certain clones of @xmath57 which satisfy an additional topological closure property : equip @xmath41 with the discrete topology , and @xmath58 with the corresponding product topology ( tychonoff topology ) , for every @xmath42 . a clone @xmath47 is called _ locally closed _ or just _ local _ iff each of its @xmath45-ary fragments @xmath59 is a closed subset of @xmath43 . equivalently , a clone @xmath47 is local iff it satisfies the following interpolation property :    _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ for all @xmath42 and all @xmath60 , if for all finite @xmath61 there exists an @xmath45-ary @xmath52 which agrees with @xmath62 on @xmath63 , then @xmath64 . _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _    again , taking the set of all local clones on @xmath41 , and ordering them according to set - theoretical inclusion , one obtains a complete lattice , which we denote by @xmath65 : this is because arbitrary intersections of clones are clones , and because arbitrary intersections of closed sets are closed . the join of a family @xmath66 is calculated as follows : first , consider the set of all operations on @xmath41 which can be obtained by composing operations from @xmath67 ; this set is a clone , but might not be locally closed . for this reason , the topological closure of this set has to be formed in addition in order to arrive at the join in @xmath65 . for a set of operations @xmath68 , we write @xmath69 for the smallest local clone containing @xmath70 ; if @xmath47 is a local clone and @xmath71 , then we say that @xmath47 is _ generated _ by @xmath70 . observe that @xmath69 is just the intersection of all local clones containing @xmath70 , or equivalently the topological closure of the set of term operations that can be built from @xmath70 . using this notation , the join of the family @xmath66 is simply @xmath72 . this paper investigates , and in some sense classifies , those local clones on @xmath41 which contain all permutations of @xmath41 . it turns out that the number of such clones is uncountable . let @xmath73 and let @xmath74 be a relation . we say that @xmath75 _ preserves _ @xmath76 iff @xmath77 whenever @xmath78 , where @xmath79 is calculated componentwise . this notion of preservation links finitary relations on @xmath41 to finitary operations and is the prime tool for studying the reducts of @xmath37 , and indeed of all other @xmath13-categorical structures , up to primitive positive interdefinability .    for a set of relations @xmath24 , we write @xmath80 for the set of those operations in @xmath48 which preserve all @xmath81 . the operations in @xmath80 are called _ polymorphisms _ of @xmath24 . the following is folklore in universal algebra , see e.g.@xcite . [ prop : polrislocalclone ] @xmath80 is a local clone for all sets of relations @xmath24 . moreover , every local clone is of this form . we have seen how to assign sets of operations to sets of relations ; likewise , we can go the other way . for an operation @xmath73 and a relation @xmath74 , we say that @xmath76 is _ invariant _ under @xmath75 iff @xmath75 preserves @xmath76 . given a set of operations @xmath68 , we write @xmath82 for the set of all relations which are invariant under all @xmath83 . the following is well - known . [ prop : invfisppclosed ] @xmath82 is a pp - closed set of relations for every @xmath68 .    using the galois connection defined by the operators @xmath84 and @xmath85 which link operations and relations , we obtain the following well - known alternative for describing the hull operator which assigns to a set of operations the local clone which this set generates ( confer @xcite ) .    [ prop : localclosure ] let @xmath68 . then @xmath86 . the reader will now expect that our notion of closure for structures @xmath0 , namely closure under primitive positive definitions , will coincide with the closure operator @xmath87 of our galois connection . although this is not true for infinite structures in general , the following theorem from @xcite states that it holds if @xmath0 is not too far from the finite . ( in the following , we often identify structures @xmath0 with their sets of relations , e.g. , when writing @xmath88 . ) [ thm : ppdefinability ] let @xmath0 be @xmath13-categorical . then @xmath89 .    ordering locally closed permutation groups ( just like clones , a permutation group is called locally closed iff it is a closed subset of @xmath48 ) by set - theoretical inclusion , one obtains a complete lattice since arbitrary intersections of local permutation groups are local permutation groups again . similarly , the first - order closed structures on @xmath41 form a complete lattice . using our notation , we can state the well - known connection ( see e.g.  @xcite ) between locally closed permutation groups and first - order closed reducts of @xmath13-categorical structures as follows . [ thm : autinv ] let @xmath0 be an @xmath13-categorical structure . the mapping @xmath90 sending every locally closed permutation group @xmath91 containing the automorphism group @xmath92 of @xmath0 to its set of invariant relations is an antiisomorphism between the lattice of such groups and the lattice of those reducts of @xmath0 which are closed under first - order definitions . utilizing local clones , we obtain an analogous statement to theorem [ thm : autinv ] for reducts up to primitive positive interdefinability . [ thm : galoisconnectionppreductslocalclones ] let @xmath0 be an @xmath13-categorical structure . then we have :    1 . the operator @xmath84 maps every reduct of the first - order expansion of @xmath0 to a local clone above @xmath92 . two reducts @xmath93 are mapped to the same local clone if and only if they are equivalent with respect to primitive positive interdefinability . every local clone above @xmath92 is the polymorphism clone of a reduct of @xmath0 . 4 .   the mappings @xmath84 and @xmath85 are antiisomorphisms beween the lattice of local clones above @xmath92 and the lattice of those reducts of the first - order expansion of @xmath0 which are closed under primitive positive definitions . ( 1 ) : let @xmath1 be the expansion of @xmath0 by all first - order definable relations and let @xmath94 be a reduct of @xmath1 . its is easy to see and well - known that @xmath95 . thus @xmath96 . by proposition [ prop : polrislocalclone ] , @xmath88 is a local clone . + ( 2 ) : if @xmath97 , then @xmath98 by theorem [ thm : ppdefinability ] . on the other hand , if @xmath99 , then @xmath100 thus , @xmath101 by proposition [ prop : localclosure ] , and hence @xmath102 . theorem [ thm : ppdefinability ] then implies @xmath103 . + ( 3 ) : given a local clone @xmath104 , consider @xmath105 . by proposition [ prop : localclosure ] we have @xmath106 . it remains to show that @xmath94 is a reduct of @xmath0 , i.e. , @xmath107 , where @xmath1 is the first - order expansion of @xmath0 . but this is obvious , since @xmath104 implies @xmath108 . + ( 4 ) : by ( 1 ) , ( 2 ) , and ( 3 ) , @xmath84 is a bijective mapping from the pp - closed reducts of @xmath0 onto the local clones containing @xmath92 . it is obvious from its definition that this mapping is antitone . by theorem  [ thm : ppdefinability ] , the restriction of @xmath85 to the local clones containing @xmath92 is the inverse of @xmath84 . the above theorem tells us that classifying reducts of @xmath13-categorical structures up to primitive positive interdefinability really amounts to understanding the lattice of local clones containing its automorphisms ; in our case , since clearly all permutations are automorphisms of @xmath37 , we have to investigate local clones containing all permutations of @xmath41 . via the galois correspondence inv  pol , it is possible to describe the reducts of @xmath37 either on the relational or on the operational side . we will now give the classification on the clone side in as much detail as is gainful at this point of the paper ; since we still want to spare the reader the technical details , we will have to be informal at times . an operation is called _ essentially unary _ iff it depends on at most one of its variables . unary clone _ is a clone all of whose operations are essentially unary . clearly , unary clones are just disguised monoids of transformations on @xmath41 . the first part of our result describes the locally closed unary clones containing the set @xmath109 of all permutations of @xmath41 . [ thm : unaryclones ] let @xmath110 be the lattice of locally closed unary clones containing @xmath109 . then :    1 . @xmath110 is countably infinite . @xmath110 is isomorphic to the lattice of order ideals of a certain partial order @xmath111 on the set of finite increasing sequences of positive natural numbers . 3 .   in particular , both @xmath110 and its inverse order are algebraic ( that is , isomorphic to the subalgebra lattice of an algebra ) , and @xmath110 is a distributive lattice . 4 .   @xmath110 is a well - quasi - order , that is , there exist no infinite descending chains and no infinite antichains in @xmath110 . ( in fact , @xmath110 is a better - quasi - order . ) all elements of @xmath110 are finitely generated over @xmath112 , i.e. , for every @xmath113 there exists a finite set @xmath68 such that @xmath114 .    theorem  [ thm : unaryclones ] will be proven in section [ sect : monoids ] ; it is also there that the partial order @xmath111 is defined . we remark that @xmath110 is an exceptionally well - behaved part of @xmath65 , since @xmath65 is far from satisfying any statement of the theorem : @xmath115 , @xmath65 is not algebraic ( not even upper continuous ) , and @xmath65 does not satisfy any non - trivial lattice identities @xcite .    having described the unary clones , we proceed as follows : consider any unary clone . then this clone has only essentially unary operations , and therefore differs only formally from a monoid @xmath116 of transformations . now it turns out that the set of all local clones @xmath47 which have @xmath116 as their unary fragment , i.e. , which satisfy @xmath117 , forms an interval @xmath118 of the lattice @xmath65 ; intervals of this form are called _ monoidal_. the smallest element of @xmath118 is the unary clone we started this argument with , namely the clone of those essentially unary operations which are `` elements '' of @xmath116 ; this clone is just @xmath119 . the largest element of @xmath118 is called @xmath120 and contains all @xmath121 satisfying @xmath122 whenever @xmath123 . ( this notation is consistent with our previous use of @xmath84 , if one thinks of the elements of @xmath116 as @xmath41-ary relations . ) clearly , the monoidal intervals constitute a natural partition of @xmath65 . our strategy for describing the local clones containing @xmath109 is to determine the monoidal interval @xmath118 for each locally closed monoid @xmath116 containing @xmath109 ; confer figure [ figure : monoidalintervals ] .    ] the following theorem describes @xmath118 for all monoids @xmath116 which contain an operation which is neither injective nor constant . we refer the reader to section  5 , which contains the proof of the theorem , for the definition of quasilinearity . [ thm : monoidalintervalsoflargemonoids ] let @xmath116 be a locally closed monoid containing @xmath109 as well as a non - constant and non - injective operation . then :    1 .   if @xmath124 , then @xmath118 is a chain of order type @xmath125 with largest element @xmath48 . + its smallest element is the clone @xmath126 of all essentially unary operations . + its second smallest element is burle s clone @xmath127 of all operations which are either essentially unary or quasilinear . + for @xmath128 , its @xmath45-th smallest element is the clone @xmath129 of all operations which are either essentially unary or whose range contains less than @xmath45 elements . 2 .   if @xmath130 , then there exists a maximal natural number @xmath131 such that @xmath116 contains all unary operations which take at most @xmath18 values . + if @xmath132 , then @xmath118 has only one element @xmath119 . + otherwise , @xmath118 is a finite chain of length @xmath133 , and : + its smallest element is @xmath119 . + its second smallest element @xmath134 consists of @xmath119 plus all quasilinear operations . + for @xmath135 , its @xmath45-th smallest element @xmath136 consists of @xmath119 plus all operations whose range is smaller than @xmath45 . we now turn to the monoid @xmath137 locally generated by @xmath109 . this , as a quick check shows , consists of all injections in @xmath138 . its monoidal interval is the hardest to understand , and we need a few definitions before stating the theorem describing it . [ def : hornclone ] let @xmath139 be the set of operations which are , up to fictitious variables , injective . [ defn : barclone ] let @xmath140 and let @xmath141 . if there exists an injection @xmath142 such that @xmath143 for all @xmath144 and @xmath145 for all @xmath146 , then we call @xmath75 a _ @xmath18-bar function_. let @xmath147 be the clone generated ( in the sense of  [ sect : notation ] ) by any bar function , i.e. , the smallest local clone containing that bar function and all permutations of @xmath41 ( we will see in section  [ subsect : bar ] that this definition makes sense ) . [ def : injectiveinonedirectionandrichard ] let @xmath148 . we call an operation @xmath73 _ injective in the @xmath149-th direction _ iff @xmath150 whenever @xmath151 and @xmath152 . we say that @xmath73 is _ injective in one direction _ iff there exists @xmath148 such that @xmath75 is injective in the @xmath149-th direction . let @xmath24 be the set of all operations which are injective in one direction . [ def : oddclone ] let @xmath153 any operation satisfying the following :    * @xmath154 , @xmath155 , @xmath156 , and * for all other arguments , the function arbitrarily takes a value that is distinct from all other function values . we set @xmath157 to be the clone generated by @xmath158 , i.e. , the smallest local clone containing @xmath158 and @xmath109 . the following theorem summarizes the highlights of the monoidal interval corresponding to the monoid @xmath137 generated by @xmath109 ; confer figure  [ figure : monoidalintervali ] . more detailed descriptions of the clones of the theorem as well as other clones in that interval can be found in section  [ sect : infiniterangeops ] . [ figure : monoidalintervali ] ]    [ thm : monoidalintervalofs ] the monoid locally generated by @xmath109 is the monoid @xmath137 of injections , and :    1 . the largest element of @xmath159 , @xmath160 , equals @xmath161 , where @xmath162 is the ( binary ) inequality relation . @xmath139 is the unique cover of @xmath163 in @xmath159 , and all elements of @xmath159 except @xmath163 contain @xmath139 . moreover , @xmath139 is generated by any binary injection , and @xmath164 consists of all relations definable by a horn formula . @xmath147 is the unique cover of @xmath139 in @xmath159 , and all elements of @xmath159 except @xmath163 and @xmath139 contain @xmath147 . @xmath165 are incomparable clones in @xmath159 and every clone in @xmath159 is either contained in @xmath157 or contains @xmath24 . the number of elements of @xmath159 containing @xmath24 equals the continuum : in fact , the power set of @xmath13 , ordered by reverse inclusion , has an order embedding into the interval @xmath166 $ ] . in particular , the same holds for the interval @xmath159 , as well as for the set of local clones above @xmath109 . the last statement of theorem  [ thm : monoidalintervalofs ] is among the hardest to prove in this paper , and has strong consequences for pp classification projects , so that it deserves an own corollary . let @xmath0 be any relational structure . then the number of its pp - closed reducts is uncountable . in fact , there exists an order embedding of the power set of @xmath13 into the lattice of pp - closed reducts of @xmath0 . it is for this reason that we can not expect to completely characterize the pp - closed reducts of any relational structure . in our case , we obtain a complete characterization of the closed monoid lattice and of all monoidal intervals except for those corresponding to the monoids @xmath137 and @xmath167 ( see below ) , where we must content ourselves with some insights on the structure of those intervals . it remains to describe the monoidal intervals of those monoids which contain all injections , and some constant operations . clearly , there is only one such monoid , namely the monoid @xmath167 consisting of all constants and all injections . in general , for any set of operations @xmath68 , write @xmath168 for @xmath70 plus all constant operations , and @xmath169 for @xmath70 without all constant operations . it turns out that @xmath170 is a complete sublattice of @xmath171 , as described in the following theorem :    [ thm : monoidalintervalofsplusconst ] let @xmath167 be the monoid of all injective and of all constant operations . then :    1 . if @xmath172 , then @xmath173 is a local clone in @xmath159 . 2 .   @xmath174 and @xmath175 . 3 .   the mapping from @xmath170 into the subinterval @xmath176 $ ] of @xmath159 which sends every clone @xmath47 to @xmath173 is a complete lattice embedding which preserves the smallest and the largest element . if @xmath177 , then @xmath178 iff @xmath179 . 5 .   for all @xmath180 which do not contain @xmath24 , @xmath181 is a local clone in @xmath170 . all clones @xmath47 in @xmath170 are of this form , as @xmath182 . @xmath184 is the unique cover of @xmath185 in @xmath170 . @xmath186 is the unique cover of @xmath184 in @xmath170 . we remark that the mapping that sends every @xmath172 to @xmath173 is not surjective onto the interval @xmath176 $ ] ; see the remark after proposition  [ prop:+notinjective ] . the following sections contain the proof of our result , and of course more detailed definitions of the structures involved . each theorem corresponds to a section : theorems  @xmath187 , @xmath188 , @xmath189 and @xmath190 are proven in sections  @xmath191 , @xmath192 , @xmath193 , and @xmath187 , respectively . in addition to the notation introduced so far , we establish the following conventions . if @xmath121 , since we are only interested in local clones containing @xmath109 , we abuse the notation @xmath194 and write @xmath195 for the local clone generated by @xmath75 together with @xmath109 . for @xmath196 , we say that @xmath75 _ generates _ @xmath62 iff @xmath197 . similarly for @xmath198 and @xmath68 , we say that @xmath70 _ generates _ @xmath62 iff @xmath199 . if @xmath121 , we write @xmath200 for its range .    for a relation @xmath19 , we will usually write @xmath201 instead of @xmath202 for the set of all operations which preserve @xmath19 . if @xmath5 is an @xmath45-tuple , then we refer by @xmath203 to the @xmath149-th component of @xmath5 , for all @xmath148 . we prove theorem  [ thm : unaryclones ] describing all unary clones containing @xmath109 . recall that a unary clone consists only of operations depending on at most one variable , and is therefore a disguised monoid of transformations . for convenience , we therefore only deal with unary operations and monoids in this section . in particular , we adjust the meaning of certain notations for this section : for example , @xmath69 refers to the local _ monoid _ ( rather than the local clone ) generated by a set @xmath204 together with @xmath112 . the various statements of theorem  [ thm : unaryclones ] are obtained in propositions  [ prop : unary : isotoideallattice ] , [ prop : unary : ideallatticewqo ] , [ prop : unary : finitelgenerated ] and corollaries  [ cor : unary : latticedistributive ] and [ cor : unary : cloneswqo ] .    in a first lemma , we officially state what we already observed in the last section , namely that @xmath112 locally generates all unary injections . let @xmath205 be a locally closed monoid . then @xmath116 contains the monoid @xmath137 of all unary injective operations . clearly , on any finite set every injection can be locally interpolated by a suitable permutation . the following lemma implies that except for the full transformation monoid @xmath138 , all closed monoids above @xmath112 consist of the injections plus some finite range operations . [ lem : unary : noninjectiveinfrangegeneratesall ] let @xmath206 have infinite image , and assume it is not injective . then @xmath75 generates all unary operations . we skip the fairly easy proof , and refer the reader to the very similar ( first part of the ) proof of lemma  [ lem : unary : kerneltuplesorderisgeneratingorder ] . we thus wish to know , given a finite range operation , which other finite range operations it generates . for that , we need the following concept .    let @xmath206 have finite range , and write @xmath207 . enumerate the kernel classes of @xmath75 by @xmath208 in such a way that their sizes are increasing . the _ kernel tuple _ @xmath209 of @xmath75 is the @xmath45-tuple @xmath210 . note that the last entry of a kernel tuple @xmath211 always equals @xmath13 since @xmath75 must have at least one infinite kernel class . having assigned a finite sequence with positive values in @xmath125 to every finite range operation , we are ready to order such sequences and give the definition of @xmath212 . * let @xmath213 . for @xmath214 and @xmath215 we write @xmath216 iff @xmath217 and the following holds : there exists a partition @xmath218 of @xmath219 into @xmath18 classes such that @xmath220 for all @xmath221 . * we write @xmath222 for the partial order of finite increasing sequences of non - zero elements of @xmath125 ordered by @xmath223 . * we write @xmath212 for the partial order of the finite increasing sequences of positive natural numbers ( not of values in @xmath125 ! ) ordered by @xmath223 . observe that for finite increasing sequences @xmath224 of the same length we have @xmath216 iff @xmath225 for all @xmath148 . the following lemma justifies our definition of @xmath223 . [ lem : unary : kerneltuplesorderisgeneratingorder ] let @xmath226 have finite range . then @xmath75 generates @xmath62 iff @xmath227 . assume first that @xmath227 . let @xmath211 have length @xmath45 and @xmath228 have length @xmath217 . if @xmath229 , then @xmath230 for all @xmath148 . it is then not hard to see that for any finite set @xmath231 , there exist permutations @xmath232 such that @xmath233 agrees with @xmath62 on @xmath63 . if @xmath234 , then let @xmath235 be the partition provided by the definition of @xmath223 . enumerate the kernel classes of @xmath75 by @xmath208 and in such a way that @xmath236 contains @xmath237 elements , for all @xmath238 . now take any @xmath239 which are distinct but equivalent with respect to the partition @xmath235 . by composing @xmath75 with a permutation , we may assume that @xmath75 maps the classes @xmath240 and @xmath236 into the class @xmath241 , and all other classes into classes @xmath242 in such a way that no two classes are mapped into the same class . then @xmath243 is a function with @xmath244 values in its range , and @xmath245 . proceeding like this , we arrive after @xmath246 steps at an operation @xmath247 which takes @xmath18 values and which satisfies @xmath248 for all @xmath221 . thus we are back in the case @xmath229 , and the proof of this direction of the lemma is finished . for the other direction , assume that @xmath75 generates @xmath62 . let @xmath249 be as before . since the local clone generated by @xmath75 is the topological closure of the set of term operations generated by @xmath75 , we have that for every @xmath250 , there exists a term @xmath251 consisting of permutations and @xmath75 which agrees with @xmath62 on the finite set @xmath252 . we can write each @xmath251 as @xmath253 , where @xmath254 consists of permutations and @xmath75 , and @xmath255 is a permutation . thus in every term @xmath251 , certain classes of @xmath75 are joined by the application of @xmath254 ( and shifted by @xmath255 , which we do not care about for the moment ) ; since there are only finitely many possibilities of joining classes of @xmath75 , there is one constellation which appears for infinitely many @xmath256 . since @xmath257 implies that @xmath258 agrees with @xmath62 on @xmath252 , by replacing terms we may assume that the same classes are joined for all @xmath250 . naturally , this partition of classes induces a partition @xmath259 on @xmath219 via @xmath211 . if @xmath260 are equivalent modulo the kernel of @xmath62 , then the kernel classes of @xmath75 containing @xmath261 and @xmath262 , respectively , are equivalent with respect to the partition @xmath259 . on the other hand , if @xmath260 are not in the same class of @xmath62 , then @xmath261 and @xmath262 will not lie in equivalent @xmath75-classes . thus , taking @xmath256 large enough so that @xmath252 meets all kernel classes of @xmath62 , we can assign to every @xmath62-class ( with , say , index @xmath263 ) an equivalence class @xmath264 in an injective way ; in particular , @xmath265 . for infinitely many @xmath256 , this assignment is the same ; again , by replacing terms where necessary , we may assume it is always the same . since for large enough @xmath256 arbitrarily large parts of the kernel classes of @xmath62 are hit , we must have @xmath266 for all @xmath263 , where @xmath267 is the class assigned to @xmath268 . by joining some classes @xmath269 , we can obtain @xmath270 without changing the latter fact . [ lem : unary : unboundedfiniterange ] let @xmath204 . if there is no finite bound to the sizes of the ranges of the finite range operations in @xmath70 , then @xmath70 generates @xmath138 . let @xmath75 be any finite range operation , and let @xmath231 be finite . then there exists a finite range function @xmath62 which agrees with @xmath75 on @xmath63 and whose kernel sequence @xmath228 has only one entry equal to @xmath13 . now there exists a finite range operation @xmath271 in @xmath70 with @xmath272 , so @xmath62 is generated by @xmath70 . this proves that @xmath75 is generated by @xmath70 , and hence @xmath70 generates all finite range operations . clearly , any operation in @xmath138 can be interpolated on any finite set by a finite range operation , which implies our assertion . the following is a consequence of lemma  [ lem : unary : kerneltuplesorderisgeneratingorder ] ; it says that if finitely many finite range operations join forces , the joint generating power is not more than the sum of the generating powers of the single operations . [ prop : unary : closure ] let @xmath204 be finite . then @xmath273 . the non - trivial direction is to show @xmath274 . if @xmath275 is any term made of operations in @xmath70 , then it is of the form @xmath276 , where @xmath277 is a term and @xmath83 . clearly , @xmath278 , implying @xmath279 . thus , @xmath280 contains all terms that can be built from @xmath70 . this implies that the union is a monoid . being a finite union of ( topologically ) closed sets @xmath280 is itself closed , and hence contains even @xmath69 . we now assign ideals of @xmath212 to local monoids containing @xmath112 .    for a local monoid @xmath205 , we set @xmath281 for a sequence @xmath282 , write @xmath283 for the sequence obtained by gluing @xmath13 to the end of @xmath284 . now set @xmath285    by lemma  [ lem : unary : kerneltuplesorderisgeneratingorder ] , @xmath286 is always an ideal of @xmath212 . conversely , we show in the following how to get closed monoids from ideals of @xmath212 . [ defn : unary : limit ] let @xmath141 and let @xmath287 be an ascending sequence of @xmath18-tuples in @xmath222 . we write @xmath288 for the smallest ( according to @xmath223 ) @xmath18-tuple @xmath284 in @xmath222 satisfying @xmath289 for all @xmath290 . + for an ideal @xmath291 , we let @xmath292 contain all operations in @xmath138 which are either injective , or which have finite range and whose kernel sequence is a limit of an ascending sequence of @xmath18-tuples of the form @xmath293 , where @xmath294 . [ lem : unary : moniismonoid ] let @xmath291 be an ideal . then @xmath292 is a local monoid containing @xmath112 . observe that if @xmath295 is a finite range function , and if @xmath296 is a finite range function such that @xmath227 , then @xmath292 contains also @xmath62 . the range of @xmath75 have @xmath45 elements , let the range of @xmath62 have @xmath217 elements , and let @xmath235 be the partition of @xmath219 provided by the definition of @xmath223 . a quick check shows that we may assume @xmath297 . let @xmath298 be the sequence of @xmath299-tuples in @xmath300 such that @xmath301 . set @xmath302 , for all @xmath303 and all @xmath304 . since @xmath305 , all @xmath306 are elements of @xmath300 , provided they are actually increasing tuples . fixing @xmath149 , define inductively @xmath307 , for all @xmath304 . it is not hard to see that the @xmath308 are in @xmath300 , too , and that @xmath228 is the limit of the increasing sequence @xmath309 , so @xmath310 .    using lemma  [ lem : unary : kerneltuplesorderisgeneratingorder ] and proposition  [ prop : unary : closure ] , one now readily derives from this that @xmath292 is indeed a monoid . it remains to show that @xmath292 is local . let @xmath206 , and assume it can be interpolated on all finite sets by operations from @xmath292 ; assume also that it is not injective . if @xmath75 has infinite range , then @xmath292 must contain non - injections of arbitrarily large finite range , which in turn implies that @xmath300 contains tuples of arbitrary length . the definition of @xmath212 then shows that @xmath311 , a contradiction . thus , all non - injections in the local closure of @xmath292 have finite range . assume again that @xmath75 is such a non - injection , and assume @xmath211 has length @xmath18 . fix for every set @xmath312 an operation @xmath313 which agrees with @xmath75 on this set . from some @xmath45 on , the @xmath314 will have to take at least @xmath18 values , so we take the liberty of assuming that all @xmath314 have this property . an easy manipulation of the @xmath314 using the fact that @xmath310 whenever @xmath315 allows us to assume that every @xmath314 takes exactly @xmath18 values and that @xmath316 for all @xmath290 . by thinning out the sequence , we may also assume that the kernel sequences of the @xmath314 are increasing with respect to @xmath223 . we then have @xmath317 . now replace each @xmath18-tuple @xmath318 by a @xmath319-tuple @xmath320 with @xmath321 in such a way that @xmath322 and that the sequence @xmath287 is still ascending . clearly , @xmath323 for all @xmath290 , and so @xmath324 implies @xmath295 . hence , @xmath292 is locally closed . [ prop : unary : isotoideallattice ] the mapping @xmath325 is an isomorphism from the lattice @xmath110 of locally closed monoids that contain @xmath112 onto the lattice of ideals of @xmath212 .    that @xmath286 is an ideal of @xmath212 for all monoids @xmath116 follows directly from lemma  [ lem : unary : kerneltuplesorderisgeneratingorder ] . from lemma  [ lem : unary : unboundedfiniterange ] we know that @xmath326 iff @xmath124 , and obviously @xmath327 iff @xmath116 contains only injections . we have seen in lemma  [ lem : unary : moniismonoid ] that for any proper ideal @xmath300 of @xmath212 , @xmath292 is a local monoid , and a straightforward verification shows @xmath328 , thus @xmath329 is onto . also , an easy check using lemma  [ lem : unary : kerneltuplesorderisgeneratingorder ] shows that @xmath330 for every local monoid which contains @xmath109 and all of whose non - injections have finite range , so @xmath329 is injective . it is obvious that both @xmath329 and @xmath331 are order - preserving . recall that a lattice is _ algebraic _ iff it is isomorphic to the subalgebra lattice of an algebra . [ cor : unary : latticedistributive ] the lattice @xmath110 of local monoids above @xmath112 is distributive . moreover , @xmath110 and its dual order are algebraic .    by the preceding proposition , @xmath110 is the lattice of ideals of a partial order . the assertions then follow from  @xcite . a partial order is called a _ well - quasi - order _ iff there are no infinite descending chains and no infinite antichains in it . + we call a sequence @xmath332 in a partial order with order relation @xmath333 _ bad _ iff for no @xmath334 we have @xmath335 .    a standard application of the infinite ramsey s theorem shows that a partial order is well - quasi - ordered iff it contains no bad sequence ( confer e.g.  @xcite ) . [ lem : kerneltupleswellfoundednoinfantichain ] the set of finite sequences with values in @xmath125 ordered by @xmath223 is a well - quasi - order . in particular , its suborders @xmath222 and @xmath212 are well - quasi - orders . assume that @xmath332 were a bad sequence of such finite sequences . for every @xmath290 , let @xmath336 be the number of occurrences of @xmath13 in the tuple @xmath337 . if the sequence @xmath338 were unbounded , then we could find @xmath290 such that @xmath336 is greater than the length of @xmath339 , implying @xmath340 , a contradiction . thus , we can thin out the sequence in such a way that all @xmath336 are equal . let @xmath341 be the tuple obtained from @xmath337 by leaving away the @xmath336 components equal to @xmath13 , for all @xmath290 . clearly , the @xmath341 form a bad sequence of tuples with values in @xmath13 . now if the sequence of lengths of the @xmath341 were unbounded , then we could find some @xmath303 such that the length of @xmath342 is greater than the sum of all components of @xmath343 , hence @xmath344 , a contradiction . thin out the sequence @xmath345 is such a way that all tuples have the same length @xmath18 . now for all @xmath346 , we thin out our sequence so that the sequence consisting of the @xmath347-th component of the @xmath341 is increasing ; we can do this since @xmath13 is well - ordered . the remaining sequence of @xmath341 is ascending , a contradiction .    in general , the ideal lattice of a given well - quasi - order need not be a well - quasi - order . certain well - quasi - orders which satisfy a certain strong combinatorial property and which are called _ better - quasi - orders _ , however , do have the property that their ideal lattice is well - quasi - ordered . although giving the definition of a better - quasi - order ( see e.g.  @xcite ) would be out of scope of the present paper , we remark that it follows from the basic theory of better - quasi - orders that our well - quasi - order @xmath212 is in fact a better - quasi - order ( as kruskal states in  @xcite : `` all naturally known well - quasi - ordered sets which are known are better - quasi - ordered . '' ) . therefore , the lattice of ideals of @xmath212 is a well - quasi - order ( and , in fact , even a better - quasi - order as well ) . in order to spare the reader the pain of reading the definition of a better - quasi - order , we prove the following    [ prop : unary : ideallatticewqo ] the lattice of ideals of @xmath212 is a well - quasi - order . suppose that @xmath348 were a bad sequence of ideals . by taking away the first element of the sequence , we may assume that @xmath349 for all @xmath290 . consider for all @xmath290 the set @xmath350 consisting of @xmath351 plus all limits of ascending chains of tuples of the same length in @xmath351 ( as in definition  [ defn : unary : limit ] ) : so @xmath352 for all @xmath290 . in @xmath350 , every chain is bounded from above : if @xmath353 is a chain in @xmath350 , then there is some @xmath354 such that all tuples in @xmath353 have length at most @xmath18 ; for otherwise , @xmath351 contains sequences of arbitrary length , implying @xmath355 contrary to our assumption . but if the elements of @xmath353 all have length at most @xmath18 , then @xmath353 is bounded by construction of @xmath350 ( i.e. , adding the limits of ascending chains ) .    applying zorn s lemma , we get that every element of @xmath351 is below some maximal tuple of @xmath350 . by construction of @xmath350 , every tuple in @xmath212 which is below a maximal tuple of @xmath350 also is an element of @xmath351 . the maximal elements of @xmath350 form an antichain with respect to @xmath223 . by lemma  [ lem : kerneltupleswellfoundednoinfantichain ] , the set of sequences in @xmath125 , equipped with the order @xmath223 , is a well - quasi - order . in particular , the antichain of maximal elements of @xmath350 is finite . for every @xmath356 , there exists a tuple in @xmath357 . thus , there is a maximal tuple of @xmath358 which is not in @xmath350 . we can thin out our sequence of @xmath351 so that this witnessing maximal tuple is the same for all @xmath356 ; denote it by @xmath359 . now we do the same for @xmath360 and all @xmath361 , obtaining a maximal tuple @xmath362 which is not in any @xmath350 with @xmath361 . we continue inductively in this fashion , obtaining a sequence @xmath287 . by construction , this sequence is a bad sequence in the order of finite @xmath363-valued sequences with @xmath223 , a contradiction . [ cor : unary : cloneswqo ] the lattice of local monoids above @xmath112 is well - quasi - ordered . [ prop : unary : finitelgenerated ] every local monoid @xmath116 above @xmath112 is finitely generated over @xmath112 , i.e. , there exists a finite @xmath364 such that @xmath365 . moreover , the number of such monoids is countable . if @xmath124 , then it is generated by any non - injective operation with infinite range , by lemma  [ lem : unary : noninjectiveinfrangegeneratesall ] . assume henceforth that @xmath116 contains only injections and finite range operations . set @xmath366 to consist of all kernel sequences of operations in @xmath116 . by local closure and what is by now a standard argument , one sees that every chain in @xmath366 has an upper bound in @xmath366 ( confer e.g.  the proof of lemma  [ lem : unary : moniismonoid ] ) . hence , zorn s lemma implies that every element of @xmath366 is below a maximal element of @xmath366 . the maximal elements of @xmath366 form an antichain with respect to @xmath223 , and therefore are finite in number by lemma  [ lem : kerneltupleswellfoundednoinfantichain ] . pick for each maximal tuple one corresponding operation in @xmath116 . the set @xmath70 of operations thus chosen is as desired , by lemma  [ lem : unary : kerneltuplesorderisgeneratingorder ] . the above argument shows that every local monoid containing @xmath112 is determined by a finite set of finite sequences with values in @xmath125 . there are only countably many possibilities for such finite sets , so the number of such monoids is countable . having understood the structure of the lattice of local monoids containing @xmath112 , we move on to describe the monoidal interval corresponding to each such monoid . in this section , we will prove theorem  [ thm : monoidalintervalsoflargemonoids ] , which deals with those monoids which contain a non - constant and non - injective operation . an operation @xmath75 on a set @xmath12 is called _ essential _ iff it is not essentially unary , i.e. , it depends on at least two of its variables . we will see that except for @xmath48 , all clones whose unary fragment contains a non - constant and non - injective operation contain only essential operations with finite range , and none with infinite range ; hence the title of this section . it turns out that the monoidal intervals of the monoids under consideration here are all chains which can be described nicely . this is essentially a consequence of a theorem from  @xcite for clones on finite sets , and the power of local closure . in order to state that theorem , we need the following definition . let @xmath12 be any set . we call an @xmath45-ary operation @xmath75 on @xmath12 _ quasilinear _ iff there exist functions @xmath367 and @xmath368 such that @xmath369 , where @xmath370 denotes the sum modulo @xmath371 .    [ thm : s5:haddad - rosenberg ] let @xmath12 be a finite set of at least three elements and let @xmath75 be an essential operation on @xmath12 . set @xmath372 . then , writing @xmath373 for the set of all permutations on @xmath12 , we have :    * if @xmath374 , then @xmath75 together with @xmath373 generate all operations on @xmath12 which take at most @xmath18 values . * if @xmath375 and @xmath75 is not quasilinear , then @xmath75 together with @xmath373 generate all operations on @xmath12 which take at most two values . * if @xmath375 , @xmath75 is quasilinear , and @xmath376 is odd , then @xmath75 together with @xmath373 generate all quasilinear operations on @xmath12 . observe that there is no such thing as local interpolation on finite @xmath12 , so `` generates '' in the theorem refers to the term closure . the following lemma is the infinite local version of this theorem . [ lem : s5:haddadrosenberg : forinfinite ] let @xmath73 be essential , and assume that @xmath377 , where @xmath378 .    1 . if @xmath374 , then @xmath75 generates all operations which take at most @xmath18 values . if @xmath375 and @xmath75 is not quasilinear , then @xmath75 generates all functions which take at most @xmath18 values . 3 .   if @xmath375 and @xmath75 is quasilinear , then @xmath75 generates all quasilinear operations . ( 1 ) : let any operation @xmath62 on @xmath379 be given . it suffices to show that for every @xmath290 , @xmath75 generates an operation @xmath271 which agrees with @xmath62 on @xmath312 . choosing @xmath45 large enough , we may assume that the ranges of both @xmath75 and @xmath62 are contained in @xmath312 . also , again by making @xmath45 larger , we may assume that the restriction @xmath380 of @xmath75 to @xmath312 is essential and takes @xmath18 values . then @xmath380 is an essential operation on @xmath312 which takes @xmath18 values , and hence generates all such functions by theorem  [ thm : s5:haddad - rosenberg ] . in particular , @xmath380 generates a function @xmath381 which agrees with @xmath62 on @xmath312 . the permutations which appear in the term which represents @xmath381 can be extended to @xmath9 by the identity ; occurrences of @xmath380 can be replaced by @xmath75 . the resulting term @xmath271 is a function on @xmath9 which still agrees with @xmath62 on @xmath312 . + ( 2 ) : again , let @xmath62 and @xmath45 be given . enlarge @xmath45 as before , if necessary , so that the restriction of @xmath75 to @xmath312 is not quasilinear . now we argue as in the preceding proof . + ( 3 ) : the proof works as before ; @xmath45 only has to be chosen odd in order to allow application of theorem  [ thm : s5:haddad - rosenberg ] .    with the preceding lemma , we see that it is quite easy to understand what happens when we add an essential finite range operation to a monoid . we will now show that to the monoids relevant for this section , we in fact can not add an essential infinite range operation without generating @xmath48 . to establish this , we distinguish between those operations which preserve the binary inequality relation @xmath162 , and those which do not . the latter case can be eliminated right away :    [ prop : s5:essentialwithinfiniteimagepreservesneq ] let @xmath75 be an essential operation with infinite image . then @xmath75 preserves @xmath162 , or it generates all operations .    the proposition will follow from the following lemma . [ lem : s5:constantpaste ] let @xmath73 have infinite image , and assume it does not preserve @xmath162 . then @xmath75 generates a unary non - injective function that has infinite range .    before proving the lemma we show how the proposition follows from it :    by lemma  [ lem : s5:constantpaste ] , @xmath75 generates a unary non - injective operation with infinite range ; lemma  [ lem : unary : noninjectiveinfrangegeneratesall ] then implies that @xmath75 generates all unary operations . let @xmath382 be arbitrary . we can find a unary finite range operation @xmath383 such that @xmath384 is essential and takes at least @xmath18 values . by lemma  [ lem : s5:haddadrosenberg : forinfinite ] , this implies that @xmath75 generates all operations which take not more than @xmath18 values . since @xmath18 was arbitrary and by local interpolation , this implies that @xmath75 generates @xmath48 . we only have to prove something if @xmath75 is essential , for @xmath75 is itself a unary non - injective operation with infinite range otherwise . we also assume @xmath75 to depend on all of its variables . + _ case 1 : _ there exist injective functions @xmath385 such that @xmath386 is injective . choose @xmath387 infinite such that @xmath388 and @xmath389\cup\ldots \cup g_n[s])$ ] are infinite . since @xmath75 does not preserve @xmath162 , there exist @xmath390 such that @xmath391 for all @xmath148 and such that @xmath392 . we may assume that those values are not in @xmath393\cup\ldots\cup g_n[s]$ ] . for all @xmath148 , set @xmath394 on @xmath395 and @xmath396 and @xmath397 . write @xmath398 . on @xmath399 , @xmath400 is a function with infinite range which is not injective . furthermore , the @xmath401 can be extended to permutations on @xmath9 since they are injective and have co - infinite domains and ranges . this completes the first case . + _ case 2 : _ @xmath386 is not injective for all injective @xmath402 . since @xmath75 is not constant , there exist injections @xmath403 such that @xmath404 is not constant . by assumption for this case we have that @xmath404 is not injective . thus , @xmath404 generates a function @xmath405 which is constant except for one argument , at which it takes another value . to see this , just observe that for such an @xmath277 , the kernel sequence @xmath406 satisfies @xmath407 for any non - constant @xmath408 , and apply lemma [ lem : unary : kerneltuplesorderisgeneratingorder ] . consider arbitrary @xmath385 such that @xmath386 is injective . such functions exist since @xmath75 has infinite range . pick an infinite @xmath387 on which each @xmath409 is either injective or constant . observe that it is impossible that all those restrictions of @xmath409 are constant . say the restriction of @xmath409 to @xmath395 is constant with value @xmath410 for @xmath221 , where @xmath411 . + since @xmath75 depends on its first variable , there exist @xmath412 and @xmath413 such that @xmath414 . for otherwise the value of @xmath75 is determined by the values of the arguments @xmath415 , contradicting that @xmath75 depends on @xmath416 . choose @xmath417 such that @xmath418 is distinct from both @xmath419 and @xmath420 ; this is possible as @xmath421 takes infinitely many values . set @xmath422 and @xmath423 if @xmath424 , for @xmath221 . let moreover @xmath425 , and @xmath426 if @xmath427 , for all @xmath428 . all @xmath429 and @xmath430 are generated by the two - valued function @xmath277 and hence by @xmath75 . set @xmath431 . we have that @xmath432 and @xmath433 and @xmath434 are pairwise distinct ; also , @xmath435 has finite range . hence , @xmath75 generates a unary function @xmath435 that takes exactly three values . + pick @xmath151 such that @xmath436 for all @xmath148 and such that @xmath437 . for all @xmath221 , let @xmath438 satisfy @xmath439 , @xmath440 , and @xmath441 for all @xmath442 . clearly , @xmath443 is generated by the unary function @xmath435 with three values , and hence also by @xmath75 . for all @xmath428 , let @xmath444 be any permutation that maps @xmath445 to @xmath203 and @xmath446 to @xmath447 . now we set @xmath448 and have that @xmath449 and @xmath450 takes infinitely many values . we are thus left with essential infinite range operations which do preserve the inequality relation . the crucial theorem here has been shown in  @xcite . [ thm : s5:bininj ] every essential operation @xmath451 generates a binary injective operation . able to produce a binary injection , we use this operation in order to enlarge ranges of unary operations :    [ lem : s5:binaryinjectionplusfiniterange ] let @xmath140 be injective , and let @xmath452 be a non - constant function with finite range . then @xmath75 and @xmath62 together generate @xmath48 .    write @xmath453 . either @xmath62 is itself ( essentially ) unary , or it generates a non - constant unary operation which takes @xmath18 values by lemma  [ lem : s5:haddadrosenberg : forinfinite ] . pick such a unary operation @xmath454 , and set @xmath455 . the operation @xmath456 takes @xmath457 values . hence , @xmath75 and @xmath62 together also generate a unary operation @xmath458 which takes @xmath459 values . continuing in this fashion , and since @xmath460 , we obtain unary operations of all finite ranges , and hence also @xmath138 by lemma  [ lem : unary : kerneltuplesorderisgeneratingorder ] . but clearly , for every operation @xmath461 , there exists a unary @xmath462 such that @xmath463 . thus , since @xmath271 was arbitrary , @xmath75 and @xmath62 generate @xmath464 , and in turn also @xmath48 , as it is well - known and easy to see that @xmath465 . we are thus ready to prove theorem  [ thm : monoidalintervalsoflargemonoids ] . we are given a monoid @xmath116 which contains an operation which is neither constant nor injective . it follows from lemma  [ lem : s5:binaryinjectionplusfiniterange ] that no clone properly contained in @xmath48 and containing @xmath116 can have a binary injection . therefore , by theorem  [ thm : s5:bininj ] , it can not have any essential operation which preserves the inequality relation . nor can it contain an essential operation with infinite range which does not preserve the inequality , by proposition  [ prop : s5:essentialwithinfiniteimagepreservesneq ] . thus , it can not contain any essential operation with infinite range . we now distinguish the two cases of the theorem : + ( 1 ) : if @xmath124 , then the only clones above @xmath138 can be the ones mentioned in the theorem , by lemma  [ lem : s5:haddadrosenberg : forinfinite ] . that these sets of operations are actually clones is a straightforward verification and left to the reader . + ( 2 ) : if @xmath466 , then there is a largest natural number @xmath18 such that @xmath116 contains all unary operations which take at most @xmath18 values ; this follows from lemma  [ lem : unary : unboundedfiniterange ] . if @xmath132 , then no clone having @xmath116 as its unary fragment can have an essential operation , since this operation would generate all quasilinear operations by lemma  [ lem : s5:haddadrosenberg : forinfinite ] , and hence all unary operations with at most two values . consider thus the case @xmath467 . again by lemma  [ lem : s5:haddadrosenberg : forinfinite ] , the only clones in @xmath118 can be @xmath119 , @xmath134 and the @xmath468 , where @xmath469 . it is easy to verify that these are indeed clones . this section deals with the monoidal interval of @xmath159 , the monoid of all injections , and contains the proof of theorem  [ thm : monoidalintervalofs ] . before we start with an outline of this section , let us observe that as a straightforward verification shows , the largest element of this interval , @xmath160 , equals @xmath470 ( this is statement ( 1 ) of theorem  [ thm : monoidalintervalofs ] ) . in particular , all operations of clones in this interval have infinite range ; hence the title of this section . in subsection  [ subsect : horn ] we prove that @xmath139 is the unique cover above @xmath471 in @xmath159 , and that @xmath164 is the set of all relations definable by a horn formula ( theorem  [ thm : monoidalintervalofs ] , part ( 2 ) ) . in subsection  [ subsect : bar ] we prove that @xmath147 is the unique cover of @xmath139 in @xmath159 ( theorem  [ thm : monoidalintervalofs ] , part ( 3 ) ) .    in subsection  [ subsect : bar - odd ] we present an infinite strictly decreasing chain of clones that contain @xmath147 , and are contained in @xmath157 . to this end , we also give relational descriptions of @xmath147 and of @xmath157 .    in subsection [ subsect : richard ] we show that @xmath24 and @xmath157 are incomparable , and that every clone in @xmath159 is either contained in @xmath157 or contains @xmath24 ( theorem  [ thm : monoidalintervalofs ] , part ( 4 ) ) .    in subsection  [ subsect : richardsmanyfriends ] we show that the power set of @xmath13 embeds into the intervals of those clones in @xmath159 that contain @xmath24 ; in particular , the size of this interval equals the continuum ( theorem  [ thm : monoidalintervalofs ] , part ( 5 ) ) .      in this subsection we show that @xmath163 has the cover @xmath139 in the monoidal interval @xmath159 . recall from definition  [ def : hornclone ] that @xmath139 is the clone consisting of all operations @xmath75 that are essentially injective , i.e. , all operations @xmath75 that are the composition @xmath472 of an injective operation @xmath149 with projections @xmath473 ( it is straightforward to verify that this set of operations indeed forms a locally closed clone ) . the clone @xmath139 is also called the _ horn clone _ ; the reason for this name will be given in proposition  [ prop : hornchar ] . let @xmath474 be a quantifier - free first - order formula where all atomic subformulas are of the form @xmath475 . then @xmath474 is called _ horn _ if @xmath25 is in conjunctive normal form ( henceforth abbreviated cnf ) and each clause in @xmath474 contains at most one positive literal . let @xmath476 be a formula in cnf . we call @xmath25 _ reduced _ iff it is not logically equivalent to any of its subformulas , i.e. , there is no formula @xmath477 obtained from @xmath25 by deleting literals or clauses such that @xmath478 iff @xmath479 for all @xmath480 . clearly , for every formula @xmath25 in cnf there exists a logically equivalent reduced formula .    in the following proposition , the equvalence of ( 1 ) and ( 7 ) proves item ( 2 ) of theorem  [ thm : monoidalintervalofs ] , stating that the horn clone is the unique cover of @xmath163 in @xmath159 . moreover , items ( 5 ) and ( 6 ) provide finite relational generating systems of @xmath164 , and ( 2 ) provides a finite operational generating system ( in fact : a continuum of such systems ) of @xmath139 . recall that a formula is _ horn _ iff it is in conjunctive normal form and each of its clauses contains at most one positive literal . item ( 4 ) gives us a syntactical description of the formulas defining relations in @xmath164 . [ prop : hornchar ] for all relations @xmath19 with a first - order definition in @xmath481 the following are equivalent .    1 . @xmath19 is preserved by an essential operation that preserves @xmath162 . @xmath19 is preserved by a binary injective operation . 3 .   every reduced definition of @xmath19 is horn . 4 .   @xmath19 has a horn definition . @xmath19 has a pp definition in @xmath482 where @xmath483 6 . @xmath19 has a pp - definition in @xmath484 where @xmath485 7 . @xmath19 is preserved by @xmath139 .    the implication from ( 1 ) to ( 2 ) is theorem  [ thm : s5:bininj ] .    for the implication from ( 2 ) to ( 3 ) , suppose that @xmath474 is a reduced formula that defines @xmath19 but is not horn . then there exists a clause @xmath477 of @xmath474 which contains two equalities @xmath486 and @xmath487 . construct @xmath488 from @xmath477 by removing the equation @xmath486 , and @xmath489 by removing @xmath487 . since @xmath474 is reduced , there exist @xmath490 such that @xmath478 but not @xmath491 , and @xmath492 but not @xmath493 . clearly , @xmath494 , @xmath495 , @xmath496 , and @xmath497 . set @xmath498 , where @xmath75 is the binary injection preserving @xmath19 . then @xmath499 , @xmath500 , and in fact @xmath501 does not hold . hence @xmath19 is not preserved by @xmath75 , a contradiction . the implication from ( 3 ) to ( 4 ) is trivial .    for the implication from ( 4 ) to ( 5 ) , let @xmath474 be a horn formula . it suffices to show that all clauses @xmath477 of @xmath474 have a pp definition in @xmath502 . if @xmath477 is of the form @xmath503 , consider the following pp formula . @xmath504 assume that @xmath505 for all @xmath506 . in this case , the pp formula implies that @xmath507 , and hence also implies that @xmath508 . now , if @xmath509 for some @xmath506 , then for all choices of values for the other free variables the formula can be satisfied by setting @xmath510 to values that are distinct from all other values . hence , the formula is a pp definition of @xmath477 in @xmath511 . if @xmath477 does not contain a positive literal , consider the formula @xmath512 , which is equivalent to @xmath477 ( we assume that @xmath268 and @xmath513 are fresh variables ) . we have seen above that the term in brackets is equivalent to a pp formula . it is then straightforward to rewrite the whole expression as a pp formula .    for the implication from ( 5 ) to ( 6 ) , it suffices to show that @xmath300 and @xmath162 have pp definitions in @xmath484 . for @xmath162 , this is obvious . to express @xmath514 , consider the pp formula @xmath515 if @xmath516 , the variables @xmath517 must denote the same value , and hence the formula implies @xmath518 . if @xmath519 , then for all choices of values for @xmath520 and @xmath521 it is possible to select values for @xmath517 that satisfy the formula . hence , the above formula is a pp definition of @xmath300 in @xmath484 . it is straightforward to verify the implication from ( 6 ) to ( 7 ) , because @xmath522 is preserved by projections and by injective operations . the implication from ( 7 ) to ( 1 ) is immediate , since every at least binary injective operation is essential and has infinite image . we show that the bar clone @xmath147 ( confer definition  [ defn : barclone ] ) is the smallest clone below @xmath470 that strictly contains @xmath139 , thus proving item ( 3 ) of theorem  [ thm : monoidalintervalofs ] . a smallest non - empty @xmath18-ary relation that is preserved by all permutations of @xmath523 is called an _ orbit of @xmath18-tuples_. it is clear that every relation that is preserved by all permutations is the union of a finite number of orbits of @xmath18-tuples . the following lemma will be useful here and in the following subsections , and a proof can be found in  @xcite . [ lem : op - arity ] let @xmath19 be a @xmath18-ary relation that consists of @xmath54 orbits of @xmath18-tuples . then every operation @xmath75 that violates @xmath19 generates an @xmath54-ary operation that violates @xmath19 . the relation @xmath522 has been introduced in proposition  [ prop : hornchar ] ; we recall it for the convenience of the reader : @xmath522 is the four - ary relation @xmath524 . [ lem : binabovehorn ] let @xmath525 . then @xmath75 generates a _ binary _ operation that violates @xmath522 . the operation @xmath75 must violate the relation @xmath522 . indeed , otherwise we would have @xmath526 , since all relations in @xmath164 have a primitive positive definition in @xmath484 by proposition  [ prop : hornchar ]  a contradiction . since @xmath522 consists of two orbits of tuples , lemma  [ lem : op - arity ] implies that @xmath75 generates a binary operation that violates @xmath522 . clearly , the binary operation from lemma  [ lem : binabovehorn ] is essential and not injective . recall from definition  [ defn : barclone ] that a binary function @xmath75 is called a @xmath18-bar function iff there exists an injection @xmath142 such that @xmath143 for all @xmath144 and @xmath145 for all @xmath146 ; recall also that @xmath147 is the clone generated by any bar function . we show next that @xmath147 is well - defined . clearly , for fixed @xmath141 , the @xmath18-bar functions generate each other . it is also easy to see that if @xmath527 , then any @xmath18-bar function generates all @xmath45-bar functions . [ lem : barfunctionsequvalent ] let @xmath141 , and let @xmath140 be a @xmath18-bar function and @xmath461 be a @xmath528-bar function . then @xmath75 generates @xmath271 . let @xmath75 be a @xmath18-bar function , and @xmath62 be a variant of the @xmath446-bar which satisfies @xmath529 for all @xmath530 , and which is injective otherwise . clearly , @xmath62 is generated by @xmath75 . set @xmath531 . let @xmath532 . then @xmath533 for all @xmath530 since @xmath534 for all @xmath535 . also , @xmath536 for all @xmath537 . moreover , if @xmath538 and @xmath539 and @xmath540 , then it is easy to see that @xmath541 . hence , @xmath271 is essentially a @xmath528-bar function , the only difference to a @xmath528-bar function being the value of @xmath542 , which can be undone by composing any permutation which swaps @xmath133 and @xmath543 with @xmath271 . the next lemma characterizes the binary operations in @xmath147 . recall the definition of  injective in one direction " from definition [ def : injectiveinonedirectionandrichard ] . [ lem : binarybarfunctionsdescription ] let @xmath140 . then @xmath544 iff @xmath75 is injective in one direction and for all @xmath545 , each of the unary operations @xmath546 and @xmath547 is either constant or injective . assume that @xmath75 is of that form , and let @xmath548 be given . we can say without loss of generality that @xmath75 is injective in the first direction . write @xmath312 as a disjoint union @xmath549 in such a way that @xmath550 is injective for all @xmath551 , and constant for all @xmath552 . if @xmath553 , then there exist injections @xmath554 and a @xmath347-bar function @xmath62 such that @xmath555 agrees with @xmath75 on @xmath312 . hence , @xmath544 . + we use induction over terms to show the other direction . the statement is true for all bar - functions , including the projections . assume it holds for @xmath556 , and consider @xmath557 . then @xmath275 is injective in one direction ( this is easy to see , and also follows from lemma  [ lem : risaclone ] in subsection  [ subsect : richard ] ) . let @xmath558 be arbitrary and consider @xmath559 . by induction hypothesis , we have that @xmath560 and @xmath561 are constant or injective . if both @xmath562 and @xmath563 are injective , then so is @xmath399 , since @xmath75 is injective in one direction . if on the other hand both @xmath562 and @xmath563 are constant , then @xmath399 is constant as well . assume therefore without loss of generality that @xmath562 is injective and @xmath563 is constant with value @xmath521 . now if @xmath564 is constant , then so is @xmath399 , and if @xmath435 is injective , then the same holds for @xmath399 again , and we are done . [ lem : producinginjectivefields ] let @xmath565 be essential and non - injective , and let @xmath566 . then @xmath75 generates a binary function @xmath62 which is not injective but injective on @xmath567 .    without loss of generality we assume @xmath568 for some @xmath569 and distinct @xmath570 . pick any binary injection @xmath271 . by lemma [ prop : hornchar ] , @xmath271 is generated by @xmath75 . . then @xmath380 satisfies @xmath572 , and is injective in the @xmath371-nd direction . therefore , replacing @xmath75 by @xmath380 , we may assume that @xmath75 is injective in the @xmath371-nd direction . we use induction over @xmath18 to prove the assertion of the lemma . + for the induction beginning , let @xmath375 . we may assume that there exist @xmath573 and distinct @xmath574 with @xmath575 . indeed , otherwise @xmath75 is injective on the infinite square of pairs from @xmath576 , in which case we get the assertion by applying permutations . since @xmath75 is essential , we may assume @xmath577 . we have that @xmath578 and @xmath579 as @xmath75 is injective in the @xmath371-nd direction . therefore , the only thing in our way to an injection on @xmath14 is that possibly @xmath580 . in that case , we let a permutation @xmath581 map @xmath582 to @xmath445 , @xmath583 to @xmath284 , and set @xmath584 . it is easy to check that @xmath380 is injective on @xmath371 and satisfies @xmath575 . + for the induction step , let @xmath75 be injective on @xmath18 , where @xmath566 . we generate a function @xmath62 that is injective on @xmath133 and satisfies @xmath585 for some @xmath586 with @xmath587 . again , we pick a binary injection @xmath271 and set @xmath571 . clearly , @xmath380 is still injective on @xmath18 . moreover , @xmath380 satisfies @xmath572 , and is injective in the @xmath371-nd direction . therefore , replacing @xmath75 by @xmath380 , we may henceforth assume that @xmath75 is injective in the @xmath371-nd direction . + as in the induction beginning , we may assume that there exist @xmath573 and distinct @xmath574 with @xmath575 . since @xmath75 is injective in the @xmath371-nd direction we have @xmath588 $ ] . + if @xmath589 for some @xmath590 and @xmath591 , then we do the following : choose a permutation @xmath581 that exchanges @xmath18 with some @xmath592 for which @xmath593 , and which is the identity otherwise . let @xmath594 be a permutation that maps @xmath595 into @xmath18 , and @xmath583 to @xmath284 . now set @xmath596 . we have :    * all points @xmath597 that had different values under @xmath75 still have different values under @xmath380 ; in particular , @xmath380 is injective in the @xmath371-nd direction , and injective on @xmath18 . * @xmath598 . * @xmath599 . if we repeat this procedure for all @xmath591 for which there exists @xmath590 with @xmath589 , then in the end @xmath600 for all @xmath601 and all @xmath591 . now the only non - injectivity that could be left on @xmath133 could be that @xmath602 for some distinct @xmath603 . one gets rid of this setting a last time @xmath604 , where @xmath594 is a permutation that maps @xmath605 into @xmath18 , and @xmath583 to @xmath284 . [ lem : everybinarygeneratestheonebar ] let @xmath565 be essential and non - injective . then it generates a @xmath446-bar function . fix a @xmath446-bar function @xmath606 . we show that for arbitrary @xmath566 , @xmath75 generates a function which agrees with @xmath606 on @xmath18 . define a finite sequence of natural numbers @xmath607 by setting @xmath608 , and @xmath609 . by lemma [ lem : producinginjectivefields ] and the use of permutations , we can produce a function @xmath62 which is injective on @xmath610 and satisfies @xmath611 for some distinct @xmath612 . moreover , we may assume that @xmath613\subseteq m_k$ ] . we first want to produce a function @xmath614 which is injective on @xmath615 and satisfies @xmath616 . there is nothing to show if @xmath617 . otherwise , we may assume @xmath618 , and set @xmath619 ; it is easy to check that @xmath614 has the desired properties . replace @xmath62 by @xmath614 . by repeating this procedure we can produce a function @xmath614 which is injective on @xmath620 and satisfies @xmath621 . doing the same @xmath18 times , we get @xmath614 which is injective on @xmath622 and satisfies @xmath623 . clearly , there exists a permutation @xmath581 such that @xmath624 agrees with @xmath606 on @xmath625 . the following summarizes the results about @xmath147 obtained so far . relational descriptions of @xmath147 will be given in proposition  [ prop : relbarchar ] . observe that the equivalence between ( 1 ) and ( 5 ) is exactly statement ( 3 ) of theorem  [ thm : monoidalintervalofs ] . [ prop : barchar ] let @xmath19 be a relation with a first - order definition in @xmath481 . then the following are equivalent .    1 . @xmath19 is preserved by an operation from @xmath626 , i.e. , @xmath627 . @xmath19 is preserved by a non - injective operation that depends on all its arguments and preserves @xmath162 . @xmath19 is preserved by an operation from @xmath628 that violates @xmath522 . @xmath19 is preserved by a @xmath446-bar function . @xmath19 is preserved by @xmath147 , i.e. , @xmath629 . given an operation from @xmath626 , we obtain an operation as described in ( 2 ) by leaving away all fictitious arguments , so ( 1 ) implies ( 2 ) . an operation that is non - injective and depends on all its arguments is not generated by an injective operation , and therefore lemma  [ lem : binabovehorn ] shows the implication from @xmath630 to @xmath631 . any binary operation that violates @xmath522 is necessarily essential and non - injective , and hence the conditions of lemma  [ lem : everybinarygeneratestheonebar ] are satisfied , which shows the implication from @xmath631 to @xmath632 . the equivalence of @xmath632 and @xmath633 is lemma  [ lem : barfunctionsequvalent ] , and the implication from @xmath632 to @xmath630 is immediate . the equivalence of @xmath633 and @xmath634 is by definition .      in this subsection , we explore those clones in the monoidal interval @xmath159 which contain the bar clone @xmath147 , but which are not contained in @xmath24 ( the clone of operations which are injective in one direction , cf .  definition  [ def : injectiveinonedirectionandrichard ] ) . it will be necessary to first give a relational description of @xmath147 . in the following it will be convenient to work with first - order formulas whose atomic formulas are of the form @xmath475 , _ true _ , or _ false_. the _ graph _ of a quantifier - free formula @xmath474 with such atomic formulas is the graph where the vertices are the variables of @xmath474 , and where two vertices @xmath635 are adjacent iff @xmath474 contains the sub - formula @xmath475 or the sub - formula @xmath636 . we recall standard terminology . if a formula @xmath474 is in conjunctive normal form , the conjuncts in @xmath474 are called _ clauses _ , and the disjuncts in a clause are called _ literals_. hence , literals are formulas that are either atomic , in which case they are also called _ positive _ , or the negation of an atomic formula , in which case they are also called _ negative_.    let @xmath474 be a quantifier - free first - order formula where all atomic formulas are of the form @xmath475 or _ false_. then @xmath474 is called    * _ horn _ iff @xmath474 is in conjunctive normal form and each clause in @xmath474 contains at most one positive literal ; * _ connected horn _ iff @xmath474 is horn and the graph of a clause @xmath477 in @xmath474 has at most two connected components when @xmath477 has no positive literals , and is connected when @xmath477 has positive literals . * _ extended horn _ iff @xmath474 is a conjunction of formulas of the form @xmath637 for @xmath638 where @xmath639 are atomic formulas ( and hence of the form @xmath475 or _ false _ ) . * _ connected extended horn _ iff @xmath474 is extended horn , and if a conjunct @xmath477 of @xmath474 is connected whenever the right - hand side of the implication in @xmath477 contains a literal of the form @xmath475 and no literal _ false_.    clearly , every connected horn formula can be written as a connected extended horn formula . but there are connected extended horn formulas that are not equivalent to any connected horn formula ; we will even see that there are connected extended horn formulas that do not have a pp definition by connected horn formulas ( lemmas  [ lem : gkpresrk-1 ] and [ lem : gkviolatesrk ] ) . the conjuncts in an extended horn formula are also called _ extended horn clauses _ , and the literals on the left - hand side ( right - hand side ) of the implication of an extended horn clause are called the _ negative literals _ ( _ positive literals _ , respectively ) of the extended horn clause . note that extended horn formulas can always be translated into ( standard ) horn formulas : if @xmath640 is an extended horn clause , then we can replace this clause by the conjunction of horn clauses @xmath641 .    it will be convenient to say that a formula is _ preserved _ by an operation ( or a set of operations ) iff the relation that is defined by the formula is preserved by the operation ( or by the set of operations , respectively ) . we want to give a syntactic description of the formulas that are preserved by @xmath147 . we show that every such formula is equivalent to a connected extended horn formula . in fact , we show the stronger result that every _ expanded horn formula _ preserved by @xmath147  is itself a connected extended horn formula . [ def : expand ] a extended horn formula @xmath474 is called _ expanded horn _ iff it contains all connected extended horn clauses on the same set of variables as @xmath474 that are implied by @xmath474 , and for every disconnected clause @xmath642 in @xmath474 where @xmath643 does not contain _ false _  and for all variables @xmath635 in @xmath474    * adding an atomic formula of the form @xmath475 to @xmath644 , or * adding an atomic formula of the form @xmath475 to @xmath643 , or * setting @xmath643 to _ false _    results in a formula that is not equivalent to @xmath474 . [ lem : expand ] every extended horn formula is equivalent to an expanded horn formula . let @xmath474 be any given extended horn formula . we construct the expanded horn formula that is equivalent to @xmath474 , as follows . we first add to @xmath474 all connected extended horn clauses that are implied by @xmath474 . then , if @xmath474 contains an extended horn clause @xmath645 that is not connected and where @xmath643 does not contain _ false _ , and @xmath474 is equivalent to a formula @xmath646 obtained from @xmath474 by adding an atomic formula of the form @xmath475 to @xmath644 or to @xmath643 for variables @xmath635 in @xmath474 , or by setting @xmath643 to _ false _ , then we replace @xmath474 by @xmath646 . if @xmath474 does not contain such a clause ( which will always happen after a finite number of steps , because there is only a finite number of formulas of the form @xmath475 for variables @xmath635 in @xmath474 ) , then @xmath474 is expanded horn , and clearly equivalent to the formula we started with . [ lem : connexthorn ] if @xmath474 is an expanded horn formula , and @xmath474 defines a relation @xmath19 that is preserved by @xmath147 , then @xmath474 is connected extended horn . suppose for contradiction that @xmath647 contains an extended horn clause @xmath477 of the form @xmath642 whose graph @xmath450 contains at least two connected components , and where @xmath643 does not contain _ false _  and contains at least one positive literal @xmath486 . let @xmath648 be a variable from a connected component of @xmath450 that does not contain @xmath649 and @xmath650 . let @xmath651 be the components of @xmath652 , where @xmath653 is the graph of @xmath643 . observe that @xmath649 and @xmath650 are in distinct components : otherwise , if we replace the clause @xmath477 by @xmath654 , we obtain an equivalent formula . because @xmath477 is disconnected , this is in contradiction to the assumption that @xmath474 is expanded . assume for the sake of notation that @xmath655 is the component of @xmath649 , and @xmath656 the one of @xmath650 . we claim that there is a tuple @xmath284 for which @xmath657 is true , for which @xmath658 , and for which @xmath659 whenever @xmath660 are both in @xmath655 or are both in @xmath656 . otherwise , @xmath474 implies @xmath661 , which is a connected expanded horn formula and therefore contained in @xmath474 . then @xmath474 must be equivalent to the formula @xmath646 obtained from @xmath474 by replacing the disconnected clause @xmath477 by @xmath662 , again in contradiction to the assumption that @xmath474 is expanded . to show the equivalence , it clearly suffices to prove that @xmath646 implies @xmath474 . so suppose that @xmath284 satisfies @xmath646 and @xmath644 . the clause @xmath661 , which is contained in @xmath474 and in @xmath646 , shows that @xmath663 . but then the premise of the new extended horn clause of @xmath646 is satisfied as well , and therefore @xmath284 satisfies @xmath643 , which is what we had to show . next , we claim that there is a tuple @xmath275 with @xmath664 satisfying @xmath474 and where @xmath665 if @xmath660 are from the same component @xmath666 for some @xmath667 . otherwise , @xmath474 implies @xmath668 . but then the formula @xmath646 obtained from @xmath474 by replacing @xmath477 by @xmath669 is clearly equivalent to @xmath474 . this again contradicts the assumption that @xmath474 is expanded . let @xmath75 be a binary operation such that @xmath670 is constant for all entries @xmath513 of @xmath275 except for @xmath671 , and which is injective otherwise . clearly , modulo permutations acting on its arguments , @xmath75 is an @xmath45-bar operation , and hence @xmath672 . now , consider the tuple @xmath673 . note that @xmath674 , because @xmath275 satisfies @xmath474 and @xmath275 satisfies the premise of the clause @xmath477 that is contained in @xmath474 ; since the conclusion of @xmath477 contains @xmath486 we have that @xmath674 . it is straightforward to verify that @xmath277 does not satisfy @xmath474 , because @xmath277 satisfies @xmath644 , but @xmath675 , and therefore @xmath477 is violated . the following relations play an important role in the relational description of @xmath147 and the clones above @xmath147 .    for @xmath676 , let @xmath677 , @xmath678 , and @xmath679 be the relations defined by @xmath680    note that all three relations can be defined by connected extended horn formulas . observe also that the expressive power of the relations in each of these sequences increases with increasing @xmath45 : for example , @xmath681 is a pp definition of @xmath677 from @xmath682 .    [ prop : relbarchar ] let @xmath19 be a relation with a first - order definition in @xmath481 . then the following are equivalent .    1 . @xmath19 is preserved by @xmath147 , i.e. , @xmath629 . every expanded horn formula that defines @xmath19 is connected extended horn . @xmath19 can be defined by a connected extended horn formula . 4 .   there exists an @xmath45 such that @xmath19 has a pp - definition in @xmath683 .    the implication from @xmath630 to @xmath631 is shown in lemma  [ lem : connexthorn ] . for the implication from @xmath631 to @xmath632 , recall that @xmath147 contains @xmath139 and hence the relation @xmath19 has a horn definition . by lemma  [ lem : expand ] , every horn formula has an equivalent expanded horn formula , and by assumption this formula is a connected extended horn definition of @xmath19 .    to show that @xmath632 implies @xmath633 , let @xmath19 be a relation with a connected extended horn definition @xmath474 . we first show that every extended horn clause @xmath642 from @xmath474 can be pp - defined in @xmath684 , for a sufficiently large @xmath45 , if @xmath643 is non - empty and does not contain _ let @xmath450 be the graph of @xmath644 where we add isolated vertices for each variable that appears in @xmath643 but not in @xmath644 ; in other words , let @xmath450 be the graph of @xmath642 where we remove an edge between @xmath685 and @xmath686 if @xmath475 is a literal of @xmath643 and not of @xmath644 . let @xmath687 be the components of the graph @xmath450 . we claim that @xmath642 can be pp - defined by @xmath678 where @xmath688 . a pp definition is obtained from the formula @xmath689 by existentially quantifying @xmath690 , where @xmath691 . in this pp definition , the variables @xmath692 are the variables in the component @xmath693 from @xmath642 .    to see that this is correct , consider a satisfying assignment to the variables of @xmath642 . set for all @xmath149 the variables @xmath694 to the same value as @xmath695 . suppose first that there exist two variables @xmath696 from the same component @xmath240 which are mapped to different values . then @xmath487 can not be equal to both @xmath697 and @xmath698 , and hence either @xmath699 or @xmath700 . hence , the conjunct @xmath701 is satisfied , and the assignment satisfies the given pp formula . suppose now that otherwise all variables which have the same component are mapped to the same value . since @xmath642 is connected horn , this implies by transitivity of equality that all variables that appear in @xmath642 must have the same value . but this assignment clearly satisfies the given pp formula as well , so we are done with one direction of the correctness proof .    for the other direction , consider a satisfying assignment for the pp formula . if all variables are set to the same value , then @xmath642 will be satisfied by this assignment as well , because @xmath643 does not contain _ false_. otherwise , @xmath699 for some @xmath702 because of the conjunct @xmath701 . let @xmath693 be the component of @xmath697 in @xmath450 . then @xmath703 . but since @xmath693 is a connected component , this implies that one of the equalities in @xmath644 must be falsified , showing that @xmath642 is satisfied by the assignment .    now , suppose that @xmath474 contains a clause @xmath642 where @xmath643 contains _ false _ ; i.e. , the clause is logically equivalent to a disjunction of literals of the form @xmath636 . we proceed just as in the case above , but use the relation @xmath704 instead of @xmath705 with two new existentially quantified variables @xmath706 and @xmath707 at the two additional arguments , and we also add the conjunct @xmath708 to the formula . we leave the verification that the resulting formula is equivalent to @xmath642 to the reader . as we have seen , any clause from a connected horn formula can be pp - defined in @xmath709 , and thus @xmath632 implies @xmath633 . finally , @xmath633 implies @xmath630 : it is easy to see that for all @xmath676 the relations @xmath710 and the relation @xmath162 are preserved by @xmath446-bar operations .      in this section we show that the interval between @xmath147 and @xmath470 contains an infinite strictly decreasing sequence of clones whose intersection is @xmath147 . [ def : fk ] for all @xmath566 , fix an operation @xmath711 satisfying the following : @xmath712 moreover , for all other arguments , the function arbitrarily takes a value that is distinct from all other function values . observe that @xmath158 appeared already in definition  [ def : oddclone ] . we use the @xmath713 to define another sequence of operations . [ def : gk ] for all @xmath374 , fix an operation @xmath714 which satisfies @xmath715 and which takes distinct values for all other arguments . observe that each of the operations @xmath383 ( and similarly @xmath713 ) generates @xmath147 : obviously , @xmath383 depends on all arguments , is non - injective , and preserves @xmath162 . by proposition  [ prop : barchar ] , all relations that are preserved by @xmath383 are also preserved by @xmath147 , and hence @xmath383 generates @xmath147 .    we now show that the operations @xmath383 , for increasing @xmath18 , generate smaller and smaller clones . [ lem : gkpresrk-1 ] for @xmath716 , the operations @xmath383 and @xmath713 preserve @xmath717 . we show the lemma for @xmath383 ; the proof for @xmath713 is similar and a bit easier , and left to the reader . let @xmath718 be @xmath719-tuples that all satisfy @xmath720 . let @xmath721 , and suppose that @xmath722 . by the definition of @xmath383 , this implies that @xmath723 , and that for all @xmath724 the tuples @xmath725 and @xmath726 have equal entries except for at most one position , call it @xmath727 . since the function @xmath728 takes at most @xmath729 values , there must be a @xmath730 which is not in the range of @xmath728 . for this @xmath347 we thus have @xmath731 . because @xmath732 , this implies that @xmath733 . hence , the tuple @xmath734 is constant as well ; therefore , @xmath383 preserves @xmath720 . [ lem : gkviolatesrk ] for @xmath716 , the operation @xmath713 preserves neither @xmath735 nor @xmath736 . the operation @xmath383 does not preserve @xmath735 .    if we apply @xmath713 to the @xmath737-tuples @xmath738 that all satisfy @xmath739 ( and all satisfy @xmath736 ) , then we obtain @xmath740 , which does not satisfy @xmath741 ( and does not satisfy @xmath736 ) . for @xmath383 , we define @xmath742 , and apply @xmath383 to @xmath743 . we have thus seen that @xmath744 is a strictly decreasing chain of clones ( it is decreasing by the remark after the definition of these relations , and strictly so by the preceding lemma ) . by proposition  [ prop : relbarchar ] its intersection equals @xmath147 . a clone of special interest ( see theorems  [ thm : monoidalintervalofs ] and [ thm : monoidalintervalofsplusconst ] ) is the clone @xmath157 generated by @xmath158 , which will be called the _ odd clone _ ( cf .  definition  [ def : oddclone ] ) . we will now describe the relations invariant under @xmath157 by providing a ( finite ) generating system of these relations , as well as a syntactic characterization of the formulas defining such relations . let @xmath745 be the ternary relation @xmath746    [ prop : schar ] let @xmath19 be a relation with a first - order definition in @xmath481 . then the following are equivalent .    1 . @xmath19 can be defined by a connected horn formula . 2 .   @xmath19 has a pp definition by @xmath747 and @xmath162 . 3 .   @xmath19 has a pp definition by @xmath745 and @xmath162 . 4 .   @xmath748 , i.e. , @xmath19 is preserved by @xmath158 . @xmath749 , but there is no definition of @xmath750 in @xmath751 .    before proving the proposition , we need two proof - theoretical lemmas observing restrictions on what can be derived from connected extended horn formulas .    [ lem : restrsem ] suppose @xmath474 is a connected extended horn formula that does not imply @xmath516 , but @xmath752 implies @xmath516 . then @xmath752 also implies @xmath753 . we rewrite @xmath474 as a conjunction @xmath754 of ( standard ) horn clauses as described above . when for an extended clause @xmath755 for some @xmath756 we have @xmath757 , then we first remove all positive literals except @xmath16 from the extended clause , which leads to an equivalent formula . it is well - known that the restricted form of resolution for predicate logic that requires that at least one of the parent clauses in a resolution step has to be positive , also known as _ p - resolution _ , is complete ( see e.g.  @xcite , p.  102 ) . when we apply resolution on a formula , we assume that there are always clauses @xmath758 , @xmath759 , and @xmath760 for universally quantified variables @xmath517 ( that axiomatize that the symbol @xmath761 for equality is an equivalence relation ) , and we also assume that all other variables in the formula are in fact constant symbols ( i.e. , they are existential variables before skolemization ) .    since @xmath762-resolution is complete , we have in particular that @xmath763 implies @xmath516 if and only if @xmath516 can be derived by p - resolution from @xmath763 . we show that @xmath763 implies @xmath753 for all formulas @xmath516 that are not implied by @xmath754 but implied by @xmath763 . suppose for contradiction that there is a literal @xmath516 that can be derived by p - resolution from @xmath763 but can not be derived from @xmath754 , and where @xmath763 does not imply @xmath753 . select a literal @xmath516 with these properties whose @xmath762-derivation from @xmath763 is shortest possible . the literal @xmath516 has either been derived from a clause @xmath764 in @xmath754 by resolving with the literals @xmath765 , or by resolving with of the three clauses having universally quantified variables ( after instantiating the universal variables ) . in the second case , suppose that the universal clause was @xmath766 , and @xmath516 has been derived by resolving with @xmath767 and @xmath768 , for some @xmath520 ( for the other two universal clauses , the argument is analogous ) . then at least one of the literals @xmath767 and @xmath768 can not be derived from @xmath754 alone , because otherwise @xmath516 can be derived from @xmath754 alone , in contradiction to our assumptions . suppose the literal that can not be derived from @xmath754 alone is @xmath767 ( the other case is analogous ) . by the choice of @xmath516 , the formula @xmath763 implies @xmath769 . at the same time , we have that @xmath763 implies @xmath516 , and hence @xmath754 implies @xmath753 , a contradiction . in the first case , at least one of the literals in the clause @xmath764 , say @xmath770 , can not be derived from @xmath754 alone , because otherwise @xmath516 can be derived from @xmath754 alone , in contradiction to our assumptions . by the choice of @xmath516 , @xmath763 implies @xmath771 . let @xmath25 be the extended horn clause in @xmath474 that corresponds to the horn clause @xmath477 in @xmath754 ( i.e. , @xmath477 is among the clauses that have replaced the clause @xmath25 when creating @xmath754 from @xmath474 ) . since @xmath25 is a connected extended horn clause , there is a sequence of variables @xmath772 of @xmath25 with @xmath773 and @xmath774 such that @xmath775 for @xmath776 is either a sub - formula of the right - hand side or of the left - hand side of the implication @xmath25 . by construction of @xmath754 , for each literal @xmath775 on the right - hand side there is the clause @xmath777 in @xmath754 . but then it is clear that @xmath778 implies that @xmath779 , and hence also that @xmath780 . therefore , @xmath763 implies @xmath753 , a contradiction .    the following is a straightforward consequence . [ lem : restrsem2 ] let @xmath474 be a connected extended horn formula and let @xmath477 be a conjunction of equalities @xmath781 . if @xmath782 implies @xmath783 , but @xmath784 does not imply @xmath783 for any subconjunction @xmath488 of @xmath477 , then @xmath782 also implies @xmath785 . we apply lemma  [ lem : restrsem ] to @xmath786 , @xmath787 , and @xmath788 to derive that @xmath789 implies @xmath790 . we can argue analogously for @xmath791 instead of @xmath787 for all @xmath792 , and the statement follows .    to show that ( 1 ) implies ( 2 ) , suppose that @xmath474 is a connected horn definition of @xmath19 . we show that each clause @xmath477 of @xmath474 has a pp definition in @xmath793 . first , consider the case that @xmath477 contains a positive literal @xmath783 . the graph of @xmath477 without the edge between @xmath794 and @xmath795 has at most two connected components . in the case that the graph is still connected even after removing the edge between @xmath794 and @xmath795 , the clause @xmath477 is a tautology and can be ignored . otherwise , let @xmath796 be the variables of the connected component of @xmath794 , and let @xmath797 be the variables of the connected component of @xmath686 . consider the formula @xmath488 defined by @xmath798 we show that a tuple satisfies @xmath477 if and only if it satisfies @xmath488 . if the tuple satisfies no negative literal of @xmath477 , then the only situation where @xmath488 is true is @xmath799 ; hence in this case , @xmath488 holds if and only if the tuple satisfies @xmath783 , which in turn is the case if and only if @xmath477 holds . if on the other hand the tuple satisfies some negative literal of @xmath477 , then either there is @xmath800 such that @xmath801 or @xmath802 such that @xmath803 ; assume wlog the first is the case . then we set @xmath804 to @xmath805 and @xmath806 to @xmath807 , @xmath808 to @xmath809 , and set @xmath810 to arbitrary pairwise disjoint values that are also distinct from all the values taken by any other variable of the clause . it is easy to check that this assignment of variables is a satisfying assignment for the existentially quantified variables in the formula @xmath488 . hence , @xmath488 is a pp definition of @xmath477 .    if @xmath477 does not contain a positive literal , then the graph of @xmath477 consists of at most two connected components , because @xmath25 is connected horn . assume first it does have two components . let @xmath796 be the variables in the first and @xmath797 be the variables in the second connected component . as above , it is easy to verify that the following formula is equivalent to @xmath477 . @xmath811    if the graph of @xmath477 has only one component , then the following formula is equivalent to @xmath477 : @xmath812    for the implication from @xmath631 to @xmath632 , note that @xmath813 can be pp defined by @xmath814 we check that this formula is indeed equivalent to @xmath815 : let @xmath275 be a @xmath191-tupel that satisfies @xmath813 ; we assign values to the @xmath816 such that the formula above is satisfied . if @xmath817 then set @xmath818 to @xmath819 . if @xmath820 then set @xmath821 to @xmath822 . note that if both @xmath817 and @xmath820 then our choice for @xmath823 is well - defined , since @xmath813 then implies that @xmath824 . if @xmath825 then set @xmath826 to distinct values that are also distinct from all entries of @xmath275 . similarly , if @xmath827 , then set @xmath828 to distinct values that are also distinct from all entries of @xmath275 . if both @xmath825 and @xmath827 , then set @xmath823 to any value that is distinct from the values for @xmath829 . it is straightforward to verify that these assignments satisfy all conjunct in the given formula . conversely , if a @xmath191-tuple @xmath275 satisfies the formula , and @xmath817 and @xmath820 , then @xmath824 , and hence @xmath275 satisfies @xmath813 .    for the implication from @xmath632 to @xmath633 it suffices to verify that @xmath158 preserves @xmath745 . every 3-tuple @xmath275 from @xmath745 either satisfies @xmath830 or @xmath831 . to violate @xmath745 , we would have to find three such tuples @xmath832 such that @xmath833 has two equal entries that are distinct from a third entry , say wlog . @xmath834 . the only two ways to have @xmath835 are when @xmath835 is from @xmath836 , or when this is not the case and the tuples @xmath837 and @xmath838 are equal . consider the first case , and assume wlog . . then we know that @xmath840 and @xmath841 . but then , since @xmath606 and @xmath520 are in @xmath745 , we have @xmath842 as well , and hence @xmath843 , a contradiction . the second case is similar and left to the reader . hence , @xmath158 preserves @xmath745 .    for the implication from @xmath633 to @xmath634 , containment in @xmath844 follows from the fact that @xmath158 generates all operations in @xmath147 ( see also the remark after definition  [ def : gk ] ) . by lemma  [ lem : gkpresrk-1 ] , @xmath158 preserves @xmath747 and @xmath158 also clearly preserves @xmath162 , so it suffices to show that @xmath158 violates @xmath845 . if we apply @xmath158 to the 6-tuples @xmath846 , @xmath847 , @xmath848 , which all satisfy @xmath845 , we obtain @xmath849 , which does not satisfy @xmath845 . finally , we show the contraposition of the implication from @xmath634 to @xmath630 : if @xmath19 can not be defined by a connected horn formula , but is preserved by @xmath147 , then there is a pp - definition of @xmath850 in @xmath751 for some @xmath851 . because @xmath845 clearly has a pp - definition by @xmath850 for all @xmath851 this will show the statement . let @xmath852 be an expanded horn formula that defines @xmath19 . by proposition  [ prop : relbarchar ] , we know that @xmath474 is a connected extended horn formula . we first claim that if for all extended horn clauses @xmath642 in @xmath474 the graph of @xmath644 has at most two connected components , then @xmath474 has a connected horn definition , contradicting our assumption on @xmath474 . to see this , we show that every such clause @xmath853 has a connected horn definition . if @xmath643 contains _ false _  or is empty then there is nothing to show ; assume thus that this is not the case . if the graph of @xmath644 has exactly two components @xmath655 and @xmath656 , we know that @xmath643 contains a conjunct @xmath475 where @xmath854 and @xmath855 , because @xmath474 is connected extended horn . then @xmath642 is equivalent to the conjunction of the connected horn clauses @xmath856 and @xmath857 for every other conjunct @xmath858 of @xmath643 . the case that the graph of @xmath644 is connected is easier and left to the reader . therefore , @xmath474 must contain a clause @xmath642 such that @xmath644 consists of @xmath851 connected components @xmath859 . we show that @xmath860 has the following pp - definition by @xmath19 , @xmath747 and @xmath162 . @xmath861    to prove the equivalence , assume that @xmath862 . we want to show that @xmath275 does not satisfy @xmath863 . if @xmath275 violates the second line of the formula @xmath863 , we are done . otherwise , it must hold that @xmath864 . suppose for contradiction that there are elements @xmath865 as specified in @xmath863 . then for all @xmath792 the sub - formula @xmath866 implies that all variables @xmath809 from @xmath240 must have the same value as @xmath791 . then the clause @xmath642 in @xmath474 implies that @xmath867 ( because @xmath868 is connected ) , which contradicts the second line of formula @xmath863 . now assume that @xmath869 . we want to show that @xmath275 satisfies @xmath863 . if @xmath275 satisfies @xmath870 for all @xmath871 , then any tuple from @xmath19 gives a assignment to the existentially quantified variables in @xmath863 that shows that @xmath275 satisfies @xmath863 . for the sake of notation , let us thus assume that there is a @xmath18 with @xmath872 such that @xmath275 satisfies @xmath791 for @xmath873 , and @xmath870 for all @xmath874 . we claim that there exists a tuple @xmath875 such that for all @xmath876 and all @xmath877 , @xmath878 it holds that @xmath879 if and only if @xmath880 . otherwise , the formula @xmath881 is unsatisfiable . since p - resolution ( also see the proof of lemma  [ lem : restrsem ] ) is complete , there is a p - resolution proof of unsatisfiability . this proof uses at most once a clause of the form @xmath882 from this formula , since it resolves only with positive literals and since therefore every resolution step using @xmath882 must be the last one , deriving _ false_. therefore , @xmath883 implies @xmath884 . let @xmath25 be the smallest sub - formula of @xmath885 such that @xmath886 implies @xmath884 . if @xmath25 is empty , then the clause @xmath884 is contained in @xmath474 because @xmath474 is expanded ; but then , adding @xmath887 to @xmath477 in the clause @xmath642 results in an equivalent formula , a contradiction to @xmath474 being expanded . if @xmath25 is not empty , we can apply lemma  [ lem : restrsem2 ] and obtain that @xmath886 implies that all variables @xmath888 that appear in @xmath25 have the same value as the value of @xmath884 . because @xmath474 is expanded , it has to contain the connected extended horn clause @xmath889 ; again , this shows that adding @xmath887 to @xmath644 in the clause @xmath642 results in an equivalent formula , a contradiction . hence , we have shown the existence of a tuple @xmath875 with the properties as claimed above . the tuple @xmath277 gives witnesses for the existentially quantified variables in @xmath863 that show that @xmath275 satisfies @xmath863 .      in this section we show that @xmath24 and @xmath157 are incomparable clones , and that every clone in @xmath159 is either contained in @xmath157 or contains @xmath24 . we start with the fundamental observation that the set of operations @xmath24 ( see definition  [ def : injectiveinonedirectionandrichard ] ) is indeed a clone . [ lem : risaclone ] @xmath24 is a clone . clearly , @xmath24 contains the projections . let @xmath890 and @xmath891 . there exist @xmath148 and @xmath892 such that @xmath75 is injective in the @xmath149-th direction and @xmath409 is injective in the @xmath347-th direction . it is readily verified that @xmath386 is injective in the @xmath347-th direction . let @xmath25 be a quantifier - free first - order formula where all atomic subformulas are of the form @xmath475 . then @xmath25 is called _ negative _ if @xmath25 is in conjunctive normal form and each clause in @xmath25 either consists of a single positive literal , or does not contain positive literals . the following theorem has been stated in equivalent form in  ( * ? ? ? * lemma 8.6 ) . for the convenience of the reader , and for completeness , we also present a simplified proof here . [ thm : negative ] let @xmath19 be a relation having a reduced horn definition that is not negative . then @xmath745 has a pp definition from @xmath19 and @xmath162 . let @xmath647 be a reduced horn definition of @xmath19 which is not negative ; assume moreover that among such definitions of @xmath19 , @xmath474 is one with the minimal possible number of occurrences of variables . since @xmath19 is not negative , there must be a clause @xmath477 in @xmath474 of the form @xmath893 for @xmath894 . since @xmath474 is reduced , it contains a tuple @xmath895 with @xmath896 for all @xmath897 : otherwise , @xmath474 would imply @xmath898 , and we would obtain an equivalent formula by removing the literal @xmath899 from @xmath477 . moreover , @xmath19 contains a tuple @xmath900 with @xmath901 , @xmath902 , and @xmath903 for all @xmath904 : otherwise , we could remove the literal @xmath905 from @xmath477 . now consider the formula @xmath906 note that because @xmath19 is reduced , we have @xmath907 . we first look at the case where @xmath908 . by appropriately renaming the variables of @xmath474 , we may assume that @xmath909 , and that @xmath910 and @xmath911 . let @xmath912 be the ternary relation defined by existentially quantifying all variables in ( * ) except for @xmath649,@xmath913,@xmath914 . because @xmath915 satisfies @xmath916 for all @xmath917 , it satisfies ( * ) . since @xmath918 , the relation @xmath919 contains a triple with three equal entries . moreover , because @xmath920 satisfies ( * ) too , the relation @xmath919 contains a tuple @xmath921 with @xmath922 and @xmath923 . assume first that @xmath919 contains a triple with three distinct entries . we know that @xmath919 does not contain any tuple of the form @xmath924 for @xmath636 , because every @xmath45-tuple @xmath5 with @xmath925 and @xmath926 violates @xmath927 . hence , the relation defined by @xmath928 only contains the tuples with three distinct entries and the tuples with three equal entries , and we have indeed found a pp - definition of the relation @xmath745 in @xmath929 .    striving for a contradiction , we suppose now that @xmath930 does not contain a triple with three distinct entries . then it is impossible that there is a tuple @xmath931 where @xmath932 : this is because having a horn definition , @xmath19 is preserved by a binary injection , by proposition  [ prop : hornchar ] , and so is @xmath919 . but the tuple obtained by applying a binary injective operation to @xmath277 and @xmath921 has three distinct entries , which contradicts our assumption for this case . thus the clause @xmath933 is entailed by @xmath474 . hence , we could replace the clause @xmath477 in @xmath474 by this shorter clause and obtain a formula that is equivalent to @xmath474 , because conversely , @xmath934 implies @xmath935 ( recall that @xmath936 ) . this contradicts the choice of @xmath474 . now take the case where @xmath937 ; say wlog @xmath938 . let @xmath939 be the relation defined by @xmath863 by existentially quantifying all variables except for @xmath940 . as before we observe that @xmath941 and @xmath942 . if @xmath943 , then the tuple obtained by applying a binary injective operation to @xmath944 and @xmath945 has four distinct entries ; this tuple is an element of @xmath19 , by proposition  [ prop : hornchar ] . it is easy to verify that then the formula @xmath946 is a pp definition of the relation @xmath947 given by @xmath948 the relation @xmath949 has the following pp - definition . @xmath950    now suppose that @xmath951 and hence @xmath944 is the tuple with four equal entries . assume for a moment that there exist @xmath952 and @xmath953 such that @xmath954 implies @xmath955 . then the relation obtained from @xmath954 by existentially quantifying @xmath956 is such that we can proceed as in the case where @xmath957 . thus , we may henceforth assume that @xmath955 is not entailed for any @xmath958 and @xmath953 . for every such pair @xmath959 , fix a tuple in @xmath919 witnessing that @xmath960 can be satisfied . now applying a @xmath192-ary injection to these four witnessing tuples and @xmath945 , we obtain a tuple all of whose entries are distinct . this tuple is in @xmath919 as @xmath919 is preserved by @xmath139 , by proposition  [ prop : hornchar ] . consider the formula @xmath961 defined by the following formula . @xmath962    where @xmath963 denotes the symmetric group on @xmath964 . we claim that @xmath965 defines @xmath745 . note that tuples of the form @xmath966 and @xmath967 , for distinct @xmath968 , are not contained in @xmath919 since every @xmath45-tuple @xmath521 with @xmath969 and @xmath970 violates @xmath927 . therefore , the relation @xmath965 does not contain tuples with two values where one value appears three times , or tuples with three values where one value appears twice . but certainly @xmath965 does contain all tuples with four equal values , and all tuples with four pairwise distinct values . if some tuple where two values occur twice is excluded from @xmath919 , then @xmath965 does not contain any tuple with two values . hence in this case , @xmath971 is a pp definition of @xmath949 , and we are done . otherwise , @xmath965 contains all tuples where two values occur twice . similarly as before it is easy to verify that then the expression  @xmath972 above where @xmath919 has been replaced by @xmath965 is a pp definition of @xmath947 . we have already seen that @xmath745 has a pp definition from @xmath399 , so it has a pp definition in @xmath973 as well . the following proposition describes the clone @xmath24 : item ( 1 ) shows that @xmath24 is finitely generated ( namely , by any binary operation which violates @xmath745 but is injective in one direction ) ; and ( 2 ) and ( 3 ) provide a syntactical description of the formulas defining relations in @xmath974 .    [ prop : disjofineq ] let @xmath19 be a relation with a first - order definition in @xmath481 . then the following are equivalent .    1 . @xmath19 is preserved by a binary operation from @xmath470 that violates @xmath745 . every reduced definition of @xmath19 is negative . 3 .   @xmath19 has a negative definition . @xmath19 is preserved by @xmath24 .    to see that @xmath630 implies @xmath631 , fix any reduced definition of @xmath19 . since @xmath19 is preserved by a binary operation from @xmath470 , proposition  [ prop : hornchar ] implies that this definition is horn . as there is a binary operation preserving @xmath19 and @xmath162 which violates @xmath745 , there is no pp definition of @xmath745 from @xmath19 and @xmath162 . hence , our reduced definition must be negative , by theorem  [ thm : negative ] . the implication from @xmath631 to @xmath632 is trivial .    to show that @xmath632 implies @xmath633 , fix a negative definition @xmath474 of @xmath19 . let @xmath890 and @xmath975 be arbitrary . assume without loss of generality that @xmath75 is injective in the @xmath446-st direction . then @xmath976 satisfies all inequalities that were satisfied by @xmath977 , which is enough to satisfy @xmath474 as @xmath474 is negative . hence , @xmath75 preserves @xmath19 . the implication from @xmath633 to @xmath630 is witnessed by any binary operation which is not in @xmath147 but injective in one direction , as is easily verified . the following proposition establishes statement ( 4 ) of theorem  [ thm : monoidalintervalofs ] . [ prop : rsantichain ] the clones @xmath24 and @xmath157 form a maximal antichain in the interval @xmath978 $ ] . in fact , every clone in this interval is either contained in @xmath157 or contains @xmath24 . in particular , @xmath24 is a cover of @xmath979 . first , we have to show that @xmath24 and @xmath157 are indeed incomparable . by proposition  [ prop : disjofineq ] it is clear that @xmath24 is not a subset of @xmath157 , because it contains an operation that violates @xmath745 . to show that @xmath157 is not a subset of @xmath24 , it suffices to show that the operation @xmath158 from definition  [ def : oddclone ] is not injective in any direction . indeed , this holds as @xmath980 and @xmath981 and @xmath982 for all @xmath983 . therefore , @xmath984 and hence @xmath24 and @xmath157 form an antichain . now , let @xmath47 be any clone from the interval @xmath978 $ ] which is not contained in @xmath157 . then it contains an operation in @xmath470 that does not preserve @xmath745 . since @xmath745 has two orbits , @xmath47 contains a binary operation with these properties , by lemma  [ lem : op - arity ] . thus , proposition  [ prop : disjofineq ] implies that @xmath47 is above @xmath24 . hence , the antichain that consists of @xmath24 and @xmath157 is maximal , and every clone of the interval not contained in @xmath157 does contain @xmath24 . we now prove that there exists an antitone and injective mapping from the power set of @xmath13 into the interval @xmath985 $ ] ; in particular , this interval has cardinality @xmath986 . this proves the last statement ( 5 ) of theorem  [ thm : monoidalintervalofs ] .    for all @xmath128 , write @xmath987 for all @xmath988 with @xmath989 , writing @xmath990 with @xmath991 , we set @xmath992    set @xmath993    observe that the @xmath994 are all negative formulas ; hence , by proposition  [ prop : disjofineq ] , polymorphism clones of sets of relations defined by such @xmath994 will always contain @xmath24 . in the rest of this section , we will prove that no fixed @xmath994 can be defined from the others by primitive positive definitions . therefore , distinct sets of such formulas define distinct clones above @xmath24 , which is what we want . we now enumerate tuples @xmath995 as @xmath996 . if @xmath997 is a formula , then we say that @xmath520 satisfies @xmath25 iff @xmath998 holds ; this is to say that we insert @xmath999 for @xmath1000 , where @xmath1001 and @xmath148 . moreover , if @xmath1002 , we denote the `` @xmath1003-th column tuple '' @xmath1004 by @xmath1005 .    for all @xmath128 , we set @xmath241 to be the @xmath1006-ary relation defined by @xmath994 .    the operations of the following definition will separate the polymorphism clones of the @xmath241 .    for all @xmath128 , the _ hubie - violator _ @xmath1007 is an operation defined as follows : enumerate @xmath1008 , that is , those elements of @xmath241 which have only entries in @xmath1009 , by @xmath1010 . note that @xmath1011 since @xmath241 always contains the tuple where @xmath1012 and @xmath1013 , for all @xmath1014 . now we define @xmath1015 by @xmath1016 , for all @xmath238 ; in other words , we set @xmath1017 . for every other input tuple in @xmath1018 , @xmath1007 takes a unique value distinct from all other values in its range . +    let @xmath128 . then the hubie - violator @xmath1007 violates @xmath241 .    by definition , @xmath1017 , a tuple which does not satisfy @xmath1019 and which is therefore not an element of @xmath241 . +    let @xmath1020 . then the hubie - violator @xmath1007 preserves @xmath1021 . write @xmath54 for the arity of @xmath1007 . let @xmath1022 and set @xmath1023 . we must show @xmath1024 . we first check that @xmath284 satisfies the clauses @xmath1025 . suppose it does not , and pick any @xmath1026 with @xmath1027 witnessing this . we may assume wlog that @xmath1028 , where @xmath1029 , and write @xmath1030 . set @xmath1031 , and @xmath1032 , and @xmath1033 . if @xmath1034 were empty , then since for every value in @xmath1035 there is only a unique tuple that @xmath1007 sends to that value , we have that the column @xmath1036 equals the column @xmath1037 , for all @xmath1038 ( where we set @xmath1039 ) . thus in that case , no row @xmath1040 would satisfy @xmath1025 , a contradiction .    assuming that @xmath1035 were empty , we now show that there exists @xmath892 such that the row @xmath1040 does not satisfy @xmath1041 . since @xmath1042 , we have @xmath1043 , for some @xmath1001 . similarly , @xmath1044 , @xmath1045 , and @xmath1046 , where @xmath1047 . consider first the case where @xmath1048 and @xmath1049 ( @xmath1050 may well equal @xmath1051 ) . pick @xmath1052 such that @xmath1053 , @xmath1054 , and @xmath1055 . this is without doubt possible by defining all other entries to be very unequal . because in the definition of the hubie - violator all tuples of @xmath1008 appear , there is @xmath892 with @xmath1056 . we have : @xmath1057 , @xmath1058 , @xmath1059 , and @xmath1060 . hence , @xmath1061 does not satisfy @xmath1041 , a contradiction . the case where @xmath1062 or @xmath1063 is even easier : say wlog @xmath1062 , and pick @xmath1064 such that @xmath1065 , and @xmath1066 . we have : @xmath1067 , @xmath1058 , @xmath1059 , and @xmath1068 . hence , in this case @xmath1069 does not satisfy @xmath1041 either , a contradiction .    finally , consider the case where neither @xmath1034 nor @xmath1035 are empty . assume wlog that @xmath1070 and @xmath1071 . we have @xmath1072 , for some @xmath1073 . let @xmath1074 be minimal with the property that @xmath1075 ; write @xmath1076 . then @xmath1077 for some @xmath1001 . pick @xmath1064 such that @xmath1078 . we then have that @xmath1040 does not satisfy @xmath1079 : indeed @xmath1080 , and @xmath1081 for all @xmath1082 as columns since @xmath1083 . a contradiction . it remains to show that @xmath284 satisfies @xmath1084 . suppose it does not ; we claim that under this assumption , there is @xmath892 such that @xmath1040 does not satisfy @xmath1084 either . set @xmath1085 to consist of all values that appear in @xmath284 , @xmath1032 , and @xmath1086 . write @xmath728 for the cardinality of @xmath1034 ; wlog we may assume @xmath1087 . observe that since @xmath284 has length @xmath737 and since it does not satisfy @xmath1084 , we have @xmath1088 . consider the @xmath1006-tuple @xmath1089 . using @xmath1090 , one readily checks that @xmath1091 , hence @xmath1092 for some @xmath892 . thus , since @xmath1093 appears in the @xmath347-th row of the definition of the hubie - violator @xmath1007 , we have that for all @xmath1094 and all @xmath1038 , if @xmath1095 , then @xmath1096 . in particular , this holds for the vectors @xmath1097 and @xmath1098 for which @xmath1099 , and we have @xmath1100 for those columns . but for the other columns @xmath1101 whose ( equal ) image under @xmath1007 is in @xmath1035 , we have @xmath1100 anyway since values outside @xmath219 are taken by at most one tuple . summarizing these two observations , we have that @xmath1102 for all @xmath1103 , so @xmath1040 does not satisfy @xmath1084 . a contradiction . we thus know that for all @xmath128 , @xmath241 has no pp - definition from @xmath1104 . for otherwise , the polymorphisms of @xmath1105 would be contained in those of @xmath241 , which is not the case by the preceding two lemmas . it remains to show that @xmath241 can not be defined from the @xmath1021 with @xmath1106 either . let @xmath1020 . then the hubie - violator @xmath1107 preserves @xmath241 . denote the arity of @xmath1107 by @xmath54 . as before , let @xmath1108 and set @xmath1109 . to see that @xmath284 satisfies the clauses @xmath1025 , one proceeds as in the preceding proof , with @xmath18 and @xmath45 exchanged . what is more difficult here is to check that @xmath284 satisfies @xmath1019 . suppose it does not , and define @xmath1110 , as well as @xmath1111 , as before ( only with @xmath18 and @xmath45 switched ) . now we distinguish two cases , @xmath1112 and @xmath1113 .    in the first case , we argue like at the end of the proof of the preceding lemma : consider the tuple @xmath1114 . one readily checks that @xmath1115 , so @xmath1092 for some @xmath892 . thus , since @xmath1093 appears in the @xmath347-th line of the definition of @xmath1107 , we have that for all @xmath1094 and all @xmath1038 , if @xmath1116 , then @xmath1096 . in particular , this holds for those vectors @xmath1097 and @xmath1098 which are sent by @xmath1107 to a value in @xmath1034 . since @xmath1117 for the other columns ( i.e. , those with value in @xmath1035 ) , this implies that @xmath1102 for all @xmath1118 , so @xmath1040 does not satisfy @xmath1019 , a contradiction . to finish the proof , consider the case where @xmath1113 . observe first that for every @xmath221 , there exists exactly one @xmath1118 such that @xmath1119 . there is at least one such @xmath277 as @xmath1113 ; suppose there were distinct @xmath1120 with this property . then @xmath1121 are all elements of @xmath1122 . pick any tuple @xmath1123 with @xmath1124 . we have that @xmath1125 are all equal , hence @xmath1040 does not satisfy @xmath1126 , a contradiction . we may therefore wlog assume that @xmath284 looks like this : @xmath1127 , where all entries starting from the question mark are elements of @xmath1035 . if we had @xmath1128 for some @xmath1129 , then we could derive a contradiction just like in the case @xmath1112 , by taking @xmath149 out of @xmath1034 . so assume this is not the case . then the set of vectors @xmath1130 equals @xmath1131 . we prove that there exists @xmath892 such that @xmath1040 does not satisfy @xmath1132 . let @xmath329 be the permutation on the indices of the tuple @xmath1133 which sends this tuple to @xmath1134 . observe that @xmath329 only switches @xmath1135 and @xmath1136 , if necessary . now consider the tuple @xmath1137 , and apply @xmath1138 to the indices of this tuple , obtaining a new tuple @xmath1139 . one readily checks @xmath1140 , so @xmath1141 for some @xmath1142 . thus the tuple @xmath1143 , which is obtained by applying @xmath329 to @xmath1144 , equals @xmath606 . but @xmath606 does not satisfy @xmath1132 , so @xmath1145 , a contradiction . we end this section by the following proposition , which completes the proof of theorem  [ thm : monoidalintervalofs ] and of the corollary after . the mapping @xmath329 from the power set of @xmath13 into @xmath1146 which sends every @xmath1147 to the local clone @xmath1148 is injective and antitone ( with respect to inclusion , on both sides ) . in particular , the number of local clones containing @xmath112 equals the continuum . since @xmath84 is antitone , it follows that the same holds for @xmath329 . now let @xmath1149 be unequal , say wlog that there is @xmath1150 . then the hubie - violator @xmath1151 violates @xmath1152 but preserves all @xmath1153 , where @xmath1154 . thus @xmath1155 , and @xmath329 is indeed injective . it remains to investigate one last monoidal interval , namely the one corresponding to the monoid @xmath167 consisting of all unary operations which are either injective or constant . we will thus be concerned with the proof of theorem  [ thm : monoidalintervalofsplusconst ] in this section . the crucial ingredients to the proof will be proposition  [ prop : rsantichain ] and the following lemma ; the definition of @xmath157 was given in definition  [ def : oddclone ] . [ lem : s+locallyclosed ] @xmath1156 . we have to show that @xmath1157 is a local clone . let @xmath1158 be an arbitrary non - constant operation . we claim that @xmath1159 . to see this , let @xmath63 be any finite subset of @xmath1160 , where @xmath45 is the arity of @xmath75 . extend @xmath63 to a finite set @xmath1161 such that @xmath75 is non - constant on @xmath1162 . since @xmath1158 , and since @xmath157 is by definition generated by @xmath158 , there exists a term @xmath275 using @xmath158 and the constants which agrees with @xmath75 on @xmath1162 . since @xmath275 is non - constant , it can as well be written without constants , using @xmath158 only : this is because inserting a constant as an argument of @xmath158 gives us an injection or essentially a bar operation , both of which are generated by @xmath158 without using constants . thus , @xmath75 can be interpolated on @xmath1162 , and hence also on @xmath63 , by a term in @xmath157 . this proves @xmath1159 . recall that @xmath24 consists of all operations which are injective in one direction ( definition  [ def : injectiveinonedirectionandrichard ] ) . whereas @xmath1157 is a local clone , we can not add constants to @xmath24 without generating all operations :    @xmath183 . let @xmath1163 be arbitrary , and let @xmath61 be finite . define @xmath1164 as follows : if @xmath1165 and @xmath1166 , then @xmath62 returns @xmath1167 . for every other input tuple , @xmath62 returns a unique value distinct from all other values in its range . clearly , @xmath62 is injective in the @xmath1168-st direction , so @xmath1169 . moreover , @xmath1170 agrees with @xmath75 on @xmath63 , implying @xmath1171 as @xmath63 was arbitrary . note that the preceding proposition proves item ( 7 ) of theorem  [ thm : monoidalintervalofsplusconst ] . we have found the largest element of our monoidal interval @xmath170 :    [ lem : s+isthelargest ] @xmath1172 . clearly , the unary fragment of @xmath1157 equals @xmath167 , hence @xmath1157 is an element of the corresponding monoidal interval @xmath170 . suppose there was a local clone @xmath47 in this interval which properly contains @xmath1157 . take any @xmath1173 . clearly , @xmath75 must be essential . since the only non - injections in the unary fragment of @xmath47 are constant , lemma  [ lem : s5:haddadrosenberg : forinfinite ] implies that @xmath75 must have infinite range . by proposition  [ prop : s5:essentialwithinfiniteimagepreservesneq ] , @xmath75 preserves @xmath162 . thus , @xmath1174 , so @xmath75 generates @xmath24 by proposition  [ prop : rsantichain ] . hence @xmath1175 by the preceding proposition . the following proposition proves statement ( 1 ) of theorem  [ thm : monoidalintervalofsplusconst ] . . then @xmath1176 . in particular , @xmath173 is a local clone in @xmath159 .    by lemma  [ lem : s+isthelargest ] , @xmath47 is a subclone of @xmath1157 ; hence intersecting @xmath47 with @xmath157 just means taking away the constants , which proves our assertion . since the intersection of local clones is a local clone , so is @xmath173 . clearly , the unary fragment of @xmath173 equals @xmath137 , hence @xmath173 is an element of @xmath159 . observe that the second statement of the theorem is trivial . we turn to the proof of item  ( 3 ) . the mapping from @xmath170 into the subinterval @xmath176 $ ] of @xmath159 which sends every clone @xmath47 to @xmath173 is a complete lattice embedding which preserves the smallest and the largest element . it is clear that this mapping preserves the order and by the second statement of theorem  [ thm : monoidalintervalofsplusconst ] , it sends the smallest ( largest ) element of @xmath170 to the smallest ( largest ) element of @xmath176 $ ] . it is also obvious that the mapping is injective . let @xmath177 . clearly , @xmath1177 , hence the mapping preserves finite meets ; larger meets work the same way . since @xmath1178 contains both @xmath173 and @xmath1179 , it contains also their join , so @xmath1180 . for the other inclusion , let @xmath75 be any non - constant operation in the ( not necessarily local ) clone generated by @xmath1181 . then @xmath75 can be written as a term over @xmath1181 . we can assume that in this term , thinking of it as a tree , the constants appear only as leaves . we may also assume that except for leaves , no subtree of this tree is constant . that just means that the nodes above the leaves are operation symbols in @xmath1182 , some of whose variables are set to constant values . but these operations in @xmath1182 with some variables set to constants are again elements of @xmath1182 , as they are non - constant by assumption and since @xmath47 and @xmath1183 are clones containing all constants . summarizing , we can write @xmath75 as a term over @xmath1182 without the use of constants . hence , @xmath1184 . this proves @xmath1185 , and hence our mapping preserves finite joins . infinite joins work the same way . observe that item ( 4 ) of theorem  [ thm : monoidalintervalofsplusconst ] is clear from the definitions . we prove ( 5 ) .    for all @xmath180 which do not contain @xmath24 , @xmath181 is a local clone in @xmath170 .    by proposition  [ prop : rsantichain ] , @xmath47 is contained in @xmath157 . hence , @xmath181 is contained in @xmath1157 by lemma  [ lem : s+locallyclosed ] , which equals @xmath1186 by lemma  [ lem : s+isthelargest ] . therefore @xmath181 is indeed a local clone in @xmath170 .    item ( 6 ) is trivial from the definitions . we finish the proof of the theorem by the following proposition , which restates items ( 8) and ( 9 ) :    @xmath184 is the unique cover of @xmath185 and @xmath186 is the unique cover of @xmath184 in @xmath170 . let @xmath47 be in @xmath170 , and assume it has an essential operation @xmath75 . then @xmath1159 by lemma  [ lem : s+isthelargest ] , thus @xmath75 generates @xmath139 by proposition  [ prop : hornchar ] . it is easy to see that @xmath184 is a local clone , which proves the first assertion . similarly , if @xmath47 is in @xmath170 and properly contains @xmath184 , then any operation witnessing this generates @xmath147 , by proposition  [ prop : barchar ] . again , it is straightforward to check that @xmath186 is a local clone . we want to close this section with the remark that the mapping which sends every clone @xmath47 in the interval @xmath176 $ ] of @xmath159 to @xmath181 is not injective . in particular , it collapses all clones between @xmath1187 and @xmath157 . [ prop:+notinjective ] @xmath1188    the operation @xmath1189 ( definition  [ def : gk ] ) is injective in the first argument , and hence contained in @xmath24 . by lemma 59 , @xmath1189 preserves @xmath1190 , and , being an element of @xmath24 , it also preserves @xmath162 . proposition  [ prop : schar ] then implies that @xmath1189 is contained in @xmath157 : otherwise , it would violate a relation preserved by @xmath157 ; that relation would have a pp definition from @xmath1190 and @xmath162 , a contradiction . therefore , the operation @xmath1189 is in @xmath1187 . the operation given by @xmath1191 equals by definition the operation @xmath158 ( definition  [ def : oddclone ] or [ def : fk ] ) , which by definition generates @xmath157 . hence , @xmath1192 contains @xmath1157 . the converse containment is trivial . observe that this proposition implies that the complete lattice embedding that sends every @xmath172 to @xmath173 is not surjective onto the interval @xmath176 $ ] : if there existed a clone @xmath172 such that @xmath1193 , then @xmath1194 since @xmath182 . thus @xmath1195 would be a clone and hence equal to @xmath1157 , implying @xmath1196 , a contradiction . in fact the same argument shows that a clone @xmath1197 $ ] is in the range of this embedding iff @xmath1198 is a clone . we have to leave the complete description of the monoidal intervals corresponding to @xmath137 and @xmath167 open ; we do not know if a reasonable description of these intervals is possible at all . two particular problems seem most important to us at this point :    * can one effectively decide whether for a given sequence @xmath1199 of relations that are first - order definable in @xmath1200 there is a pp - definition of @xmath1201 in the structure @xmath1202 ? * what is the cardinality of the monoidal interval corresponding to @xmath167 ? m.  bodirsky and j.  kra . the complexity of equality constraint languages . , 3(2):136158 , 2008 . a conference version of the paper appeared in the proceedings of the international computer science symposium in russia ( csr06 ) .
we initiate the study of reducts of relational structures up to primitive positive interdefinability : after providing the tools for such a study , we apply these tools in order to obtain a classification of the reducts of the logic of equality . 
 it turns out that there exists a continuum of such reducts . 
 equivalently , expressed in the language of universal algebra , we classify those locally closed clones over a countable domain which contain all permutations of the domain .