Abstract
LetA be a finite set,n≥1 andD⊆A n. We say thatf :D →A is a functionally complete partial operation of size |D| if eachf*:A n →A agreeing withf onD is functionally complete. Such an operation of sized represents thus a family of\(|A|^{(|A|^n - d)} \) functionally complete operations. We investigate the least possible size of functionally complete partial groupoids. Such groupoids not defined on a row or column have size either |A|+1 or |A|+2 or are of size at least 2|A|−2. We prove that |A|+1 is the least size of such a groupoid and completely determine those of size |A|+1. As one might expect, these groupoids are very special. This study shows how surprisingly little information is needed to ensure that a groupoid is functionally complete and, at the same time, gives a description of large classes of functionally complete groupoids.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Berge, C.,Graphs and hypergraphs. North-Holland/American Elsevier, New York, 1973.
Csakany, B.,Homogeneous algebras are functionally complete. Algebra Univ.11 (1980), 149–158.
Fried, E. andPixley, A. F.,The dual discriminator function in universal algebra. Acta. Sci. Math. (Szeged)41 (1979), 83–100.
Hughes, D., Personal communication.
Mal'cev, A. I.,A strengthening of the theorem of Slupecki and Jablonskii (Russian, English Summary). Algebra i Logika (SEM)6 (3) (1967), 61–75. English translation inThe Metamathematics of Algebraic Systems. Collected papers 1936–1967, Studies in Logic and Foundations of Mathematics Vol. 66, North-Holland, Amsterdam, 1971.
Mullin, R. C., Personal communication.
Muzio, J. C.,Ternary two-place functions that are complete with constants. Proceedings 1975 Internat. Sympos. Multiple-Valued Logic (Bloomington, Ind.), 1975, pp. 27–33.
Pixley, A. F.,Functionally complete algebras generating distributive and permutable classes. Math. Z.114 (1970), 361–372.
Quackenbush, R. W.,Primality: The influence of Boolean algebras in universal algebra. Appendix No. 5 in G. Grätzer,Universal Algebra, 2nd edition, Springer, New York-Heidelberg-Berlin, 1979.
Rosenberg, I. G., La structure des fonctions de plusieurs variables sur un ensemble fini. C. R. Acad. Sci. Paris, Sér. A-B260 (1965), 3817–3819.
Rosenberg, I. G., Über die funktionale Vollstandigkeit in dem mehrwertigen Lohiken (Struktur der Funktionen von mehreren Veränderlichen auf endlichen Mengen). Rozpravy Cesk. Akad. Ved. Ser. Math. Nat. Sci.,80 (4) (1970), 3–93.
Rosenberg, I. G.,Completeness properties of multiple-valued logic algebras. InComputer Science and Multiple-Valued Logic, Theory and Applications, North-Holland, Amsterdam, 1977, pp. 144–186.
Rosenberg, I. G.,On generating large classes of Sheffer functions. Aequationes Math.17 (1978), 164–181.
Rosenberg, I. G.,Cyclic structure of affine transformations of vector spaces over GP(P). Preprint CRM-863, Montreal, 1979.
Rosenberg, I.G.,Functional completeness of single generated or surjective algebras. InFinite Algebra and Multiple-Valued Logic, Colloq. Math. Soc. János Bolyai, Vol. 28, North-Holland, 1981, pp. 635–652.
Rosenberg, I. G.,Large classes of functionally complete groupoids II. Proceedings 11th Internat. Sympos. Multiple-Valued Logic (IEEE, Oklahoma, May 1981), 259–262.
Rousseau, G.,Completeness in finite algebras with a single operation. Proc. Amer. Math. Soc.18 (1967), 1009–1013.
Szábó, L. andSzendrei, A.,Almost all algebras with triply transitive automorphism groups are functionally complete. Acta Sci. Math.41 (1979), 391–402.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Muzio, J.C., Rosenberg, I.G. Large classes of functionally complete groupoids I. Aeq. Math. 25, 274–288 (1982). https://doi.org/10.1007/BF02189623
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02189623