Premium
Binary Relations and Permutation Groups
Author(s) -
Andréka Hajnal,
Düntsch Ivo
Publication year - 1995
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19950410207
Subject(s) - mathematics , galois connection , permutation (music) , binary relation , cyclic permutation , galois group , embedding problem , partial permutation , relation (database) , connection (principal bundle) , set (abstract data type) , algebra over a field , discrete mathematics , pure mathematics , symmetric group , computer science , data mining , physics , geometry , acoustics , programming language
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.