Galois connection for multiple-output operations. (English) Zbl 1402.08002

The paper presents a generalization of a special type of Galois connection, namely, given a base set \(B\), instead of classes of operations \(f:B^n\longrightarrow B\), the partial, multi-valued functions \(f:B^n\longrightarrow B^m\), \(m\geq 0\) are considered. Functions \(f:B^k\longrightarrow M\) valued in partially ordered monoids \(M\) as invariants are also used. As main results the paper presents:
the main Galois connection between partial multi-valued multi-output functions and pomonoid-valued weight functions in its most general form;
variants of Galois connections for restricted classes of multi-output functions or weights;
Galois connections for classes of total multi-output functions;
a description of finitely generated subdirectly irreducible commutative monoids.


08A40 Operations and polynomials in algebraic structures, primal algebras
06F05 Ordered semigroups and monoids
06A15 Galois correspondences, closure operators (in relation to ordered sets)
Full Text: DOI arXiv


[1] Aaronson, S.: Classifying reversible gates. Theoretical Computer Science Stack Exchange (2014). http://cstheory.stackexchange.com/q/25730. Accessed 14 Mar 2018
[2] Aaronson, S., Grier, D., Schaeffer, L.: The classification of reversible bit operations (2015). arXiv:1504.05155(quant-ph) · Zbl 1404.68042
[3] Bloom, SL, Varieties of ordered algebras, J. Comput. Syst. Sci., 13, 200-212, (1976) · Zbl 0337.06008
[4] Bodnarchuk, VG; Kaluzhnin, LA; Kotov, VN; Romov, BA, Galois theory for post algebras. I, Cybernetics, 5, 243-252, (1969) · Zbl 0212.31802
[5] Bodnarchuk, VG; Kaluzhnin, LA; Kotov, VN; Romov, BA, Galois theory for post algebras. II, Cybernetics, 5, 531-539, (1969) · Zbl 0212.31802
[6] Burris, S.N., Sankappanavar, H.P.: A Course in Universal Algebra, Graduate Texts in Mathematics, vol. 78. Springer, New York (1981) · Zbl 0478.08001
[7] Couceiro, M; Chajda, Dorfer (ed.); Eigenthaler, Halaš (ed.); Müller, Pöschel (ed.), Galois connections for generalized functions and relational constraints, No. 16, 35-54, (2005), Klagenfurt
[8] Geiger, D, Closed systems of functions and predicates, Pac. J. Math., 27, 95-100, (1968) · Zbl 0186.02502
[9] Grillet, PA, On subdirectly irreducible commutative semigroups, Paci. J. Math., 69, 55-71, (1977) · Zbl 0387.20047
[10] Iskander, AA, Subalgebra systems of powers of partial universal algebras, Pac. J. Math., 38, 457-463, (1971) · Zbl 0234.08004
[11] Jaeger, G.: Quantum Information: An Overview. Springer, New York (2007) · Zbl 1166.81001
[12] Jeřábek, E.: Answer to [1]. Theoretical Computer Science Stack Exchange (2014). http://cstheory.stackexchange.com/a/25791. Accessed 14 Mar 2018
[13] Kerkhoff, S, A general Galois theory for operations and relations in arbitrary categories, Algebra Universalis, 68, 325-352, (2012) · Zbl 1283.06010
[14] Krasner, M.: Généralisation abstraite de la théorie de Galois. In: Algèbre et théorie des nombres, Paris 25. 9.-1. 10. 1949. Colloques Internationaux du Centre National de la Recherche Scientifique, vol. 24, pp. 163-168 (1950)
[15] Krasner, M, Abstract Galois theory and endotheory, I. Acta Sci. Math., 50, 253-286, (1986) · Zbl 0632.08001
[16] Mal’cev, AI, On homomorphisms onto finite groups, Uchen. Zap. Ivanov. Gos. Ped. Inst., 18, 49-60, (1958)
[17] Mal’cev, A.I.: Algebraic Systems, Die Grundlehren der mathematischen Wissenschaften, vol. 192. Springer, Berlin (1973). (Translated from Russian by B. D. Seckler and A. P. Doohovskoy (1973)) · Zbl 0186.02502
[18] Perumalla, K.S.: Introduction to Reversible Computing. Chapman and Hall/CRC, Computational Science Series, Boca Raton (2013)
[19] Pigozzi, D.: Partially ordered varieties and quasivarieties. Lecture notes (2004). http://orion.math.iastate.edu/dpigozzi. Accessed 14 Mar 2018
[20] Pöschel, R.: A General Galois Theory for Operations and Relations and Concrete Characterization of Related Algebraic Structures. Tech. Rep. R-01/80. Akademie der Wissenschaften der DDR, Zentralinstitut für Mathematik und Mechanik, Berlin (1980) · Zbl 0435.08001
[21] Post, E.L.: The Two-Valued Iterative Systems of Mathematical Logic. No. 5 in Annals of Mathematics Studies. Princeton University Press, Princeton (1941) · Zbl 0063.06326
[22] Rosenberg, IG, A classification of universal algebras by infinitary relations, Algebra Universalis, 1, 350-354, (1971) · Zbl 0243.08006
[23] Rosenberg, I.G.: Galois theory for partial algebras. In: R.S. Freese, O.C. Garcia (eds.) Universal Algebra and Lattice Theory. Lecture Notes in Mathematics, vol. 1004, pp. 257-272. Springer, Berlin (1983)
[24] Schein, BM, Homomorphisms and subdirect decompositions of semigroups, Pac. J. Math., 17, 529-547, (1966) · Zbl 0197.01603
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.