Abstract
A clonoid is a set of finitary functions from a set A to a set B that is closed under taking minors. Hence clonoids are generalizations of clones. By a classical result of Post, there are only countably many clones on a 2-element set. In contrast to that, we present continuum many clonoids for \(A = B = \{0,1\}\). More generally, for any finite set A and any 2-element algebra \({\mathbf {B}}\), we give the cardinality of the set of clonoids from A to \({\mathbf {B}}\) that are closed under the operations of \({\mathbf {B}}\). Further, for any finite set A and finite idempotent algebra \({\mathbf {B}}\) without a cube term (with \(|A|,|B|\ge 2\)) there are continuum many clonoids from A to \({\mathbf {B}}\) that are closed under the operations of \({\mathbf {B}}\); if \({\mathbf {B}}\) has a cube term there are countably many such clonoids.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aichinger, E., Mayr, P.: Finitely generated equational classes. J. Pure Appl. Algebra 220, 2816–2827 (2016)
Baker, K.A., Pixley, A.F.: Polynomial interpolation and the Chinese remainder theorem for algebraic systems. Math. Z. 143, 165–174 (1975)
Brakensiek, J., Guruswami, V.: Promise constraint satisfaction structure theory and a symmetric Boolean dichotomy. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1782–1801. SIAM, Philadelphia, PA (2018)
Bulatov, A.: On the number of finite Mal’tsev algebras. Contributions to General Algebra. 13 (Velké Karlovice, 1999/Dresden, 2000), pp. 41–54. Heyn, Klagenfurt (2001)
Foster, A.L.: The identities of–and unique subdirect factorization within–classes of universal algebras. Math. Z. 62, 171–188 (1955)
Lau, D.: Function Algebras on Finite Sets. A Basic Course on Many-Valued Logic and Clone Theory. Springer Monographs in Mathematics. Springer, Berlin (2006)
Marković, P., Maróti, M., McKenzie, R.: Finitely related clones and algebras with cube terms. Order 29, 345–359 (2012)
Pippenger, N.: Galois theory for minors of finite functions. Discrete Math. 254, 405–419 (2002)
Acknowledgements
The author thanks Peter Mayr for discussions on the material in this paper and the anonymous referee for their comments and asking a question that led to Theorem 1.4.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This material is based upon work supported by the National Science Foundation under Grant No. DMS 1500254.
Rights and permissions
About this article
Cite this article
Sparks, A. On the number of clonoids. Algebra Univers. 80, 53 (2019). https://doi.org/10.1007/s00012-019-0629-x
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00012-019-0629-x