Closed classes of functions, generalized constraints, and clusters

DOI10.1007/S00012-010-0071-6MaRDI QIDQ607451zbMATH OpenOpenAlexFDO

Authors Erkko Lehtonen

Publication date 22 November 2010

Published in Algebra Universalis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0810.3212

zbMATH Keywords

clonesclosed setclusterfunction algebraGalois connectioniterative algebra

Mathematics Subject Classification ID

Galois correspondences, closure operators (in relation to ordered sets) (06A15) Operations and polynomials in algebraic structures, primal algebras (08A40)

Abstract: Classes of functions of several variables on arbitrary non-empty domains that are closed under permutation of variables and addition of dummy variables are characterized in terms of generalized constraints, and hereby Hellerstein's Galois theory of functions and generalized constraints is extended to infinite domains. Furthermore, classes of operations on arbitrary non-empty domains that are closed under permutation of variables, addition of dummy variables and composition are characterized in terms of clusters, and a Galois connection is established between operations and clusters.

Review text

For a fixed base set \(A\), the maps \(f : A^n \rightarrow A\) can also be regarded as operations on \(A\). Let \({\mathcal O}_A\) be the set of all operations on \(A\). Mal'tsev introduced five types of operations on the set \({\mathcal O}_A\): two kinds of permutation of variables (denoted \(\zeta\), \(\tau\)), identification of variables or diagonalization (denoted \(\Delta\)), addition of a dummy variable or cylindrification (denoted \(\nabla\)) and composition (\(*\)). The algebra \(({\mathcal O}_A, \{\zeta, \tau, \Delta, \nabla, * \})\) is called the full iterative algebra on \(A\); its subalgebras are called iterative algebras on \(A\). Clones are iterative algebras that contain all projections. The ``preservation relation between operations and relations on \(A\) induces a Galois connection whose closed operations are exactly the clones of \(A\). The first part of this paper presents existing results on classes of functions that are closed under only some of the iterative algebra operations, and on a Galois theory developed for these variants to describe the closed classes in terms of a ``preservation relation between functions and some ``dual objects which in this case are more general than relations. In addition, the authors describe the classes of operations on arbitrary nonempty sets \(A\) that are closed under the iterative algebra operations except for the identification of variables. They show that the classes of operations on \(A\) that contain all projections and are closed under this subset of operations are precisely the closed classes of the Galois connection induced by the ``preservation relation between operations and clusters (downward closed sets of multisets of \(m\)-tuples on \(A\)). They also describe the Galois closed classes of clusters as classes that are closed under certain operators (conjunctive mirrors, unions, quotients, dividends).

Recommendations

• On generalized cluster sets of functions and multifunctions
• On closed sets of relational constraints and classes of functions closed under variable substitutions
• Generalized cluster sets of real functions
• On the closed form of Clausen functions
• A class of generalized close-to-convex functions
• On composition closed function classes
• A generalized class of close-to-convex functions
• scientific article; zbMATH DE number 3973793
• GENERALIZED CONVEXITY AND CLOSURE CONDITIONS
• scientific article; zbMATH DE number 908067

Cites work

• Closed systems of functions and predicates
• Function Algebras on Finite Sets
• Galois theory for minors of finite functions
• scientific article; zbMATH DE number 3968584 (Why is no real title available?)
• scientific article; zbMATH DE number 2118880 (Why is no real title available?)
• On closed sets of relational constraints and classes of functions closed under variable substitutions
• On generalized constraints and certificates

Cited in

(13)

• Closed sets of finitary functions between products of finite fields of coprime order
• Closed sets of finitary functions between finite fields of coprime order
• On closed sets of relational constraints and classes of functions closed under variable substitutions
• Characterization of preclones by matrix collections
• Galois theory for semiclones
• scientific article; zbMATH DE number 4218123 (Why is no real title available?)
• Galois theory for sets of operations closed under permutation, cylindrification, and composition
• scientific article; zbMATH DE number 1522671 (Why is no real title available?)
• Closed function sets on groups of prime order
• A complete classification of equational classes of threshold functions included in clones
• Characterization of sets of discrete functions by algebraic identities
• Galois theory for analogical classifiers
• Cluster structures and collections of Galois closed entity subsets

This page was built for publication: Closed classes of functions, generalized constraints, and clusters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q607451)