×

On the number of finite algebraic structures. (English) Zbl 1432.08001

Summary: We prove that every clone of operations on a finite set \(A\), if it contains a Malcev operation, is finitely related – i.e., identical with the clone of all operations respecting \(R\) for some finitary relation \(R\) over \(A\). It follows that for a fixed finite set \(A\), the set of all such Malcev clones is countable. This completes the solution of a problem that was first formulated in 1980, or earlier: how many Malcev clones can finite sets support? More generally, we prove that every finite algebra with few subpowers has a finitely related clone of term operations. Hence modulo term equivalence and a renaming of the elements, there are only countably many finite algebras with few subpowers, and thus only countably many finite algebras with a Malcev term.

MSC:

08A40 Operations and polynomials in algebraic structures, primal algebras
08B05 Equational logic, Mal’tsev conditions
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aichinger, E.: Constantive Mal’cev clones on finite sets are finitely related. Proc. Amer. Math. Soc. 138, 3501-3507 (2010) · Zbl 1215.08002 · doi:10.1090/S0002-9939-2010-10395-7
[2] Aichinger, E., Mudrinski, N.: Polynomial clones of Mal’cev algebras with small congruence lattices. Acta Math. Hungar. 126, 315-333 (2010) · Zbl 1274.08012 · doi:10.1007/s10474-009-9068-z
[3] Baker, K. A., Pixley, A. F.: Polynomial interpolation and the Chinese remainder theorem for algebraic systems. Math. Z. 143, 165-174 (1975) · Zbl 0292.08004 · doi:10.1007/BF01187059
[4] Barto, L.: Finitely related algebras in congruence distributive algebras have near una- nimity terms. Canad. J. Math. 65, 3-21 (2013) · Zbl 1283.08009 · doi:10.4153/CJM-2011-087-3
[5] Berman, J., Idziak, P., Marković, P., McKenzie, R., Valeriote, M., Willard, R.: Vari- eties with few subalgebras of powers. Trans. Amer. Math. Soc. 362, 1445-1473 (2010) · Zbl 1190.08004 · doi:10.1090/S0002-9947-09-04874-0
[6] Bulatov, A.: On the number of finite Mal’tsev algebras. In: Contributions to General Algebra, 13 (Velké Karlovice, 1999/Dresden, 2000), Heyn, Klagenfurt, 41-54 (2001) · Zbl 0986.08003
[7] Bulatov, A., Dalmau, V.: A simple algorithm for Mal’tsev constraints. SIAM J. Comput. 36, 16-27 (2006) · Zbl 1112.08002 · doi:10.1137/050628957
[8] Burris, S., Sankappanavar, H. P.: A Course in Universal Algebra. Springer, New York (1981) · Zbl 0478.08001
[9] Higman, G.: Ordering by divisibility in abstract algebras. Proc. London Math. Soc. (3) 2, 326-336 (1952) · Zbl 0047.03402 · doi:10.1112/plms/s3-2.1.326
[10] Hobby, D., McKenzie, R.: The Structure of Finite Algebras. Contemp. Math. 76, Amer. Math. Soc. (1988) · Zbl 0721.08001
[11] Idziak, P. M.: Clones containing Mal’tsev operations. Int. J. Algebra Comput. 9, 213- 226 (1999) · Zbl 1023.08003 · doi:10.1142/S021819679900014X
[12] Idziak, P., Marković, P., McKenzie, R., Valeriote, M., Willard, R.: Tractability and learnability arising from algebras with few subpowers. In: Proc. 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), 221-230 (2007) · Zbl 1216.68129 · doi:10.1137/090775646
[13] Janov, J. I., Mu\check cnik, A. A.: Existence of k-valued closed classes without a finite basis. Dokl. Akad. Nauk SSSR 127, 44-46 (1959) (in Russian) · Zbl 0100.01001
[14] Kearnes, K. A., Szendrei, Á.: Clones of finite groups. Algebra Universalis 54, 23-52 (2005) · Zbl 1114.20014 · doi:10.1007/s00012-005-1919-z
[15] Kearnes, K. A., Szendrei, Á.: Clones of algebras with parallelogram terms. Int. J. Al- gebra Comput. 22, no. 1, 1250005, 30 pp. (2012) · Zbl 1286.08002 · doi:10.1142/S0218196711006716
[16] Kiss, E. W., Pröhle, P.: Problems and results in tame congruence theory. A survey of the ’88 Budapest Workshop. Algebra Universalis 29, 151-171 (1992) · Zbl 0759.08003 · doi:10.1007/BF01190604
[17] Kozik, M.: A finite set of functions with an EXPTIME-complete composition problem. Theoret. Comput. Sci. 407, 330-341 (2008) · Zbl 1152.68023 · doi:10.1016/j.tcs.2008.06.057
[18] Laver, R.: Well-quasi-orderings and sets of finite sequences. Math. Proc. Cambridge Philos. Soc. 79, 1-10 (1976) · Zbl 0405.06001 · doi:10.1017/S030500410005204X
[19] Mal’cev, A. I.: On the general theory of algebraic systems. Mat. Sb. (N.S.) 35(77), 3-20 (1954) (in Russian) · Zbl 0057.02403
[20] Marković, P., McKenzie, R.: Few subpowers, congruence distributivity and near- unanimity terms. Algebra Universalis 58, 119-128 (2008) · Zbl 1155.08001 · doi:10.1007/s00012-008-2049-1
[21] Mayr, P.: Polynomial clones on squarefree groups. Int. J. Algebra Comput. 18, 759-777 (2008) · Zbl 1147.08003 · doi:10.1142/S0218196708004597
[22] Mayr, P.: Mal’cev algebras with supernilpotent centralizers. Algebra Universalis 65, 193-211 (2011) · Zbl 1219.08001 · doi:10.1007/s00012-011-0124-5
[23] McKenzie, R. N., McNulty, G. F., F. Taylor, W.: Algebras, Lattices, Varieties, Vol. I. Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA (1987) · Zbl 0611.08001
[24] Nash-Williams, C. St. J. A.: On well-quasi-ordering finite trees. Proc. Cambridge Philos. Soc. 59, 833-835 (1963) · Zbl 0122.25001
[25] Pöschel, R., A. Kalu\check znin, L.: Funktionen- und Relationenalgebren. Math. Monogra- phien 15, Deutscher Verlag der Wiss., Berlin (1979) · Zbl 0418.03044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.