Minimal clones—a minicourse

This paper provides an elementary introduction to minimal clones, as well as a survey of recent trends and results. Received September 27, 2002; accepted in final form October 10, 2002.     

Homomorphisms of direct powers of algebras

We give an example of n-coconnected algebra that is not (n+1)-coconnected, for any n ≥ 2. Received June 8, 2005; accepted in final form August 28, 2005.     

Measurement structures with archimedean ordered translation groups

The paper focuses on three problems of generalizing properties of concatenation structures (ordered structures with a monotonic operation) to ordered structures lacking any operation. (1) What is the natural generalization of the idea of Archimedeaness, of commensurability between large and small? (2) What is the natural generalization of the concept of a unit concatenation structure in which the translations (automorphisms with no fixed point) can be represented by multiplication by a constant? (3) What is the natural generalization of a ratio scale concatenation structure being distributive in a conjoint one, which has been shown to force a multiplicative representation of the latter and the product-of-powers representation of units found in physics? It is established (Theorems 5.1 and 5.2) that for homogeneous structures, the latter two questions are equivalent to it having the property that the set of all translations forms a homogeneous Archimedean ordered group. A sufficient condition for Archimedeaness of the translations is that they form a group, which is equivalent to their being 1-point unique, and the structure be Dedekind complete and order dense (Theorems 2.1 and 2.2). It is suggested that Archimedean order of the translations is, indeed, also the answer to the first question. As a lead into that conclusion, a number of results are reported in Section 3 on Archimedeaness in concatenation structures, including for positive structures sufficient conditions for several different notions of Archimedeaness to be equivalent. The results about idempotent structures are fragmentary.     

Relations compatible with near unanimity operations

Given a system of k-ary relations on a finite set A which are compatible with a (k + 1)-ary near unanimity operation on A, we provide a characterization of when is the system of all k-ary subuniverses of an algebra A on A.In Celebration of the Sixtieth Birthday of Ralph N. McKenzieReceived August 26, 2003; accepted in final form July 10, 2004.     

Maximal clones on uncountable sets that include all permutations

We first determine the maximal clones on a set X of infinite regular cardinality κ which contain all permutations but not all unary functions, extending a result of Heindorf’s for countably infinite X. If κ is countably infinite or weakly compact, this yields a list of all maximal clones containing the permutations, since in that case the maximal clones above the unary functions are known. We then generalize a result of Gavrilov’s to obtain on all infinite X a list of all maximal submonoids of the monoid of unary functions which contain the permutations. Received January 8, 2004; accepted in final form December 22, 2004.     

Weakly diagonal algebras and definable principal congruences

An algebra is called weakly diagonal if every subuniverse of its square contains the graph of an automorphism. We show that every variety generated by a finite algebra with no proper subalgebras has a weakly diagonal generator. The result is applied in several ways and, in particular, to show that every arithmetical affine complete variety of finite type has equationally definable principal congruences. This paper is dedicated to Walter Taylor. Received February 22, 2005; accepted in final form June 3, 2005. Work of the first author was supported by grant No. 5368 from The Estonian Science Foundation.     

Many-sorted algebras in congruence modular varieties

We present several basic results on many-sorted algebras, most of them only valid in congruence modular varieties. We describe a connection between the properties of many-sorted varieties and those of varieties of one sort and give some results on functional completeness, the commutator and Abelian algebras.Presented by H. P. Gumm.     

Valuations of terms

Let be a type of algebras. There are several commonly used measurements of the complexity of terms of type , including the depth or height of a term and the number of variable symbols appearing in a term. In this paper we formalize these various measurements, by defining a complexity or valuation mapping on terms. A valuation of terms is thus a mapping from the absolutely free term algebra of type into another algebra of the same type on which an order relation is defined. We develop the interconnections between such term valuations and the equational theory of Universal Algebra. The collection of all varieties of a given type forms a complete lattice which is very complex and difficult to study; valuations of terms offer a new method to study complete sublattices of this lattice.     

A characterization of k-normal varieties

Let v be a valuation of terms of type , assigning to each term t of type a value v(t) 0. Let k 1 be a natural number. An identity of type is called k-normal if either s = t or both s and t have value k, and otherwise is called non-k-normal. A variety V of type is said to be k-normal if all its identities are k-normal, and non-k-normal otherwise. In the latter case, there is a unique smallest k-normal variety to contain V , called the k-normalization of V. Inthe case k = 1, for the usual depth valuation of terms, these notions coincide with the well-known concepts of normal identity, normal variety, and normalization of a variety. I. Chajda has characterized the normalization of a variety by means of choice algebras. In this paper we generalize his results to a characterization of the k-normalization of a variety, using k-choice algebras. We also introduce the concept of a k-inflation algebra, and for the case that v is the usual depth valuation of terms, we prove that a variety V is k-normal iff it is closed under the formation of k-inflations, and that the k-normalization of V consists precisely of all homomorphic images of k-inflations of algebras in V .     

Monoidal intervals of clones on infinite sets

Let X be an infinite set of cardinality κ. We show that if L is an algebraic and dually algebraic distributive lattice with at most 2^κ completely join irreducibles, then there exists a monoidal interval in the clone lattice on X which is isomorphic to the lattice 1+L obtained by adding a new smallest element to L. In particular, we find that if L is any chain which is an algebraic lattice, and if L does not have more than 2^κ completely join irreducibles, then 1+L appears as a monoidal interval; also, if λ?2^κ, then the power set of λ with an additional smallest element is a monoidal interval. Concerning cardinalities of monoidal intervals these results imply that there are monoidal intervals of all cardinalities not greater than 2^κ, as well as monoidal intervals of cardinality 2^λ, for all λ?2^κ.     

On subtractive varieties,I

A varietyV is subtractive if it obeys the laws s(x, x)=0, s(x, 0)=x for some binary terms and constant 0. This means thatV has 0-permutable congruences (namely [0]R ºS=[0]S ºR for any congruencesR, S of any algebra inV). We present the basic features of such varieties, mainly from the viewpoint of ideal theory. Subtractivity does not imply congruence modularity, yet the commutator theory for ideals works fine. We characterize i-Abelian algebras, (i.e. those in which the commutator is identically 0). In the appendix we consider the case of a classical ideal theory (comprising: groups, loops, rings, Heyting and Boolean algebras, even with multioperators and virtually all algebras coming from logic) and we characterize the corresponding class of subtractive varieties.Presented by A. F. Pixley.     

A local proof for a tolerance intersection property

Congruence modular varieties satisfy a very useful tolerance identity, called TIP. We show that it is enough to suppose that all subalgebras of A⁴ satisfy the Shifting Lemma in order to obtain that A satisfies a tolerance identity slightly weaker than TIP. Received October 15, 2004; accepted in final form April 12, 2005.     

On closed sets of relational constraints and classes of functions closed under variable substitutions

Pippenger’s Galois theory of finite functions and relational constraints is extended to the infinite case. The functions involved are functions of several variables on a set A and taking values in a possibly different set B, where any or both of A and B may be finite or infinite. Received April 30, 2004; accepted in final form February 8, 2005.     

Positive primitive formulas preventing enough algebraic operations

A finite unary algebra with a positive primitive formula defining a pp-acyclic relation does not have enough algebraic operations and does not have a finite basis for its quasi-equations.In Celebration of the Sixtieth Birthday of Ralph N. McKenzieReceived June 17, 2003; accepted in final form August 12, 2004.     

Prime spectra in modular varieties

By using the concept of modular commutator, prime congruences are defined for algebras in modular varieties. Then the prime spectrum of an algebra is defined and various spectral properties are discussed. In particular some conditions are given for the spectrum of an algebra to be homeomorphic to a ring spectrum.Presented by A. F. Pixley.     

Congruence lattices of locally finite algebras

It is shown that there exist algebraic lattices that cannot be represented as the congruence lattice of a locally finite algebra. Received August 11, 2004; accepted in final form January 6, 2005.     

Monotone clones and the varieties they determine

A finite, nontrivial algebra is order-primal if its term functions are precisely the monotone functions for some order on the underlying set. We show that the prevariety generated by an order-primal algebra P is relatively congruence-distributive and that the variety generated by P is congruence-distributive if and only if it contains at most two non-ismorphic subdirectly irreducible algebras. We also prove that if the prevarieties generated by order-primal algebras P and Q are equivalent as categories, then the corresponding orders or their duals generate the same order variety. A large class of order-primal algebras is described each member of which generates a variety equivalent as a category to the variety determined by the six-element, bounded ordered set which is not a lattice. These results are proved by considering topological dualities with particular emphasis on the case where there is a monotone near-unanimity function.This research was carried out while the third author held a research fellowship at La Trobe University supported by ARGS grant B85154851. The second author was supported by a grant from the NSERC.     

Unary operations with long pre-periods

It is well known that the congruence lattice ConA of an algebra A is uniquely determined by the unary polynomial operations of A (see e.g. [K. Denecke, S.L. Wismath, Universal Algebra and Applications in Theoretical Computer Science, Chapman & Hall, CRC Press, Boca Raton, London, New York, Washington DC, 2002 [2]]). Let A be a finite algebra with |A|=n. If Imf=A or |Imf|=1 for every unary polynomial operation f of A, then A is called a permutation algebra. Permutation algebras play an important role in tame congruence theory [D. Hobby, R. McKenzie, The structure of finite algebras, Contemporary Mathematics, vol. 76, Providence, Rhode Island, 1988 [3]]. If f:A→A is not a permutation then A⊃Imf and there is a least natural number λ(f) with Imf^λ(f)=Imf^λ(f)+1. We consider unary operations with λ(f)=n-1 for n?2 and λ(f)=n-2 for n?3 and look for equivalence relations on A which are invariant with respect to such unary operations. As application we show that every finite group which has a unary polynomial operation with one of these properties is simple or has only normal subgroups of index 2.