×

Binary relations and permutation groups. (English) Zbl 0823.03036

Summary: We discuss some new properties of the natural Galois connection among set relation algebras, permutation groups, and first order logic. In particular, we exhibit infinitely many permutational relation algebras without a Galois closed representation, and we also show that every relation algebra on a set with at most six elements is Galois closed and essentially unique. Thus, we obtain the surprising result that on such sets, logic with three variables is as powerful in expression as full first order logic.

MSC:

03G15 Cylindric and polyadic algebras; relation algebras
03B10 Classical first-order logic
06A15 Galois correspondences, closure operators (in relation to ordered sets)
08A40 Operations and polynomials in algebraic structures, primal algebras
20B99 Permutation groups

Software:

nauty
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Andréka, Michigan Math. J. 39 pp 371– (1992)
[2] , and , Expressibility of Properties of Relations. Math. Institute, Hungarian Academy of Science, 1994.
[3] and , Representations for Small Relation Algebras. Preprint, Department of Mathematics, Iowa State University, 1988.
[4] and , On Jönsson’s clones of operations on binary relations. In: Algebraic Logic (, and , eds.), North Holland Publ. Comp., Amsterdam 1991, pp. 431–442. · Zbl 0756.08002
[5] and , Permutation Groups and Combinatorial Structures. London Mathematical Society Lecture Notes Series 33, Cambridge University Press, Cambridge New York 1979. · Zbl 0415.05002
[6] A language for group theory. Technical Report, University of Sidney, 1987.
[7] Düntsch, J. Symbolic Computation. (1994)
[8] Fagin, Springer Lecture Notes in Computer Science 470 pp 3– (1987)
[9] Universal Algebra. 2nd ed. Springer-Verlag, Berlin-Heidelberg-New York 1979.
[10] Logic and the challenge of computer science. In: Trends in Theoretical Computer Science (ed.), Computer Science Press, Rockville, MD, 1988, pp. 1–57.
[11] Immerman, J. Computer System Science 25 pp 76– (1982)
[12] Immerman, SIAM J. Computing 16 pp 760– (1987)
[13] Immerman, In-formation and Computation 83 pp 121– (1989)
[14] Jönsson, Contemporary Mathematics 33 pp 299– (1984)
[15] The theory of binary relations. In: Algebraic Logic (, and , eds.), North Holland Publ. Comp., Amsterdam 1991, pp. 245–292. · Zbl 0760.03018
[16] Jönsson, Amer. J. Math. 74 pp 127– (1952)
[17] Nauty user guide. Technical Report TR-CS-90–02, Australian National University, 1990.
[18] McKenzie, Michigan Math. J. 17 pp 279– (1970)
[19] and , A Formalization of Set Theory without Variables. American Mathematical Society Colloquium Publications 41, Providence, RI, 1987. · Zbl 0654.03036
[20] Finite Permutation Groups. Academic Press, New York-London 1964. · Zbl 0138.02501
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.