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.     

Finite degree: algebras in general and semigroups in particular

An algebra A has finite degree if its term functions are determined by some finite set of finitary relations on A. We study this concept for finite algebras in general and for finite semigroups in particular. For example, we show that every finite nilpotent semigroup has finite degree (more generally, every finite algebra with bounded p _n -sequence), and every finite commutative semigroup has finite degree. We give an example of a five-element unary semigroup that has infinite degree. We also give examples to show that finite degree is not preserved in general under taking subalgebras, homomorphic images, direct products or subdirect factors.     

On a strong property of the weak subalgebra lattice

In the present paper, we apply results from [Pió1] to prove that for an arbitrary total and locally finite unary algebra A of finite unary type K, its weak subalgebra lattice uniquely determines its strong subalgebra lattice (recall that in the case of total algebras the strong subalgebra lattice is the well-known lattice of all (total) subalgebras). More precisely, we prove that for every unary partial algebra B of the same unary type K, if weak subalgebra lattices of A and B are isomorphic (with A as above), then the strong subalgebra lattices of A and B are isomorphic, and moreover B is also total and locally finite. At the end of this paper we also show the necessity of all the three conditions for A. Received September 5, 1997; accepted in final form October 7, 1998.     

Finite Intervals in the Lattice of Topologies

We discuss the question whether every finite interval in the lattice of all topologies on some set is isomorphic to an interval in the lattice of all topologies on a finite set – or, equivalently, whether the finite intervals in lattices of topologies are, up to isomorphism, exactly the duals of finite intervals in lattices of quasiorders. The answer to this question is in the affirmative at least for finite atomistic lattices. Applying recent results about intervals in lattices of quasiorders, we see that, for example, the five-element modular but non-distributive lattice cannot be an interval in the lattice of topologies. We show that a finite lattice whose greatest element is the join of two atoms is an interval of T ₀-topologies iff it is the four-element Boolean lattice or the five-element non-modular lattice. But only the first of these two selfdual lattices is an interval of orders because order intervals are known to be dually locally distributive.     

Congruences of Clone Lattices, II

We continue the study of congruences of clone lattices _A , where A is finite, started in an earlier paper by the author and A. P. Semigrodskikh. We prove that each clone that either contains all unary operations or consists of essentially unary operations forms a one-element class of any non-trivial congruence of _A . As a consequence, we get that _A has the greatest non-trivial congruence provided the lattice is not simple, that _A is directly indecomposable, and that it has neither distributive nor dually distributive elements except for the trivial ones.For |A|>2, no example of a non-trivial congruence is known so far. We exhibit some reasons why such congruences are not easy to find.     

Hyperidentities of quasilinear clones on the three-element set

Under study is the possibility of distinguishing by formulas the clones of quasilinear functions on the three-element set. We find a distinguishing formula for every pair of the nonisomorphic clones of this type without creative functions and indicate the pairs of clones indistinguishable by hyperidentities with unary function variables.     

Minimally Supported Frequency Composite Dilation Parseval Frame Wavelets

A composite dilation Parseval frame wavelet is a collection of functions generating a Parseval frame for L ²(ℝ ⁿ ) under the actions of translations from a full rank lattice and dilations by products of elements of groups A and B. A minimally supported frequency composite dilation Parseval frame wavelet has generating functions whose Fourier transforms are characteristic functions of sets contained in a lattice tiling set. Constructive proofs are used to establish the existence of minimally supported frequency composite dilation Parseval frame wavelets in arbitrary dimension using any finite group B, any full rank lattice, and an expanding matrix generating the group A and normalizing the group B. Moreover, every such system is derived from a Parseval frame multiresolution analysis. Multiple examples are provided including examples that capture directional information.      

Binary homomorphisms and natural dualities

We investigate ways in which certain binary homomorphisms of a finite algebra can guarantee its dualisability. Of particular interest are those binary homomorphisms which are lattice, flat-semilattice or group operations. We prove that a finite algebra which has a pair of lattice operations amongst its binary homomorphisms is dualisable. As an application of this result, we find that every finite unary algebra can be embedded into a dualisable algebra. We develop some general tools which we use to prove the dualisability of a large number of unary algebras. For example, we show that the endomorphisms of a finite cyclic group are the operations of a dualisable unary algebra.     

Intervals in lattices of quasiorders

We investigate the structure of intervals in the lattice of all closed quasiorders on a compact or discrete space. As a first step, we show that if the intervalI has no infinite chains then the underlying space may be assumed to be finite, and in particular,I must be finite, too. We compute several upper bounds for its size in terms of its heighth, which in turn can be computed easily by means of the least and the greatest element ofI. The cover degreec of the interval (i.e. the maximal number of atoms in a subinterval) is less than 4h. Moreover, ifc4(n–1) thenI contains a Boolean subinterval of size 2 ⁿ , and ifI is geometric then it is already a finite Boolean lattice. While every finite distributive lattice is isomorphic to some interval of quasiorders, we show that a nondistributive finite interval of quasiorders is neither a vertical sum nor a horizontal sum of two lattices, with exception of the pentagon. Many further lattices are excluded from the class of intervals of quasiorders by the fact that no join-irreducible element of such an interval can have two incomparable join-irreducible complements. Up to isomorphism, we determine all quasiorder intervals with less than 9 elements and all quasiorder intervals with two complementary atoms or coatoms.     

Laws of the lattices of partially composition formations

We prove that every law of the lattice of all formations of finite groups is fulfilled in the lattice of all n-multiply ω-composition formations of finite groups for every nonempty set of primes ω and every natural n.     

Generalizing semidistributivity

A latticeL is called congruence normal if it can be generated by doubling of convex sets starting with the one-element lattice. In the special case of intervals, the lattice is called bounded. It has been proven thatL is bounded if and only ifL is congruence normal and semidistributive.In this paper we study the connection between certain classes of convex sets and generalized semidistributive laws. These so-called doubling classes are pseudovarieties which can be described by implications as well as by forbiden substructures. In the end, we examine the structure of the lattice of all doubling classes.     

On homogeneous extensions of finite predicate systems

It is shown that any finite n-element predicate system for which any two one-element subsystems are isomorphic is embeddable in a finite (2 ⁿ − 1)-element system having a transitive automorphism group.     

The Maximal Closed Classes of Unary Functions in p-Valued Logic

In many-valued logic the decision of functional completeness is a basic and important problem, and the thorough solution to this problem depends on determining all maximal closed sets in the set of many-valued logic functions. It includes three famous problems, i.e., to determine all maximal closed sets in the set of the total, of the partial and of the unary many-valued logic functions, respectively. The first two problems have been completely solved ([1], [2], [8]), and the solution to the third problem boils down to determining all maximal subgroups in the k-degree symmetric group S_k, which is an open problem in the finite group theory. In this paper, all maximal closed sets in the set of unary p-valued logic functions are determined, where p is a prime. Mathematics Subject Classification: 03B50, 20B35.     

Minimally Supported Frequency Composite Dilation Wavelets

A composite dilation wavelet is a collection of functions generating an orthonormal basis for L ²(ℝ ⁿ ) under the actions of translations from a full rank lattice and dilations by products of elements of non-commuting groups A and B. A minimally supported frequency composite dilation wavelet has generating functions whose Fourier transforms are characteristic functions of a lattice tiling set. In this paper, we study the case where A is the group of integer powers of some expanding matrix while B is a finite subgroup of the invertible n×n matrices. This paper establishes that with any finite group B together with almost any full rank lattice, one can generate a minimally supported frequency composite dilation wavelet system. The paper proceeds by demonstrating the ability to find such minimally supported frequency composite dilation wavelets with a single generator.     

Congruences on ockham algebras with pseudocomplementation

The variety pOconsists of those algebras (L;?,?,f,^*,0,1) where (L;?,?,f,0,1) is an Ockham algebra, (L;?,?,f,^*,0,1) is a p-algebra, and the unary operations fand ^*. commute. For an algebra in pK _ωwe show that the compact congruences form a dual Stone lattice and use this to determine necessary and sufficient conditions for a principal congruence to be complemented. We also describe the lattice of subvarieties of pK _1,1identifying therein the biggest subvariety in which every principal congruence is complemented, and the biggest subvariety in which the intersection of two principal congruences is principal.     

Stability Constants in Linear Spaces

We investigate the stability constants of convex sets in linear spaces. We prove that the stability constants of affinity and of the Jensen equation are of the same order of magnitude for every convex set in arbitrary linear spaces, even for functions mapping into an arbitrary Banach space. We also show that the second Whitney constant corresponding to the bounded functions equals half of the stability constant of the Jensen equation whenever the latter is finite. We show that if a convex set contains arbitrarily long segments in every direction, then its Jensen and Whitney constants are uniformly bounded. We prove a result that reduces the investigation of the stability constants to the case when the underlying set is the unit ball of a Banach space. As an application we prove that if D is convex and every δ-Jensen function on D differs from a Jensen function by a bounded function, then the stability constants of D are finite.     

Smooth Groups

A group is called smooth if it has a finite maximal chain of subgroups in which any two intervals of the same length are isomorphic (as lattices). We show that every finite smooth group G is a semidirect product of a p-group by a cyclic group; in particular, G is soluble. We determine the exact structure of G if G is not a p-group.